Margarita Veshchezerova, Mikhail Somov, David Bertsche, Steffen Limmer, Sebastian Schmitt, Michael Perelshtein, Ayush Joshi, "A Hybrid Quantum-Classical Approach to the Electric Mobility Problem", IEEE Quantum Week 2023, 2023.

We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem. The original formulation is a Mixed Integer Linear Program with continuous variables and inequality constraints. To separate inequality constraints that are difficult for quantum routines we use a decomposition in master and pricing problems: the former targets the assignment of vehicles to reservations and the latter suggests vehicle exploitation plans that respect the battery state-of-charge constraints. The master problem is equivalent to the search for an optimal set partition. In our hybrid scheme, the master problem is reformulated in quadratic unconstrained binary optimization and solved with quantum annealing on the DWave Advantage system. We benchmark the annealing performance against the classical and quantum-inspired metaheuristics: simulated annealing, tabu search, and vector annealing by NEC. We found out that our new approach not only enables quantum-based methods but also provides comparable solutions to the initial mixed integer linear formulation in terms of optimality while being faster and scaling better to larger instances.