Cette thèse intitulée « Extraction de connaissance pour les métaheuristiques à partir des solutions appliquée aux problèmes de tournées de véhicules bi-objectif » s’intéresse à l’intégration de mécanismes d’apprentissage au sein d’algorithmes multi-objectifs existants. En effet, l’utilisation d’apprentissage machine pour résoudre des problèmes d’optimisation combinatoire a permis d’améliorer de manière significative (à la fois en termes de performance et de temps d’exécution) des métaheuristiques existantes. Nous nous sommes concentrés sur un problème de tournées de véhicules bi-objectif avec fenêtres de temps qui est un problème de logistique où l’on cherche à optimiser la création de tournées pour livrer chaque client à une période précise, symbolisée par une fenêtre de temps. La résolution de ce type de problèmes est un enjeux pour de nombreuses entreprises. Les deux objectifs minimisés sont le coût total de transport et le temps total d’attente des livreurs, provoqué par l’arrivée du livreur avant le début de la période de livraison. Pour résoudre ce problème, nous proposons d’exploiter les séquences de clients livrés consécutivement au sein d’une tournée. Ces séquences sont extraites lors de l’exécution de l’algorithme à partir de solutions générées. Les séquences les plus prometteuses sont ensuite intégrées dans d’autres solutions pour les améliorer. Si l’apprentissage de séquences pour résoudre ce type de problèmes s’est révélé efficace en mono-objectif, cela reste un challenge de les exploiter dans un cadre multi-objectif, puisque certaines séquences intéressantes pour un objectif peuvent se révéler inutiles pour l’autre objectif. Plus précisément, dans cette thèse, nous nous interrogeons sur les manières d’exploiter au mieux les séquences disponibles dans les solutions. En particulier cela nous a conduits à nous poser les questions suivantes : comment gérer ces séquences dans un cadre multi-objectif ? De quelles solutions devons-nous extraire les séquences et dans quelles solutions les injecter ? A quel moment de l’exécution, les étapes d’injection et d’extraction doivent-elles être effectuées ? Les réponses à ces questions nous ont menés à l’élaboration d’un modèle d’apprentissage exploitant les séquences des solutions dans un cadre multi-objectif, où des groupes de connaissance sont créés pour stocker les séquences relatives à une partie de l’espace de recherche. Ce modèle a ensuite été intégré dans deux algorithmes populaires : MOEA/D et MOLS, montrant l’efficacité du modèle proposé.
Mme Laëtitia JOURDAN Université de Lille Co-directrice de thèse, Mme Caroline PRODHON Université Technologique de Troyes Examinatrice, M. Jin-Kao HAO Université d'Angers Rapporteur, M. Nicolas JOZEFOWIEZ Université de Lorraine Rapporteur, M. Lhassane IDOUMGHAR Université de Haute-Alsace Examinateur, Mme Marie-Eléonore KESSACI Université de Lille Directrice de thèse, M. Diego CATTARUZZA Centrale Lille Examinateur, M. Jean-Stéphane VARRE Université de Lille Examinateur.
Thèse de l'équipe ORKAD soutenue le 24/09/2024
français
English