A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem

 J. F. Gonçalves and M. G. C. Resende

J. of Combinatorial Optimization, vol. 22, pp. 180-201, 2011.


This paper addresses a constrained two-dimensional (2D), non-guillotine restricted, packing problem, where a fixed set of small rectangles has to be placed into a larger stock rectangle so as to maximize the value of the rectangles packed. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We propose also a new fitness function to drive the optimization. The approach is tested on a set of instances taken from the literature and compared with other approaches. The experimental results validate the quality of the solutions and the effctiveness of the proposed algorithm.

PDF file of full paper
Go back
Mauricio G.C. Resende's Home Page
Last modified: 11 July 2011

Copyright Notice