The six elements to block-building approaches for the single container loading problem

摘要

In the Single Container Loading Problem, the aim is to pack three-dimensional boxes into a three-dimensional container so as to maximize the volume utilization of the container. Many recently successful techniques for this problem share a similar structure involving the use of blocks of boxes. However, each technique comprises several seemingly disparate parts, which makes it difficult to analyze these techniques in a systematic manner. By dissecting block building approaches into 6 common elements, we found that existing techniques only differ in the strategies used for each element. This allows us to better understand these algorithms and identify their effective strategies. We then combine those effective strategies into a greedy heuristic for the SCLP problem. Computational experiments on 1,600 commonly used test cases show that our approach outperforms all other existing single-threaded approaches, and is comparable to the best parallel approach to the SCLP. It demonstrates the usefulness of our component-based analysis in the design of block building algorithms.