Optimal Evacuation Plan Design with IP-Solver

Janacek, Jaroslav; Sibila, Michal · 2009 · DOAJ

DOI: 10.26552/com.C.2009.3.29-35

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the combinatorial problem of designing optimal evacuation plans to minimize the total time required to transport endangered populations from dwelling places to pre-assigned safe shelters. The study focuses on assigning available homogeneous vehicle fleets to these locations, assuming that each dwelling place has a predetermined destination and that vehicles may make multiple trips to evacuate the entire population. The authors propose and compare two distinct mathematical modeling approaches for this assignment problem: one treating vehicle fleets as indivisible units and another allowing fleets to be split into smaller, divisible groups. The first approach assumes that entire fleets must act as single convoys, assigning all vehicles of a fleet to one specific dwelling place. This method results in a linear integer programming (IP) model that is straightforward to solve but generates a large number of constraints and variables. To mitigate the model size, the authors tested grouping individual vehicles into larger fleets (groups of two, four, and eight). The second approach allows fleets to be divided, assigning arbitrary integer numbers of vehicles from a fleet to different locations. While this creates a more compact model, it initially introduces non-linear constraints. The authors successfully reformulated this into a linear model using auxiliary binary variables to handle the product of decision variables, enabling the use of standard commercial IP solvers. Numerical experiments were conducted using ten instances based on potential emergency scenarios in Slovakia, including a dam break scenario involving 26 communities and 411 vehicles. The models were solved using the XPRESS-IVE software with a 20-minute time limit. Results for the indivisible fleet approach showed that while grouping vehicles reduced model size, it often led to worse evacuation times or infeasibility. In contrast, the divisible fleet approach consistently produced superior results. For example, in the "Hradza" instance, the divisible fleet model achieved a best evacuation time of 81 minutes, compared to 93 minutes for indivisible fleets. Across all instances, the divisible fleet approach yielded shorter evacuation times and handled the computational constraints more effectively, despite the increased complexity of the linearization process. The study concludes that while the indivisible fleet model is simpler to formulate, the divisible fleet approach is superior for practical evacuation planning. The ability to split fleets allows for more efficient resource allocation, resulting in significantly reduced evacuation times. The successful linearization of the divisible fleet model demonstrates that complex, non-linear evacuation problems can be effectively solved using standard commercial optimization software, providing a robust tool for emergency management planning.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• evacuation egress