수치 실험을 통한 조선 강판 전용 Nesting Algorithm의 적합도 함수의 결정

Determination of Nesting Algorithm Fitness Function through Various Numerical Experiments

Article information

J. Ocean Eng. Technol. 2013;27(5):28-35
이혜빈*, 유원선**
Corresponding author Won-Sun Ruy: +82-042-821-6623, wsruy@cnu.ac.kr
Received 2013 June 14; Accepted 2013 October 10; Revised 2013 September 05.

Trans Abstract

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.

1. 서 론

원자재에서 제품을 구성하는 부재들을 취재하여 제품을 생산하는 산업 분야인 조선․자동차․항공 및 의류산업에서는 부재들을 원자재에 최적 배치하는 것이 무엇보다 중요하다. 특히, 최근 원자재 가격의 꾸준한 상승으로 인해 원자재 소비를 최소화 하여 비용을 절감하기를 기대하고, Steel cutting 공정시간을 단축하여 시간적 측면의 공정 효율을 높이기 위한 방향으로 산업이 관심을 갖는 가운데, 네스팅 알고리즘에 대한 중요성은 날로 증가되고 있다.

네스팅 알고리즘은 형상표현 기법에 따라 크게 두 분류로 나눌 수 있는데(Sheen, 2012), 첫 번째로 No-fit-polygon(NFP)이 있다(Adamowicz and Albano, 1976). NFP는 Fig. 1과 같이 두 부재가 서로 겹치지 않고 외곽선을 맞대고 있을 수 있는 모든 위치의 조합이라고 할 수 있으며 이 개념을 이용하는 네스팅 방법에서는 임의의 패턴을 직선 선분들로 근사화시킨 다각형 근사법으로 표현하여 사용한다(Kim et al., 2006). NFP를 이용하면 부재 간의 중첩여부 판단 및 중첩을 해소하기 위한 방향과 이동거리의 계산이 가능하다(Ryu and Kim, 2004).

Fig. 1

No-Fit-Polygon (Burke et al., 2007)

두 번째로 격자 표현법(Pixel representation/Grid algorithm)이 있다(Oliveira and Ferreira, 1993). 격자 표현법은 부재 형상을 격자로 쪼개어 형상의 내부와 경계선에 해당하는 격자와 그렇지 않은 격자로 구분하여 형상을 표현한다. 이 때 격자의 세밀한 정도, 즉 해상도를 어떻게 설정하느냐에 따라 격자형상이 본래의 형상을 얼마만큼 정확히 구현되는지가 결정 된다. 해상도가 높으면 높을수록 격자가 세밀하게 형성하게 되어 부재의 실제 형상에 가깝게 격자 형상을 생성할 수 있으나 격자가 많아지기 때문에 계산에 소요되는 시간 및 비용이 증가하게 된다. 반면, 해상도가 낮을수록 계산에 소요되는 시간은 줄어들지만 격자가 세밀하지 못하므로 부재의 실제 형상과 격자 형상 간에 차이가 발생한다.

두 접근 방법 모두 적합도 함수를 어떻게 설정하느냐에 따라 부재가 배치되는 과정, 배치 결과 및 소요 시간이 민감하게 영향을 받는다. 네스팅 프로세스의 주요 목표는 부재들을 원자재에 배치할 때 서로 겹치지 않으면서 배치 후 남은 스크랩의 면적을 최소화하고, 이 때 스크랩의 형상이 직사각형과 같이 최대한 잘 정의된 형상으로 만들어 추후에 남은 영역을 잔재로 활용할 수 있도록 하는 것이다. 또한 Steel cutting을 할 때, 공정 시간을 최대한 단축할 수 있는 효율적인 N/C코드를 작성하는 것 또한 중요하다. 따라서 적합도 함수는 이러한 목표들을 고려하여 가장 좋은 효율을 갖는 네스팅 결과를 도출할 수 있도록 구성되어야 한다.

