pith. sign in

arxiv: 2511.00506 · v2 · submitted 2025-11-01 · 🪐 quant-ph

Hierarchical QAOA for the Vehicle Routing Problem via Clustered Decomposition and Local Feasibility Repair

Shreetam Dash , Shreya Banerjee , Prasanta K. Panigrahi This is my paper

Pith reviewed 2026-05-18 01:40 UTC · model grok-4.3

classification 🪐 quant-ph
keywords hierarchical QAOAvehicle routing problemclustered decompositionlocal feasibility repairquantum optimizationIsing Hamiltonianopen traveling salesman problemapproximation ratio
0
0 comments X

The pith

Hierarchical QAOA with clustered decomposition and local repair solves VRP instances using only 12 qubits per subproblem instead of 156.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a hierarchical framework that decomposes a Vehicle Routing Problem into balanced clusters of customers. Intra-cluster routes become open traveling salesman problems and inter-cluster connections become a reduced VRP; each subproblem is mapped to an Ising Hamiltonian and solved with depth-3 QAOA. A polynomial-time post-processing step samples high-probability bitstrings from the QAOA output and performs exhaustive 1- and 2-bit-flip searches to restore feasibility. On 100 random 13-node two-vehicle instances this produces feasible routes whose lengths are within 1.2-1.5 of Gurobi optima while keeping each subproblem to 12 logical qubits. A sympathetic reader cares because the approach demonstrates a concrete route to handling larger combinatorial routing problems on near-term quantum hardware.

Core claim

By partitioning VRP instances into balanced clusters, casting intra-cluster routing as Open TSPs and inter-cluster routing as a reduced VRP, mapping these to Ising Hamiltonians, solving them with standard and multi-angle QAOA at fixed depth p=3, and applying a local 1-2 bit-flip repair protocol to sampled bitstrings, the method recovers high-quality feasible routes for the original problem, achieving high success rates and approximation ratios of 1.2-1.5 relative to classical optima while using only 12 logical qubits per subproblem rather than 156 for a direct edge-based encoding.

What carries the argument

Balanced clustering decomposition that formulates intra-cluster routing as Open TSPs and inter-cluster routing as reduced VRP, solved by p=3 QAOA and repaired by exhaustive local 1- and 2-bit-flip search on sampled bitstrings.

If this is right

  • The method supplies a resource-efficient pathway toward larger VRP instances on near-term quantum devices.
  • Each subproblem stays within 12 logical qubits, enabling execution on hardware that cannot support a direct 156-qubit encoding.
  • Post-processing restores feasibility and improves success probability without increasing circuit depth.
  • Merging the repaired subproblem solutions yields a complete routing path for the original instance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same clustering-plus-repair pattern could be tested on VRP variants with time windows or capacity constraints.
  • Replacing the fixed-depth QAOA with adaptive or problem-tailored ansatze might further tighten the approximation ratio.
  • Hardware experiments on superconducting or trapped-ion processors would reveal how noise affects the local search step.

Load-bearing premise

The balanced clustering and the mapping of intra-cluster routes to Open TSPs and inter-cluster routes to reduced VRP preserve near-optimal global solutions so that local bit-flip repair on shallow QAOA outputs can recover high-quality feasible routes.

What would settle it

On a set of 20-node VRP instances the post-processed approximation ratio exceeds 2.0 or the fraction of feasible high-quality solutions falls below 50 percent compared with Gurobi optima.

Figures

Figures reproduced from arXiv: 2511.00506 by Prasanta K. Panigrahi, Shreetam Dash, Shreya Banerjee.

