A hybrid improvement heuristic for the one-dimensional bin packing problem
Adriana C. Alvim (alviminf.puc-rio.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.
Entry Submitted: 03/10/2002
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|