Hybrid Genetic Algorithm with Simulated Annealing based on Best-Fit Strategy for Rectangular Packing Problem

摘要

In this paper we address a rectangular packing problem (RPP), which is one of the most difficult NP-complete problems. Borrowing from the respective advantages of the two algorithms, a hybrid of genetic algorithm (GA) and simulated annealing (SA) is developed to solve the RPP. Firstly, we adopt and improve Burke’s best-fit (BF) placement strategy, which is not restricted to the first shape but may search the list for better candidate shapes for placement. Secondly, we propose a new crossover operator, named Improved Precedence Operation Crossover (IPOX), which can preserve the valuable characteristics of the previous generation. At last, using a new temperature and iterations strategy and Boltzmann-type operator, we propose SA to re-intensify search from the promising solutions. The computational results validate the quality and the effectiveness of hybrid algorithm.