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.

Abstract

In the last five decades, the uncapacitated facility location problem (UFLP) has been widely studied in operations research because of its features and its many applications in industrial contexts. Given a set of customers to service and a set of potential sites on which a warehouse can be built, the UFLP consists of selecting on which sites to install a warehouse and assigning one and only one warehouse to each customer. A fixed cost for building a warehouse is associated with each site and customer/warehouse assignment costs are also considered. The aim of the problem is to minimize the total cost. This NP-hard problem is very hard to solve to optimality, especially when the instance size is large. In this master's thesis, we propose a method to solve it to optimality. The proposed method is based on a combination of a tabu search heuristic and a linear programming solution algorithm called Improved Primal Simplex (IPS). It starts by computing a solution close to optimality using tabu search. This solution is then used to initialize IPS that solves the problem to optimality. The IPS algorithm overcomes a weakness of the simplex primal algorithm by taking advantage of degeneracy when it appears during the solution process. Typically, the UFLP yields high degeneracy. In this thesis, we first develop an efficient tabu search method that produces better results in some cases than the algorithms from the literature. Second, we show that the proposed method solves the linear relaxation of UFLP more efficiently than the classic primal simplex algorithm for instances where the assignment cost matrix has a density between 0.1 and 0.6. This efficiency increases with the instance size. We report a reduction of the computational time of up to a factor of 3.5 when the IPS algorithm is compared with the primal simplex algorithm. Then, for the integer solution process, we test an integration of the IPS method into a branch-and-bound algorithm using two search strategies: depth-first and best-first. Our tests highlight a weakness of this approach that forbids our method to keep its superiority over the same branch-and-bound algorithm based on the primal simplex algorithm. We conclude this thesis by briefly discussing future research directions for the proposed method and also for its application to solve the UFLP.