Crisis Management Days

Mathematical Evacuation Planning: Graph Theory and Optimization Approaches

Iva Golubić

Veleučilište Velika Gorica

Marjana Kuliš

Veleučilište Velika Gorica

Martin Mustač

Veleučilište Velika Gorica

Keywords: Evacuation, Dijkstra’s algorithm, A* algorithm, linear programming, graph theory, optimization

---

Abstract

Evacuation represents one of the key components of crisis management, addressing the organized movement of people from hazardous environments to safe locations. It occurs in a wide range of situations, including natural disasters such as floods, earthquakes, and wildfires, as well as in human-induced emergencies like industrial accidents or security threats. The primary objective of evacuation is to preserve human life while maintaining order and reducing the likelihood of panic. However, achieving this goal is far from trivial, as evacuation processes involve numerous interacting factors and uncertainties.

In real-world situations, evacuation planning requires careful consideration of population distribution, transportation resources, infrastructure capacity, and the availability of safe zones. Human behaviour adds an additional layer of complexity, as individuals may react unpredictably under stress, potentially causing congestion or inefficiencies. Moreover, timing plays a crucial role, since delays or poorly designed evacuation routes can significantly increase risk. For these reasons, evacuation is not merely a logistical task but a complex system that must be analysed and understood in a structured way.

Mathematics provides a natural framework for addressing such complexity. Many mathematical fields are incorporated both in evacuation planning and in other segments of crisis management. We will present two of them: graph theory and optimisation.

Graph theory is a branch of mathematics that studies structures made up of points which are called nodes (or vertices) and connections between them, which are called edges. We assign values to these connections such as distance, travel time or capacity. These structures are then called networks. In the context of evacuation, a network would consist of intersections, buildings, shelters that are represented as nodes, and the roads and paths between them as edges. Networks can be road systems, transportation grids, or building layouts. For evacuation planning, we apply algorithms that identify efficient routes and detect potential bottlenecks. This is exactly what this paper will present. We show two shortest path algorithms: the Dijkstra’s algorithm and the A* algorithm. While Dijkstra’s algorithm only considers the travelled distance from the starting position toward the goal, A* incorporates estimations of how far you are from the goal.

Optimization is a field of mathematics focused on finding the best possible solution to a problem under a given set of constraints. Typically, this involves maximizing or minimizing a certain quantity, such as time, cost, or resource usage, while respecting limitations like capacity or availability. In evacuation planning, optimization plays a crucial role in determining how to use limited resources effectively. For example, decision-makers may need to decide how to allocate vehicles, assign emergency personnel, or distribute evacuees across multiple routes. They usually need to do so in the minimum total evacuation time or to maximise the number of people safely relocated. In the paper, we explain such optimisation problems through one of the most common optimisation frameworks, linear programming.

Shortest path algorithms determine optimal routes for individuals, whereas linear programming models optimize the allocation of flows across a system under constraints, making them more suitable for large-scale evacuation planning. Altogether, we show basic concepts from graph theory and optimization to evacuation scenarios through simple examples to show the wider audience how mathematics helps evacuation planning.

---

References

Astana, I. N. Y., Sudarsana, I. D. K., & Puspa, N. M. W. (2023). Designing evacuation route using Dijkstra methods. International Journal of Progressive Sciences and Technologies (IJPSAT), 37(2), 303–314.

Bin Obaid, H., Trafalis, T. B., Abushaega, M. M., Altherwi, A., & Hamzi, A. (2025). Optimizing dynamic evacuation using mixed-integer linear programming. Mathematics, 13(1), 12.

Rudrawar, S. K., Ghorpade, P., & Sakhare, D. Y. (2021). Implementation of A* algorithm for real-time evacuation during fire situation. In Techno-Societal 2020 (pp. 197–208). Springer.

https://doi.org/10.3390/math13010012

Khakzad, N. (2023). A methodology based on Dijkstra's algorithm and mathematical programming for optimal evacuation in process plants in the event of major tank fires. Reliability Engineering & System Safety, 236, 109291. https://doi.org/10.1016/j.ress.2023.109291