Feature-Guided Metaheuristic with Diversity Management for Solving the Capacitated Vehicle Routing Problem
This work addresses a domain-specific optimization problem in logistics and routing, offering incremental improvements to existing metaheuristic methods.
The paper tackles the Capacitated Vehicle Routing Problem by proposing a feature-based guidance mechanism using Explainable AI to enhance metaheuristic algorithms, resulting in statistically significant performance gains on benchmark instances with up to 30,000 customer nodes.
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.