Dynamic Vehicle Routing in Emergency Evacuation

Since Hurricane Katrina, extensive studies have been conducted aiming to optimize the transit vehicle routing in the event of an emergency evacuation. However, the vast majority of the studies focus on solving the deterministic vehicle routing problem that all the evacuation data are known in advance. These studies are generally not practical in dealing with real-world problems which involve considerable uncertainty in the evacuation data set. In this dissertation, a SmartEvac system is developed for dynamic vehicle routing optimization in emergency evacuation. The SmartEvac system is capable of processing dynamic evacuation data in real time, such as random pickup requests, travel time change, network interruptions. The objective is to minimize the total travel time for all transit vehicles. A column generation based online optimization model is integrated into the SmartEvac system. The optimization model is based on the following structure: a master problem model and a sub-problem model. The master problem model is used for routes selection from a restricted routes set while the sub-problem model is developed to progressively add new routes into the restricted routes set. The sub-problem is formulated as a shortest path problem with capacity constraint and is solved using a cycle elimination algorithm. When the evacuation data are updated, the SmartEvac system will reformulate the optimization model and generate a new routes set based on the existing routes set. The computational results on benchmark problems are compared to other studies in the literature. The SmartEvac system outperforms other approaches on most of the benchmark problems in terms of computation time and solution quality. CORSIM simulation is used as a test bed for the SmartEvac system. CORSIM Run-Time-Extension is developed for communications between the simulation and the SmartEvac system. A case study of the Hurricane Gustav emergency evacuation is conducted. Different scenarios corresponding to different situations that presented in the Hurricane Gustav emergency evacuation are proposed to evaluate the performance of the SmartEvac system in response to real-time data. The average processing time is 28.9 seconds and the maximum processing time is 171 seconds, which demonstrate the SmartEvac system’s capability of real-time vehicle routing optimization