Hierarchical QAOA for the Vehicle Routing Problem via Clustered Decomposition and Local Feasibility Repair
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917480204599296 |
|---|---|
| author | Dash, Shreetam Banerjee, Shreya Panigrahi, Prasanta K. |
| author_facet | Dash, Shreetam Banerjee, Shreya Panigrahi, Prasanta K. |
| contents | We propose a hierarchical quantum approximate optimization framework for solving large-scale Vehicle Routing Problems (VRP) using Quantum Approximate Optimization Algorithm (QAOA). The method decomposes a VRP instance into balanced clusters of customer nodes. We formulate intra-cluster routing as Open loop Traveling Salesman Problems (OTSPs), and inter-cluster routing as a reduced VRP over the cluster representatives and depot. We then map the sub-problems to Ising Hamiltonians and solve with both standard and multi-angle QAOA variants at fixed depth p=3, and merge them to produce a routing path for the original VRP. Additionally, to improve solution feasibility and success probability, we introduce a polynomial-time post-processing protocol that samples candidate bit-strings from the QAOA output using a probability threshold and performs exhaustive local 1 and 2 bit-flip searches around these candidates. Benchmarking on 100 randomly generated 13-node, two-vehicle VRP instances, we show that the post-processed standard-QAOA implementation achieves high success rates and approximation ratios within 1.2-1.5 compared to classical optimizer (Gurobi) solutions, while requiring only 12 logical qubits per subproblem instead of 156 qubits for a direct edge-based encoding. These results provide a proof-of-concept demonstration that hierarchical decomposition, shallow QAOA, and local bit-flip repair can offer a scalable and resource-efficient pathway toward larger VRP instances on near-term quantum devices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_00506 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hierarchical QAOA for the Vehicle Routing Problem via Clustered Decomposition and Local Feasibility Repair Dash, Shreetam Banerjee, Shreya Panigrahi, Prasanta K. Quantum Physics We propose a hierarchical quantum approximate optimization framework for solving large-scale Vehicle Routing Problems (VRP) using Quantum Approximate Optimization Algorithm (QAOA). The method decomposes a VRP instance into balanced clusters of customer nodes. We formulate intra-cluster routing as Open loop Traveling Salesman Problems (OTSPs), and inter-cluster routing as a reduced VRP over the cluster representatives and depot. We then map the sub-problems to Ising Hamiltonians and solve with both standard and multi-angle QAOA variants at fixed depth p=3, and merge them to produce a routing path for the original VRP. Additionally, to improve solution feasibility and success probability, we introduce a polynomial-time post-processing protocol that samples candidate bit-strings from the QAOA output using a probability threshold and performs exhaustive local 1 and 2 bit-flip searches around these candidates. Benchmarking on 100 randomly generated 13-node, two-vehicle VRP instances, we show that the post-processed standard-QAOA implementation achieves high success rates and approximation ratios within 1.2-1.5 compared to classical optimizer (Gurobi) solutions, while requiring only 12 logical qubits per subproblem instead of 156 qubits for a direct edge-based encoding. These results provide a proof-of-concept demonstration that hierarchical decomposition, shallow QAOA, and local bit-flip repair can offer a scalable and resource-efficient pathway toward larger VRP instances on near-term quantum devices. |
| title | Hierarchical QAOA for the Vehicle Routing Problem via Clustered Decomposition and Local Feasibility Repair |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2511.00506 |