Evacuation Route Optimization with Evacuee Capacity Constraints Using an Ising Machine

In this study, the evacuation route optimization problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem and solved using Ising machines, such as the D-Wave quantum annealer. In quantum annealing, an optimization problem is mapped onto an Ising Hamiltonian, and its ground state is obtained through time evolution driven by quantum fluctuations, thereby yielding an approximate optimal solution to the combinatorial optimization problem [4].

First, the spatial structure of the building is represented as a graph composed of nodes and edges. For each evacuee or evacuee group placed on the graph, multiple candidate routes to exits are generated in advance. Each candidate route is then encoded as a binary variable, and the combination of route selections is formulated as the optimization target. An energy function is constructed, consisting of a cost term representing the total evacuation time and penalty terms that suppress violations of capacity constraints at corridors, exits, and rooms. In this way, the evacuation route selection problem considering congestion is expressed as a QUBO problem. The formulated QUBO is then solved as an energy minimization problem on an Ising machine. From the obtained low-energy solution, the selected route for each evacuee or group is reconstructed, resulting in an evacuation plan that reduces congestion across the entire building.

Unlike conventional approaches in which routes are merely evaluated a posteriori using crowd simulations [5], our formulation directly optimizes route assignments under explicit congestion constraints via Ising-machine-based combinatorial optimization. 

As the target problem, a graph model representing an underground commercial space, where congestion is likely to occur due to constraints in corridor width and exits, was constructed, and the evacuation route assignment problem was formulated based on this model. Multiple initial placement patterns of evacuees were prepared, and the proposed method was applied to each scenario to derive route assignments that account for congestion.

In this study, the Fixstars Amplify Annealing Engine was employed as the Ising machine for optimization [6]. It is a quantum-inspired Ising machine implemented on GPU-based digital computation, which performs solution search based on energy minimization for problems formulated as QUBO. The significance of adopting the QUBO formulation lies in the fact that it is a standard problem representation in quantum annealing. By using this formulation, the optimization problem constructed in this study can be directly handled in the same form on quantum annealers in the future. In other words, this study not only enables validation using quantum-inspired computation but also provides a framework that is directly transferable to future quantum hardware.

The obtained solutions were evaluated by reproducing evacuee movements using crowd simulations, in which the total evacuation time and congestion levels at corridors and exits were measured. Furthermore, the effectiveness of the proposed method was verified by comparison with a baseline method that assigns evacuees to their nearest exits without explicitly considering congestion. The results confirmed that the proposed method contributes to the dispersion of congestion and the reduction of evacuation time.

In this study, optimization was performed on maps involving several hundred evacuees. However, in real-world building evacuation design, the number of evacuees can reach several thousands, making the increase in problem size unavoidable when considering applications to larger-scale facilities. In our formulation, candidate route selections for each evacuee or evacuee group are represented as binary variables, and thus the problem size grows with the number of candidate routes and groups.

To address scalability for such large-scale problems, we investigate strategies to improve computational efficiency. First, the number of variables is reduced by treating evacuees as groups rather than individuals. Second, the search space is reduced by preselecting promising candidate routes in advance. These approaches enable the application of the method to practical problem sizes while keeping the QUBO size manageable.

Furthermore, a hybrid strategy is adopted that combines combinatorial optimization using an Ising machine with evaluation via crowd simulation. Specifically, candidate solutions are generated efficiently using the Ising machine and subsequently evaluated through simulation. This reduces the number of simulations required in the search process compared to conventional approaches that rely solely on repeated simulations.

As a result, the proposed method provides an optimization framework applicable to large-scale evacuation route design problems, which are difficult to handle using exhaustive search or simulation-based approaches alone.