[논문]시간 제약을 가지는 차량 경로 스케줄링 문제 해결을 위한 기회시간 반영 하이브리드 휴리스틱

유영훈; 차상진; 조근식

시간 제약을 가지는 차량 경로 스케줄링 문제 해결을 위한 기회시간 반영 하이브리드 휴리스틱
Hybrid Heuristic Applied by the Opportunity Time to Solve the Vehicle Routing and Scheduling Problem with Time Window 원문보기

지능정보연구 = Journal of intelligence and information systems, v.15 no.3, 2009년, pp.137 - 150

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

초록
AI-Helper

본 연구는 시간 제약조건을 가지는 차량 경로 탐색과 스케줄링 문제(VRSPTW, the Vehicle Routing and Scheduling Problem with Time Window)를 해결하기 위하여, 기회시간(Opportunity time)을 반영한 하이브리드 휴리스틱을 제안하였다. 기회시간은 각 고객 노드에서 요구하는 하역 서비스를 수행 한 뒤에도 남아 있는 여유시간이다. 제안된 휴리스틱은 기회시간에 대한 제약조건을 추가하고, 기회시간을 고려한 비용 평가함수를 삽입 전략에 적용함으로써 초기 해를 구하였다. 또한 고객 노드 교환에 의한 타부 탐색 전략에도 기회시간을 반영함으로써 해를 개선 시켰다. 마지막으로 지리적, 시간적, 용량적으로 다양한 데이터 유형들에 대하여 각각 효과적으로 최적 해를 구할 수 있는 초기 경로 생성 전략들을 소개하고 비교하였다. 본 연구의 실험에서는 제안된 휴리스틱이 Solomon I1 휴리스틱 보다 효율적으로 최근사 해를 얻을 수 있음을 보였다.

Abstract ▼ AI-Helper

This paper proposes the hybrid heuristic method to apply the opportunity time to solve the vehicle routing and scheduling problem with time constraints(VRSPTW). The opportunity time indicates the idle time which remains after the vehicle performs the unloading service required by each customer's node. In this proposed heuristic, we add the constraints to VRSPTW model for the opportunity time. We also obtain the initial solution by applying the cost evaluation function to the insertion strategy considering the opportunity time. In addition, we improve the former result by applying the opportunity time to the tabu search strategy by swapping the customer's node. Finally, we suggest the construction strategies of initial routing which can efficiently acquire the nearest optimal solution from various types of data in terms of geographical condition, scheduling horizon and vehicle capacity. Our experiment show that our heuristic can get the nearest optimal solution more efficiently than the Solomon's I1 heuristic.

주제어

AI 본문요약
AI-Helper

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

문제 정의

그러나 이 방법은 문제에 따라서 최적 해를 구하는 시간이 오래 걸리거나, 최적 해를 구한다는 보장이 없을 수도 있다. 메타 휴리스틱 기법은 최근사 해(Nearest Optimal Solution)를 효율적으로 얻는 것을 목적으로 한다. 이를 위해 다른 분야의 개념들을 결합하여 정보를 구축하고 학습함으로써 지능적으로 탐색공간을 탐색한다.
본 연구는 VRSPTW 문제를 해결하기 위해, 기회시간을 고려한 비용 평가 함수를 적용한 삽입 전략을 수립하였다. 이는 고객의 종료시간 내에 고객 요구량을 배송할 수 있는 시간적 가능성 정도를 나타낸다.
본 연구에서는 기회 시간을 반영한 삽입 전략으로 생성된 각 경로들에 대하여, 기회시간을 반영한 2-opt기반의 타부 탐색 전략을 적용함으로써 해를 개선시키고자 하였다.

가설 설정

이 문제에서의 차량 대수는 주어진 고객 노드 수만큼 사용할 수 있지만, 구성된 경로에서의 고객 요구 총 용량은 경로에 투입되어야 하는 차량의 적재 용량보다 클 수 없다. 또한, 모든 차량의 적재용량은 모두 동일한 것으로 가정한다.
따라서, 이전 고객 방문지 i-1에서 출발하여 i에 도착할 경우, 고객 i로의 도착시각 ai 는 고객 i의 업무 시간보다 일찍 도착한다면 i의 시작시각 s_i가 되며, 그렇지 않으면 i-1으로의 도착시각과 i-1에서의 하역 서비스 시간 l_i, 두 고객 i-1과 i사이의 이동시간을 더한 시간이 된다. 여기서, 두 고객 간의 이동 시간은 직접적인 연결 거리인 유클리디안 거리(Euclidean distance)를 사용하기 때문에 이동 거리와 동일한 것으로 가정한다.

제안 방법

