Graph Neural Networks in Neighbourhood Selection for a Vehicle Routing Problem solver

Abstract

This research paper examines the use of Graph Neural Networks (GNNs) for selecting a sub-problem to be optimized by a Vehicle Routing Problem (VRP) solver. The task is termed neighbourhood selection and has many overlapping properties with a more extensively researched approach to solving VRPs - Large Neighbourhood Search (LNS). This paper explores how do GNNs compare to other methods of neighbourhood selection for optimizing the solution of VRP which are already developed within Dassault Systèmes ’ DELMIA, in collaboration with whom the current research is conducted.

VRP assumes a set of destinations that need to be visited by a set of vehicles and can be defined as a problem from graph theory. Because of this, GNN is considered a likely tool to approach solving the problem. In order to explore the method, sub-problems of VRP are represented as graphs, embedded via a GNN and compared in terms of how much optimizing them would improve the overall solution. Multiple models assuming different graph representations are trained on that task. They are consequently tested in real-world-like scenarios, where a VRPs solution is iteratively improved by using the models to select the best neighborhood (or sub-problem) which is then optimized using aDassault Syst`emes ’ algorithm.

Through experimentation, this research project examines methods to represent VRP sub-problems as a graphs-input for GNNs, as well as how to make and compare GNN embeddings. It provides a proof of concept that a GNN is a feasible approach to neighbourhood selection for VRP optimization.