Advanced
Determination of Nesting Algorithm Fitness Function through Various Numerical Experiments
Determination of Nesting Algorithm Fitness Function through Various Numerical Experiments
Journal of Ocean Engineering and Technology. 2013. Oct, 27(5): 28-35
Copyright © 2013, Korean Society of Ocean Engineers
  • Received : June 14, 2013
  • Accepted : October 10, 2013
  • Published : October 31, 2013
Download
PDF
e-PUB
PubReader
PPT
Export by style
Article
Author
Metrics
Cited by
TagCloud
About the Authors
혜빈 이
원선 유

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.
Keywords
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 ).
PPT Slide
Lager Image
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 ).
PPT Slide
Lager Image
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'로 설정된다. 이렇게 형성된 강재의 격자 형상에 부재의 격자 형상을 배치한다.
PPT Slide
Lager Image
Grid representation process for a bracket-type part
부재를 배치하는 순서는 다양한 방법이 있는데, 본 연구에서는 네스팅 전문가들이 흔히 사용하는 방법인 부재 넓이에 따른 내림차순으로 진행하여 면적이 넓은 부재부터 강재에 배치를 한다. 부재 배치 과정을 순서도로 Fig. 4 에 나타내었다. 부재 배치를 위한 위치 탐색은 강재의 첫 행, 첫 열부터 이루어지며 좌에서 우 방향으로 조사를 먼저 실시하여 부재가 놓일 수 있는 최소 x 좌표를 갖는 격자에 배치를 시도하고 적합도 함수를 계산한다. 한행에 대한 탐색이 끝나면 다음 행으로 넘어가 다시 열 방향으로 배치 위치 탐색을 실시한다. 이와 같이 첫 행부터 마지막 행까지 탐색을 마치면 그 중에 가장 작은 적합도 함수의 결과를 갖는 위치에 부재가 최종적으로 배치된다. 부재가 배치를 시도할 때, 부재의 격자 데이터와 강재의 격자 데이터를 합하여 배치가 가능한지 확인하는데 부재의 내부와 경계선에 해당하는 격자가 위치한 강재의 격자는 '3'이 되고, 부재의 외부에 해당하는 격자가 위치한 강재의 격자는 초기 데이터 '2'를 유지한다. 이 과정에서 강재의 격자 데이터가 '4'가 되면 이전 과정에서 부재가 배치되어 격자 데이터가 '3'으로 설정되어 있는 격자에 다시 배치를 하려는 것이기 때문에 겹침이 발생한 것으로 판단하여 현재 배치 위치에 대한 탐색을 종료하고 배치가 가능한 다음 위치를 탐색한다. 이러한 과정을 부재를 회전시킬 때마다 반복하여 각 회전 각도에 대한 배치 위치를 찾고 적합도 함수를 계산하여 회전이 종료되면 회전 각도마다의 적합도 함수 결과를 비교하여 가장 좋은 효율을 보이는 회전 각도로 부재를 회전시키고, 그 각도에 대한 최적의 위치에 부재를 최종 배치시키고 다음 부재에 대한 배치 위치 탐색을 시작한다. 이와 같이 모든 부재를 배치하면 네스팅이 종료된다.
PPT Slide
Lager Image
Flow chart of searching the allocation position
한편 부재의 회전은 다음과 같이 두 가지 방법으로 실시할 수 있는데, 부재의 본 형상 자체를 회전시켜 매 각도마다 새로운 격자형상을 생성하는 방법( Kang, 1998 )과 회전을 하지 않은 부재를 격자 형상화하여 구한 격자들을 회전시키는 방법( Bang, 1990 )이 있다. 본 논문에서는 Fig. 5 에서와 같이 부재의 본 형상을 회전시켜 회전 시마다 격자 형상을 새로 생성하였으며, 부재의 외접사각형의 중심을 기준으로 회전하였다.
PPT Slide
Lager Image
Rotation of a part
회전된 부재에 대해 격자 형상을 생성하면 음(-)의 좌표 값이 발생하거나 회전 한 후의 격자 좌표들 중 최소 x 와 최소 y 가 각각 0이 아닌 경우가 생기는데, 이 때 발생하는 에러를 방지하고 메모리의 낭비를 최소화하기 위해 최소 x 와 최소 y 가 모두 0이 되도록 하는 보정 값을 적용한다( Fig. 6 ).
PPT Slide
Lager Image
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 Area x 방향 경계의 합을 말한다. 이 세 가지의 면적이 중요한 파라미터가 되어 다음 식 (2)에서 (6)까지와 같이 적합도 함수의 다섯 개의 항을 구성한다.
PPT Slide
Lager Image
Rectangular Area(left), X - Enclosure Area(middle), Y - Enclosure Area(right) (Bang, 1990)
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
여기서 A 는 이미 배치되어 고정되어 있는 부재의 면적이며, A ′은 배치가 진행 중인 부재의 면적이다.
한편 Kang의 학위 논문에서는 격자 표현법으로 네스팅 알고 리즘을 구현하는데 있어서 제안된 적합도 함수로서 x, y xy 방향으로 스크랩(Scrap)에 해당하는 격자의 수를 세어 계산한다( Kang, 1998 ).
PPT Slide
Lager Image
fx 는 후보부재가 최대한 원판의 좌측에 배치되도록 기여하는 항이며, 후보부재가 배치된 행에서 x 방향의 스크랩 면적을 의미한다. fy 는 후보부재가 원판의 아래쪽에 배치되도록 하는 항이며, 후보부재가 배치된 열에서 y 방향의 스크랩 면적을 의미한다. fxy 는 부재들이 배치되어 가는 형태가 직사각형을 이루도록 하며 후보부재가 배치된 영역 안의 스크랩 면적을 의미한다. Fig. 8 은 부재의 배치에 따라 각 항이 고려하는 영역(파란 영역)이 나타내어져 있다. fx 는 배치된 부재가 차지하는 행에서 생기는 스크랩에 해당하는 격자를, fy 는 배치된 부재가 차지하는 열에서 생기는 스크랩에 해당하는 격자를, fxy 는 원점에서 배치된 부재를 포함하는 사각형 내의 스크랩에 해당하는 격자를 각각 세어 수치로 나타낸다.
PPT Slide
Lager Image
fx(left-top), fy(right-top), fxy(bottom
한편 Weng and Kuo(2011) 에 의해 제안된 네스팅 시스템에서는 Usage Length Usage Density 의 개념을 도입하여 부재를 배치할 최적의 위치를 찾는다. 이 때 Usage Length 는 강재의 너비( Lt )와 현재 배치 중인 부재를 포함하는 영역의 너비( Lu )의 비로 정의된다. Usage Density 는 현재 배치 중인 부재를 포함하는 영역의 너비( Lu )와 강재의 폭( H )을 갖는 외접사각형 내에 실제 부재가 배치된 영역의 비로 정의 된다. 각각의 파라미터들은 Fig. 9 에 나타나 있다.
PPT Slide
Lager Image
Parameters of fitness function(Weng and Kuo, 2011)
PPT Slide
Lager Image
PPT Slide
Lager Image
- 3.2 적합도 함수
본 논문에서는 이미 제안된 적합도 함수들의 항들을 취사선택하여 새로운 조합을 만들고, 다목적 최적화의 일종인 가중치법(Weighting factor method)을 사용하여 각 항의 비중을 달리 함으로써 조선용 부재의 배치에 어떤 결과가 나타나는지를 살펴본다.
PPT Slide
Lager Image
기존의 목적함수들을 이용하여 조선용 부재에 적용하여 본 결과, Kang(1998) 이 제안한 함수는 스크랩률을 줄이는데 기여를 하며, Weng and Kuo(2011) 가 제안한 함수는 잔재를 효율적으로 남기는데 기여를 한다. 이에 따라 여기서 고려한 항목으로는 Kang(1998) 에 의해 제안된 식 (7)의 fx , fy , fxy Weng and Kuo(2011) 에 의해 제안된 Usage Length (식 (8)), Usang Density (식 (9)) 등에 주목하였다. fx 의 경우, 판의 첫 열부터의 x 축 방향으로 스크랩을 고려하게 되면 Fig. 10 에서처럼 부재 A의 배치 결과에 영향을 받아 다음 배치되는 부재들이 배치 위치를 선정할 때 x 방향의 스크랩이 덜 발생하는 위치를 선택하기 위해 사각형 영역 안에 보이는 바와 같이 강재의 하단에서 약간 떨어진 곳에 배치될 가능성이 있다. 이러한 영향을 줄이고자 본 적합도 함수에서는 fx Fig. 11 (b) 와 같이 현재 배치 중인 후보부재의 외접 사각형 내에서의 x 축 방향 스크랩만을 고려하도록 변경하였다. Fig. 11 (a) 에서 빗금 친 부분의 스크랩 면적이 식 (7)의 fx 를 이용하였을 때의 스크랩 면적이고, (b) 의 빗금 친 부분이 본 논문에서 사용한 fx 를 이용하여 부재의 외접 사각형 내의 스크랩을 나타낸 모습이다.
PPT Slide
Lager Image
Problem caused by fx
PPT Slide
Lager Image
Comparison of scrap ratio depending on fx
Usage Density 의 경우, 조사영역은 그대로 유지하되 조사영역 내에 부재가 위치한 면적을 계산하는 본래의 Usage Density 가 아니라 스크랩 면적을 조사하도록 수정하였다. Usage Length Usage Density 가 0과 1사이의 값을 가지는 반면, 기존의 fx , fy , fxy 의 경우 조사 면적 내의 격자의 수를 세기 때문에 Usage Length Usage 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 는 각 케이스마다의 네스팅 결과이다.
Weighting factor sets for each case
PPT Slide
Lager Image
Weighting factor sets for each case
Numerical results of nesting process for stern
PPT Slide
Lager Image
Numerical results of nesting process for stern
부재 그룹 1의 네스팅 결과를 분석해보면 케이스 3과 4( Fig. 12 )의 적합도 함수를 이용하였을 때 19개의 부재를 모두 한 판에 배치하였으며 이에 따라 스크랩이 가장 적게 발생하였으나, 이 외의 케이스들은 한판에 모든 부재들을 배치하지 못하였다.
PPT Slide
Lager Image
Case 3(top) and 4(bottom) for part group 1
한편 케이스 4와 5는 Usage Length 에 대한 가중치를 고정시킨 뒤, fx fy 의 가중치가 서로 뒤바뀌어 있는 케이스들이며, 그에 따라 네스팅 결과가 달라짐을 Fig. 12 13 에서 확인할 수 있다. fx 의 비중이 fy 의 비중보다 큰 케이스 4( Fig. 12 의 아래)의 적합도 함수를 적용하였을 때의 네스팅 결과를 살펴보면 x 축의 스크랩이 덜 발생하는 각도로 부재들이 회전하여 배치된 반면, fy 의 비중이 큰 케이스 5( Fig. 13 )의 적합도 함수를 적용한 결과는 y 축의 스크랩이 덜 발생하도록 부재가 회전하여 배치된 것을 알 수 있다. 이와 같은 차이에 의해, 케이스 4의 경우 모든 부재가 한 판의 강재에 배치되었으나, 케이스 5의 경우 한판 안에 모두 배치하지 못한 결과를 보였다. 그러므로 적합도 함수에서 각 항의 비중을 어떻게 설정하느냐에 따라 부재들의 배치 경향 및 결과에 영향을 미친다는 것을 알 수 있다.
PPT Slide
Lager Image
Case 5 for part group 1
부재 그룹 2의 네스팅 결과를 살펴보면 모든 케이스에 대해서 스크랩률이 약 0.555로 비슷하게 나타났으나, 잔재의 효용성을 판단하는 측면에서 케이스 1의 경우 Fig. 14 에서처럼 부재들이 x 축으로 길게 배치가 되면서 잔재 활용성이 떨어지는 결과를 보였다. 이에 반해 케이스 2( Fig. 15 )에서는 잔재의 x 축 방향 길이가 가장 길게 나타나 이 후 잔재로 효율적으로 활용할 수 있을 것이라 기대된다.
PPT Slide
Lager Image
Case 1 for part group 2
PPT Slide
Lager Image
Case 2 for part group 2
케이스 1을 제외한 나머지 케이스들은 모두 fy Usage Length 를 고려하였다는 공통점을 가지고 있는데( Table 1 ), 나머지 케이스들에 대한 네스팅 결과도 케이스 2와 비슷한 가용 길이를 나타냄으로써 두 가지 항목이 고려된 적합도 함수를 적용하여 네스팅 하였을 때, 잔재의 효용성 측면에서 좋은 효율을 보인다는 것을 알 수 있었다( Table 2 ).
여러 가지 적합도 함수를 이용하여 네스팅을 실시한 결과를 두 가지 측면에서 판단해보았을 때, 각각 케이스 2와 케이스 3, 4가 좋은 효율을 보이는 것으로 나타났다. 이 케이스들은 모두 Usage Length fy 를 고려한 케이스였으며, 각 항에 적용한 가중치 또한 네스팅 결과에 영향을 미침을 알 수 있다.
다음은 앞선 두 가지의 네스팅 결과 비교를 통해 좋은 효율을 보이는 케이스를 선택하여 선박의 중앙부 블록의 부재에 대하여 네스팅을 실시한 결과이다. 적용된 케이스는 Table 1 의 적합도 함수 중 케이스 2와 4이며, 그 결과는 격자표현법으로 얻은 0과 1을 비트맵화 시켜서 얻은 이미지와 조선용 상업 CAD 시스템으로 연동하여 얻은 이미지로 각각 Fig. 16 17 에 나타내었다. 그림에서 주목할 점은 우선 부재의 홀 안에 다른 부재들의 배치가 잘 이루어진 점과 알고리즘 구현 시 따로 고려하지 않았던 부재들 간의 Pairing, Grouping의 수준이 만족할 만하게 나타난 점이다.
PPT Slide
Lager Image
Bitmap image (top) and a CAD drawing (bottom) from the result of case 2
PPT Slide
Lager Image
Bitmap image (top) and a CAD drawing (bottom) from the result of case 4
Table 3 은 각 케이스 별로 강재 안에 배치된 부재의 수와 스크랩률이다. 그 결과를 살펴보면 케이스 2의 적합도 함수를 이용하여 배치하였을 때, 한 강재 안에 6개의 부재가 더 배치되었다. 앞서 선박의 선미부 부재들을 대상으로 네스팅 한 결과에서는 케이스 4가 더 효율적이었으나, 이 경우에는 케이스 2가 더 효율적임을 알 수 있다. 따라서 배치하려는 부재의 특성 등에 따라 적합도 함수는 다른 효율을 가질 수 있음을 알 수 있다.
Comparison of the nesting results
PPT Slide
Lager Image
Comparison of the nesting results
다음은 엔진룸 부재를 케이스 2와 4를 적용하여 네스팅한 결과이다. 26개의 부재를 선별하여 만들어진 부재 그룹을 네스팅 하였는데, 케이스 2를 적용했을 때는 모든 부재를 한 강재 안에 배치를 하였으나( Fig. 18 ), 케이스 4를 적용하면 2개가 모자란 24개의 부재만이 한 판에 배치가 되었다( Fig. 19 ). 이 때 스크랩률의 차이는 약 0.03으로 나타났다( Table 4 ).
PPT Slide
Lager Image
Case 2 for engine room parts
PPT Slide
Lager Image
Case 4 for engine room parts
Comparison of the nesting results
PPT Slide
Lager Image
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 와 각각 비교해보았을 때, 한 강재 안에 배치된 부재의 개수나 스크랩률 등이 큰 차이가 없음을 알 수 있다.
Nesting results and computing time
PPT Slide
Lager Image
Nesting results and computing time
케이스 2와 4에 대한 계산소요 시간을 비교해보면 부재 그룹 1과 엔진룸에 대한 네스팅 결과, 케이스 4를 적용했을 때 시간이 더 소요되었다. 케이스 4의 경우 케이스 2와는 달리 fx 를 추가로 고려하는데, fx 에 해당하는 격자 계산하기 때문에 시간이 더 소요되므로 케이스 4를 적용하였을 때 케이스 2보다 더 많은 시간이 소요되었다.
부재그룹 1에 비해 더 많은 부재를 배치하는 엔진룸의 네스팅의 경우, 계산 시간은 덜 소요가 되는데 이는 테스트 할 때 사용한 엔진룸의 부재들의 형상이 부재그룹 1에 비해 회전 단계에서 배치가 불가능한 경우가 많았기 때문이다.
4. 결 론
본 연구에서는 최적배치를 위한 네스팅 알고리즘 연구를 실시하였으며, 특히 조선용 부재에 대한 네스팅을 고려하여 효율적인 결과를 얻을 수 있는 적합도 함수의 구성에 대해 알아보았다. 조선용 부재와 자재(잔재 포함)는 형상과 크기가 다양하고 고려해야하는 조건이 복잡한 특징을 가지고 있는 네스팅 문제이다.
기존에 연구 되었던 적합도 함수에서 x축 및 y 축 방향으로의 스크랩을 고려하는 항 일부를 취사선택 및 수정하고 조합을 달리하여 적합도 함수를 구성하여 반복적으로 실험을 수행하였으며, 특히 가중치법을 사용하여 각 항의 중요도를 평가하여 네스팅을 평가하는 기준을 만족시키는 적절한 적합도 함수를 구성하고자 하였다.
이 과정에서 Kang(1998) 에 의해 제안된 fx , fy , fxy Weng and Kuo(2011) 에 의해 제안된 Usage Length , Usage Density 를 고려하였는데, 그 결과 대체적으로 fy Usage 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    DOI : 10.1016/0010-4485(76)90006-3
Bang G.B. 1990 Optimal Allocation of Two-Dimensional Irregular Shapes for Minimum Waste. Master Seoul National University Seoul
Bresenham J.E. 1965 Algorithm for Computer Control of a Digital Plotter IBM System Journal 4 (1) 25 - 30    DOI : 10.1147/sj.41.0025
Burkardt J. 2011 Florida State University. [Online] Available at :
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    DOI : 10.1016/j.ejor.2006.03.011
Kang H.G. 1998 Optimal Layout of Irregular Shape Ship Parts. Master Chonnam National University Kwangju
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
Oliveira J.F. , Ferreira J.S. , Vidal R.V.V. 1993 Algorithms for Nesting Problems, Applied Simulated Annealing Springer Verlag Lecture Notes in Econ. and Maths Systems 396 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
Sheen D.M. 2012 Nesting Expert System using Heuristic Search Journal of the Korean Society of Ocean Engineers 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    DOI : 10.1016/j.advengsoft.2011.04.009