Contraflow transportation network reconfiguration for evacuation route planning

Sangho Kim, Shashi Shekhar, Manki Min

Research output: Contribution to journalArticlepeer-review

137 Scopus citations

Abstract

Given a transportation network having source nodes with evacuees and destination nodes, we want to find a contraflow network configuration (that is, ideal direction for each edge) to minimize the evacuation time. Contraflow lane reversal is considered a potential remedy to reduce congestion during evacuations in the context of homeland security and natural disasters (for example, hurricanes). This problem is computationally challenging because of the very large search space and the expense of calculating the evacuation time on a given network. To our knowledge, this paper presents the first macroscopic approaches for the solution of a contraflow network reconfiguration incorporating road capacity constraints, multiple sources, congestion, and scalability. We formally define the contraflow problem based on graph theory and provide a framework of computational structure to classify our approaches. A Greedy heuristic is designed to produce high-quality solutions with significant performance. A Bottleneck Relief heuristic is developed to deal with large numbers of evacuees. We evaluate the proposed approaches both analytically and experimentally using real-world data sets. Experimental results show that our contraflow approaches can reduce the evacuation time by 40 percent or more.

Original languageEnglish (US)
Article number4384487
Pages (from-to)1115-1129
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume20
Issue number8
DOIs
StatePublished - Aug 2008

Bibliographical note

Funding Information:
The authors are particularly grateful to the members of the Spatial Database Research Group at the University of Minnesota for their helpful comments and valuable discussions. The authors’ evacuation research members, including Qingsong Lu and Betsy George, gave them especially valuable comments. The ArcGIS Network Analyst and geodatabase teams at ESRI have given the authors a chance to implement the ideas in this paper on their GIS development framework. Kim Koffolt and ESRI helped the authors improve the readability of the paper. They are thankful for the use of the program RelaxIV, developed by the CRIFOR research group, and CS, developed by A. Goldberg. This work was supported by a grant (Contract 81655) from the Minnesota Department of Transportation.

Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

Keywords

  • Contraflow
  • Graph algorithms
  • Heuristics design
  • Optimization

Fingerprint

Dive into the research topics of 'Contraflow transportation network reconfiguration for evacuation route planning'. Together they form a unique fingerprint.

Cite this