Pith. sign in

REVIEW 3 major objections 6 minor 38 references

Quantum Annealing based Hybrid Strategies for Real Time Route Optimization

T0 review · 3 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Splitting CVRP into fuzzy clustering plus quantum-annealed routing yields five-instance tours within 17% of best-known costs in about 15 minutes each.

desk verdict The H3S pipeline is a legitimate small extension of Feld et al., but the paper never fully specifies the QUBO models, so the reported route costs cannot be verified as feasible CVRP solutions. read the letter →

arxiv 2412.02720 v1 pith:HT35WI3M submitted 2024-11-21 quant-ph cs.CEcs.ET

Sushil Mario , Pavan Teja Pothamsetti , Louie Antony Thalakottor , Trisha Vishwanath , Sanjay H.A , Anees Ahmed , Salvatore Sinno , Shruthi Thuravakkath
show 1 more author
Sinthuja M
This is my paper · ORCID
classification quant-phcs.CEcs.ET MSC 90C2790C5981P68
keywords quantumannealingcapacitatedvehicleroutingproblemQUBOfuzzyC-meansclusteringhybridclassical-quantumalgorithmtravelingsalesmanrouteoptimizationlogistics
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to establish that a hybrid classical-quantum pipeline can produce usable approximate solutions to the Capacitated Vehicle Routing Problem (CVRP) in about fifteen minutes per instance. The authors split the problem into a capacitated clustering phase, run on a classical computer with fuzzy C-means, and a routing phase whose TSP/CVRP subproblems are encoded as QUBO Hamiltonians and minimized on a quantum annealer. They propose two variants: H2S, which routes each cluster directly as a TSP, and H3S, which adds an intermediate CVRP layer over cluster centroids before expanding back to customers. On five benchmark instances with 32 to 37 customers, both return tours with optimality gaps of roughly 5 to 17 percent above known best solutions, and one further H2S instance produced no feasible solution. If the QUBO encoding is correct, this supports the idea that quantum annealing can assist classical solvers for small real-time routing problems.

What carries the argument

The load-bearing object is the QUBO Hamiltonian built from binary edge variables $x_{ij}^t$ indicating that truck $t$ traverses edge $(i,j)$. The objective is the sum of edge costs, and the constraints — each customer visited once, each truck leaves the depot once, route continuity, capacity, and subtour elimination via a step variable — are folded in as Lagrange-weighted penalties, with the same model reused for TSP by dropping the capacity constraint. Around this, the classical side is Fuzzy C-Means clustering with depot copies and an iterative preference-and-capacity assignment module; H3S adds a compressed CVRP layer on cluster centroids before the final TSP expansion.

What would settle it

Run one of the reported instances (for example A-n32-k5) with the H3S QUBO on a classical simulator, decode the lowest-energy samples into routes, and check every route against the capacity and single-visit constraints; if any decoded low-energy sample violates a constraint, then the Table 2 route costs are not valid CVRP solutions and the central claim collapses.

Watch

Extended reading notes

Core claim

The paper's central claim is that the H2S and H3S strategies produce promising results in both solution time and solution cost. Concretely, after fuzzy C-means clustering with depot copies and capacity-aware assignment, each cluster is routed either as a TSP (H2S) or through a compressed CVRP over centroids followed by cluster expansion and TSP (H3S). The QUBO Hamiltonians are minimized by quantum annealing, and Table 2 reports total route costs of 695 to 938 against best-known values of 661 to 799 for five instances, corresponding to gaps around 5 to 17 percent, with the annealer taking roughly 15 minutes per instance. The paper also makes a preliminary observation that H3S tends to do better when the depot lies at the corner of the instance and H2S when the depot is central.

Load-bearing premise

The central validity assumption is that the QUBO Hamiltonians used in Section 4.4.2 encode the CVRP constraints correctly, so that any low-energy bitstring the annealer returns decodes to a feasible set of truck routes.

Editorial extensions

