모형선 제작을 위한 최적 네스팅 및 절단 경로 생성

Abstract

2차원 네스팅(Nesting)은 조선, 자동차, 의류산업 등에서 자주 사용되는 방법으로, 배치를 효과적으로 함으로써 자원과 재료의 낭비를 최소화 할 수 있으며, 배치 자동화를 통해 공수를 절감하고 생산성을 높일 수 있다. 현재 모형선 제작 과정에서는 피스 배치를 수작업으로 진행하고 있기 때문에 작업 시간이 오래 걸리며 재료의 낭비를 최소로 하는 최적 배치를 찾기 어려운 점이 있다. 이러한 문제를 해결하기 위하여 본 연구에서는 모형선 제작에 필요한 자재의 남김율을 최소화 하는 최적 배치 자동화 방법을 제안한다. 본 연구의 목표는 원자재 목판 안에 여러 개의 피스 형상들이 중첩하지 않고 자재의 남김율을 최소화하며 최대의 피스 수로 최적의 배치를 하는 것이다. 모형선 피스의 특성을 고려하여 다중 판 배치에 대한 네스팅 알고리즘을 구현하였다. 피스를 원자재 판 위에 최적으로 배치하는 방법을 다음과 같이 제시한다. 형상 정보를 표현하는 방법에는 격자 표현법, Non-Fit-Polygon, Phi-function 등의 방법이 있다. 본 연구에서는 격자 표현법을 선택하였다. 격자 표현 방법의 경우 형상을 격자 형태로 간단히 표현할 수 있으며, 다른 방법들에 비해 형상 간 중첩 여부 판단이 쉽다. 그리고 음함수의 특성을 활용해 격자에 피스의 외형선을 표현하는 방법을 제시하였다. 형상 내부의 경우 다차원 배열에서 각 격자를 방문하는 알고리즘인 Breadth-first Search 기법을 사용하여 형상의 내부와 외부를 정의하였다. 형상 회전의 경우 전역 좌표계를 기준으로 회전시켰으며 좌표 값이 음수로 표현되었을 때 그 값 만큼 x축 또는 y축으로 평행이동을 시켜 좌표 값이 최소 좌표인 (0,0) 이상을 가지도록 하였다. 배치 알고리즘의 경우 두 가지 목적 함수를 구성하여 배치 결과를 비교하였다. 배치 순서와 피스의 각도에 따라서 배치 결과가 달라질 수 있는데 유전 알고리즘을 사용해 자재의 버림율이 최소 값일 때의 배치 순서를 결정하였을 뿐만 아니라 해당 순서일 때 피스의 최적의 회전 각도도 도출하였다. 본 연구에서 제시하는 절단 경로 생성 알고리즘은 공구의 절단 경로를 최소화하기 위해서 원점에서 가장 가까운 위치의 피스부터 절단된 피스에서 가까운 피스를 선택하는 방식으로 진행된다. 폴리라인(Polyline)에 대한 절단 경로를 생성하기 위해 피스들이 지니고 있는 선분과 호의 시작점과 끝점을 이용하여 점 간 최소 이동거리를 계산하는 알고리즘도 적용하였다. 이는 메타 휴리스틱 알고리즘에 비하여 실행시간이 짧으며 합리적인 경로를 제시할 수 있다.