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.
Citation
Research report, Catholic University of Rio de Janeiro, Department of Computer Science, Rio de Janeiro (Brazil), revised vesion, July 2003.
Article
View A hybrid improvement heuristic for the one-dimensional bin packing problem