A Decomposition-Based Heuristic for the Truck Scheduling Problem in a Cross-Docking Terminal

We consider the truck scheduling problem at a cross docking terminal with many inbound and outbound doors, under the assumption of constant handling time for all the trucks, the objective being to minimize the completion time of the whole process. We propose a mathematical model together with a Lagrangian Relaxation scheme. We discuss the structural properties of the relaxed problem and derive a Lagrangian heuristic able to compute, at the same time, good feasible solutions and increasing lower bounds. The numerical results show that the Lagrangian decomposition is a promising approach to the solution of such problems.