[논문]A hybrid genetic algorithm for the optimal transporter management plan in a shipyard

Jun-Ho Park; Yung-Keun Kwon

doi:10.9708/jksci.2023.28.12.049

A hybrid genetic algorithm for the optimal transporter management plan in a shipyard 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.28 no.12, 2023년, pp.49 - 56

Jun-Ho Park (School of IT Convergence, University of Ulsan) , Yung-Keun Kwon (Department of Electrical, Electronic and Computer Engineering, University of Ulsan)

초록
AI-Helper

본 연구에서는 트랜스포터의 할당 및 운행 순서를 최적화하기 위한 유전 알고리즘을 제안한다. 유전 알고리즘의 해는 리스트의 집합으로 표현되는데 각 리스트는 해당 트랜스포터가 작업할 순서를 나타낸다. 또한 성능 향상을 위해 효과적인 지역 탐색 연산을 결합한 혼합형 유전 알고리즘의 형태로 구현하였다. 지역 탐색 연산은 작업량이 적은 트랜스포터에서 작업의 블록을 꺼내어 다른 트랜스포터의 작업 목록에 삽입함으로써 트랜스포터 운용 대수의 감소를 유도한다. 제안하는 알고리즘의 효용성을 평가하기 위해 실제 조선소와 유사한 규모의 시뮬레이션 환경을 통해 Multi-Start 및 순수 유전알고리즘과 비교하였다. 가장 큰 규모의 문제에 대해 그들에 비해 트랜스 포터 수는 각각 40% 및 34%, 총작업 소요 시간은 27% 및 17% 감소시켰다.

Abstract ▼ AI-Helper

In this study, we propose a genetic algorithm (GA) to optimize the allocation and operation order of transporters. The solution in the GA is represented by a set of lists each of which the operation order of the corresponding transporter. In addition, it was implemented in the form of a hybrid genetic algorithm combining effective local search operations for performance improvement. The local search reduces the number of operating transporters by moving blocks from a transporter with a low workload into that with a high workload. To evaluate the effectiveness of the proposed algorithm, it was compared with Multi-Start and a pure genetic algorithm through a simulation environment similar in scale to an actual shipyard. For the largest problem, compared to them, the number of transporters was reduced by 40% and 34%, and the total task time was reduced by 27% and 17%, respectively.

주제어

표/그림 (13)

표 Table 1. Example of Transporter Information Data
표 Table 2. Example of Block Transport Schedule Data
표 Table 3. Example of Schedule Program Results
그림 Fig. 1. Flow of the Proposed Method
그림 Fig. 2. Example of a Chromosomal Representation
그림 Fig. 3. Example of Crossover Operation
그림 Fig. 4. Example of Block-Move Mutate
그림 Fig. 5. Example of Transporter-Swap Mutate
그림 Fig. 6. Pseudo-Code of the Local Search Algorithm
그림 Fig. 7. Fitness-Generation Graph
그림 Fig. 8. Example of a Graph in a Shipyard
표 Table 4. Simulation Parameters
표 Table 5. Our HGA Parameters

AI 본문요약
AI-Helper

문제 정의

본 논문에서 다루는 트랜스포터 운용 문제는 각 트랜스포터에 운반할 블록들을 할당하고 운반 순서를 스케줄링하는 조합 최적화 문제이다. 이러한 종류의 문제를 풀기 위해 유전 알고리즘 기반의 방법을 제안하며 특히 순수 유전 알고리즘의 낮은 지역 탐색 능력을 보완하기 위해 지역탐색이 결합한 혼합형 유전 알고리즘 모델을 활용한다.
본 논문에서는 조선소에서 블록 운송 작업에 투입되는 트랜스포터의 대수를 최소화하기 위해 트랜스포터 작업할당을 최적화하는 방법으로 HGA 방법을 제안하였다. 조립 공장간 최단 거리를 얻기 위해 Dijkstra 알고리즘을 적용하였으며, 유전 알고리즘에서 국부적 탐색을 강화하기 위해 지역 탐색 기능을 탑재하였다.
즉 운반해야 할 N개 블록 각각에 대해 운반을 담당할 트랜스포터의 번호와 해당 트랜스포터가 운반할 순서를 출력한다. 할당된 트랜스포터와 순서에 따라 작업의 효율성이 달라지기 때문에 본 연구에서는 제약 조건을 만족하면서 가장 적은 수의 트랜스포터를 할당하고 운영시간을 최소화하도록 Table 3을 최적화하는 것이 본 연구의 목표가 된다. 실제 조선소 상황을 고려하여 본 연구에서 다음과 같은 3가지 제약사항을 반영하였다.

