[논문]효과적인 차량 선적을 위한 공간 배치의 최적화 기법

차주형; 최진석; 배유수; 우영운

doi:10.6109/jkiice.2020.24.2.186

효과적인 차량 선적을 위한 공간 배치의 최적화 기법
An Optimization Method of Spatial Placement for Effective Vehicle Loading 원문보기

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.24 no.2, 2020년, pp.186 - 191

차주형 (Division of Creative Software Eng., Dong-eui University) , 최진석 (Logistics System Institute, Total Soft Bank Ltd.) , 배유수 (Logistics System Institute, Total Soft Bank Ltd.) , 우영운 (Division of Creative Software Eng., Dong-eui University)

초록
AI-Helper

이 논문에서는 차량 운반선에서 선적 계획과 하적 계획에 따른 차량 선적을 효과적으로 진행하기 위하여, 선박 내 데크에 차량을 효율적으로 배치하는 최적화 기법을 제안하였다. 이를 위해, 선박의 공간 정보를 나타내는 XML 데이터의 변환, 병합 및 분할 알고리즘, 유전자 알고리즘을 활용하였으며, 또한 최적화된 차량 배치 결과를 시각화하는 기능까지 구현하였다. 기존의 전형적인 유전자 알고리즘에서 사용되는 선택, 교차, 변이, 엘리트 보존 등의 기법들을 활용하였으며, 특히 차량의 선적을 위한 선박 공간을 병합 및 분할하는 기법을 함께 제안하여 차량 배치 최적화 기법을 제안하였다. 실험 결과, 기존의 유전자 알고리즘만으로 최적화하기 힘든 부분에 제안한 병합 및 분할 기법을 적용하는 것이 최적화 과정에 효과적이었음을 확인할 수 있었다. 또한, 시각화 기법을 통해 차량 배치 결과를 도면 형태로 보여줌으로써 배치 결과의 효율성을 전문가가 쉽게 판단할 수 있도록 하였다.

Abstract ▼ AI-Helper

In this paper, we proposed an optimization technique for efficiently placing vehicles on decks in a vehicle-carrying ship to efficiently handle loading and unloading. For this purpose, we utilized the transformation method of the XML data representing the ship's spatial information, merging and branching algorithm and genetic algorithm, and implemented the function to visualize the optimized vehicle placement results. The techniques of selection, crossover, mutation, and elite preservation, which are used in the conventional genetic algorithms, are used. In particular, the vehicle placement optimization method is proposed by merging and branching the ship space for the vehicle loading. The experimental results show that the proposed merging and branching method is effective for the optimization process that is difficult to optimize with the existing genetic algorithm alone. In addition, visualization results show vehicle layout results in the form of drawings so that experts can easily determine the efficiency of the layout results.

주제어

표/그림 (9)

그림 Fig. 1 Overall Deck Shapes of a Car-carrying Ship
그림 Fig. 2 Comparison of Number of Loadable Cars by No Margin and 1m Margin
그림 Fig. 3 Sail Route of a Car-carrying Ship
그림 Fig. 4 Organized Data for Loading and Unloading of Cars Using POD, POL Lining Up
그림 Fig. 5 XML Data Generated by Dividing 1^st Floor of the Decks by 5AEU × 5AEU Block Size
그림 Fig. 6 Merging Process
그림 Fig. 7 Branching Process
그림 Fig. 8 Results of Optimization on Car Placement in a Car-carrying Ship having Multi-deck
그림 Fig. 9 Results of Optimization on Car Placement by 10AEU × 10AEU and 15AEU × 15AEU

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

따라서 이 논문에서는 이러한 제약 사항을 극복하고 데크를 여러 개 갖는 대형 차량 운반선을 위한 인공지능기법을 제안하였다. 먼저, 차량 운반선에서 선적 계획과하적 계획에 따른 차량 선적을 효과적으로 진행하기 위하여, 선박 내 데크에 차량을 효율적으로 배치하기 위하여 선박의 공간 정보를 나타내는 XML 데이터를 변환하는 모듈을 구현하였고, 선박 데크 공간의 효율적인 처리를 위한 병합 및 분할 알고리즘을 제안하였으며, 유전자 알고리즘을 활용하여 차량 배치를 최적화였다.

제안 방법

