skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Simulation-Assisted Optimization for Large-Scale Evacuation Planning with Congestion-Dependent Delays
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
Award ID(s):
2053013
PAR ID:
10521667
Author(s) / Creator(s):
; ; ; ; ;
Publisher / Repository:
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)
Date Published:
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, Transportation Research Record: Journal of the Transportation Research Board)
    null (Ed.)
    The State of Florida is significantly vulnerable to catastrophic hurricanes that cause widespread infrastructural damage and claim lives annually. In 2017, Hurricane Irma, a Category 4 hurricane, took on the entirety of Florida, causing the state’s largest evacuation ever as 7 million residents fled the hurricane. Floridians fleeing the hurricane faced the unique challenge of where to go, since Irma made an unusual landfall from the south, enveloping the entire state, forcing evacuees to drive farther north, and creating traffic jams along Florida’s evacuation routes that were worse than during any other hurricane in Florida's history. This study aimed to assess the spatiotemporal traffic impacts of Irma on Florida’s major highways based on real-time traffic data before, during, and after the hurricane made landfall. First, we conducted a time-series-based analysis to evaluate the temporal evacuation patterns of this large-scale evacuation. Second, we developed a metric, namely the congestion index (CI), to assess the spatiotemporal evacuation patterns on I-95, I-75, I-10, I-4, and turnpike (SR-91) highways with a focus on both evacuation and returning traffic. Third, we employed a geographic information system-based analysis to visually illustrate the CI values of corresponding highway sections with respect to different dates and times. Findings clearly showed that imperfect forecasts and the uncertainty surrounding Irma’s predicted path resulted in high levels of congestion and severe delays on Florida’s major evacuation routes. 
    more » « less
  2. ; ; ; ; (, IEEE International Conference on Big Data)
    null (Ed.)
    Abstract—Evacuation planning methods aim to design routes and schedules to relocate people to safety in the event of natural or man-made disasters. The primary goal is to minimize casualties which often requires the evacuation process to be completed as soon as possible. In this paper, we present QueST, an agent-based discrete event queuing network simulation system, and STEERS, an iterative routing algorithm that uses QueST for designing and evaluating large scale evacuation plans in terms of total egress time and congestion/bottlenecks occurring during evacuation. We use the Houston Metropolitan Area, which consists of nine US counties and spans an area of 9,444 square miles as a case study, and compare the performance of STEERS with two existing route planning methods. We find that STEERS is either better or comparable to these methods in terms of total evacuation time and congestion faced by the evacuees. We also analyze the large volume of data generated by the simulation process to gain insights about the scenarios arising from following the evacuation routes prescribed by these methods. 
    more » « less
  3. ; ; ; ; (, Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems)
    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
  4. ; ; ; (, Winter Simulation Conference 2019)
    We present a method to apply simulations to the tracking of a live event such as an evacuation. We assume only a limited amount of information is available as the event is ongoing, through population-counting sensors such as surveillance cameras. In this context, agent-based models provide a useful ability to simulate individual behaviors and relationships among members of a population; however, agent-based models also introduce a significant data-association challenge when used with population-counting sensors that do not specifically identify agents. The main contribution of this paper is to develop an efficient method for managing the combinatorial complexity of data association. The key to our approach is to map from the state-space to an alternative correspondence-vector domain, where the measurement update can be implemented efficiently. We present a simulation study involving an evacuation over a road network and show that our method allows close tracking of the population over time. 
    more » « less
  5. ; ; (, IEEE)
    Combinatorial distribution system optimization problems, such as scheduling electric vehicle (EV) charging during evacuations, present significant computational challenges. These challenges stem from the large numbers of constraints, continuous variables, and discrete variables, coupled with the unbalanced nature of distribution systems. In response to the escalating frequency of extreme events impacting electric power systems, this paper introduces a method that integrates sample-based conservative linear power flow approximations (CLAs) into an optimization framework. In particular, this integration aims to ameliorate the aforementioned challenges of distribution system optimization in the context of efficiently minimizing the charging time required for EVs in urban evacuation scenarios. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email