Quantum Optimization for the Steiner Traveling Salesman Problem with Time Windows and Pickup and Delivery Journal: a journal
Alessia Ciacco, Francesca Guerriero, Eneko Osaba · 2025
Read Quantum Optimization for the Steiner Traveling Salesman Problem with Time Windows and Pickup and Delivery Journal: a journal by Alessia Ciacco, Francesca Guerriero, Eneko Osaba (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-17896.txt.
Introduction
Alessia Ciacco, Francesca Guerriero, and Eneko Osaba present a 2025 routing problem that blends classic and quantum optimization. Their variant of the traveling salesman task adds time windows, pickup and delivery jobs, and vehicle load limits. Optional stops from the Steiner form add one more twist.
Those traits mirror last mile delivery, returns logistics, and on demand services. The problem is NP hard, so the team gives two math forms: one based on arcs and one on nodes. A cleanup step cuts redundant arcs to speed the solve. A test case generator builds varied, scalable scenes for fair checks. Classical solves run on a commercial solver, while quantum routes are tested in parallel for robustness.
Catalog record
| CREATOR | Alessia Ciacco, Francesca Guerriero, Eneko Osaba |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-17896
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum Optimization for the Steiner Traveling Salesman Problem with Time Windows and Pickup and Delivery Journal: a journal Alessia Ciacco, Francesca Guerriero, Eneko Osaba Abstract We present 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. Both models are implemented on D-Wave’s LeapCQMHybrid platform, which combines quantum and classical techniques for solving constrained optimization tasks. We further introduce a preprocessing reduction method that eliminates redundant arcs, significantly enhancing computational performance and scalability. Experimental results demonstrate that hybrid quantum approaches are capable of solving problem instances of realistic size, underscoring their potential as a transformative tool for next-generation routing optimization. 1 Introduction Routing problems are among the most central and extensively studied challenges in combinatorial optimization, due to their wide range of real-world applications in domains such as logistics, transportation and urban distribution. In recent years, the relevance of these problems has grown significantly, driven by the digital transformation of supply chains, the exponential rise of e-commerce, and the increasing demand for reliable, customized solutions. Effective route optimization not only reduces operational costs but also contributes to lower emissions, improved fleet utilization and higher service quality. The Vehicle Routing Problem (VRP) is a fundamental combinatorial optimization problem in logistics and transportation. It focuses on determining the most efficient routes for a fleet of vehicles to deliver goods to a set of customers, starting and ending at one or more depots [ 1 , 2 ] . Among the most studied extensions of the VRP is the variant involving time windows, where each customer must be served within a specified time interval. This reflects realistic delivery scenarios, where users often select preferred delivery slots when placing an order. These temporal constraints add realism to the model but also significantly increase its computational complexity, as feasible solutions must simultaneously satisfy both spatial and temporal requirements [ 3 , 4 , 5 ] . Another practically relevant variant is the VRP with pickup and deliveries (VRP-PDP), in which each request involves a pair of locations, one for pickup and one for delivery, subject to precedence and capacity constraints. This model reflects the growing complexity of modern logistics systems, where vehicles must not only deliver but also collect items, such as in reverse logistics, product returns or shared mobility services. VRP-PDP based models have a wide range of applications, including ride-sharing, e-commerce, hospital logistics and urban freight distribution [ 6 , 7 ] . The simultaneous integration of time windows and pickup and delivery constraints results in a highly challenging class of routing problems, due to the combined presence of spatial, temporal and logistical dimensions. These problems are known to be NP-hard and their complexity grows rapidly with problem size, making them particularly difficult for both exact and heuristic classical methods. Furthermore, the Steiner Traveling Salesman Problem (STSP) is a combinatorial optimization problem that generalizes both the Traveling Salesman Problem (TSP) and the Steiner Tree Problem (STP). It aims to find a minimum-cost route that visits a subset of required nodes, referred to as required nodes, in a graph at least once. The route may include optional Steiner nodes, non-required vertices that help reduce the overall cost and allows edges to be traversed multiple times, offering flexibility not present in the classical TSP. From the TSP, the STSP inherits the objective of constructing an efficient tour. However, unlike the TSP, which requires visiting all nodes exactly once, the STSP only requires covering the required nodes and permits the reuse of nodes and edges. From the STP, it adopts the idea of connecting key nodes while using intermediate ones to minimize cost, though the STSP seeks a tour rather than a tree structure. This hybrid structure makes the STSP particularly suitable for applications in network design, logistics, and transportation, where only a subset of critical points must be connected efficiently within an existing infrastructure. As with the TSP and STP, the STSP is NP-hard, and solving large instances exactly remains computationally challenging. Despite its practical potential, extending the STSP to account for real-world constraints such as time windows and pickup and delivery has received limited attention in the literature, possibly due to the high computational complexity these extensions introduce. In recent years, quantum computing has emerged as a promising paradigm for addressing combinatorial optimization problems that are notoriously difficult for classical algorithms, such as those found in routing and logistics. The potential of quantum technologies, particularly quantum annealing, lies in their ability to explore vast solution spaces more efficiently through parallelism and energy-based optimization landscapes. This capability is especially relevant for VRPs and their variants, which often involve large-scale, constraint-rich formulations that challenge the limits of exact and heuristic solvers. Given this context, the use of quantum computing, especially hybrid quantum-classical methods, represents a highly relevant and timely research direction for tackling next-generation routing problems that combine spatial, temporal and logistical complexity. In this work, we propose and study a novel and realistic variant, referred to as the Steiner Traveling Salesman Problem with Time Windows and Pickup and Delivery (STSP-TWPD). This new formulation captures the partial coverage structure of the STSP while incorporating temporal constraints related to customer availability, as well as precedence and capacity constraints typical of pickup and delivery operations. As such, the STSP-TWPD models a wide range of real-world logistics and transportation problems that cannot be adequately represented by classical STSP or VRP formulations. Our contribution is distinctive in that we not only define this problem, but also demonstrate its tractability through a quantum-compatible representation. Leveraging the Constrained Quadratic Model (CQM) formulation and D-Wave’s LeapCQMHybrid solver, we provide the first implementation of the STSP-TWPD in a hybrid quantum-classical environment. This allows for a natural and structured way to express complex real-world constraints, such as pickup-delivery precedence, time feasibility and capacity limitations, without oversimplifying the problem structure or relying on hard-coded heuristics. The use of the CQM framework provides a modeling advantage over traditional QUBO-based approaches, which often require cumbersome reformulations and can limit flexibility when new constraints are introduced. To the best of our knowledge, this is the first study to integrate the constraint structure of the STSP-TWPD with the capabilities of quantum annealing. In doing so, we not only push the boundaries of quantum-enabled optimization, but also demonstrate that hybrid quantum solvers are already capable of addressing problem instances of realistic size and complexity. In this work, we propose two distinct mathematical formulations for the STSP-TWPD. In the first, an Arc-Based Formulation (ABF) the route variables are associated with arcs. This formulation builds upon the classical STSP model by incorporating additional constraints to manage time windows as well as pickup and delivery operations. The second, a Node-Based Formulation (NBF), is a model in which the routing