Performance of Commercial Quantum Annealing Solvers for the Capacitated Vehicle Routing Problem

We provide an efficient analysis of the quality of the solutions returned by adiabatic quantum annealers for the Capacitated Vehicle Routing Problem (CVRP). Theoretical studies and simulations on classic hardware often assume that the computation in adiabatically closed systems occurs without environmental interference. However, this is not a realistic assumption for real systems. Therefore, these theory-based simulations on classical hardware or limited tests do not accurately assess the capability of current commercial quantum annealers . Therefore, it becomes essential to analyze the accuracy of solutions returned by commercial quantum annealers. To address this, we first developed the mathematical model using Constrained Quadratic Model to implement the CVRP problem on AQC. Later, we provide the comparative analysis on the accuracy of solutions returned by quantum annealer vs 1. benchmark datasets, 2. data size, 3. constraint density, and 4. problem complexity. As a result, we obtained an absolute error is between 0.12 to 0.55. We also observed that as the constraint density increases, the quality of the solution returned by the quantum annealer degrades. Therefore, more than the problem size, the model complexity plays a critical role, and practical applications should select formulations that minimize the constraint density.