Skip to content
Paper

A Meta-Heuristic Solution Approach to Isolated Evacuation Problems

 
Download PDF  (0.40 MB)
Publication: IEEE (Institute of Electrical and Electronics Engineers)
Volume: 2022 Winter Simulation Conference (WSC) INFORMS
Publication Date: 2022
Summary:

This paper provides an approximation method for the optimization of isolated evacuation operations, modeled through the recently introduced Isolated Community Evacuation Problem (ICEP). This routing model optimizes the planning for evacuations of isolated areas, such as islands, mountain valleys, or locations cut off through hostile military action or other hazards that are not accessible by road and require evacuation by a coordinated set of special equipment. Due to its routing structure, the ICEP is NP-complete and does not scale well. The urgent need for decisions during emergencies requires evacuation models to be solved quickly. Therefore, this paper investigates solving this problem using a Biased Random-Key Genetic Algorithm. The paper presents a new decoder specific to the ICEP, that allows to translate in between an instance of the S-ICEP and the BRKGA. This method approximates the global optimum and is suitable for parallel processing. The method is validated through computational experiments.

Authors: Dr. Anne GoodchildFiete Krutein, Linda Ng Boyle (University of Washington Dept. of Industrial & Systems Engineering)
Recommended Citation:
K. F. Krutein, L. N. Boyle and A. Goodchild, "A Meta-Heuristic Solution Approach to Isolated Evacuation Problems," 2022 Winter Simulation Conference (WSC), Singapore, 2022, pp. 2002-2012, doi: 10.1109/WSC57314.2022.10015470.
Student Thesis and Dissertations

Optimization Modeling Approaches to Evacuations of Isolated Communities

Publication Date: 2022
Summary:

Isolated communities are particularly vulnerable to disasters caused by natural hazards. In many cases, evacuation is the only option to ensure the population’s safety. Isolated communities are becoming increasingly aware of this threat and demand solutions to this problem. However, the large body of existing research on evacuation modeling usually considers environments where populations can evacuate via private vehicles and by using an existing road infrastructure. These models are often not applicable to remote valleys and islands, where road connections can be disrupted or do not exist at all. The use of external resources is therefore essential to evacuate the population. How to systematically evacuate an isolated community through a coordinated fleet of resources has not yet been researched. This dissertation thesis addresses this knowledge gap by designing a new routing problem called the Isolated Community Evacuation Problem (ICEP) that optimally routes recovery resources between evacuation pick-up points and shelter locations to minimize the total evacuation time. The research presents derivations of the initial model for (a) emergency planning and (b) response purposes to give emergency planners and researchers tools to prepare for and react to an evacuation of an isolated community. For (a), a scenario-based two-stage stochastic program with recourse considers different emergency scenarios to select the optimal set of recovery resources to hold available for any evacuation emergency. Furthermore, the dissertation explores efficient structure-based heuristics to solve the problem quickly. For (b), the assumption of certainty over the size of the affected population at the time of evacuation is relaxed. Approaches from robust and rolling-horizon optimization are presented to solve this problem. Moreover, meta-heuristics are explored to solve the problem to optimality while overcoming the complexity of the problem formulation. Finally, an in-depth, real-world case study that was conducted in collaboration with first responders and emergency authorities on Bowen Island in Canada is presented to test and evaluate the applicability of the proposed models. This case study further informed the official evacuation plan of the island. This collaboration demonstrates the potential of full integration of the research approach with local emergency expertise from the affected area and highlights the data requirements that need to be met to maximize the use of the model.

Authors: Fiete Krutein
Paper

The Isolated Community Evacuation Problem with Mixed Integer Programming

 
Download PDF  (0.78 MB)
Publication: Transportation Research Part E: Logistics and Transportation Review
Volume: 161
Pages: 102710
Publication Date: 2022
Summary:

As awareness of the vulnerability of isolated regions to natural disasters grows, the demand for efficient evacuation plans is increasing. However, isolated areas, such as islands, often have characteristics that make conventional methods, such as evacuation by private vehicle, impractical to infeasible. Mathematical models are conventional tools for evacuation planning. Most previous models have focused on densely populated areas, and are inapplicable to isolated communities that are dependent on marine vessels or aircraft to evacuate. This paper introduces the Isolated Community Evacuation Problem (ICEP) and a corresponding mixed integer programming formulation that aims to minimize the evacuation time of an isolated community through optimally routing a coordinated fleet of heterogeneous recovery resources. ICEP differs from previous models on resource-based evacuation in that it is highly asymmetric and incorporates compatibility issues between resources and access points. The formulation is expanded to a two-stage stochastic problem that allows scenario-based optimal resource planning while also ensuring minimal evacuation time. In addition, objective functions with a varying degree of risk are provided, and the sensitivity of the model to different objective functions and problem sizes is presented through numerical experiments. To increase efficiency, structure-based heuristics to solve the deterministic and stochastic problems are introduced and evaluated through computational experiments. The results give researchers and emergency planners in remote areas a tool to build optimal evacuation plans given the heterogeneous resource fleets available, which is something they have not been previously able to do and to take actions to improve the resilience of their communities accordingly.

Recommended Citation:
Krutein, K. F., & Goodchild, A. (2022). The isolated community evacuation problem with mixed integer programming. In Transportation Research Part E: Logistics and Transportation Review (Vol. 161, p. 102710). Elsevier BV. https://doi.org/10.1016/j.tre.2022.10271