Quantum Annealing Algorithm for Vehicle Scheduling

Abstract

In this paper we propose a new strategy for solving the Capacitated Vehicle Routing Problem using a quantum annealing algorithm. The Capacitated Vehicle Routing Problem is a variant of the Vehicle Routing Problem being characterized by capacitated vehicles which contain goods up to a certain maximum capacity. Quantum annealing is a metaheuristic that uses quantum tunneling in the annealing process. We discuss devising a spin encoding scheme for solving the Capacitated Vehicle Routing Problem with a quantum annealing algorithm and an empirical approach for tuning parameters. We study the effectiveness of quantum annealing in comparison with best known solutions for a range of benchmark instances.