Lors du transport du bois de la forêt vers les usines, de nombreux événements imprévus peuvent se produire, événements qui perturbent les trajets prévus (par exemple, en raison des conditions météo, des feux de forêt, de la présence de nouveaux chargements, etc.). Lorsque de tels événements ne sont connus que durant un trajet, le camion qui accomplit ce trajet doit être détourné vers un chemin alternatif. En l’absence d’informations sur un tel chemin, le chauffeur du camion est susceptible de choisir un chemin alternatif inutilement long ou pire, qui est lui-même "fermé" suite à un événement imprévu. Il est donc essentiel de fournir aux chauffeurs des informations en temps réel, en particulier des suggestions de chemins alternatifs lorsqu’une route prévue s’avère impraticable. Les possibilités de recours en cas d’imprévus dépendent des caractéristiques de la chaîne logistique étudiée comme la présence de camions auto-chargeurs et la politique de gestion du transport. Nous présentons trois articles traitant de contextes d’application différents ainsi que des modèles et des méthodes de résolution adaptés à chacun des contextes. Dans le premier article, les chauffeurs de camion disposent de l’ensemble du plan hebdomadaire de la semaine en cours. Dans ce contexte, tous les efforts doivent être faits pour minimiser les changements apportés au plan initial. Bien que la flotte de camions soit homogène, il y a un ordre de priorité des chauffeurs. Les plus prioritaires obtiennent les volumes de travail les plus importants. Minimiser les changements dans leurs plans est également une priorité. Étant donné que les conséquences des événements imprévus sur le plan de transport sont essentiellement des annulations et/ou des retards de certains voyages, l’approche proposée traite d’abord l’annulation et le retard d’un seul voyage, puis elle est généralisée pour traiter des événements plus complexes. Dans cette ap- proche, nous essayons de re-planifier les voyages impactés durant la même semaine de telle sorte qu’une chargeuse soit libre au moment de l’arrivée du camion à la fois au site forestier et à l’usine. De cette façon, les voyages des autres camions ne seront pas mo- difiés. Cette approche fournit aux répartiteurs des plans alternatifs en quelques secondes. De meilleures solutions pourraient être obtenues si le répartiteur était autorisé à apporter plus de modifications au plan initial. Dans le second article, nous considérons un contexte où un seul voyage à la fois est communiqué aux chauffeurs. Le répartiteur attend jusqu’à ce que le chauffeur termine son voyage avant de lui révéler le prochain voyage. Ce contexte est plus souple et offre plus de possibilités de recours en cas d’imprévus. En plus, le problème hebdomadaire peut être divisé en des problèmes quotidiens, puisque la demande est quotidienne et les usines sont ouvertes pendant des périodes limitées durant la journée. Nous utilisons un modèle de programmation mathématique basé sur un réseau espace-temps pour réagir aux perturbations. Bien que ces dernières puissent avoir des effets différents sur le plan de transport initial, une caractéristique clé du modèle proposé est qu’il reste valable pour traiter tous les imprévus, quelle que soit leur nature. En effet, l’impact de ces événements est capturé dans le réseau espace-temps et dans les paramètres d’entrée plutôt que dans le modèle lui-même. Le modèle est résolu pour la journée en cours chaque fois qu’un événement imprévu est révélé. Dans le dernier article, la flotte de camions est hétérogène, comprenant des camions avec des chargeuses à bord. La configuration des routes de ces camions est différente de celle des camions réguliers, car ils ne doivent pas être synchronisés avec les chargeuses. Nous utilisons un modèle mathématique où les colonnes peuvent être facilement et naturellement interprétées comme des itinéraires de camions. Nous résolvons ce modèle en utilisant la génération de colonnes. Dans un premier temps, nous relaxons l’intégralité des variables de décision et nous considérons seulement un sous-ensemble des itinéraires réalisables. Les itinéraires avec un potentiel d’amélioration de la solution courante sont ajoutés au modèle de manière itérative. Un réseau espace-temps est utilisé à la fois pour représenter les impacts des événements imprévus et pour générer ces itinéraires. La solution obtenue est généralement fractionnaire et un algorithme de branch-and-price est utilisé pour trouver des solutions entières. Plusieurs scénarios de perturbation ont été développés pour tester l’approche proposée sur des études de cas provenant de l’industrie forestière canadienne et les résultats numériques sont présentés pour les trois contextes. / When wood is transported from forest sites to mills, several unforeseen events may occur, events which perturb planned trips (e.g., because of weather conditions, forest fires, or the occurrence of new loads). When such events take place while the trip is under way, the truck involved must be rerouted to an alternative itinerary. Without relevant information on such alternative itineraries, the truck driver may choose a needlessly long one or, even worse, an itinerary that may itself be "closed" by an unforeseen event (the same event as for the original itinerary or another one). It is thus critical to provide drivers with real-time information, in particular, suggestions of alternative itineraries, when the planned one cannot be performed. Recourse strategies to deal with unforeseen events depend on the characteristics of the studied supply chain, such as the presence of auto-loaders and the management policy of forestry transportation companies. We present three papers dealing with three differ- ent application contexts, as well as models and solution methods adapted to each context. In the first paper, we assume a context where truck drivers are provided a priori with the whole weekly plan. In this context, every effort must be made to minimize the changes in the initial plan. Although the fleet of trucks is homogeneous, there is a priority ranking of the truck drivers. The priority drivers are ensured the highest work- loads. Minimizing the changes in their plans is also a priority. Since the consequences of unforeseen events on transportation are cancellations and/or delaying of some trips, the proposed approach deals first with single cancellations and single delayed trips and builds on these simple events to deal with more complex ones. In this approach, we try to reschedule the impacted trips within the same week in such a way that a loader is free at the truck arrival time both at the forest site and at the mill. In this way, none of the other trips will be impacted or changed. This approach provides the dispatchers with alternative plans in a few seconds. Better solutions could be found if the dispatcher is allowed to make more changes to the original plan. In the second paper, we assume a context where only one trip at a time is communicated to the drivers. The dispatcher waits until the truck finishes its trip before revealing the next trip. This context is more flexible and provides more recourse possibilities. Also, the weekly problem can be divided into daily problems since the demand is daily and the mills are open only for limited periods in the day. We use a mathematical programming model based on a time-space network representation to react to disruptions. Although the latter can have different impacts on the initial transportation plan, one key characteristic of the proposed model is that it remains valid for dealing with all the unforeseen events, regardless of their nature. Indeed, the impacts of such events are reflected in the time-space network and in the input parameters rather than in the model itself. The model is solved for the current day each time an unforeseen event is revealed. In the last paper, the fleet of trucks is heterogeneous, including trucks with onboard loaders. The route configuration of the latter is different than the regular truck routes, since they do not have to be synchronized with the loaders. We use a mathematical model where the columns can be easily and naturally interpreted as truck routes. We solve this model using column generation. As a first step, we relax the integrality of the decision variables and consider only a subset of feasible routes. The feasible routes with a potential to improve the solution are added iteratively to the model. A time-space network is used both to represent the impacts of unforeseen events and to generate these routes. The solution obtained is generally fractional and a heuristic branch-and-price algorithm is used to find integer solutions. Several disruption scenarios were developed to test the proposed approach on case studies from the Canadian forest industry and numerical results are presented for the three contexts.

