Notre sujet de recherche porte sur la résolution du problème de transport avec coûts fixes (FCTP). Le problème de transport classique consiste à déterminer le schéma optimal de distribution dans un réseau. Le réseau est divisé en deux sous-ensembles de sommets : les origines caractérisées par une offre et les destinations caractérisées par une demande. À chaque arc reliant une origine et une destination, est associé un coût variable. L'objectif est de satisfaire toutes les demandes en minimisant la somme des coûts variables de transport. Dans le FCTP, il y a aussi des coûts fixes associés à tous les arcs, en supplément de tout ce qui décrit un problème de transport classique. Ainsi, à chaque arc, est associé un coût variable et un coût fixe qui est considéré si et seulement si l'arc est utilisé. L'objectif est désormais de minimiser la somme totale des coûts, variables et fixes. Le FCTP nous confronte donc à un modèle différent et plus complexe. La complexité de résolution est accrue pour les instances de grande taille. Dans ce mémoire, nous étudions et présentons une nouvelle méthode de résolution pour les instances de grande taille du FCTP. Il s'agit d'une méthode de décomposition lagrangienne qui utilise la relaxation lagrangienne et un algorithme de sous-gradient pour trouver une borne inférieure au problème global. Nous avons intégré à la méthode une heuristique lagrangienne, incluant une procédure de ``slope scaling'' afin d'améliorer notre algorithme de sous-gradient et le résultat final de la méthode. À l'issue de notre processus de résolution, nous trouvons, pour certaines instances de grande taille, un moyen d'améliorer la solution proposée par CPLEX pour le FCTP en donnant comme paramètre à CPLEX la solution finale de notre méthode. / Our research topic focuses on solving the fixed charge transportation problem (FCTP). The classic transportation problem is to determine the optimal distribution pattern in a network. The network is divided into two subsets of vertices : the origins characterized by a supply and the destinations characterized by a demand. Each arc connecting an origin and a destination has a variable cost associated with it. The objective is to satisfy all demands while minimizing the sum of variable transportation costs. In FCTP, there are also fixed costs associated with all arcs, in addition to all others things that describe a typical transportation problem. So, each arc is associated a variable cost and a fixed cost which is considered if and only if the arc is used. The objective is now to minimize the total sum of costs, variable and fixed. The FCTP therefore confronts us with a different and more complex model. The resolution complexity is even increased for large instances. In this thesis, we study and present a new resolution method for large FCTP instances. This is a lagrangian decomposition method which uses lagrangian relaxation and a subgradient algorithm to find a lower bound to the global problem. We have integrated into the method a lagrangian heuristic, including a “slope scaling” procedure in order to improve our sub-gradient algorithm and the final result of the method. At the end of our resolution process, we find, for some large instances, a way to improve the solution proposed by CPLEX for the FCTP by giving as parameter to CPLEX the final solution of our method.

La conception de réseaux est un riche sous-domaine de l'optimisation combinatoire ayant de nombreuses applications pratiques. Du point de vue méthodologique, la plupart des problèmes de cette classe sont notoirement difficiles en raison de leur nature combinatoire et de l'interdépendance des décisions qu'ils impliquent. Ce mémoire aborde deux problèmes de conception de réseaux dont les structures respectives posent des défis bien distincts. Tout d'abord, nous examinons un problème déterministe dans lequel un client doit acquérir au prix minimum un certain nombre d'unités d'un produit auprès d'un ensemble de fournisseurs proposant différents coûts fixes et unitaires, et dont les stocks sont limités. Ensuite, nous étudions un problème probabiliste dans lequel une entreprise entrant sur un marché existant cherche, en ouvrant un certain nombre d'installations parmi un ensemble de sites disponibles, à maximiser sa part espérée d'un marché composé de clients maximisant une fonction d'utilité aléatoire. Ces deux problèmes, soit le problème de transport à coût fixe à un puits et le problème d'emplacement d'installations compétitif basé sur les choix, sont étroitement liés au problème du sac à dos et au problème de couverture maximale, respectivement. Nous introduisons de nouvelles reformulations prenant avantage de ces connexions avec des problèmes classiques d'optimisation combinatoire. Dans les deux cas, nous exploitons ces reformulations pour démontrer de nouvelles propriétés théoriques et développer des méthodes de résolution efficaces. Notre nouvel algorithme pour le problème de transport à coûts fixes à un puits domine les meilleurs algorithmes de la littérature, réduisant le temps de résolution des instances de grande taille jusqu'à quatre ordres de grandeur. Une autre contribution notable de ce mémoire est la démonstration que la fonction objectif du problème d'emplacement d'installations compétitif basé sur les choix est sous-modulaire sous n'importe quel modèle de maximisation d’utilité aléatoire. Notre méthode de résolution basée sur la simulation exploite cette propriété et améliore l'état de l'art pour plusieurs groupes d'instances. / Network design is a rich subfield of combinatorial optimization with wide-ranging real-life applications. From a methodological standpoint, most problems in this class are notoriously difficult due to their combinatorial nature and the interdependence of the decisions they involve. This thesis addresses two network design problems whose respective structures pose very distinct challenges. First, we consider a deterministic problem in which a customer must acquire at the minimum price a number of units of a product from a set of vendors offering different fixed and unit costs and whose supply is limited. Second, we study a probabilistic problem in which a firm entering an existing market seeks, by opening a number of facilities from a set of available locations, to maximize its expected share in a market composed of random utility-maximizing customers. These two problems, namely the single-sink fixed-charge-transportation problem and the choice-based competitive facility location problem, are closely related to the knapsack problem and the maximum covering problem, respectively. We introduce novel model reformulations that leverage these connections to classical combinatorial optimization problems. In both cases, we exploit these reformulations to prove new theoretical properties and to develop efficient solution methods. Our novel algorithm for the single-sink fixed-charge-transportation problem dominates the state-of-the-art methods from the literature, reducing the solving time of large instances by up to four orders of magnitude. Another notable contribution of this thesis is the demonstration that the objective function of the choice-based competitive facility location problem is submodular under any random utility maximization model. Our simulation-based method exploits this property and achieves state-of-the-art results for several groups of instances.