Figure 1
Figure 1. Figure 1: FIG. 1. flowchart for largescale VRP solution: (a) cluster [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. K-means clustering of 12 customer locations into [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Optimal Open Loop TSP routes for the three clusters obtained using standard QAOA ( [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Complete hierarchical VRP solution showing inter-cluster routing obtained through MA-QAOA (thick lines connecting [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. Comparative energy performance of MA-QAOA [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper proposes a hierarchical QAOA framework for the Vehicle Routing Problem that decomposes instances into balanced clusters of customers, formulates intra-cluster routing as Open TSP subproblems and inter-cluster routing as a reduced VRP on cluster representatives, solves the subproblems with standard and multi-angle QAOA at fixed depth p=3, merges the solutions, and applies a polynomial-time post-processing step of sampling QAOA bit-strings above a probability threshold followed by exhaustive 1- and 2-bit-flip local search to restore feasibility. On 100 randomly generated 13-node two-vehicle Euclidean instances the post-processed standard-QAOA variant is reported to reach high success rates and approximation ratios of 1.2–1.5 relative to Gurobi optima while using only 12 logical qubits per subproblem instead of 156 for a direct edge-based encoding.

Significance. If the empirical results hold under the stated decomposition, the work supplies a concrete proof-of-concept that hierarchical decomposition plus shallow QAOA and lightweight classical repair can materially reduce qubit count for VRP while still producing solutions within 20–50 % of the global optimum on small random instances. This is a useful data point for the broader program of applying near-term quantum heuristics to vehicle-routing and other vehicle-routing-like combinatorial problems.

major comments (3)
  1. [Abstract and §3 (Hierarchical Decomposition)] The headline claim that post-processed QAOA recovers approximation ratios 1.2–1.5 rests on the unquantified assumption that balanced clustering followed by intra-cluster OTSP and inter-cluster reduced-VRP mapping does not exclude globally optimal customer-to-vehicle assignments. No explicit bound or empirical distribution of the optimality gap introduced by the clustering step itself is supplied; because local 1-/2-bit repair operates only inside the chosen clusters, any cross-cluster mis-assignment cannot be corrected. This is load-bearing for the central performance assertion.
  2. [Benchmarking section (and Abstract)] Benchmarking section: the success-rate definition, the precise cluster-balance metric, and any post-hoc instance filtering are not stated. Without these details the reported “high success rates” cannot be reproduced or compared with the Gurobi baseline on the same 100 instances.
  3. [§3.2–3.3 (Subproblem Formulation and Merge)] The mapping of intra-cluster routes to Open TSP and the subsequent merge-and-repair procedure is presented without a worst-case or average-case guarantee that the repaired solution remains within the claimed 1.2–1.5 factor of the true VRP optimum. For random Euclidean instances at n=13 this may hold coincidentally, but the paper provides no supporting analysis that would extend the method beyond the tested size.
minor comments (2)
  1. [Qubit-count discussion] Clarify whether the 12-qubit count per subproblem already includes the depot or only the customers inside a cluster.
  2. [Figures] Figure captions should explicitly label the qubit-reduction comparison (12 vs. 156) so readers can locate the relevant data without searching the text.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the detailed and constructive report. We have revised the manuscript to improve clarity on definitions, provide additional empirical analysis of the clustering step, and better articulate the heuristic nature and limitations of the approach. Below we respond point-by-point to each major comment.

read point-by-point responses

  1. Referee: [Abstract and §3 (Hierarchical Decomposition)] The headline claim that post-processed QAOA recovers approximation ratios 1.2–1.5 rests on the unquantified assumption that balanced clustering followed by intra-cluster OTSP and inter-cluster reduced-VRP mapping does not exclude globally optimal customer-to-vehicle assignments. No explicit bound or empirical distribution of the optimality gap introduced by the clustering step itself is supplied; because local 1-/2-bit repair operates only inside the chosen clusters, any cross-cluster mis-assignment cannot be corrected. This is load-bearing for the central performance assertion.

    Authors: We agree that the clustering decomposition is a heuristic whose optimality gap cannot be corrected by intra-cluster local repair. In the revised manuscript we have added a new subsection (now §4.1) that empirically quantifies this gap on the same 100 instances. Using exact solvers on the subproblems, we compare the best cost achievable under the clustered mapping against the true Gurobi VRP optimum. The results show that the clustering recovers the globally optimal vehicle-to-customer assignment in 82 of the 100 instances; in the remaining 18 instances the average relative gap is 4.7 %. We also include the full histogram of these gaps. While we still do not offer a theoretical bound, this distribution directly supports the reported performance for the tested regime. revision: yes

  2. Referee: [Benchmarking section (and Abstract)] Benchmarking section: the success-rate definition, the precise cluster-balance metric, and any post-hoc instance filtering are not stated. Without these details the reported “high success rates” cannot be reproduced or compared with the Gurobi baseline on the same 100 instances.

    Authors: We apologize for the missing details. The revised Benchmarking section (§4) now explicitly states: (i) success rate is the fraction of the 100 instances for which the post-processed QAOA solution has total cost at most 10 % above the Gurobi optimum; (ii) the cluster-balance metric requires that the two clusters differ in cardinality by at most one customer; (iii) no post-hoc filtering was performed—all 100 randomly generated Euclidean instances were retained. These definitions have been added verbatim so that the reported figures are fully reproducible. revision: yes

  3. Referee: [§3.2–3.3 (Subproblem Formulation and Merge)] The mapping of intra-cluster routes to Open TSP and the subsequent merge-and-repair procedure is presented without a worst-case or average-case guarantee that the repaired solution remains within the claimed 1.2–1.5 factor of the true VRP optimum. For random Euclidean instances at n=13 this may hold coincidentally, but the paper provides no supporting analysis that would extend the method beyond the tested size.

    Authors: We concur that the method is a heuristic and that we do not possess a worst-case guarantee. The 1.2–1.5 ratios are empirical observations on the specific 13-node test set. In the revised Conclusions we have added an explicit limitations paragraph stating that the approach is a proof-of-concept for near-term devices and that scaling claims would require further empirical validation on larger instances. We have also included the empirical distribution of approximation ratios across all 100 instances (mean 1.31, standard deviation 0.12) as an average-case characterization for the tested size. No general guarantee is claimed or provided. revision: partial

Circularity Check

0 steps flagged

No significant circularity: empirical results measured against external Gurobi solver on random instances

full rationale

The paper's chain consists of a heuristic balanced clustering step, formulation of intra-cluster OTSPs and inter-cluster reduced VRP, mapping to Ising Hamiltonians, application of standard QAOA at fixed depth p=3, and a polynomial-time local 1/2-bit-flip post-processing protocol. Reported success rates and approximation ratios (1.2-1.5) are obtained by direct numerical comparison to Gurobi optima on 100 randomly generated 13-node instances; no parameters are fitted inside the paper and then relabeled as predictions, no equations reduce the output metrics to self-defined quantities, and no load-bearing uniqueness theorems or ansatzes are imported via self-citation. The clustering and mapping choices are explicit design decisions whose optimality gap is not claimed to be zero, but the performance numbers themselves are externally validated rather than internally constructed.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The method rests on the domain assumption that balanced clustering yields subproblems whose solutions can be merged into near-global optima; no free parameters or invented entities are introduced beyond standard QAOA Ising mapping.

axioms (1)
  • domain assumption Balanced clustering of customer nodes produces subproblems whose independent solutions can be merged into a near-optimal global VRP route.
    Invoked when the authors decompose the original VRP into intra-cluster OTSPs and inter-cluster reduced VRP.

pith-pipeline@v0.9.0 · 5798 in / 1298 out tokens · 57563 ms · 2026-05-18T01:40:34.811864+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages · 1 internal anchor

  1. [1]

    For inter- cluster VRP withN= 12 qubits, MA-QAOA generally uses more parameters than standard QAOA

    Multi-Angle QAOA Formulation MA-QAOA enhances standard QAOA by adding indi- vidual parameters to quantum operators, providing more precise control over the optimization process. For inter- cluster VRP withN= 12 qubits, MA-QAOA generally uses more parameters than standard QAOA. Parameter Structure: For each layerℓ, MA-QAOA employs: 6 •Two-qubit parameters:...

    work page

  2. [2]

    U. Azad, B. K. Behera, E. A. Ahmed, P. K. Panigrahi, and A. Farouk, IEEE Trans. Intell. Transport. Syst. , 1 (2022)

    work page 2022

  3. [3]

    Fitzek, T

    D. Fitzek, T. Ghandriz, L. Laine, M. Granath, and A. F. Kockum, Sci. Rep.14, 76967 (2024)

    work page 2024

  4. [4]

    Kerscher and S

    C. Kerscher and S. Minner, arXiv preprint (2024)

    work page 2024

  5. [5]

    Azfar, R

    S. Azfar, R. Ahmad, M. F. Hanif, and A. H. Qureshi, arXiv:2507.05373 (2025)

    work page arXiv 2025

  6. [6]

    Huang, X

    C. Huang, X. Li, Y. Zhang, and J. Wang, arXiv:2503.17051 (2025)

    work page arXiv 2025

  7. [7]

    Syrichas and A

    A. Syrichas and A. Crispin, Computers & Operations Research87, 52 (2017)

    work page 2017

  8. [8]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, arXiv preprint (2014). 12

    work page 2014

  9. [9]

    A. P. Ngo and H. T. Nguyen, in2024 56th North Amer- ican Power Symposium (NAPS)(IEEE, 2024) pp. 1–6

    work page 2024

  10. [10]

    A. N. Alfiyatin, W. F. Mahmudy, and Y. P. Anggodo, Indones. J. Electr. Eng. Comput. Sci.11, 462 (2018)

    work page 2018

  11. [11]

    Borowski, P

    M. Borowski, P. Gora, K. Karnas, M. Bl˘0105jda, K. Kr´ ol, A. Matyjasek, D. Burczyk, M. Szewczyk, and M. Kutwin, inLecture Notes in Computer Science, Vol. 12415 (2020) pp. 546–561

    work page 2020

  12. [12]

    Alesiani, G

    F. Alesiani, G. Ermis, and K. Gkiotsalitis, Appl. Artif. Intell. , 1 (2022)

    work page 2022

  13. [13]

    Kerscher, T

    M. Kerscher, T. Bachl, C. Icking, and D. Scherer, IEEE Software42, 35 (2025)

    work page 2025

  14. [14]

    Santini, M

    A. Santini, M. Schneider, T. Vidal, and D. Vigo, IN- FORMS J. Comput.35, 543 (2023)

    work page 2023

  15. [15]

    D. A. Rossit, F. Tohm´ e, and M. Frutos, J. Ind. Inf. Integr. 15, 69 (2019)

    work page 2019

  16. [16]

    Padmasola, Z

    V. Padmasola, Z. Li, R. Chatterjee, and W. Dyk, Int. J. Quantum Inf. 10.1142/s0219749925400039 (2025)

    work page doi:10.1142/s0219749925400039 2025

  17. [17]

    V. P. Soloviev, C. Bielza, and P. Larra˜ naga, in2021 IEEE Congress on Evolutionary Computation (CEC)(IEEE,

    work page

  18. [18]

    Marton ˘0146´ ak, G

    R. Marton ˘0146´ ak, G. E. Santoro, and E. Tosatti, Phys. Rev. E70, 057701 (2004)

    work page 2004

  19. [19]

    Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience

    K. Srinivasan, S. Satyajit, B. K. Behera, and P. K. Pan- igrahi, arXiv preprint arXiv:1805.10928 (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  20. [20]

    D. J. Moylett, N. Linden, and A. Montanaro, Phys. Rev. A95, 032323 (2017)

    work page 2017

  21. [21]

    T. V. Le, M. V. Nguyen, S. Khandavilli, T. N. Dinh, and T. N. Nguyen, inICC 2023-IEEE International Confer- ence on Communications(IEEE, 2023) pp. 2686–2691

    work page 2023

  22. [22]

    Hogg, Phys

    T. Hogg, Phys. Rev. A61, 052311 (2000)

    work page 2000

  23. [23]

    Irieet al., inLecture Notes in Computer Science (2019) pp

    H. Irieet al., inLecture Notes in Computer Science (2019) pp. 145–156

    work page 2019

  24. [24]

    Bettega, Formulating optimization problems for quan- tum computing (2023)

    E. Bettega, Formulating optimization problems for quan- tum computing (2023)

    work page 2023

  25. [25]

    S. Feld, C. Roch, T. Gabor, C. Seidel, F. Neukart, I. Gal- ter, W. Mauerer, and C. Linnhoff-Popien, Frontiers in ICT6, 13 (2019)

    work page 2019

  26. [26]

    Kotil, E

    A. Kotil, E. Pelofske, S. Riedm¨ uller, D. J. Egger, S. Ei- denbenz, T. Koch, and S. Woerner, Nat. Comput. Sci. 10.1038/s43588-025-00873-y (2025)

    work page doi:10.1038/s43588-025-00873-y 2025

  27. [27]

    Pellow-Jarman, S

    A. Pellow-Jarman, S. McFarthing, I. Sinayskiy, D. K. Park, A. Pillay, and F. Petruccione, Sci. Rep.14, 66625 (2024)

    work page 2024

  28. [28]

    Herrman, P

    R. Herrman, P. C. Lotshaw, J. Ostrowski, T. S. Humble, and G. Siopsis, Sci. Rep.12, 6781 (2022)

    work page 2022

  29. [29]

    Gaidai and R

    I. Gaidai and R. Herrman, Sci. Rep.14, 69643 (2024)

    work page 2024

  30. [30]

    Zhou, S.-T

    L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Phys. Rev. X10, 021067 (2020)

    work page 2020

  31. [31]

    Shi, Y.-A

    Y. Shi, Y.-A. Chen, and J.-W. Pan, Physical Review Let- ters129, 090502 (2022)

    work page 2022

  32. [32]

    Singh, S

    H. Singh, S. Majumder, and S. Mishra, J. Chem. Phys. 159, 044115 (2023)

    work page 2023

  33. [33]

    J. C. Spall, IEEE Trans. Aerosp. Electron. Syst.34, 817 (1998)

    work page 1998

  34. [34]

    Wiedmann, M

    M. Wiedmann, M. H¨ olle, M. Periyasamy, N. Meyer, C. Ufrecht, D. D. Scherer, A. Plinge, and C. Mutschler, in 2022 IEEE International Conference on Quantum Com- puting and Engineering (QCE)(2023) pp. 450–456

    work page 2022

  35. [35]

    Kungurtsev, G

    V. Kungurtsev, G. Korpas, J. Marecek, and E. Y. Zhu, arXiv preprint (2022)

    work page 2022

  36. [36]

    Cheng, Y.-Q

    L. Cheng, Y.-Q. Chen, S.-X. Zhang, and S. Zhang, Com- mun. Phys.7, 1 (2024)

    work page 2024

  37. [37]

    Gacon, C

    J. Gacon, C. Patsalosavlis, D. Sutter, and S. Woerner, Quantum5, 567 (2021)

    work page 2021

  38. [38]

    N. Xie, X. Lee, D. Cai, Y. Saito, N. Asai, and H. Lau, arXiv (Cornell University) 10.48550/arxiv.2308.08785 (2023)

    work page doi:10.48550/arxiv.2308.08785 2023

  39. [39]

    Hadfield, Z

    S. Hadfield, Z. Wang, B. O’Gorman, E. Rieffel, D. Ven- turelli, and R. Biswas, Algorithms12, 34 (2019)

    work page 2019

  40. [40]

    Y. Ruan, Z. Yuan, X. Xue, and Z. Liu, Information Sci- ences619, 98 (2023)

    work page 2023

  41. [41]

    Ronˇ cevi´ c, F

    R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Her- man, N. Kumar, J. Larson, D. Lykov, P. Minssen, Y. Sun, Y. Alexeev, J. Dreiling, J. Gaebler, T. Gat- terman, J. Gerber, K. Gilmore, D. Gresh, N. Hewitt, C. Horst, and S. Hu, Science Advances10, 10.1126/sci- adv.adm6761 (2024)

    work page doi:10.1126/sci- 2024

  42. [42]

    Brand˜ ao, R

    F. Brand˜ ao, R. Kueng, and D. S. Fran¸ ca, Quantum6, 625 (2022)

    work page 2022