기본적인 유전자 알고리즘을 그대로 사용하게 될 경우, 차량 선적 최적화를 1AEU 단위로 하게 되므로 많은 시간이 소요될 것으로 예상하여 새로운 기법을 제안하였다. 즉, 1AEU 단위로 최적화하는 것이 아닌 10AEU × 10AEU 또는 5AEU × 5AEU 크기와 같이 영역, 즉 구역별로 공간을 크게 만들어 빠른 시간 내에 최적해를 찾아내는 알고리즘을 제안하였다.
더욱이 최적화된 차량 배치 결과를 시각화하는 기능을 구현하여 배치 결과의 효율성을 전문가가 쉽게 판단할 수 있도록 하였다. 기존의 전형적인 유전자 알고리즘에서 사용되는 선택, 교차, 변이, 엘리트 보존 등의 기법들을 그대로 활용하였으며, 특히 차량의 선적을 위한 선박 공간을 병합 및 분할하는 새로운 기법을 제안하였다. 2장에서는 이 논문에서 제안한 차량 배치 최적화 기법에 대해 제시하고, 3장에서는 실험결과를 제시하였다.
제안하였다. 먼저, 차량 운반선에서 선적 계획과하적 계획에 따른 차량 선적을 효과적으로 진행하기 위하여, 선박 내 데크에 차량을 효율적으로 배치하기 위하여 선박의 공간 정보를 나타내는 XML 데이터를 변환하는 모듈을 구현하였고, 선박 데크 공간의 효율적인 처리를 위한 병합 및 분할 알고리즘을 제안하였으며, 유전자 알고리즘을 활용하여 차량 배치를 최적화였다. 더욱이 최적화된 차량 배치 결과를 시각화하는 기능을 구현하여 배치 결과의 효율성을 전문가가 쉽게 판단할 수 있도록 하였다.
병합 및 분할 알고리즘과 유전자 알고리즘을 활용하여 차량 배치를 최적화하는 알고리즘을 제안하고 실험 결과를 제시하였다. 최적화를 위한 진화 과정을 통하여 최선의 적합도 값으로 바뀌는 변화를 확인할 수 있었다.
이 논문에서 실험을 위하여 차량 배치 공간을 최적화하기 위한 유전자 알고리즘에서 적합도 함수는 사용된 블록의 수에 따라서 값의 변화가 생기도록 수식 (1) 과같이 정의하였다. 이 수식에서 ExitFloor는 선적한 화물이 바깥으로 나가는 층을 의미하며, _의 Floor 층을 뺀 값을 제곱하여 먼 지역의 POD 화물이 Exit Floor에 가까이에 있다면 매우 높은 가중치를 주었으며, 사용되지 않은 블록이 많으면 500이라는 추가 가중치를 부여하였다.
이 논문에서 제안한 유전자 알고리즘에서의 교차 역할을 대신하는 제안 알고리즘은 공간의 병합 및 분할 기법을 활용하는 것이다. 공간의 병합 및 분할을 반복하여 공간 최적화를 찾아가는 이 알고리즘을 이 논문에서는 병합 및 분할(merging and branching) 알고리즘이라고 명명하였다.
각 그림에서, 색이 옅은 공간은 차량이 일부만 배치되어 적은 양을 차지하고 있다는 것을 의미하며, 색이 짙은 공간은 차량이 많이 배치되어 거의 모든 공간을 차지하고 있다는 것을 의미한다. 이 논문에서의 배치 최적화 기법은 이 병합 및 분할 알고리즘이 핵심이며, 이 알고리즘과 유전자 알고리즘의 적합도 함수값을 함께 이용하여 최적화를 진행하게 된다.
즉, 1AEU 단위로 최적화하는 것이 아닌 10AEU × 10AEU 또는 5AEU × 5AEU 크기와 같이 영역, 즉 구역별로 공간을 크게 만들어 빠른 시간 내에 최적해를 찾아내는 알고리즘을 제안하였다. 예를 들어 1층 데크의 공간을 5AEU × 5AEU 크기로 영역을 분할하였다고 가정할 경우에 분할된 공간의 좌표와 선적 가능 차량 대수를 변환한 XML 데이터는 그림 5와 같이 생성된다.
즉, 병합 및 분할 알고리즘을 활용하고 거리가 가까울수록 좋은 유전자를 의미하는 적합도 함수를 통하여 최적화된 차량 선적 데이터를 찾아내는 알고리즘을 구현하였다. 구현된 알고리즘에 의한 최적화 과정의 1세대 결과와 1,000세대 진화 결과는 그림 8과 같다.
특히 선박에서 화물 배치를 자동으로 최적화하기 위해 유전자 알고리즘을 활용한 기법도 제안된 바 있다[3]. 하지만 이 논문에서 제안된 기법에서는 규칙적인 사각형 형태의 대형 화물을 하나의 데크에 배치하기 위한 기법으로서 여러 개의 데크를 갖는 차량 운반선 등에는 적용하기 어려운 점이 있다.

이론/모형

선박 공간에 대한 차량 선적을 최적화하기 위하여 딥러닝을 사용을 시도하였으나 샘플 데이터의 부족으로 인하여 적합도(fitness) 함수를 활용하여 최적의 모습을 찾아가는 알고리즘인 유전자 알고리즘을 선택하게 되었다[7].

성능/효과