If this is right

  • If the QUBO encoding is sound, the two-phase decomposition lets a current quantum annealer return feasible CVRP tours for instances with 32 to 37 customers in about 15 minutes, a scale beyond what direct annealer TSP formulations handled in earlier work.
  • The H3S compressed-cluster step gives a way to assign multiple clusters to one truck, which matters when truck capacity is large relative to cluster demand.
  • The reported depot-location pattern, if it holds, gives a cheap rule for choosing between H2S and H3S: corner depots favor H3S, central depots favor H2S.
  • The approach does not claim to beat classical solvers; it claims a practical quality-time tradeoff for near-real-time logistics.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The real bottleneck may be the clustering assignment rather than the annealer: any error in assigning a node to a wrong cluster is baked into the final route cost, so better capacity-aware clustering could shrink the gap more than a better annealer.
  • A natural testable extension is to replace the quantum TSP solver with a classical exact TSP solver on the same clusters; the gap between those results and the quantum ones would isolate the annealer's contribution to the optimality gap.
  • The five-instance depot-location pattern is underpowered, but it suggests a meta-heuristic: use instance geometry to pick the decomposition strategy adaptively.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper proposes two hybrid classical-quantum strategies, H2S and H3S, for the Capacitated Vehicle Routing Problem (CVRP). Both use Fuzzy C-Means clustering on a classical computer and quantum annealing on a D-Wave machine for routing: H2S solves a TSP per cluster, while H3S first solves a CVRP over cluster centroids and then a TSP per route. The authors evaluate the strategies on five small VRPLib instances (32–37 customers) and report costs with optimality gaps of roughly 8–19% relative to best-known solutions. They also offer a preliminary, qualitative analysis of when each approach performs better based on customer distribution and depot location.

Significance. If the reported solutions are feasible and the encoding is correct, the paper demonstrates that a hybrid fuzzy-clustering/quantum-annealing pipeline can produce moderate-quality CVRP tours on small instances. This would be a useful application note for practitioners exploring hybrid quantum-classical optimization. However, the current manuscript does not provide the actual QUBO Hamiltonians, does not report repeated runs or statistical measures, and lacks any classical baseline, so the central performance claim is not yet substantiated. The contribution is potentially salvageable but requires substantial additional evidence.

major comments (3)
  1. [Section 4.4.2] The objective function and all five Hamiltonian equations for the CVRP QUBO are missing or garbled in the manuscript; the formulas do not render. Since the central claim that the reported routes are feasible CVRP tours depends entirely on this QUBO correctly encoding single-visit, depot-first, route-validity, capacity, and subtour-elimination constraints, the reader cannot verify that the costs in Table 2 correspond to valid solutions. The paper's own statement that 'There was no feasible solution found for the H2S instance of A-n33-k6' shows the pipeline can produce infeasible output, and without the explicit Hamiltonians, penalty weights, and decoding procedure, the feasibility of every reported solution is unverified.
  2. [Section 5, Table 2 and text] The text immediately after Table 2 claims that 'the H3S solutions are significantly lesser than the H2S solutions for instances A–n33-k5, A-n33-k6, A-n34-k5, A-n37-k5', but the table shows the opposite for A-n33-k5 (H2S: 695 vs H3S: 712) and A-n37-k5 (H2S: 763 vs H3S: 766), and A-n33-k6 does not appear in Table 2 at all. The comparative evaluation of H2S and H3S is therefore contradicted by the paper's own data.
  3. [Section 5] The experimental methodology reports only a single run per instance, with no error bars, no repeated annealing samples, and no statistical analysis. Since D-Wave annealing is stochastic, a single solution value is insufficient to support the optimality-gap claims. Moreover, no classical baseline is provided (e.g., the same clustering followed by a classical TSP solver, or a standard CVRP heuristic), so the abstract's claim of 'promising results, both in terms of solution time and solution cost' is unsupported: no comparison of solution time to classical alternatives is given, and the absolute gaps of 8–19% are not contextualized.
minor comments (6)
  1. [Section 4.1] The FCM centroid and membership-update equations are not rendered; please check the mathematical display.
  2. [Section 4.2] The sentence 'We begin the assignment algorithm by associating each node with its most preferred cluster centroid, .' contains a missing symbol and should be completed.
  3. [Section 5] The text refers to 'From table 1' when discussing the results table; the table numbering should be corrected to Table 2.
  4. [Section 5, Figures] Figure numbering is inconsistent: the text references Fig. 4 and Fig. 5, but the displayed figures are labeled Fig. 6 and Fig. 7.
  5. [References] References [37] and [38] appear in the bibliography but are not cited anywhere in the text.
  6. [Section 5] The statement that 'the computational time for the quantum annealer is 15 minutes to solve the problem' is ambiguous; specify whether this is QPU time, wall-clock time, or total hybrid runtime, and include standard deviations if available.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: evaluation is against external VRPlib optima; the only self-referential element (Table 3) is explicitly post-hoc and not presented as a prediction.

full rationale

