Employing Subgroup Evolution for Irregular-Shape Nesting

Abstract

This paper introduces a new method to solve the irregular-shape, full-rotation nesting problem by a genetic algorithm. Layout patterns are evolved in hierarchical subgroups to facilitate the search for an optimal solution in such a complex solution space. The genotype used in the genetic algorithm contains both the sequence and rotation for each shape, requiring new genetic operators to manipulate a multi-type genetic representation. A lower-left placement heuristic coupled with matrix encoding of the shapes and plate prevents overlap and constrains the solution space to valid solutions. This new method is able to efficiently search the solution space for large problems involving complex shapes with 360 degrees of freedom. The algorithm generates better solutions than previously published evolutionary methods.

Department(s)

Engineering Management and Systems Engineering

Keywords and Phrases

Evolutionary Computing; Gentic Algorithms; Geometric Modeling; Nesting; Optimization; Stock-Cutting

International Standard Serial Number (ISSN)

0956-5515

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2004 Springer Verlag, All rights reserved.

Publication Date

01 Apr 2004

Share

 
COinS