Les métaheuristiques sont très utilisées dans le domaine de l'optimisation discrète. Elles permettent d’obtenir une solution de bonne qualité en un temps raisonnable, pour des problèmes qui sont de grande taille, complexes, et difficiles à résoudre. Souvent, les métaheuristiques ont beaucoup de paramètres que l’utilisateur doit ajuster manuellement pour un problème donné. L'objectif d'une métaheuristique adaptative est de permettre l'ajustement automatique de certains paramètres par la méthode, en se basant sur l’instance à résoudre. La métaheuristique adaptative, en utilisant les connaissances préalables dans la compréhension du problème, des notions de l'apprentissage machine et des domaines associés, crée une méthode plus générale et automatique pour résoudre des problèmes. L’optimisation globale des complexes miniers vise à établir les mouvements des matériaux dans les mines et les flux de traitement afin de maximiser la valeur économique du système. Souvent, en raison du grand nombre de variables entières dans le modèle, de la présence de contraintes complexes et de contraintes non-linéaires, il devient prohibitif de résoudre ces modèles en utilisant les optimiseurs disponibles dans l’industrie. Par conséquent, les métaheuristiques sont souvent utilisées pour l’optimisation de complexes miniers. Ce mémoire améliore un procédé de recuit simulé développé par Goodfellow & Dimitrakopoulos (2016) pour l’optimisation stochastique des complexes miniers stochastiques. La méthode développée par les auteurs nécessite beaucoup de paramètres pour fonctionner. Un de ceux-ci est de savoir comment la méthode de recuit simulé cherche dans le voisinage local de solutions. Ce mémoire implémente une méthode adaptative de recherche dans le voisinage pour améliorer la qualité d'une solution. Les résultats numériques montrent une augmentation jusqu'à 10% de la valeur de la fonction économique. / Metaheuristics are a useful tool within the field of discrete optimization that allow for large, complex, and difficult optimization problems to achieve a solution with a good quality in a reasonable amount of time. Often metaheuristics have many parameters that require a user to manually define and tune for a given problem. An adaptive metaheuristic aims to remove some parameters from being tuned or defined by the end user by allowing the method to specify and/or adapt a parameter or set of parameters based on the problem. The adaptive metaheuristic, using advancements in understanding of the problem being solved, machine learning, and related fields, aims to provide this more generalized and automatic toolkit for solving problems. Global optimization of mining complexes aims to schedule material movement in mines and processing streams to maximize the economic value of the system. Often due to the large number of integer variables within the model, complicated constraints, and non-linear constraints, it becomes prohibitive to solve these models using commercially available optimizers. Therefore, metaheuristics are often employed in solving mining complexes. This thesis builds upon a simulated annealing method developed by Goodfellow & Dimitrakopoulos (2016) to optimize the stochastic global mining complex. The method outlined by the authors requires many parameters to be defined to operate. One of these is how the simulated annealing algorithm searches the local neighborhood of solutions. This thesis illustrates and implements an adaptive way of searching the neighborhood for increasing the quality of a solution. Numerical results show up to a 10% increase in objective function value.

