Quantum Annealing Approaches to Solving the Shipment Rerouting Problems

Arul Rhik Mazumder; Fei Li; Max Zhao

REVIEW 3 major objections 5 minor 15 references

Quantum Annealing Approaches to Solving the Shipment Rerouting Problems

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read The paper argues that a constrained-quadratic-model quantum annealing formulation solves small shipment rerouting problems to optimality in roughly constant time, where an exact classical MILP solver's runtime grows steeply with shipment…

desk verdict The CQM formulations are a genuine extension, but a mis-linearized classical objective C9 invalidates the 'QA matches optimal' comparison, so the paper's central empirical claim does not survive. read the letter →

arxiv 2501.05624 v1 pith:LJRRMMMF submitted 2025-01-09 quant-ph

Fei Li , Arul Rhik Mazumder , Max Zhao This is my paper · ORCID

classification quant-ph

keywords shipmentreroutingproblemquantumannealingconstrainedquadraticmodelmixed-integerlinearprogrammingcapacitatedtruckroutingNP-hardoptimizationhybridquantum-classicalsolverlogistics

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 studies the shipment rerouting problem (SRP), an NP-hard logistics problem in which a fleet of capacitated trucks with rental costs must carry indivisible goods from source hubs to destination hubs at minimum rental-plus-travel cost. The authors build two exact mixed-integer linear programs for SRP—one plain and one with a dispatch center—and translate both into constrained-quadratic-model (CQM) formulations suitable for quantum annealing. They test all four formulations on six road networks with 1 to 5 shipments and report that the quantum annealing solvers return the same total costs as the classical solver while their measured runtimes stay near 3 seconds, against classical runtimes that climb from 0.03 to over 100 seconds. If these results hold beyond the tested instances, hybrid quantum-classical solvers would offer a practical way to solve small SRP instances to optimality faster than exact classical branch-and-cut.

What carries the argument

The load-bearing object is the constrained-quadratic-model reformulation of the stop-based MILP. Both formulations use binary variables $X(i,j,p)$ and $Y(i,j,p)$ marking whether shipment $i$'s source or destination is the $p$-th stop of truck $j$, plus $Z(j)$ for truck use; the CQM version writes the transition cost between consecutive stops directly as quadratic products such as $X(i,j,q-1)X(i',j,q)$, and hands the constraints D1–D8 to a hybrid quantum-classical CQM solver. This avoids the auxiliary $w_{j,q}$ variables of the MILP's objective C9 and reduces the variable count from $O(m^2K)$ with a large constant to $O(m^2K)$ with a much smaller constant—exactly the comparison the experiments display. The dispatch-center variant adds $c_\alpha$ and $c_\beta$ terms that anchor each route to a central depot and, on the classical side, prune the search space.

What would settle it

On Sioux Falls, run the same comparison with six shipments and only three trucks of capacity 100, so every truck must be full; if the quantum solver's runtime stops being flat or its total cost exceeds the classical optimum, the paper's optimality-and-constant-time claim fails on that class of instances.

Watch

Extended reading notes

Core claim

The paper's central claim is that a CQM-based quantum annealing formulation can solve the shipment rerouting problem optimally—at least on all tested instances—and does so in roughly constant wall-clock time, whereas classical MILP solve time grows quickly with the number of shipments. In the experiments, both quantum formulations match the classical optimum on Sioux Falls, and the authors write that the quantum annealing algorithms work optimally as the classical solutions. The reason offered is structural: the quantum CQM formulation expresses route-transition costs directly as quadratic products of binary stop variables, eliminating the auxiliary linearization variables of the MILP, so the binary-variable count is about one sixth of the MILP count. The authors conclude by recommending the quantum annealing algorithms for SRP on the strength of this speed at equal solution quality.

Load-bearing premise

The central empirical conclusion assumes that instances with 1–5 shipments, all loads 50, all truck capacities 100, and all rental fees 1 are representative enough of SRP's difficulty; because the capacity limit is never varied or pushed to its binding point, the packing–sequencing interaction that makes the problem hard is not exercised.

Editorial extensions

If this is right

On all tested instances, the two quantum annealing formulations return the same total cost as the classical MILP formulations, so the paper claims they are optimal for those instances.
The measured runtime of the quantum solver stays near 3 seconds as the number of shipments grows from 1 to 5, while the classical solver's runtime grows from 0.03 to 101.3 seconds without a depot and from 0.02 to 11.9 seconds with a depot.
The CQM formulations use roughly one sixth as many binary variables as the MILP formulations (505 vs. 5005 at five shipments), which the paper identifies as the structural source of the speed difference.
Adding a dispatch center to the classical formulation sharply reduces its solve time, indicating that constraints anchoring routes to a depot prune the classical search space.
The paper recommends using the quantum annealing algorithms for the shipment rerouting problem, based on their speed at matching the classical optimum.