먼저, 주어진 차량과 고객 정보들로 고객 리스트와 거리 테이블을 생성하고, 초기 경로를 생성하기 위한 전략과 비용 평가 함수 적용 전략을 설정한다. 각각 4가지의 초기 경로 생성전략과 2가지의 비용평가 함수를 사용하였다. 초기 경로 생성 전략으로는 기회시간을 최소로 가지는 고객 노드를 우선 선택하여 초기 경로를 생성하는 방법과 3시 방향을 기준으로 시계 반대방향으로 각도 회전(sweep)하여 형성된 클러스터의 중간에 위치한 고객 노드를 선택하는 방법(Gillet and Miller, 1974; 고준택 외 2, 2009), 고객의 요구 종료시간이 가장 일찍 끝나는 고객 노드를 선택하는 방법(Solomon M.
이는 R2나 RC2와 같이 시간 제약을 고려해야할 가변적 요인이 큰 경우에 기회 시간을 고려한 비용 평가가 효과적임을 보여준다. 또한 비교적 빠른 실행시간 내에 해를 구하였다.
이는 고객의 종료시간 내에 고객 요구량을 배송할 수 있는 시간적 가능성 정도를 나타낸다. 또한, 초기 경로를 생성할 때, 고객 노드를 선택하기 위한 몇 가지 전략들을 소개하였으며, 각 전략에 대한 라우팅 결과를 보였다.
많은 계산 복잡성을 가지는 VRSPTW문제를 해결하기 위해, 기존 Solomon I1 휴리스틱(Solomon M., 1987)을 개선하여 기회 시간을 고려한 비용 평가 함수를 반영한 하이브리드 삽입 휴리스틱을 제안하고 그 효율성을 보였다.
삽입 휴리스틱의 결과인 각 경로는 제안된 타부 탐색 전략에 의해 다시 최적화된다. 본 연구의 타부 탐색 전략은 표준 타부 탐색 전략(Golver et al., 1993)과 2-Opt(Baker and Schaffer, 1988)를 응용하여 시간제약과 기회시간을 고려할 수 있도록 확장 되었다. <표 3>과 같이 경로 상의 두 고객 노드를 선택 한 뒤, 교환할 경로가 타부 리스트 상에 존재하지 않으면 식 (15)가 만족하는지 확인 하고, 만족하면 비용 평가 식 (16)에 의거 비용을 평가한다.
, 1987), 거점에서 가장 멀리 떨어진 고객 노드를 우선 선택하여 초기 경로를 구성하는 방법을 각각 적용하였다. 비용평가 함수로는 기회시간을 고려한 평가함수와 그렇지 않은 함수를 각각 적용하였다. 삽입 전략에 의해 수행된 결과를 가지고 타부 전략을 사용하여 해를 개선시키며, 개선된 해들 중 가장 좋은 해를 최종 해로 선정한다.
기회시간은 각 고객 노드에서 요구되는 하역 서비스를 수행 한 뒤에도 남아 있는 여유시간이다. 이 기회시간이 반영된 추가 제약조건과 비용 평가 함수를 삽입 전략에 우선 적용함으로써 경로 생성을 위해 요구되는 차량 수를 줄였으며, 각 생성된 경로들에 대해서는 기회시간을 평가하여 타부 탐색을 수행함으로써 해를 개선 시켰다. 개선된 해는 고객 노드의 지리적 위치가 비교적 임의 분산 되어 있으며, 시간 제약은 범위가 크고, 차량이 처리해야할 용량이 클 경우에 나타났다.
삽입 전략에 의해 수행된 결과를 가지고 타부 전략을 사용하여 해를 개선시키며, 개선된 해들 중 가장 좋은 해를 최종 해로 선정한다. 이때, 기회 시간은 삽입과 타부 탐색 전략의 제약조건 뿐만 아니라 삽입 평가함수로도 적용하였다.
메타 휴리스틱 기법은 최근사 해(Nearest Optimal Solution)를 효율적으로 얻는 것을 목적으로 한다. 이를 위해 다른 분야의 개념들을 결합하여 정보를 구축하고 학습함으로써 지능적으로 탐색공간을 탐색한다. 이때에 내부 휴리스틱들을 제어하여 반복적으로 생성된 해(iterative generation process)들 중 최근사해를 산출해 낸다.

