Guided local search for the three-dimensional bin-packing problem

Guided local search for the three-dimensional bin-packing problem

0.00 Avg rating0 Votes
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: , ,
Keywords: packing
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.

Reviews

Required fields are marked *. Your email address will not be published.