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 (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.
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 language | English |
|---|---|
| Place of Publication | Copenhagen |
| Publisher | Københavns Universitet - Datalogisk Institut |
| Number of pages | 28 |
| DOIs | |
| Publication status | Published - 1999 |
Publication series
| Name | DIKU rapport |
|---|---|
| No. | 13 |
| Volume | 99 |