Development of learning metaheuristics for vehicle routing problems

Cette thèse étudie l’intégration de le Machine Learning (ML) et des algorithmes d’optimisation pour résoudre des problèmes d’optimisation combinatoire, en particulier les Vehicle Routing Problems (VRPs). Pour les VRPs de grande taille, les métaheuristiques sont couramment utilisées afin d’obtenir des solutions quasi-optimales en un temps raisonnable. Deux approches hybrides sont proposées pour renforcer ces méthodes : des mécanismes guidés par les données et des mécanismes guidés par l’apprentissage itératif. D’abord, les approches guidées par les données exploitent l’IA Explicable (XAI) pour identifier les caractéristiques influençant la qualité des solutions, aboutissant à une métaheuristique pilotée par ces caractéristiques. Ensuite, deux modèles innovants sont introduits : Edge-Selector, qui prédit les mouvements sous-optimaux lors de la recherche locale et généralise sur différentes variantes et tailles de VRPs, et Node-Destroyer, qui améliore la recherche à voisinage étendu en sélectionnant de façon stratégique les nœuds à supprimer. Ces contributions sont validées par des analyses statistiques, montrant comment le ML peut renforcer les métaheuristiques en capturant la structure des problèmes, en guidant la recherche et en facilitant les améliorations itératives.