The 6 Key Elements to SCLP Block Building Approaches

The aim of the Single Container Loading Problem is to pack three-dimensional boxes into a three-dimensional container so as to maximize the volume utilization of the container. Many recently developed, 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. In this paper, we explain the 6 key elements in block building approaches, namely 1) how to represent free space in a container; 2) how to generate a list of blocks; 3) how to select a free space; 4) how to select a block; 5) how to place the selected block into the selected space; and 6) what is the overarching search strategy. All block building approaches only differ in the strategies used for each decision. Aided by this understanding, we selected some of the most effective strategies from existing literature for each decision, and combined those strategies into an effective greedy heuristic for the SCLP problem. Experiments show that our approach outperforms all other existing approaches. © 2010 IEEE.