The central claim, that H2S and H3S return routes with the costs and optimality gaps shown in Table 2, is tested against externally published best-known and proven-optimal values from the VRPlib class A instances (Augerat et al. 1995). No parameter is fitted to those target values: the FCM clustering, assignment procedure, and QUBO construction are described as fixed heuristics before the experiments, and the route costs are compared with the published optima. The garbled or missing QUBO Hamiltonians in Section 4.4.2 and the admitted infeasible H2S run on A-n33-k6 are correctness and verifiability concerns, not circularity: if the encoding is wrong, the reported costs are invalid, but that is an empirical/technical failure mode rather than a derivation that assumes its own conclusion. Table 3, which matches each instance's best-performing approach with depot location and customer distribution, is explicitly post-hoc ('A preliminary observation was that H3S seemed to perform better on instances with depot location as corner... Further testing will be needed to confirm if this pattern is indeed statistically significant'), so it is interpretation of the same data, not a prediction derived from the model. No self-citation chain is load-bearing; the hybrid architecture is credited to Feld et al. and to CC-CVRP, and the results are not obtained by renaming a known result or by fitting a parameter to the benchmark. Consequently, no circular step can be exhibited by quote-and-reduction, and the circularity score is 0.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central claim depends on several unverified modeling choices: the decomposition assumption, the correctness of the QUBO encoding, and the depot-duplication heuristic. The Lagrange weights are free parameters with unreported values, making the exact results non-reproducible.

free parameters (4)
  • Lagrange penalty weights (A, B) for CVRP/TSP constraints
    Used to balance feasibility vs. cost in QUBO. No values are given in the paper; they must be tuned, and different values would change results.
  • Fuzziness parameter m for FCM = 2
    Standard choice, not fitted to data, but affects clustering and therefore routes.
  • Number of clusters c
    For H2S, c equals the number of trucks; for H3S it is chosen via the elbow method. The choice directly determines the routing subproblems.
  • FCM convergence tolerance
    Stopping criterion for clustering; unspecified in the paper. Affects cluster assignments.
assumptions (4)
  • domain assumption CVRP can be decomposed into clustering and routing phases without large loss in solution quality
    The entire hybrid approach relies on this decomposition (Sections 2 and 4.1). If clustering-induced routes are far from optimal, the central claim fails.
  • ad hoc to paper The QUBO formulations in Section 4.4.2 correctly encode the CVRP/TSP constraints
    The paper provides only partial, partly garbled equations. The results' validity depends on this encoding being exact.
  • ad hoc to paper Duplicating the depot as one copy per cluster before FCM produces centroids near the depot and improves routing
    Section 4.1 says this modification 'skews the clusters so that centroids are located closer to the depot.' No evidence is provided that this improves final routes.
  • standard math Standard FCM convergence and defuzzification produce good soft assignments
    Section 4.1 builds on FCM without modifying its convergence properties.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Annealing based Hybrid Strategies for Real Time Route Optimization." pith.science (2026). https://pith.science/paper/HT35WI3M

@misc{pith2026241202720,
  author       = {Pith},
  title        = {Pith review of: Quantum Annealing based Hybrid Strategies for Real Time Route Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HT35WI3M}},
  note         = {Machine review of arXiv:2412.02720}
}
read the original abstract

One of the most well-known problems in transportation and logistics is the Capacitated Vehicle Routing Problem (CVRP). It involves optimizing a set of truck routes to service a set of customers, subject to limits on truck capacity, to reduce travel costs. The biggest challenge faced whilst attempting to solve the issue is that the time complexity of the issue grows exponentially with the number of customers and trucks, rendering it virtually intractable to traditional computers and algorithms. In this paper, we propose a method to circumvent this limitation, employing quantum computers to aid classical computers in solving problems faster while reducing complexity. To obtain our results, we employ two algorithms: Hybrid Two Step (H2S) and Hybrid Three Step (H3S). Both algorithms involve two phases: clustering and routing. It has been observed that both algorithms produce promising results, both in terms of solution time and solution cost.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 37 canonical work pages

  1. [1]

    A., Lo, N., Abdulaziz, R

    Ibrahim, A. A., Lo, N., Abdulaziz, R. O., & Ishaya, J. A. (2019). Capacitated vehicle routing problem. Éditions universitaires européennes

    work page 2019

  2. [2]

    Moghdani, R., Salimifard, K., Demir, E., & Benyettou, A. (2021). The green vehicle routing problem: A systematic literature review. Journal of Cleaner Production, 279, 123691

    work page 2021

  3. [3]

    Y., & Yeh, W

    Tan, S. Y., & Yeh, W. C. (2021). The vehicle routing problem: State-of-the-art classification and review. Applied Sciences, 11(21), 10295

    work page 2021

  4. [4]

    Quantum Computing

    Rietsche R, Dremel C, Bosch S, Steinacker L, Meckel M, Leimeister J. Quantum Computing. Electronic Markets. 2022; 32:2525-36

    work page 2022

  5. [5]

    S., & Del Ser, J

    Osaba, E., Yang, X. S., & Del Ser, J. (2020). Traveling salesman problem: a perspective review of recent research and new results with bio-inspired metaheuristics. Nature-inspired computation and swarm intelligence, 135-164

    work page 2020

  6. [6]

    Literature Review on Traveling Salesman Problem

    Sangwan S. Literature Review on Traveling Salesman Problem. International Journal of Research. 2018; 5(16):1152

    work page 2018

  7. [7]

    Dahiya, C., & Sangwan, S. (2018). Literature review on travelling salesman problem. International Journal of Research, 5(16), 1152-1155

    work page 2018

  8. [8]

    O., & Adeleke, O

    Adewumi, A. O., & Adeleke, O. J. (2018). A survey of recent advances in vehicle routing problems. International Journal of System Assurance Engineering and Management, 9, 155-172

    work page 2018

