Eine Heuristik für das dreidimensionale Strip-Packing-Problem

The contribution presents a heuristic for the three-dimensional strip-packing problem (3D-SPP) with rectangular shaped pieces (boxes). The considered 3D-SPP can be formulated as follows: for a given set of boxes and a given longitudinal open container, determine a feasible arrangement of all boxes within the container so that the required containter length is minimized. The presented heuristic was derived from a branch-and-bound approach for the container loading problem (CLP) that was recently proposed by Pisinger. This method fills the container in a number of vertical layers across the length of the container. Two approaches are investigated to adapt the CLP method fo the 3D-SPP: The first approach, referred to as adaption with an open container, looks directly at a container of practically infinite length. The second approach, referred to as adaption with closed container, generates a solution of an SPP instance by computing a sequence of CLP instances with descending container length. For each container length, this approach tries to reuse parts of the current best solution by packing its boxes. If all boxes can be stowed within the current container length, a new best solution has been achieved. The approach with closed containers proves to be much more successful. The heuristic for the SPP is subjected to a comparative test that considers some alternative methods. The test is based on a subset of the well-known benchmark instances from Bischoff and Ratcliff for the CLP, which have been adapted to the 3D-SPP. The obtained computational results show a high performance of the proposed heuristic.