On the single door cross-docking problem

A cross-docking terminal is a logistic platform involved in the distri- bution process of products from the suppliers to the retailers. It can be seen as a facility where products arriving by inbound trucks, generally as less-than-truckload shipments, are arranged with respect to retailers' requirements into full truckloads and directly delivered by outbound trucks, skipping thus the storage phase. Such a distribution strategy needs a high level of synchronization between the inbound and outbound operations, that is truck unloading and loading, respectively. In this talk we address the problem in case the terminal is equipped with two doors, one for the unloading and the other for loading operations. For this basic problem, we propose an Integer Linear Programming formulation and a Lagrangian Relaxation approach. We show that the Lagrangian problem decomposes in two combinatorial sub-problems. We study the mathematical properties of the sub-problems and derive exact solution algorithms for both of them, as well as optimality condition for the Lagrangian Dual problem. Based on the theoretical results, we propose a Lagrangian heuristic algorithm. Finally, we present and discuss some numerical results.