Abstract (FR)

De nombreux problèmes d'optimisation combinatoire considèrent plusieurs objectifs, souvent conflictuels. Cette thèse s'intéresse à l'utilisation de méthodes de recherche locale, de structures de données et de recherche Monte-Carlo pour la recherche de l'ensemble des solutions efficaces de tels problèmes, représentant l'ensemble des meilleurs compromis pouvant être réalisés en considération de tous les objectifs.Nous proposons une nouvelle méthode d'approximation appelée 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combinant les concepts de recherche locale Pareto (PLS) et de décomposition. La PLS est une descente de recherche locale adaptée au multi-objectif, et la décomposition consiste en la subdivision du problème multi-objectif en plusieurs problèmes mono-objectif. Deux méthodes d'optimisation mono-objectif sont considérées: la recherche locale itérée et la recherche Monte-Carlo imbriquée. Deux modules principaux sont intégrés à 2PIPLS/D. Le premier généralise et améliore une méthode existante et génère un ensemble initial de solutions. Le second réduit efficacement l'espace de recherche et permet d'accélérer la PLS sans négliger la qualité de l'approximation générée. Nous introduisons aussi deux nouvelles structures de données gérant dynamiquement un ensemble de solutions incomparables, la première est spécialisée pour le cas bi-objectif et la seconde pour le cas général.2PIPLS/D est appliquée au Problème du Voyageur de Commerce bi-objectif et tri-objectif et surpasse ses concurrents sur les instances testées. Ensuite, 2PIPLS/D est appliquée à un nouveau problème avec cinq objectifs en lien avec la récente réforme territoriale d'agrandissement des régions françaises.