An official website of the United States government
Evacuation planning is a crucial part of disaster management. However, joint optimization of its two essential components, routing and scheduling, with objectives such as minimizing average evacuation time or evacuation completion time, is a computationally hard problem. To approach it, we present MIP-LNS, a scalable optimization method that utilizes heuristic search with mathematical optimization and can optimize a variety of objective functions. We also present the method MIPLNS-SIM, where we combine agent-based simulation with MIP-LNS to estimate delays due to congestion, as well as, find optimized plans considering such delays. 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. However, when congestion dependent delay is considered, MIP-LNS-SIM outperforms MIP-LNS in multiple performance metrics. In addition, MIP-LNS-SIM has a significantly lower percent error in estimated evacuation completion time compared to MIP-LNS.
more »
« less
Data-driven Agent-based Models for Optimal Evacuation of Large Metropolitan Areas for Improved Disaster Planning
ABSTRACT Evacuation plans are designed to move people to safety in case of a disaster. It mainly consists of two components: routing and scheduling. Joint optimization of these two components with the goal of minimizing total evacuation time is a computationally hard problem, specifically when the problem instance is large. Moreover, often in disaster situations, there is uncertainty regarding the passability of roads throughout the evacuation time period. In this paper, we present a way to model the time-varying risk associated with roads in disaster situations. We also design a heuristic method based on the well known Large Neighborhood Search framework to perform the joint optimization task. We use real-world road network and population data from Harris County in Houston, Texas and apply our heuristic to find evacuation routes and schedules for the area. We show that the proposed method is able to find good solutions within a reasonable amount of time. We also perform agent-based simulations of the evacuation using these solutions to evaluate their quality and efficacy.
more »
« less
- PAR ID:
- 10403915
- Date Published:
- Journal Name:
- Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems
- Page Range / eLocation ID:
- 1639-1641
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study highway-based shipping of preowned automobiles by auto carriers, an important although overlooked problem in the automobile shipping literature. The special structure associated with auto carriers implies many different ways of loading a set of automobiles to an auto carrier with different loading costs. Thus, in addition to vehicle routing decisions, loading decisions are essential in automobile shipping optimization. The objective of our problem is to maximize the total revenue minus the total routing and loading cost subject to time windows and loading constraints among others. Most existing automobile shipping studies treat loading and routing separately; some studies partially address the loading aspect in routing optimization but only check the loading feasibility without evaluating the quality of loading decisions. We, thus, contribute to the literature by fully integrating loading decisions into routing decision making. An integrated machine learning (ML) and optimization approach is proposed to solve the problem. The overall approach follows a column generation–based solution framework, in which an insertion heuristic is proposed to find new routes based on existing routes, and ML is employed to predict the loading feasibility and estimate the minimum loading cost of a given route without solving the complex loading optimization problem. The integration of the ML approach and the insertion heuristic enables us to find high-quality new routes quickly in each column generation iteration. Two variants of this integrated approach are evaluated against a benchmark sequential approach in which routing and loading are tackled separately and another benchmark approach in which routing and loading are optimized jointly without using ML. Computational experiments demonstrate that the proposed integrated ML and optimization approach generates significantly better solutions than the sequential benchmark approach with only slightly more computation time and similar solutions to the joint optimization benchmark approach but with significantly less computation time. The proposed solution approach can be adopted by automobile shipping companies. It can also be adapted for other joint optimization problems, such as those in aircraft load planning. Funding: Y. Sun is partially supported by the National Science Foundation [Grants 2332161, 2100745, and 2055347]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2024.0712 .more » « less
-
Abstract. Previous tsunami evacuation simulations have mostly been based on arbitrary assumptions or inputs adapted from non-emergency situations, but a few studies have used empirical behavior data. This study bridges this gap by integrating empirical decision data from surveys on local evacuation expectations and evacuation drills into an agent-based model of evacuation behavior for two Cascadia subduction zone (CSZ) communities that would be inundated within 20–40 min after a CSZ earthquake. The model also considers the impacts of liquefaction and landslides from the earthquake on tsunami evacuation. Furthermore, we integrate the slope-speed component from least-cost distance to build the simulation model that better represents the complex nature of evacuations. The simulation results indicate that milling time and the evacuation participation rate have significant nonlinear impacts on tsunami mortality estimates. When people walk faster than 1 m s−1, evacuation by foot is more effective because it avoids traffic congestion when driving. We also find that evacuation results are more sensitive to walking speed, milling time, evacuation participation, and choosing the closest safe location than to other behavioral variables. Minimum tsunami mortality results from maximizing the evacuation participation rate, minimizing milling time, and choosing the closest safe destination outside of the inundation zone. This study's comparison of the agent-based model and the beat-the-wave (BtW) model finds consistency between the two models' results. By integrating the natural system, built environment, and social system, this interdisciplinary model incorporates substantial aspects of the real world into the multi-hazard agent-based platform. This model provides a unique opportunity for local authorities to prioritize their resources for hazard education, community disaster preparedness, and resilience plans.more » « less
-
Abstract We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of new infections subject to a budget constraint on the total number of available vaccinations for the contagions. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. This optimization problem is NP-hard. We present two main solution approaches for the problem, namely an integer linear programming (ILP) formulation to obtain optimal solutions and a heuristic based on a generalization of the set cover problem. We carry out a comprehensive experimental evaluation of our solution approaches using many real-world networks. The experimental results show that our heuristic algorithm produces solutions that are close to the optimal solution and runs several orders of magnitude faster than the ILP-based approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm.more » « less
-
null (Ed.)This paper introduces and studies a graph-based variant of the path planning problem arising in hostile environments. We consider a setting where an agent (e.g. a robot) must reach a given destination while avoiding being intercepted by probabilistic entities which exist in the graph with a given probability and move according to a probabilistic motion pattern known a priori. Given a goal vertex and a deadline to reach it, the agent must compute the path to the goal that maximizes its chances of survival. We study the computational complexity of the problem, and present two algorithms for computing high quality solutions in the general case: an exact algorithm based on Mixed-Integer Nonlinear Programming, working well in instances of moderate size, and a pseudo-polynomial time heuristic algorithm allowing to solve large scale problems in reasonable time. We also consider the two limit cases where the agent can survive with probability 0 or 1, and provide specialized algorithms to detect these kinds of situations more efficiently.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
