Quantum Optimization Solves 13-Location Vehicle Routing Problems with Multi-Angle QAOA and Clustered Decomposition

The Vehicle Routing Problem, a critical challenge in logistics and supply chain management, often becomes computationally intractable as the number of delivery locations increases, hindering efficient distribution networks. Shreetam Dash from the Center for Quantum Science and Technology, Siksha ’O’ Anusandhan, Shreya Banerjee from the University of Exeter, and Prasanta K. Panigrahi, along with their colleagues, now demonstrate a quantum approach that significantly expands the scale of solvable vehicle routing problems. Their method combines standard and multi-angle quantum algorithms, strategically breaking down a 13-location problem into smaller, manageable clusters. This innovative technique not only identifies optimal routes within each cluster with remarkable accuracy, matching classical optimisation results, but also achieves competitive performance for the overall inter-cluster routing, pushing the boundaries of quantum optimisation for real-world logistical challenges and extending solution capabilities beyond previous limitations of only a few locations.

The research focuses on developing a Hierarchical Quantum Optimization (HQO) algorithm that leverages the Quantum Approximate Optimization Algorithm (QAOA) in a multi-angle configuration. This method overcomes limitations of existing quantum algorithms when applied to problems with many locations, commonly found in real-world vehicle routing scenarios. The core of the approach involves a clustered decomposition technique, breaking the overall problem into smaller, more manageable subproblems based on geographical proximity.

The hierarchical structure enables the algorithm to tackle problems with up to 100 locations, demonstrating a substantial improvement over traditional QAOA implementations. Specifically, the team introduces a novel method for constructing the cost function within the QAOA framework, tailored to the constraints of the vehicle routing problem. This cost function incorporates factors such as distance travelled, vehicle capacity, and delivery time windows. The multi-angle QAOA configuration, combined with the clustered decomposition, significantly enhances the algorithm’s ability to find near-optimal solutions for complex vehicle routing instances. The authors explore a hybrid quantum-classical approach to optimize delivery routes, aiming to leverage the potential of near-term quantum computers for practical logistics applications. The core challenge is to find the most efficient routes for a fleet of vehicles to serve a set of customers, minimizing total travel distance or cost. This is a computationally hard problem, becoming increasingly complex with more customers and vehicles.

The research focuses on using QAOA, a variational quantum algorithm, to find approximate solutions to the VRP. QAOA is combined with classical optimization techniques in a hybrid approach. The VRP is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, suitable for implementation on quantum annealers or QAOA circuits. The performance of QAOA relies on optimizing its parameters, and the authors employed classical optimization algorithms to find the best parameter settings for the QAOA circuit. The research involved simulating the QAOA algorithm on classical computers to evaluate its performance, with the ultimate goal of running these algorithms on actual near-term quantum hardware.

The Spall algorithm, a derivative-free optimization method, was used to tune the parameters of the QAOA circuit. The research suggests that QAOA and hybrid quantum-classical algorithms could offer a potential advantage over classical algorithms for solving the VRP, particularly as quantum hardware improves. The authors emphasize the focus on near-term quantum devices and demonstrate that meaningful results can be obtained even with current hardware limitations. The combination of quantum and classical algorithms is essential for achieving good performance, with the quantum part handling the combinatorial optimization and the classical part optimizing the parameters and potentially performing post-processing. The team achieved this advancement through a hierarchical decomposition approach, utilizing K-means clustering to divide the problem into smaller subproblems, standard Quantum Approximate Optimization Algorithm (QAOA) for routing within each cluster, and Multi-Angle QAOA for optimizing connections between clusters. Results show that standard QAOA consistently identifies optimal solutions for the intra-cluster routing tasks, precisely matching the performance of classical optimization algorithms. 29% across diverse test instances. This demonstrates the potential of quantum methods to address complex logistical challenges, even with the inherent noise present in current quantum hardware. The authors acknowledge that the performance of the Multi-Angle QAOA relies on effective optimization of a substantial number of parameters, and the chosen optimization technique proved well-suited to this task.