Machine Learning for combinatorial optimization: the case of Vehicle Routing

The Vehicle Routing Problem (VRP) is one of the most intensively studied combinatorial optimization problems in the Operations Research (OR) community. Its relevance is not only related to the various real-world applications it deals with, but to its inherent complexity being an NP-hard problem. From its original formulation more than 60 years ago, numerous mathematical models and algorithms have been proposed to solve VRP. The most recent trend is to leverage Machine Learning (ML) in conjunction with these traditional approaches to enhance their performance. In particular, this work investigates the use of ML-driven components as destroy or repair methods inside the Large Neighborhood Search (LNS) metaheuristic, trying to understand if, where, and when it is effective to apply them in the context of VRP. For these purposes, we propose NeuRouting, an open-source hybridization framework aimed at facilitating the integration between ML and LNS. Regarding the destroy phase, we adopt a Graph Neural Network (GNN) assisted heuristic, which we hybridize with a neural repair methodology taken from the literature. We investigate this integration both on its own and as part of an Adaptive Large Neighborhood Search (ALNS), performing an empirical study on instances of various sizes and against some traditional solvers.