Abstract

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.

Keywords

Cite this article

@article{cai-1978,
  author  = {Kwangcheol Shin and Sangyong Han},
  title   = {A Centroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem},
  journal = {Computing and Informatics},
  volume  = {30},
  number  = {4},
  pages   = {721--732},
  year    = {2011},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2011/4/a-centroid-based-heuristic-algorithm-for-the-capacitated-vehicle-routing-problem/}
}
Download .bib