본 논문에서는 격자 표현법에 집중하여 이전까지 진행되었던 논문에서 제시한 여러 가지 적합도 함수를 적용하여 각 경우에 따라 부재가 원자재에 어떻게 배치되는지, 그 결과를 비교하고 특히 조선 산업용 부재의 특성에 맞추어 가장 효율적인 배치 결과를 나타내고 계산 비용 절감에 가장 좋은 결과를 갖는 적합도 함수를 제안하고자 한다.

2. 격자 형상화

본 연구에서는 격자 표현법을 이용하여 네스팅 알고리즘을 구현하였는데, 조선용 상업 CAD 시스템인 Tribon M3(generic file)를 통해 얻어진 형상 정보로부터 격자 형상을 생성하였다. 이 때 주어지는 기본 선분 형상 정보는 형상의 꼭짓점의 x,y좌표가 있으며, 형상을 이루는 선분이 호(Arc)인 경우 Amplitude 또한 주어진다(Fig. 2).

Fig. 2

Geometric segment data from CAD system (arc)

격자 표현법을 이용하여 부재 형상을 표현하는 과정을 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. 3

Grid representation process for a bracket-type part

부재를 배치하는 순서는 다양한 방법이 있는데, 본 연구에서는 네스팅 전문가들이 흔히 사용하는 방법인 부재 넓이에 따른 내림차순으로 진행하여 면적이 넓은 부재부터 강재에 배치를 한다. 부재 배치 과정을 순서도로 Fig. 4에 나타내었다. 부재 배치를 위한 위치 탐색은 강재의 첫 행, 첫 열부터 이루어지며 좌에서 우 방향으로 조사를 먼저 실시하여 부재가 놓일 수 있는 최소 x좌표를 갖는 격자에 배치를 시도하고 적합도 함수를 계산한다. 한행에 대한 탐색이 끝나면 다음 행으로 넘어가 다시 열 방향으로 배치 위치 탐색을 실시한다. 이와 같이 첫 행부터 마지막 행까지 탐색을 마치면 그 중에 가장 작은 적합도 함수의 결과를 갖는 위치에 부재가 최종적으로 배치된다. 부재가 배치를 시도할 때, 부재의 격자 데이터와 강재의 격자 데이터를 합하여 배치가 가능한지 확인하는데 부재의 내부와 경계선에 해당하는 격자가 위치한 강재의 격자는 '3'이 되고, 부재의 외부에 해당하는 격자가 위치한 강재의 격자는 초기 데이터 '2'를 유지한다. 이 과정에서 강재의 격자 데이터가 '4'가 되면 이전 과정에서 부재가 배치되어 격자 데이터가 '3'으로 설정되어 있는 격자에 다시 배치를 하려는 것이기 때문에 겹침이 발생한 것으로 판단하여 현재 배치 위치에 대한 탐색을 종료하고 배치가 가능한 다음 위치를 탐색한다. 이러한 과정을 부재를 회전시킬 때마다 반복하여 각 회전 각도에 대한 배치 위치를 찾고 적합도 함수를 계산하여 회전이 종료되면 회전 각도마다의 적합도 함수 결과를 비교하여 가장 좋은 효율을 보이는 회전 각도로 부재를 회전시키고, 그 각도에 대한 최적의 위치에 부재를 최종 배치시키고 다음 부재에 대한 배치 위치 탐색을 시작한다. 이와 같이 모든 부재를 배치하면 네스팅이 종료된다.

Fig. 4

Flow chart of searching the allocation position

한편 부재의 회전은 다음과 같이 두 가지 방법으로 실시할 수 있는데, 부재의 본 형상 자체를 회전시켜 매 각도마다 새로운 격자형상을 생성하는 방법(Kang, 1998)과 회전을 하지 않은 부재를 격자 형상화하여 구한 격자들을 회전시키는 방법(Bang, 1990)이 있다. 본 논문에서는 Fig. 5에서와 같이 부재의 본 형상을 회전시켜 회전 시마다 격자 형상을 새로 생성하였으며, 부재의 외접사각형의 중심을 기준으로 회전하였다.

Fig. 5

Rotation of a part

