Fast and Accurate Evacuation Planning Algorithm with Bayesian Optimization

In this work, we propose a method for generating an evacuation plan at a high speed to realize safe and swift evacuation in the event of a large-scale disaster such as an earthquake and its accompanying tsunami. Existing conventional methods have several problems. Simulation-based methods that use agents and methods that use existing time expansion networks have high computational costs, which makes it difficult for evacuation routes to be immediately changed according to the effects of disasters such as collapsed buildings and roads. Although heuristics with reduced calculation costs are also being researched, they may result in very long evacuation completion times and cannot generate optimal evacuation plans. We guarantee the optimal solution by reducing the number of maximum flow problem calculations, which constitute the bottleneck for methods using the existing time expansion network, through the use of the Bayesian optimization machine learning method. This reduces the calculation cost of the entire algorithm. The performance of our method is evaluated from the two viewpoints of the evacuation completion time, which indicates the quality of the evacuation plan, and the time required for the generation by the solution of the algorithm in computer experiments under multiple scenarios. In addition, the impact of the number of evacuees and the locations of the sinks are analyzed. We show that our method can quickly generate an optimal evacuation plan.