Abstract FR:

Nous nous proposons, dans cette thèse, d'aborder le problème de routage dans une grille par une approche différente des méthodes classiques à la recuit simulé. Nous établissons le rapport entre le problème énoncé et l'affectation linéaire en d dimensions (dD-LAP), problème NP-difficile bien connu de la recherche opérationnelle. Nous étendons l'étude polyédrale du problème 3D-LAP au cas multidimensionnel en montrant l'accroissement de la complexité avec le nombre de dimensions. Parmi les différentes méthodes de résolution de ce problème, nous investiguons en détail les méthodes de sous-gradient, les plus adaptées compte tenu de la taille des problèmes envisagés ; notamment, nous introduisons deux heuristiques nouvelles pour le 3D-LAP: l'approximation locale et l'approximation globale. Toutes les deux sont basées sur la relaxation lagrangienne avec sous-gradient et sur la prise en compte de la structure polyédrale du 3D-LAP pour orienter la direction de recherche le long de la trajectoire du sous-gradient. Le polyèdre du problème est approximé localement/globalement par un nombre restreint de facettes. Donc il s'agit d'une approche encore inconnue dans la littérature, à notre connaissance: comment choisir un ensemble de facettes de cardinalité restreinte contenant des facettes "efficaces" parmi un nombre très grand (typiquement en nombre exponentiel pour un problème NP-difficile