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. From a physical point of view, it consists of a number of gates, determining the number of trucks that can be simultaneously processed. Goods unloaded at the inbound gates are transfered to the outbound gates by a conveying system; there they are nally loaded into the outbound trucks. Note that, in both the loading and unloading phases, a truck is not allowed to leave the gate where it is processed until the loading/discharging operation is completed [3]. The management at the operative level of a CD aims, therefore, at optimizing the truck sequencing at the gates. For a complete review of the literature the interested reader can refer to [1], [2], [4]. 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.