A Lagrangian heuristics for the truck scheduling problem in multi-door, multi-product Cross-Docking with constant processing time

The paper describes a Lagrangian heuristic algorithm for a cross-docking problem, where given amounts of several products must be directly transshipped from a given set of inbound trucks to a given set of outbound trucks. The cross-docking centre is equipped with some inbound and outbound doors (or gates), where the discharging/loading activities, which are assumed to require a constant time for each truck, take place. The objective is to schedule the activities and to design the transshipment plan, while minimizing the ending time of the whole process. Moving along a research line recently traced for the single-door case, the main contribution of the paper is the Lagrangian decomposition scheme for the structured integer linear model of the problem. In particular, decomposition in three subproblems is provided. For all such problems effective solution algorithms are proposed. Two repairing heuristics are embedded into the algorithm for tackling the Lagrangian dual, thus allowing calculation of both lower and upper bounds on the optimal objective function. The performance of the algorithm is evaluated through extensive computational experiments on instances of different typologies in terms of number of gates, trucks and products.