Hybrid genetic algorithm and simulated annealing for two-dimensional non-guillotine rectangular packing problems

摘要

In this paper, genetic algorithm (GA) and simulated annealing (SA) with improved bottom left (BL) algorithm were applied to two-dimensional non-guillotine rectangular packing problems. The performance and efficiency of these algorithms on several test problems [Hopper, E., Turton, B.C.H., 2000. An empirical investigation of meta-heuristic and heuristic algorithms for two-dimensional packing problem. European Journal of Operational Research 128 (1), 34-57] were compared. These test problems consist of 17 and 29 individual rectangular pieces to place in main object limited with a size of 200 x 200 units. Both solution approaches were compared, based on the trim losses of the test problems. Also, the influences of the GA parameters (population sizes, mutation rates, crossover techniques) and of the SA parameters (cooling schedules, neighborhood moves, the number of inner loop, different temperature values) on the solution of these problems were examined. For considering all solutions of the test problems, the hybrid GA produces much better results than the hybrid SA.