A General Purpose Algorithm for Three-Dimensional Packing

摘要

We present a fast and efficient heuristic algorithm for solving a large class of three-dimensional packing problems with the objective of maximizing the average volumetric utilization of containers that might be of different dimensions. The algorithm is a tree-search algorithm that implicitly explores the solution space. The algorithm relies on the fact that, in practice, (ⅰ) the number of different types of objects to pack is limited and known in advance, and (ⅱ) the number of occurrences of those objects is sufficiently high to permit use of a pattern approach to solve, at least partially, the problem. Each node of the search tree is solved using an extension of a pallet-loading heuristic developed by Morabito and Morales to generate the patterns and of a container-loading heuristic developed by Pisinger to treat the objects not packed by the pattern approach. We report on our extensive computations on a new large library of instances derived from real world applications.