Enhancing Vehicle Routing with Time Windows Solutions via K-means Clustering: A Comparative Study of Elbow and Truck Utilization Methods

Article Sidebar

PDF
Published: Nov 15, 2025
Keywords:
Clustering K-means Routing Problem Time Windows

Main Article Content

Kanokporn Boonjubut
Department of Engineering Management, Faculty of Industrial Technology, Nakhon Ratchasima Rajabhat University, Nakhon Ratchasima, Thailand
Prat Boonsam
Department of Engineering Management, Faculty of Industrial Technology, Nakhon Ratchasima Rajabhat University, Nakhon Ratchasima, Thailand
Sirichai Yodwangjai
Department of Industrial Engineering Technology, College of Industrial Technology, King Mongkut’s University North Bangkok, Bangkok, Thailand

Abstract

The vehicle routing problem with time windows is important in optimizing logistics distribution. For VRPTW optimization, a strategy is used to classify and optimize routes using artificial intelligence methods. Therefore, an improved two-phase algorithm is required to find a solution. Namely, a customer group can be divided into several regions using the K-means algorithm in the first phase, and each region can be decomposed into smaller subgroups according to certain constraints. In the second phase, local search from OR-tools solves the routing problem. In this experiment, two different methods of determining the number of clusters, namely, the elbow method and the truck utilization method, are compared by experimenting with a total of 26 standard instances. The results show that the truck utilization ratio outperforms the elbow method for the K-means algorithm in terms of overall results. The results from this experiment can be highly beneficial for routing, particularly when handling huge amounts of data that need to be subdivided ahead.

Article Details

How to Cite
Boonjubut, K., Boonsam, P. ., & Yodwangjai, S. (2025). Enhancing Vehicle Routing with Time Windows Solutions via K-means Clustering: A Comparative Study of Elbow and Truck Utilization Methods. INTERNATIONAL SCIENTIFIC JOURNAL OF ENGINEERING AND TECHNOLOGY (ISJET), 9(2), 18–29. retrieved from https://ph02.tci-thaijo.org/index.php/isjet/article/view/259271
Issue
Vol. 9 No. 2 (2025): July-December
Section
Research Article
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

เนื้อหาข้อมูล

Author Biographies

Kanokporn Boonjubut, Department of Engineering Management, Faculty of Industrial Technology, Nakhon Ratchasima Rajabhat University, Nakhon Ratchasima, Thailand

Kanokporn Boonjubut is a lecturer in the Department of Engineering Management at Nakhon Rachasima Rajabhat University, Thailand. She received her Ph.D. degree in Functional Control Systems from Shibaura Institute of Technology (SIT), Japan. Her research interests include optimization, logistics, and supply chain management.

Prat Boonsam, Department of Engineering Management, Faculty of Industrial Technology, Nakhon Ratchasima Rajabhat University, Nakhon Ratchasima, Thailand

Prat Boonsam is an Assistant Professor of the Department of Engineering Management at Nakhon Rachasima Rajabhat University, Thailand. He received his Ph.D. in Logistics from the University of the Thai Chamber of Commerce, Thailand. His interests include truck distribution planning and industrial productivity improvement.

Sirichai Yodwangjai, Department of Industrial Engineering Technology, College of Industrial Technology, King Mongkut’s University North Bangkok, Bangkok, Thailand

Sirichai Yodwangjai is an Assistant Professor in the Department of Industrial Engineering Technology, College of Industrial Technology, King Mongkut’s University  North Bangkok, Thailand. He received a Ph.D. from Naresuan University, Phitsanulok, Thailand. His research interests are optimization, metaheuristics, logistics, and supply chain.

References

P. Toth and D. Vigo, Vehicle Routing: Problems, Methods, and Applications, 2nd ed, Philadelphia, PA: SIAM, 2014, pp. 1-8.

M. Haonan, Y. C. He, M. Huang, Y. Wen, Y. Cheng, and Y. Jin, “Application of K-means clustering algorithms in optimizing logistics distribution routes,” in Proc. 6th Int. Conf. Systems and Informatics (ICSAI), 2019, pp. 1466-1470.

