pith. sign in

arxiv: 2508.17896 · v3 · submitted 2025-08-25 · 💻 cs.ET

Steiner Traveling Salesman Problem with Time Windows and Pickup-Delivery: integrating classical and quantum optimization

Alessia Ciacco , Francesca Guerriero , Eneko Osaba This is my paper

Pith reviewed 2026-05-18 21:32 UTC · model grok-4.3

classification 💻 cs.ET
keywords Steiner traveling salesman problemtime windowspickup and deliveryvehicle routingmathematical formulationspreprocessingquantum optimizationhybrid approaches
0
0 comments X

The pith

A variant of the traveling salesman problem that includes Steiner nodes, time windows, pickup and delivery pairs, and capacity can be formulated in two ways and solved with classical or quantum optimization after preprocessing.

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

This paper defines a new routing problem that adds Steiner nodes for optional visits, strict time windows, paired pickup and delivery operations, and vehicle capacity to the classic traveling salesman model. These additions reflect the demands of current logistics operations such as last-mile delivery and reverse logistics. The authors present an arc-based formulation and a node-based formulation to encode the problem, along with a preprocessing technique that removes unnecessary arcs to shrink the instance size. They then solve the resulting models using both classical optimization and hybrid quantum approaches, and test them on numerical instances to check correctness and performance gains from preprocessing.

Core claim

The Steiner Traveling Salesman Problem with Time Windows and Pickup and Delivery is defined by integrating Steiner nodes, time window constraints, pickup-delivery pairs, and capacity limits. Two mathematical formulations are proposed: an arc-based model and a node-oriented model. A preprocessing reduction method eliminates redundant arcs to improve scalability. Both formulations are solved using classical optimization and quantum optimization approaches. Numerical experiments validate the formulations and show the benefits of the preprocessing method on problem size and solution efficiency.

What carries the argument

An arc-based formulation and a node-oriented formulation of the problem constraints, supported by a preprocessing step that removes redundant arcs from the graph.

If this is right

  • The models correctly represent all constraints including Steiner nodes that may or may not be visited, time windows that must be respected, paired pickup and delivery tasks, and capacity limits.
  • Eliminating redundant arcs through preprocessing reduces the number of variables and constraints, leading to faster solution times for both classical and quantum approaches.
  • Classical optimization can find optimal or near-optimal solutions for the formulated problem.
  • Hybrid quantum approaches can also produce high-quality feasible solutions for instances of practical size.

Where Pith is reading between the lines

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

  • The choice between arc-based and node-based models may depend on the density of the underlying graph or the number of Steiner nodes.
  • Such models could be adapted to dynamic versions of the problem where time windows or demands change over time.
  • Testing the quantum approach on larger instances might reveal scaling advantages or limitations compared to purely classical methods.

Load-bearing premise

The two formulations accurately encode the full set of constraints without allowing invalid routes or missing feasible ones, and the hybrid quantum approach reliably finds good solutions for realistic problem sizes.

What would settle it

Running the model on a small hand-crafted instance with a known feasible solution and checking whether the solver returns that solution or an infeasible one would confirm or refute the correctness of the encoding.

Figures

Figures reproduced from arXiv: 2508.17896 by Alessia Ciacco, Eneko Osaba, Francesca Guerriero.

