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

José F. Gonçalves(jfgoncalfep.up.pt)
Mauricio G. C. Resende(mgcrresearch.att.com)

Abstract: This paper addresses a constrained two-dimensional (2D), non-guillotine restricted, packing problem, where a fixed set of small rectangles has to be packed 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 effectiveness of the proposed algorithm.

Keywords: Packing, cutting, two-dimensional packing, two-dimensional cutting, non-guillotine cutting, genetic algorithm.

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Global Optimization (Stochastic Approaches )

Category 3: Applications -- OR and Management Sciences (Production and Logistics )

Citation: AT&T Labs Research Technical Report TD-7M7QJG, AT&T Labs Research, Florham Park, NJ 07932, December 10, 2008.

Download: [PDF]

Entry Submitted: 01/07/2009
Entry Accepted: 01/08/2009
Entry Last Modified: 01/07/2009

Modify/Update this entry