Feature-Guided Metaheuristic with Diversity Management for Solving the Capacitated Vehicle Routing Problem

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.