A Lagrangian approach to a cross-docking problem with multiple gates

A cross-docking center (CD) is a distribution facility, where goods entering the facility by inbound trucks are unloaded, consolidated with respect to customers' orders, and delivered by outbound trucks being stored for a very short time or even not stored at all. The management at the operative level of a CD aims at optimizing the truck sequencing at the gates. Here we address the general case where multiple inbound and outbound gates are considered and each inbound (outbound) truck ships (requires) possibly multiple products. The Multi-Gates Multi-Products Cross-Docking problem (MGMPCD) is then to schedule the inbound and outbound trucks at the respective gates, and to decide the amount of each product to be shipped from each inbound truck to each outbound truck, so as to minimize the makespan. We propose a Lagrangian heuristic and discuss some preliminary computational results obtained by our algorithm on a set of randomly generated test instances, by a comparison with the solutions computed by a benchmark ILP solver.