Lagrangian Relaxation for the Intermediate Facilities Location Problem

The consolidation and merging of freight flows is crucial for logistics operations in order to reduce costs and keep the level of service provided to customers, especially when trucks travel with a half-full load. These kinds of operations take place in intermediate facilities or terminals located between the origins and the destinations of freight. We consider the problem of locating the intermediate facilities in a transportation network, which gives rise to a combinatorial problem. We address the problem through the Lagrangian decomposition. The Lagrangian dual is solved by efficient non-differentiable optimization methods and the sub-problem (the Lagrangian relaxation) is reduced to a binary quasi-knapsack problem. The proposed method is extensively tested on randomly generated instances showing it obtains tight lower bounds. In addition, we develop a Lagrangian-based heuristic to attain an integer feasible solution. Numerical results are reported, comparing the performance of the proposed methods with those obtained by applying a general-purpose Mixed-Integer Linear Programming solver to a mathematical formulation of the problem.