A Hybrid K-Means, MST, and DFS Approach for Solving The Capacitated Routing Problem
About this article
Abstract
The Routing Problem (VRP) is a central challenge in logistics, where optimizing costs and adhering to operational constraints are critical for efficient distribution networks. These challenges include minimizing distances traveled, reducing transportation costs, and limiting computation times for real-time applications. This paper proposes a hybrid approach combining K-Means clustering, Minimum Spanning Tree (MST), and Depth-First Search (DFS) to efficiently solve the Capacitated Routing Problem (CVRP). Using the Solomon datasets as a benchmark, we evaluate the method’s performance. The results demonstrate a significant reduction in total distance traveled while maintaining low computation times, making this approach competitive with traditional heuristics.
Keywords
- DFS
- Means
- MST
- VRP
References
[1] Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6(1), 80–91. https://doi.org/10.1287/mnsc.6.1.80.
[2] Solomon, M. M. (1987). Algorithms for the Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35(2), 254–265. https://doi.org/10.1287/opre.35.2.254.
[3] Clarke, G., & Wright, J. W. (1964). Scheduling of shipments from a Central Depot to a Number of Delivery Points. Operations Research, 12(4), 568–581. https://doi.org/10.1287/opre.12.4.568.
[4] Amarouche, Y., et al. (2018). A Two-Phase Resolution Method for the Routing Problem. Journal of Logistics and Optimization, 22(4), 112–130.
[5] Purba Daru, K., & Meta, K. (2021). Multi-Depot Capacitated Routing Problem. International Journal of Operations Research, 18(2), 75–89.
View more references (7)
[6] Laporte, G. (2009). Fifty Years of Routing. Transportation Science, 43(4), 408–416. https://doi.org/10.1287/trsc.1090.0301.
[7] Gendreau, M., Hertz, A., & Laporte, G. (1994). A Tabu Search Heuristic for the Routing Problem. Management Science, 40(10), 1276–1290. https://doi.org/10.1287/mnsc.40.10.1276.
[8] Wu, Y., Cai, Y., & Fang, C. (2025). An Efficient Hybrid Framework with Knowledge Transfer for Solving Capacitated Routing Problems. Complex & Intelligent Systems, 11, 337. https://doi.org/10.1007/s40747-025-01920-x.
[9] Sharma, M., & Lau, H. C. (2025). Hybrid Learning and Optimization Methods for Solving Capacitated Routing Problem. arXiv preprint, arXiv:2509.15262.
[10] Wang, E., Cai, Y., & Sun, Z. (2025). Flexible Capacitated Routing Problem Solution Method Based on Memory Pointer Network. Mathematics, 13(7), 1061. https://doi.org/10.3390/math13071061.
[11] Li, J., & Zhang, Q. (2023). A Q-Learning-Assisted Evolutionary Algorithm for Capacitated Routing Problem. Applied Soft Computing, 142, 110345.
[12] Mohamed, R. E., & El-Shaikh, A. (2009). A Clustering-Based Heuristic for the Routing Problem. International Journal of Production Research, 47(3), 789–805.