This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Fanslau, T. Articles by Bortfeldt, A.

A Tree Search Algorithm for Solving the Container Loading Problem

Department of Information Systems, University of Hagen, 58084 Hagen, Germany
Department of Information Systems, University of Hagen, 58084 Hagen, Germany
tobias.fanslau{at}onlinehome.de
andreas.bortfeldt{at}fernuni-hagen.de

This paper presents a tree search algorithm for the 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 packing volume is maximized. The method includes two variants: the full-support variant guarantees full support from below for all packed boxes, although this constraint is not taken into account by the nonsupport variant. The guillotine cut constraint is considered by both variants. The method is mainly based on two concepts. On the one hand, the block building approach is generalized. Not only are blocks of identical boxes in the same spatial orientation applied but also blocks of different boxes with small inner gaps. On the other hand, the tree search is carried out in a special fashion called a partition-controlled tree search. This makes the search both efficient and diverse, enabling a sufficient search width as well as a suitable degree of foresight. The approach achieves excellent results for the well-known 3D-CLP instances suggested by Bischoff and Ratcliff [Bischoff, E. E., M. S. W. Ratcliff. 1995. Issues in the development of approaches to container loading. Omega 23(4) 377–390] with reasonable computing time.

Key words: container loading; 3D packing; heuristic; tree search
History: received December 2007; revised March 2009; accepted March 2009.