Capacity constrained routing algorithms for evacuation route planning

Evacuation route planning identifies routes to minimize the time to evacuate vulnerable population to safe destinations. It is critical for numerous important applications like disaster management and homeland defense. Traditional warning systems did not consider capacity constraints of the transportation network and led to unanticipated effects on the evacuation process. Effective evacuation route planning honoring the capacity constraints of transportation network has the potential of reducing congestion during large scale evacuations. Previous approaches of evacuation route planning use linear programming method to generate optimal evacuation plans by using time expanded networks, which requires a user-provided upper-bound on evacuation time. This method is computationally expensive and its scalability is limited. There is an immediate need for a scalable algorithm that generates high quality evacuation plans.; This thesis presents a comprehensive overview of the algorithm framework for evacuation route planning problem and propose new approaches to address the limitation of previous works. First, an alternate optimal algorithm using A* search is presented. This algorithm uses only the original network to find optimal solutions and it does not require prior knowledge on evacuation time. However, this algorithm is not scalable to large size networks. To address the need for more computationally efficient algorithms, a new heuristic approach is proposed, namely Capacity Constrained Route Planner(CCRP). Earlier versions of CCRP are CCRP_03 and CCRP_05, they produce high quality solutions while the run-time is reduced to less than half of the optimal algorithm, but its scalability to large size network is limited. Major improvements are done in the CCRP algorithm to scale up to large evacuation scenarios. An improved heuristic algorithm CCRP_06 is proposed by exploring available design decisions for CCRP. We characterize the design space and evaluate the performance of CCRP. A wide range of shortest path algorithms and data structures are explored. We prove that CCRP_06, which uses Dijkstra's algorithm with double-bucket, is faster than the linear programming method in real evacuation scenarios and requires less memory. Experiment evaluation shows that CCRP_06 produces high quality solutions and is much more computationally efficient than the linear programming algorithm.