Exact decomposition approaches for a single container loading problem with stacking constraints and medium-sized weakly heterogeneous items
研究一个真实的三维容器装载问题，目标最大化装入单个车辆的物品体积，针对中尺寸、弱异构、可堆叠等特征，提出了基于Benders分解的精确算法，并通过实验比较了不同分解策略的效果。
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.