Investigation of cluster-first route-second methods for vehicle routing problem using machine learning

Vehicle routing is an important operation in the logistics industry to optimize travel, reduce fuel/electricity consumption, and improve delivery times. However, as the complexity increases, solving large-scale routing problems can become challenging. In today's world, generating the route that vehicles follow from one point to another is known to be a costly and challenging problem in terms of resources and time, given the various purposes for which vehicles are used. Particularly when the number of points used for route construction is substantial, the level of complexity escalates, and the feasibility of resolution diminishes. In this scenario, the cluster-first route-second approach presents a significant solution. This approach involves using clustering algorithms initially to decompose the complexity of the problem into smaller and meaningful clusters, aiming to address large and intricate routing problems. Optimal routes are determined between delivery points within each of the resulting clusters. Consequently, a large routing problem is divided into smaller and more manageable sub-problems. Dividing clusters into smaller segments ensures that sub-clusters contain fewer delivery points, facilitating faster operation of routing algorithms and the discovery of more optimized routes. In this study, the results obtained by different clustering algorithms (K-Means, DBSCAN, BIRCH, OPTICS) on three different datasets were compared. According to the findings obtained for the main dataset, K-Means produced the best results. Experimental results demonstrate that the cluster-first route-second approach reduces computational complexity and optimizes travel distances, thereby reducing travel costs in vehicle routing problems.