Clustering approach for vehicle routing

One of the primary objectives of businesses today is to ensure the timely delivery of products to customers. In the product delivery process, numerous criteria must be considered, such as the number of vehicles available for distribution, distances between customers and distribution centers, delivery timing, accurate delivery of the correct quantity of products, and the internal arrangement of products within vehicles. Vehicle Routing Problems (VRPs) are utilized to address these criteria, aiming to enhance customer satisfaction while minimizing operational costs. Consequently, VRPs are widely studied both in the academic literature and in practice. Vehicle Routing Problems are the problems of determining the optimum number of distribution/collection routes for a given number of vehicles to distribute/collect products from at least one main warehouse (or more than one warehouse) to a set of customers or dealers who are scattered in different physical locations and have known demand. In solving vehicle routing problems, the following objectives are taken into consideration: minimizing total transportation costs by taking into account the total travel time of the vehicles and their fixed costs, minimizing the number of vehicles to be used by ensuring that no customer/dealer is left without receiving products/services, balancing the determined routes in terms of vehicle load and distance traveled, and preventing partial distribution of orders to customers/dealers. Depending on the nature of the problem, it may sometimes be necessary to create a model to achieve more than one and/or conflicting objectives. Vehicle Routing Problems, for which many different exact methods and many general heuristic methods can be used, are integrated optimization problems that have remained popular for many years. Many different types of Vehicle Routing Problems, which have been studied frequently both in literature and in practical applications since the 1950s, have been introduced by adding new constraints, and many mixed models and algorithms have been developed for these problem types. The main objective in Vehicle Routing Problems is to provide all the desired constraints depending on the structure of the problem, keep the number of vehicles to a minimum, keep the total travel time and/or distance to a minimum and at the same time minimize the cost function. While all these basic objectives are provided in Vehicle Routing Problems, the secondary objective that needs to be provided is to keep customer satisfaction at the maximum level. In order to achieve all these goals, businesses produce solutions based on their past experiences without using mathematical models, which results in high distribution costs (such as labor, vehicles, time), and ineffective/inefficient distribution routes can create extra costs for businesses. In addition, inefficient vehicle routes can affect delivery time and delivery accuracy, thus reducing customer satisfaction. During the routing process, various techniques are employed depending on constraints such as vehicle capacity, distance, and the number of depots. These techniques include capacitated, distance-constrained, multi-depot, delivery-then-pickup, simultaneous pickup and delivery, and time-windowed routing methods. The common objectives of these techniques are to reduce distribution costs, determine routes that maximize deliveries with the fewest trips, and enhance delivery and service quality. One of the approaches employed in routing is clustering, used to group delivery points effectively. Clustering algorithms such as K-means Clustering Algorithm, Hierarchical Clustering Algorithm, Model-Based Clustering methods, Grid-Based methods, and Density-Based methods are among the techniques that can be utilized. In this study, a vehicle routing application is presented for a manufacturing company operating in the white goods sector, aiming to ensure the accurate and efficient shipment of final products to its dealers. The "cluster first, route second" approach was adopted for solving the routing of dealers. Initially, data such as dealer locations, order volumes, and order details were collected. A distance matrix was then created using Google Maps, taking into account the distances between the dealers and the main depot. Based on the "cluster first, route second" approach, two different clustering algorithms — K-means and Fuzzy C-means — were applied to cluster the dealers. Subsequently, two different metaheuristic algorithms — Artificial Bee Colony (ABC) Algorithm and Firefly Algorithm — were employed to perform routing based on the clusters formed by each clustering method. As a result, four different routing solutions were obtained by pairing the clustering and routing algorithms: (1) K-means & ABC, (2) K-means & Firefly, (3) Fuzzy C-means & ABC, and (4) Fuzzy C-means & Firefly. All algorithms were coded and executed using Python. The resulting routes were compared in terms of the number of vehicles used, total distance traveled, and vehicle load capacities. When clustering was performed using the K-means algorithm, the optimum number of clusters was determined as four based on the Elbow Method. Since Cluster 2 contained a volume of products exceeding the capacity of a single vehicle, five vehicles were assigned to Cluster 2. Consequently, a total of eight vehicles were used in each routing solution based on K-means clustering. Therefore, when comparing the two routing solutions derived from K-means, the primary comparison criterion is the total distance traveled. When clustering was performed using the Fuzzy C-means algorithm, the optimum number of clusters was found to be ten. In the routing solution using the Firefly Algorithm, Clusters 2 and 3 exceeded the capacity of a single vehicle, thus requiring two vehicles each. Therefore, a total of twelve vehicles were used in the routing solution combining Fuzzy C-means clustering and the Firefly Algorithm. Thus, when comparing the two routing solutions derived from Fuzzy C-means, both the number of vehicles and the total distance traveled must be considered. Upon examining the results of all solutions, it was observed that the combination of K-means clustering and Firefly routing provided the optimum solution, achieving both the minimum number of vehicles (eight) and the shortest total distance traveled (1886.98 km). In the current distribution practice of the white goods company under study, product deliveries to dealers are planned based on the sales personnel's knowledge and experience. Since clustering is not applied during distribution planning, orders from geographically distant dealers may be loaded onto the same vehicles. Furthermore, due to the absence of a systematic routing method, the number of vehicles used and the total distances traveled are substantially higher. The proposed solution, utilizing K-means clustering and Firefly routing, achieved significant improvements in both the number of vehicles required and the total distance traveled.