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.

Dans cette thèse, on s'intéresse à deux problèmes de conception de réseaux, utilisant la technologie OFDM multi-bandes. Le premier problème concerne la conception d'un réseau mono-couche avec contraintes spécifiques. Nous donnons une formulation en PLNE pour ce problème et étudions le polyèdre associé à sa restriction sur un arc. Nous introduisons deux familles d'inégalités valides définissant des facettes et développons un algorithme de coupes et branchements pour le problème. Nous étudions la variante multicouche du problème précédent et proposons plusieurs PLNE pour le modéliser. Nous identifions plusieurs familles de facettes et discutons des problèmes de séparation associés. Nous développons un algorithme de coupes et branchements utilisant l'ensemble des contraintes identifiées. Enfin, une formulation compacte et deux formulations basées sur des chemins sont proposées pour le problème. Nous présentons deux algorithmes de génération de colonnes et branchements pour le problème. / In this thesis we consider two capacitated network design (CND) problems, using OFDM multi-band technology. The first problem is related to single-layer network design with specific requirements. We give an ILP formulation for this problem and study the polyhedra associated with its arc-set restriction. We describe two families of facet defining inequalities. We devise a Branch-and-Cut algorithm for the problem. Next, we investigate the multilayer version of CND using OFDM technology. We propose several ILP formulations and study the polyhedron associated with the first (cut) formulation. We identify several classes of facets and discuss the related separation problem. We devise a Branch-and-Cut algorithm embedding valid inequalities of both single-layer and multilayer problems. The second formulation is compact, and holds a polynomial number of constraints and variables. Two further path formulations are given which yield two efficient Branch-and-Price algorithms for the problem.

Le problème de routage de véhicules avec fenêtres de temps et routes multiples (MTVRPTW) est une généralisation du problème de routage de véhicules avec fenêtres de temps (VRPTW). Dans le MTVRPTW, on autorise un véhicule à effectuer plusieurs routes durant une période de planification, ce qui permet d'optimiser les transports lorsque le nombre de véhicules est limité et peu élevé. Nous proposons dans cette thèse la première méthode exacte permettant de résoudre ce problème. Notre modélisation prend la forme d'un problème de couverture des clients dont les variables sont des routes. Des contraintes d'exclusion mutuelle expriment la disponibilité des véhicules. Nous utilisons la Génération de Colonnes, avec un sous-problème effectuant, par programmation dynamique, une recherche de plus court chemin élémentaire contraint en ressources. Notre méthode de programmation dynamique tient compte des dépendances de plusieurs ressources grâce à la notion de label représentatif, et est ainsi plus efficace qu'une approche classique. La méthode de Génération de Colonnes est incluse dans un schéma de Branch and Price composé de deux types de branchement, l'un basé sur les arcs, l'autre sur la résolution d'un VRPTW. Nous avons mis en place diverses méthodes accélératrices spécifiques du MTVRPTW. Nous donnons les résultats de l'algorithme sur les instances de Solomon. Des résultats issus de méthodes exactes étaient disponibles dans la littérature pour le MTVRPTW avec durée limite sur les routes. Nous avons proposé un nouvel algorithme plus performant, et basé sur nos méthodes, pour cette variante du problème. / The multi-trip vehicle routing problem with time windows (MTVRPTW) is a generalization of the vehicle routing problem with time windows (VRPTW). In the MTVRPTW, one vehicle can perform several trips during a planning period. This allows optimizing the transport when the number of vehicles is limited and small.We propose here the first exact method for solving this problem.Our model is designed as a coverage problem for customers where the variables are trips. Mutual exclusion constraints express the availability of vehicles. We use a column generation scheme in which the sub-problem is an elementary shortest path problem with resource constraints (ESPPRC). Our dynamic programming method for ESPPRC takes into account dependencies of several resources through the concept of representative label. It is thus more efficient than a conventional approach. The column generation method is included in a Branch and Price scheme with two types of branching. One is based on arc selection, and the other on solving a VRPTW. We have implemented various accelerating methods which are specific to MTVRPTW. We give the results of our algorithm on Solomon instances.Results from exact methods were available in the literature for the MTVRPTW with time limit on the trips. We proposed a new and more efficient algorithm, based on our methods, to solve this variant of the problem.

.

Le bloc opératoire constitue l'un des secteurs les plus coûteux et les plus importants dans un établissement hospitalier. Afin, d'utiliser de manière efficace et rationnelle les ressources (humaines et matérielles) disponibles tout en assurant une bonne qualité de service vis-à-vis des patients, la planification du bloc opératoire est devenue l'une des premières préoccupations des établissements hospitaliers. Le problème de planification du bloc opératoire consiste à déterminer pour un horizon de plusieurs jours, l'ensemble d'interventions qui seront réalisées dans chaque salle opératoire. Ce problème a été traité dans la littérature et plusieurs approches de planification ont été proposées. Toutefois, les approches existantes sont essentiellement basées sur des modèles déterministes qui font abstraction de toutes sortes d'aléas. Or, le bloc opératoire est sujet à nombreuses formes d'aléas qui concernent essentiellement la chirurgie d'urgence et les durées d'interventions. À ce titre, l'objectif de notre travail de recherche est de développer des modèles et méthodes pour la planification des activités chirurgicales dans le bloc opératoire tout en tenant compte des aléas importants. Dans le cadre de cette thèse, nous avons proposé des modèles stochastiques qui (i) capturent les éléments essentiels à considérer lors de la planification des activités chirurgicales, (ii) permettent de modéliser de manière explicite différentes formes d'aléas tels que les incertitudes relatives aux durées des interventions et à la chirurgie d'urgence, et (iii) peuvent être facilement étendus pour modéliser d'autres contraintes dues aux pratiques du terrain. Nous avons aussi développé plusieurs approches et méthodes d'optimisation complètes et complémentaires pour la planification stochastique du bloc opératoire. Moyennant des expérimentations numériques, nous avons évalué les performances de ces différentes approches et nous avons montré leurs efficacités. En particulier, nous avons montré que des gains considérables peuvent être réalisés moyennant une modélisation stochastique du problème de planification du bloc opératoire.