La survie des réseaux est un domaine d'étude technique très intéressant ainsi qu'une préoccupation critique dans la conception des réseaux. Compte tenu du fait que de plus en plus de données sont transportées à travers des réseaux de communication, une simple panne peut interrompre des millions d'utilisateurs et engendrer des millions de dollars de pertes de revenu. Les techniques de protection des réseaux consistent à fournir une capacité supplémentaire dans un réseau et à réacheminer les flux automatiquement autour de la panne en utilisant cette disponibilité de capacité. Cette thèse porte sur la conception de réseaux optiques intégrant des techniques de survie qui utilisent des schémas de protection basés sur les p-cycles. Plus précisément, les p-cycles de protection par chemin sont exploités dans le contexte de pannes sur les liens. Notre étude se concentre sur la mise en place de structures de protection par p-cycles, et ce, en supposant que les chemins d'opération pour l'ensemble des requêtes sont définis a priori. La majorité des travaux existants utilisent des heuristiques ou des méthodes de résolution ayant de la difficulté à résoudre des instances de grande taille. L'objectif de cette thèse est double. D'une part, nous proposons des modèles et des méthodes de résolution capables d'aborder des problèmes de plus grande taille que ceux déjà présentés dans la littérature. D'autre part, grâce aux nouveaux algorithmes, nous sommes en mesure de produire des solutions optimales ou quasi-optimales. Pour ce faire, nous nous appuyons sur la technique de génération de colonnes, celle-ci étant adéquate pour résoudre des problèmes de programmation linéaire de grande taille. Dans ce projet, la génération de colonnes est utilisée comme une façon intelligente d'énumérer implicitement des cycles prometteurs. Nous proposons d'abord des formulations pour le problème maître et le problème auxiliaire ainsi qu'un premier algorithme de génération de colonnes pour la conception de réseaux protegées par des p-cycles de la protection par chemin. L'algorithme obtient de meilleures solutions, dans un temps raisonnable, que celles obtenues par les méthodes existantes. Par la suite, une formulation plus compacte est proposée pour le problème auxiliaire. De plus, nous présentons une nouvelle méthode de décomposition hiérarchique qui apporte une grande amélioration de l'efficacité globale de l'algorithme. En ce qui concerne les solutions en nombres entiers, nous proposons deux méthodes heurisiques qui arrivent à trouver des bonnes solutions. Nous nous attardons aussi à une comparaison systématique entre les p-cycles et les schémas classiques de protection partagée. Nous effectuons donc une comparaison précise en utilisant des formulations unifiées et basées sur la génération de colonnes pour obtenir des résultats de bonne qualité. Par la suite, nous évaluons empiriquement les versions orientée et non-orientée des p-cycles pour la protection par lien ainsi que pour la protection par chemin, dans des scénarios de trafic asymétrique. Nous montrons quel est le coût de protection additionnel engendré lorsque des systèmes bidirectionnels sont employés dans de tels scénarios. Finalement, nous étudions une formulation de génération de colonnes pour la conception de réseaux avec des p-cycles en présence d'exigences de disponibilité et nous obtenons des premières bornes inférieures pour ce problème. / Network survivability is a very interesting area of technical study and a critical concern in network design. As more and more data are carried over communication networks, a single outage can disrupt millions of users and result in millions of dollars of lost revenue. Survivability techniques involve providing some redundant capacity within the network and automatically rerouting traffic around the failure using this redundant capacity. This thesis concerns the design of survivable optical networks using p-cycle based schemes, more particularly, path-protecting p-cycles, in link failure scenarios. Our study focuses on the placement of p-cycle protection structures assuming that the working routes for the set of connection requests are defined a priori. Most existing work carried out on p-cycles concerns heuristic algorithms or methods suffering from critical lack of scalability. Thus, the objective of this thesis is twofold: on the one hand, to propose scalable models and solution methods enabling to approach larger problem instances and on the other hand, to produce optimal or near optimal solutions with mathematically proven optimality gaps. For this, we rely on the column generation technique which is suitable to solve large scale linear programming problems. Here, column generation is used as an intelligent way of implicitly enumerating promising cycles to be part of p-cycle designs. At first, we propose mathematical formulations for the master and the pricing problems as well as the first column generation algorithm for the design of survivable networks based on path-protecting p-cycles. The resulting algorithm obtains better solutions within reasonable running time in comparison with existing methods. Then, a much more compact formulation of the pricing problem is obtained. In addition, we also propose a new hierarchical decomposition method which greatly improves the efficiency of the whole algorithm and allows us to solve larger problem instances. As for integer solutions, two heuristic approaches are proposed to obtain good solutions. Next, we dedicate our attention to a systematic comparison of p-cycles and classical shared protection schemes. We perform an accurate comparison by using a unified column generation framework to find provably good results. Afterwards, our study concerns an empirical evaluation of directed and undirected link- and path-protecting p-cycles under asymmetric traffic scenarios. We show how much additional protection cost results from employing bidirectional systems in such scenarios. Finally, we investigate a column generation formulation for the design of p-cycle networks under availability requirements and obtain the first lower bounds for the problem.

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48]. / The capacitated location-routing problem (CLRP) arises as a key problem in the design of distribution networks. It generalizes both the capacitated facility location problem (CFLP) and the multiple depot vehicle routing problem (MDVRP), the first by considering additional routing decisions and the second by adding the location decision variables. In this thesis we use different mathematical programming tools to develop and specialize new models and algorithms for solving the CLRP. In Chapter 3, three new models are presented for the CLRP based on vehicle-flow and commodity-flow formulations, all of which are shown to dominate, in terms of the linear relaxation lower bound, the original two-index vehicle-flow formulation [19]. Known valid inequalities are complemented with some new ones and included using separation algorithms that in many cases generalize extisting ones found in the literature. Computational experiments suggest that flow models can be efficient for dealing with small or medium size instances of the CLRP (50 customers or less). In Chapter 4, a new branch-and-cut-and-price exact algorithm is introduced for the CLRP based on a set-partitioning formulation. The pricing problem is a shortest path problem with resource constraints (SPPRC). In particular, we consider a relaxation of such problem in which routes are allowed to contain cycles of length three or more. This is complemented with the development of new valid inequalities that are shown to be effective for closing the optimality gap as well as to restrict the appearance of cycles. Computational experience supports the fact that this method is now the best exact method for the CLRP. In Chapter 5, we introduce a new metaheuristic with the aim of finding good quality solutions in short or moderate computing times. First, a bundle of good solutions is generated with the help of a greedy randomized adaptive search procedure (GRASP). Following this, a blending procedure is applied with the aim of producing a better upper bound as a combination of all the others in the bundle. An iterative destroy-and-repair method is then applied using a location-reallocation model that generalizes the reallocation model due to de Franceschi et al. [48].

