Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes

Abstract

With the expansion of complex transport infrastructure, new paths for linking different destinations have emerged, allowing the definition of multiple routes. The introduction of new roads may also lead to disruptions in traffic flow. This problem can be generalized into a special case of VRP, which aims to find the optimal route for a fleet of vehicles within a network of destinations. Finding solutions to this problem requires an exponential number of operations, hindering the ability of exact solvers to deal with large instances, which must therefore be tackled using heuristics, often leading to suboptimal results. Quantum-based algorithms may allow us to find exact solutions in polynomial time with high probability, offering a potential future alternative to classical solvers and in this work, we focus on the QAOA. Our novel contributions are a parameter-initialization strategy that improves the convergence probability and the integration of the subtour constraints directly into the optimization without using additional qubits by employing an approximation of exponential equality constraints. We believe that our results pave the way for effectively solving instances of VRP using quantum-based solutions, leveraging the space-efficient problem encoding and our initialization strategy, which limits the effect of barren-plateau under random parameter initialization.

The paper studies QAOA for the vehicle routing problem (VRP), focusing on parameter initialization and encoding subtour-elimination inequalities without slack-variable qubits. It uses a directed-edge encoding with $N(N-1)$ binary variables for $N$ nodes, including the depot. The initialization procedure evaluates $D$ parameter settings with every layer sharing $\gamma_k=\beta_k=d\pi/D$, then starts variational optimization from the lowest-energy setting. This adds $O(D)$ energy evaluations. Comparisons against random initialization use 50 random instances in each of five three- or four-node VRP classes and report higher average probability of sampling optimal solutions. The evidence concerns optimization performance rather than an asymptotic bound on gradient concentration. For subtour elimination, the paper applies an existing unbalanced-penalty approach: exponential penalties for inequality violations are approximated by quadratic expressions and incorporated into the QUBO. This avoids auxiliary qubits but retains sums over node subsets and introduces penalty coefficients requiring tuning. Optuna searches these coefficients, and Adam optimizes the QAOA parameters on noiseless statevector simulators. Reported examples involve $N=3$–$5$ nodes, $6$–$24$ QAOA layers, and optimal-solution sampling probabilities ranging from approximately $0.423$ to $0.9999$. The stated limitations are the small instance sizes, absence of noise characterization, and sensitivity to penalty hyperparameters: the ground state need not encode the optimal feasible route unless those coefficients are suitably chosen. Changing the node or vehicle count requires renewed hyperparameter tuning; broadly transferable settings remain future work.