In this paper, a research on the composition of the nesting algorithm fitness function is carried out by performing various numerical experiments to inspect how it affects the scrap efficiency, allocation characteristics, and time consumption, targeting the nesting results of ship parts. This paper specifically concentrates on a method to minimize the scrap ratio and efficiently use the well-defined remnants of a raw plate after the nesting process for the remnant nesting. Therefore, experiments for various ship parts are carried out with the weighting factor method, one of the multi-objective optimum design methods. Using various weighting factor sets, the nesting results are evaluated in accordance with the above purposes and compared with each set for each ship part groups. Consequently, it is suggested that the nesting algorithm fitness function should be constructed differently depending on the characteristics of the parts and the needs of the users.
원자재에서 제품을 구성하는 부재들을 취재하여 제품을 생산하는 산업 분야인 조선․자동차․항공 및 의류산업에서는 부재들을 원자재에 최적 배치하는 것이 무엇보다 중요하다. 특히, 최근 원자재 가격의 꾸준한 상승으로 인해 원자재 소비를 최소화 하여 비용을 절감하기를 기대하고, Steel cutting 공정시간을 단축하여 시간적 측면의 공정 효율을 높이기 위한 방향으로 산업이 관심을 갖는 가운데, 네스팅 알고리즘에 대한 중요성은 날로 증가되고 있다.
네스팅 알고리즘은 형상표현 기법에 따라 크게 두 분류로 나눌 수 있는데(Sheen, 2012), 첫 번째로 No-fit-polygon(NFP)이 있다(Adamowicz and Albano, 1976). NFP는 Fig. 1과 같이 두 부재가 서로 겹치지 않고 외곽선을 맞대고 있을 수 있는 모든 위치의 조합이라고 할 수 있으며 이 개념을 이용하는 네스팅 방법에서는 임의의 패턴을 직선 선분들로 근사화시킨 다각형 근사법으로 표현하여 사용한다(Kim et al., 2006). NFP를 이용하면 부재 간의 중첩여부 판단 및 중첩을 해소하기 위한 방향과 이동거리의 계산이 가능하다(Ryu and Kim, 2004).
두 번째로 격자 표현법(Pixel representation/Grid algorithm)이 있다(Oliveira and Ferreira, 1993). 격자 표현법은 부재 형상을 격자로 쪼개어 형상의 내부와 경계선에 해당하는 격자와 그렇지 않은 격자로 구분하여 형상을 표현한다. 이 때 격자의 세밀한 정도, 즉 해상도를 어떻게 설정하느냐에 따라 격자형상이 본래의 형상을 얼마만큼 정확히 구현되는지가 결정 된다. 해상도가 높으면 높을수록 격자가 세밀하게 형성하게 되어 부재의 실제 형상에 가깝게 격자 형상을 생성할 수 있으나 격자가 많아지기 때문에 계산에 소요되는 시간 및 비용이 증가하게 된다. 반면, 해상도가 낮을수록 계산에 소요되는 시간은 줄어들지만 격자가 세밀하지 못하므로 부재의 실제 형상과 격자 형상 간에 차이가 발생한다.
두 접근 방법 모두 적합도 함수를 어떻게 설정하느냐에 따라 부재가 배치되는 과정, 배치 결과 및 소요 시간이 민감하게 영향을 받는다. 네스팅 프로세스의 주요 목표는 부재들을 원자재에 배치할 때 서로 겹치지 않으면서 배치 후 남은 스크랩의 면적을 최소화하고, 이 때 스크랩의 형상이 직사각형과 같이 최대한 잘 정의된 형상으로 만들어 추후에 남은 영역을 잔재로 활용할 수 있도록 하는 것이다. 또한 Steel cutting을 할 때, 공정 시간을 최대한 단축할 수 있는 효율적인 N/C코드를 작성하는 것 또한 중요하다. 따라서 적합도 함수는 이러한 목표들을 고려하여 가장 좋은 효율을 갖는 네스팅 결과를 도출할 수 있도록 구성되어야 한다.
본 논문에서는 격자 표현법에 집중하여 이전까지 진행되었던 논문에서 제시한 여러 가지 적합도 함수를 적용하여 각 경우에 따라 부재가 원자재에 어떻게 배치되는지, 그 결과를 비교하고 특히 조선 산업용 부재의 특성에 맞추어 가장 효율적인 배치 결과를 나타내고 계산 비용 절감에 가장 좋은 결과를 갖는 적합도 함수를 제안하고자 한다.
본 연구에서는 격자 표현법을 이용하여 네스팅 알고리즘을 구현하였는데, 조선용 상업 CAD 시스템인 Tribon M3(generic file)를 통해 얻어진 형상 정보로부터 격자 형상을 생성하였다. 이 때 주어지는 기본 선분 형상 정보는 형상의 꼭짓점의
격자 표현법을 이용하여 부재 형상을 표현하는 과정을 Fig. 3에 나타내었다. 형상을 표현하는 첫 번째 단계에서는 Fig. 3의 (a)와 같이 부재와 동일한 폭과 길이를 갖는 사각형을 격자 형상으로 생성한다. 이 때 격자의 초기 데이터는 '2'로 설정이 된다. 두 번째 단계에서는 형성된 격자 형상에서 Fig. 3의 (b)와 같이 부재의 외곽선과 홀의 외곽선에 해당하는 격자를 찾고, 그 격자의 데이터를 '1'로 설정한다. 외곽선의 성분이 직선인 경우에는 Bresenham algorithm (Bresenham, 1965)을 사용하여 격자의 좌표를 계산하고, 호의 경우는 CIRCLE_ARC_GRID algorithm (Burkardt, 2011)을 통해 좌표를 구한다. 이 때, 격자의 데이터와 더불어 각 격자마다 격자의 정보를 나타내는 모드(Mode)를 설정하여 외곽선 중에서도 부재의 외곽선과 홀의 외곽선으로 구분하였다. 이는 다음 단계에서 나머지 격자에 대하여 부재의 외부 및 내부 판단을 쉽게 하는 역할을 한다. 마지막으로 이전 단계에서 형성된 외곽선 격자를 이용하여 나머지 격자들이 각각 부재의 내부와 외부 중 어디에 속하는지를 구분하여 부재의 내부에 해당하는 격자의 데이터를 '1'로 설정하고 부재의 외부 또는 홀의 내부에 해당하는 격자를 '0'으로 설정한다. 이러한 과정을 거쳐 Fig. 3의 (c)처럼 부재가 격자 형상화되어진다. 강재 역시 강재와 동일한 폭과 길이를 갖는 사각형으로 격자 형상화 되고 격자 데이터는 초기 데이터인 '2'로 설정된다. 이렇게 형성된 강재의 격자 형상에 부재의 격자 형상을 배치한다.
부재를 배치하는 순서는 다양한 방법이 있는데, 본 연구에서는 네스팅 전문가들이 흔히 사용하는 방법인 부재 넓이에 따른 내림차순으로 진행하여 면적이 넓은 부재부터 강재에 배치를 한다. 부재 배치 과정을 순서도로 Fig. 4에 나타내었다. 부재 배치를 위한 위치 탐색은 강재의 첫 행, 첫 열부터 이루어지며 좌에서 우 방향으로 조사를 먼저 실시하여 부재가 놓일 수 있는 최소
한편 부재의 회전은 다음과 같이 두 가지 방법으로 실시할 수 있는데, 부재의 본 형상 자체를 회전시켜 매 각도마다 새로운 격자형상을 생성하는 방법(Kang, 1998)과 회전을 하지 않은 부재를 격자 형상화하여 구한 격자들을 회전시키는 방법(Bang, 1990)이 있다. 본 논문에서는 Fig. 5에서와 같이 부재의 본 형상을 회전시켜 회전 시마다 격자 형상을 새로 생성하였으며, 부재의 외접사각형의 중심을 기준으로 회전하였다.
회전된 부재에 대해 격자 형상을 생성하면 음(-)의 좌표 값이 발생하거나 회전 한 후의 격자 좌표들 중 최소
Bang(1990)이 제안한 목적함수는 Fig. 7의 세 가지 항을 이용하여 배치 탐색을 하는데,
여기서
한편 Kang의 학위 논문에서는 격자 표현법으로 네스팅 알고 리즘을 구현하는데 있어서 제안된 적합도 함수로서
한편 Weng and Kuo(2011)에 의해 제안된 네스팅 시스템에서는
본 논문에서는 이미 제안된 적합도 함수들의 항들을 취사선택하여 새로운 조합을 만들고, 다목적 최적화의 일종인 가중치법(Weighting factor method)을 사용하여 각 항의 비중을 달리 함으로써 조선용 부재의 배치에 어떤 결과가 나타나는지를 살펴본다.
기존의 목적함수들을 이용하여 조선용 부재에 적용하여 본 결과, Kang(1998)이 제안한 함수는 스크랩률을 줄이는데 기여를 하며, Weng and Kuo(2011)가 제안한 함수는 잔재를 효율적으로 남기는데 기여를 한다. 이에 따라 여기서 고려한 항목으로는 Kang(1998)에 의해 제안된 식 (7)의
네스팅 결과는 판단하는 기준이 다양하기 때문에 그 기준을 어떻게 설정하느냐에 따라 적합도 함수의 적절성과 효율성 등이 다르게 평가될 수 있다. 본 논문에서는 네스팅의 결과를 평가할 때, 첫 번째로 스크랩률(Scrap ratio)을 비교하고 두 번째로 다른 분야의 네스팅과 차별적인 특징이라고 할 수 있는 잔재의 효용성을 고려한다. 즉, 네스팅 후 강재에 부재를 배치하고 남은 영역의 길이가 많이 확보될수록 좋은데, 이는 이 후 스크랩을 이용하여 부재 배치를 다시 시도할 때 좀 더 효율적으로 사용할 수 있기 때문이다. 따라서 본 논문에서는 부재가 최대한 강재의 좌측 및 하 단에 배치되는 것을 지향하고 있다.
적합도 함수의 효율성을 평가하기 위해 선박의 선미부, 중앙부, 엔진룸의 부재들을 대상으로 네스팅을 실시하였다. 선미부 부재들은 곡 형태의 부재가 많은데 직선의 폴리곤(Polygon) 형태보다 호를 포함하는 부재가 많다. 또한 부재들 간의 크기가 비교적 비슷한 특징을 가지고 있다. 이에 반해 중앙부 부재들은 부재들의 크기가 크고, 비교적 사각형에 가까운 부재들이 많기 때문에 네스팅이 쉽다. 한편 엔진룸은 일반적으로 전체 부재들의 개수가 많고 부재들 간의 크기는 중앙부에 비해 비교적 일관적인 편이다. 그러나 부재들의 형상이 매우 다양하여 네스팅이 가장 어렵다.
첫 번째로 선미부에 대한 네스팅을 실시하였는데, 선미부 부재들을 각각 두 그룹으로 나누어 두 가지 다른 측면에서 적합도 함수에 따른 배치 결과를 비교하였다. 첫 번째 부재 그룹은 총 19개의 부재로 구성되어 있는데 배치 결과 한 판의 강재에 얼마나 많은 부재를 배치하는지 알아보고 그 때 발생하는 스크랩 면적을 비교하였다. 두 번째 부재 그룹은 34개의 부재로 구성되어 있으며 배치 결과를 통해서 발생한 스크랩 형상의
조선용 부재를 배치하기 위한 강재의 사이즈는 가로×세로×두께(Quality) 20m×4m×13t(A Grade)로 고정시켰다. 격자 하나는 가로, 세로 각각 20mm를 나타내도록 설정하였으며, 부재의 최적 배치 위치를 찾기 위하여 부재를 0도에서 360도까지 5도 간격으로 회전시키고 회전시킬 때마다 격자형상을 새로 구하여 회전된 부재의 격자 형상을 대상으로 배치 시도를 하였다. 배치는 면적이 큰 부재부터 내림차순으로 진행하였으며, 부재에 대한 정보는 조선용 상업 CAD 시스템인 Tribon M3에서 취득하여 이용하였다.
가중치 선정을 위하여 가중치를 충분히 다양하게 변경해가며 실험을 수행하고 그 결과를 살펴보았는데, Table. 1은 수치 실험을 진행했던 적합도 함수 중에서 몇 가지 대표적인 케이스들 을 선별하여 가중치를 어떻게 설정하였는지를 나타내었다. Table. 2는 각 케이스마다의 네스팅 결과이다.
[Table 1] Weighting factor sets for each case
Weighting factor sets for each case
[Table 2] Numerical results of nesting process for stern
Numerical results of nesting process for stern
부재 그룹 1의 네스팅 결과를 분석해보면 케이스 3과 4(Fig. 12)의 적합도 함수를 이용하였을 때 19개의 부재를 모두 한 판에 배치하였으며 이에 따라 스크랩이 가장 적게 발생하였으나, 이 외의 케이스들은 한판에 모든 부재들을 배치하지 못하였다.
한편 케이스 4와 5는
부재 그룹 2의 네스팅 결과를 살펴보면 모든 케이스에 대해서 스크랩률이 약 0.555로 비슷하게 나타났으나, 잔재의 효용성을 판단하는 측면에서 케이스 1의 경우 Fig. 14에서처럼 부재들이
케이스 1을 제외한 나머지 케이스들은 모두
여러 가지 적합도 함수를 이용하여 네스팅을 실시한 결과를 두 가지 측면에서 판단해보았을 때, 각각 케이스 2와 케이스 3, 4가 좋은 효율을 보이는 것으로 나타났다. 이 케이스들은 모두
다음은 앞선 두 가지의 네스팅 결과 비교를 통해 좋은 효율을 보이는 케이스를 선택하여 선박의 중앙부 블록의 부재에 대하여 네스팅을 실시한 결과이다. 적용된 케이스는 Table 1의 적합도 함수 중 케이스 2와 4이며, 그 결과는 격자표현법으로 얻은 0과 1을 비트맵화 시켜서 얻은 이미지와 조선용 상업 CAD 시스템으로 연동하여 얻은 이미지로 각각 Fig. 16과 17에 나타내었다. 그림에서 주목할 점은 우선 부재의 홀 안에 다른 부재들의 배치가 잘 이루어진 점과 알고리즘 구현 시 따로 고려하지 않았던 부재들 간의 Pairing, Grouping의 수준이 만족할 만하게 나타난 점이다.
Table 3은 각 케이스 별로 강재 안에 배치된 부재의 수와 스크랩률이다. 그 결과를 살펴보면 케이스 2의 적합도 함수를 이용하여 배치하였을 때, 한 강재 안에 6개의 부재가 더 배치되었다. 앞서 선박의 선미부 부재들을 대상으로 네스팅 한 결과에서는 케이스 4가 더 효율적이었으나, 이 경우에는 케이스 2가 더 효율적임을 알 수 있다. 따라서 배치하려는 부재의 특성 등에 따라 적합도 함수는 다른 효율을 가질 수 있음을 알 수 있다.
[Table 3] Comparison of the nesting results
Comparison of the nesting results
다음은 엔진룸 부재를 케이스 2와 4를 적용하여 네스팅한 결과이다. 26개의 부재를 선별하여 만들어진 부재 그룹을 네스팅 하였는데, 케이스 2를 적용했을 때는 모든 부재를 한 강재 안에 배치를 하였으나(Fig. 18), 케이스 4를 적용하면 2개가 모자란 24개의 부재만이 한 판에 배치가 되었다(Fig. 19). 이 때 스크랩률의 차이는 약 0.03으로 나타났다(Table 4).
[Table 4] Comparison of the nesting results
Comparison of the nesting results
부재의 크기가 비교적 비슷한 부재들로 이루어진 선미부 부재에 대한 네스팅 결과와 중앙부 및 엔진룸의 부재들에 대한 네스팅 결과를 비교해보았을 때, 형상이 비교적 사각형에 가까운 부재들이 많고 부재들 간의 규모의 차이가 많이 나는 중앙부나 엔진룸의 부재들을 네스팅 할 때는 케이스 2가 더 많은 부재를 한강재 안에 배치함으로써 케이스 4에 비해 좋은 효율을 보였으며, 부재들 간의 크기가 비슷한 부재들을 네스팅 할 때에는 케이스 4가 한 강재에 더 많이 배치를 시킴으로 더 좋은 효율을 보였다.
한편 네스팅에 소요되는 계산 시간 비교를 위해 선미부 부재 그룹 1과 엔진룸 부재들을 대상으로 시간을 측정하였다. 본 실험은 Intel(R) Core(TM) i3-2120 CPU @ 3.30GHz의 프로세서와 4.00 GB의 RAM의 시스템에서 수행되었으며, 부재 회전은 0도부터 360도까지 15도 간격으로 실시하였다. Table 5는 케이스 2와 4를 적용하여 네스팅 한 결과와 그 때의 소요시간을 보여준다. 부재 그룹 1의 네스팅 결과와 엔진룸 부재에 대한 결과를 동일 부재에 대해 회전을 5도 간격으로 실시하여 얻은 네스팅 결과인 Table 2, Table 4와 각각 비교해보았을 때, 한 강재 안에 배치된 부재의 개수나 스크랩률 등이 큰 차이가 없음을 알 수 있다.
[Table 5] Nesting results and computing time
Nesting results and computing time
케이스 2와 4에 대한 계산소요 시간을 비교해보면 부재 그룹 1과 엔진룸에 대한 네스팅 결과, 케이스 4를 적용했을 때 시간이 더 소요되었다. 케이스 4의 경우 케이스 2와는 달리
부재그룹 1에 비해 더 많은 부재를 배치하는 엔진룸의 네스팅의 경우, 계산 시간은 덜 소요가 되는데 이는 테스트 할 때 사용한 엔진룸의 부재들의 형상이 부재그룹 1에 비해 회전 단계에서 배치가 불가능한 경우가 많았기 때문이다.
본 연구에서는 최적배치를 위한 네스팅 알고리즘 연구를 실시하였으며, 특히 조선용 부재에 대한 네스팅을 고려하여 효율적인 결과를 얻을 수 있는 적합도 함수의 구성에 대해 알아보았다. 조선용 부재와 자재(잔재 포함)는 형상과 크기가 다양하고 고려해야하는 조건이 복잡한 특징을 가지고 있는 네스팅 문제이다.
기존에 연구 되었던 적합도 함수에서 x축 및
이 과정에서 Kang(1998)에 의해 제안된
선박의 선미부의 두 가지 부재 그룹에 대해 각각 네스팅을 실시하고, 중앙부와 엔진룸의 부재에 대해 네스팅을 실시한 결과, 좋은 결과를 보이는 적합도 함수가 각각 다른 것을 확인함으로서, 고정된 하나의 적합도 함수만을 이용하여 모든 부재를 네스팅하는 것 보다는 부재의 특성 및 사용자의 판단 기준에 따라 적합도 함수를 구성하고 네스팅에 적용시키는 것이 더 적절한 결과를 얻을 수 있을 것이라 기대된다.
현재의 네스팅 알고리즘을 이용한 부재 배치에서는 부재의 면적을 기준으로 내림차순으로 배치를 실시하는데, 추후에는 배치 순서를 SA(Simulated annealing) 등을 이용하여 강재에 스크랩을 덜 발생시키는 최적의 배치 순서를 구하여 네스팅 알고리즘에 적용할 계획이다.