가설 설정

이때 실제 운반은 시작 시각 이후에 시작되어 종료 시각 이전에 종료되어야 함을 의미한다. 또한 각 트랜스포터는 할당된 블록들을 한번에 하나의 블록만을 운반하며 하나의 블록을 운반 완료한 후 다음 블록을 운반할 수 있다고 가정한다. 한편, 트랜스포터 스케줄링 문제의 출력은 각각의 블록 운반 일정(즉 Table 2의 각 행)에 대해 운반을 담당할 트랜스포터를 할당하고 운반 순서를 스케줄링하는 것이다.
본 논문에서는 단위 계획 기간 동안 각 생산 공정 및 적치 위치에 따라 운반해야 할 블록들의 모든 요구량이 미리 알려진 있는 환경이라고 가정한다. 이러한 환경과 제약사항을 만족시키며 계획된 모든 블록을 운반하는 데 필요한 트랜스포터의 대수와 이동 거리를 최소화할 방법을 제안한다.

제안 방법

변형된 새로운 해는 변형 전보다 적합도가 떨어질 수도 있지만 새로운 문제공간을 탐색하는 데 도움이 된다. 본 연구에서 두 가지 변이 연산 Block-Move Mutate와 Transporter-Swap Mutate를 구현하였다. 전자는 어느 한 블록이 할당된 트랜스포터 및 운반 순서를 변경하는 것이고 후자는 한 쌍의 트랜스포터들에 대해 역할을 교환하는 것이다.
교차 연산은 두 개의 부모 해에서 새로운 자식 해를 생성하는 연산이다. 본 연구에서는 교차 연산의 과정에서 자식 해에 중복되는 블록 번호가 생기지 않도록 균일 교차(uniform crossover) 연산을 구현하였다. Figure 3은 두 부모 해 i와 j의 교차 연산 예를 보여준다.
본 연구에서는 운용 트랜스포터의 최소화와 트랜스포터의 총 주행 시간의 최소화를 목표로 최적화를 진행한다. 이를 위해 기존 유전 알고리즘에서 지역 탐색을 추가한 혼합형 유전알고리즘을 통해 추가적인 성능 개선 방안을 제안한다.
트랜스포터의 작업 순서를 최적화하는 작업은 순회 판매원 문제(Travelling Salesman Problem; TSP) 문제[11]로 표현된다. 본 연구에서는 트랜스포터에 할당되는 블록의 개수가 현실적으로 크지 않은 점을 고려하여 간단한 별도의 유전 알고리즘을 구현하여 문제를 간단하게 해결하였다.
위의 연구 방법들은 트랜스포터의 블록 운반 문제를 해결하기 위한 다양한 알고리즘들을 적용하였으며, 각 방법은 소수의 트랜스포터 운용이나 블록 이동과 같은 제한된 문제 환경에 적합한 접근 방식을 사용하였다. 그러나 수십대의 트랜스포터와 매일 수백 개의 블록을 이동하는 실제 운영 환경에서의 적용 가능성에 대해서는 성공적인 결과를 보이지 못한 한계점이 있다.
본 논문에서는 단위 계획 기간 동안 각 생산 공정 및 적치 위치에 따라 운반해야 할 블록들의 모든 요구량이 미리 알려진 있는 환경이라고 가정한다. 이러한 환경과 제약사항을 만족시키며 계획된 모든 블록을 운반하는 데 필요한 트랜스포터의 대수와 이동 거리를 최소화할 방법을 제안한다. 이를 위해 사용할 트랜스포터들의 목록과 각 트랜스포터가 운반할 블록들의 리스트로 해를 표현하고 최적해를 탐색하기 위한 유전 알고리즘을 고안하였다.
본 연구에서는 운용 트랜스포터의 최소화와 트랜스포터의 총 주행 시간의 최소화를 목표로 최적화를 진행한다. 이를 위해 기존 유전 알고리즘에서 지역 탐색을 추가한 혼합형 유전알고리즘을 통해 추가적인 성능 개선 방안을 제안한다. 실험은 두 알고리즘의 성능 차이를 확인하기 위해서 제안하는 모델로 프로그램을 구축한 뒤 실험 결과를 비교한다.
이러한 환경과 제약사항을 만족시키며 계획된 모든 블록을 운반하는 데 필요한 트랜스포터의 대수와 이동 거리를 최소화할 방법을 제안한다. 이를 위해 사용할 트랜스포터들의 목록과 각 트랜스포터가 운반할 블록들의 리스트로 해를 표현하고 최적해를 탐색하기 위한 유전 알고리즘을 고안하였다. 특히 효과적인 지역 최적해를 탐색하여 성능을 개선한다고 알려져 있는 혼합형 유전 알고리즘[4][5][6]을 사용하였다.

