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:
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).
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.
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.)
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.
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
Temporal Databases).
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.
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.
Forces of Nature,
Inventing Tomorrow, Institute of Technology, 30(1), Winter 2006 (pp. 36-38).
Republished
article in
UMN News, University of Minnesota, April 6th, 2006.
S. Shekhar, and Q. Lu,
Evacuation Planning for Homeland Security
,
Homeland Security Emergency Management Metro Regions Newsletter,
Volume 18,
October 2004,
Minnesota Public Safety.
