Feature-Guided Metaheuristic with Diversity Management for Solving the Capacitated Vehicle Routing Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914211312959488 |
|---|---|
| author | Herdianto, Bachtiar Billot, Romain Lucas, Flavien Sevaux, Marc |
| author_facet | Herdianto, Bachtiar Billot, Romain Lucas, Flavien Sevaux, Marc |
| contents | We propose a feature-based guidance mechanism to enhance metaheuristic algorithms for solving the Capacitated Vehicle Routing Problem (CVRP). This mechanism leverages an Explainable AI (XAI) model to identify features that correlate with high-quality solutions. These insights are used to guide the search process by promoting solution diversity and avoiding premature convergence. The guidance mechanism is first integrated into a custom metaheuristic algorithm, which combines neighborhood search with a novel hybrid of the split algorithm and path relinking. Experiments on benchmark instances with up to $30,000$ customer nodes demonstrate that the guidance significantly improves the performance of this baseline algorithm. Furthermore, we validate the generalizability of the guidance approach by integrating it into a state-of-the-art metaheuristic, where it again yields statistically significant performance gains. These results confirm that the proposed mechanism is both scalable and transferable across algorithmic frameworks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_20777 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Feature-Guided Metaheuristic with Diversity Management for Solving the Capacitated Vehicle Routing Problem Herdianto, Bachtiar Billot, Romain Lucas, Flavien Sevaux, Marc Artificial Intelligence Discrete Mathematics We propose a feature-based guidance mechanism to enhance metaheuristic algorithms for solving the Capacitated Vehicle Routing Problem (CVRP). This mechanism leverages an Explainable AI (XAI) model to identify features that correlate with high-quality solutions. These insights are used to guide the search process by promoting solution diversity and avoiding premature convergence. The guidance mechanism is first integrated into a custom metaheuristic algorithm, which combines neighborhood search with a novel hybrid of the split algorithm and path relinking. Experiments on benchmark instances with up to $30,000$ customer nodes demonstrate that the guidance significantly improves the performance of this baseline algorithm. Furthermore, we validate the generalizability of the guidance approach by integrating it into a state-of-the-art metaheuristic, where it again yields statistically significant performance gains. These results confirm that the proposed mechanism is both scalable and transferable across algorithmic frameworks. |
| title | Feature-Guided Metaheuristic with Diversity Management for Solving the Capacitated Vehicle Routing Problem |
| topic | Artificial Intelligence Discrete Mathematics |
| url | https://arxiv.org/abs/2407.20777 |