Résumé
Nous nous intéressons dans cette thèse aux
possibilités d'hybridation entre les méthodes exactes et les
méthodes heuristiques afin de pouvoir tirer avantage de chacune des deux
approches : optimalité de la résolution exacte, caractère
moins déterministe et rapidité de la composante heuristique. Dans
l'objectif de résoudre des problèmes NPdifficiles de taille
relativement importante tels que les problèmes de transports, nous nous
intéressons dans les deux dernières parties de ce mémoire
à la conception de méthodes incomplètes basées sur
ces hybridations.
Dans la première partie, nous allons nous
intéresser aux méthodes de résolution par recherche
arborescente. Nous introduisons une nouvelle approche pour la gestion des
décisions de branchement, que nous appelons Dynamic Learning Search
(DLS). Cette méthode définit de manière dynamique des
règles de priorité pour la sélection des variables
à chaque noeud et l'ordre des valeurs sur lesquelles brancher. Ces
règles sont conçues dans une optique de
généricité, de manière à pouvoir utiliser la
méthode indépendamment du problème traité. Le
principe général est de tenir compte par une technique
d'apprentissage de l'impact qu'ont eu les décisions de branchement dans
les parties déjà explorées de l'arbre. Nous
évaluons l'efficacité de la méthode proposée sur
deux problèmes classiques : un problème d'optimisation
combinatoire et un problème à satisfaction de contraintes.
La deuxième partie de ce mémoire traite des
recherches à grand voisinage. Nous présentons un nouvel
opérateur de voisinage, qui détermine par un algorithme de
programmation dynamique la sous-séquence optimale d'un chemin dans un
graphe. Nous montrons que cet opérateur est tout particulièrement
destiné à des problèmes de tournées pour lesquels
tous les noeuds ne nécessitent pas d'être visités. Nous
appelons cette classe de problème les Problèmes de
Tournées avec Couverture Partielle et présentons quelques
problèmes faisant partie de cette classe. Les chapitres 3 et 4 montrent,
à travers des tests expérimentaux conséquents,
l'efficacité de l'opérateur que nous proposons en appliquant
cette recherche à voisinage large sur deux problèmes,
respectivement le Problème de l'Acheteur Itinérant (TPP) et le
Problème de Voyageur de Commerce Généralisé (GTSP).
Nous montrons alors que cet opérateur peut être combiné de
manière efficace avec des métaheuristiques classiques, telles que
des algorithmes génétiques ou des algorithmes d'Optimisation par
Colonies de Fourmis.
Enfin, la troisième partie présente des
méthodes heuristiques basées sur un algorithme de
Génération de Colonnes. Ces méthodes sont
appliquées sur un problème
complexe : le problème de Tournées de
Véhicules avec Contraintes de Chargement à Deux Dimensions
(2L-VRP). Nous montrons une partie des possibilités qu'il existe afin de
modifier une méthode a priori exacte en une méthode
heuristique et nous évaluons ces possibilités à l'aide de
tests expérimentaux.
| 
