.png){kind=icon}
.png){kind=icon}
Return
A Tree Search-Based Heuristic for the Three-Dimensional Single Container Loading Problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2026.01.039.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The three-dimensional single-container loading problem aims to fill a container with items to maximize the volume utilization. Items are rectangular and may rotate, but only orthogonal placements are allowed. This problem is highly relevant to industry, notably in supply chain logistics. Heuristics remain the most suitable and widely used method for medium and large-sized instances. We consider a beam search heuristic embedded into a double-effort mechanism. It uses a cover representation with maximal empty spaces for the residual space and generates blocks of items in a guillotine pattern. A two-stage fitness function selects the blocks, and a greedy search selects the most promising partial packings. We propose several advancements to this heuristic, including specific data structures to represent residual spaces, deeper calibration of its metaparameters, hash structures to avoid recomputing packings, and a two-stage fitness function. Computational experiments on 1,600 benchmark instances demonstrate the high performance of the proposed heuristic. Using the same computer, our method achieves 95.91% average volume usage in 30 seconds, a +0.59% improvement over the state-of-the-art within the 30-second time limit. With 5 seconds, it achieves a 95.40% result, still outperforming the state-of-the-art by +0.08%. All these improvements are statistically significant and represent a considerable advance when considered in the historical context. The 2014 literature method required 500 seconds and achieved a +0.42% gain, while the 2017 state-of-the-art method reduced runtime to 30 seconds and achieved a +0.13% gain.
Keywords:
Packing
Container loading problem
Heuristic
Beam search algorithm
Tree search
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W