Evacuation Route Planning: Capacity Constrained Routing Approach


Shashi Shekhar : Biography , Homepage


Computer Science Department, University of Minnesota.





Evacuation planning is critical for numerous important applications, e.g. disaster emergency management and homeland defense preparation. Efficient tools are needed to produce evacuation plans that identify routes and schedules to evacuate affected populations to safety in the event of natural disasters or terrorist attacks. Current methods are based on linear programming paradigm and suffer from two limitations. First, they may not scale up to large (e.g. 100,000 nodes and 1 Million people) transportation networks in urban scenarios as they use time-expanded networks requiring large amount of computer storage and aim at computing optimal path incurring exorbitant computational costs. Second, they require users to provide an estimate of an upper bound on the total evacuation time. Incorrect estimate may lead to failure of the paradigm.

We present a new heuristic approach, namely Capacity Constrained Route Planner (CCRP), to quickly identify feasible evacuation plan. This method may be used to provide an upper bound on optimal evacuation time for the methods based on linear programming paradigm. Alternatively, our method may be used to determine plausible evacuation plans for very large transportation networks when resource constraints or dynamic conditions make it infeasible or uninteresting to determine the optimal routes. Proposed CCRP approach models has two key ideas. First, it models node/edge attributes as functions of time rather than fixed numbers. Thus node/edge capacities, node occupancies, etc. are modeled as time-series. Second, it iteratively considers all pairs of sources and destinations. In each iteration, it schedules evacuation of a group of evacuees across the closest source-destination pair. Special graphs construction is used eliminate redundant computation in this step. 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. For smaller networks, where software based on linear programming can be used, CCRP produces high quality solutions with evacuation times comparable to those achieved by linear programming methods.

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 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). In future work, we plan to formally characterize the quality of solutions identified by the CCRP approach. In addition, we will explore new ideas, e.g. phased evacuations and contra-flow, to further reduce evacuation times.


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


Some of the results discussed in this talk appeared in the following recent technical and general interest publications:
  1. ``Walk, don't drive, to safety: State officials reveal details if disaster hits" , Pioneer Press , March 9th, 2006 and a blog entry on March 14th by U of M public engagement leadership.
  2. A scientific approach to evacuation planning , The Sensor Newsletter, Volume 6, Number 3, Intelligent Transportation Systems Institute, University of Minnesota, Winter 2005.
  3. Q. Lu, B. George, S. Shekhar, Capacity Constrained Routing Algorithms for Evacuation Planning: A Summary of Results , Proc. 9th Intl. Symposium on Spatial and Temporal Databases, 2005.
  4. S. Shekhar, and Q. Lu, Evacuation Planning for Homeland Security , Homeland Security Emergency Management Metro Regions Newsletter, Volume 18, October 2004, Minnesota Public Safety.
  5. 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.
  6. 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)).
  7. 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.