A Flexible Hybrid Quantum Algorithm for Vehicle Routing

The capacitated vehicle routing problem (CVRP) is an important problem for logistics optimization in supply chain. We propose a novel hybrid classical quantum algorithm that works by splitting the problem into a quantum travelling salesman problem (TSP) phase and a partitioning phase. In order to validate our methods, we run tests using D-Wave's Leap framework on random test cases, as well as a real-world data set from the retail domain. We run a comparison study against existing state of the art hybrid quantum-classical approaches for the CVRP, in addition to classical heuristic methods. Our method is shown to have the additional flexibility to handle fleet extension, and the solution quality is at least as good as the considered state of the art quantum hybrid algorithms. Further, we show that the algorithm can easily be modified for tackling other realistic vehicle routing variants.