- For General Audience:
summary (pdf) ,
- For Computer Science Audience:
ABSTRACT for general audience:
Evacuation planning is critical for important applications, e.g., emergency management, to evacuate
affected populations to safety in the event of natural disasters, industrial accidents or terrorist
attacks. Currently, evacuation plans are often hand-crafted using table-top exercises. These rely on
participantsí knowledge of local transportation networks and populations as well skills to evaluate
alternative routes by travel times, capacities and transportation chokepoints. These are time and labor
intensive as well as expensive limiting the number of scenarios during planning and adjustments to
unanticipated events during disaster repose. Computerized tools may help address these limitations. In
addition, these may recommend novel routes not yet considered and assist with alternative strategies
(e.g., contraflow, phased evacuation).
Traditional computerized methods for evacuation route (and schedule) planning are based on either linear
programming paradigm or game-theoretic models (e.g., Wardrop equilibrium) of commuter traffic. These are
effective for small scenarios, e.g., small office building, villages and small towns. However, these do
not scale up to large (e.g., >50,000 nodes) transportation networks as they use either microscopic
simulations or time-expanded networks requiring large amount of computer storage and incurring
exorbitant computational costs. We describe a novel geo-spatial approach, namely Capacity Constrained
Route Planning (CCRP) approach, to quickly identify feasible evacuation plans. This approach can provide
an efficient decision support tool for emergency management officials to evaluate existing evacuation
plans or to determine novel plausible evacuation plans for large-scale evacuation scenario.
We also discuss case-studies for scenarios relating to Nuclear Power Plant, large metropolitan areas and
large gatherings. First case study with 10-mile radius evacuation zone around Monticello nuclear power
plant near Minneapolis/St. Paul Twin Cities metropolitan area showed that computerized methods lowered
evacuation time by almost 30% relative to existing hand-crafted plans by relieving transportation
bottleneck chokepoints and by choosing shorter routes. Second case study with numerous homeland security
scenarios in Minneapolis/St. Paul metropolitan area spanning hundreds of square mile and over 2 Million
people studied effects of incident locations, shelter choices, transportation modes (driving, public
transportation, walking), incident locations, incident time of the day, transportation networks etc. It
helped identify areas which are difficult to evacuation and may need enrichment of transportation
networks. It also showed that walking able-bodied the first mile often speeded up evacuation
significantly. A third case study in context of Minnesota state fair, a gathering of 100,000 to 125,000
people, reconfirmed the value of walking able-bodied about a mile in speeding up evacuation. Another
case study is in progress with Hajj scenarios near Mecca, Saudi Arabia.
ABSTRACT for Computer Science Audience:
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
real and synthetic transportation networks show that the proposed approach
scales up to much larger networks, where software based on linear programming
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.
Evacuation, Routing, Shortest path, Capacity constraints,
Emergency planning, Homeland defense, Intelligent Transportation Systems.
Following recent technical publications uncover details of the
results discussed in this talk:
- Intelligent Shelter Allotment for Emergency Evacuation Planning: A Case Study of Makkah,
Intelligent Systems, IEEE, 30(5):66-76, September-October, 2015.
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
International Journal of Geographical Information Science, 26(12), pp: 2253-2265,
Taylor and Francis, December 2012.
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).
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
Technical Report No. P1104-T1,
Center of Research Excellence in Hajj and Omrah (Hajjcore),
Umm Al-Qura University, Makkah, Saudi Arabia,
- Q. Lu, B. George, S. Shekhar,
Capacity Constrained Routing Algorithms for Evacuation Planning:
A Summary of Results (
local pdf ,
9th Intl. Symposium on Spatial and Temporal Databases, 2005,
Springer LNCS 3633 ,
(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.)
- 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
It is also detailed in a related
Mn/Dot report 2006-21 from
Center for Transportation Studies, University of Minnesota.
summary of results appeared in Proc. ACMGIS 2005.
- 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.
- 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
- S. Shekhar, Q. Lu, S. Kim,
A Novel Approch to Evacuation Route Planning,
in Army AHPCRC Research Center Bulletin, 15(4), 2005.
- 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.
- Q. Lu, Y. Huang and S. Shekhar,
A Capacity Constrained Routing Approach ,
in Proceeding of the
1st NSF/NIJ Symposium on Intelligence and Security
Tucson, Arizona, June 2-3, 2003.
Following general interest publications highlight
some of the results discussed in this talk:
Evacuation project wins award
The CTS Report,
Center for Transportation Systems,
University of Minnesota, May 2006.
- News media coverage:
Fox TV (channel 9, KMSP) evening news on Monday May 8th 2006.
The video-clip (about 4 minutes 40 seconds) :
avi - 65Mb
quicktime H.264 - 128Mb
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.
Pioneer Press , March 9th, 2006:
``Walk, don't drive, to safety: State officials reveal details if disaster hits" .
Office for Public Engagement,
University of Minnesota :
entry on March 14th on
Vice President's blog
about article in Pioneer Press.
Star Tribune , September 11th, 2005:
``Agencies planning for worst in Cities" .
- Take Heed and Change Direction, Page 13 of
Research: An annual publication of the Office of the Vice President for Research
University of Minnesota.
Legacy Magazine, University of Minnesota Foundation,
- Forces of Nature,
Inventing Tomorrow, Institute of Technology, 30(1), Winter 2006 (pp. 36-38).
UMN News, University of Minnesota, April 6th, 2006.
Evacuation Planning using Virtual Earth ,
Microsoft Development Network Blogs, May 8th, 2008.
Evacuation research nets additional federal funds ,
CTS Report, Center for Transportation Studies, October 2007.
- The Minnesota Daily, University of Minnesota, November 22nd, 2010:
U prof develops software to plan evacuations .
Can we improve evacuation planning? ,
Computer Science & Engineering Discoveries, University of Minnesota: Driven to Discover, 2011.
- S. Shekhar, and Q. Lu,
Evacuation Planning for Homeland Security
Homeland Security Emergency Management Metro Regions Newsletter,
Minnesota Public Safety.
- S. Shekhar, Evacuation Planning for Homeland Defense,
an invited presentation at the
UCGIS Congressional Breakfast on Homeland Security and GIS, ,
February 2004 (
CTS Report published a
brief coverage of the event.
Directions Magazine also published an
article describing this event.
Efficient Evacuation Route Planning and Emergency Management ,
Office of Technology Commercialization, University of Minnesota.