데이터처리

조립 공장간 최단 거리를 얻기 위해 Dijkstra 알고리즘을 적용하였으며, 유전 알고리즘에서 국부적 탐색을 강화하기 위해 지역 탐색 기능을 탑재하였다. 그리고 제안한 알고리즘에 대한 효용성을 검증하기 위해, 다양한 크기의 문제를 설정하고 이를 유전 알고리즘과 Multi-Start 두 알고리즘과 비교 실험해보았다. 그 결과 본 연구에서 개발한 알고리즘이 다른 두 알고리즘보다 효과적으로 작용함을 확인할 수 있었다.
또한 GA 방법은 기존 HGA 방법에서 지역 탐색 연산을 제거하고 최적해를 찾아가는 방법이며 그 외의 연산은 HGA와 동일하게 구성하였다. 다양한 문제 크기에 대한 비교를 위해서 블록의 개수(N = 100, 200, 300)를 변경하며 진행하였으며 각각에 대해 5회 실험을 통해 트랜스포터 대수와 소요 시간에 대한 평균값을 비교하였다. 표에서 보듯이 소요 시간의 경우 GA는 Multi-Start에 비해 N = 100, 200, 300 각각의 경우 13.
본 논문에서 제안하는 방법(HGA)을 검증하기 위해 다른 알고리즘들과 성능을 비교하였다 (Table 6). 이 표에서 Multi-Start 방법은 다수의 임의 해를 탐색한 후 그 중 최선 해를 반환하며 공정한 비교를 위해 HGA와 총탐색 횟수가 동일하도록 설정하였다.
이를 위해 기존 유전 알고리즘에서 지역 탐색을 추가한 혼합형 유전알고리즘을 통해 추가적인 성능 개선 방안을 제안한다. 실험은 두 알고리즘의 성능 차이를 확인하기 위해서 제안하는 모델로 프로그램을 구축한 뒤 실험 결과를 비교한다. 또한 실제 운영 환경과 비슷하도록 블록 수와 트랜스포터 수를 맞추어 실험 데이터를 구성하였다.

이론/모형

