Experiences with evacuation route planning algorithms

Abstract

Efficient tools are needed to identify routes and schedules to evacuate affected populations to safety in the event of natural disasters. Hurricane Rita and the recent tsunami revealed limitations of traditional approaches to provide emergency preparedness for evacuees and to predict the effects of evacuation route planning (ERP). Challenges arise during evacuations due to the spread of people over space and time and the multiple paths that can be taken to reach them; key assumptions such as stationary ranking of alternative routes and optimal substructure are violated in such situations. Algorithms for ERP were first developed by researchers in operations research and transportation science. However, these proved to have high computational complexity and did not scale well to large problems. Over the last decade, we developed a different approach, namely the Capacity Constrained Route Planner (CCRP), which generalizes shortest path algorithms by honoring capacity constraints and the spread of people over space and time. The CCRP uses time-aggregated graphs to reduce storage overhead and increase computational efficiency. Experimental evaluation and field use in Twin Cities Homeland Security scenarios demonstrated that CCRP is faster, more scalable, and easier to use than previous techniques. We also propose a novel scalable algorithm that exploits the spatial structure of transportation networks to accelerate routing algorithms for large network datasets. We evaluated our new approach for large-scale networks around downtown Minneapolis and riverside areas. This article summarizes experiences and lessons learned during the last decade in ERP and relates these to Professor Goodchild's contributions.

Keywords:

• evacuation route planning
• emergency response

Acknowledgments

This article is based on the work supported by the National Science Foundation under Grant Nos. 1029711, III-CXT IIS-0713214, IGERT DGE-0504195, and CRI:IAD CNS-0708604 and the US Department of Defense (USDOD) under Grant Nos. HM1582-08-1-0017, HM1582-07-1-2035, and W9132V-09-C-0009. We would like to thank Kim Koffolt, Pradeep Mohan, Mike Evans, Ravdeep Singh Gill, and the members of the University of Minnesota Spatial Database and Spatial Data Mining Research Group for their comments.