Exact decomposition approaches for a single container loading problem with stacking constraints and medium-sized weakly heterogeneous items

We consider a real-world three-dimensional container loading problem in which the objective is to maximize the volume of the items packed into a single vehicle. While container loading problems have been extensively studied in the literature, our case study displays a set of item features (rotation, medium-sized dimensions, stackability, weak heterogeneity) that was not often considered together in previous research papers. In fact, we show that some of these features can be exploited in an innovative way to derive more effective exact algorithms. We first describe a compact integer programming model to solve the problem exactly together with a number of ad hoc reduction procedures and modeling tricks to enhance the empirical performance of the model. We then present a sequential approach where one generates item columns in a first stage and then solves a two-dimensional knapsack problem afterwards and show that each of the two components is NP-hard. Thereafter, we introduce a set of exact algorithms based on Benders’ decomposition. We identify three ways to split the problem decisions (deciding if an item should be packed, in which column, in which x-coordinate, and in which y-coordinate) into the classical master-subproblem framework and we observe trough an extensive set of computational experiments on both real and randomly generated instances that not all decomposition methods are as competitive as the others. We conclude our work by showing how relevant extensions of the problem related to item fragility and customer visit order can be taken into account. Overall, this work aims at establishing a bridge between the theoretical field of two-dimensional packing problems and the more practical field of container loading problems.