Applying a tabu search approach for solving the two-dimensional bin packing problem

The 2DBPP (Two-Dimensional Bin Packing Problem) is a problem of packing each item into a bin so that no two items overlap and the number of required bins is minimized under the set of rectangular items which may not be rotated and an unlimited number of identical rectangular bins. The 2DBPP is strongly NP-hard and finds many practical applications in industry. In this paper we discuss a tabu search approach which includes tabu list, intensifying and diversification strategies. The HNFDH (Hybrid Next Fit Decreasing Height) algorithm is used as an internal algorithm. We find that use of the proper parameter and function such as maximum number of tabu list and space utilization function yields a good solution in a reduced time. We present a tabu search algorithm and its performance through extensive computational experiments.