Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm

Abstract

In this paper, we describe the usage of the Quantum Approximate Optimization Algorithm (QAOA), which is a quantum-classical heuristic, to solve a combinatorial optimization and integer programming task known as Vehicle Routing Problem (VRP). We outline the Ising formulation for VRP and present a detailed procedure to solve VRP by minimizing its simulated Ising Hamiltonian using the IBM Qiskit platform. Here, we attempt to find solutions for the VRP problems: (4,2), (5,2), and (5,3), where each (n, k) represents a VRP problem with n locations and k vehicles. We find that the performance of QAOA is not just dependent upon the classical optimizer used, the number of steps p in which an adiabatic path is realized, or the way parameters are initialized, but also on the problem instance itself.

7 pages, 7 figures

References in corpus (14)

• Quantum Computing in the NISQ era and beyond
• Barren plateaus in quantum neural network training landscapes
• A Quantum Approximate Optimization Algorithm
• Hybrid quantum-classical algorithms and quantum error mitigation
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Concrete Categorical Model of a Quantum Circuit Description Language with Measurement
• $XY$-mixers: analytical and numerical results for QAOA
• A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
• Quantum annealing initialization of the quantum approximate optimization algorithm
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Benchmarking the Quantum Approximate Optimization Algorithm
• Parameter Concentration in Quantum Approximate Optimization
• A quantum algorithm to train neural networks using low-depth circuits
• Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits

Cited by in corpus (17)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum variational optimization: The role of entanglement and problem hardness
• Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem
• Analysis of The Vehicle Routing Problem Solved via Hybrid Quantum Algorithms in Presence of Noisy Channels
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem
• Calibrating the role of entanglement in variational quantum circuits
• Quantum Optimization Methods for Satellite Mission Planning
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management
• Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem
• Solving The Vehicle Routing Problem via Quantum Support Vector Machines
• QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems
• Alleviating the quantum Big-$M$ problem
• General Oscillator-Based Ising Machine Models with Phase-Amplitude Dynamics and Polynomial Interactions
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
• Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
• Qubit-efficient quantum combinatorial optimization solver