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

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

0.00 Avg rating0 Votes
Article ID: iaor20043740
Country: Netherlands
Volume: 10
Issue: 2
Start Page Number: 205
End Page Number: 229
Publication Date: Mar 2004
Journal: Journal of Heuristics
Authors: , , ,
Keywords: heuristics
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 a very wide range of benchmark instances, illustrating the robustness of the algorithm. The hybrid improvement procedure compares favourably with all other heuristics in the literature. It improved the best known solutions for many of the benchmark instances and found the largest number of optimal solutions with respect to the other available approximate algorithms.

Reviews

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