Genetic Algorithm Coding Methods for Leather Nesting

摘要

The problem of placing a number of specific shapes in order to minimise waste is commonly encountered in the sheet metal, clothing and shoe-making industries. The paper presents genetic algorithm coding methodologies for the leather nesting problem which involves cutting shoe upper components from hides so as to maximise material utilisation. Algorithmic methods for computer-aided nesting can be either packing or connectivity driven. The paper discusses approaches to how both types of method can be realised using a local placement strategy whereby one shape at a time is placed on the surface. In each case the underlying coding method is based on the use of the no-fit polygon (NFP) that allows the genetic algorithm to evolve non-overlapping configurations. The packing approach requires that a local space utilisation measure is developed. The connectivity approach is based on an adaptive graph method. Coding techniques for dealing with some of the more intractable aspects of the leather nesting problem such as directionality constraints and surface grading quality constraints are also discussed. The benefits and drawbacks of the two approaches are presented.