Evacuation Route Planning: Scalable Algorithms and Case Studies


Shashi Shekhar : Biography , Homepage , Picture


Computer Science Department, University of Minnesota.




ABSTRACT for general audience:

Evacuation planning is critical for emergency preparation and response to move vulnerable population to safety in the event of natural or man-made disasters. Hand-crafting evacuation routes is labor-intensive limiting number of planning scenarios and adjustments to unanticipated events during response. Traditional computerized evacuation route planning based on linear programming or game-theory (e.g., Wardrop equilibrium of commute traffic) do not scale up to large events and cities. To overcome these limitations, we describe the capacity constrained route planner (CCRP) approach with novel data-structures (e.g., time-aggregated graphs) and algorithms (e.g., generalized shortest path algorithm). We share case studies evaluating CCRP for scenarios related to Monticello nuclear plant, and Minnesota state fair. CCRP was used for numerous homeland security scenarios in Minneapolis/St. Paul metropolitan area, where it helped identify difficult-to-evacuate areas needing enrichment of transportation networks. It also showed that walking able-bodied the first mile often speeded up evacuation significantly. Recently, it was used for shelter allocation in Hajj (Mecca).

KEYWORDS: Evacuation, Routing, Shortest path, Capacity constraints, Emergency planning, Homeland defense, Intelligent Transportation Systems.
NOTE 1: Following recent technical publications uncover details of the results discussed in this talk:
  1. Intelligent Shelter Allotment for Emergency Evacuation Planning: A Case Study of Makkah, (pdf at publisher and at local server ), Intelligent Systems, IEEE, 30(5):66-76, September-October, 2015. (doi: 10.1109/MIS.2015.39).
  2. S. Shekhar, K. S. Yang, V. Gunturi, L. Manikonda, D. Oliver, X. Zhou, B. George, S. Kim, J. Wolff, Q. S. Lu, Experiences with evacuation route planning algorithms (pdf at publisher and at local server ), International Journal of Geographical Information Science, 26(12), pp: 2253-2265, Taylor and Francis, December 2012.
  3. X. Zhou, B. George, S. Kim, J. Wolff, Q. Lu, S. Shekhar, Evacuation Planning: A Spatial Network Database Approach. , IEEE Data Eng. Bulletin, 33(2): 26-31 (2010).
  4. K. Yang, F. Ur Rehman, H. Lahza, S. Basalamah, S. Shekhar, I. Ahmed, and A. Ghafoor, Intelligent Shelter Allotment for Emergency Evacuation Planning: A Case Study of Makkah , Technical Report No. P1104-T1, Center of Research Excellence in Hajj and Omrah (Hajjcore), Umm Al-Qura University, Makkah, Saudi Arabia, Oct. 2012.
  5. Q. Lu, B. George, S. Shekhar, Capacity Constrained Routing Algorithms for Evacuation Planning: A Summary of Results ( local pdf , SpringerLink page ), Proc. 9th Intl. Symposium on Spatial and Temporal Databases, 2005, Springer LNCS 3633 , isbn: 3-540-28127-4. (Full paper titled Evacuation route planning: a case study in semantic computing appeared in Int. J. Semantic Computing, vol. 1, no. 2, pp. 249\226303, 2007.)
  6. S. Kim, S. Shekhar, M. Min, Contraflow Transportation Network Reconfiguration for Evacuation Route Planning, IEEE Transactions on Knowledge and Data Eng., 20(8): 1115-1129, 2008 ( local pdf, ieeexplore.ieee.org link). It is also detailed in a related Mn/Dot report 2006-21 from Center for Transportation Studies, University of Minnesota. A summary of results appeared in Proc. ACMGIS 2005.
  7. S. Kim, B. George, and S. Shekhar, Evacuation Route Planning: Scalable Heuristics , Proceedings of the 15th annual ACM International Symposium on Advances in Geographic Information Systems, 2007.
  8. B. George, S. Shekhar, and S. Kim, Spatio-temporal Network Databases and Routing Algorithms, University of Minnesota - CSE TR 08-039, 2008. (A summary of results appeared in 2007 Symposium on Spatial and Temporal Databases).
  9. S. Shekhar, Q. Lu, S. Kim, A Novel Approch to Evacuation Route Planning, in Army AHPCRC Research Center Bulletin, 15(4), 2005.
  10. Q. Lu, S. Shekhar, Capacity Constrained Routing for Evacuation Planning, in Proceeding of Intelligent Transportation Systems Safety and Security Conference, Miami, Florida, March 24-25, 2004.
  11. Q. Lu, Y. Huang and S. Shekhar, Evacuation Planning: A Capacity Constrained Routing Approach , in Proceeding of the 1st NSF/NIJ Symposium on Intelligence and Security Informatics, Tucson, Arizona, June 2-3, 2003.

NOTE 2: Following general interest publications highlight some of the results discussed in this talk:
  1. Evacuation project wins award , The CTS Report, Center for Transportation Systems, University of Minnesota, May 2006.
  2. News media coverage:
  3. S. Shekhar, and Q. Lu, Evacuation Planning for Homeland Security , Homeland Security Emergency Management Metro Regions Newsletter, Volume 18, October 2004, Minnesota Public Safety.
  4. S. Shekhar, Evacuation Planning for Homeland Defense, an invited presentation at the UCGIS Congressional Breakfast on Homeland Security and GIS, , February 2004 ( abstract (html), slides (ppt)). CTS Report published a brief coverage of the event. Directions Magazine also published an article describing this event.
  5. Efficient Evacuation Route Planning and Emergency Management , Office of Technology Commercialization, University of Minnesota.