Enhancing vehicle routing problem through a qubit-efficient Symmetric Arc Reduction using Quantum Approximate...

Finding the most efficient routes for a fleet of delivery vehicles remains a critical and costly challenge for nearly any logistics business. This core idea is known as the Vehicle Routing Problem (VRP). The primary goal is to minimize operational costs, such as the total travel distance or the number of trucks deployed, while ensuring all the customers are served. Because VRP is NP-hard, finding a perfect solution is often impossible, forcing industries to rely on classical approximate algorithms. However, quantum variational algorithms offer a new paradigm by iteratively optimizing parameters to navigate the solution space, presenting a new and promising avenue for finding better and faster solutions.

In this paper, we introduce Symmetric Arc Reduction in Quantum Approximate Optimization Algorithm (SAR-QAOA), which systematically eliminates redundant symmetric routing variables in the binary integer programming formulation prior to the Quadratic Unconstrained Binary Optimization (QUBO) formulation. The proposed SAR-QAOA encodes edge-based VRP while reducing the qubit requirement from n(n-1) to n(n-1)/2, thereby improving the resource efficiency of the QUBO formulation by prioritizing regions of the solution space that are more likely to contain high-quality solutions; SAR enhances both search accuracy and computational efficiency.

Experimental results on noiseless quantum simulators validate the feasibility of the proposed formulation and its integration with the QAOA framework, providing a promising foundation for future investigations on larger routing problems and evolving quantum hardware.