[논문]Quadratic 복수 컨테이너 적재 문제에 관한 연구

여기태; 석상문; 이상욱

문제 정의

결국, 이는 탐색공간의 범위를 과도하게 확장시킴으로서 탐색 성능을 급격하게 떨어뜨린다. 따라서 본 논문에서는 이러한 단점을 개선할 수 있는 방법을 제안한다.
따라서 본 연구에서는 다수의 목적지를 가지는 상품들을 컨테이너에 적재할 경우 어떻게 하면 화주가 더 많은 이득을 얻을 수 있는지에 대한 문제를 다루다
따라서, 본 논문에서는 기존 NetKey 방법이 지닌 중복성 (redundancy)를 줄이기 위해 새로운 인코딩 및 디코딩 방법을 사용하며, 성능을 향상시키기 위해 휴리스틱 방법을 결합하는 새로운 방법을 제안한다. 비록 제안하는 방법이 해의 개선을 위해 사용하는 휴리스틱 방법으로 인해 더 많은 겨]산 시간을 필요로 하지만 제안하는 방법이 기존의 NetKey 방법보다 성능면에서 훨씬 더 우수한 결과를 찾을 수 있음을 비교 실험을 통해 보인다.
본 논문에서는 Quadratic 복수 컨테이너 적재 문제(QMCPP)를 해결하기 위한 효율적인 유전 알고리즘을 제안하였다. 제안하는 방법은 해 표현법으로 개선된 랜덤 키 표현법(random key representa- tion)을 사용하고 균등 교차 연산자와 상호교환 변이 연산자를 유전 연산자로 사용하였으며, 해의 개선을 위해 두 가지 휴리스틱 기법을 사용하였다.
본 논문에서는 제안하는 방법을 통해 구해진 해를 보다 더 개선시키기 위한 두 가지 지역 탐색법을 제안한다.
비록 제안하는 방법이 해의 개선을 위해 사용하는 휴리스틱 방법으로 인해 더 많은 겨]산 시간을 필요로 하지만 제안하는 방법이 기존의 NetKey 방법보다 성능면에서 훨씬 더 우수한 결과를 찾을 수 있음을 비교 실험을 통해 보인다. 이와 더불어 기존에 QMCPP를 위해 개발된 방법들과의 비교를 통해 제안하는 방법의 성능을 보이는 것을 본 연구의 주목적으로.하고 있다.

제안 방법

QMCPP는 Hiley and Julstrom[4]에 의해 처음 소개되었으며, Hiley와 Justrome QMCPP를 해결하기 위해 상대적 가치 밀도(relative value den- sity)라는 개념을 사용하는 3가지 방법을 제안하였다. 상대적 가치 밀도는 다음과 같이 정의된다.
Sarac 와 Sipahioglu 또한 유전 알고리즘(SS-GA)을 사용하였다. SS-GA에서는 Hiley와 Julstrom이 제안한 HJ- GA를 사용한 해 표현법을 사용하였으며, 성능을 개선하기 위해 특별히 고안된 교차 연산자 및 변이 연산자를 사용하여 비교실험을 수행하였다.
al.[7] 이 걸침나무 문제를 해결하기 위해 제안한 네트워크 랜덤 7] (Network Random Key : Net~ Key) 방법을 개선하는 새로운 방법을 사용하는 유전 알고리즘을 제안한다.
위해 사용하였다. 그리고 벤치마크문제는 衆와 %값이 0이 아닌 비율에 따라 d = 0.25와 d = 0.75 로 크게 2가지 그룹으로 나누어지며, 각 컨테이너의 최대 허용가능 용량은 기존의 연구들처럼 모든 상품의 용량(叫, )의 합의 80%를 컨테이너의 개수 C로 나눈 값으로 설정하였다.
기존의 연구들에서는 종료 조건으로 200번의 반복회수(generation limit)를 사용하였지만, 일반적으로 이 조건은 유전 알고리즘이 수렴하기에는 충분하지 않을 뿐만 아니라 제안하는 방법 역시 이 조건에서 충분히 수렴하지 못하였다. 그리고 본 논문의 목적이 기존의 방법들이 찾아낸 해보다 우수한 해를 찾는 것이기 때문에 기존의 방법과 달리 제안하는 방법이 충분히 수렴할 수 있도록 1, 000세대(generation) 동안 해의 개선이 없을 경우 종료시키도록 종료조건을 설정하였다. 하지만, 기존의 방법들과의 직접적인 비교를 위해 200세대에서의 결과도 함께 보인다.
특히, 각각의 해를 생성할 때 컨테이너의 최대 적재가능량 Cj를 고려하여 모든 제약식을 만족하도록 생성한다. 그리고 여기에 특별히 고안된 교차 연산자(crossover operator) 와변이 연산자(mutation operator)를 적용하였다.
따라서, 본 논문에서 제안하는 방법은 해 표현을 위해 상품만을 고려하는 방법을 제안한다. [그림 1] 은 기존의 NetKey 방법과 제안하는 개선된 NetKey 방법을 보여준다.
그리고 이렇게 생성된 해가 해집단 내에 동일한 해가 있는지를 확인하고 없을 경우에만 해집단에 포함시킨다. 마지막으로 이렇게 생성된 해집단에 특별하게 고안된 교차연산자(crossover operator)와 두 가지 다른 변이 연산자(mutation operator)# 적용하여 탐색공간을 탐색한다.
본 논문에서는 기존의 연구들이 벤치마크(bench- rmrk)문제[12]로 사용한 문제를 보다 정확한 비교실험을 위해 사용하였다. 그리고 벤치마크문제는 衆와 %값이 0이 아닌 비율에 따라 d = 0.
1절에서 일반적인 NetKey 방법을 설명하기 위해 간단한 예를 소개하였다. 여기서 NetKey 방법을 위해 사용한 것이 각 상품의 적재 가능한 총 경우의 수 즉, 총 가능한 에지를 기초로 해 표현을 하였다. 하지만, 이럴 경우 상품이 한 개 증가할 때마다 에지의 개수는 컨테이너의 개수인 C개 증가하고 컨테이너가 한 개 증가할 때마다 에지의 개수는 상품의 개수인 n개 증가하게 된다.

