[논문]차량 경로 스케줄링 문제 해결을 위한 멀티 비용 함수를 갖는 개미 군집 최적화 기법 기반의 휴리스틱

홍명덕; 유영훈; 조근식

차량 경로 스케줄링 문제 해결을 위한 멀티 비용 함수를 갖는 개미 군집 최적화 기법 기반의 휴리스틱
The Heuristic based on the Ant Colony Optimization using by the Multi-Cost Function to Solve the Vehicle Routing and Scheduling Problem 원문보기

홍명덕 (인하대학교 일반대학원 정보공학과) , 유영훈 (인하대학교 공과대학 컴퓨터정보공학부) , 조근식 (인하대학교 공과대학 컴퓨터정보공학부)

본 연구는 차량 경로 스케줄링 문제(VRSPTW, the Vehicle Routing and Scheduling Problem with Time Window)를 해결하기 위하여, 멀티 비용 함수(Multi Cost Function)를 갖는 개미 군집 최적화(Ant Colony Optimization)을 이용한 휴리스틱을 제안하였다. 멀티 비용 함수는 각 개미가 다음 고객 노드로 이동하기 위해 비용을 평가할 때 거리, 요구량, 각도, 시간제약에 대해 서로 다른 가중치를 반영하여 우수한 초기 경로를 구할 수 있도록 한다. 본 연구의 실험결과에서 제안된 휴리스틱이 Solomon I1 휴리스틱과 기회시간이 반영된 하이브리드 휴리스틱보다 효율적으로 최근사 해를 얻을 수 있음을 보였다.

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

문제 정의

본 연구에서는 개미 군집 최적화(ACO, Ant Colony Optimization) 기법을 사용하여 VRSPTW를 해결하고자 한다.
본 연구에서는 개미 군집 최적화의 장점인 전역적 탐색정보 능력을 이용하여 해를 유도하는 최근접 이웃 휴리스틱을 적용한 알고리즘을 소개한다.
본 연구에서는 멀티 비용 함수가 적용된 최근접 이웃 휴리스틱을 이용하여 적은 수의 개미로 개미 군집 최적화의 특징을 사용하는 방법을 제안한다.

가설 설정

1) 모든 차량은 동종의 차량이다.
10) 차량은 물류 창고에서 동시에 출발하며 물류 창고 서비스 종료 시간 내에 복귀해야 한다.
5) 화물의 적재 및 하역에 소요되는 시간은 고려되지 않는다.
7) 모든 고객 노드들은 서비스를 받아야 한다.
8) 한 차량의 총 이동거리에 대한 제약은 없다.
9) 모든 고객 노드들은 서비스가 가능한 시간대를 가진다.

제안 방법

각각의 개미들은 하나의 차량과 동일하다. 각 개미들은 현재 경로에 포함되지 않고 제약조건을 만족하는 노드들에 대하여 비용 함수를 통해 비용을 구한다. 구해진 비용 중 높은 비용을 갖는 노드를 결정하여 해당 개미의 경로에 포함하는 과정을 반복적으로 수행하여 경로를 구성한다.
단계 2-2 : 경로 개선

개미들이 구축한 경로를 2-opt과 Relocate를 수행하여 이웃해 집단을 생성 후 가장 우수한 이웃해로 대체한다.
각 개미들은 현재 경로에 포함되지 않고 제약조건을 만족하는 노드들에 대하여 비용 함수를 통해 비용을 구한다. 구해진 비용 중 높은 비용을 갖는 노드를 결정하여 해당 개미의 경로에 포함하는 과정을 반복적으로 수행하여 경로를 구성한다.
본 연구에서는 초기 경로 구성 시 최근접 이웃 휴리스틱(NNH, Nearest Neighbor Heuristic)을 사용하고, 다른 노드를 선택 할 때 멀티 비용 함수(Multi Cost Function)를 통해 가장 높은 비용을 가진 경로를 선택한다. 보다 다양한 해를 도출하기 위해 매 초기 경로 구축 시 사용되는 멀티 비용 함수에 비용 가중치(Cost Weight)를 적용한다.
알고리즘 실행을 위해 비용 가중치 목록 생성과 초기 페로몬 매트리스를 생성한다.
여러 가지 구성형 해법 중에서 비교적 개념이 쉬우면서 빠르게 해를 구축할 수 있는 효과적인 기법인 최근접 이웃 휴리스틱을 이용하며 다음에 방문할 노드를 결정하는 비용 함수를 설계하여 그 비용들 중 가장 큰 비용을 갖는 노드를 방문하는 과정을 반복하여 해를 구축한다.
보다 다양한 해를 도출하기 위해 매 초기 경로 구축 시 사용되는 멀티 비용 함수에 비용 가중치(Cost Weight)를 적용한다. 이로 인해 부적절한 해가 나오는 것을 방지하며, 반복 과정 시 페로몬 갱신 규칙을 적용함으로써 적은 수의 인공 개미와 반복 과정을 통해 좋은 최적 근사 해를 구한다.
전 단계에서 개선된 경로와 현재까지 가장 우수한 경로를 이용하여 페로몬 업데이트를 한다.

