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.
17 pages, 11 figures
References in corpus (8)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Variational Quantum Algorithms
- Quantum computational advantage using photons
- Noisy intermediate-scale quantum (NISQ) algorithms
- Logical quantum processor based on reconfigurable atom arrays
- Parameter Concentration in Quantum Approximate Optimization
- 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