Abstract FR:

Cette thèse contient deux parties : la première partie est consacrée aux méthodes de résolution du problème de localisation de dépôts avec équilibrage proposé par Crainic, Dejax et Delorme en 1986. Deux relaxations lagrangiennes sont proposées dans la thèse. Elles sont ensuite utilisées pour construire un algorithme optimal et un algorithme heuristique. L'algorithme optimal que nous avons proposé est un algorithme de séparation et d’évaluation progressive. La première relaxation lagrangienne est appliquée pour l'évaluation des bornes inférieures. Nous proposons aussi une règle efficace pour la séparation. En ce qui concerne la résolution heuristique du problème, les algorithmes gloutons (ascendant, descendant), d'amélioration par échange et une heuristique lagrangienne sont adaptés en tenant compte de la structure spécifique du problème. Dans la deuxième partie, nous modélisons une extension du problème de localisation de dépôts avec équilibrage. Cette extension consiste à introduire les contraintes de capacité pour les dépôts. Nous proposons une relaxation faible et deux relaxations lagrangiennes. Les algorithmes de résolution présentes dans la première partie s'adaptent aussi au nouveau problème.