Combining Stochastic local search with Machine Learning for Vehicle Routing

Abstract

In this work a hybrid approach to the Capacitated, Periodic, Vehicle Routing Problem with Multiple Trips (and Optional Customers) (CPVRPMT) is presented: First, Simulated Annealing is used to generate a moderately sized batch of sufficiently good solutions. Second, an unsupervised machine learning algorithm is trained on these solutions to obtain vector representations for all customers/orders. The vector representations contain meaningful information about the relation between orders and enable us to calculate the Cosine Similarity between them. The Cosine Similarity we interpret as a measure indicating if two orders should generally be close together in a route and if so, how close? Third, the Simulated Annealing algorithm from the ?rst step (SA) is adjusted so that it can take the Cosine Similarity into account, forming new algorithm SACos. Both SACos and SA are tested on a simpli?cation of a real case and compared by looking at the average score of their generated solutions under several conditions. It is found that although SACos is slightly slower, it more than signi?cantly outperforms SA.