Local Search and Machine Learning for Capacitated Vehicle Routing

Abstract

In a fast-changing economy, demand for high-quality logistics solutions increases rapidly. The number of parcels shipped worldwide has doubled since 2014 and is expected to have doubled again by 2025. With this growing demand comes the need for first-class vehicle scheduling, both from an environmental as well as an economic standpoint. The goal is to find optimal planning solutions, but since these problems are NP-hard, this is not always possible in reasonable time. Therefore, Local Search methods, like Simulated Annealing, are often used to find good (not necessarily optimal) solutions. This study aims to find a way to combine machine learning and simulated annealing by looking for good features with machine learning of existing solutions and guiding the SA algorithm towards good solutions. In this thesis, we look into capacitated vehicle scheduling in the context of garbage collection. We propose a new variant of the SA algorithm, Smart Simulated Annealing (SSA). This algorithm uses OrderVectors found by AdaGrad, a stochastic gradient descent algorithm. We show that the number of iterations needed to find solutions compared to SA can be reduced by 10 percent for short runs and by 17 percent for long runs. Our results indicate that SSA can reduce the number of iterations needed to find good solutions. Future research can focus on optimizing SSA and its parameters and on the robustness of the solutions to check if theoretical solutions can be used in real-life.