Abstract FR:

L'objet de cette thèse est la proposition d'une méthodologie permettant de construire des systèmes de voisinage performants pour la résolution des problèmes d'optimisation combinatoire par les méthodes approchées. L'objectif principal poursuivi tout au long du mémoire est d'essayer de justifier en quoi notre démarche de conception de systèmes de voisinage est intéressante. Ce travail est conduit aussi bien sur le plan théorique que sur le plan expérimental. Sur le plan théorique, une caractérisation des systèmes de voisinage par deux grandeurs mathématiques, la combinatoire et la profondeur, est proposée. La combinatoire mesure la taille des systèmes de voisinage, et la profondeur détermine la faculté qu'un système de voisinage a de trouver des minima locaux de bonne qualité. La force de ces outils réside dans leur mise en oeuvre, qui se révèle très simple en comparaison de l'existant. Sur un plan expérimental, notre démarche est mise en oeuvre avec succès sur trois problèmes différents (le TSP, le ATSP et le JSSP avec transport), et en utilisant métaheuristiques différentes (kangourou, recuit simulé, recherche locale itérée et méthode hybride recuit/recherche locale). Pour le TSP, nous proposons une variante efficace de l'algorithme du kangourou. Une solution optimale est obtenue pour la majorité des instances de la TSPLIB inférieures à 1500 villes. L'approche de résolution utilisée pour résoudre le ATSP consiste à transformer une instance asymétrique en une instance symétrique, afin d'appliquer la méthode précédente. La majorité des instances de la TSPLIB sont résolues en quelques secondes. Le problème de Job Shop avec transport est un problème qui apparaît dans les systèmes flexibles de production. C'est un problème difficile car il s'agit de résoudre conjointement deux problèmes NP-complets : le JSSP et le VSP. Les trois méthodes testées sont toujours au moins aussi bonnes que les meilleurs résultats connus, et 23 des 40 instances testées sont améliorées