대상 데이터

실험 데이터는 R, C, RC 유형으로 구분되며 R은 노드의 분포도가 임의로 설정되었고 C은 노드의 분포도가 군집으로 설정되었고 RC은 R과 C을 혼합형으로 설정되어 있다. 또한 1, 2 유형으로 구분되며 1은 차량의 용적량이 작고 거점의 배송 시간이 짧으며 배송처의 시간 제약이 좁게 설정되어 있고 2는 차량의 용적량이 크고 거점의 배송 시간이 길며 배송처의 시간 제약이 넓게 설정되어 있다.

이론/모형

비용 함수가 반영된 최근접 이웃 휴리스틱를 이용하여 생성된 초기해를 2-opt 알고리즘을 적용하여 해를 개선한다.
실험은 Solomon[3]의 실험 데이터와 동일한 테스트 데이터 집합을 사용하였다.

성능/효과

2) 운행되는 차량의 비용은 총 운행 거리에 비례한다.
3) 각 차량은 최대 적재용량까지 적재가 가능하며 모든 차량의 적재 용량은 동일하다.
4) 고객 노드들 간의 차량 운행속도는 동일하다.
6) 차량의 출발 및 종착은 물류 창고에서만 이루어지며, 단일 물류 창고만 존재한다.
계산량이 지수적으로 증가하는 VRSPTW 문제를 해결하기 위해, 멀티 비용 가중치가 적용된 최근접 이웃 휴리스틱을 이용한 향상된 개미 군집 최적화를 제안하고 그 효율성을 보였다. 멀티 비용 가중치를 통해 매 경로를 구성할 때 마다 해당 개미가 어떤 비용에 더 큰 비중을 두는지는 다양하게 하여 여러 초기해를 얻을 수 있었다.
멀티 비용 가중치를 통해 매 경로를 구성할 때 마다 해당 개미가 어떤 비용에 더 큰 비중을 두는지는 다양하게 하여 여러 초기해를 얻을 수 있었다. 또한 제안 휴리스틱에서 페로몬 증발률을 0.8로 하였을 때 가장 유리하였으며, 고객 노드의 위치가 임의 분산 되어있고, 차량의 용적량이 크고, 거점의 배송 시간이 길며, 시간 제약이 넓게 설정된 데이터 유형에서 더 유용함을 보였다. 하지만 결국 모든 데이터 유형에서 최적 값을 찾을 수 없었는데, 배송처의 시간 제약의 출현 빈도가 낮아질수록 해가 좋지 않았음을 확인할 수 있었다.
표시된 값은 각 유형별 모든 데이터 집합에 대한 평균값이다. 실험의 결과는 R2와 RC2형에서 다른 휴리스틱이 구해진 결과보다 좋은 결과를 보여준다.
여기서 ρ는 페로몬 증발률(Pheromone Evaporation)이다. 알고리즘의 종료 조건은 초기화 과정에서 생성되는 멀티 비용 가중치 목록의 개수(3⁵= 243회) 만큼 반복 후 종료한다.
표 2는 실험에서 사용될 페로몬 증발률(ρ)을 결정하기 위해 ρ을 0.1부터 0.9까지 0.1씩 증가해 가며 실험하여 모든 실험데이터의 평균을 구하여 비교한 결과로 0.8의 값을 지정한 경우 가장 우수한 해를 도출하는 것을 확인하였다.
8로 하였을 때 가장 유리하였으며, 고객 노드의 위치가 임의 분산 되어있고, 차량의 용적량이 크고, 거점의 배송 시간이 길며, 시간 제약이 넓게 설정된 데이터 유형에서 더 유용함을 보였다. 하지만 결국 모든 데이터 유형에서 최적 값을 찾을 수 없었는데, 배송처의 시간 제약의 출현 빈도가 낮아질수록 해가 좋지 않았음을 확인할 수 있었다. 따라서 이를 극복할 수 있도록 해를 향상 시킬 수 있는 다른 경로 개선 알고리즘을 적용하거나 멀티 비용 가중치가 적용된 최근접 이웃 휴리스틱이 보다 다양하고 우수한 초기해를 가질 수 있도록 하는 방법에 대한 연구가 필요하다.

