A multiplier adjustment algorithm for a truck scheduling and transshipment problem at a cross-docking terminal

The paper deals with a truck scheduling and transshipment problem in a cross-docking terminal, with one inbound gate and one outbound gate. Each inbound truck carries one or more load units possibly of different commodities, and each outbound truck must be loaded with different commodities as well. The problem is to define the sequence of trucks at the inbound and outbound gates and the transshipment plan, so as to minimize the makespan of the whole process. We propose a Lagrangian relaxation scheme and a dual ascent method to optimize the Lagrangian dual that encloses three heuristics aimed at recovering feasible solutions for the problem at hand from the solution of the Lagrangian problem. Computational experiments are also provided, in order to evaluate the effectiveness of the Lagrangian approach.