A new design of genetic algorithm for bin packing

Abstract

In this paper, a new design of genetic algorithm (GA) is proposed for solving the one-dimensional bin packing problem, which is to pack a given set of items into the minimum number of bins. GA should be designed in such a way that offspring inherit important factors of parents. Such a factor in this problem is the combination of items in a bin. Thus, our GA lays emphasis on the combination of items. Furthermore, heuristic methods, which are effective for the bin packing problem, are introduced into our GA for obtaining a better solution. The effectiveness of our GA is investigated through computational results for benchmark instances. It is confirmed from the computational results that our GA outperforms a tabu search based method and a variable neighborhood search from the viewpoint of accuracy of solution obtained.