Guided Local Search for the Three-Dimensional Bin-Packing Problem

Oluf Faroe, David Pisinger, Martin Zachariasen

INFORMS Journal on Computing · 2003 · Volume 15 · Issue 3

Abstract

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.

Keywords

Analysis of Algorithms, Suboptimal Algorithms, Cutting and Packing

Enable JavaScript for citation tools and additional paper interactions.