Decision Support System for Evacuation Route-Schedule Planning: Determining Optimal Network Configuration

Principal Investigator(s):

Shashi Shekhar, McKnight Distinguished Professor, Computer Science and Engineering

Project summary:

Given a transportation network having source nodes with evacuees and destination nodes, the researchers aimed to find a contraflow network configuration, i.e., ideal direction for each edge, to minimize evacuation time. Contraflow is considered a potential way to reduce congestion during evacuations in the context of homeland security and natural disasters (e.g., hurricanes). This problem is computationally challenging because of the very large search space and the expensive calculation of evacuation time on a given network. To the best of the researchers' knowledge, this work presents the first macroscopic approaches for the solution of contraflow network reconfiguration, incorporating road capacity constraints, multiple sources, the congestion factor, and scalability. The researchers formally defined the contraflow problem based on graph theory and provide a framework of computational structure to classify their approaches. A "Greedy" heuristic was designed to produce high-quality solutions with significant performance. A "Bottleneck Relief" heuristic was developed to deal with large numbers of evacuees. They evaluated the proposed approaches both analytically and experimentally using real-world data sets. Experimental results show that their contraflow approaches can reduce evacuation time by 40 percent or more.

Project details:

  • Project number: 2004006
  • Start date: 06/2004
  • Project status: Completed
  • Research area: Transportation Safety and Traffic Flow
  • Topics: Data and modeling, Planning