Automating Bin Packing: A Layer Building Matheuristics for Cost Effective Logistics

In this paper, we address the problem of automating the definition of feasible pallets configurations. This issue is crucial for the competitiveness of logistic companies and is still one of the most difficult problems in internal logistics. In fact, it requires the fast solution of a three-dimensional Bin Packing Problem (3D-BPP) with additional logistic specifications that are fundamental in real applications. To this aim, we propose a matheuristics that, given a set of items, provides feasible pallets configurations that satisfy the practical requirements of items' grouping by logistic features, load bearing, stability, height homogeneity, overhang as well as weight limits, and robotized layer picking. The proposed matheuristics combines a mixed integer linear programming (MILP) formulation of the 3D-Single Bin-Size BPP (3D-SBSBPP) and a layer building heuristics. In particular, the feasible pallets configurations are obtained by sequentially solving two MILP sub-problems: the first, given the set of items to be packed, aims at minimizing the unused space in each layer and thus the number of layers; the latter aims at minimizing the number of shipping bins given the set of layers obtained from the first problem. The approach is extensively tested and compared with existing approaches. For its validation we use both realistic data-sets drawn from the literature and real data-sets, obtained from an Italian logistics leader. The resulting outcomes show the effectiveness of the method in providing high-quality bin configurations in short computational times.