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.
The problem is also very relevant on its own, as a case of routing optimization with a-priori routes @cite_8 . In practical routing applications, retaining some fixed route fragments can lead to a better operational and computational tractability for companies, as well as efficiency gains through driver learning. The corresponding subproblem is called the evaluation problem for a-priori routes, and efficient solution methods are needed to quickly react to changing environments. We also show that the same model encompasses several lot sizing applications with re-qualification costs.
@cite_8
1998707332
Abstract In 1985, Jaillet introduced the probabilistic traveling salesman problem (PTSP), a variant of the classical TSP in which only a subset of the nodes may be present in any given instance of the problem. The goal is to find an a priori tour of minimal expected length, with the strategy of visiting the present nodes in a particular instance in the same order as they appear in the a priori tour. In this paper we reexamine the PTSP using a variety of theoretical and computational approaches. We sharpen the best known bounds for the PTSP, derive several asymptotic relations, and compare from various veiwpoints the PTSP with the re-optimization strategy, i.e., finding an optimal tour in every problem instance. When a Euclidean metric is used and the nodes are uniformly distributed in the unit square, a heuristic for the PTSP is shown to be very close to the re-optimization strategy. We examine some PTSP heuristics with provable worst-case performance, and address the question of finding constant-guarantee heuristics. Implementations of various heuristics, some based on sorting and some on local optimality, permit us to discuss the qualitative and quantitative properties of computational problems with up to 5000 nodes.