이론/모형

), 대기시간(w)과 기회 시간(r)이 있다. 본 연구에서는 Solomon이 고려한 비용 평가 요소(Solomon M., 1987)인 거리와 스케줄 시간뿐만 아니라 기회 시간도 함께 고려하였다.
실험은 Solomon의 실험 데이터와 동일한 테스트 데이터 집합을 사용하였다(Christofides et al., 1979; Solomon M., 1987). <그림 3>과 같이 이 데이터는 100개의 고객노드가 지역적으로 군집된 C 형, 임의 위치로 분산된 R형, C와 R이 혼합된 RC 형으로 구분되며, 시간 제약의 범위가 짧고 차량용적량이 작은 경우엔 1(C1, R1, RC1)로, 그렇지 않은 경우엔 2(C2, R2, RC2)로 표현된 6가지 유형을 가진다.
각각 4가지의 초기 경로 생성전략과 2가지의 비용평가 함수를 사용하였다. 초기 경로 생성 전략으로는 기회시간을 최소로 가지는 고객 노드를 우선 선택하여 초기 경로를 생성하는 방법과 3시 방향을 기준으로 시계 반대방향으로 각도 회전(sweep)하여 형성된 클러스터의 중간에 위치한 고객 노드를 선택하는 방법(Gillet and Miller, 1974; 고준택 외 2, 2009), 고객의 요구 종료시간이 가장 일찍 끝나는 고객 노드를 선택하는 방법(Solomon M., 1987), 거점에서 가장 멀리 떨어진 고객 노드를 우선 선택하여 초기 경로를 구성하는 방법을 각각 적용하였다. 비용평가 함수로는 기회시간을 고려한 평가함수와 그렇지 않은 함수를 각각 적용하였다.

성능/효과

이 기회시간이 반영된 추가 제약조건과 비용 평가 함수를 삽입 전략에 우선 적용함으로써 경로 생성을 위해 요구되는 차량 수를 줄였으며, 각 생성된 경로들에 대해서는 기회시간을 평가하여 타부 탐색을 수행함으로써 해를 개선 시켰다. 개선된 해는 고객 노드의 지리적 위치가 비교적 임의 분산 되어 있으며, 시간 제약은 범위가 크고, 차량이 처리해야할 용량이 클 경우에 나타났다. 또한 각 데이터 유형에 대한 초기 경로 생성 전략들을 평가하고 각 유형에 효과적인 초기 경로 생성 전략들을 보였다.
개선된 해는 고객 노드의 지리적 위치가 비교적 임의 분산 되어 있으며, 시간 제약은 범위가 크고, 차량이 처리해야할 용량이 클 경우에 나타났다. 또한 각 데이터 유형에 대한 초기 경로 생성 전략들을 평가하고 각 유형에 효과적인 초기 경로 생성 전략들을 보였다. 이는 VRSPTW 문제를 해결하기 위한 삽입 전략뿐만 아니라 시간 제약 평가 함수를 사용해야하는 휴리스틱에서 기회시간을 반영한 비용 평가함수는 해 개선 효과를 기대할 수 있을 것이다.
표시된 값은 각 유형별 모든 데이터 집합에 대한 평균값이다. 실험결과는 비교적 지리적으로 임의 분산되어 있으며, 시간 제약 범위가 크고, 차량의 적재 용량이 큰 R2와 RC2형에서 Solomon I1의 비용 평가함수보다 좋은 결과를 보였다. 이는 R2나 RC2와 같이 시간 제약을 고려해야할 가변적 요인이 큰 경우에 기회 시간을 고려한 비용 평가가 효과적임을 보여준다.

후속연구

또한 각 데이터 유형에 대한 초기 경로 생성 전략들을 평가하고 각 유형에 효과적인 초기 경로 생성 전략들을 보였다. 이는 VRSPTW 문제를 해결하기 위한 삽입 전략뿐만 아니라 시간 제약 평가 함수를 사용해야하는 휴리스틱에서 기회시간을 반영한 비용 평가함수는 해 개선 효과를 기대할 수 있을 것이다.
경로 구성에 참여된 고객 노드들은 Vu에서 제거된다. 이후, 현재 구성된 모든 path들에 대하여 V_u에서 삽입 예상 비용이 가장 작은 고객 노드 v를 찾기 위해 제약조건과 삽입 평가함수가 고려된다. 식 (1)～식 (8)에 의해 주어진 제약 조건이 만족하는지 확인하며 모두 만족하면 삽입 예상 비용을 계산한다.

질의응답