이론/모형

QMCPP를 위한 또 다른 접근법은 Singh and Baghel[9〕에 의해 제안된 안정상태 해집단 대체 전략(steady-state population replacement methodX 가지는 그룹핑 유전 알고리즘(Grouping Genetic Algorithm : SB-GGA) 이다, SB-GGA는 우선 각각의 해 (chromosome)를 Hiley와 Jidstrom이 제안한 탐욕적 휴리스틱 방법(greedy heuristic)을 변형한 방법을 이용하여 해집단을 생성한다. 구체적으로, 각 컨테이너의 첫 번째 상품을 가장 상대적 가치 밀도 값이 큰 상품을 선택하는 것이 아니라 랜덤하게 선택하고 아직 적재되지 않은 상품들 중에서 상대적 가치 밀도 값이 가장 큰 상품들을 선택함으로써 컨테이너를 채워나간다.
Sarac 와 Sipahioglu 또한 유전 알고리즘(SS-GA)을 사용하였다. SS-GA에서는 Hiley와 Julstrom이 제안한 HJ- GA를 사용한 해 표현법을 사용하였으며, 성능을 개선하기 위해 특별히 고안된 교차 연산자 및 변이 연산자를 사용하여 비교실험을 수행하였다.
논문에서는 디코딩 방법으로 R瓦![6]이 복수 컨테이너 적재 문제(the multiple contains- packing problem : MCPP) 를 위해 제안했던 방법을 사용한다.
하지만 복수 배낭 문제 (Multiple Knape sack Problem: M福)는 많은 연구들에서 서로 다른 문제를 지칭하는 것으로 사용되어 오면서 연구자들에게 혼돈을 초래했었다. 따라서 QMKP 또한 MKP 로 인해 발생하는 혼돈에서 자유롭지 못하기 때문에 본 논문에서는 이러한 혼돈을 피하기 위해 QMKP 대신 기존의 복수 컨테이너 적재 문제(Multiple Container Packing Problem : MCPP) 의 특수한 경우인 Quadratic 복수 컨테이너 적재 문제(Quadratic Multiple Container Packing Problem : QMCPP) 라는 용어를 사용한다.
어떤 제약도 없다. 따라서 기존의 랜덤 키 표현법에서 가장 우수한 결과를 주는 것으로 알려진 균등 교차 연산자(uniform crossover)와 상호 교환 변이연산자(reciprocal exchange mutation)를 사용하였다[切.
제안하였다. 제안하는 방법은 해 표현법으로 개선된 랜덤 키 표현법(random key representa- tion)을 사용하고 균등 교차 연산자와 상호교환 변이 연산자를 유전 연산자로 사용하였으며, 해의 개선을 위해 두 가지 휴리스틱 기법을 사용하였다.

성능/효과

그리고 d = 0.25에 비해 d = 0.75에서 기존의 해를 휠씬 더 개선시켰으며 이는 제안하는 방법이 상품들 상호간의 의존도가 높은 문제들에서 더 우수한 성능을 보여준다는 것을 의미한다. 이는 해의 개선을 위해 사용한 지역탐색 휴리스틱 기법의 특성 때문이다.
다음은 기존의 연구 결과들과 제안하는 방법의 결과를 비교해 보면, d = 0.25의 경우는 30개의 문제 중에서 11개의 문제에서 제안하는 방법이 200 세대에서 가장 우수했던 결과를 보여주었으며, d = 0.75의 경우에는 19개의 문제에서 제안하는 방법이 200 세대에서 가장 우수했던 결과를 보여주었다. 또한 최종 결과를 비교해 보면, d = 0.
25의 200-5-5, 200느0-1, 么)0-10-3 문제)를 제외하고 모든 경우에서 개선된 유전 알고리즘이 더 우수한 성능을 보였다. 또한 최종 결과들끼리 비교한 결과 d = 0.25인 경우 최소 5.71%, 최대 21.99%, 평균 11.79%, d = 0.75°1 경우 최소 4.8%, 최대 21.57%, 평균 10.52% 의 해의 개선을 달성하였다. 이는 제안하는 방법이 사용하는 인코딩 및 디코딩 방법을 통해 기존의 NetKey 방법에 비해 해의 중복-성 (redundancy)을 줄이고, 기존의 NetKey 방법에서는 적용하기 어려웠던 효과적인 지역탐색 휴리스틱 기법을 결합한 결과로 판단된다.
75의 경우에는 19개의 문제에서 제안하는 방법이 200 세대에서 가장 우수했던 결과를 보여주었다. 또한 최종 결과를 비교해 보면, d = 0.西의 경우는 25 개의 문제에서 d = 0.75의 경우는 모든 문제에서 제안하는 방법이 기존에 찾았던 해 보다도 더 우수한해를 찾아내었다.
또한, 여기서 밑줄로 강조된 부분은 200세대에서 가장 우수했던 결과를 나타내며, 굵은 글씨로 강조된 부분은 최종 결과(Final)에서 가장 우수했던 결과를 나타내고 있다.
이는 해의 개선을 위해 사용한 지역탐색 휴리스틱 기법의 특성 때문이다. 또한, 표준편차(STD) 역시 대부분의 경우에서 최종 평균 결과 대비 2%를 넘지 않았는데, 이는 제안하는 방법이 언제나 안정된 결과 값을 줄 수 있음을 의미한다.
비록 제안하는 방법이 해의 개선을 위해 사용하는 휴리스틱 방법으로 인해 더 많은 겨]산 시간을 필요로 하지만 제안하는 방법이 기존의 NetKey 방법보다 성능면에서 훨씬 더 우수한 결과를 찾을 수 있음을 비교 실험을 통해 보인다. 이와 더불어 기존에 QMCPP를 위해 개발된 방법들과의 비교를 통해 제안하는 방법의 성능을 보이는 것을 본 연구의 주목적으로.
우선 NetKey 방법을 사용하는 유전 알고리즘과 개선된 NetKey 방법을 사용하는 유전 알고리즘 사이의 성능비교를 보면, d = 0.25인 경우뿐만 아니라 d = 0.75인 경우 모두에서 제안하는 개선된 NetKey 방법을 사용하는 유전 알고리즘이 훨씬 우수한 성능을 보이는 것을 확인할 수 있다. 특히, 기존의 NetKey 방법을 사용하는 유전 알고리즘의 최종 결과(Final)와 제안하는 개선된 NetKey 방법을 사용하는 유전 알고리즘의 200세대(200 generation) 의결과를 비교해 보면, 세 경우(d = 0.
위 세 가지 방법들에 대한 비교 실험에서 확률적 언덕 오르기 기법이 평균적으로 가장 우수한 성능을 보였으며, 다음으로 유전 알고리즘, 탐욕적 휴리스틱 방법 순으로 우수한 성능을 보여 주었다. 특히나 유전 알고리즘의 경우는 컨테이너의 개수가 작은 문제들에서 더 좋은 성능을 보였으며, 컨테이너의 개수가 증가할수록 성능이 급격하게 떨어지는 특성을 보여 주었다.
52% 의 해의 개선을 달성하였다. 이는 제안하는 방법이 사용하는 인코딩 및 디코딩 방법을 통해 기존의 NetKey 방법에 비해 해의 중복-성 (redundancy)을 줄이고, 기존의 NetKey 방법에서는 적용하기 어려웠던 효과적인 지역탐색 휴리스틱 기법을 결합한 결과로 판단된다. 하지만, 이렇게 결합된 휴리스틱 기법 때문에 제안하는 방법이 기존의 NetKey 방법에 비해 더 많은 계산시간을 필요로 하였다.
이들 또한 Hiley와 Julstrom의 실험결과와 비교실험을 수행하였는데, SS-GA가 몇몇 문제들에서 알고리즘들 간의 가장 우수한 해들 사이의 차이가 20% 이상 좋은 해를 찾으며, 또한 SS-GA가 컨테이너의 개수가 3 또는 5개인 d = 0.75인 문제보다는 d = 0.25인 문제들에서 더욱 좋은 성능을 보인다는 것을 보여주었다. 여기서, d = 0.
그리고 한국해양수산개발원에 따르면[5] 항만을 통하여 수출 . 입되는 전체 화물 중 수입기준으로 出11년 47%, 次)15년 48%, 2020년 49% 정도가 컨테이너로 운송이 될 것이며, 수출기준으로는 2011년 67%, X15년 72%, 2020년 74% 정도가 컨테이너로 운송이 될 것으로 전망하고 있다.
제안하는 방법의 성능을 평가하기 위해 기존의 연구들이 사용했던 벤치마크문제에서 실험을 수행하여 기존 연구들과 성능을 비교하였는데, 제안하는 방법이 대부분의 문제들에서 비록 계산 시간은 알고리즘의 구조적인 문제로 더 많이 필요로 하였지만 기존의 알려진 가장 우수한 결과보다 더 우수한 결과를 찾을 수 있음을 확인하였다.
특히, SB-(曲를 통해 얻은 평균 해의 성능의 경우는 HJ-GA 및 HJ-SHC의 평균 해의 성능보다 항상 더 우수한 결과를 보여주었다.
75인 경우 모두에서 제안하는 개선된 NetKey 방법을 사용하는 유전 알고리즘이 훨씬 우수한 성능을 보이는 것을 확인할 수 있다. 특히, 기존의 NetKey 방법을 사용하는 유전 알고리즘의 최종 결과(Final)와 제안하는 개선된 NetKey 방법을 사용하는 유전 알고리즘의 200세대(200 generation) 의결과를 비교해 보면, 세 경우(d = 0.25의 200-5-5, 200느0-1, 么)0-10-3 문제)를 제외하고 모든 경우에서 개선된 유전 알고리즘이 더 우수한 성능을 보였다. 또한 최종 결과들끼리 비교한 결과 d = 0.
특히나 유전 알고리즘의 경우는 컨테이너의 개수가 작은 문제들에서 더 좋은 성능을 보였으며, 컨테이너의 개수가 증가할수록 성능이 급격하게 떨어지는 특성을 보여 주었다.
이는 제안하는 방법이 사용하는 인코딩 및 디코딩 방법을 통해 기존의 NetKey 방법에 비해 해의 중복-성 (redundancy)을 줄이고, 기존의 NetKey 방법에서는 적용하기 어려웠던 효과적인 지역탐색 휴리스틱 기법을 결합한 결과로 판단된다. 하지만, 이렇게 결합된 휴리스틱 기법 때문에 제안하는 방법이 기존의 NetKey 방법에 비해 더 많은 계산시간을 필요로 하였다.

