S10 - Insights from Failure & Quantum Methods for Emerging Domains

Vehicle routing problems (VRP) are a central class of problems in logistics and supply-chain optimization. They formalize the efficient allocation of limited transportation resources to meet distributed demand while accounting for operational constraints such as vehicle capacities, travel costs, and service requirements. Vehicle routing is part of the group of classical combinatorial optimization problems given that they are NP-hard (Toth, 2002), posing significant computational challenges, particularly for large-scale and real-world instances. Because of their practical relevance, a large body of research exists on how to solve different vehicle routing variants either exactly or via approximations (Cordeau, 2007) (Elshaer, 2020).
Column generation (CG) (Desaulniers, 2006) is a widely used approach for tackling large-scale vehicle routing by using a set-partitioning formulation where each feasible route represents a variable. By iteratively adding only promising routes, CG avoids explicit enumeration of all possibilities and scales effectively to complex VRP variants, serving as the foundation of exact solution methods such as branch‑and‑price (Feillet, 2010). 
The CG methodology provides a natural blueprint to implement a hybrid quantum algorithm, as it naturally decomposes problems into a Linear Program (master) and a Binary Program (pricing). Several works propose to formulate pricing as a Quadratic Unconstrained Binary Problem (QUBO), which can be solved natively using quantum hardware such as quantum annealers (da Silva Coelho, 2023) (Kanai, 2024). 
Building upon this work, we consider the application of battery-constrained routing, i.e., formulations where the vehicles have a limited battery life and must return to charge periodically. This is a relevant scenario for electric vehicles or drones. For our application, we use a prize-collecting objective, i.e., each location to be visited has an associated prize. The goal is to maximize the collected prize while respecting the battery capacity and the limited number of vehicles.
We model this problem using the CG framework and experimentally compare the performance of a number of solvers for the resulting pricing problem, including both classical and quantum solvers. Our findings show that quantum solvers offer no computational advantage in the context of the CG framework and our application, due to inevitable obstructions arising from the structural properties of the pricing problem. These obstructions apply equally well to variations of the considered routing problem that suffer from the same structural obstructions, such the classical cost-minimization setting, where it is instead enforced that all locations be visited.

We address the evacuation route optimization problem in indoor environments. In recent years, ensuring safe evacuation during disasters has become a critical societal issue due to the increasing scale and complexity of large commercial facilities and underground spaces. In particular, during emergencies such as fires and earthquakes, a large number of evacuees move simultaneously, leading to severe congestion at corridors and exits. This congestion results in increased evacuation times and a higher risk of secondary accidents [1].
In practice, evacuation planning is generally conducted based on regulatory standards, such as building and fire safety codes, in which routing to the nearest exits is adopted as a standard principle. Crowd simulations are sometimes used as a supplementary tool to evaluate the safety of designed evacuation plans; however, they are primarily intended to assess routes and are not, by themselves, used to explicitly optimize route assignments that account for interactions among evacuees and time-dependent congestion [2]. Furthermore, although optimization-based approaches for evacuation planning have been proposed, their application to large-scale combinatorial route assignment problems remains challenging. In particular, approaches based on QUBO formulations and Ising machines have not yet been sufficiently explored in this context.
Under these circumstances, determining appropriate route assignments that explicitly consider congestion is essential for improving evacuation safety, as it enables the reduction of evacuation time and the avoidance of bottlenecks. For example, Abdelghany et al. [3] proposed a simulation–optimization approach using a genetic algorithm and reported that it reduced evacuation time by approximately 6% compared to a nearest-exit-based strategy.