Article ID: | iaor2007350 |
Country: | United States |
Volume: | 15 |
Issue: | 3 |
Start Page Number: | 267 |
End Page Number: | 283 |
Publication Date: | Jun 2003 |
Journal: | INFORMS Journal On Computing |
Authors: | Pisinger David, Zachariasen Martin, Faroe Oluf |
Keywords: | packing |
The three-dimensional bin-packing problem is the problem of orthogonally packing a set of boxes into a minimum number of three-dimensional bins. In this paper we present a heuristic algorithm based on guided local search. Starting with an upper bound on the number of bins obtained by a greedy heuristic, the presented algorithm iteratively decreases the number of bins, each time searching for a feasible packing of the boxes. The process terminates when a given time limit has been reached or the upper bound matches a precomputed lower bound. The algorithm can also be applied to two-dimensional bin-packing problems by having a constant depth for all boxes and bins. Computational experiments are reported for two- and three-dimensional instances with up to 200 boxes, showing that the algorithm on average finds better solutions than do heuristics from the literature.