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

作     者：Delorme, Maxence Wagenaar, Joris 

作者机构：Tilburg Univ Dept Econometr & Operat Res Tilburg Netherlands 

出 版 物：《OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE》 (Omega)

年 卷 期：2024年第125卷

核心收录：

学科分类：12[管理学] 120202[管理学-企业管理（含：财务管理、市场营销、人力资源管理）] 0202[经济学-应用经济学] 02[经济学] 1202[管理学-工商管理] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

基　　金：Dutch ministry of education SURF 

主　　题：Container loading problem Operations research applications Exact algorithms Integer linear programming Benders' decomposition 

摘      要：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.