Reliable Route Planning for Emergency Evacuation

Large scale evacuations are important in the wake of events such as an anticipated strike of a natural disaster or a looming military attack. Planning to evacuate people towards safe areas and effective management of the plan using limited set of resources is, therefore, an integral part of disaster management. Evacuation planning based on deterministic estimate of demand at the source nodes and capacity of the road links yield unsatisfactory result. Recent research publications are addressing the randomness associated with such events using stochastic optimization models. Models considering the inherent uncertainty associated with transportation network facilitate a robust and efficient evacuation plan. In this dissertation, large scale network flow optimization models for both deterministic and stochastic evacuation scenarios are presented with an emphasis on coming up with an effective and reliable evacuation plan. Effective implementation of an evacuation plan in the wake of a limited set of resources demands that a minimum number of paths are selected for loading the evacuation traffic. This objective has eluded the eyes of the research community involved in evacuation planning optimization. Model, solution technique and computational results for this problem is presented that describes the complete evacuation plan comprising of paths, traffic flow and starting schedule. Traffic scenario is often non-deterministic and assumption of a deterministic capacity for the road links would result in poor quality evacuation plan in terms of paths and time required for evacuation. Motivated by the stochastic behavior of the arc capacity, a chance constrained model for bottleneck minimization is proposed that finds the evacuation paths and the traffic flow rate on the paths within a given time bound that would result in minimum traffic congestion. Given the horizon time for evacuation, model selects the evacuation paths and finds flows on the selected paths that result in minimum congestion in the network and finds the reliability of the evacuation plan. Numerical examples are presented and we discuss the effectiveness of the stochastic models in evacuation planning. It is shown that the reliability based evacuation plan is conservative as compared to plans obtained using a deterministic model. Stochastic models guarantee that congestion can be avoided with a confidence level at the cost of increased clearance time. Apart from the random arc capacity, in this dissertation we propose an evacuation planning model where the demand for the number of evacuees is unknown and is subject to uncertainty. Chance constrained approach is used in such situations to enforce the constraints for given level of confidence. We analyze the model for the situation when the probability distribution of the random demand is not known and only partial moments and support information is specified. A distributional robust chance constrained model is proposed for evacuation planning that guarantee the vehicle demand constraints for any probability distribution consistent with the known properties. We find a tight upper bound for the shortfall in evacuating people from the specified target in the given clearance time. Numerical experiments show that the robust approximation method of chance constraints provide excellent results as compared to solution based on approximated distribution and sampling based solution.Industrial Engineering, Department o