A tree search-based heuristic for the three-dimensional single container loading problem

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 1600 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.