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

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