The lateral transhipment problem with a-priori routes, and a lot sizing application

Martin Romauch, Thibaut Vidal, Richard F. HartlarXiv 2015 · arXiv

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:

  1. Superposition: Calculating the result of a pickup or delivery move by combining the current value function with the cost function of the move.
  2. Envelope: Finding the lower (or upper) envelope of several options to determine the optimal decision at a given state.
Geometric operations for the DP: superposition and envelope calculation.

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$.

Visualization of the 3D value function surface and its representation using nested lists.

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

Abstract

We propose exact solution approaches for a lateral transhipment problem which, given a pre-specified sequence of customers, seeks an optimal inventory redistribution plan considering travel costs and profits dependent on inventory levels. Trip-duration and vehicle-capacity constraints are also imposed. The same problem arises in some lot sizing applications, in the presence of setup costs and equipment re-qualifications. We introduce a pure dynamic programming approach and a branch-and-bound framework that combines dynamic programming with Lagrangian relaxation. Computational experiments are conducted to determine the most suitable solution approach for different instances, depending on their size, vehicle capacities and duration constraints. The branch-and-bound approach, in particular, solves problems with up to 50 delivery locations in less than ten seconds on a modern computer.
BibTeX
@misc{romauch2015lateral,
  author = {Martin Romauch and Thibaut Vidal and Richard F. Hartl},
  title = {{The lateral transhipment problem with a-priori routes, and a lot sizing application}},
  year = {2015},
  eprint = {1512.07449},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1512.07449},
}
Figure