Les problèmes d’optimisation discrète sont pour beaucoup difficiles à résoudre, de par leur nature combinatoire. Citons par exemple les problèmes de programmation linéaire en nombres entiers. Une approche couramment employée pour les résoudre exactement est l’approche de Séparation et Évaluation Progressive. Une approche différente appelée « Resolution Search » a été proposée par Chvátal en 1997 pour résoudre exactement des problèmes d’optimisation à variables 0-1, mais elle reste mal connue et n’a été que peu appliquée depuis. Cette thèse tente de remédier à cela, avec un succès partiel. Une première contribution consiste en la généralisation de Resolution Search à tout problème d’optimisation discrète, tout en introduisant de nouveaux concepts et définitions. Ensuite, afin de confirmer l’intérêt de cette approche, nous avons essayé de l’appliquer en pratique pour résoudre efficacement des problèmes bien connus. Bien que notre recherche n’ait pas abouti sur ce point, elle nous a amené à de nouvelles méthodes pour résoudre exactement les problèmes d’affectation généralisée et de localisation simple. Après avoir présenté ces méthodes, la thèse conclut avec un bilan et des perspectives sur l’application pratique de Resolution Search. / The combinatorial nature of discrete optimization problems often makes them diffi- cult to solve. Consider for instance integer linear programming problems, which are commonly solved using a Branch-and-Bound approach. An alternative approach, Resolution Search, was proposed by Chvátal in 1997 for solving 0-1 optimization problems, but remains little known to this day and as such has seen few practical applications. This thesis attempts to remedy this state of affairs, with partial success. Its first contribution consists in the generalization of Resolution Search to any discrete optimization problem, while introducing new definitions and concepts. Next, we tried to validate this approach by attempting to solve well-known problems efficiently with it. Although our research did not succeed in this respect, it lead us to new methods for solving the generalized assignment and uncapacitated facility location problems. After presenting these methods, this thesis concludes with a summary of our attempts at practical application of Resolution Search, along with further perspectives on this matter. / Thèse réalisée en cotutelle avec l'Université d'Avignon.