후속연구

하지만 결국 모든 데이터 유형에서 최적 값을 찾을 수 없었는데, 배송처의 시간 제약의 출현 빈도가 낮아질수록 해가 좋지 않았음을 확인할 수 있었다. 따라서 이를 극복할 수 있도록 해를 향상 시킬 수 있는 다른 경로 개선 알고리즘을 적용하거나 멀티 비용 가중치가 적용된 최근접 이웃 휴리스틱이 보다 다양하고 우수한 초기해를 가질 수 있도록 하는 방법에 대한 연구가 필요하다.

핵심어

질문

논문에서 추출한 답변

차량 경로 모형에 대한 제약 조건에는 어떤 것들이 있는가?

1) 모든 차량은 동종의 차량이다. 2) 운행되는 차량의 비용은 총 운행 거리에 비례한다. 3) 각 차량은 최대 적재용량까지 적재가 가능하며 모든 차량의 적재 용량은 동일하다. 4) 고객 노드들 간의 차량 운행속도는 동일하다. 5) 화물의 적재 및 하역에 소요되는 시간은 고려되지 않는다. 6) 차량의 출발 및 종착은 물류 창고에서만 이루어지며, 단일 물류 창고만 존재한다. 7) 모든 고객 노드들은 서비스를 받아야 한다. 8) 한 차량의 총 이동거리에 대한 제약은 없다. 9) 모든 고객 노드들은 서비스가 가능한 시간대를 가진다. 10) 차량은 물류 창고에서 동시에 출발하며 물류 창고 서비스 종료 시간 내에 복귀해야 한다.

휴리스틱 기법의 특징은 무엇인가?

완전 최적화 기법은 모든 가능한 경로를 조사해보는 방법으로 문제에 따라 최적 해를 구하는 시간이 오래 걸리거나, 최적 해를 구한다는 보장이 없을 수도 있다. 휴리스틱 기법은 모든 가능한 경로를 조사하지 않고 다양한 지역 탐색(Local Search) 기법을 제어하여 여러 해를 생성하고 지능적으로 정보를 구축하여 최근사 해를 도출하는 방법으로 최근사해(Nearest Optimal Solution)를 효율적으로 얻는 것을 목적으로 한다.

Solomon의 삽입 기법이란 무엇인가?

이러한 차량 경로 스케줄링 문제를 해결하기 위한 휴리스틱으로는 Solomon의 삽입 기법(Insertion Heuristic)이제안된 이후로 많은 해법들이 연구되고 있다. Solomon의 삽입 기법은 특정한 기준 값을 계산하여 일부 구성된 부분경로에 아직 경로에 포함되지 않은 고객지점 들을 하나씩 추가하면서 해를 완성하는 기법이다[3].

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

연합인증

차량 경로 스케줄링 문제 해결을 위한 멀티 비용 함수를 갖는 개미 군집 최적화 기법 기반의 휴리스틱
The Heuristic based on the Ant Colony Optimization using by the Multi-Cost Function to Solve the Vehicle Routing and Scheduling Problem 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

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

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

선택된 텍스트

연합인증

차량 경로 스케줄링 문제 해결을 위한 멀티 비용 함수를 갖는 개미 군집 최적화 기법 기반의 휴리스틱 The Heuristic based on the Ant Colony Optimization using by the Multi-Cost Function to Solve the Vehicle Routing and Scheduling Problem 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

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

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

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

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

선택된 텍스트

차량 경로 스케줄링 문제 해결을 위한 멀티 비용 함수를 갖는 개미 군집 최적화 기법 기반의 휴리스틱
The Heuristic based on the Ant Colony Optimization using by the Multi-Cost Function to Solve the Vehicle Routing and Scheduling Problem 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper