Title :
The 6 key elements to SCLP block building approaches
Author :
Weng, Yujian ; Guo, Songshan ; Zhu, Wenbin ; Lim, Andrew ; Oon, Wee-Chong
Author_Institution :
Dept. of Comput. Sci., Zhong Shan (Sun Yat-Sen) Univ., Guangzhou, China
Abstract :
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.
Keywords :
containerisation; containers; decision making; greedy algorithms; loading; search problems; SCLP; block building approach; decision making; greedy heuristic; overarching search strategy; single container loading problem; Cities and towns; 3D packing; block building; greedy heuristic; incomplete tree search;
Conference_Titel :
Educational and Information Technology (ICEIT), 2010 International Conference on
Conference_Location :
Chongqing
Print_ISBN :
978-1-4244-8033-3
Electronic_ISBN :
978-1-4244-8035-7
DOI :
10.1109/ICEIT.2010.5607657