An Intelligent Machine Learning-Driven Solving Framework for Capacitated Vehicle Routing

Hajar Bideq, Khaoula Ouaddi, Rachid Ellaia, Agnès Gorge

Despite recent advancements in solving the Capacitated Vehicle Routing Problem (CVRP), state-of-the-art learning-based methods remain hindered by costly offline training, while classical population solvers rely on implicit mechanisms and rigid parameter tuning. To bridge this methodological gap, this paper introduces the Group Learning Algorithm hybridized with a Multi-Armed Bandit (GLA-MAB), a training-free metaheuristic that transforms evolutionary search into an explicit, controllable learning process. The framework partitions the population into leader-learner groups to extract and inject proven topological structures directly into weaker solutions. Simultaneously, a hierarchical MAB layer oversees the search online, utilizing real-time reward feedback to dynamically manage operator selection and stagnation recovery. Furthermore, a spatial decomposition wrapper ensures strict scalability, extending the framework’s applicability to massive topologies of up to 1200 nodes. Comprehensive evaluations across 117 established CVRP benchmark instances validate the architecture’s efficacy. GLA-MAB achieves near-optimal convergence on classical instances, maintaining mean gaps below 0.03% on Sets A and E, and delivers highly competitive performance on large-scale heterogeneous sets such as Set Li. Ultimately, GLA-MAB provides the dynamic adaptability of modern artificial intelligence while completely eliminating the prohibitive overhead of offline dataset generation.