Reading between the lines

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

The roughly three-second floor on quantum runtimes is likely dominated by fixed hybrid-solver submission and communication overhead; if that overhead fell, the crossover point at which quantum solves beat the classical solver would move to even smaller instances.
A natural next experiment, not run in the paper, is to make the capacity constraint bind—for example, six 50-unit shipments with only three 100-unit trucks, so every truck must be full—and then compare the two approaches; that would test whether the joint packing-sequencing formulation remains optimal when packing actually constrains routes.
Because the CQM model optimizes all trucks jointly in one quadratic program, unlike the earlier single-route QUBO heuristic cited in the paper, the same modeling move may transfer to other combined assignment-and-routing logistics problems with indivisible loads.
The paper's claim is about small instances; if the flat quantum runtime persists to larger m (6–10 shipments), the practical use case would be real-time rerouting decisions where an exact classical solver would time out.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

You should know two things about this paper. First, the CQM formulations for the multi-truck shipment rerouting problem with capacities and a dispatch center are real work and a legitimate extension of the single-route QUBO and SSRP results they cite. Second, the central empirical claim—that quantum annealing matches the classical optimum and runs faster—rests on a classical baseline that is mis-specified. The C9 objective uses (X+X'-1)/2 to linearize the product X*X', which is wrong for binary variables: it gives -0.5 when both are 0, so unused trucks accumulate negative cost. The quantum D9 uses the correct product. The reported equality between QA and CPLEX therefore only shows that QA matches a solver that is minimizing the wrong objective on tiny instances.

What the paper does well: the constraint lists C1-C8 and D1-D8 are clearly laid out, the capacity constraints and the dispatch-center extension are sensible, and the NP-hardness reductions are standard but correct. The preprocessing on real transportation networks is a nice touch, and they are honest that the CQM variable count is much lower than the MIP count. There is no circular reasoning; the QA results are benchmarked against an independent solver, which is the right instinct.

The soft spots are not minor. Beyond the C9 error, the runtime comparison mixes local CPLEX solver time with D-Wave API-reported hybrid solver time, which is apples-to-oranges. The test instances are up to only 5 shipments, with loads of 50, capacity 100, and rental cost 1, so the capacity constraint never binds and the hard packing-sequencing interaction is never exercised. Quality results are reported for only one network and without error bars. The conclusion that QA is 'much faster' is not supported by this experimental design.

This paper is for readers interested in quantum annealing formulations for logistics, but as it stands it is not ready for referees. The fix is straightforward: correct the C9 linearization, rerun on instances where capacity actually binds, and make the runtime comparison apples-to-apples. I would not cite it in its current form, and I would not send it to peer review yet. Desk reject with encouragement to revise is the right call.

Referee Report

3 major / 5 minor

Summary. The paper studies a shipment rerouting problem (SRP) that combines sequencing and packing decisions for capacitated trucks on a hub network. It proposes two classical mixed-integer programming formulations (with and without a dispatch center) and two constrained-quadratic-model (CQM) formulations intended for D-Wave quantum annealing. The experiments compare CPLEX and the D-Wave LeapHybridCQMSampler on six public transportation networks with one to five shipments, and the paper claims that the quantum annealing solver produces optimal or near-optimal solutions much faster than the classical solver.

Significance. If its claims were correct, the paper would offer a useful quantum-annealing encoding for a logistics problem with both packing and sequencing constraints, and it would present an empirical speed comparison on standard benchmark networks. Credit is due for formulating the CQM model with a correct bilinear route-cost objective (D9), for using public transportation networks, and for reporting preprocessing times. However, the main classical baseline is invalidated by a mathematical error in objective C9, and the experimental instances do not exercise the capacity constraints that make SRP hard. As a result, the central claims that the classical formulations are exact and that the quantum annealing solver matches them optimally and runs faster are not supported by the presented evidence.

major comments (3)

[Section 2, objective C9 and the dispatch-center c_beta term] The linearized objective is mathematically wrong. For binary variables, (X(i,j,q-1) + X(i',j,q) - 1)/2 evaluates to -0.5 when both variables are 0, to 0 when exactly one is 1, and to +0.5 only when both are 1. It is not the product X*X' that the preceding if-case requires. Consequently, unused stop pairs contribute large negative terms to w_{j,q}, and the MIP minimizes a spurious objective rather than the sum of rental fees plus C times the actual route distance. The same error appears in the dispatch-center term c_beta, which uses (Y(i,j,q) - sum_{i'} [X(i',j,q+1)+Y(i',j,q+1)])/2 instead of the product form used in D9. Therefore the CPLEX "optimal" costs in Table 8 are not minimizers of the stated SRP cost, and the claim in Section 4.2.4 that the quantum annealing algorithms work optimally as the classical solutions is not supported. The quantum objective D9 correctly uses products, so the classical and quantum formulations are not equivalent as claimed; a correct classical encoding would require either quadratic terms or auxiliary variables with McCormick-type linearization.
[Section 4.1 and Section 4.2.4] The experimental design does not exercise the packing-sequencing interaction that makes SRP hard. With m = 1..5 shipments, uniform load 50, truck capacity 100, K = m trucks, and rental fee 1, every instance can be solved by assigning each shipment to its own dedicated truck, and the capacity constraint is never binding (no truck is ever forced to carry two shipments). The matching costs in Table 8 (SRP and QA equal, SRP-D and QA-D equal) are therefore consistent with the trivial decomposition of the instances and do not demonstrate that the quantum solver finds optimal solutions for capacitated SRP. The claim that the solver "generates near-optimal or optimal solutions" requires experiments in which the capacity constraint is active and in which the optimal solution must pack multiple shipments onto a truck; no such instances are reported.
[Section 4.2.2, Tables 4 and 5, and Figure 1] The runtime comparison is not apples-to-apples. CPLEX times are local solver times on a specified CPU, whereas the D-Wave times are LeapHybridCQMSampler API times, which include submission, queueing, and hybrid classical-quantum post-processing. The paper acknowledges that wall-clock time is not used but does not establish that the two metrics measure the same quantity. In addition, Tables 4 and 5 do not state whether the reported numbers are averages over the five runs and over the six networks, or whether they are representative single runs. The near-constant QA times (about 3.0-3.2 seconds for all m) are consistent with fixed API overhead rather than a scaling advantage, and the claim that QA times grow linearly while CPLEX times grow exponentially is based on only five values of m and no larger instances. The speed advantage asserted in the abstract and Section 4.2.2 is therefore not established.

minor comments (5)

[Section 1, NP-hardness reductions] The reductions to TSP and partition are sketched informally. In the TSP reduction, the condition that the minimum rental cost exceeds the total cost of all hub-to-hub paths is not clearly stated: the rental cost is still paid for the single truck, so the reasoning that the optimum minimizes distance only should be spelled out. The partition reduction shows a feasibility argument for a special case; it would be cleaner to state explicitly that the decision version of SRP is NP-complete.
[Section 2, condition count] After listing constraints C1-C9, the paper gives a formula for the total number of conditions as "4m2K + 2m + K·2m + m·K + m·K·2m + 2m·K + 2m·K + 2m·K + 2m·K". This expression is not derived from the listed constraints and appears to overcount or misidentify the constraint types; the paper should present a verifiable count for each constraint family.
[Section 4.2.3, variable counts] The statement that the quantum formulations use "about 1/6 of" the classical variables is only approximately true for m=5 (505 vs. 5005 for SRP, 730 vs. 5230 for SRP-D); for m=1 the ratio is closer to 1/2. The claim should be qualified by the size of m.
[Section 4.2.4, Table 8] The quality comparison is reported only for Sioux Falls, yet the concluding sentence in Section 4.2.4 generalizes to all tested networks. If the other networks were also tested, the corresponding costs should be reported or summarized; otherwise the optimality claim is based on a single network.
[General presentation] There are frequent typographical and grammar issues, such as missing articles and awkward phrasing (e.g., "we count the cost w_{j,q} that the truck j's traveling distance"). A careful proofread is needed before resubmission.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the SRP formulations are direct encodings, the classical MIP is an independent exact-solver benchmark, and the QA results are compared with rather than derived from the classical results.

full rationale

The paper does not contain a circular derivation. The classical formulations (C1-C9) and quantum formulations (D1-D9) are direct encodings of the stated SRP constraints and objective; no parameter in either formulation is fitted to the data that is later predicted. The quantum annealing results are benchmarked against CPLEX, an independent exact solver, on externally supplied Transportation Networks instances. There are no self-citations by the present authors, no imported uniqueness theorem, and no ansatz smuggled in via citation. The claim in Section 4.2.4 that 'the quantum annealing algorithms work optimally as the classical solutions' is an empirical equivalence claim, not an equivalence-by-construction: the QA objective D9 is written with product terms, while the classical C9 uses a linearized expression, and the comparison is an experimental finding. The skeptic's concern about C9's linearization is a correctness or validity issue with the classical baseline, not a circularity issue, because the QA values are not defined in terms of the classical output; they are separately solved and then compared. Given that the paper is self-contained against an external solver and external data, the appropriate circularity score is 0.

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

The formulations rely on standard optimization and graph theory. The experimental constants (load 50, capacity 100, rental 1, C=1) are settings, not fitted parameters. The D-Wave hybrid solver is treated as a black box that satisfies all CQM constraints; the paper does not prove that the solver's output is feasible for D8 or that the solver time is a fair measure of quantum performance.

assumptions (3)

standard math Shortest-path preprocessing on the road network produces a complete digraph whose edge costs satisfy the triangle inequality.
Invoked in Section 1 when constructing F from G; the triangle inequality is used implicitly in the route cost accounting.
domain assumption The D-Wave LeapHybridCQMSampler returns a feasible solution for the CQM, respecting the quadratic inequality constraints such as D8.
The experimental claims rely on the proprietary hybrid solver's ability to handle the CQM with quadratic constraints; the paper provides no verification of feasibility for larger instances.
domain assumption The CPLEX branch-and-cut solver finds the true optimum of the MIP as formulated.
The paper treats CPLEX results as exact 'optimal' baselines; if the objective C9 is misprinted, the baseline itself is wrong.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum Annealing Approaches to Solving the Shipment Rerouting Problems." pith.science (2026). https://pith.science/paper/LJRRMMMF

@misc{pith2026250105624,
  author       = {Pith},
  title        = {Pith review of: Quantum Annealing Approaches to Solving the Shipment Rerouting Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LJRRMMMF}},
  note         = {Machine review of arXiv:2501.05624}
}

read the original abstract

In this paper, we study a shipment rerouting problem (SRP) which generalizes many NP-hard sequencing and packing problems. A SRP's solution has ample practical applications in vehicle scheduling and transportation logistics. Given a network of hubs, a set of goods must be delivered by trucks from their source-hubs to their respective destination-hubs. The objective is to select a set of trucks and to schedule these trucks' routes so that the total cost is minimized. The problem SRP is NP-hard; only classical approximation algorithms have been known for some of its NP-hard variants. In this work, we design classical algorithms and quantum annealing algorithms for this problem with various capacitated trucks. The algorithms that we design use novel mathematical programming formulations and new insights into solving sequencing and packing problems simultaneously. Such formulations take advantage of network infrastructure, shipments, and truck capacities. We conduct extensive experiments showing that in various scenarios, the quantum annealing solver generates near-optimal or optimal solutions much faster than the classical algorithm solver.

Figures

Figures reproduced from arXiv: 2501.05624 by the authors.

**Figure 1.** It has been observed that with the dispatch center in our formulation, the running times of the classical algorithm SRP-D are getting significantly smaller compared to those formulations without 13 [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗

**Figure 1.** Running time comparison for the algorithms [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗

**Figure 2.** Relationship between number of shipments and the number of variables used in the [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗

Figures from the paper (2 more)

**Figure 3.** Figure 3: Relationship between number of shipments and the number of conditions required to be [PITH_FULL_IMAGE:figures/full_fig_p016_3.png]

**Figure 4.** Figure 4: Relationship between number of shipments and the total cost [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 14 canonical work pages

[1]

Chakrabarti, P

S. Chakrabarti, P. Minssen, R. Yalovetzky, and M. Pistoia. Universal quantum speedup for branch- and-bound, branch-and-cut, and tree-search algorithms. arXiv:2210.03210, 2022

arXiv 2022
[2]

Cormen, Charles E

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 4th edition, 2022

work page 2022
[3]

Implementation of a hybrid classical-quantum annealing algorithm for logistic network design

Yongcheng Ding, Xi Chen, Lucas Lamata, Enrique Solano, and Mikel Sanz. Implementation of a hybrid classical-quantum annealing algorithm for logistic network design. SN Computer Science, 2(2), 2021. 17

work page 2021
[4]

Garey and David S

Michael R. Garey and David S. Johnson. Computers and Intractability — A Guide to the Theory of NP-completeness . W. H. Freeman, 1979

work page 1979
[5]

E. L. Lawler, Jan Karel Lenstra, A. H. G. Rinnooy Kan, and David B. Shmoys. The traveling salesman problem: a guided tour of combinatorial optimization . Wiley, 1985

work page 1985
[6]

Ising formulations of many NP problems

Andrew Lucas. Ising formulations of many NP problems. Frontiers in Physics, 11(2):208–230, 2014

work page 2014
[7]

Quantum speedup of branch-and-bound algorithms

Ashley Montanaro. Quantum speedup of branch-and-bound algorithms. Physics Review Re- search, 2(013056):1–23, 2020

work page 2020
[8]

Solving a real-world package delivery routing problem using quantum annealers

Eneko Osaba, Esther Villar-Rodriguez, and Anton Asla. Solving a real-world package delivery routing problem using quantum annealers. Scientific Reports, 14(1):Article number: 24791, 2024

work page 2024

Show all 15 references

[9]

The traffic assignment problem: models & methods

Michael Patriksson. The traffic assignment problem: models & methods. 2015

2015
[10]

Transportation networks for research

Ben Stabler, Hillal Bar-Gera, and Elizabeth Sal. Transportation networks for research. https: //github.com/bstabler/TransportationNetworks/. accessed on July 15, 2024

2024
[11]

Application of ising machines and a software development for ising machines

Kotaro Tanahashi, Shinichi Takayanagi, Tomomitsu Motohashi, and Shu Tanaka. Application of ising machines and a software development for ising machines. Journal of the Physical Society of Japan , 88(6):061010, 2019

2019
[12]

Vijay. V. Vazirani. Approximation Algorithms. Springer, 2003

2003
[13]

Williamson and David B

David P. Williamson and David B. Shmoys. The design of approximation algorithms . Cam- bridge University Press, 2011

2011
[14]

Solving the shipment rerouting problem with quantum optimization techniques

Sheir Yarkoni, Andreas Huck, Hanno Schulldorf, Benjamin Speitkamp, Marc Shakory Tabrizi, Martin Leib, Thomas Back, and Florian Neukart. Solving the shipment rerouting problem with quantum optimization techniques. In Proceedings of the International Conference on Computational ...

2021
[15]

PyQUBO: Python library for mapping combinatorial optimization problems to QUBO form

Mashiyat Zaman, Kotaro Tanahashi, and Shu Tanaka. PyQUBO: Python library for mapping combinatorial optimization problems to QUBO form. https://arxiv.org/abs/2103.01708. 18

arXiv

Pith tools

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

[1] [1]

Chakrabarti, P

S. Chakrabarti, P. Minssen, R. Yalovetzky, and M. Pistoia. Universal quantum speedup for branch- and-bound, branch-and-cut, and tree-search algorithms. arXiv:2210.03210, 2022

arXiv 2022

[2] [2]

Cormen, Charles E

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 4th edition, 2022

work page 2022

[3] [3]

Implementation of a hybrid classical-quantum annealing algorithm for logistic network design

Yongcheng Ding, Xi Chen, Lucas Lamata, Enrique Solano, and Mikel Sanz. Implementation of a hybrid classical-quantum annealing algorithm for logistic network design. SN Computer Science, 2(2), 2021. 17

work page 2021

[4] [4]

Garey and David S

Michael R. Garey and David S. Johnson. Computers and Intractability — A Guide to the Theory of NP-completeness . W. H. Freeman, 1979

work page 1979

[5] [5]

E. L. Lawler, Jan Karel Lenstra, A. H. G. Rinnooy Kan, and David B. Shmoys. The traveling salesman problem: a guided tour of combinatorial optimization . Wiley, 1985

work page 1985

[6] [6]

Ising formulations of many NP problems

Andrew Lucas. Ising formulations of many NP problems. Frontiers in Physics, 11(2):208–230, 2014

work page 2014

[7] [7]

Quantum speedup of branch-and-bound algorithms

Ashley Montanaro. Quantum speedup of branch-and-bound algorithms. Physics Review Re- search, 2(013056):1–23, 2020

work page 2020

[8] [8]

Solving a real-world package delivery routing problem using quantum annealers

Eneko Osaba, Esther Villar-Rodriguez, and Anton Asla. Solving a real-world package delivery routing problem using quantum annealers. Scientific Reports, 14(1):Article number: 24791, 2024

work page 2024