Learning to Select Initialisation Heuristic for Vehicle Routing Problems

The Vehicle Routing Problem (VRP) is a complex problem that comes with a great number of applications in logistics and supply chains. It is non-trivial to select the optimal VRP techniques to solve these applications, especially since there are several possible scenarios. As there is no way to predict how each algorithm would perform until it is (at least partially) deployed, it would make sense in selecting the ones that have higher adaptability to the given environment. In this paper, we consider this idea on the initialisation part of a local search-based metaheuristic. We argue that a proper initialisation is important for obtaining better VRP solutions and apply several machine learning techniques aiming to learn how to use distinct features from four commonly used construction heuristics solutions, predicting the scenarios in which they are the most effective. We also provide relevant discussions on the effects of the initial solution on a local search context. Results show that the proposed method can help select the best or an improving method for the majority of the instances considered, especially for large-scale VRP instances.

Automated summary

The Vehicle Routing Problem (VRP) is a complex problem with numerous applications in logistics and supply chains. Selecting the optimal VRP techniques is challenging due to various possible scenarios. This paper focuses on the initialization part of a local search-based metaheuristic and proposes using machine learning techniques to predict the effectiveness of different construction heuristics solutions. Results show that this method can help select the best or improving method for most instances, especially for large-scale VRP instances.