Optimizing Coordinated Evacuation Route Planning Based on Linear Programming

Abstract

This paper introduces a novel approach for coordinated evacuation route planning during disasters, focusing on guiding groups of individuals-such as families or neigh-bors-who are spatially separated but socially connected. Recognizing the importance of group cohesion during evacuations, we designed and implemented a prototype system, which was validated through a real-world evacuation drill conducted in Kobe City during the 30th memorial year of the Great HanshinEarthquake. We introduce and formulate a new problem, termed the ‘Evacuation Routing Problem’ (ERP), using integer linear programming (ILP). Our system recommends that group members rendezvous at specific points along their evacuation routes. The core idea is to model each evacuation route as a tree on a predefined road network, where the leaves correspond to evacuees (group members) and the root corresponds to the shelter. This problem can be viewed as a variant of the Steiner Tree Problem, augmented with an additional constraint to ensure that members of a group meet at an optimal rendezvous node while en route to the shelter. To validate our method, we conducted a pilot experiment in Kobe City, Japan. We developed a prototype system featuring a web-based interface that generates high-quality evacuation routes derived from ILP solutions. The experiment involved two family groups, and the developed system navigated a real road network that included various points of interest such as parks, shopping malls, offices, and schools. The results showed that one family successfully gathered at the proposed rendezvous point and evacuated together, while the other group was unable to meet due to a suggested detour. Drawing from these experimental outcomes and user feedback, we analyze system limitations and discuss potential improvements from a user-centric perspective.