Quantum Annealing Approaches to Solving the Shipment Rerouting Problems
Fei Li, Arul Rhik Mazumder, Max Zhao · 2025
Read Quantum Annealing Approaches to Solving the Shipment Rerouting Problems by Fei Li, Arul Rhik Mazumder, Max Zhao (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-2501-05624.txt.
Introduction
Fei Li, Arul Rhik Mazumder, and Max Zhao tackle shipment rerouting, a logistics problem that bundles many hard sequencing and packing problems into one. Goods must move by truck between hubs from sources to destinations, and the solver must choose trucks and routes that minimize total cost. The problem is NP-hard, and only classical approximate methods existed for its variants with limited truck capacity.
The authors design both classical methods and quantum annealing algorithms for the task. Their edge comes from new mathematical programming formulations that exploit the network's structure, the shipments, and truck capacities together, handling sequencing and packing at once rather than separately. In extensive experiments across scenarios, the quantum annealing solver reached optimal or near-optimal solutions much faster than the standard solver. The team presents the work as evidence that quantum annealers can compete on real logistics optimization.
Catalog record
| CREATOR | Fei Li, Arul Rhik Mazumder, Max Zhao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-05624
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum Annealing Approaches to Solving the Shipment Rerouting Problems Fei Li, Arul Rhik Mazumder, Max Zhao Abstract In this paper, we study a shipment rerouting problem (SRP) which generalizes many NP-hard sequencing and packing problems. An 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. 1 Introduction We study a shipment rerouting problem that has been proposed in [ 8 ] . In this problem, there is a network that contains hubs and a set of transportation means (such as trucks or trains) that can have their runs on the network. For simplicity, we represent various transportation means using trucks with different capacities and different rental costs. A list of transportation requests , which specify some amounts of goods to be delivered from their sources to their respective destinations, should be satisfied. The objective is to minimize the total cost of successfully transporting these goods from their sources to their destinations. Problem statement. The shipment rerouting problem is formulated as follows. We have a network represented by a directed graph G=(V,E) , where V is the set of vertices and E is the set of edges. Each edge e\in E has a cost c_{e}\geq 0 . A set of goods are to be transported by trucks with various capacities running over the network. A subset of vertices H\subseteq V are labeled hubs where goods can be loaded and unloaded. Note that a hub can be both some goods’ source-hubs and some other goods’ destination-hubs. From the digraph G , we generate a complete digraph F=(H,P) where the set of vertices H\subseteq V denotes the hubs only and the set of edges p(i,j)\in P denote the shortest paths connecting two hubs i\in H and j\in H in the transportation network G=(V,E) – these path costs c({p(i,j)}):=\sum_{e\in p(i,j)}c_{e} can be precalculated using |V| rounds of the Dijkstra’s algorithm [ 2 ] in time O(|E||V|+|V|^{2}\log|V|) . The generated digraph F has its edge costs satisfy the triangular inequalities. Consider the complete digraph F=(H,P) . Let |H|=n and we label these hubs \in H as 1,2,\ldots,n . There are m transportation requests of truck runs for transporting goods. We use a triple (s_{i},t_{i},\ell_{i}) to denote a truck run i ( i=1,2,\ldots,m ), where s_{i} is the source-hub, t_{i} is the destination-hub, and \ell_{i} is the goods’ load. There are two constraints: • ( A_{1} ) The goods cannot be divided into fractions during transportation. • ( A_{2} ) Once some goods are loaded on a truck, these goods cannot be unloaded before the truck reaches these goods’ destination. That is, goods can be loaded only at these goods’ source-hubs and unloaded at their destination-hubs. There are a set of trucks with various capacities. For goods with load \ell_{i} , a truck with its remaining capacity \geq\ell_{i} can load the goods at s_{i} and unload the goods at t_{i} . There is a list of K trucks (transportation means) with their capacities L_{1},L_{2},\ldots,L_{K} respectively, and for these K trucks, we pay costs R_{1},R_{2},\cdots,R_{K} respectively for renting and operating them. Without loss of generality, we have two assumptions: ( 1 ) L_{1}\leq L_{2}\leq\ldots\leq L_{K} and ( 2 ) R_{1}\leq R_{2}\leq\cdots\leq R_{K} . All the values (edge costs, loads of goods, truck capacities, rental fees) are positive numbers. Subject to both constraints A_{1} and A_{2} , the objective is to minimize the total cost of truck rental fees and C times the traveling distances of trucks transporting all the goods from their sources to their respective destinations, where C>0 is a positive constant representing the money spent per unit of traveling distance. We name this problem SRP (shipment rerouting problem). Related work. Many variants of the shipment rerouting problem SRP have been studied in the past. The problem SRP is intractable, as shown below. Consider a setting in which all the trucks have capacities more than the total goods’ load \sum_{i}\ell_{i} and the minimum rental cost R_{1} is more than the total cost of all the paths among all the hubs. In addition, assume that all the transportation requests are very far apart from each other compared to the traveling distance of each transportation request. Thus, to minimize the total cost paid to transport all the goods, we only need one truck to ship all the goods, and the optimal solution to this SRP’s instance minimizes the total traveling distance by visiting all the hubs. The special instance of SRP is reduced to a NP-complete sequencing problem , the traveling salesman problem [ 5 ] . Now, we consider another special case in which all the transportation requests are with the same source-hub and the same destination-hub. In addition, the network is just a line graph. We show that this variant of SRP is NP-complete. Consider n transportation requests, each transportation request i having a need \ell_{i} . There are only two identical trucks, each having a capacity equal to \sum\ell_{i}/2 . Thus, we need to decide which request is assigned to which truck to carry from the source to the destination. This problem reduces to an NP-complete packing problem , the partition problem [ 4 ] . To our knowledge, there are no classical approximation algorithms known for this shipment rerouting problem. Part of the reason is that an algorithm’s approximation ratio is very sensitive to the values in the input instance. It is easy to construct an instance so that an approximation ratio can be changed from 1 to an arbitrary number given a slight change in the shipment loads, the truck capacities, and/or the rental fees. For such a problem, we consider not only how to schedule shipments to minimize the total traveling distance but also how to pack goods to satisfy the truck capacity constraints. A single algorithmic technique generally cannot optimize the objective under both constraints. The most recent work related to ours is [ 8 ] . In this work [ 8 ] , Osaba et al. gave a quadratic unconstrained binary optimization (QUBO) formulation to solve the problem. However, this QUBO-based formulation works only for a single truck route, and their algorithm is to iteratively select truck routes one by one to serve all transportation requests. This heuristic approach is not guaranteed to generate an optimal set of trucks to deliver goods, and no proof shows its optimality [ 8 ] . The QUBO formulation is solved using an Ising model-based quantum