Welcome to our project page
Evacuation Route Planning (ERP) has grown ever more imperative due to the increasing impact of natural disasters and threats of terrorism on modern infrastructure. To help mitigate loss due to these and similar large-scale situations such as nuclear disasters, ERP tasks are becoming more complex. Other complicating elements include increasing population densities, larger structures within urban environments served by multifaceted transportation networks. Because of the multitude of factors, all driving the problem toward greater scales, the ability to handcraft ideal ERPs has become nearly infeasible. This has led emergency planners to turn to artificial intelligence algorithms to quickly generate optimal paths for large-scale civilian evacuations under multiple scenarios. Multi-Party Capacity Constrained Route Planning (MPCCRP) is project geared towards developing a modified version of the original CCRP algorithm for multiple parties with separate objectives. Such scenarios include civilian evacuation route planning with additional emergency response coordination.
Contents
Overview
What does Capacity Constrained mean or what does it look like?
The figures below are visual representations of our capacity constrained networks used for our testing.
Node numbers represent maximum capacity, denoted by the size of the shaded blue outline and population colored red for evacuation zone and orange for an existing responder.
The edge numbers represent edge capacity denoted by edge width and travel time denoted by green to yellow for fast to slow.
Endangered Capacity Constrained Graph
|
Evacuated Capacity Constrained Graph
|
Large-Scale Graph With Responders
|
Evacuated Graph With Responders
|
So how does CCRP work?
For any type of evacuation agenda, zones defining both hazards and havens are defined, giving an evacuee route planner a set of endangered sources and refuge destinations. From there, we generate evacuation plans for all the evacuees while minimizing total evacuation time. CCRP does this by calculating the quickest possible route at the soonest possible time given a list of sources and destinations. This is done by generating a single pair fictitious super-source and super-destination vertices that connect to the list of sources and destinations respectively.
This allows for a simple search such as Dijkstra's algorithm to solve for the quickest path between the two super vertices using edge travel time as the weight criteria. Once this path is found, the maximum flow along that path is calculated by determining the minimum of the three parameters i.e. current source population, minimum available edge and node capacity along the path. Bookkeeping for available capacities within the graph is done to allow the algorithm to check and update reservations along the path. If the quickest path at the current start time has no more available capacity, it repetitively looks into the future and checks for available capacity along same path again.
How is MPCCRP diffrent?
MPCCRP is an expansion off CCRP by simply taking the idea of super sources and super destinations just a step further by introducing sub sources and sub destinations that are affiliated with the locations or nodes of each party. These sub sources serve as an intermediary between the capacity constrained network and the fictitious super nodes.
CCRP vs MPCCRP
|
Ok, Show me some cool stuff!
I wish I could get matplotlib to successfully save a GIF file showing an animation of executing the emergency route plan, specifically rendering the migration of both evacuees and responders to their designated destinations. But in the meantime, go check it out by simply running the MPCCRP iPython Notebook listed down in the Code section on your computer.
Documentation
Our project documentation can be found here:
Documentation
Our original paper of our supporting work in developing MPCCRP can be found here:
Civilian Evacuation and Route Planning Coordinated with Emergency Response
Our project poseter can be found here:
Click to view PDF
|
Code
A web-based interactive example of our code can be seen here using Python Notebook:
Web Demo
Our original Python code and examples can also be found at our GitHub repo:
MPCCRP Repo
Authors
Ruffin White (@ruffsl)
Varun Murali (@pjhyett)
References
[1] S. Shekhar, K. Yang, V. M. Gunturi, L. Manikonda, D. Oliver, X. Zhou, B. George, S. Kim, J. M. Wolff, and Q. Lu, “Experiences with evacuation route planningalgorithms, ”International Journal of Geographical Information Science, vol. 26, no. 12, pp. 2253–2265, Dec. 2012. [Online]. Available: http://www.tandfonline.com/doi/abs/10.1080/13658816.2012.719624
[2] F. Itwm, “Mathematical Modelling of Evacuation Problems : A State of Art,” vol. 24, no. 24, 2001.
[3] B. George and S. Shekhar, “Time-Aggregated Graphs for Modeling,” pp.85–99, 2006.