A Clustering Approach for the Metaheuristic Solution of Vehicle Routing Problem with Time Window

Vehicle routing problems are one of the real-life problems studied extensively in the literature, especially in the logistics and transportation sectors, and consist of various constraints and parameters. Vehicle routing problems, the primary purpose of which is cost minimization, are solved with heuristic or metaheuristic methods within the scope of their content.

In this study, the problem is to plan the routes for delivering white goods from a main warehouse to homes or dealers in Ankara and surrounding cities, considering the delivery time window constraint. Deliveries can be made before or after the time window, but if there is a delay, it will incur penalty costs. Therefore, the problem examined is in the class of “Vehicle routing with flexible time windows” problems. The main focus in solving the problem is to minimize cost and deliver within the time window. A two-stage method based on “cluster-first route-second” approach has been proposed. Products to be delivered are divided into two groups regarding the size and product group-based placement constraint added to the DBSCAN clustering method. If there is capacity in the vehicle, the DBSCAN algorithm was revised to include the next point in the cluster. In the second stage, clusters with a high occupancy rate and a minimized number of vehicles are routed to deliver under time window constraints with the Ant Colony Algorithm approach. The results of the study are compared with the previous planning results, financially and operationally. The proposed approach achieved a 30% improvement in the number of vehicles. The vehicle occupancy rates have been increased to an average of 94.89%.