A Centroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem


  • Kwangcheol Shin
  • Sangyong Han


Vehicle routing problem, heuristics, cluster-first route-second


The vehicle routing problem (VRP) is famous as a nondeterministic polynomial-time hard problem. This study proposes a centroid-based heuristic algorithm to solve the capacitated VRP in polynomial time. The proposed algorithm consists of three phases: cluster construction, cluster adjustment, and route establishment. At the cluster construction phase, the farthest node (customer) among un-clustered nodes is selected as a seed to form a cluster. The notion of the geometrical centre of a cluster is introduced in this study to be utilized at the cluster construction and the cluster adjustment phases. The proposed algorithm has a polynomial time complexity of O(n2.2). Experimental results on Augerat benchmark dataset show that the proposed 3-phase approach can result in smaller distances than the Sweep algorithm in more cases.


Download data is not yet available.

Author Biographies

Kwangcheol Shin

Department of Computer Science
Korea Advanced Institute of Science and Technology (KAIST)
119, Moonji-Ro, Yuseong-Gu, Daejeon, 305-732, Korea

Sangyong Han

School of Computer Science and Engineering
Chung-Ang University
221 Heuksuk-Dong, Dongjak-Gu, Seoul, 156-756, Korea




How to Cite

Shin, K., & Han, S. (2012). A Centroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem. COMPUTING AND INFORMATICS, 30(4), 721–732. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/192