Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K.A. Dowsland and W.B. Dowsland, “Solution approaches to irregular nesting problems,” European Journal of Operations Research Elsevier, vol. 84, pp. 506–521, 1995.
T. Anand, S. McCord, C. Sharma, and R. Balachander, “An integrated machine vision based system for solving the non-convex cutting stock problem using genetic algorithms,” Journal of Manufacturing Systems, vol. 18, no. 6, pp. 396–415, 1999.
C. Bounsaythip, S. Maouche, and M. Neus, “Evolutionary search techniques: Application to automated lay-planning optimisation problem,” IEEE international conference on Systems, Manufacturing and Cybernetics (SMC), Vancouver, Canada, 1995, vol. 5, pp. 4497–4503.
A. Kahng, “Classical Floorplanning harmful?” in International Symposium on Physical Design, Proceeding ACM/IEEE, 2000, pp. 207–213.
P. Clay and A.J. Crispin, “Automated lay-planning in leather manufacturing,” in 17th National Conference on Manufacturing Research, Cardiff, 2001, pp. 257–262, ISBN 1-86058-325-3.
M. Adamowicz and A. Albano, “Nesting two-dimensional shapes in rectangular modules,” Computer-Aided Design, vol. 8, no. 1, pp. 27–33, 1976.
E. Burke and G. Kendall, “Evaluation of two-dimensional bin packing using the no fit polygon,” in Computers and Industrial Engineering Conference, Melbourne, Australia, 1999.
R. Cunninghame-Green, “Geometry, shoemaking and the milk tray problem,” New Scientist, vol. 12, 1677, pp. 50–53 1989.
P.K. Ghosh, “A unified computational framework for Minkowski operations,” Computer and Graphics, vol. 17, no. 4, pp. 119–144 1993.
J.A. Bennell, K.A. Dowsland, and W.B. Dowsland, “The irregular cutting-stock problem—a new procedure for deriving the no-fit polygon,” Computers and Operations Research, vol. 28, pp. 271–287, 2000.
A.J. Crispin, P. Clay, G.E. Taylor, R. Hackney, T. Bayes, and D. Reedman, “Genetic Algorithms applied to material utilisation in leather shoe manufacturing,” in 18th National Conference on Manufacturing Research, Leeds, 2002, pp. 267–272. ISBN 1-86058-378-4.
J. Heistermann and T. Lengauer, “The nesting problem in the leather manufacturing industry,” Annals of Operations Research, vol. 57, pp. 147–173, 1995.
D.E. Goldberg, Genetic Algorithms in Search, Optimisation and Machine Learning, Addison Wesley, Longman Inc. 1989, ISBN 0-020-15767-5.
M. Mitchell, An Introduction to Genetic Algorithms, Massachusetts Institute of Technology Press, 1996, ISBN 0-262-13316-4.
P. Clay, A.J. Crispin, and S. Crossley, “Comparative analysis of search methods as applied to shearographic fringe modelling,” in Proceeding of 13th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, New Orleans, June 2000, pp. 99–108.
B. Brassard and P. Bratley, Fundamentals of Algorithmics, Prentice-Hall: New Jersey, 1996, ISBN 0-13-335068-1.
J. Gross and J. Yellen, Graph Theory and Its Applications, CRC Press: Florida, 1998, ISBN 0-8493-3982-0.
H. Mühlenbein and D. Schlierkamp-Voosen, “Predictive Models for the Breeder Genetic Algorithm,” Evolutionary Computation, vol. 1, no. 1, pp. 25–49, 1993.
A.J. Crispin, P. Clay, G.E. Taylor, R. Hackney, T. Bayes, and D. Reedman, “Genetic algorithm optimisation of part placement using a connection based coding method,” in 15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, Cairns, Australia, 2002.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Crispin, A., Clay, P., Taylor, G. et al. Genetic Algorithm Coding Methods for Leather Nesting. Appl Intell 23, 9–20 (2005). https://doi.org/10.1007/s10489-005-2368-2
Issue Date:
DOI: https://doi.org/10.1007/s10489-005-2368-2