Abstract
This paper introduces efficient exact solution methods for the "Lateral Transhipment Problem with A-Priori Routes" (ARELTP)—a challenge where a vehicle must redistribute inventory across a fixed sequence of customers to maximize profit. By combining dynamic programming with Lagrangian relaxation, the authors achieved speedups of up to 100x over commercial solvers, solving complex 50-location problems in under ten seconds. The work also establishes a mathematical equivalence between routing and lot-sizing problems, providing a unified framework for these distinct logistics challenges.
Introduction
In traditional logistics, goods usually flow from a central depot to customers. Lateral transhipment flips this: it involves moving inventory between locations at the same level of the supply chain, such as moving bikes between stations in a bike-sharing app or parts between retail stores.
The authors focus on a specific sub-problem: the a-priori route evaluation. In this scenario, a planned sequence of stops (the "a-priori route") is already established. The goal is to decide exactly how much to pick up or drop off at each stop—or even which stops to skip entirely—to maximize profit while respecting the vehicle's capacity and a total travel time limit.
The Routing-Lot Sizing Duality
A key contribution of this research is proving that the ARELTP is mathematically equivalent to lot-sizing with re-qualification costs (LSwRC). In manufacturing, re-qualification costs occur when a machine sits idle for too long and requires a setup before it can run again. The authors demonstrate that a vehicle moving through space is functionally identical to a factory moving through time: skipping a customer in a route is equivalent to having an idle period in a production schedule. This duality allows solution methods developed for one domain to be applied directly to the other.
Geometric Dynamic Programming
To solve the ARELTP, the authors developed a custom Dynamic Programming (DP) approach. For versions of the problem without a strict time limit, they use "continuous labels." Instead of checking every possible discrete inventory level, they represent the "value" of arriving at a stop as a piecewise-linear function of the current inventory.
This approach relies on two core geometric operations:
- Superposition: Calculating the result of a pickup or delivery move by combining the current value function with the cost function of the move.
- Envelope: Finding the lower (or upper) envelope of several options to determine the optimal decision at a given state.
By treating the optimization as a series of geometric operations on polygons, the authors exploit the specific structure of piecewise-linear costs, moving away from standard "black box" solvers.
Handling Global Constraints
While vehicle capacity is a "local" constraint (it only matters what is in the truck at a specific moment), travel time is a "global" constraint (it depends on the total trip duration). Pure DP becomes computationally expensive when global constraints are added. To address this, the authors implemented a Hybrid Branch-and-Bound (BBDP) approach using Lagrangian relaxation.
This technique moves the hard time limit into the objective function as a penalty for exceeding the budget. This "relaxed" version is much easier to solve with DP, providing a strong bound for the Branch-and-Bound tree. The resulting value functions $U_{i,t}(q)$ represent the optimal cost for a given inventory $q$ and time $t$.
To further improve efficiency, the authors introduced integerization. If the input data consists of integers, they can prune tiny, redundant segments of the value functions. This drastically reduces computational effort without sacrificing the optimality of the solution.
Experimental Results
The algorithms were tested on two main families of data: classic "orienteering" benchmarks (SRLTP) and a new set of lot-sizing benchmarks (LSwRC). The results were significant:
- Massive Speedups: The custom DP approach was 50 to 100 times faster than Gurobi, a top-tier commercial solver, on problems without duration limits.
- Robustness: The hybrid BBDP approach solved almost all 50-location instances in less than 10 seconds. In contrast, Gurobi occasionally took up to 30 minutes on specific lot-sizing instances.
- Efficiency: The integerization of DP labels significantly reduced the number of segments in the value functions, proving that infinite precision is not required for optimal logistics planning.
Conclusion and Future Work
The current model is restricted to a single vehicle and a single route. However, the authors suggest that these exact methods could serve as powerful "sub-routines" within larger heuristic algorithms. For instance, a Local Search algorithm could propose thousands of routes, and this paper's method could instantly evaluate the optimal profit for each. This would enable the optimization of complex, multi-vehicle city-wide redistribution systems in real-time.
Summary updated