회전, 경로 손상에 따른 총 공차 이동 시간을 각 알고리즘별로 계산하여 Dijkstra 알고리즘이 적합함을 확인하였다. 또 다른 유사한 연구[10]에서는 트랜스포터의 공주행 거리를 최소화하기 위해 Dijkstra 알고리즘을 사용하여 각 절점 간의 최단 경로를 구하였고 트랜스포터들에 블록 할당 및 운반 순서를 결정을 하는데 전역 최적화 방법 중 하나인 Simulated Annealing(이하 SA) 기법을 사용하였다. 하지만 운용 트랜스포터 수의 최소화를 고려하지 않았다.
Yim et al[1]은 유전 알고리즘을 통해 공주행을 최소로 하는 운반 계획 알고리즘을 제안하였다. 유전 알고리즘의 초기해를 구성하기 위해서 개미 군집 알고리즘을 활용하였고 운반 거리 결정을 위해서 Dijkstra 알고리즘을 사용하였다. 하지만 운용 트랜스포터 수의 최소화를 고려하지 않았다.
본 논문에서 다루는 트랜스포터 운용 문제는 각 트랜스포터에 운반할 블록들을 할당하고 운반 순서를 스케줄링하는 조합 최적화 문제이다. 이러한 종류의 문제를 풀기 위해 유전 알고리즘 기반의 방법을 제안하며 특히 순수 유전 알고리즘의 낮은 지역 탐색 능력을 보완하기 위해 지역탐색이 결합한 혼합형 유전 알고리즘 모델을 활용한다. Figure 1은 본 논문에서 제안하는 혼합형 유전 알고리즘의 흐름도를 나타내며, 유전 알고리즘의 초기 해 생성 과정, 선택, 교차, 변이 연산 그리고 지역 탐색 연산에 대한 과정을 보여주고 있다.
본 논문에서는 조선소에서 블록 운송 작업에 투입되는 트랜스포터의 대수를 최소화하기 위해 트랜스포터 작업할당을 최적화하는 방법으로 HGA 방법을 제안하였다. 조립 공장간 최단 거리를 얻기 위해 Dijkstra 알고리즘을 적용하였으며, 유전 알고리즘에서 국부적 탐색을 강화하기 위해 지역 탐색 기능을 탑재하였다. 그리고 제안한 알고리즘에 대한 효용성을 검증하기 위해, 다양한 크기의 문제를 설정하고 이를 유전 알고리즘과 Multi-Start 두 알고리즘과 비교 실험해보았다.
이를 위해 사용할 트랜스포터들의 목록과 각 트랜스포터가 운반할 블록들의 리스트로 해를 표현하고 최적해를 탐색하기 위한 유전 알고리즘을 고안하였다. 특히 효과적인 지역 최적해를 탐색하여 성능을 개선한다고 알려져 있는 혼합형 유전 알고리즘[4][5][6]을 사용하였다.
한편 해를 탐색할 때마다 불필요한 연산을 하지 않도록 다익스트라 알고리즘[12]을 사용하여 각 노드 간의 최단거리 및 경로를 미리 계산해 두어 Fitness를 구할 때 활용하였다. 그 이외의 세부적인 환경설정은 Table 4, 5와 같이 설정하였다.

성능/효과

그리고 제안한 알고리즘에 대한 효용성을 검증하기 위해, 다양한 크기의 문제를 설정하고 이를 유전 알고리즘과 Multi-Start 두 알고리즘과 비교 실험해보았다. 그 결과 본 연구에서 개발한 알고리즘이 다른 두 알고리즘보다 효과적으로 작용함을 확인할 수 있었다. 하지만 본 논문에서는 실제 도로와 교차로에서의 충돌 상황, 트랜스포터가 블록을 옮기는 작업의 효율 등 현실적인 요소를 반영하는 데 한계가 있었다.
[9]은 경로 탐색 기법 방법인 Dijkstra, A*, Floyd 알고리즘들의 계산 비용과 정밀도를 비교하였다. 회전, 경로 손상에 따른 총 공차 이동 시간을 각 알고리즘별로 계산하여 Dijkstra 알고리즘이 적합함을 확인하였다. 또 다른 유사한 연구[10]에서는 트랜스포터의 공주행 거리를 최소화하기 위해 Dijkstra 알고리즘을 사용하여 각 절점 간의 최단 경로를 구하였고 트랜스포터들에 블록 할당 및 운반 순서를 결정을 하는데 전역 최적화 방법 중 하나인 Simulated Annealing(이하 SA) 기법을 사용하였다.

후속연구

그러나 이 연구에서는 트랜스포터의 대수가 최대 8대로 제한되었다. 따라서 보다 실제 조선소 환경을 고려한 트랜스포터 운용 최적화 방법은 연구할 필요성이 있다.
그 결과 본 연구에서 개발한 알고리즘이 다른 두 알고리즘보다 효과적으로 작용함을 확인할 수 있었다. 하지만 본 논문에서는 실제 도로와 교차로에서의 충돌 상황, 트랜스포터가 블록을 옮기는 작업의 효율 등 현실적인 요소를 반영하는 데 한계가 있었다. 또한 실제 상황에서 도로가 막히는 등의 동적인 상황을 고려해야하는 경우가 생긴다.
또한 실제 상황에서 도로가 막히는 등의 동적인 상황을 고려해야하는 경우가 생긴다. 향후 연구에서는 트랜스포터가 이동하는 공간을 다차원적으로 고려하여 실제 환경에서도 적용가능한 방법에 대하여 진행할 예정이다.

