Parameter Prediction for Metaheuristic Algorithms Solving Routing Problem Instances Using Machine Learning

Setting parameter values is crucial for the performance of metaheuristics. Tuning the parameters of a metaheuristic is a computationally costly task. Moreover, parameter tuning is difficult considering their inherent stochasticity and problem instance dependence. In this work, we explore the application of machine learning algorithms to suggest suitable parameter values. We propose a methodology to use k-nearest neighbours and artificial neural network algorithms to predict suitable parameter values based on instance features. Here, we evaluate our proposal on the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) using its state-of-the-art algorithm, Hybrid Genetic Search (HGS). Additionally, we use the well-known tuning algorithm ParamILS to obtain suitable parameter configurations for HGS. We use a well-known instance set that considers between 200 and 1000 clients. Three sets of features based on geographical distribution, time windows, and client clustering are obtained. An in-depth exploratory analysis of the clustering features is also presented. The results are promising, demonstrating that the proposed method can successfully predict suitable parameter configurations for unseen instances and suggest configurations that perform better than baseline configurations. Furthermore, we present an explainability analysis to detect which features are more relevant for the prediction of suitable parameter values.