Le mémoire présente le problème de la planification tactique des “blocks” pour le transport ferroviaire intermodal, qui a été peu étudié jusqu’à présent. Nous proposons un nouveau modèle de design de réseau en tenant compte de la spécificité du transport intermodal. La recherche se concentre sur le contexte nord-américain et fait suite à une étroite collaboration avec l’une des principales compagnies ferroviaires nord-américaines. Le “blocking” constitue une importante opération de transport ferroviaire de marchandises, par laquelle des wagons d’origines et de destinations potentiellement différentes sont regroupés pour être d´eplacés et manipulés comme une seule unité, ce qui permet des économies d’échelle. La littérature se limite aux travaux traitant le problème classique du blocage des trains, où la demande est exprimée en termes de wagons. A notre connaissance, aucun travail préalable n’a été consacrè à un contexte de transport intermodal, où la demande est exprimée en termes de conteneurs à dèplacer d’un terminal d’origine donné vers un terminal de destination donné, introduisant ainsi un processus de consolidation supplémentaire. Nous proposons un modèle de “blocking” qui prend en compte plusieurs types de conteneurs et wagons, intégrant l’affectation conteneur-wagon. Nous présentons un nouveau modèle de design de réseau à trois couches en temps continu formulé sous la forme d’un programme linéaire mixte en nombres entiers (MILP), dans le but de minimiser le coût total de transport composé par la sélection de blocs, les coûts d’exploitation et la gestion du coût de la demande. Le modèle peut être résolu en utilisant un solveur commercial pour des tailles réalistes. Nous illustrons les performances et l’intérêt de la méthode proposée à travers une étude de cas approfondie d’un important chemin de fer nord-américain. / The thesis presents the tactical block-planning problem for intermodal railroads, which has been little studied so far. We propose a new block service network design model considering the specificity of intermodal rail. The research focuses on the North American context and follows a close collaboration with one of the major North American railroad companies. Blocking constitutes an important rail freight transport operation, by which cars with potentially different origins and destinations are grouped to be moved and handled as a single unit, yielding economies of scale. The literature is limited to works addressing the classical train blocking problem, where demand is given in terms of cars to be blocked among specific OD pairs. To the best of our knowledge, no prior work has been dedicated to an intermodal transportation context, where demand is expressed in terms of containers to be moved from a given origin terminal to a given destination terminal, hence introducing an additional consolidation process. We propose a blocking model that considers several types of containers and railcars, integrating the container-to-car assignment. We present a new continuous-time, three-layer service network design model formulated as a Mixed Integer Linear Program (MILP), with the objective of minimizing the total transportation cost composed by block selection, operation costs, and handling demand cost. The model can be solved using commercial solver for realistic sizes. We illustrate the performance and interest of the proposed method through an extensive case study of a major North American railroad.

