Learning Penalisation Criterion of Guided Local Search for Large Scale Vehicle Routing Problem

A recent case of success, the Knowledge-Guided Local Search was able to efficiently and effectively solve several (Large-Scale) Vehicle Routing Problems. This method presents an interesting concept of route compactness in their search process and uses it to penalise the solutions instead of using the traditional distance measure. Although mostly being successful, this measure sometimes leads to underperforming solutions when compared to the distance aspect. Based on the assumption that the best Guide Local Search penalisation criterion depends on the VRP instance, we make an analysis on how the algorithm behaves across different instances and also propose a Machine Learning model to learn to predict the best penalty criterion for a given instance. Genetic Programming, Support-Vector Machines and Random Forests are used in this classification task. Additionally, we also consider a regression model in order to estimate the improvement given for each mode. Results show that it is possible to find the correct class using the selected features and, in fact, some models were able to classify the majority of instances correctly. However, this is not consistent across different instances.