EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Steiner Traveling Salesman Problem with Time Windows and Pickup–Delivery: Integrating classical and quantum optimization

Alessia Ciacco, Francesca Guerriero, Eneko Osaba

Computers & Operations Research · 2026-10 · 194 · 107589

DOI: 10.1016/j.cor.2026.107589 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Computers & Operations Research, 2026-10. Verfasst von Alessia Ciacco und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 51 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Basque Government.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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. We also introduce a benchmark instance generator designed to create diverse and scalable test scenarios, providing a flexible framework for assessing the performance and robustness of both classical and quantum optimization methods. 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.

Förderung

  • Basque Government

Zitieren

APA

Ciacco, A., Guerriero, F., & Osaba, E. (2026). Steiner Traveling Salesman Problem with Time Windows and Pickup–Delivery: Integrating classical and quantum optimization. Computers & Operations Research, 194, 107589. https://doi.org/10.1016/j.cor.2026.107589

Vancouver

Ciacco A, Guerriero F, Osaba E. Steiner Traveling Salesman Problem with Time Windows and Pickup–Delivery: Integrating classical and quantum optimization. Computers & Operations Research. 2026;194:107589. doi:10.1016/j.cor.2026.107589

BibTeX
@article{Ciacco2026,
  author = {Ciacco, Alessia and Guerriero, Francesca and Osaba, Eneko},
  title = {Steiner Traveling Salesman Problem with Time Windows and Pickup–Delivery: Integrating classical and quantum optimization},
  journal = {Computers & Operations Research},
  year = {2026},
  volume = {194},
  pages = {107589},
  doi = {10.1016/j.cor.2026.107589}
}
Kostenlos starten →