A heuristic for the three-dimensional strip packing problem

The contribution presents a heuristic for the three-dimensional strip packing problem (3D-SPP) with rectangular pieces (boxes). The considered 3D-SPP can be formulated as follows: for a given set of boxes and a given longitudinal open container, determine an arrangement of all boxes within the container so that the required container 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. Two approaches are investigated to adapt the CLP method to the 3D-SPP. The first approach looks directly at a container of practically infinite length. The second one solves an SPP instance by computing a series of CLP instances with descending container lengths. The best parts of previously best solutions are reused systematically within the second approach that proves to be more successful.The method is tested by means of 800 benchmark instances with up to 1000 boxes. A comparison to other methods from the literature shows the high performance of the 3D-SPP heuristic.