Using Recursive KMeans and Dijkstra Algorithm to Solve CVRP
This addresses routing challenges in fields like transportation and delivery, but it appears incremental as it combines existing algorithms without proven broad impact.
The paper tackles the capacitated vehicle routing problem (CVRP), an NP-hard optimization issue, by proposing a method combining recursive K-Means clustering and Dijkstra's algorithm to approximate optimal routes, though no concrete numerical results are provided.
Capacitated vehicle routing problem (CVRP) is being one of the most common optimization problems in our days, considering the wide usage of routing algorithms in multiple fields such as transportation domain, food delivery, network routing, ... Capacitated vehicle routing problem is classified as an NP-Hard problem, hence normal optimization algorithm can't solve it. In our paper, we discuss a new way to solve the mentioned problem, using a recursive approach of the most known clustering algorithm "K-Means", one of the known shortest path algorithm "Dijkstra", and some mathematical operations. In this paper, we will show how to implement those methods together in order to get the nearest solution of the optimal route, since research and development are still on go, this research paper may be extended with another one, that will involve the implementational results of this thoric side.