Chinese Journal of Computers   Full Text
Title	A Hybrid Simulated Annealing Algorithm for the Three-Dimensional Packing Problem
Authors	ZHANG De-Fu1),2) PENG Yu1) ZHU Wen-Xing3) CHEN Huo-Wang2),4)
Address	1)(Department of Computer Science, Xiamen University, Xiamen, Fujian 361005) 2)(Longtop Group Post-doctoral Research Center, Xiamen, Fujian 361005) 3)(Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350002) 4)(School of Computer, National University of Defense Technology, Changsha 410073)
Year	2009
Issue	No.11(2147—2156)
Abstract &   Background	Abstract This paper presents an efficient hybrid simulated annealing algorithm for three dimensional container loading problem (3D-CLP). The 3D-CLP is the problem of loading a subset of a given set of rectangular boxes into a rectangular container so that the stowed volume is maximized. The algorithm introduced in this paper is based on three important algorithms. First, complex block generating, complex block can contain any number boxes of different types, which differs from the traditional algorithm. Second, basic heuristic, which is a new construction heuristic algorithm used to generate a feasible packing solution from a packing sequence. Third, simulated annealing algorithm, based on the complex block and basic heuristic, it encodes a feasible packing solution as a packing sequence, and searches in the encoding space to find an approximated optimal solution. 1500 benchmark instances with weakly and strongly heterogeneous boxes are considered in this paper. The computational results show that the volume utilization of hybrid algorithm outperforms current excellent algorithms for the considered problem. Keywords three-dimensional container loading; heuristic algorithm; simulated annealing algorithm Background Three-dimensional packing problem belongs to NP hard problem. At present, some excellent algorithms have been presented to solve the problem. The hybrid simulated annealing algorithm based on a constructive heuristic algorithm is presented, the computational results have shown that this algorithm outperforms the current excellent algorithms. The work is supported by the National Nature Science Foundation of China (Grant no. 60773126) and the Province Nature Science Foundation of Fujian (Grant No.2007J0037). The projects aim at designing highly efficient algorithms for NP hard problems, such as the packing problem and timetabling problem, which are the most important part of automated packing and timetabling software. The project team has designed some efficient algorithms for SAT problem, the circle packing problem, the rectangle packing problem, three-dimensional packing problem and Timtabling problem, some results have been published. The fundamental aim of this paper was to investigate three-dimensional packing problem and to develop state-of-the-art algorithms that could be used in an industrial field. The paper belongs to one of the key parts of the project.