Optimization Models for Pedestrian Emergency Evacuation Planning

The cell transmission model (CTM) proposed by Carlos F. Daganzo in 1994 and used by Ziliaskopoulos to formulate the Single Destination System Optimal Dynamic Traffic Assignment (SDSO-DTA) model has been widely applied to such situations as mass evacuations in a transportation network. Although the model is formulated as a linear program (LP), a network representation that embeds multi-period cells would yield an extremely large problem for real-size cases. As a result, most of these models are applied in the literature to small scale network sizes only. This doctoral research aims at developing innovative algorithms that overcome both computational efficiency and solution applicability issues. We first developed a network transformation and conversion (NTC) model to convert any transportation infrastructure into a cell-based network. NTC enables the application of different formulations to large-scale real-world networks for SO-DTA analysis employing cell transmission models. We then propose the Dynamic Cell Transmission Evacuation Planning model (DyCTEP), a modification of CTM by Arbib et al. [23, 24], to incorporate city-level networks under extreme and undesirable conditions. The formulation of DyCTEP model allows its use as a practical tool to dynamically approach pedestrian emergency evacuation, providing an optimal solution in terms of destinations, route, time, flow-staging and flow distributions. The model also approximates non-linear arc capacities to manage congestion phenomena. We also propose a heuristic algorithm for optimal route assignment that takes into consideration the whole time-dynamics of solutions. We also implemented three new approaches, namely Dynamic Earliest Arrival Flow (DEAF), Extended CTM and Multiple Cells, designed to cope with inconveniences in the DyCTEP model: in fact, single-size cells may lead to unacceptable imprecision if too large or, if too small, to an excessive number of constraints and variables in the optimization model, demanding in computational terms but in fact unnecessary to meet the desired operation accuracy. In order to formulate DEAF, we modified the Time Expanded Graph (TEG), showing that there is no need to explicitly partition and embed the underlining evacuation network into elementary cells, as the network can be converted using travel time information. We also verified and validated the equivalence of DEAF and DyCTEP model. The other two approaches are extension of the DyCTEP model to simplify the choice of the optimum cell size. Different analyses were carried out to determine the effects of these models on problem complexity, solution accuracy, and computation time. We proposed the Priority Multi-Party Capacity Constrained Route Planning method (PMPCCRP), a heuristic algorithm which extends the CCRP method by Shekhar et al. [311]. The proposed PMP-CCRP method incorporates the ability of planning the evacuation of different parties with different objectives (e.g., a situation where evacuees are directed from endangered sources to safe locations, while emergency rescuers go the other way round), therefore seeking for optimal paths for both incoming emergency units and evacuees. PMP-CCRP ensures that, during evacuation, priority is given to high-risk areas; that is, evacuees in highly endangered zone are evacuated before those in less risky areas. The feasibility and applicability of our modeling framework was investigated with the help of real case studies: the emergency evacuation of the historical centres of L’Aquila and Sulmona (Abruzzo, Italy). The models were customized with respect to several parameters, and re-scaled to the network by several orders of magnitude. In the Sulmona case study, we solved a problem with over 2,000,000 nodes. And there was a significant improvement in the computational complexity and time of the first approach. Still, the results obtained were definitely encouraging in terms of approach viability.