Machine learning and mathematical programming based hybrid solution proposal for capacitated vehicle routing problem

In this study, a three-stage approach which hybridizes machine learning techniques and mathematical programming formulations, is proposed for the solution of capacitated vehicle routing problem (CVRP). In order to solve CVRP, in the first stage, it was decided the nodes to be assigned to which vehicles via machine learning algorithms, then in the second stage it was ensured that the resulting clusters' total demand amount do not exceed the vehicle capacity using a method, which is called capacity balancing algorithm. In the third stage, the vehicle started from the depot and visits all the assigned nodes to find the shortest (minimum as an alternative) travelled distance by using the traveling salesman problem (TSP) mathematical model. The final solution of the CVRP has been formed by combining all TSP routes. The machine learning algorithms that are used in this study are for supervised learning category; K-Nearest Neighborhood (K-NN) and Logistic Regression (LR) algorithms and for unsupervised learning category; K-Means algorithm. For the proposed approach, sensitivity analyzes were carried out using different datasets from the literature with a different number of vehicles. As a result, it has been shown that the proposed hybrid approach gives better results in most of the test problems than the solution of the mathematical model of CVRP.