Convex-hull based Two-phase Algorithm to Solve Capacitated Vehicle Routing Problem

Iranian Journal of Numerical Analysis and Optimization

مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 09 تیر 1404

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.2025.93411.1643

نویسندگان

Maria Afsharirad^* ؛ Akbar Hashemi Borzabadi

Department of Applied Mathematics, University of Science and Technology of Mazandaran, Behshahr, P.O. Box: 48518-78195, Mazandaran, Iran.

چکیده

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^2\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