R. G. Dondo and J. Cerda, “A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows,” Eur. J. Oper. Res., vol. 176, no. 3, pp. 1478-1507, Feb. 2007, http://dx.doi.org/10.1016/j.ejor.2004.07.077

C. Ren, “Research on VRPTW optimizing based on k-means clustering and IGA for electronic commerce,” in Proc. 3rd IEEE Conf. Ind. Electron. Appl., 2008, pp. 61-66.

M. Schneider, A. Stenger, and D. Goeke, “The electric vehicle-routing problem with time windows and recharging stations,” Transp. Sci., vol. 48, no. 4, pp. 500-520, Mar. 2014, https://doi.org/10.1287/trsc.2013.0490

A. F. L. Villalba and E. C. G. L. Rotta, “Clustering and heuristics algorithm for the vehicle routing problem with time windows,” Int. J. Ind. Eng. Comput., vol. 13, no. 2, pp. 165-184, 2022, https://doi.org/10.5267/j.ijiec.2021.12.003

G. D. Konstantakopoulos, S. P. Gayialis, and E. P. Kechagias, “Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification,” Oper. Res. (Lond.), vol. 22, no. 3, pp. 2033-2062, Sep. 2020, https://doi.org/10.1007/s12351-020-00600-7

L. Moccia, J.-F. Cordeau, and G. Laporte, “An incremental tabu search heuristic for the generalized vehicle routing problem with time windows,” J. Oper. Res. Soc., vol. 63, no. 2, pp. 232-244, Feb. 2012, https://doi.org/10.1057/jors.2011.25

Y. Wang, L. Wang, G. Chen, Z. Cai, Y. Zhou, and L. Xing, “An improved ant colony optimization algorithm to the periodic vehicle routing problem with time window and service choice,” Swarm Evol. Comput., vol. 55, p. 100675, Jun. 2020, https://doi.org/10.1016/j.swevo.2020.100675

S. S. Khan and A. Ahmad, “Cluster center initialization algorithm for K-means clustering,” Pattern Recognit. Lett., vol. 25, no. 11, pp. 1293-1302, Aug. 2004, https://doi.org/10.1016/j.patrec.2004.04.007

R. Chunyu and W. Xiaobo, “Research on VRP optimizing based on hierarchy clustering and IGA under common distribution,” in Proc. 2006 Int. Conf. Comput. Intell. Secur., 2006, pp. 143-146. https://doi.org/10.1109/ICCIAS2006.294108

K. C. Tan, L. H. Lee, Q. L. Zhu, and K. Ou, “Heuristic methods for vehicle routing problem with time windows,” Artif. Intell. Eng., vol. 15, no. 3, pp. 281-295, Jul. 2001, https://doi.org/10.1016/S0954-1810(01)00005-X

S. E. Comert, H. R. Yazgan, S. Kır, and F. Yener, “A cluster first-route second approach for a capacitated vehicle routing problem: A case study,” Int. J. Procurement Manage., vol. 11, no. 4, p. 399, Jan. 2018, https://doi.org/10.1504/IJPM.2018.092766

R. L. Thorndike, “Who Belongs in the Family?,” Psychometrika, vol. 18, no. 4, pp. 267-276, Dec. 1953, https://doi.org/10.1007/BF02289263

N. Bertagnolli, “Elbow method and finding the right number of clusters.” Nicolas Bertagnolli, 2015. [Online]. Available: https://www.nbertagnolli.com/jekyll/update/2015/12/10/Elbow.html [Accessed: Apr. 2, 2025].

M. M. Solomon, “Algorithms for the vehicle routing and scheduling problems with time window constraints,” Operations Research, vol. 35, no. 2, pp. 254-265, Apr. 1987, https://doi.org/10.1287/opre.35.2.254

E. Queiroga, “CVRPLIB: Capacitated vehicle routing problem library,” Pontifical Catholic University of Rio de Janeiro, 2025. [Online]. Available: https://vrp.galgos.inf.puc-rio.br/index.php/en/ [Accessed: Sep 20, 2025].