Quantum Integer Programming for the Capacitated Vehicle Routing Problem

Quantum computing, with its inherent speedups, holds the promise of revolutionizing optimization problems by providing faster and more efficient solutions. In this study, we explore the application of quantum optimization techniques to tackle the challenging Vehicle Routing Problem (VRP) and its popular variant, the Capacitated VRP (CVRP). The VRP is a combinatorial optimization problem centered on determining the most efficient routes for a fleet of vehicles to deliver goods to a set of customers, while minimizing either the total travel distance or overall cost. Given its classification as a well-known NP-hard problem, finding optimal solutions for larger instances can be computationally demanding. By leveraging the power of quantum computing, we aim to explore novel approaches and algorithms that can potentially offer significant improvements in solving VRP instances. To formulate the VRP, we employ the classical two-index approach, where binary variables (x_{ij}) indicate whether an arc (i, j) is traversed by a vehicle. To ensure meaningful solutions, we incorporate subtour elimination constraints. Although these constraints improve the final solutions, they quickly become problematic when transitioning to QUBO formulation, as they introduce many integer slack variables, resulting in an excessive number of variables for gate-based quantum models. To address this issue, we also explore a heuristic two-phase approach. According to this heuristic, nodes are first clustered into disjoint groups, with each cluster containing the depot. Routing is then performed individually within each cluster. During the clustering phase, we investigate various methodologies. Initially, we approach the problem as a Multi Knapsack Problem (MKP) with a quadratic objective function. However, this formulation presents challenges for gate-based quantum algorithms, which struggle to navigate the complex energy landscape of the MKP. Subsequently, we address the clustering phase by employing a customized version of the Louvain Modularity Maximization Algorithm, enhanced with classical greedy subroutines aimed at aligning the clusters with the forthcoming routing phase. Additionally, we explore an alternative approach where we model the clustering phase as a Modularity Maximization problem, which is tackled using quantum algorithms. To ensure coherence with the subsequent routing phase, we introduce two supplementary classical greedy subroutines to refine the clusters identified through Modularity Maximization. The routing phase is instead modelled as a Travelling Salesman Problem (TSP). Here, we sequentially add subtour elimination constraints as needed (DFJ strategy) rather than adding all the constraints in advance (MTZ strategy). This adaptive approach significantly reduces the number of qubits, making the models suitable for both gate-based and annealing-based quantum devices. For quantum optimization, we investigate various quantum algorithms, including Quantum Adiabatic Computation, Quantum Approximate Optimization Algorithm (QAOA), and Variational Quantum Eigensolver (VQE) with hardware-efficient ansatz. To gauge the performance of these quantum algorithms, we employ Gurobi as a classical benchmarking method. Furthermore, owing to the current hardware limitations of NISQ devices, our focus is primarily on instances of relatively modest size. By analyzing these quantum approaches and comparing them with classical methods, we aim to gain insights into the potential quantum speedups for solving complex VRP instances. With ongoing advancements in quantum hardware development, hopefully, quantum optimization will become a robust strategy for real-world transportation and logistics applications.