선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 연구에서는 기존의 Nesting 알고리즘 및 휴리스틱 기법의 문제점을 살펴보고, 특히 NFP 알고리즘을 개선할 수 있는 새로운 VLT 휴리스틱을 제시한다. VLT 휴리스틱은 두 단계로 구성된다.
가설 설정
- 3) 부재는 면적 순에 따라 배치한다.
- 4) 부재는 목적함수를 최소화하는 위치에 배치한다.
제안 방법
- 기존 임의형상 배치의 연구결과에서 부재배치를 면적순으로 실시하지 않는 가장 큰 이유는 내부에 오목한(Concave) 부분이 발생하거나 기배치된 부재의 형상들 사이로 새로운 부재가 배치될 가능성을 차단하기 때문이다. 그러나 본 연구에서 제시한 VLT 휴리스틱의 부재의 배치위치 탐색에서는 기배치된 부재의 형상들 사이로 작은 부재들의 배치가 가능하도록 면적순 배치를 실시한다.
- 또한 배치효율의 증대와 배치시간의 단축을 위하여 다음의 4가지 기법을 적용하였다.
- 목적함수 f4는 최소 무게중심거리(방기범, 1990)를 적용하여 배치하는 함수로, 무게중심 좌표의 제곱합(조준홍, 1990)이 같은 점들의 궤적을 산출하여 최소 궤적선에 근접한 배치를 하였으나, 제곱합의 최소 궤적선을 적용할 경우 부재가 y축에 접할 수 있음에도 최소 궤적선을 따라 x축 방향으로 진행되어 배치될 수 있는 오류의 가능성이 있으므로, 본 연구에서는 이와 같은 오류를 극복하고자 목적함수의 가중치와 무게중심 비율을 적용하였다.
- , 2000;2001)을 적용하였다. 배치전략으로는 두 부재의 NFP 중 최소 직사각형(Rectangle) 면적을 갖는 위치를 선택하였으며 다음 [Figure 5]와 같이 최소 직사각형 면적이 동일한 경우에는 배치될 부재의 도심과 판재의 좌측 아래점(원점)과의 최소거리를 선택하였다.
- 본 연구에서는 부재의 배치순서를 면적 순으로 고정하되, 부재의 형상에 따라 목적함수의 가중치 및 부재의 회전각 및 탐색간격을 변경하여 적용한다. VLT 휴리스틱에 적용한 목적 함수는 다음과 같다.
- 본 연구에서는 임의 형상의 부재 배치를 위한 새로운 휴리스틱(VLT : Vertex Line Tracing) 탐색을 제시하고 Visual C++ 6.0을 이용하여 NestLogic 프로그램을 개발하여 VLT 휴리스틱에 의한 부재의 자동배치를 구현하였다.
- 본 연구의 실험은 Burke의 연구(2006) 중 수율(Yield Ratio or Density)이 명시된 5개 문제에 대하여 수율 및 버림율을 비교하였으며, 실험시 목적함수 가중치(α, β, γ, δ), 회전각(θ) 및 탐색간격(pixel)은 다음 그림과 같이 프로그램에서 선택할 수 있도록 하였다.
- 비교 대상 문제는 다음 [Table 1]과 같으며, Albano(1980)의 의복 24개 및 36개 부재에 대한 연구결과를 최근 연구결과(조경호, 1993; 한윤근, 2000) 및 상용 프로그램인 NestLib과 SigmaNest를 이용한 결과와 비교하였다. 실험을 위하여 프로그램은 Visual C++ 6.
- 시뮬레이티드 어닐링은 우수한 배치를 제공하는 기법임에는 틀림없으나, 계산시간의 방대함으로 인해 현실적인 적용에 어려움이 있다. 이러한 문제를 극복하기 위하여 인공지능의 한 분야인 자율조직 신경회로망과 시뮬레이티드 어닐링 알고리즘을 결합한 2단계 스위칭 구조를 제안하였다(한국찬, 나석주, 1993). 이들 연구의 특징은 초기 배치단계에서 신경회로망의 적용으로 빠른 시간에 대략적인 배치윤곽을 얻고, 배치개선단계에서 시뮬레이티드 어닐링을 이용하여 상세 배치를 위한 전략이다.
- VLT 휴리스틱은 두 단계로 구성된다. 첫 단계에서는 기존의 부재의 배치 위치 탐색 알고리즘을 개선한 새로운 VLT 휴리스틱 규칙을 제시하며, 두 번째 단계에서는 새로운 VLT 휴리스틱 규칙에 따른 목적함수와 배치전략을 제시한다. 본 연구에서 제시하는 휴리스틱 정보는 다음과 같다.
- 형상의 배치 순서는 면적순으로 하며 최초 부재를 배치할 때 기준점을 판재의 좌측하단에 일치시켜 기준점의 Outgoing vector를 판재의 하단(x축)으로 회전시킨 후 기준점을 중심으로 일정 각도로 회전시키면서 목적함수를 계산하는 과정을 모든 정점에 대하여 실시한다.
- 임의형상 부재 배치에 관한 기존 연구와 비교를 위하여 의복 24개 및 36개(Albano and Sapuppo, 1980) 부재를 기초로 실험하였으며, 국내 연구 결과(조경호, 1993; 한윤근, 2000)와 비교하였다. 확대실험은 최근 연구에서 제시한 5개 기본 문제(Burke et al., 2006)에 대하여 연구 결과(Hopper, 2000; Burke et al., 2006)의 비교를 통하여 VLT 휴리스틱의 우수성을 검증하였다.
대상 데이터
- 임의형상 부재 배치에 관한 기존 연구와 비교를 위하여 의복 24개 및 36개(Albano and Sapuppo, 1980) 부재를 기초로 실험하였으며, 국내 연구 결과(조경호, 1993; 한윤근, 2000)와 비교하였다. 확대실험은 최근 연구에서 제시한 5개 기본 문제(Burke et al.
데이터처리
- 75%을 얻을 수 있었다. 동일한 문제에 대하여 Burke의 연구에서 제시한 기존 연구의 결과 값과 비교하였으며 실험결과는 다음 [Table 7] 및 [Figure 22]와 같다.
- 동일한 문제에 대하여 기존 연구 및 상용 프로그램인 NestLib과 SigmaNest를 이용한 결과 값과 비교하였으며 결과는 다음 [Table 2] 및 [Figure 17]과 같다.
- 위의 실험결과로부터 f1~f4의 목적함수의 적용이 형상패턴에 따라 각각 다른 결과를 나타냄을 알 수 있었다. 동일한 문제에 대하여 기존 연구 및 상용프로그램인 LECTRA, NestLib, SigmaNest를 이용한 결과 값과 비교하였으며 실험결과는 다음 [Table 3] 및 [Figure 18]과 같다.
이론/모형
- NFP와 유전자 알고리즘을 이용한 연구(유병항, 2002)에서는 기존의 방법(Fujita et al., 1993)과 같이 배치순서를 유전자로 처리하였으며, 배치방법은 수정된 NFP 방법(Bennell et al., 2000;2001)을 적용하였다. 배치전략으로는 두 부재의 NFP 중 최소 직사각형(Rectangle) 면적을 갖는 위치를 선택하였으며 다음 [Figure 5]와 같이 최소 직사각형 면적이 동일한 경우에는 배치될 부재의 도심과 판재의 좌측 아래점(원점)과의 최소거리를 선택하였다.
- 그러나 위의 방법은 도형의 모든 선소(line segment)에 위치한 모든 점들에 대하여 조사하여 두 도형의 겹침 여부를 판단하기 때문에 계산시간이 많이 소요된다. 따라서 본 연구에서는 한윤근(1992)의 연구에서 사용한 C언어의 그래픽 함수를 이용하였다.
- , 1993), TSP(Traveling Salesman Problem)와는 달리 배치위치를 또 다른 변수로 정의해야 하는 문제점이 있었다. 또한 부재의 위치와 경사각을 유전자로 처리하여 최적의 배치를 계산하였으며, 처리속도 및 수율 향상을 위한 기법으로 부재 형상의 추상화, 페어링(Pairing) 알고리즘, 그룹핑(Grouping) 알고리즘 등을 적용하였다(Yamauchi and Tezuka, 1995).
성능/효과
- 2) 탐색절차가 순차적이며 확정적이다. 즉 한번 부재가 어떤 위치에 배치되면 더 이상 고려하지 않는다.
- Albano의 문제 중 의복 36개 부재에 대한 확대 실험을 실시한 결과, 최적 근사해는 α : 1, β : 1, γ : 0, δ : 1, 회전각 10°로 설정 시 버림율(scrap ratio) 12.77%로 상용 프로그램보다 우수한 결과를 나타내었다.
- 결과에서 보듯이 VLT 휴리스틱을 적용한 결과 내부에 움푹 패인 공간(Hollow)이 있는 부재의 배치 과정에서 기존의 NFP보다 높은 수율을 보임을 알 수 있다.
- 다음 [Table 8]과 같이 결과 비교가 가능한 문제의 유형과 비교시, 한윤근의 연구와는 유사한 결과를, Hopper의 연구결과 보다는 월등한 해를 각각 산출하였으며, 최근 연구인 Burke의 연구 결과와 비교시 Albano(24)문제를 제외하고는 우수한 해를 산출하지 못하였으나, VLT 휴리스틱을 이용하여 부재의 배치를 면적 순으로 확정하고 배치할 경우에도 형상의 패턴에 적합한 목적함수 및 탐색 범위(회전 각도 및 이동 pixel)의 개선을 통하여 문제의 유형에 따라 일부 우수한 해를 얻을 수 있는 가능성을 제시하였다. 또한 본 연구에서 목적함수 가중치(α, β, γ, δ), 회전각(θ) 및 탐색간격(pixel) 결정은 반복실험을 통하여 결정하였으나 추정값 선정을 위한 효율적인 실험계획이 요구된다.
- 두 가지의 서로 상반된 목적을 최적화하는 문제가 이러한 배치 문제를 더욱 흥미롭게 한다. 본 연구에서 제시하는 VLT 휴리스틱은 임의의 2차원 임의형상에 대한 배치 기법으로 기존의 연구 결과와 비교 시 문제의 종류에 따라 일부 문제에서 우수한 효율을 나타내었다. 향후 Nesting 관련 산업의 상업용 소프트웨어 개발에도 VLT 휴리스틱의 적용이 가능할 것이라고 판단된다.
- 98%를 얻을 수 있었다. 실험 결과 VLT 휴리스틱이 임의 형상의 다각형 배치에도 비교적 우수한 결과를 얻을 수 있음을 보여 주었다. 실험 결과를 통하여 다각형(polygon)으로 구성된 형상의 경우 탐색 시 회전각(θ)을 작게 할수록 버림율이 감소함을 알 수 있었다.
- 실험 결과 상용 프로그램인 NestLib이나 SigmaNest보다 계산 시간은 증가되나 버림율이 감소되었으며, 한윤근의 연구결과 보다는 버림율이 높지만 Burke의 2006년 연구 결과보다 버림율이 낮으며 효율이 더 좋은 것을 알 수 있었다.
- 실험 결과 최적 근사해는 α : 1, β : 0, γ : 0, δ : 1, 회전각 90°로 실험시 30.77% 버림율(Scrap Ratio)을 얻을 수 있었다.
- 실험 결과를 통하여 다각형(polygon)으로 구성된 형상의 경우 탐색 시 회전각(θ)을 작게 할수록 버림율이 감소함을 알 수 있었다.
- 위의 실험결과로부터 VLT 휴리스틱이 동일 형상의 반복 배치에 있어서도 좋은 결과를 나타냄을 알 수 있다.
- 05% 이었다. 위의 실험결과로부터 본 연구에서 제시한 목적함수 f1, f4가 f2, f3 함수의 적용 없이도 부재의 최적배치가 가능함을 알 수 있었다. 또한 부재의 형상 패턴에 따라 각도나 목적함수를 증가시키는 것이 효율적이지 않은 경우도 발생하였는데, 이는 임의 형상의 배치가 경우의 수가 많은 NP-Hard 문제로 분류되기 때문에 최적 근사해는 찾을 수 있으나 최적해는 찾기 어렵다는 것을 보여준다.
- 총 12회의 실험을 실시하였으며, 최적 근사해는 α : 1, β : 0, γ : 0, δ : 1, 회전각 30°로 설정했을 경우 버림율(Scrap Ratio)은 15.05% 이었다.
- 최적 근사해는 α : 1, β : 0, γ : 0, δ : 1, 회전각 1°로 실험시 버림율(Scrap Ratio) 23.98%를 얻을 수 있었다.
- 최적 근사해는 α : 3, β : 0, γ : 0, δ : 1, 회전각 90°로 실험시 버림율(Scrap Ratio) 23.75%을 얻을 수 있었다.
후속연구
- 끝으로 Nesting의 목적이 절단공정을 통한 판재의 효율적인 사용에 있는 바 CAD 프로그램으로부터 입력과, Nesting, 절단 공정이 통합된 연구가 바람직할 것으로 판단된다.
- 따라서 향후 연구방향은 이러한 기법들과 함께 계산시간 축소를 위한 최적화 알고리듬의 개발과 Nesting 숙련자들의 경험적 기법을 수학적으로 동시에 구현하는 것이 바람직하다고 판단되며, 목적함수 가중치(α, β, γ, δ), 회전각(θ) 및 탐색간격(pixel) 선정을 위한 효율적인 실험계획이 요구된다.
- 또한 본 연구에서 목적함수 가중치(α, β, γ, δ), 회전각(θ) 및 탐색간격(pixel) 결정은 반복실험을 통하여 결정하였으나 추정값 선정을 위한 효율적인 실험계획이 요구된다.
- 본 연구에서 제시하는 VLT 휴리스틱은 임의의 2차원 임의형상에 대한 배치 기법으로 기존의 연구 결과와 비교 시 문제의 종류에 따라 일부 문제에서 우수한 효율을 나타내었다. 향후 Nesting 관련 산업의 상업용 소프트웨어 개발에도 VLT 휴리스틱의 적용이 가능할 것이라고 판단된다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.