핵심어	질문	논문에서 추출한 답변
	차량 경로 문제란 무엇인가?	차량 경로 문제(CVRP, Capacity Vehicle Routing Problem)는 각 고객의 배송 요구량을 최소 이동 비용으로 배송하기 위한 해를 찾는 문제로써 많은 연구자들에 의해 최적해를 찾기 위한 연구가 되어 오고 있다(고준택 외 2, 2009). 그러나, 보다 현실적인 문제에서는 고객의 요구량뿐만 아니라, 고객의 업무 시작과 종료시간 준수도 요구되고 있다.
	NP-Hard 문제를 해결하기 위한 방법으로는 어떤 방법이 있는가?	이러한 문제를 해결하기 위한 방법으로는 크게 완전 최적화 기법(Exact Optimization Method)과 메타 휴리스틱 기법(Meta Heuristic Method)이 있다. 완전 최적화 기법은 모든 가능한 경로를 조사해보는 방법이다.
	VRSPTW란 무엇인가?	그러나, 보다 현실적인 문제에서는 고객의 요구량뿐만 아니라, 고객의 업무 시작과 종료시간 준수도 요구되고 있다. 이처럼, 각 고객에서의 시간 제약뿐만 아니라 요구량을 만족시키면서 최소 이동 비용을 가지는 경로를 구성하기 위한 문제를 VRSPTW(Vehicle Routing and Scheduling Problem with Time Window)라 한다(Bodin L., et al.

참고문헌 (22)

고준택, 유영훈, 조근식, "한정 용량 차량 경로탐색 문제에서 이분시드 검출법에 의한 발견적 해법", 한국지능정보시스템학회 지능정보연구논문지, 15권, 1호(2009), 1-12.
Baker E. K. and Schaffer J. R., Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints, American Journal of Mathematical and Management Sciences Vol.6(1988), 261-300.
Bard J. F., G. Kontoravdis, and G. Yu, "A Branchand-Cut procedure for the vehicle routing problem with time windows", Transportaion Secience, Vol.36, No.2(2002), 250-269
Bodin L., B. Golden, A. Assad, and M. Ball, "Routing and Scheduling of Vehicles and Crews : The State of the Art. Comput", Opns. Res. Vol.10(1983), 62-212.
Christofides N., A. Mingozzi, and P. Toth, "The Vehicle Routing Problem. In Combinatorial Optimizations", John Wiley and Sons, New York, 1979.
Clarke G. and W. Wright, "Scheduling of Vehicles from a Central Depot to A Number of Delivery Points", Operational Research, Vol.12(1964), 568-581.

상세보기
Desrochers M., J. Desrosiers, and M. M. Solomon, "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows", Operations Research, Vol.40(1992), 342-354.

상세보기
Fisher M., and R. Jaikumar, "A Generalized Assignment Heuristic for Vehicle Routing". Networks, Vol.11(1981), 109-124.

상세보기
Gillet B., and L. Miller, "A Heuristic Algorithm for the Vehicle Dispatching Problem", Operations Research Vol.22(1974), 340-349.

상세보기
Glover F., "Tabu Search Part I", ORSA Journal on Computing, Vol.1, No.3(1989), 190-206.

상세보기
Glover F., "Tabu Search Part II", ORSA Journal on Computing, Vol.2, No.1(1990), 4-32.

상세보기
Glover F., and E. Taillard, "A user's guide to tabu search", Annals of Operations Research, Vol.41 No.1(1993), 1-28.

상세보기
Ibrahim H. Osman, and James P. Kelly, METAHEURISTICS : Theory and Applications, Springer, 1 edition, March Vol.31, 1996.
Irnich S. and Villeneuve D., The shortest path problem with k-cycle elimination (k $ge$ 3) : Improving a branch-and-price algorithm for the VRPTW. INFORMS Journal of Computing (2005).
Kolen A., Rinnooy Kan A. H. G., and H. Trienekesn, "Vehicle Routing with Time Windows", Operations Research, Vol.35(1987), 266-273.

상세보기
Lau H. C., Sim M., and K. M. Teo, "Vehicle routing problem with time windows and a limited number of vehicles", Eur. J. Oper. Res., Vol.148(2003), 559-568.

상세보기
Lenstra, J. K., and Rinnooy Kan, A. H. G., "Complexity of vehicle routing and scheduling problems", Networks, Vol.1(1981), 221-227.
Or I., "Traveling Salesman-type Combinatorial Problems and their relation to the Logistics of Blood Banking", Ph.D. thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL. 1976.
Potvin J. Y. and J. M. Rousseau, "An Exchange Heuristic for Routing Problems with Time Windows", Journal of the Operational Research Society, Vol.46(1995), 1433-1446.

상세보기
Savelsbergh M., Private Communication by Alexander Rinnooy Kan. 1984.
Solomon Marius M., "Algorithms for the vehicle routing and scheduling problems with time window constraints", Operations Research, Vol.35, Is., Vol.2(1987), 254-262.

상세보기
Taillard E. D., P. Badeau, M. Gendreau, F. Guertin, and J.-Y. Potvin, "A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows", Te Vsportation Science, Vol.31, No.2(1997), 170-186.

저자의 다른 논문 :

LOADING...

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

연합인증