Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
This paper presents a binary tree search algorithm for the three dimensional container loading problem (3D-CLP). The 3D-CLP is about how to load a subset of a given set of rectangular boxes into a rectangular container, such that the packing volume is maximized. In this algorithm, all the boxes are grouped into strips and layers while three constraints, i.e., full support constraint, orientation constraint and guillotine cutting constraint are satisfied. A binary tree is created where each tree node denotes a container loading plan. For a non-root each node, the layer set of its left (or right) child is obtained by inserting a directed layer into its layer set. A directed layer is parallel (or perpendicular) to the left side of the container. Each leaf node denotes a complete container loading plan. The solution is the layer set whose total volume of the boxes is the greatest among all tree nodes. The proposed algorithm achieves good results for the well-known 3D-CLP instances suggested by Bischoff and Ratcliff with reasonable computing time. © 2014 Elsevier Ltd. All rights reserved.
Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004
Michael D. Moffitt
ICCAD 2009
David A. Selby
IBM J. Res. Dev