Guided local search for the three-dimensional bin packing problem: DIKU-rapport 99/13

Research output: Book/ReportCommissioned reportpeer-review


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 (GLS). 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
using GLS. 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, and the results are compared with those obtained by heuristics and
exact methods from the literature.
Original languageEnglish
Place of PublicationCopenhagen
PublisherKøbenhavns Universitet - Datalogisk Institut
Number of pages28
Publication statusPublished - 1999

Publication series

NameDIKU rapport


Dive into the research topics of 'Guided local search for the three-dimensional bin packing problem: DIKU-rapport 99/13'. Together they form a unique fingerprint.

Cite this