A Hybrid K-Means, MST, and DFS Approach for Solving ‎The Capacitated Routing Problem

  • Authors

    • Soro Wongniga Seydou LASDIA, Institut National Polytechnique Félix Houphouët-Boigny (INPHB); Côte d’Ivoire, BP 1093 Yamoussoukro
    • Diaby Moustapha LASTIC, École Supérieure Africaine des TIC (ESATIC); Côte d’Ivoire, 18 BP 1501 Abidjan 18‎
    • Goore Bi Tra LASDIA, Institut National Polytechnique Félix Houphouët-Boigny (INPHB); Côte d’Ivoire, BP 1093 Yamoussoukro
    https://doi.org/10.14419/amjh9c26

    Received date: September 30, 2025

    Accepted date: November 21, 2025

    Published date: December 4, 2025

  • DFS; Means; MST; VRP

  • 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‎.

  • 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.
    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. Com-plex & 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.

  • Downloads

  • How to Cite

    Seydou , S. W. ., Moustapha, D. ., & Bi Tra, G. . (2025). A Hybrid K-Means, MST, and DFS Approach for Solving ‎The Capacitated Routing Problem. International Journal of Basic and Applied Sciences, 14(8), 9-14. https://doi.org/10.14419/amjh9c26