A Centroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem
Keywords:
Vehicle routing problem, heuristics, cluster-first route-secondAbstract
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.Downloads
Download data is not yet available.
Downloads
Published
2012-01-26
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
Issue
Section
Articles