×

AUTOPACK - algorithms for automated container loading. (English) Zbl 1164.60050

The container problem is defined as follows. Given an ordered list of a finite number of boxes, place all the boxes in one container of fixed size. Each box must be placed entirely inside the container and it is required that the boxes are packed in a specified order. The objective is to find a packing with maximal density. The boxes are assumed to have a rectangular form with edges corresponding to their length, width and height. Some of the boxes are rotatable in all directions (around all of the axes), others must be placed right-side-up. All boxes are placed orthogonally to the edges of the container. No other constraints, e.g., weight or stability, are considered in this paper. The authors present a new method for solving the container loading problem. The presented method identifies three types of subproblems and uses tailor-made algorithms to solve each of them separately. The authors present a computational evaluation of the algorithm on a set of fifteen types of benchmark problems and compare the results with those obtained from the wall building and space partitioning heuristics. The results show that in terms of packing density, the proposed algorithm performs better for all these types of benchmark problems.

MSC:

60H15 Stochastic partial differential equations (aspects of stochastic analysis)
78M50 Optimization problems in optics and electromagnetic theory

Software:

AUTOPACK
PDFBibTeX XMLCite