Towards Optimal and Scalable Evacuation Planning Using Data-driven Agent Based Models

Evacuation planning is a crucial part of disaster management where the goal is to relocate people to safety and minimize casualties. Every evacuation plan has two essential components: routing and scheduling. However, joint optimization of these two components with objectives such as minimizing average evacuation time is a computationally hard problem. To approach it, we present MIP- LNS, a scalable optimization method that can optimize a variety of objective functions. We also present the method MIP-LNS-SIM, where we combine agent-based simulation with MIP-LNS to more accurately estimate delays on roads due to congestion. We use Harris County in Houston, Texas as our study area. We show that, within a given time limit, MIP-LNS finds better solutions than existing methods in terms of three different metrics. We also perform experiments with MIP-LNS-SIM to show its efficacy in estimating delays due to congestion. Our results show that, when such delays are considered, MIP-LNS-SIM can find better evacuation plans than MIP-LNS. Furthermore, MIP-LNS-SIM provides an estimate of the evacuation completion time for its plan with a small percent error.

Authors

• Kazi Ashik Islam Biocomplexity Institute, University of Virginia
• Da Qi Chen Biocomplexity Institute, University of Virginia
• Madhav Marathe
• Henning Mortveit Virginia Tech
• Samarth Swarup University of Virginia
• Anil Vullikanti Computer Science Dept., University of Virginia Biocomplexity Institute, University of Virginia

Keywords

• Evacuation
• Routing
• Scheduling
• Agent Based Simulation
• NP-hard
• Mixed Integer Program
• Heuristic
• Large Neighborhood Search