Hierarchical Quantum Optimization for Large-Scale Vehicle Routing: A Multi-Angle QAOA Approach with Clustered Decomposition

Abstract

We present a quantum optimization methodology for solving large-scale Vehicle Routing Problem (VRP) using a combination of standard and Multi-Angle Quantum Approximate Optimization Algorithms (MA-QAOA). The approach decomposes 13-locations based VRP problems through clustering into three balanced clusters of 4 nodes each, then applies standard QAOA for intra-cluster Open Loop Traveling Salesman Problem (OTSP) and MA-QAOA for inter-cluster VRP routing. Validation across 10 distinct datasets demonstrates that standard QAOA consistently identifies optimal solutions for intra-cluster routing, which is matching classical Gurobi optimizer results exactly. More significantly, MA-QAOA with Simultaneous Perturbation Stochastic Approximation(SPSA) optimizer demonstrates competitive performance against classical optimization methods, ultimately converging towards a solution that closely approximates the classical Gurobi optimizer result.The clustered decomposition enables quantum optimization of problem sizes generally larger than previous quantum VRP implementations, advancing from 4-6 location limits to 13-location problems while maintaining solution quality.