TY - JOUR AU - Shin, Kwangcheol AU - Han, Sangyong PY - 2012/01/26 Y2 - 2024/03/29 TI - A Centroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem JF - COMPUTING AND INFORMATICS JA - Comput. Inform. VL - 30 IS - 4 SE - Articles DO - UR - https://www.cai.sk/ojs/index.php/cai/article/view/192 SP - 721-732 AB - 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. ER -