Ce travail a pour objet la résolution d'un problème combinatoire posé dans le cadre de la régulation court terme (ou dynamique) du trafic aérien. On cherche à déterminer pour chaque vol régulable une trajectoire en 4 dimensions réalisable de manière à respecter les contraintes de capacité des secteurs tout en minimisant la somme des coûts des trajectoires choisies. Le problème est modélisé par un programme linéaire mixte. Une représentation ad hoc du système aérien sert de support à la modélisation fine des trajectoires. Un processus global de résolution basé sur la génération de colonnes couplée à la technique de branch-and-bound est détaillé. Les colonnes du problème représentant des trajectoires, la génération de colonnes par le sous problème de tarification se traduit par la recherche de chemins quadridimensionnels sur un réseau continu et dynamique. Un algorithme spécifique basé sur les algorithmes de plus court chemin par marquage et sur la programmation dynamique est développé et testé. Toute la méthode est évaluée sur des instances réelles représentant l'espace aérien géré par la CFMU, l'organisme européen de gestion des flux de trafic aérien. Les résultats obtenus en un temps de calcul compatible avec le contexte opérationnel valident finalement la méthode développée.

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.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

L'optimisation multi-objectif concerne la résolution de problèmes pour lesquels plusieurs objectifs (ou critères) contradictoires sont pris en compte. Contrairement aux problèmes d'optimisation ayant un seul objectif, un problème multi-objectif ne possède pas une valeur optimale unique mais plutôt un ensemble de points appelés "ensemble non dominé". Les bornes inférieures et supérieures d'un problème multi-objectif peuvent être également décrites par des ensembles. Dans la pratique, les variables utilisées en optimisation multiobjectif représentent souvent des objets non fractionnables et on parle alors de problèmes multi-objectif en nombres entiers. Afin d'obtenir de meilleures bornes qui peuvent être utilisées dans la conception de méthodes exactes, certains problèmes sont formulés avec un nombre exponentiel de variables de décision et ces problèmes sont résolus par la méthode de génération de colonnes. Les travaux de cette thèse visent à contribuer à l'étude de l'utilisation de la génération de colonnes en programmation linéaires en nombres entiers multi-objectif. Pour cela nous étudions un problème de tournées de véhicules bi-objectif qui peut être considéré comme une généralisation de plusieurs autres problèmes de tournées de véhicules. Nous proposons des formulations mathématiques pour ce problème et des techniques pour accélérer le calcul des bornes inférieures par génération de colonnes. Les sous-problèmes qui doivent être résolus pour le calcul des bornes inférieures ont une structure similaire. Nous exploitons cette caractéristique pour traiter simultanément certains sous-problèmes plutôt qu'indépendamment.

Notre travail porte sur l'étude du Problème de Routage et d'Allocation de Longueur d'Onde (Routing and Wavelength Allocation - RWA) dans des réseaux optiques WDM, indépendamment de la topologie physique sous-jacente. Le problème a été idntifié comme étant NP-difficile et plusieurs approches, tant exactes qu'approchées, existent. Nous fournissons d'abord une revue de littérature dans laquelle nous présentons quelques formulations mathématiques pour le problème ainsi que plusieurs manières d'obtenir des bornes inférieures et des heuristiques. Nous considérons le problème min-RWA dans lequel on doit satisfaire un certain nombre de requêtes avec le moins de longueurs d'onde possible. Nous présentons une méthodologie reposant sur une recherche locale de type Descente à Voisinage Variable (Variable Neighborhood Descent - VND) que l'on appelle VND-BFD. Son objectif principal est de supprimer des longueurs d'onde. Nous présentons également une méthode hybride VND-BT. Ensuite, nous proposons une nouvelle approche, elle-aussi reposant sur la VND. Elle consiste à ré-arranger les requêtes entre les longueurs d'onde disponibles. Lorsqu'elle atteint un optimum local, une procédure de perturbation est appliquée et le schéma est similaire à la Recherche Locale Itérée (Iterated Local Search - ILS). Quatre variantes sont définies selon les stratégies appliquées dans VND et ILS : VNDr-ILSp, VNDe-ILSp, VNDr-ILS5p et VNDe-ILS5p. Les résultats expérimentaux montrent que cette nouvelle approche est plus performante, en particulier la version VNDe-ILS5p. La méthode est compétitive avec les meilleures méthodes de la littérature puisque VNDe-ILS5p a permis d'améliorer une grande partie des meilleures solutions connues sur les instances standard du min-RWA. Enfin, nous considérons aussi le problème max-RWA dans lequel on doit maximiser le nombre de requêtes traitées avec un nombre donné de longueurs d'onde. Nous proposons des modèles compacts ainsi que des améliorations destinées à accélérer la résolution par des solveurs en nombre entiers. Après avoir décrit des modèles existants utilisant la génération de colonnes, nous proposons un nouveau modèle, PG-MAX-IS-IRC, utilisant lui-aussi la génération de colonnes. Il permet d'obtenir des bornes supérieures de même qualité en un temps très fortement réduit.