TITLE:

Evacuation Route Planning: Novel Spatio-temporal Network Models and Algorithms

PRESENTER:

Shashi Shekhar : Biography , Homepage , Picture

AFFILIATION:

Computer Science Department, University of Minnesota.

URL:

http://www.cs.umn.edu/~shekhar

SLIDES:

ABSTRACT:

Efficient tools are needed to identify routes and schedules to evacuate affected populations to safety in face of natural disasters or terrorist attacks. Challenges arise due to violation of key assumptions (e.g. stationary ranking of alternative routes, Wardrop equilibrium) behind popular shortest path algorithms (e.g. Dijktra's, A*) and microscopic traffic simulators (e.g. DYNASMART). Time-expanded graphs (TEG) based mathematical programming paradigm does not scale up to large urban scenarios due to excessive duplication of transportation network across time-points. We present a new approach, namely Capacity Constrained Route Planner (CCRP), advancing ideas such as Time-Aggregated Graph (TAG) and an ATST function to provide earliest-Arrival-Time given any Start-Time. Laboratory experiments and field use in Twincities for DHS scenarios (e.g. Nuclear power plant, terrorism) show that CCRP is much faster than the state of the art. A key Transportation Science insight suggests that walking the first mile, when appropriate, may speed-up evacuation by a factor of 2 to 3 for many scenarios. Geographic Information Science (e.g. Time Geography) contributions include a novel representation (e.g. TAG) for spatio-temporal networks. Computer Science contributions include graph theory limitations (e.g. non-stationary ranking of routes, non-FIFO behavior) and scalable algorithms for traditional routing problems in time-varying networks, as well as new problems such as identifying the best start-time (for a given arrival-time deadline) to minimize travel-time.

Experiments with real and synthetic transportation networks show that the proposed approach scales up to much larger networks, where software based on linear programming method crashes. Evaluation of our methods for evacuation planning for a disaster at the Monticello nuclear power plant near Minneapolis/St. Paul Twin Cities metropolitan area shows that the new methods lowered evacuation time relative to existing plans by identifying and removing bottlenecks, by providing higher capacities near the destination and by choosing shorter routes. In 2005, CCRP was used for evacuation planning (transportation component) for the Minneapolis-St. Paul twin-cities metropolitan area. It facilitated explorations of scenarios (e.g. alternative locations and times) as well as options (e.g. alternative transportation modes of pedestrian and vehicle). It also led to an interesting discovery that walking able-bodied evacuees (instead of letting them drive) reduces evacuation time significantly for small area (e.g. 1-mile radius) evacuations.

In future work, we plan to formally characterize the quality of solutions identified by the CCRP approach. We will explore new ideas, e.g. phased evacuations and contra-flow, to further reduce evacuation times. In addition, we would like to improve modeling of other transportation modes such as public transportation.

KEYWORDS: Evacuation, Routing, Shortest path, Capacity constraints, Emergency planning, Homeland defense, Intelligent Transportation Systems.

NOTE 1: 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 Mangement , , Office of Technology Commercialization University of Minnesota.

NOTE 2: Following recent technical publications uncover details of the results discussed in this talk:
  1. A scientific approach to evacuation planning , The Sensor Newsletter, Volume 6, Number 3, Intelligent Transportation Systems Institute, University of Minnesota, Winter 2006. Also highlighted ( see this link ) by Office of the Vice President of Research at the University of Minnesota.
  2. 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).
  3. 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.
  4. 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–303, 2007.)
  5. 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.
  6. 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.
  7. 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).
  8. S. Shekhar, Q. Lu, S. Kim, A Novel Approch to Evacuation Route Planning, in Army AHPCRC Research Center Bulletin, 15(4), 2005.
  9. 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.
  10. 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.