Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable. / Location decisions are frequently subject to dynamic aspects such as changes in customer demand. Often, flexibility regarding the geographic location of facilities, as well as their capacities, is the only solution to such issues. Even when demand can be forecast, finding the optimal schedule for the deployment and dynamic adjustment of capacities remains a challenge. In this thesis, we focus on multi-period facility location problems that allow for dynamic capacity adjustment, in particular those with complex cost structures. We investigate such problems from different Operations Research perspectives, presenting and comparing several mixed-integer programming (MIP) models, assessing their use in practice and developing efficient solution algorithms. The thesis is divided into four parts. We first motivate our research by an industrial application, in which a logging company needs to locate camps to host the workers involved in forestry operations. We present a MIP model that allows for the construction of additional camps, the expansion and relocation of existing ones, as well as partial closing and reopening of facilities. The model uses particular capacity constraints that involve integer rounding on the left hand side. Economies of scale are considered on several levels of the cost structure. The usefulness of the model is assessed by two case studies. The second part introduces the Dynamic Facility Location Problem with Generalized Modular Capacities (DFLPG). The model generalizes existing formulations for several dynamic facility location problems and provides stronger linear programming relaxations than the specialized formulations. The model can address facility location problems where the costs for capacity changes are defined for all pairs of capacity levels, as it is the case in the previously introduced industrial problem. It is applied to three special cases: capacity expansion and reduction, temporary facility closing and reopening, and the combination of both. We prove dominance relationships between our formulation and existing models for the special cases. Computational experiments on a large set of randomly generated instances with up to 100 facility locations and 1000 customers show that our model can obtain optimal solutions in shorter computing times than the existing specialized formulations. Given the complexity of such models for large instances, the third part of the thesis proposes efficient Lagrangian heuristics. Based on subgradient and bundle methods, good quality solutions are found even for large-scale instances with up to 250 facility locations and 1000 customers. To improve the final solution quality, a restricted model is solved based on the information collected through the solution of the Lagrangian dual. Computational results show that the Lagrangian based heuristics provide highly reliable results, producing good quality solutions in short computing times even for instances where generic solvers do not find feasible solutions. Finally, we adapt the Lagrangian heuristics to solve the industrial application. Two different relaxations are proposed and compared. Extensions of the previous concepts are presented to ensure a reliable solution of the problem, providing high quality solutions in reasonable computing times.

This dissertation studies models for locating facilities in time varying demand environments. We describe the characteristics of the time varying demand that motivate the analysis of our location models in terms of total demand and the change in value and location of the demand of each customer. The first part of the dissertation is devoted to the dynamic location model, which determines the optimal time and location for establishing capacitated facilities when demand and cost parameters are time varying. This model minimizes the total cost over a discrete and finite time horizon for establishing, operating, and closing facilities, including the transportation costs for shipping demand from facilities to customers. The model is solved using Lagrangian relaxation and Benders? decomposition. Computational results from different time varying total demand structures demonstrate, empirically, the performance of these solution methods. The second part of the dissertation studies two location models where relocation of facilities is not allowed and the objective is to determine the optimal location of capacitated facilities that will have a good performance when demand and cost parameters are time varying. The first model minimizes the total cost for opening and operating facilities and the associated transportation costs when demand and cost parameters are time varying. The model is solved using Benders? decomposition. We show that in the presence of high relocation costs of facilities (opening and closing costs), this model can be solved as a special case by the dynamic location model. The second model minimizes the maximum regret or opportunity loss between a robust configuration of facilities and the optimal configuration for each time period. We implement local search and simulated annealing metaheuristics to efficiently obtain near optimal solutions for this model.