A hybrid improvement heuristic for the one-dimensional bin packing problem

Adriana C. Alvim (alviminf.puc-rio.br)
Celso Ribeiro (Fred.Glovercolorado.edu)
Fred Glover (Fred.Glovercolorado.edu)
Dario J. Aloise (dariodigi.com.br)

Abstract: We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several features: the use of lower bounding strategies; the generation of initial solutions by reference to the dual min-max problem; the use of load redistribution based on dominance, differencing, and unbalancing; and the inclusion of an improvement process utilizing tabu search. Encouraging results have been obtained for benchmark instances composed by eight different classes of problems, showing the robustness of the algorithm. Optimal solutions were obtained for every instance for which the optimal solution is known. We improved the best known solution for many of the benchmark instances. Our algorithm is the only one that has succeeded in finding the best known results for all instances.

Keywords: Bin packing, metaheuristics, local search, tabu search

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Meta Heuristics )

Citation: Research report, Catholic University of Rio de Janeiro, Department of Computer Science, Rio de Janeiro (Brazil), revised vesion, July 2003.

Download: [Postscript]

Entry Submitted: 03/10/2002
Entry Accepted: 03/11/2002
Entry Last Modified: 10/12/2003

Modify/Update this entry