Convex-hull based two-phase algorithm to solve capacitated vehicle routing problem

The goal of this paper is to present a two-phase convex hull-based algorithm for the capacitated vehicle routing problem (CVRP), consisting of clustering and routing phases. First, a K-means-based algorithm is proposed for the clustering phase, where the centroids are updated according to the convex hull of the assigned points. Furthermore, a convex-hull-based algorithm is suggested for the routing phase, which iteratively inserts unrouted points into the convex hull. To improve the routes, an ant colony optimization algorithm is applied. It is shown that the proposed method has a time complexity of order o(n۲ log n), where n is the number of customers. For performance evaluation, we utilize CVRP benchmark samples and compare the results to those of other two-phase CVRP algorithms. The proposed clustering method combined with common routing techniques, as well as the K-means clustering method paired with the proposed routing approach, yields highly favorable results in some instances. Moreover, the proposed two-phase method outperforms other approaches in certain instances.

کلیدواژه ها:

Capacitated vehicle routing problem ، k-means algorithm ، Convex hull ، Ant Colony Optimization