Cette thèse étudie le problème du routage des locomotives qui se pose à la Compagnie des chemins de fer nationaux du Canada (CN) - le plus grand chemin de fer au Canada en termes de revenus et de taille physique de son réseau ferroviaire. Le problème vise à déterminer la séquence des activités de chaque locomotive sur un horizon de planification donné. Dans ce contexte, il faut prendre des décisions liées à l'affectation de locomotives aux trains planifiés en tenant compte des besoins d'entretien des locomotives. D’autres décisions traitant l'envoi de locomotives aux gares par mouvements à vide, les déplacements légers (sans tirer des wagons) et la location de locomotives tierces doivent également être prises en compte. Sur la base d'une formulation de programmation en nombres entiers et d'un réseau espace-temps présentés dans la littérature, nous introduisons une approche par horizon roulant pour trouver des solutions sous-optimales de ce problème dans un temps de calcul acceptable. Une formulation mathématique et un réseau espace-temps issus de la littérature sont adaptés à notre problème. Nous introduisons un nouveau type d'arcs pour le réseau et de nouvelles contraintes pour le modèle pour faire face aux problèmes qui se posent lors de la division de l'horizon de planification en plus petits morceaux. Les expériences numériques sur des instances réelles montrent les avantages et les inconvénients de notre algorithme par rapport à une approche exacte. / This thesis addresses the locomotive routing problem arising at the Canadian National Railway Company (CN) - the largest railway in Canada in terms of both revenue and the physical size of its rail network. The problem aims to determine the sequence of activities for each locomotive over the planning horizon. Besides assigning locomotives to scheduled trains and considering scheduled locomotive maintenance requirements, the problem also includes other decisions, such as sending locomotives to stations by deadheading, light traveling, and leasing of third-party locomotives. Based on an Integer Programming formulation and a Time-Expanded Network presented in the literature, we introduce a Rolling Horizon Approach (RHA) as a method to find near-optimal solutions of this problem in acceptable computing time. We adapt a mathematical formulation and a space-time network from the literature. We introduce a new type of arcs for the network and new constraints for the model to cope with issues arising when dividing the planning horizon into smaller ones. Computational experiments on real-life instances show the pros and cons of our algorithm when compared to an exact solution approach.