Show all 38 references
  1. [9]

    Solving Capacitated Vehicle Routing Problem (CVRP) Using Tabu Search Algorithm (TSA)

    Obaid O I. Solving Capacitated Vehicle Routing Problem (CVRP) Using Tabu Search Algorithm (TSA). Ibn AL- Haitham Journal for Pure and Applied Science. 2018; 31(2):199

    2018

  2. [10]

    Yarkoni, S., Raponi, E., Bäck, T., & Schmitt, S. (2022). Quantum annealing for industry applications: Introduction and review. Reports on Progress in Physics

    2022

  3. [11]

    M., Azar, D., Helal, N., & Keirouz, W

    Harmanani, H. M., Azar, D., Helal, N., & Keirouz, W. (2011). A Simulated Annealing Algorithm for the Capacitated Vehicle Routing Problem. In CATA (pp. 96-101)

    2011

  4. [12]

    Antosiewicz, M., Koloch, G., & Kamiński, B. (2013). Choice of best possible metaheuristic algorithm for the travelling salesman problem with limited computational time: quality, uncertainty and speed. Journal of Theoretical and Applied Computer Science, 7(1), 46-55

    2013

  5. [13]

    Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., & Subramanian, A. (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3), 845-858

    2017

  6. [14]

    G., Toropov, V

    Sahab, M. G., Toropov, V. V., & Gandomi, A. H. (2013). A review on traditional and modern structural optimization: problems and techniques. Metaheuristic applications in structures and infrastructures, 25-47

    2013

  7. [15]

    Glover, F., Kochenberger, G., & Du, Y. (2018). A tutorial on formulating and using QUBO models. arXiv preprint arXiv:1811.11538

    2018 arXiv

  8. [16]

    Glover, F., Kochenberger, G., Hennig, R., & Du, Y. (2022). Quantum bridge analytics I: a tutorial on formulating and using QUBO models. Annals of Operations Research, 314(1), 141-183

    2022

  9. [17]

    K., Ahmed, E

    Azad, U., Behera, B. K., Ahmed, E. A., Panigrahi, P. K., & Farouk, A. (2022). Solving vehicle routing problem using quantum approximate optimization algorithm. IEEE Transactions on Intelligent Transportation Systems

    2022

  10. [18]

    Pascal, R., & Pross, A. (2015). Stability and its manifestation in the chemical and biological worlds. Chemical Communications, 51(90), 16160-16165

    2015

  11. [19]

    N., Kortikar, N

    Hegade, N. N., Kortikar, N. L., Das, B., Behera, B. K., & Panigrahi, P. K. (2017). Experimental demonstration of quantum tunneling in IBM quantum computer. arXiv preprint arXiv:1712.07326

    2017 arXiv

  12. [20]

    Grover, L. K. (2000). Synthesis of quantum superpositions by quantum computation. Physical review letters, 85(6), 1334

    2000

  13. [21]

    B., Gomez, M

    Finnila, A. B., Gomez, M. A., Sebenik, C., Stenson, C., & Doll, J. D. (1994). Quantum annealing: A new method for minimizing multidimensional functions. Chemical physics letters, 219(5-6), 343-348

    1994

  14. [22]

    A., & Calude, C

    Abbott, A. A., & Calude, C. S. (2010). Understanding the quantum computational speedup via de- quantization. arXiv preprint arXiv:1006.1419

    2010 arXiv

  15. [23]

    (2014, July)

    Si, C., Shen, J., Zou, X., Wang, L., & Wu, Q. (2014, July). Mapping constrained optimization problems to penalty parameters: an empirical study. In 2014 IEEE Congress on Evolutionary Computation (CEC) (pp. 3073-3079). IEEE

    2014

  16. [24]

    Rockafellar, R. T. (1993). Basic issues in lagrangian optimization. In Optimization in Planning and Operation of Electric Power Systems: Lecture Notes of the SVOR/ASRO Tutorial Thun, Switzerland, October 14–16, 1992 (pp. 3-30). Physica-Verlag HD

    1993

  17. [25]

    Abdillah, U., & Suyanto, S. (2020). Clustering Nodes and Discretizing Movement to Increase the Effectiveness of HEFA for a CVRP. International Journal of Advanced Computer Science and Applications, 11(4)

    2020

  18. [26]

    M., Javadi-Abhari, A., Chong, F

    Murali, P., Baker, J. M., Javadi-Abhari, A., Chong, F. T., & Martonosi, M. (2019, April). Noise- adaptive compiler mappings for noisy intermediate-scale quantum computers. In Proceedings of the twenty-fourth international conference on architectural support for programming lan...

    2019

  19. [27]

    W., Lee, Z

    Lin, S. W., Lee, Z. J., Ying, K. C., & Lee, C. Y. (2009). Applying hybrid meta -heuristics for capacitated vehicle routing problem. Expert Systems with Applications, 36(2), 1505-1512

    2009

  20. [28]

    Peters, G., Crespo, F., Lingras, P., & Weber, R. (2013). Soft clustering–fuzzy and rough approaches and their extensions and derivatives. International Journal of Approximate Reasoning, 54(2), 307-322

    2013

  21. [29]

    (2021, November)

    Parekh, R., Ricciardi, A., Darwish, A., & DiAdamo, S. (2021, November). Quantum algorithms and simulation for parallel and distributed quantum computing. In 2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS) (pp. 9-19). IEEE

    2021

  22. [30]

    Solving the traveling salesman problem on the D-Wave quantum computer

    Jain S. Solving the traveling salesman problem on the D-Wave quantum computer. Frontiers in Physics. 2021; 9:760783

    2021

  23. [31]

    Croatian Operational Research Review

    Borcinova Z, Two models of the capacitated vehicle routing problem. Croatian Operational Research Review. 2017; 8(2):463–469

    2017

  24. [32]

    Unconstrained binary models of the traveling salesman problem variants for quantum optimization

    Salehi O, Glos A, Miszczak J A. Unconstrained binary models of the traveling salesman problem variants for quantum optimization. Quantum Information Processing. 2022; 21:67

    2022

  25. [33]

    Irie, H., Wongpaisarnsin, G., Terabe, M., Miki, A., & Taguchi, S. (2019). Quantum annealing of vehicle routing problem with time, state and capacity. In Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proc...

    2019

  26. [34]

    A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer

    Feld S, Roch C, Gabor T, Seidel C, Neukart F, Galter I, Mauerer W, Linnhoff-Popien C. A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. Frontiers ICT. 2019; 6

    2019

  27. [35]

    Constrained clustering for the capacitated vehicle routing problem (CC-CVRP)

    Alesiani F, Ermis G, Gkiotsalitis K. Constrained clustering for the capacitated vehicle routing problem (CC-CVRP). Applied Artificial Intelligence.2022; 36(3):1–25

    2022

  28. [36]

    Goal seeking Quadratic Unconstrained Binary Optimization

    Verma A, Lewis M. Goal seeking Quadratic Unconstrained Binary Optimization. Results in Control and Optimization.2022; 7:100125

    2022

  29. [37]

    C., DeClaris, N., & Liu, T

    Su, M. C., DeClaris, N., & Liu, T. K. (1997, October). Application of neural networks in cluster analysis. In 1997 IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation (Vol. 1, pp. 1-6). IEEE

    1997

  30. [38]

    (2022, September)

    Abdelatti, M., Sodhi, M., & Sendag, R. (2022, September). A Multi-GPU Parallel Genetic Algorithm For Large-Scale Vehicle Routing Problems. In 2022 IEEE High Performance Extreme Computing Conference (HPEC) (pp. 1-8). IEEE

    2022

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.