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 applica...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-03-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/15/6/2946 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850090084818223104 |
|---|---|
| author | Tomás Barros-Everett Elizabeth Montero Nicolás Rojas-Morales |
| author_facet | Tomás Barros-Everett Elizabeth Montero Nicolás Rojas-Morales |
| author_sort | Tomás Barros-Everett |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-e7f31ab7972a4baea0230afdfcbbca9c |
| institution | DOAJ |
| issn | 2076-3417 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj-art-e7f31ab7972a4baea0230afdfcbbca9c2025-08-20T02:42:38ZengMDPI AGApplied Sciences2076-34172025-03-01156294610.3390/app15062946Parameter Prediction for Metaheuristic Algorithms Solving Routing Problem Instances Using Machine LearningTomás Barros-Everett0Elizabeth Montero1Nicolás Rojas-Morales2Departamento de Informática, Universidad Técnica Federico Santa María, Avenida España 1680, Valparaíso 2390123, ChileDepartamento de Informática, Universidad Técnica Federico Santa María, Avenida España 1680, Valparaíso 2390123, ChileDepartamento de Informática, Universidad Técnica Federico Santa María, Avenida España 1680, Valparaíso 2390123, ChileSetting 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.https://www.mdpi.com/2076-3417/15/6/2946automatic metaheuristic configurationexplainable artificial intelligencemachine learningparameter values prediction |
| spellingShingle | Tomás Barros-Everett Elizabeth Montero Nicolás Rojas-Morales Parameter Prediction for Metaheuristic Algorithms Solving Routing Problem Instances Using Machine Learning Applied Sciences automatic metaheuristic configuration explainable artificial intelligence machine learning parameter values prediction |
| title | Parameter Prediction for Metaheuristic Algorithms Solving Routing Problem Instances Using Machine Learning |
| title_full | Parameter Prediction for Metaheuristic Algorithms Solving Routing Problem Instances Using Machine Learning |
| title_fullStr | Parameter Prediction for Metaheuristic Algorithms Solving Routing Problem Instances Using Machine Learning |
| title_full_unstemmed | Parameter Prediction for Metaheuristic Algorithms Solving Routing Problem Instances Using Machine Learning |
| title_short | Parameter Prediction for Metaheuristic Algorithms Solving Routing Problem Instances Using Machine Learning |
| title_sort | parameter prediction for metaheuristic algorithms solving routing problem instances using machine learning |
| topic | automatic metaheuristic configuration explainable artificial intelligence machine learning parameter values prediction |
| url | https://www.mdpi.com/2076-3417/15/6/2946 |
| work_keys_str_mv | AT tomasbarroseverett parameterpredictionformetaheuristicalgorithmssolvingroutingprobleminstancesusingmachinelearning AT elizabethmontero parameterpredictionformetaheuristicalgorithmssolvingroutingprobleminstancesusingmachinelearning AT nicolasrojasmorales parameterpredictionformetaheuristicalgorithmssolvingroutingprobleminstancesusingmachinelearning |