A Hybrid Quantum-Classical Approach to the Electric Mobility Problem
Authors:
- Margarita VeshchezerovaMVMargarita Veshchezerova
- Mikhail SomovMSMikhail Somov
- David BertscheDBDavid Bertsche
- Steffen LimmerSLSteffen Limmer
- Sebastian SchmittSSSebastian Schmitt
- Michael PerelshteinMPMichael Perelshtein
- Ayush Joshi TripathiATAyush Joshi Tripathi
Preprint
Abstract
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 a quadratic unconstrained binary optimization problem which can be solved with quantum annealing on the DWave Advantage system. On large instances, we benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics: simulated annealing, tabu search, and vector annealing by NEC. The numerical results with purely classical solvers are comparable to the solutions from the traditional mixed integer linear programming approaches in terms of solution quality while being faster. In addition, it scales better to larger instances. The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints. We show this by initial studies on DWave hardware where optimal solutions can be found for small instances.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Hybrid Quantum-Classical Heuristic to Solve Large-Scale Integer Linear ProgramsPhysical Review Applied, 2023
- Computational Methods for Scheduling the Charging and Assignment of an On-Site Shared Electric Vehicle FleetIEEE Access, 2022
- Quantum annealing for industry applications: introduction and reviewReports on Progress in Physics, 2022
- Penalty and partitioning techniques to improve performance of QUBO solversDiscrete Optimization, 2022
- Driver Hamiltonians for constrained optimization in quantum annealingPhysical Review A, 2016
- Quantum Annealing for Constrained OptimizationPhysical Review Applied, 2016
- A new approach for modeling and solving set packing problemsEuropean Journal of Operational Research, 2008
- Multistart Tabu Search Strategies for the Unconstrained Binary Quadratic Optimization ProblemAnnals of Operations Research, 2004
- Strong duality theorem2001
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998