Cette thèse porte sur la prévision de la demande des expéditeurs et des offres de capacité des transporteurs pour la planification opérationnelle des systèmes `Many-to-One-to-Many' (M1M). Un tel système agit comme un décideur intermédiaire entre les expéditeurs et les transporteurs en coordonnant le transport des marchandises des expéditeurs aux destinataires en utilisant les capacités offertes par les transporteurs. Le décideur prend ses décisions dans un horizon de planification opérationnelle, en optimisant ces décisions en tenant compte de l'incertitude sur les périodes futures. Pour accompagner les décisions du décideur, il est essentiel de prédire les nouvelles demandes des expéditeurs et les nouvelles capacités des transporteurs. Cela conduit à des problèmes de prévision de séries chronologiques à plusieurs variables et à plusieurs étapes. L'objectif de ce travail est d'analyser l'impact des erreurs de prévision sur la qualité de la solution pour un problème de planification opérationnelle M1M donné. Cette thèse présente d'abord la structure du système M1M, la planification opérationnelle et les tâches de prévision associées. Nous décrivons la caractérisation des demandes des expéditeurs et des offres des transporteurs ainsi que comment la prévision peut soutenir les décisions en définissant les informations nécessaires pour le décideur sur l'horizon opérationnel. Nous couvrons ensuite l’optimisation de l’affectation charge-transporteur en introduisant un modèle d'optimisation déterministe et les prévisions utilisées en entrée. En l'absence de données réelles, nous générons un ensemble de données synthétiques qui est ensuite utilisé pour estimer les modèles de prévision. L'objectif est de définir quelques modèles de prévision qui présentent des erreurs afin que nous puissions évaluer leur impact sur la qualité de la solution pour le problème de planification opérationnelle. Dans ce contexte, nous comparons plusieurs modèles ARIMA pour prédire les futures demandes et offres. Nous constatons que les modèles avec des erreurs de prévision relativement faibles peuvent conduire à des améliorations significatives de la qualité de la solution. Enfin, nous exposons quelques pistes de recherches futures. / This thesis is about forecasting new shipper-demand requests and carrier-capacity offers for operational planning of Many-to-One-to-Many (M1M) systems. Such a system acts as an intermediary decision-maker between shippers and carriers, coordinating the transportation of goods from shippers to consignees (shipment recipients) using capacity offered from carriers. The decision-maker makes the decisions within an operational planning horizon, optimizing these decisions accounting for uncertainty over future time periods. To support the decisions, forecasting new shipper-demands and carrier capacities is essential. This leads to multi-variate multi-step time series forecasting problems. The objective of this work is to analyze the impact of forecast errors on the solution quality for a given M1M operational planning optimisation method. This thesis first presents the M1M system structure, operational planning, and related forecasting tasks. It explains the characterization of the shipper requests and carrier offers. We describe how forecasting can support the decisions by defining the needed information for the decision-maker over the operational horizon. We then cover the optimization of load-to-carrier assignments introducing a deterministic formulation and the forecasts used as input. In the absence of real data, we generate a synthetic data set that is then used for estimating forecasting models. The aim is to define a few forecasting models that exhibit some errors so that we can assess their impact on the solution quality for the operational planning problem. In this context, we compare several ARIMA models to predict future requests and offers. We find that the models with relatively low forecast errors can lead to significant improvements in solution quality. Finally, we outline a few directions for future research.

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.

Dans ce mémoire, nous présentons un nouveau type de problème de confection de tour- née pour un seul véhicule avec cueillettes et livraisons et contrainte de chargement. Cette variante est motivée par des problèmes similaires rapportés dans la littérature. Le véhi- cule en question contient plusieurs piles où des colis de hauteurs différentes sont empilés durant leur transport. La hauteur totale des items contenus dans chacune des piles ne peut dépasser une certaine hauteur maximale. Aucun déplacement n’est permis lors de la li- vraison d’un colis, ce qui signifie que le colis doit être sur le dessus d’une pile au moment d’être livré. De plus, tout colis i ramassé avant un colis j et contenu dans la même pile doit être livré après j. Une heuristique à grand voisinage, basé sur des travaux récents dans le domaine, est proposée comme méthode de résolution. Des résultats numériques sont rapportés pour plusieurs instances classiques ainsi que pour de nouvelles instances. / In this work, we consider a new type of pickup and delivery routing problem with last- in-first-out loading constraints for a single vehicle with multiple stacks. This problem is motivated by similar problems reported in the literature. In the problem considered, items are collected and put on top of one of multiple stacks inside the vehicle, such that the total height of the items on each stack does not exceed a given threshold. The loading constraints state that if items i and j are in the same stack and item i is collected before item j, then i must be delivered after j. Furthermore, an item can be delivered only if it is on the top of a stack. An adaptive large neighborhood heuristic, based on recent studies in this field, is proposed to solve the problem. Numerical results are reported on many classical instances reported in the literature and also on some new ones.