Design and analysis of a fast approximation algorithm for multi-modal emergency evacuation routes in the 3D environment

We consider a multi-modal constrained routing problem arising in emergency evacuation situ-ations. Given a three-dimensional geometric structure of the evacuation network related to an area, such as a high-rise building or a city area with tense population, an emergency evacuation route is a sequence of move-ments of people away from the threat or actual occurrence of a hazard (e.g., a fire or a hidden bomb) to a safe exit of the area. The multi-modality condition corresponds to different possible ways and modes of evacuation (ambulances, trucks, helicopters, planes, etc.) and dictates specific demands to the solution algorithms. We provide a new pseudo-polynomial-time dynamic programming algorithm to solve this problem. Based on this algorithm, we construct a Fully Polynomial- Time Approximation Scheme (FPTAS), providing “almost-optimal” solutions in real time.