Effective evacuation route planning algorithms by updating earliest arrival time of multiple paths

More and more natural disasters are happening around the globe and in such urgent situations, effective evacuation planning is one of the most critical tools for human safety. Evacuation planning algorithms are different from traditional network routing algorithms in the sense that the objective is to minimize the time when the last evacuee arrives at the destination. Among the existing evacuation planning algo- rithms, CCRP++ finds good solutions but its computation time is not scalable in terms of the number of the evacuees. In addition, in order to improve the computation time from the base algorithm CCRP, CCRP++ makes non-global up- date of earliest arrival time of each source node which results in unnecessarily large evacuation time. In this paper we investigated the two factors (evacua- tion time and computation time) of CCRP++ and proposed three algorithms, DMP, SMP, and EET, that significantly improve both factors. All four algorithms take the trans- portation network as the input and output the complete evacuation scenarios in which individualized evacuation plan for each evacuee is determined. Our first algorithm DMP significantly reduces the number of the shortest path find- ings during the evacuation iteration which is the main rea- son of large computation time of CCRP++. In addition, by updating the earliest arrival time of each found path ef- ficiently, the evacuation time of DMP output is on average reduced compared to that of CCRP++ output. Our sec- ond algorithm SMP further reduces the computation time by first finding the limited number of shortest paths before the evacuation iteration while maintaining the reduced evac- uation time. Our third algorithm EET focuses on reducing the evacuation time of SMP output even in the worst-case scenarios by efficiently and effectively estimating the evacu- ation time and by using it to determine the source node to be evacuated in each round. The computation results show that EET successfully reduces the evacuation time, espe- cially when DMP/SMP outputs were worse than CCRP++. Due to its algorithmic complication, EET has slightly in- creased computation time compared to SMP, but still re- mains comparable to DMP.