Evacuation route planning: Scalable heuristics

Sangho Kim, Betsy George, Shashi Shekhar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

80 Scopus citations

Abstract

Given a transportation network, a vulnerable population, and a set of destinations, evacuation route planning identifies routes to minimize the time to evacuate the vulnerable population. Evacuation route planning is a vital components of efforts by civil authorities to prepare for both natural and man-made disasters (e.g., hurricanes, terrorist acts, etc). However, evacuation route planning is computationally challenging due to the size of transportation networks, the large number of evacuees, and capacity constraints. For example, the number of evacuees often far exceeds the bottleneck capacity, i.e., the minimum cut of a given network. Current approaches (e.g., linear programming and Capacity Constrained Route Planner (CCRP), a recently proposed evacuation planning algorithm) do not scale well because of intensive computation needs in order to produce the schedules of evacuees as well as routing plans. This paper presents innovative heuristics scalable to very large transportation networks. The Intelligent Load Reduction heuristic accelerates the routing computation by the reduction of evacuees using the bottleneck saturation. The performance of Intelligent Load Reduction is evaluated using real world scenarios. Results show that the Intelligent Load Reduction heuristic significantly improve the runtime of CCRP. We propose another heuristic named Incremental Data Structure. While the Intelligent Load Reduction gains performance increase by giving up the schedules of evacuees, the Incremental Data Structure heuristic can reduce calculation time of the CCRP algorithm by the enhanced data structures without affecting the outputs.

Original languageEnglish (US)
Title of host publicationProceedings of the 15th ACM International Symposium on Advances in Geographic Information Systems, GIS 2007
Pages146-153
Number of pages8
DOIs
StatePublished - 2007
Event15th ACM International Symposium on Advances in Geographic Information Systems, GIS 2007 - Seattle, WA, United States
Duration: Nov 7 2007Nov 9 2007

Publication series

NameGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems

Other

Other15th ACM International Symposium on Advances in Geographic Information Systems, GIS 2007
Country/TerritoryUnited States
CitySeattle, WA
Period11/7/0711/9/07

Keywords

  • algorithm
  • evacuation route planning
  • spatial network

Fingerprint

Dive into the research topics of 'Evacuation route planning: Scalable heuristics'. Together they form a unique fingerprint.

Cite this