A new hybrid local search algorithm on Bin Packing problem

Bin Packing (BP) is an NP-hard combinatorial optimization problem. Sophisticated algorithms are needed for solving large instances of the problem. A hybrid framework that includes a Ruin and Recreate (RR) procedure and an acceptance criterion similar to the Metropolis Criterion, is proposed for the problem in this study. Ruin and Recreate is used to create new individuals in the search process and the acceptance mechanism is used for balancing the exploration and exploitation of the search space. Also hill climbers are integrated into the framework for fine-tuning. Furthermore, the algorithm is run on a population of individuals and a certain amount of crossover operation is utilized on the population in order to benefit from the reproduction process that takes place in Genetic Algorithms (GAs). The constructed algorithm is applied on frequently used data sets in the literature and the results are compared with other state of the art algorithms.