Application de la méthode IPS au problème de localisation d'entrepôt sans capacité

Le problème de localisation d'entrepôts sans capacité (LESC) est un problème qui a été très étudié dans le domaine de la recherche opérationnelle depuis une cinquantaine d'années pour ses caractéristiques et ses applications dans le monde industriel. Il consiste à installer un certain nombre d'entrepôts sur un ensemble de sites et à affecter un et un seul entrepôt à chaque client d'un ensemble de clients. Sur chaque site, il coûte un certain montant pour y installer un entrepôt et pour chaque client, il coûte un autre montant pour l'affecter à un site sur lequel un entrepôt est installé. L'objectif est de minimiser le coût total. Ce problème NP-difficile est très compliqué à résoudre de manière exacte surtout pour des instances de grande taille. Nous proposons dans ce mémoire une méthode permettant de le résoudre à l'optimalité. La méthode proposée est basée sur la combinaison d'une métaheuristique de type recherche tabou et d'un algorithme de résolution de programmes linéaires nommé IPS (Improved Primal Simplex) qui implémente une version améliorée du très connu algorithme du simplexe primal. Le tout fonctionne en faisant créer par la métaheuristique une solution proche de la solution optimale. Celle-ci sert de point de départ pour l'algorithme IPS qui termine la résolution jusqu'à l'optimalité. Cet algorithme IPS corrige une faiblesse de l'algorithme du simplexe primal en profitant de la dégénérescence quand celle-ci apparaît lors de la résolution d'un problème. Le problème LESC fait partie des problèmes à dégénérescence forte. Dans ce mémoire, nous développons d'abord une métaheuristique de recherche tabou qui produit des résultats qui sont, dans certains cas, supérieurs à ceux obtenus dans la littérature. Par la suite, nous montrons que la méthode proposée est plus efficace pour résoudre la relaxation linéaire du problème LESC que le traditionnel algorithme du simplexe primal sur les instances dont la matrice des coûts d'affectation a une densité comprise entre 0,1 et 0,6. Nous montrons également que cette efficacité augmente avec la taille des instances. Nos résultats mettent en évidence des temps de calcul réduits d'un facteur pouvant aller jusqu'à 3,5 pour certaines relaxations linéaires par rapport à l'algorithme du simplexe primal. Enfin, pour la résolution en nombres entiers, nous testons l'intégration de cette méthode dans un algorithme d'évaluation et séparation utilisant deux stratégies différentes : la stratégie profondeur d'abord et la stratégie meilleur d'abord. Nos tests sur cette intégration dans l'algorithme d'évaluation et séparation font ressortir des faiblesses sur l'implémentation, ce qui empêche la méthode proposée de conserver sa supériorité sur un algorithme d'évaluation et séparation identique utilisant l'algorithme du simplexe primal. Nous terminons ce mémoire en donnant des pistes d'amélioration pour la méthode proposée, ainsi que pour son application à la résolution du problème LESC.