A tree search algorithm for solving the container loading problem

A tree search algorithm for solving the container loading problem

0.00 Avg rating0 Votes
Article ID: iaor20104214
Volume: 22
Issue: 2
Start Page Number: 222
End Page Number: 235
Publication Date: Mar 2010
Journal: INFORMS Journal on Computing
Authors: ,
Keywords: programming: integer
Abstract:

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 (1995) with reasonable computing time.

Reviews

Required fields are marked *. Your email address will not be published.