회전된 부재에 대해 격자 형상을 생성하면 음(-)의 좌표 값이 발생하거나 회전 한 후의 격자 좌표들 중 최소 x와 최소 y가 각각 0이 아닌 경우가 생기는데, 이 때 발생하는 에러를 방지하고 메모리의 낭비를 최소화하기 위해 최소 x와 최소 y가 모두 0이 되도록 하는 보정 값을 적용한다(Fig. 6).

Fig. 6

Process of translating a part

3. 적합도 함수

3.1 관련 연구

Bang(1990)이 제안한 목적함수는 Fig. 7의 세 가지 항을 이용하여 배치 탐색을 하는데, Rectangular Area는 Shape 1과 2를 포함하는 외접사각형의 면적이며, X - Enclosure Area는 Shape 1과 2를 포함하는 y방향 경계의 합, Y - Enclosure Areax 방향 경계의 합을 말한다. 이 세 가지의 면적이 중요한 파라미터가 되어 다음 식 (2)에서 (6)까지와 같이 적합도 함수의 다섯 개의 항을 구성한다.

Fig. 7

Rectangular Area(left), X - Enclosure Area(middle), Y - Enclosure Area(right) (Bang, 1990)

여기서 A는 이미 배치되어 고정되어 있는 부재의 면적이며, A′은 배치가 진행 중인 부재의 면적이다.

한편 Kang의 학위 논문에서는 격자 표현법으로 네스팅 알고 리즘을 구현하는데 있어서 제안된 적합도 함수로서 x, yxy 방향으로 스크랩(Scrap)에 해당하는 격자의 수를 세어 계산한다(Kang, 1998).

fx는 후보부재가 최대한 원판의 좌측에 배치되도록 기여하는 항이며, 후보부재가 배치된 행에서 x방향의 스크랩 면적을 의미한다. fy는 후보부재가 원판의 아래쪽에 배치되도록 하는 항이며, 후보부재가 배치된 열에서 y방향의 스크랩 면적을 의미한다. fxy는 부재들이 배치되어 가는 형태가 직사각형을 이루도록 하며 후보부재가 배치된 영역 안의 스크랩 면적을 의미한다. Fig. 8은 부재의 배치에 따라 각 항이 고려하는 영역(파란 영역)이 나타내어져 있다. fx는 배치된 부재가 차지하는 행에서 생기는 스크랩에 해당하는 격자를, fy는 배치된 부재가 차지하는 열에서 생기는 스크랩에 해당하는 격자를, fxy는 원점에서 배치된 부재를 포함하는 사각형 내의 스크랩에 해당하는 격자를 각각 세어 수치로 나타낸다.

Fig. 8

