Emergency Evacuation Planning Problem under Uncertainty in Events



Journal Title

Journal ISSN

Volume Title



Large-scale emergency evacuations in the wake of hazardous events, such as hurricanes, tsunamis, volcanic disruptions, nuclear meltdowns, etc., are an important part of disaster management as they directly associate with protecting human lives. Due to the unpredictable nature of disasters, an evacuation plan can be heavily affected by the uncertainty of events. The resulting deviations can contribute to road congestions, prolonged evacuation process, unstable traffic behaviors, and lead to chaos, injuries, and loss of life. Two approaches can be taken to handle these uncertainties. First could be to develop an evacuation route plan and schedule prior to the arrival of the adversarial event by considering the risk of exposure to the disaster impact (pro-active planning), and second would be to monitor the progress of the evacuation, detect deviations, and make adjustments if needed (recovery strategy). Our proposed research focuses on developing pro-active plans and recovery strategies to handle associated uncertainties that are either due to the occurrence of probable incidents or randomness in data. Using the theory of dynamic network flow optimization, the following studies are conducted: First, emergency evacuation management under possible road disruptions in the transportation network is studied. During an evacuation, roads can be cut off due to road flooding, blocked because of wild-fire propagation, accidents or collapse of highway structures, etc. A comprehensive approach for rerouting the disturbed flow is introduced which can address disruptions on multiple roads occurring at different times. Two innovative algorithms for parameter calculation are introduced to reduce mathematical complexity and computational burden. Using these algorithms, a MIP formulation for rerouting the disturbed flow is proposed. Computational results show the validity of our approach. Second, the effect of uncertain road closures on traffic dynamics in a system-optimal setting is investigated to provide a proactive evacuation plan while considering a recovery strategy (rerouting) to compensate for the negative effects of the disruption. The previously mentioned algorithms for parameter calculation are extended to be implemented for disruption scenarios, and a MIP two-stage stochastic program is introduced to solve the problem. The first stage of the two-stage program aims to find the proactive evacuation plan while the second stage finds the best recovery strategy in the face of each scenario of disruption. Comparisons are made between the plans yielded from existing deterministic models with the plans provided by our proposed approach which demonstrates the superiority of our developed stochastic program. Third, an evacuation planning problem under uncertainty of the number of would-be evacuees (demand) is investigated. It is assumed that based on the available historical data, accurate predictions on demand are not possible and the probability distribution function of demand cannot be estimated. Accordingly, a data-driven robust optimization approach is developed to solve the evacuation planning problem by directly incorporating data samples in the mathematical formulation of the problem. To build the uncertainty sets, an unsupervised machine learning approach (support vector clustering) is used which employs a piecewise linear kernel function to effectively capture the distributional geometry of massive demand data. Furthermore, to provide tighter uncertainty sets, an uncertainty set based on the intersection of the previous uncertainty set (SVC-based uncertainty set) and a conventional robust optimization uncertainty set (e.g., Box uncertainty set) is introduced. Mixed-integer programming (MIP) data-driven formulations for each of the introduced uncertainty sets are developed and numerical experiments are conducted. Results show that by using a regularization parameter it is possible to adjust the level of robustness and conservatism in the optimization models. Fourth, a framework to provide proactive evacuation plans under the risk of unexpected capacity disruptions in the evacuation network is proposed. It is assumed that due to the uniqueness of disastrous events, enough information on the uncertain road disruptions is not available, the uncertainty distributions are not perfectly known, and only partial information on the probability distributions is accessible. The problem is formulated as a distributionally robust data-driven model to ensure that constraints affected by uncertainties are satisfied under any probability distribution consistent with the constructed uncertainty set. Auxiliary variables are introduced to reformulate the problem and build a MIP optimization framework. A heuristic algorithm is introduced to even more reduce the complexity of the problem and decrease its computational time. Numerical experiments indicate that by using the heuristic approach the computational time is significantly reduced. Moreover, compared to the existing deterministic models, the proposed distributionally robust data-driven program can reduce the percentage of disturbed evacuees and negative consequences of road disruptions.



Emergency Evacuation, Reroute Planning, Dynamic Network Flow Optimization, Two-Stage Programming, Distributionally Chance-Constraint Programming, Data-Driven Robust Optimization, Support Vector Clustering (SVC)