A Study on the Irregular Nesting Problem Using Genetic Algorithm and No Fit Polygon Methodology

J. Ocean Eng. Technol. 2004;18(2):77-82.

유전 알고리즘과 No Fit Polygon법을 이용한 임의 형상 부재 최적배치 연구

유병항,김동준

부산산업학교,부경대학교 조선해양시스템공학과

Keywords: Nesting Algorithm, Genetic Algorithm, No Fit Polygon, Non-convex Polygon, Travelling Salesman Problem

핵심용어: 네스팅 알고리즘, 유전 알고리즘, 노 핏 폴리곤, 비볼록 다각형, 순회 판매원 문제

Abstract

The purpose of this study is to develop a nesting algorithm, using a genetic algorithm to optimize nesting order, and modified No Fit Polygon(NFP) methodology to place parts with the order generated from the previous genetic algorithm. Various genetic algorithm techniques, which have thus far been applied to the Travelling Salesman Problem, were tested. The partially mapped crossover method, the inversion method for mutation, the elitist strategy, and the linear scaling method of fitness value were selected to optimize the nesting order. A modified NFP methodology, with improved searching capability for non-convex polygon, was applied repeatedly to the placement of parts according to the order generated from previous genetic algorithm. Modified NFP, combined with the genetic algorithms that have been proven in TSP, were applied to the nesting problem. For two example cases, the combined nesting algorithm, proposed in this study, shows better results than that from previous studies.