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

Document Type : Research Article

Authors

• M. Afsharirad
• A. Hashemi Borzabadi

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

10.22067/ijnao.2025.93411.1643

Abstract

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(n2 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. 

Keywords

• Capacitated vehicle routing problem
• K-means algorithm
• Convex hull
• Ant colony optimization

Main Subjects

• Computational Mathematics

---

References

[1] Baldacci, R., Christofides, N. and Mingozzi, A. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, Math. Program., 115 (2008), 351–385.
[2] Barreto, S., Ferreira, C., Paixao, J. and Santos, B.S. Using clustering analysis in a capacitated location-routing problem, Eur. J. Oper. Res., 179 (2007), 968–977.
[3] Bell, J. and McMullen, P. Ant colony optimization techniques for the vehicle routing problem, Adv. Eng. Inform., 18 (2004), 41–48.
[4] Bodin, L.D. and Golden, B.L. Classification in vehicle routing and scheduling, Networks, 11 (1981), 97–108.
[5] Bodin, L.D. The state of the art in the routing and scheduling of vehicles and crews, Urban Mass Transp. Adm., Vol. 1, 1983.
[6] Bruwer, F. Petal-shaped clustering for the capacitated vehicle routing problem, Master Thesis, Univ. Witwatersrand, Johannesburg, 2018.
[7] Buhrmann, J.H., Campbell, I. and Ali, M. A capacitated clustering heuristic for large datasets, Proc. Int. Conf. Ind. Eng. Oper. Manag., 2018.
[8] Carlsson, J., Ge, D., Subramaniam, A., Wu, A. and Ye, Y. Solving minmax multi-depot vehicle routing problem, Lect. Glob. Optim., 55 (2009), 31–46.
[9] Chen, A., Gu, X. and Gao, Z. Two-phase algorithm to multiple depots vehicle routing problem with soft time windows, IOP Conf. Ser.: Earth Environ. Sci., 2020.

[10] Christofides, N., Mignozzi, A. and Toth, P. The vehicle routing problem, In: Christofides, N. (ed.), Combinatorial Optimization, Wiley, Hoboken (1979), 315–338.
[11] Cinar, D., Gakis, K. and Pardalos, P.M. A 2-phase constructive algorithm for cumulative vehicle routing problems with limited duration, Expert Syst. Appl., 56 (2016), 48–58.
[12] Clarke, G. and Wright, J.R. Scheduling of vehicles from a central depot to a number of delivery points, Oper. Res., 12(4) (1964), 568–581.
[13] Comert, S., Yazgan, H., Sertvuran, I. and Sengul, H. A new approach for solution of vehicle routing problem with hard time window: An application in a supermarket chain, Indian Acad. Sci., 42(12) (2017), 2067–2080.
[14] Dang, S., Liu, Y., Luo, Z., Liu, Z. and Shi, J., Survey of the routing problem for cooperated trucks and drones., Drones, 8(10) (2024), 550.
[15] Dantzig, G. and Ramser, J., The truck dispatching problem, Manag. Sci., 6(1) (1959), 80–91.
[16] Dewinter, M., Vandeviver, Ch., Vander Beken, T. and Witlox, F., Analyzing the police patrol routing problem: A review, ISPRS Int. J. Geo-Inf., 9(3) (2020), 157.
[17] Ding, N., Li, M. and Hao, J., A two-phase approach to routing a mixed fleet with intermediate depots, Mathematics, 11(8) (2023), 1924.
[18] Dondo, R. and Cerda, J., A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows, Eur. J. Oper. Res., 176 (2007), 1478–1507.
[19] Euchi, J. and Saduk, A., Hybrid Genetic-Sweep algorithm to solve the vehicle routing problem with drones, Phys. Commun., 44 (2020), 101236.
[20] Fatemi-Anaraki, S., Mokhtarzadeh, M., Rabbani, M. and Abdolhamidi, D., A hybrid of K-means and genetic algorithm to solve a bi-objective green delivery and pick-up problem, J. Ind. Prod. Eng., (2021), 1–12.

[21] Fisher, M.L. and Jaikumar, R., A generalized assignment heuristic for vehicle routing, Networks, 11(2) (1981), 109–124.
[22] Gillett, B. and Miller, L., A heuristic algorithm for the vehicle-dispatch problem, Oper. Res., 22(2) (1974), 340–349.
[23] Golden, B., Bodin, L., Doyle, T. and Stewart, W., JR., Approximate traveling salesman algorithms, Oper. Res., 28(3), part 2 (1979), 694–711.
[24] Goutham, M., Menon, M., Garrow, S. and Stockar, S., A convex hull cheapest insertion heuristic for the non-euclidean TSP. arXiv preprint arXiv:2302.06582, 2023.
[25] Hammami, F., Rekik, M. and Coelho, L.C., A hybrid adaptive large neighborhood search heuristic for the team orienteering problem, Comput. Oper. Res., 123 (2020), 105034.
[26] Hertrich, C., Hungerländer, P. and Truden, C., Sweep algorithms for the capacitated vehicle routing problem with structured time windows, Oper. Res. Proc. 2018, (2019), 127–133.
[27] Imran, N. and Won, M., VRPD-DT: Vehicle routing problem with drones under dynamically changing traffic conditions, arXiv preprint arXiv:2404.09065 (2024).
[28] Jones, J. and Adamatzky, A., Computation of the traveling salesman problem by a sShrinking blob, Nat. Comput., 13(1) (2014), 1–16.
[29] Laporte, G., and Nobert, Y., A branch and bound algorithm for the capacitated vehicle routing problem, Oper.-Res.-Spektrum, 5(2) (1983), 77–85.
[30] Larson, R. and Odoni, A., Urban operations research, Prentice Hall, Englewood Cliffs, N.J., 1981.
[31] Liao, T.-Y., On-line vehicle routing problems for carbon emissions reduction, Comput.-Aided Civ. Infrastruct. Eng., 32(12) (2017), 1047–1063. 

[32] Liu, Q., Xu, P., Wu, Y., and Shen, T., A two-stage algorithm for vehicle routing problem with charging relief in post-disaster, IET. Intel. Transp. Sys., 45(3) (2023), 123–137.
[33] Luo, J., and Chen, M.R., Multi-phase modified shuffled frog leaping algorithm with extremal optimization for the MDVRP and the MDVRPTW, Comput. Ind. Eng., 72 (2014), 84–97.
[34] Mahmud, N., and Haque, M.M., Solving multiple depot vehicle routing problem (MDVRP) using genetic algorithm, 2019 Int. Conf. Electr. Comput. Commun. Eng., (2019), 1–6.
[35] Marinakis Y., Marinaki M. and Migdalas A., Variants and formulations of the vehicle routing problem, Open Probl. Optim. Data Anal., Springer Optim. Its Appl., (2018), 91–127.
[36] Meira, L., Martins, P., Menzori, M. and Zeni, G., Multi-objective vehicle routing problem applied to large scale post office deliveries, arXiv preprint arXiv:1801.00712, (2017).
[37] Nadizadeh, A., Sahraeian, R., Sabzevarizadeh, A. and Homayouni, S.M., Using greedy clustering method to solve capacitated location-routing problem, Afr. J. Bus. Manag., 5(17) (2011), 7499–7506.
[38] Nallusamy, R., Duraiswamy, K., Dhalanaksmi, R. and Parthiban, P., Optimization of multiple vehicle routing problems using approximation algorithms, Int. J. Eng. Sci. Technol., 1(3) (2009), 129–135.
[39] Narasimha, K., Ant colony optimization technique to solve min-max multi depot vehicle routing problem, Master Thesis, Natl. Inst. Technol. Karnataka, India, 2011.
[40] Negreiros, M. and Palhano, A., The capacitated centred clustering problem, Comput. Oper. Res., 33(6) (2006), 1639–1663.
[41] Nuriyeva, F. and Kutucu, H., A convex hull based algorithm for solving the traveling salesman problem, TWMS J. App. Eng. Math. (2025).

[42] Nurkahyo, G., Alias, R., Shamsuddin, S.M. and Noor, Md., Sweep algorithm in vehicle routing problem for public transport, J. Antarabangsa, 2 (2002), 51–64.
[43] Poot, A., Kant, G. and Wagelmans, A., A savings based method for real-life vehicle routing problems, J. Oper. Res. Soc., 53 (2002), 57–68.
[44] Pourmohammadreza, N. and Jokar, M.R.A., A novel two-phase approach for optimization of the last-mile delivery problem with service options, Sustainability, 15(10), (2023), 8098.
[45] Ralphs, T.K., Kopman, L., Pulleyblank, W.R. and Trotter, L.E., JR., On the capacitated vehicle routing problem, Math. Program., 94 (2003), 343–359.
[46] Renaud, J., Laporte, G. and Boctor, F., A Tabu search heuristic for the multi-depot vehicle routing problem, Comput. Oper. Res., 23(3) (1996), 229–235.
[47] Rossit, D., Vigo, D., Tohme, F. and Frutos, M., Improving visual attrac-tiveness in capacitated vehicle routing problems: A heuristic algorithm, XVIII Lat.-Iberoam. Conf. Oper. Res.-CLAIO, 749, 2016.
[48] Sariklis, D. and Powell, S., A heuristic method for the open vehicle routing problem, J. Oper. Res. Soc., 51(5) (2000), 564–573.
[49] Sehta, N. and Thakar, U., Capacitated vehicle routing problem: A solution using convex hull based sweep algorithm and genetic algorithm, In AIP Conference Proceedings (Vol. 2705, No. 1). AIP Publishing, 2023.
[50] Simchi-Levi, D. and Bramel, J., The logic of logistics: Theory, algorithms and applications for logistics management, Springer-Verlag, New York, 2nd ed., 1997.
[51] Singanamala, P., Reddy, K. and Venkataramaiah, P., Solution to a multi depot vehicle routing problem using K-means algorithm, Clarke and Wright algorithm and ant colony optimization, Int. J. Appl. Eng. Res., 13(21) (2018), 15236–15246.

[52] Solomon, M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper. Res., 35(2) (1987), 254–265.
[53] Solomon, M.M. and Desrosiers, J., Time window constrained routing and scheduling problems, Transp. Sci., 22(1) (1988), 1–13.
[54] Soto-Concha, R., Escobar, J.W., Morillo-Torres, D. and Linfati, R., The vehicle-routing problem with satellites utilization: A systematic review of the literature., Mathematics, 13(7) (2025), 1–29.
[55] Stewart, W.R., Computational comparison of five heuristic algorithms for the Euclidean traveling salesman problem, Lect. Notes Econ. Math. Syst., 199 (1982), Springer, Berlin, Heidelberg.
[56] Thibbotuwawa, A., Bocewicz, G., Nielsen, P. and Banaszak, Z., Unmanned aerial vehicle routing problems: A literature review, Appl. Sci., 10(13) (2020), 4504.
[57] Toth, P. and Vigo, D., Branch-and-bound algorithms for the capacitated VRP, SIAM, (2002), 29–51.
[58] Toth, P. and Vigo, D., Eds., Vehicle routing: Problems, methods, and applications, SIAM, 2014.
[59] Wang, Z. and Sheu, J.B., Vehicle routing problem with drones, Transp. Res. Part B Methodol., 122 (2019), 350–364.