DIGITAL LIBRARY ARCHIVE
HOME > DIGITAL LIBRARY ARCHIVE
< Previous   List   Next >  
Hybrid Heuristic Applied by the Opportunity Time to Solve the Vehicle Routing and Scheduling Problem with Time Window
Full-text Download
Young Hoon Yu (School of Information Engineering, Inha University)
Sang Jin Cha (School of Information Engineering, Inha University)
Geun Sik Jo (School of Computer and Information Engineering, Inha University)
Vol. 15, No. 3, Page: 137 ~ 150
Keywords
VRSPTW(Vehicle Routing and Scheduling Problem with Time Window), Insertion Heuristic, Tabu Search, Opportunity Time, Opportunity Time, 2-Opt Algorithm
Abstract
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.
Show/Hide Detailed Information in Korean
시간 제약을 가지는 차량 경로 스케줄링 문제 해결을 위한 기회시간 반영 하이브리드 휴리스틱
유영훈 (인하대학교 일반대학원 정보공학과)
차상진 (인하대학교 일반대학원 정보공학과)
조근식 (인하대학교 공과대학 컴퓨터정보공학부)
Abstract
본 연구는 시간 제약조건을 가지는 차량 경로 탐색과 스케줄링 문제(VRSPTW, the Vehicle Routing and Scheduling Problem with Time Window)를 해결하기 위하여, 기회시간(Opportunity time)을 반영한 하이브리드 휴리스틱을 제안하였다. 기회시간은 각 고객 노드에서 요구하는 하역 서비스를 수행 한 뒤에도 남아 있는 여유시간이다. 제안된 휴리스틱은 기회시간에 대한 제약조건을 추가하고, 기회시간을 고려한 비용 평가함수를 삽입 전략에 적용함으로써 초기 해를 구하였다. 또한 고객 노드 교환에 의한 타부 탐색 전략에도 기회시간을 반영함으로써 해를 개선 시켰다. 마지막으로 지리적, 시간적, 용량적으로 다양한 데이터 유형들에 대하여 각각 효과적으로 최적 해를 구할 수 있는 초기 경로 생성 전략들을 소개하고 비교하였다. 본 연구의 실험에서는 제안된 휴리스틱이 Solomon I1 휴리스틱 보다 효율적으로 최근사 해를 얻을 수 있음을 보였다.
Cite this article
JIIS Style
Yu, Y. H., S. J. Cha, and G. S. Jo, "Hybrid Heuristic Applied by the Opportunity Time to Solve the Vehicle Routing and Scheduling Problem with Time Window ", Journal of Intelligence and Information Systems, Vol. 15, No. 3 (2009), 137~150.

IEEE Style
Young Hoon Yu, Sang Jin Cha, and Geun Sik Jo, "Hybrid Heuristic Applied by the Opportunity Time to Solve the Vehicle Routing and Scheduling Problem with Time Window ", Journal of Intelligence and Information Systems, vol. 15, no. 3, pp. 137~150, 2009.

ACM Style
Yu, Y. H., Cha, S. J., and Jo, G. S., 2009. Hybrid Heuristic Applied by the Opportunity Time to Solve the Vehicle Routing and Scheduling Problem with Time Window . Journal of Intelligence and Information Systems. 15, 3, 137--150.
Export Formats : BiBTeX, EndNote

Warning: include(/home/hosting_users/ev_jiisonline/www/admin/archive/advancedSearch.php) [function.include]: failed to open stream: No such file or directory in /home/hosting_users/ev_jiisonline/www/archive/detail.php on line 429

Warning: include() [function.include]: Failed opening '/home/hosting_users/ev_jiisonline/www/admin/archive/advancedSearch.php' for inclusion (include_path='.:/usr/local/php/lib/php') in /home/hosting_users/ev_jiisonline/www/archive/detail.php on line 429
@article{Yu:JIIS:2009:378,
author = {Yu, Young Hoon and Cha, Sang Jin and Jo, Geun Sik},
title = {Hybrid Heuristic Applied by the Opportunity Time to Solve the Vehicle Routing and Scheduling Problem with Time Window },
journal = {Journal of Intelligence and Information Systems},
issue_date = {September 2009},
volume = {15},
number = {3},
month = Sep,
year = {2009},
issn = {2288-4866},
pages = {137--150},
url = {},
doi = {},
publisher = {Korea Intelligent Information System Society},
address = {Seoul, Republic of Korea},
keywords = { VRSPTW(Vehicle Routing and Scheduling Problem with Time Window), Insertion Heuristic, Tabu Search, Opportunity Time, Opportunity Time and 2-Opt Algorithm },
}
%0 Journal Article
%1 378
%A Young Hoon Yu
%A Sang Jin Cha
%A Geun Sik Jo
%T Hybrid Heuristic Applied by the Opportunity Time to Solve the Vehicle Routing and Scheduling Problem with Time Window
%J Journal of Intelligence and Information Systems
%@ 2288-4866
%V 15
%N 3
%P 137-150
%D 2009
%R
%I Korea Intelligent Information System Society