A clustering approach for the metaheuristic solution of vehicle routing problem with time window

Vehicle routing problems are one of the real-life problems that have been studied extensively in the literature, especially in the logistics and distribution sectors, and consist of various constraints and parameters. Vehicle routing problems, the main 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 goods from a white goods main distribution warehouse of a logistics company to homes or dealers in Ankara and surrounding cities, considering the delivery time window constraint. The company delivers goods to 75 dealers located in Ankara and surrounding cities with a 20-minute service time. Each dealer has their own delivery time window. The most important constraint is to make deliveries within the specified time window for each dealer. 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. Although the problem is a real-time problem in the existing warehouse, shipments are planned based on the experience and opinions of the planning personnel, and there is no systematic approach. The aim is to reduce costs in shipments, achieve maximum deliveries with minimum trips, improve shipment and service quality, and minimize planning errors. The inferences to be systematized were analyzed by examining the planning system made by the shipping planning personnel. According to the data obtained, dealer locations, delivery time intervals, order volumes were classified, and customer and shipment constraints were analyzed. A two-stage method based on "cluster first and then route" approach has been proposed. Due to the regular density of orders in the Ankara region, requiring a density-based clustering approach, the unknown number of clusters at the beginning, and the tolerance towards noise points, it is concluded that the DBSCAN algorithm is a suitable method. For each clustered route, vehicle routing was carried out under the time window constraint with the Ant Colony Algorithm approach, which is one of the metaheuristic methods, using the MATLAB R2022a program. Penalty costs are added for visits outside of time windows for each dealer. The data obtained as a result of the analysis and the previous planning data were compared financially and operationally.