The application of two clustering methods in the vehicle routing problem - A numerical example in the city of Turin

The main topic of this thesis is the Vehicle Routing Problem (VRP). In particular, four algorithms are proposed to solve the static version of VRP. Each of these four algorithms is characterized by an initial phase in which customers are divided in clusters, prior to the routing phase in which the VRP is actually solved. Two different clustering approaches for the management of customers locations (i.e., the k-means method and the affinity propagation method) and two different resolution methods (i.e., the insert method and the rebuild method) for the planning of routes have been implemented, giving rise to four different Python-based algorithms to solve the VRP. If on one hand the k-means method is widely popular in the context of VRP, the affinity propagation method is not. In addition, in this thesis the concept of time is introduced even in the case of the static VRP. In real-word situations customers arrive in different moments of time before the departure of vehicles from the depot. However, even if these new customers enter the problem in a second moment, they can be still labelled like known customers if they appear before the departure time of vehicles. In this thesis new solution methods that incorporate this concept of adjusting routes based on new customers entering the problem in different moments of time are introduced. Intermediate solutions are computed and continuously changed in order to find the best solution for vehicles at the moment of departure. The last solution before the departure time of vehicles represents the routes followed by drivers to visit all customers. The problem still falls in the category of static VRPs since, even if new customers enter the problem in different moments, all of them appear before the departure time of vehicles. Hence, they can be still labelled like known customers. Finally, the simulation of a numerical example placed in the city of Turin is conceived to test and compare the performances of the four algoritmhs.