Machine learning approach to solving the capacitated vehicle routing problem

The Vehicle Routing Problem (VRP) is a combinatorial optimization problem of practical importance and complexity that attracts the attention of researchers. The Capacitated Vehicle Routing Problem (CVRP) is one of the best known variants of the VRP. It involves finding the optimal routes for a set of vehicles with limited carrying capacity, while satisfying customer demand deterministically. Many approaches have been proposed to solve CVRP. In our case, we have chosen a solution method that uses a powerful machine learning approach that researchers are currently investing in such concepts. We have developed two algorithms that, in a first phase, use the K-mean method to create groups of customers to be delivered and, in a second phase, use two different optimisation heuristics to find the optimal delivery route. A comparative study of computational results and execution time was carried out to determine the best approach to use in such an operational research problem.