먼저, 차량 운반선에서 선적 계획과하적 계획에 따른 차량 선적을 효과적으로 진행하기 위하여, 선박 내 데크에 차량을 효율적으로 배치하기 위하여 선박의 공간 정보를 나타내는 XML 데이터를 변환하는 모듈을 구현하였고, 선박 데크 공간의 효율적인 처리를 위한 병합 및 분할 알고리즘을 제안하였으며, 유전자 알고리즘을 활용하여 차량 배치를 최적화였다. 더욱이 최적화된 차량 배치 결과를 시각화하는 기능을 구현하여 배치 결과의 효율성을 전문가가 쉽게 판단할 수 있도록 하였다. 기존의 전형적인 유전자 알고리즘에서 사용되는 선택, 교차, 변이, 엘리트 보존 등의 기법들을 그대로 활용하였으며, 특히 차량의 선적을 위한 선박 공간을 병합 및 분할하는 새로운 기법을 제안하였다.
제시하였다. 최적화를 위한 진화 과정을 통하여 최선의 적합도 값으로 바뀌는 변화를 확인할 수 있었다. 향후 적합도 함수를 더욱 개선하여 제약 조건, 상태 조건과 같이 여러 가지의 상태와 필요한 조건을 추가 구현한다면 더욱 우수한 결과를 나타낼 수 있을 것으로 예상한다.

후속연구

기법도 제안된 바 있다[4]. 그러나 이 논문에서 제안된 기법 또한 대상 공간도 사각형이고 화물 파렛트 또한 사각형으로 가장 단순한 형태에서의 최적화 문제로 접근하고 있기 때문에, 일반적인 배치 최적화 문제에는 적용하기 어렵다는 단점을 가지고 있다.
향후 적합도 함수를 더욱 개선하여 제약 조건, 상태 조건과 같이 여러 가지의 상태와 필요한 조건을 추가 구현한다면 더욱 우수한 결과를 나타낼 수 있을 것으로 예상한다. 또한, 병합 및 분할 알고리즘에서 공간 위치를 강제적으로 교환하는 알고리즘 등을 추가하는 방식을 통해 부족한 공간은 그 공간만큼 분할하도록 개선한다면 더욱 빠르게 우수한 유전자를 찾아갈 수 있을 것으로 예상한다.
최적화를 위한 진화 과정을 통하여 최선의 적합도 값으로 바뀌는 변화를 확인할 수 있었다. 향후 적합도 함수를 더욱 개선하여 제약 조건, 상태 조건과 같이 여러 가지의 상태와 필요한 조건을 추가 구현한다면 더욱 우수한 결과를 나타낼 수 있을 것으로 예상한다. 또한, 병합 및 분할 알고리즘에서 공간 위치를 강제적으로 교환하는 알고리즘 등을 추가하는 방식을 통해 부족한 공간은 그 공간만큼 분할하도록 개선한다면 더욱 빠르게 우수한 유전자를 찾아갈 수 있을 것으로 예상한다.

참고문헌 (8)

Shipping, Hyundai Glovis [Internet]. Available: https://www.glovis.net/Eng/business/contentsid/304/index.do.
S. K. Kim, K. S. Kim, J. W. Hong, S. Ha, and M. I. Roh, "Integrated Method for Optimal Layout of Offshore Plant Topside," Proc. of The Proceedings of Korean CAD/CAM Winter Conference, pp. 287-291, 2015.
K. Y. Lee, S. N. Han, and M. I. Roh, "Optimal Compartment Layout Design for a Naval Ship Using an Improved Genetic Algorithm," Marine Technology, vol.39, no.3, pp. 159-169, Jul. 2002.
J.-H. Park, D.-M. Kim, and G.-T. Yeo, "A Study on the Estimation of Optimal Storage Area in the Distribution Center," Journal of Digital Convergence, vol.17, no.7, pp. 59-71, Jul. 2019(https://doi.org/10.14400/JDC.2019.17.7. 059).

원문보기 상세보기
XML Tutorial, w3schools.com. [Internet]. Available : www.w3schools.com/xml/.
Shipping Terms, Carry Cargo International. [Internet]. Available : www.carrycargo.com/shipping-terms/.
J. H. Cha, Y. W. Woo, and I. Lee, "An Effective Method for Generating Images Using Genetic Algorithm," Journal of the Korea Institute of Information and Communication Engineering, vol. 23, no. 8, pp. 896-902, Aug. 2019 (https://doi.org/10.6109/jkiice.2019.23.8.896).

원문보기 상세보기
A. J. Umbarkar, and P. D. Sheth, "Crossover Operators in Genetic Algorithms: A Review," ICTACT Journal on Soft Computing, vol.6, no.1, pp. 1083-1092, Oct. 2015 (https://doi.org/10.21917/ijsc.2015.0150).

상세보기

저자의 다른 논문 :

표제어: 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

연합인증