J. Ocean Eng. Technol. Search


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

A Study on the Irregular Nesting Problem Using Genetic Algorithm and No Fit Polygon Methodology
유전 알고리즘과 No Fit Polygon법을 이용한 임의 형상 부재 최적배치 연구
부산산업학교,부경대학교 조선해양시스템공학과
© 2004 The Korean Society of Ocean Engineers     Open access / Under a Creative Commons License
Keywords: Nesting Algorithm, Genetic Algorithm, No Fit Polygon, Non-convex Polygon, Travelling Salesman Problem
핵심용어: 네스팅 알고리즘, 유전 알고리즘, 노 핏 폴리곤, 비볼록 다각형, 순회 판매원 문제
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.


Browse all articles >

Editorial Office
President Office BD Rm. 1302, 13 Jungang-daero 180beon-gil, Dong-gu, Busan 48821, Republic of Korea
Tel: +82-51-759-0656    Fax: +82-51-759-0656    E-mail: ksoehj@ksoe.or.kr                

Copyright © 2023 by The Korean Society of Ocean Engineers.

Developed in M2PI

Close layer
prev next