Solving the Capacitated Vehicle Routing Problem Using the Quantum Approximate Optimization Algorithm: A Benchmark Against Classical Guided Local Search

The Capacitated Vehicle Routing Problem (CVRP) is a combinatorial optimization problem that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, making it a potential application for near-term quantum optimization. This paper benchmarks the Quantum Approximate Optimization Algorithm (QAOA, p = 2) against Google OR-Tools Guided Local Search on a seeded instance with three customers and two vehicles. The study examines the QUBO formulation, energy spectrum, optimization behavior, penalty weights, Hamiltonian scaling, and circuit depths. The experiments show that the tested QAOA configurations do not reliably concentrate probability on optimal solutions. The classical solver identifies the optimal solution for the selected instance. The study provides a reproducible baseline and discusses limitations and future research directions. The findings are limited to the tested instance, formulation, and optimization configurations.