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

Maxence Delorme and Joris Wagenaar

Omega, 2024, vol. 125, issue C

Abstract: 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.

Keywords: Container loading problem; Operations research applications; Exact algorithms; Integer linear programming; Benders’ decomposition (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048324000069
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:125:y:2024:i:c:s0305048324000069

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2024.103039

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().