Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm

Utkarsh, Bikash K. Behera, Prasanta K. Panigrahi

Published 2020-02-02Version 1

In this paper, we describe the usage of 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 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 largely limited by the problem instance.