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

Year, pages: 2011, 721 - 732

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.

Shin, K., Han, S. 2011. A Centroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem. In Computing and Informatics, vol. 30, no.4, pp. 721-732. 1335-9150.

Shin, K., Han, S. (2011). A Centroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem. Computing and Informatics, 30(4), 721-732. 1335-9150.