Genetic algorithms applied to leather lay plan material utilization

Abstract

This paper presents a genetic algorithm method for the leather-nesting problem that involves cutting shoe upper components from hides so as to maximize material utilization. A significant proportion of the manufacturing cost of a pair of shoes is invested in the natural raw material, and so the efficient utilization of this resource is of prime importance. Consequently, the part nesting and cutting process is one of the most important stages in the manufacture of leather shoes. The genetic algorithm method presented for leather lay-planning is capable of handling some of the more intractable aspects of the problem, namely multiple non-convex shapes, irregularly shaped hides, directionality constraints and surface grading quality issues. The underlying encoding method is based on the use of the no-fit polygon (NFP), lay angles and directionality angle constraints. The NFP allows the genetic algorithm to evolve non-overlapping configurations. Lay-plan results are presented using standard shoe component shapes and scanned hide input data conforming to a grading scale commonly used in shoemaking.