Large-scale evacuation route optimization leveraging sampling diversity in quantum annealing

Abstract In regions such as Japan, where natural disasters frequently occur, it is crucial to evacuate swiftly in the event of a disaster. However, evacuees tend to behave selfishly, that is, they typically head to the nearest shelter along the shortest path. This tendency can lead to severe traffic congestion, thereby exacerbating the damage. To address this issue, we formulate an evacuation route optimization problem that enhances evacuation efficiency as a binary quadratic programming (BQP) problem. The proposed formulation simultaneously minimizes the distance each vehicle must travel to reach a safe location and the penalty associated with overlapping routes among vehicles. In this way, we implicitly aim to reduce the overall completion time of evacuation for all vehicles. For an operational deployment of the proposed method during a disaster, the computation of optimal routes must be completed within a short time; otherwise, it is not practically useful. We therefore investigate the feasibility of employing the quantum annealing machine developed by D-Wave Systems Inc., which has been attracting attention as a promising high-speed solver. Since the current D-Wave machine cannot directly handle large-scale problems that cover an entire city, we design a decomposition method that exploits the intrinsic sampling diversity of the D-Wave machine. We examine the trade-off between solution quality and computation time. Numerical experiments using a traffic simulator demonstrate that the solution of the proposed BQP formulation can shorten the evacuation completion time by up to 33.6% in a specific region of Japan, compared with a locally optimal approach in which all vehicles select the shortest route to the nearest shelter. Although the solution obtained by the proposed decomposition method does not reach the global optimum, it achieves significantly shorter evacuation times than the locally optimal approach, while reducing the computation time drastically. These results are obtained under the assumption that all vehicles strictly follow the computed routes. We further perform simulations under a more realistic assumption in which a fraction of cars choose routes different from those prescribed by the optimization. The results reveal that even if only 1% of vehicles deviate from the optimized routes, the evacuation efficiency deteriorates sharply. Nevertheless, the proposed method still yields a shorter evacuation completion time than the locally optimal approach. These findings suggest that, in time-critical disaster situations, our method provides practical insights for evacuation planning that prioritize rapid and effective action under uncertain conditions, rather than insisting on strict optimality.