참고문헌 (12)

Yeon mi Suh, Myung-Il Roh, and Doo-Yeon Cho, "A Study on？the Optimal Operation Planning of a Transpoter Using the？Optimization Technique," Korean Journal of Computational？Design and Engineering Conference Paper Collection, pp.？187-192, Jan. 2011.
Sun-Bin Yim, Myung-ll Roh, Ju-Hwan Cha and Kyu-Yeul Lee,？"Optimal Block Transportation Scheduling Considering the？Minimization of the Travel Distance without Overload of a？Transporter," Journal of the Society of Naval Architects of Korea,？Vol. 45, No. 6, pp. 646-655, Dec. 2008. DOI: 10.3744/snak.2008.45.6.646

원문보기 상세보기
Cheol Min Joo, "Determination of the number and schedule of？transporters for block transportation in shipbuilding," Journal of？the Korean Society of Supply Chain Management, Vol. 13, No.？2, pp. 143-150, Oct. 2013.
Ahmed Maghawry, Rania Hodhod, Yasser Omar and Mohamed？Kholief. "An approach for optimizing multi-objective problems？using hybrid genetic algorithms," Soft Computing, Vol. 25, pp.？389-405, 2021. DOI:10.1007/s00500-020-05149-3

상세보기
Hossam Magdy Balaha, Mohamed Saif, Ahmed Tamer and Ehab？H. Abdelhay, "Hybrid deep learning and genetic algorithms？approach (HMB-DLGAHA) for the early ultrasound diagnoses of？breast cancer," Neural Computing and Applications, Vol. 34, pp.？8671-8695, 2022. DOI:10.1007/s00521-021-06851-5

상세보기
Gagan Deep Singh, Manish Prateek, Sunil Kumar, Madhushi？Verma, Dilbag Singh and Heung-No Lee, "Hybrid Genetic Firefly？Algorithm-Based Routing Protocol for VANETs," IEEE Access,？Vol. 10, pp. 9142-9151, 2022, DOI: 10.1109/ACCESS.2022.3142811.

상세보기
Jae-Young Shin and Na-Hyun Bak, "Transporter Scheduling with？Transporter Combination in Shipbuilding," Journal of Navigation？and Port Research, Vol. 38, No. 3, pp. 299-305, Jun. 2014. DOI:？10.5394/KINPR.2014.38.3.299

원문보기 상세보기
Woon-Seek Lee, Won-Il Lim, and Pyung-Hoi Koo, "Transporter？scheduling based on a network flow model for dynamic block？transportation environment," IE interfaces, Vol. 22, No. 1, pp.？63-72, Mar. 2009.
Jong-Heon Moon, Won-Sun Ruy and Doo-Yeoun Cho, "An？Operation Scheduling of Transporters Considering Turns and？Passing Delay at the Intersection Roads on the Shipyard," Journal？of the Society of Naval Architects of Korea, Vol. 54, No. 3, pp.？187-195, Jun, 2017. DOI: 10.3744/SNAK.2017.54.3.187

원문보기 상세보기
Jong-Heon Moon, Won-Sun Ruy, and Ju-Hwan Cha,？"Comparison of Optimal Path Algorithms and Implementation？of Block Transporter Planning System," Journal of the Society？of Naval Architects of Korea, Vol. 53, No. 2, pp. 115-126,？Apr. 2016. DOI: 10.3744/snak.2016.53.2.115

원문보기 상세보기
Michael Junger, Gerhard Reinelt, and Giovanni Rinaldi, "The？traveling salesman problem," Handbooks in operations research？and management science, Vol. 7, pp.225-330, 1995. DOI:？10.1016/S0927-0507(05)80121-5
Edsger Wybe Dijkstra, "A note on two problems in connexion？with graphs," Edsger Wybe Dijkstra: His Life, Work, and Legacy,？pp. 287-290, July 2022. DOI: 10.1145/3544585.3544600

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증