DIGITAL LIBRARY ARCHIVE
HOME > DIGITAL LIBRARY ARCHIVE
< Previous   List   Next >  
The Bisection Seed Detection Heuristic for Solving the Capacitated Vehicle Routing Problem
Full-text Download
Jun Taek Ko (School of Information Engineering, Inha University)
Young Hoon Yu (School of Information Engineering, Inha University)
Geun Sik Jo (School of Computer and Information Engineering, Inha University )
Vol. 15, No. 1, Page: 1 ~ 14
Keywords
Capacitated Vehicle Routing Problem, Bisection Seed Detection Heuristic, Sweep Algorithm, Exchange Algorithm, Exchange Algorithm
Abstract
The Capacitated Vehicle Routing Problem (CVRP) is the problem that the vehicles stationed at central depot are to be optimally routed to supply customers with demands, satisfying vehicle capacity constraints. The CVRP is the NP-hard as it is a natural generalization of the Traveling Salesman Problem (TSP). In this article, we propose the heuristic algorithm, called the bisection seed detection method, to solve the CVRP. The algorithm is composed of 3-phases. In the first phase, we work out the initial cluster using the improved sweep algorithm. In the next phase, we choose a seed node in each initial cluster by using the bisection seed detection method, and we compose the rout with the nearest node from each seed. At this phase, we compute the regret value to decide the list of priorities for the node assignment. In the final phase, we improve the route result by using the tabu search and exchange algorithm. We compared our heuristic with different heuristics such as the Clark-Wright heuristic and the genetic algorithm. The result of proposed heuristic show that our algorithm can get the nearest optimal value within the shortest execution time comparatively.
Show/Hide Detailed Information in Korean
한정 용량 차량 경로 탐색 문제에서 이분 시드 검출 법에 의한 발견적 해법
고준택 (인하대학교 대학원 정보공학과)
유영훈 (인하대학교 대학원 정보공학과)
조근식 (인하대학교 IT공과대학 컴퓨터정보공학부)
Abstract
본 연구에서는 한정 용량 차량 경로탐색 문제(CVRP, Capacitated Vehicle Routing Problem)에서 이분 시드 검출 방법(Bisection Seed Detection)을 이용한 휴리스틱 알고리즘을 제안하였다. 이 알고리즘은 3단계로 구성된다. 1단계에서는 improved sweep 알고리즘을 이용해서 초기 클러스터를 구성한다. 2단계에서는 1단계에서 얻은 각 클러스터에 대하여 이분 시드 검출 법을 이용해서 seed 노드를 선택하고, regret 값에 따라 각 경로에 고객 노드들을 삽입 함으로서 차량 이동 경로를 생성한다. 3단계에서는 tabu 탐색 방법과 노드 교환 알고리즘(node exchange algorithm)을 이용하여 2단계에서 얻어진 각 경로를 더욱 향상 시킨다. 본 논문의 실험에서는 제안된 휴리스틱이 비교적 빠른 시간 내에 최적 근사 값을 얻을 수 있음을 보였으며, 이는 빠른 실행 시간을 요구하는 실 업무에 유용하다.
Cite this article
JIIS Style
Ko, J. T., Y. H. Yu , and G. S. Jo, "The Bisection Seed Detection Heuristic for Solving the Capacitated Vehicle Routing Problem", Journal of Intelligence and Information Systems, Vol. 15, No. 1 (2009), 1~14.

IEEE Style
Jun Taek Ko, Young Hoon Yu , and Geun Sik Jo, "The Bisection Seed Detection Heuristic for Solving the Capacitated Vehicle Routing Problem", Journal of Intelligence and Information Systems, vol. 15, no. 1, pp. 1~14, 2009.

ACM Style
Ko, J. T., Yu , Y. H., and Jo, G. S., 2009. The Bisection Seed Detection Heuristic for Solving the Capacitated Vehicle Routing Problem. Journal of Intelligence and Information Systems. 15, 1, 1--14.
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{Ko:JIIS:2009:355,
author = {Ko, Jun Taek and Yu , Young Hoon and Jo, Geun Sik},
title = {The Bisection Seed Detection Heuristic for Solving the Capacitated Vehicle Routing Problem},
journal = {Journal of Intelligence and Information Systems},
issue_date = {March 2009},
volume = {15},
number = {1},
month = Mar,
year = {2009},
issn = {2288-4866},
pages = {1--14},
url = {},
doi = {},
publisher = {Korea Intelligent Information System Society},
address = {Seoul, Republic of Korea},
keywords = { Capacitated Vehicle Routing Problem, Bisection Seed Detection Heuristic, Sweep Algorithm, Exchange Algorithm and Exchange Algorithm },
}
%0 Journal Article
%1 355
%A Jun Taek Ko
%A Young Hoon Yu
%A Geun Sik Jo
%T The Bisection Seed Detection Heuristic for Solving the Capacitated Vehicle Routing Problem
%J Journal of Intelligence and Information Systems
%@ 2288-4866
%V 15
%N 1
%P 1-14
%D 2009
%R
%I Korea Intelligent Information System Society