fx(left-top), fy(right-top), fxy(bottom

한편 Weng and Kuo(2011)에 의해 제안된 네스팅 시스템에서는 Usage LengthUsage Density의 개념을 도입하여 부재를 배치할 최적의 위치를 찾는다. 이 때 Usage Length는 강재의 너비(Lt )와 현재 배치 중인 부재를 포함하는 영역의 너비(Lu)의 비로 정의된다. Usage Density는 현재 배치 중인 부재를 포함하는 영역의 너비(Lu)와 강재의 폭(H)을 갖는 외접사각형 내에 실제 부재가 배치된 영역의 비로 정의 된다. 각각의 파라미터들은 Fig. 9에 나타나 있다.

Fig. 9

Parameters of fitness function(Weng and Kuo, 2011)

3.2 적합도 함수

본 논문에서는 이미 제안된 적합도 함수들의 항들을 취사선택하여 새로운 조합을 만들고, 다목적 최적화의 일종인 가중치법(Weighting factor method)을 사용하여 각 항의 비중을 달리 함으로써 조선용 부재의 배치에 어떤 결과가 나타나는지를 살펴본다.

기존의 목적함수들을 이용하여 조선용 부재에 적용하여 본 결과, Kang(1998)이 제안한 함수는 스크랩률을 줄이는데 기여를 하며, Weng and Kuo(2011)가 제안한 함수는 잔재를 효율적으로 남기는데 기여를 한다. 이에 따라 여기서 고려한 항목으로는 Kang(1998)에 의해 제안된 식 (7)의 fx, fy, fxyWeng and Kuo(2011)에 의해 제안된 Usage Length(식 (8)), Usang Density(식 (9)) 등에 주목하였다. fx의 경우, 판의 첫 열부터의 x축 방향으로 스크랩을 고려하게 되면 Fig. 10에서처럼 부재 A의 배치 결과에 영향을 받아 다음 배치되는 부재들이 배치 위치를 선정할 때 x방향의 스크랩이 덜 발생하는 위치를 선택하기 위해 사각형 영역 안에 보이는 바와 같이 강재의 하단에서 약간 떨어진 곳에 배치될 가능성이 있다. 이러한 영향을 줄이고자 본 적합도 함수에서는 fxFig. 11(b)와 같이 현재 배치 중인 후보부재의 외접 사각형 내에서의 x축 방향 스크랩만을 고려하도록 변경하였다. Fig. 11(a)에서 빗금 친 부분의 스크랩 면적이 식 (7)의 fx를 이용하였을 때의 스크랩 면적이고, (b)의 빗금 친 부분이 본 논문에서 사용한 fx를 이용하여 부재의 외접 사각형 내의 스크랩을 나타낸 모습이다.

Fig. 10

Problem caused by fx

Fig. 11

Comparison of scrap ratio depending on fx

Usage Density의 경우, 조사영역은 그대로 유지하되 조사영역 내에 부재가 위치한 면적을 계산하는 본래의 Usage Density가 아니라 스크랩 면적을 조사하도록 수정하였다. Usage LengthUsage Density가 0과 1사이의 값을 가지는 반면, 기존의 fx, fy, fxy의 경우 조사 면적 내의 격자의 수를 세기 때문에Usage LengthUsage Density에 비해 매우 큰 값을 갖게 된다. 따라서 다섯 항을 동일한 차원에서 비교하기 위하여 각각 조사한 스크랩에 해당하는 격자수를 조사 영역의 넓이로 나눠주어 정규화 시켜주었다. 적합도 함수의 구성을 위하여 각 항의 가중치(Weighting factor)의 합은 1이 되도록 하였고, 비중을 달리하여 네스팅 결과가 어떻게 변화되는지를 비교하며 반복적인 실험을 실시하였다.

네스팅 결과는 판단하는 기준이 다양하기 때문에 그 기준을 어떻게 설정하느냐에 따라 적합도 함수의 적절성과 효율성 등이 다르게 평가될 수 있다. 본 논문에서는 네스팅의 결과를 평가할 때, 첫 번째로 스크랩률(Scrap ratio)을 비교하고 두 번째로 다른 분야의 네스팅과 차별적인 특징이라고 할 수 있는 잔재의 효용성을 고려한다. 즉, 네스팅 후 강재에 부재를 배치하고 남은 영역의 길이가 많이 확보될수록 좋은데, 이는 이 후 스크랩을 이용하여 부재 배치를 다시 시도할 때 좀 더 효율적으로 사용할 수 있기 때문이다. 따라서 본 논문에서는 부재가 최대한 강재의 좌측 및 하 단에 배치되는 것을 지향하고 있다.

적합도 함수의 효율성을 평가하기 위해 선박의 선미부, 중앙부, 엔진룸의 부재들을 대상으로 네스팅을 실시하였다. 선미부 부재들은 곡 형태의 부재가 많은데 직선의 폴리곤(Polygon) 형태보다 호를 포함하는 부재가 많다. 또한 부재들 간의 크기가 비교적 비슷한 특징을 가지고 있다. 이에 반해 중앙부 부재들은 부재들의 크기가 크고, 비교적 사각형에 가까운 부재들이 많기 때문에 네스팅이 쉽다. 한편 엔진룸은 일반적으로 전체 부재들의 개수가 많고 부재들 간의 크기는 중앙부에 비해 비교적 일관적인 편이다. 그러나 부재들의 형상이 매우 다양하여 네스팅이 가장 어렵다.

첫 번째로 선미부에 대한 네스팅을 실시하였는데, 선미부 부재들을 각각 두 그룹으로 나누어 두 가지 다른 측면에서 적합도 함수에 따른 배치 결과를 비교하였다. 첫 번째 부재 그룹은 총 19개의 부재로 구성되어 있는데 배치 결과 한 판의 강재에 얼마나 많은 부재를 배치하는지 알아보고 그 때 발생하는 스크랩 면적을 비교하였다. 두 번째 부재 그룹은 34개의 부재로 구성되어 있으며 배치 결과를 통해서 발생한 스크랩 형상의 x축 방향 길이를 비교하였다. 이 때 잔재의 효용성을 기준으로 평가하기 위하여 부재의 총 면적에 비해 비교적 큰 사이즈의 자재에 배치하여 테스트를 실시하였다. 선미부 블록 부재에 대한 배치가 완료되면 배치 결과를 토대로 좋은 효율을 나타내는 케이스 중 몇 가지를 적용하여 선박 중앙부 블록 부재와 엔진룸 블록 부재에 대해 네스팅을 다시 수행하여 효율이 어떻게 달라지는지를 확인하기 위한 테스트를 실시하였다.

조선용 부재를 배치하기 위한 강재의 사이즈는 가로×세로×두께(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

Table 2

Numerical results of nesting process for stern

부재 그룹 1의 네스팅 결과를 분석해보면 케이스 3과 4(Fig. 12)의 적합도 함수를 이용하였을 때 19개의 부재를 모두 한 판에 배치하였으며 이에 따라 스크랩이 가장 적게 발생하였으나, 이 외의 케이스들은 한판에 모든 부재들을 배치하지 못하였다.

Fig. 12

Case 3(top) and 4(bottom) for part group 1

한편 케이스 4와 5는 Usage Length에 대한 가중치를 고정시킨 뒤, fxfy의 가중치가 서로 뒤바뀌어 있는 케이스들이며, 그에 따라 네스팅 결과가 달라짐을 Fig. 1213에서 확인할 수 있다. fx의 비중이 fy의 비중보다 큰 케이스 4(Fig. 12의 아래)의 적합도 함수를 적용하였을 때의 네스팅 결과를 살펴보면 x축의 스크랩이 덜 발생하는 각도로 부재들이 회전하여 배치된 반면, fy의 비중이 큰 케이스 5(Fig. 13)의 적합도 함수를 적용한 결과는 y축의 스크랩이 덜 발생하도록 부재가 회전하여 배치된 것을 알 수 있다. 이와 같은 차이에 의해, 케이스 4의 경우 모든 부재가 한 판의 강재에 배치되었으나, 케이스 5의 경우 한판 안에 모두 배치하지 못한 결과를 보였다. 그러므로 적합도 함수에서 각 항의 비중을 어떻게 설정하느냐에 따라 부재들의 배치 경향 및 결과에 영향을 미친다는 것을 알 수 있다.

Fig. 13

Case 5 for part group 1

부재 그룹 2의 네스팅 결과를 살펴보면 모든 케이스에 대해서 스크랩률이 약 0.555로 비슷하게 나타났으나, 잔재의 효용성을 판단하는 측면에서 케이스 1의 경우 Fig. 14에서처럼 부재들이 x축으로 길게 배치가 되면서 잔재 활용성이 떨어지는 결과를 보였다. 이에 반해 케이스 2(Fig. 15)에서는 잔재의 x축 방향 길이가 가장 길게 나타나 이 후 잔재로 효율적으로 활용할 수 있을 것이라 기대된다.

Fig. 14

Case 1 for part group 2

Fig. 15

Case 2 for part group 2

케이스 1을 제외한 나머지 케이스들은 모두 fyUsage Length를 고려하였다는 공통점을 가지고 있는데(Table 1), 나머지 케이스들에 대한 네스팅 결과도 케이스 2와 비슷한 가용 길이를 나타냄으로써 두 가지 항목이 고려된 적합도 함수를 적용하여 네스팅 하였을 때, 잔재의 효용성 측면에서 좋은 효율을 보인다는 것을 알 수 있었다(Table 2).

여러 가지 적합도 함수를 이용하여 네스팅을 실시한 결과를 두 가지 측면에서 판단해보았을 때, 각각 케이스 2와 케이스 3, 4가 좋은 효율을 보이는 것으로 나타났다. 이 케이스들은 모두 Usage Lengthfy를 고려한 케이스였으며, 각 항에 적용한 가중치 또한 네스팅 결과에 영향을 미침을 알 수 있다.

다음은 앞선 두 가지의 네스팅 결과 비교를 통해 좋은 효율을 보이는 케이스를 선택하여 선박의 중앙부 블록의 부재에 대하여 네스팅을 실시한 결과이다. 적용된 케이스는 Table 1의 적합도 함수 중 케이스 2와 4이며, 그 결과는 격자표현법으로 얻은 0과 1을 비트맵화 시켜서 얻은 이미지와 조선용 상업 CAD 시스템으로 연동하여 얻은 이미지로 각각 Fig. 1617에 나타내었다. 그림에서 주목할 점은 우선 부재의 홀 안에 다른 부재들의 배치가 잘 이루어진 점과 알고리즘 구현 시 따로 고려하지 않았던 부재들 간의 Pairing, Grouping의 수준이 만족할 만하게 나타난 점이다.

Fig. 16

Bitmap image (top) and a CAD drawing (bottom) from the result of case 2

Fig. 17

Bitmap image (top) and a CAD drawing (bottom) from the result of case 4

Table 3은 각 케이스 별로 강재 안에 배치된 부재의 수와 스크랩률이다. 그 결과를 살펴보면 케이스 2의 적합도 함수를 이용하여 배치하였을 때, 한 강재 안에 6개의 부재가 더 배치되었다. 앞서 선박의 선미부 부재들을 대상으로 네스팅 한 결과에서는 케이스 4가 더 효율적이었으나, 이 경우에는 케이스 2가 더 효율적임을 알 수 있다. 따라서 배치하려는 부재의 특성 등에 따라 적합도 함수는 다른 효율을 가질 수 있음을 알 수 있다.

Table 3

Comparison of the nesting results

다음은 엔진룸 부재를 케이스 2와 4를 적용하여 네스팅한 결과이다. 26개의 부재를 선별하여 만들어진 부재 그룹을 네스팅 하였는데, 케이스 2를 적용했을 때는 모든 부재를 한 강재 안에 배치를 하였으나(Fig. 18), 케이스 4를 적용하면 2개가 모자란 24개의 부재만이 한 판에 배치가 되었다(Fig. 19). 이 때 스크랩률의 차이는 약 0.03으로 나타났다(Table 4).

Fig. 18

Case 2 for engine room parts

Fig. 19

Case 4 for engine room parts

Table 4

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

케이스 2와 4에 대한 계산소요 시간을 비교해보면 부재 그룹 1과 엔진룸에 대한 네스팅 결과, 케이스 4를 적용했을 때 시간이 더 소요되었다. 케이스 4의 경우 케이스 2와는 달리 fx를 추가로 고려하는데, fx에 해당하는 격자 계산하기 때문에 시간이 더 소요되므로 케이스 4를 적용하였을 때 케이스 2보다 더 많은 시간이 소요되었다.

부재그룹 1에 비해 더 많은 부재를 배치하는 엔진룸의 네스팅의 경우, 계산 시간은 덜 소요가 되는데 이는 테스트 할 때 사용한 엔진룸의 부재들의 형상이 부재그룹 1에 비해 회전 단계에서 배치가 불가능한 경우가 많았기 때문이다.

4. 결 론

본 연구에서는 최적배치를 위한 네스팅 알고리즘 연구를 실시하였으며, 특히 조선용 부재에 대한 네스팅을 고려하여 효율적인 결과를 얻을 수 있는 적합도 함수의 구성에 대해 알아보았다. 조선용 부재와 자재(잔재 포함)는 형상과 크기가 다양하고 고려해야하는 조건이 복잡한 특징을 가지고 있는 네스팅 문제이다.

기존에 연구 되었던 적합도 함수에서 x축 및 y축 방향으로의 스크랩을 고려하는 항 일부를 취사선택 및 수정하고 조합을 달리하여 적합도 함수를 구성하여 반복적으로 실험을 수행하였으며, 특히 가중치법을 사용하여 각 항의 중요도를 평가하여 네스팅을 평가하는 기준을 만족시키는 적절한 적합도 함수를 구성하고자 하였다.

이 과정에서 Kang(1998)에 의해 제안된 fx, fy, fxyWeng and Kuo(2011)에 의해 제안된 Usage Length, Usage Density를 고려하였는데, 그 결과 대체적으로 fyUsage Length를 포함하여 구성된 적합도 함수를 이용한 네스팅이 조선용 강재의 효율적인 배치 및 활용 가능한 잔재 형성에 가장 적합하다는 것을 알 수 있었다. 또한 가중치를 어떻게 정하느냐에 따라 네스팅 결과가 민감한 영향을 미친다는 것을 알 수 있다.

선박의 선미부의 두 가지 부재 그룹에 대해 각각 네스팅을 실시하고, 중앙부와 엔진룸의 부재에 대해 네스팅을 실시한 결과, 좋은 결과를 보이는 적합도 함수가 각각 다른 것을 확인함으로서, 고정된 하나의 적합도 함수만을 이용하여 모든 부재를 네스팅하는 것 보다는 부재의 특성 및 사용자의 판단 기준에 따라 적합도 함수를 구성하고 네스팅에 적용시키는 것이 더 적절한 결과를 얻을 수 있을 것이라 기대된다.

현재의 네스팅 알고리즘을 이용한 부재 배치에서는 부재의 면적을 기준으로 내림차순으로 배치를 실시하는데, 추후에는 배치 순서를 SA(Simulated annealing) 등을 이용하여 강재에 스크랩을 덜 발생시키는 최적의 배치 순서를 구하여 네스팅 알고리즘에 적용할 계획이다.

Acknowledgements

본 논문은 지식경제부 산업융합원천기술개발사업(IT융합, 10035331, 시뮬레이션 기반의 선박 및 해양플랜트 생산기술 개발)으로 지원된 연구임

References

Adamowicz, M., Albano, A., 1976. Nesting Two-Dimensional Shapes in Rectangular Modules. Computer-Aided Design, 8(1), 27-33.

Adamowicz M., Albano A.. Nesting Two-Dimensional Shapes in Rectangular Modules. Computer-Aided Design 1976;8(1):27–33. 10.1016/0010-4485(76)90006-3.

Bang, G.B., 1990. Optimal Allocation of Two-Dimensional Irregular Shapes for Minimum Waste. Master. Seoul: Seoul National University.

Bang G.B.. Optimal Allocation of Two-Dimensional Irregular Shapes for Minimum Waste. Master Seoul National University; Seoul: 1990.

Bresenham, J.E., 1965. Algorithm for Computer Control of a Digital Plotter. IBM System Journal, 4(1), 25-30.

Bresenham J.E.. Algorithm for Computer Control of a Digital Plotter. IBM System Journal 1965;4(1):25–30. 10.1147/sj.41.0025.

Burkardt, J., 2011. Florida State University. [Online] Available at : <http://people.sc.fsu.edu/-jburkardt/cpp_src/circle_arc_ grid/circle_arc_grid.html> [Accessed 13 Jun. 2013].

Burkardt J.. Florida State University. [Online] 2011. Available at : <http://people.sc.fsu.edu/-jburkardt/cpp_src/circle_arc_ grid/circle_arc_grid.html>. [Accessed 13 Jun. 2013].

Burke, E.K., Hellier, R.S.R., Kendall, G., Whitwell, G., 2007. Complete and Robust No-Fit Polygon Generation for the Irregular Stock Cutting Problem. European Journal of Operational Research, 179(1), 27-49.

Burke E.K., Hellier R.S.R., Kendall G., Whitwell G.. Complete and Robust No-Fit Polygon Generation for the Irregular Stock Cutting Problem. European Journal of Operational Research 2007;179(1):27–49. 10.1016/j.ejor.2006.03.011.

Kang, H.G., 1998. Optimal Layout of Irregular Shape Ship Parts. Master. Kwangju: Chonnam National University.

Kang H.G.. Optimal Layout of Irregular Shape Ship Parts. Master Chonnam National University; Kwangju: 1998.

Kim, Y.G., Yang, K.B., Cho, K.H., 2006. Development of 2DWord Pattern and Bit Operators for Optimal Nesting. Proceedings of the Korean Society of Mechanical Engineers, 3155-3160.

Kim Y.G., Yang K.B., Cho K.H.. Development of 2DWord Pattern and Bit Operators for Optimal Nesting. Proceedings of the Korean Society of Mechanical Engineers 2006;:3155–3160.

Oliveira, J.F., Ferreira, J.S., 1993. Algorithms for Nesting Problems, Applied Simulated Annealing. In: Vidal, R.V.V. (Ed.), Lecture Notes in Econ. and Maths Systems, Vol. 396. Springer Verlag, 255-274.

Oliveira J.F., Ferreira J.S., Vidal R.V.V.. Algorithms for Nesting Problems, Applied Simulated Annealing In : Lecture Notes in Econ. and Maths Systems. Springer Verlag; 1993. 396p. 255–274.

Ryu, B.H., Kim, D.J., 2004. A Study on the Irregular Nesting Problem Using Genetic Algorithm and No Fit Polygon Methodology. Journal of the Korean Society of Ocean Engineers, 18(2), 77-82.

Ryu B.H., Kim D.J.. A Study on the Irregular Nesting Problem Using Genetic Algorithm and No Fit Polygon Methodology. Journal of the Korean Society of Ocean Engineers 2004;18(2):77–82.

Sheen, D.M., 2012. Nesting Expert System using Heuristic Search. Journal of the Korean Society of Ocean Engineers, 26(4), 8-14.

Sheen D.M.. Nesting Expert System using Heuristic Search. Journal of the Korean Society of Ocean Engineers 2012;26(4):8–14.

Weng, W.C., Kuo, H.C., 2011. Irregular Stock Cutting System Based on AutoCAD. Advances in Engineering Software, 42(9), 634-643.

Weng W.C., Kuo H.C.. Irregular Stock Cutting System Based on AutoCAD. Advances in Engineering Software 2011;42(9):634–643. 10.1016/j.advengsoft.2011.04.009.

Article information Continued

Fig. 2

Geometric segment data from CAD system (arc)

Fig. 3

Grid representation process for a bracket-type part

Fig. 4

Flow chart of searching the allocation position

Fig. 5

Rotation of a part

Fig. 6

Process of translating a part

Fig. 7

Rectangular Area(left), X - Enclosure Area(middle), Y - Enclosure Area(right) (Bang, 1990)

Fig. 8

fx(left-top), fy(right-top), fxy(bottom

Fig. 10

Problem caused by fx

Fig. 11

Comparison of scrap ratio depending on fx

Table 1

Weighting factor sets for each case

Table 1

Table 2

Numerical results of nesting process for stern

Table 2

Fig. 12

Case 3(top) and 4(bottom) for part group 1

Fig. 13

Case 5 for part group 1

Fig. 14

Case 1 for part group 2

Fig. 15

Case 2 for part group 2

Fig. 16

Bitmap image (top) and a CAD drawing (bottom) from the result of case 2

Fig. 17

Bitmap image (top) and a CAD drawing (bottom) from the result of case 4

Table 3

Comparison of the nesting results

Table 3

Fig. 18

Case 2 for engine room parts

Fig. 19

Case 4 for engine room parts

Table 4

Comparison of the nesting results

Table 4

Table 5

Nesting results and computing time

Table 5