후속연구

결론적으로 제안하는 알고리즘이 현재 Quadratic 복수 컨테이너 문제를 해결하는 알고리즘들 중에서 가장 우수한 것으로 판단되며, 따라서 앞으로 이 문제를 다룰 경우 가장 우선적으로 고려되어야 할 것으로 판단된다.
때문이다. 하지만, 컨테이너 적재문제는 아주 급박하게 처리를 해야 하는 문제가 아닐 뿐만 아니라 컨테이너에 적재되는 상품이 많을수록 화주 입장에서는 이득이기 때문에 기존의 방법과 비교해 제안하는 방법이 더 매력적일 수 있을 것으로 판단된다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

Quadratic 복수 컨테이너 적재 문제에 관한 연구
A Study on the Quadratic Multiple Container Packing Problem 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

후속연구

참고문헌 (12)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

Quadratic 복수 컨테이너 적재 문제에 관한 연구 A Study on the Quadratic Multiple Container Packing Problem 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

후속연구

참고문헌 (12)

이 논문을 인용한 문헌

저자의 다른 논문 :

여기태 (99) 이상욱 (10)

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

Quadratic 복수 컨테이너 적재 문제에 관한 연구
A Study on the Quadratic Multiple Container Packing Problem 원문보기

AI 본문요약
AI-Helper