Figure 1
Figure 1. Figure 1: Comparison of optimal routes generated by the STSP-TWPD, STSP-PD and STSP-TW models for [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of optimal routes generated by the STSP-TWPD, STSP-PD, and STSP-TW models for [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of optimal routes generated by the STSP-TWPD, STSP-PD, and STSP-TW models for [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of optimal routes generated by the STSP-TWPD, STSP-PD, and STSP-TW models for [PITH_FULL_IMAGE:figures/full_fig_p018_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Objective function values for STSP-TWPD, STSP-PD, and STSP-TW models as a function of [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Comparison of the total number of variables and constraints in the ABF model with and without AFGR as a function of [PITH_FULL_IMAGE:figures/full_fig_p020_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Comparison of the total number of constraints in the NBF model with and without AFGR as a function of [PITH_FULL_IMAGE:figures/full_fig_p021_7.png] view at source ↗
read the original abstract

We propose the Steiner Traveling Salesman Problem with Time Windows and Pickup and Delivery, an advanced and practical extension of classical routing models. This variant integrates the characteristics of the Steiner Traveling Salesman Problem with time-window constraints, pickup and delivery operations and vehicle capacity limitations. These features closely mirror the complexities of contemporary logistics challenges, including last-mile distribution, reverse logistics and on-demand service scenarios. To tackle the inherent computational difficulties of this NP-hard problem, we propose two specialized mathematical formulations: an arc-based model and a node-oriented model, each designed to capture distinct structural aspects of the problem. We further introduce a preprocessing reduction method that eliminates redundant arcs, significantly enhancing computational performance and scalability. Both formulations are implemented using classical and quantum optimization approaches. In particular, the classical models are solved with Gurobi, whereas the quantum implementation is carried out on D-Wave's LeapCQMHybrid platform, a hybrid quantum-classical environment that integrates quantum annealing with classical optimization techniques for constrained problem solving. Numerical experiments are conducted to validate the proposed formulations and the preprocessing reduction method. The analyses performed assess the structural properties of the two models, their computational behavior, and the impact of preprocessing on problem size and solution efficiency.

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

0 major / 2 minor

Summary. The paper proposes the Steiner Traveling Salesman Problem with Time Windows and Pickup and Delivery (STSP-TW-PD), extending classical routing models with Steiner nodes, time windows, pickup-delivery pairs, and vehicle capacity. It introduces two MIP formulations (arc-based and node-oriented) that encode these features via standard big-M and flow-balance constraints, a preprocessing method for arc elimination, and solves the models classically with Gurobi and via D-Wave LeapCQMHybrid quantum-classical solver. Numerical experiments on generated instances validate the formulations, preprocessing impact on problem size, and solution feasibility.

Significance. If the formulations are correct and the hybrid solver produces feasible solutions of practical quality, the work advances the literature on realistic vehicle routing by combining multiple operational constraints and demonstrating hybrid quantum-classical methods for constrained combinatorial problems. The explicit derivation and testing of the preprocessing reduction is a strength that could aid scalability.

minor comments (2)
  1. [§3.2] §3.2 (node-oriented formulation): the description of how pickup-delivery precedence is enforced via time-window variables could be expanded with a short example instance to clarify the interaction with Steiner node selection.
  2. [Table 4] Table 4 (computational results): the column reporting solution quality for D-Wave runs should include the number of feasible solutions found across multiple runs or the best objective gap relative to Gurobi, to strengthen the comparison.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work on the Steiner Traveling Salesman Problem with Time Windows and Pickup-Delivery (STSP-TW-PD), for recognizing the value of the arc-based and node-based formulations, the arc-reduction preprocessing, and the hybrid quantum-classical experiments on D-Wave LeapCQMHybrid. We appreciate the recommendation for minor revision and will incorporate clarifications and improvements accordingly.

Circularity Check

0 steps flagged

No significant circularity; direct modeling and solver validation

full rationale

The paper introduces two new mathematical formulations (arc-based and node-oriented) for the Steiner TSP with time windows, pickup-delivery, and capacity, along with a preprocessing arc-elimination method. These are constructed from standard constraint patterns (big-M, flow balance, time-window inequalities) applied to the problem definition, then solved via Gurobi and D-Wave LeapCQMHybrid on generated test instances. No equation reduces to a fitted parameter renamed as a prediction, no load-bearing premise rests on a self-citation chain, and no uniqueness theorem or ansatz is smuggled in. The numerical experiments supply independent feasibility and performance data outside any internal loop, rendering the derivation self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard integer-programming modeling assumptions for routing problems and on the correctness of external solvers (Gurobi, D-Wave hybrid). No new free parameters, ad-hoc axioms, or invented physical entities are introduced in the abstract.

axioms (1)
  • standard math Standard assumptions of integer linear programming for routing problems hold (binary variables, flow conservation, subtour elimination).
    Invoked when the arc-based and node-based models are stated.

pith-pipeline@v0.9.0 · 5751 in / 1172 out tokens · 34460 ms · 2026-05-18T21:32:34.102828+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.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem

    quant-ph 2026-04 unverdicted novelty 3.0

    Iterative cutting-plane generation and arc preprocessing reduce TSP model size and yield performance gains on classical, direct quantum, and hybrid D-Wave solvers.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages · cited by 1 Pith paper

  1. [1]

    Ghiani, F

    G. Ghiani, F. Guerriero, G. Laporte, R. Musmanno, Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies, European journal of operational research 151 (2003) 1–11

    work page 2003

  2. [2]

    Braekers, K

    K. Braekers, K. Ramaekers, I. Van Nieuwenhuyse, The vehicle routing problem: State of the art classification and review, Computers & indus- trial engineering 99 (2016) 300–313

    work page 2016

  3. [3]

    Di Puglia Pugliese, F

    L. Di Puglia Pugliese, F. Guerriero, Last-mile deliveries by using drones and classical vehicles, in: International Conference on Optimization and Decision Science, Springer, 2017, pp. 557–565

    work page 2017

  4. [4]

    A. M. Ham, Integrated scheduling of m-truck, m-drone, and m- depot constrained by time-window, drop-pickup, and m-visit using constraint programming, Transportation Research Part C: Emerging Technologies 91 (2018) 1–14. URL: https://www.sciencedirect. com/science/article/pii/S0968090X18304121. doi: https: //doi.org/10.1016/j.trc.2018.03.025

    work page doi:10.1016/j.trc.2018.03.025 2018

  5. [5]

    Di Puglia Pugliese, G

    L. Di Puglia Pugliese, G. Macrina, F. Guerriero, Trucks and drones coop- eration in the last-mile delivery process, Networks (2020)

    work page 2020

  6. [6]

    H. Li, A. Lim, A metaheuristic for the pickup and delivery problem with time windows, in: Proceedings 13th IEEE international conference on tools with artificial intelligence. ICTAI 2001, IEEE, 2001, pp. 160–167

    work page 2001

  7. [7]

    Ropke, D

    S. Ropke, D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation science 40 (2006) 455–472

    work page 2006

  8. [8]

    Cornuéjols, J

    G. Cornuéjols, J. Fonlupt, D. Naddef, The traveling salesman problem on a graph and some related integer polyhedra, Mathematical programming 33 (1985) 1–27

    work page 1985

  9. [9]

    Fleischmann, A cutting plane procedure for the travelling salesman problem on road networks, European Journal of Operational Research 21 (1985) 307–317

    B. Fleischmann, A cutting plane procedure for the travelling salesman problem on road networks, European Journal of Operational Research 21 (1985) 307–317

    work page 1985

  10. [10]

    A. N. Letchford, S. D. Nasiri, D. O. Theis, Compact formulations of the steiner traveling salesman problem and related problems, European Journal of Operational Research 228 (2013) 83–92

    work page 2013

  11. [11]

    Rodríguez-Pereira, E

    J. Rodríguez-Pereira, E. Fernández, G. Laporte, E. Benavent, A. Martínez-Sykora, The steiner traveling salesman problem and its ex- tensions, European Journal of Operational Research 278 (2019) 615–628

    work page 2019

  12. [12]

    Interian, C

    R. Interian, C. C. Ribeiro, A grasp heuristic using path-relinking and restarts for the steiner traveling salesman problem, International Transac- tions in Operational Research 24 (2017) 1307–1323

    work page 2017

  13. [13]

    Álvarez-Miranda, M

    E. Álvarez-Miranda, M. Sinnl, A note on computational aspects of the steiner traveling salesman problem, International Transactions in Opera- tional Research 26 (2019) 1396–1401

    work page 2019

  14. [14]

    H. Liu, H. Zhang, Y . Xu, The m-steiner traveling salesman problem with online edge blockages, Journal of Combinatorial Optimization 41 (2021) 844–860

    work page 2021

  15. [15]

    Zhang, Z

    Y . Zhang, Z. Zhang, Z. Liu, Q. Chen, An asymptotically tight online algo- rithm for m-steiner traveling salesman problem, Information Processing Letters 174 (2022) 106177

    work page 2022

  16. [16]

    Dumas, J

    Y . Dumas, J. Desrosiers, F. Soumis, The pickup and delivery problem with time windows, European journal of operational research 54 (1991) 7–22

    work page 1991

  17. [17]

    Chang, S.-R

    M.-S. Chang, S.-R. Chen, C.-F. Hsueh, Real-time vehicle routing problem with time windows and simultaneous delivery /pickup demands, Journal of the Eastern Asia Society for Transportation Studies 5 (2003) 2273– 2286

    work page 2003

  18. [18]

    Caramia, G

    M. Caramia, G. F. Italiano, G. Oriolo, A. Pacifici, A. Perugia, Rout- ing a fleet of vehicles for dynamic combined pick-up and deliveries ser- vices, in: Operations Research Proceedings 2001: Selected Papers of the International Conference on Operations Research (OR 2001) Duisburg, September 3–5, 2001, Springer, 2002, pp. 3–8

    work page 2001

  19. [19]

    Fabri, P

    A. Fabri, P. Recht, On dynamic pickup and delivery vehicle routing with several time windows and waiting times, Transportation Research Part B: Methodological 40 (2006) 335–350

    work page 2006

  20. [20]

    Lin, A vehicle routing problem with pickup and delivery time win- dows, and coordination of transportable resources, Computers & Opera- tions Research 38 (2011) 1596–1609

    C. Lin, A vehicle routing problem with pickup and delivery time win- dows, and coordination of transportable resources, Computers & Opera- tions Research 38 (2011) 1596–1609

    work page 2011

  21. [21]

    Grandinetti, F

    L. Grandinetti, F. Guerriero, F. Pezzella, O. Pisacane, A pick-up and delivery problem with time windows by electric vehicles, International Journal of Productivity and Quality Management 18 (2016) 403–423

    work page 2016

  22. [22]

    Ciacco, F

    A. Ciacco, F. Guerriero, E. Osaba, Steiner traveling salesman problem with quantum annealing, in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2025, pp. 2412–2418

    work page 2025

  23. [23]

    Osaba, E

    E. Osaba, E. Villar-Rodriguez, P. Miranda-Rodriguez, A. Asla, Optimiz- ing package delivery with quantum annealers: Addressing time-windows and simultaneous pickup and delivery, arXiv preprint arXiv:2504.01560 (2025)

    work page arXiv 2025

  24. [24]

    Venturelli, D

    D. Venturelli, D. Marchand, G. Rojo, Job shop scheduling solver based on quantum annealing, in: Proc. of ICAPS-16 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling (COPLAS), 2016, pp. 25–34

    work page 2016

  25. [25]

    L. F. Pérez Armas, S. Creemers, S. Deleplanque, Solving the resource- constrained project scheduling problem (rcpsp) with quantum annealing, Available at SSRN 4689017 (2024)

    work page 2024

  26. [26]

    Bo˙ zejko, J

    W. Bo˙ zejko, J. Pempera, M. Uchro ´nski, M. Wodecki, Quantum annealing-driven branch and bound for the single machine total weighted number of tardy jobs scheduling problem, Future Generation Computer Systems 155 (2024) 245–255

    work page 2024

  27. [27]

    F. Orts, A. M. Puertas, G. Ortega, E. M. Garzón, Quantum annealing solution for the unrelated parallel machine scheduling with priorities and delay of task switching on machines, Future Generation Computer Sys- tems 148 (2023) 514–523

    work page 2023

  28. [28]

    Y . Ding, X. Chen, L. Lamata, E. Solano, M. Sanz, Implementation of a hybrid classical-quantum annealing algorithm for logistic network design, SN Computer Science 2 (2021) 1–9

    work page 2021

  29. [29]

    Malviya, B

    G. Malviya, B. AkashNarayanan, J. Seshadri, Logistics network op- timization using quantum annealing, in: International Conference on Emerging Trends and Technologies on Intelligent Systems, Springer, 2023, pp. 401–413

    work page 2023

  30. [30]

    Ciacco, F

    A. Ciacco, F. Guerriero, F. P. Saccomanno, Quantum annealing for the two-level facility location problem, Future Generation Computer Systems (2025) 107961

    work page 2025

  31. [31]

    M. G. de Andoin, E. Osaba, I. Oregi, E. Villar-Rodriguez, M. Sanz, Hy- brid quantum-classical heuristic for the bin packing problem, in: Pro- ceedings of the Genetic and Evolutionary Computation Conference Com- panion, 2022, pp. 2214–2222

    work page 2022

  32. [32]

    Garcia-de Andoin, I

    M. Garcia-de Andoin, I. Oregi, E. Villar-Rodriguez, E. Osaba, M. Sanz, Comparative benchmark of a quantum algorithm for the bin packing prob- lem, arXiv preprint arXiv:2207.07460 (2022)

    work page arXiv 2022

  33. [33]

    Syrichas and A

    A. Syrichas, A. Crispin, Large-scale vehicle routing problems: Quantum annealing, tunings and results, Computers & Operations Research 87 (2017) 52–62. URL: https://www.sciencedirect. com/science/article/pii/S0305054817301260. doi: https: //doi.org/10.1016/j.cor.2017.05.014

    work page doi:10.1016/j.cor.2017.05.014 2017

  34. [34]

    T. D. Tambunan, A. B. Suksmono, I. J. M. Edward, R. Mulyawan, Quan- tum annealing for vehicle routing problem with weighted segment, 2022. arXiv:2203.13469

    work page arXiv 2022

  35. [35]

    J. B. Holliday, D. Blount, E. Osaba, K. Luu, Advanced quantum an- nealing approach to vehicle routing problems with time windows, arXiv preprint arXiv:2503.24285 (2025). 24

    work page arXiv 2025

  36. [36]

    T. V . Le, M. V . Nguyen, S. Khandavilli, T. N. Dinh, T. N. Nguyen, Quan- tum annealing approach for selective traveling salesman problem, in: ICC 2023-IEEE International Conference on Communications, IEEE, 2023, pp. 2686–2691

    work page 2023

  37. [37]

    N. Mori, S. Furukawa, Quantum annealing for the adjuster rout- ing problem, Frontiers in Physics 11 (2023). URL: https://www. frontiersin.org/articles/10.3389/fphy.2023.1129594. doi:10.3389/fphy.2023.1129594

    work page doi:10.3389/fphy.2023.1129594 2023

  38. [38]

    Osaba, E

    E. Osaba, E. Villar-Rodriguez, A. Asla, Solving a real-world package delivery routing problem using quantum annealers, Scientific Reports 14 (2024) 24791

    work page 2024

  39. [39]

    Ciacco, F

    A. Ciacco, F. Guerriero, G. Macrina, Review of quantum algorithms for medicine, finance and logistics, Soft Computing (2025) 1–42

    work page 2025

  40. [40]

    Osaba, E

    E. Osaba, E. Villar-Rodriguez, I. Oregi, A systematic literature review of quantum computing for routing problems, IEEE Access 10 (2022) 55805–55817

    work page 2022

  41. [41]

    Osaba, P

    E. Osaba, P. Miranda-Rodriguez, D-wave’s nonlinear-program hybrid solver: Description and performance analysis, IEEE Access (2025)

    work page 2025

  42. [42]

    Bertuzzi, D

    A. Bertuzzi, D. Ferrari, A. Manzalini, M. Amoretti, Evaluation of quan- tum and hybrid solvers for combinatorial optimization, in: Proceedings of the 21st ACM International Conference on Computing Frontiers, 2024, pp. 232–239

    work page 2024

  43. [43]

    Willsch, M

    D. Willsch, M. Willsch, C. D. Gonzalez Calaza, F. Jin, H. De Raedt, M. Svensson, K. Michielsen, Benchmarking advantage and d-wave 2000q quantum annealers with exact cover problems, Quantum Information Pro- cessing 21 (2022) 141. 25

    work page 2022