Guided Local Search for the Three-Dimensional Bin Packing Problem

Research output: Contribution to journalArticlepeer-review

168 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)267-283
Number of pages17
JournalINFORMS Journal on Computing
Volume15
Issue number3
DOIs
Publication statusPublished - 2003

Fingerprint

Dive into the research topics of 'Guided Local Search for the Three-Dimensional Bin Packing Problem'. Together they form a unique fingerprint.

Cite this