Contraflow network reconfiguration for evacuation planning: A summary of results

Sangho Kim, Shashi Shekhar

Research output: Contribution to conferencePaper

50 Scopus citations

Abstract

Contraflow, or lane reversal, is a way of increasing outbound capacity of a real network by reversing the direction of inbound roads during evacuations. The contraflow is considered a potential remedy to solve congestions during evacuations in context of homeland security and natural disasters (e.g., hurricanes). Currently available contraflow algorithms only tackle a single-source and multiple-destinations situation. These approaches cannot handle a multiple-sources problem which is harder due to conflicts across the optimal paths from different sources. We formally define the evacuation situations using graph and flow theory and show the NP-completeness of the contraflow problem. We propose two capacity-aware global contraflow heuristics that produce contraflow configuration in the presence of conflicts among routes preferred by different source nodes. We evaluate proposed heuristics experimentally using synthetic networks as well as real world datasets. In addition, we provide algebraic cost model. Experimental results show that our contraflow heuristics can reduce evacuation time by 30% or more.

Original languageEnglish (US)
Pages250-259
Number of pages10
StatePublished - Dec 1 2005
EventGIS'05: Proceedings of the 13th ACM International Workshop on Geographic Information Systems - Bremen, Germany
Duration: Nov 4 2005Nov 5 2005

Other

OtherGIS'05: Proceedings of the 13th ACM International Workshop on Geographic Information Systems
CountryGermany
CityBremen
Period11/4/0511/5/05

Keywords

  • Combinatorial optimization
  • Contraflow
  • Evacuation planning
  • Lane reversal
  • Simulated annealing
  • Time expanded graph

Fingerprint Dive into the research topics of 'Contraflow network reconfiguration for evacuation planning: A summary of results'. Together they form a unique fingerprint.

  • Cite this

    Kim, S., & Shekhar, S. (2005). Contraflow network reconfiguration for evacuation planning: A summary of results. 250-259. Paper presented at GIS'05: Proceedings of the 13th ACM International Workshop on Geographic Information Systems, Bremen, Germany.