Applying quantum approximate optimization to the heterogeneous vehicle routing problem
arXiv:2110.06799 · doi:10.1038/s41598-024-76967-w
Abstract
Quantum computing offers new heuristics for combinatorial problems. With small- and intermediate-scale quantum devices becoming available, it is possible to implement and test these heuristics on small-size problems. A candidate for such combinatorial problems is the heterogeneous vehicle routing problem (HVRP): the problem of finding the optimal set of routes, given a heterogeneous fleet of vehicles with varying loading capacities, to deliver goods to a given set of customers. In this work, we investigate the potential use of a quantum computer to find approximate solutions to the HVRP using the quantum approximate optimization algorithm (QAOA). For this purpose we formulate a mapping of the HVRP to an Ising Hamiltonian and simulate the algorithm on problem instances of up to 21 qubits. We find that the number of qubits needed for this mapping scales quadratically with the number of customers. We compare the performance of different classical optimizers in the QAOA for varying problem size of the HVRP, finding a trade-off between optimizer performance and runtime.
arXiv comment17 pages, 11 figures
References in corpus (29)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Variational Quantum Algorithms
- Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms
- Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
- Ising formulations of many NP problems
- Quantum computational advantage using photons
- Noisy intermediate-scale quantum (NISQ) algorithms
- Quantum computational chemistry
- Trapped-Ion Quantum Computing: Progress and Challenges
- Logical quantum processor based on reconfigurable atom arrays
- Quantum algorithms: an overview
- Quantum information processing with superconducting circuits: a review
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Perspectives of quantum annealing: Methods and implementations
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Quantum Computing for Finance: State of the Art and Future Prospects
- Improving Variational Quantum Optimization using CVaR
- -mixers: analytical and numerical results for QAOA
- A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
- Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
- Benchmarking the Quantum Approximate Optimization Algorithm
- An Adaptive Optimizer for Measurement-Frugal Variational Algorithms
- Parameter Concentration in Quantum Approximate Optimization
- Classical Optimizers for Noisy Intermediate-Scale Quantum Devices
- Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
- Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
- Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem
- Quantum algorithms with local particle number conservation: noise effects and error correction