Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

L'intérêt pour les transports collectifs ne cesse de croître avec la prise de conscience des problèmes engendrés par le «tout automobile». Dans ce contexte, les transports en commun en site propre, et particulièrement les tramways, reconquièrent les villes. Toutes ces nouvelles orientations représentent des sommes d'argent considérables, c'est pourquoi les questions de conception et d'évaluation des projets de transport public sont cruciaux.<br />Cette thèse développe une méthode qualitative d'aide à la conception et à l'évaluation des réseaux de transports collectifs et s'intéresse, plus spécifiquement aux lignes de tramway. La méthode constitue aussi un outil puissant de pondération des outils quantitatifs.<br />Toute personne possède une représentation mentale de l'espace urbain qu'elle parcourt réellement ou virtuellement. Les réseaux de transport collectif influencent les cartes mentales de l'espace urbain. Ils contraignent la perception que les gens ont de la ville à travers leurs itinéraires mais aussi modifient les distances entre les points, créant un espace temps spécifique. Cependant, les cartes mentales, tels des instruments de navigation, agissent par activations sélectives ou abandon de certaines branches du réseau. C'est pourquoi l'étude des représentations mentales, de leur capacité à intégrer des éléments nouveaux comme une nouvelle ligne de transport public est capitale.<br />Cette recherche étudie les éléments constitutifs des cartes mentales puis la manière dont celles-ci évoluent avec la mise en service d'une nouvelle ligne de transport collectif. Elle s'intéresse aussi à la taille, à la localisation des territoires d'appartenance des individus et à leurs évolutions, question essentielle pour désenclaver les quartiers en difficulté.<br />Les enseignements cernent les éléments du transport collectif qui déterminent fortement les représentations mentales. La topologie de celles-ci, les seuils de perception sont analysés en particulier et partiellement expliqués. Enfin, les cartes mentales peuvent se regrouper par types selon leur capacité à intégrer des éléments nouveaux. Chaque type correspond à un profil d'individu. Cette conclusion est capitale car elle permet, par l'utilisation de la méthode, d'évaluer dans quelle mesure les représentations mentales des individus, concernés par un projet de transport collectif, sont enclines à intégrer la future ligne ou non.<br />Les résultats de cette recherche, ainsi que la méthode développée, sont autant d'enseignements précieux pour un aménageur ou, de manière générale, un décideur en matière d'urbanisme et de transport.

Les réseaux de transport de gaz naturel nécessitent des investissements très importants pour faire face à une demande toujours croissante en énergie et pour satisfaire des contraintes réglementaires de plus en plus importantes. En effet, la libéralisation des marchés gaziers a imposé aux opérateurs de transport de gaz, d'une part, des règles de transparence d'un monopole naturel pour justifier leurs dépenses et, in fine, leurs tarifs, et, d'autre part, des objectifs de fluidification du marché afin de faciliter l'accès à la concurrence des clients finaux. Ces investissements majeurs justifient l'utilisation de techniques d'optimisation permettant de réduire leurs coûts. Au vue de la présence de choix discrets en combinaison avec des contraintes physiques non linéaires, les programmes à résoudre sont des programmes d'optimisation non linéaires en nombres entiers (PNLNE) de grandes tailles. Ce type de programmes étant connu pour être particulièrement difficile à résoudre en temps polynomial (NP-difficile), des méthodes avancées d'optimisation doivent être mises en œuvre pour obtenir des réponses réalistes. Les objectifs de cette thèse sont au nombre de trois. Il s'agit d'abord de proposer une modélisation des problèmes d'investissement dans les réseaux de transport de gaz à partir des motivations du monde industriel. Il s'agit ensuite d'identifier les méthodes et algorithmes les plus adéquats pour résoudre les problèmes ainsi formulés. Il s'agit enfin d'évaluer les avantages et les inconvénients de ces méthodes à l'aide d'applications numériques sur des cas réels.

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.

La première partie de cette thèse, concerne une étude de robustesse des algorithmes de points intérieurs prédicteurs correcteurs, ainsi qu'une approche par décomposition de cette méthode pour la résolution de problè mes de multiflot. Dans la deuxième partie, nous nous intéressons au Problème de Sécurisation Globale dont l'objectif est de déterminer un multiflot (qui transporte toute demande de son noeud origine à son noeud destination en respectant la loi de Kirchhoff) et l'investissement de moindre coût en capacité s nominale et de réserve qui assure le routage nominal et garantit sa survie par reroutage global. Dans notre modèle les routages et les capacités peuvent être fractionnés. PSG se formule alors comme un problème linéaire de grande taille avec plusieurs niveaux de couplage. Sa structure particulière appelle à l'emploi d'algorithmes de décompositions. Nous proposons quatre méthodes utilisant la technique de génération de colonnes. Les deux premières sont basées sur les techniques proximales. Leur tâche principale consiste en la résolution de sous problèmes quadratiques indépendants. Le troisième algorithme s'inspire de l'approche de points intérieurs décrite à la première partie. Pour finir, nous intégrons une procédure d'élimination de chemins dans une adaptation d'un solveur de points intérieurs. Nous reportons des résultats numériques obtenus en testant ces algorithmes sur des données réelles fournies par le CNET.

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.

Avec la croissance exponentielle du trafic lié au développement de la vidéo et des services d’Internet, les systèmes WDM évoluent régulièrement pour augmenter la capacité de la fibre optique. Pour atteindre cet objectif, les concepts d’«élasticité» et de grille WDM flexible ont été introduits et ont conduit au développement de nouveaux équipements optiques. Dans le cadre des réseaux flexibles, le dimensionnement de réseaux se complexifie, et les outils de dimensionnement traditionnels doivent être repensés. De plus, des problèmes stratégiques et technologiques apparaissent avec l’arrivée de ce nouveau concept. Presque tous les équipements optiques doivent être remplacés par d’autres mieux adaptés, entraînant un coût de déploiement additionnel. Ce travail propose et implémente des nouveaux outils mathématiques et logiciels de dimensionnement multicouche des réseaux optiques flexibles. Des cas d’usage intéressants à étudier dans le cadre des réseaux flexibles sont aussi identifiés et proposés dans cette thèse. De même, ce travail traite les problèmes principaux émanant de la flexibilité optique. De façon plus spécifique, nous étudions le problème de la fragmentation du spectre WDM flexible dans les réseaux d’opérateurs et proposons des solutions. De plus, nous proposons et évaluons un cas d’usage qui combine l’élasticité et la restauration optique du trafic dans un contexte multicouche. Enfin, nous identifions et proposons une solution au problème lié à l’utilisation des amplificateurs optiques dans les réseaux flexibles / With the exponential growth of traffic driven by video and Internet services, WDM systems evolve regularly to increase optical fiber capacity. To meet the relentless need for capacity, advanced features have been integrated into optical layer leading to the notion of channel flexibility (datarate elasticity, flex-grid). In contrast, with the potential benefits that optical channel flexibility provides, network dimensioning gets even more complicated, and traditional dimensioning tools should be rethought. Moreover, some strategic and technological problems appear with optical layer flexibility. Almost, all legacy equipment in the optical layer needs to be replaced by greenfield and well-adapted equipment, which requires new investments. Furthermore, spectrum fragmentation has been identified as the main disadvantage of optical layer flexibility. This work proposes and implements different mathematical multilayer tools for network dimensioning with the aim of evaluating optical layer flexibility. It identifies profitable and advantageous use cases and networking scenarios that bring forward the interest of flex-grid and elasticity. This work also deals with the potential troubles of flexibility and provides solutions to them. Specifically, we thoroughly investigate spectrum fragmentation in operator network context, and propose some traffic engineering strategies. We propose and evaluate a new use case that combines datarate elasticity and optical restoration within a multilayer context. Finally, we state a new drawback of flex-grid technology regarding the use of legacy optical amplifiers with flex-grid networks and provide a solution to overcome this problem

This thesis presents an exploration into the topic of decision-focused learning (DFL) for network design. The approach represents a novel experiment combining machine learning (ML) with mathematical optimization. In recent years, the progress of DFL has demonstrated success in key optimization problems such as the Knapsack problem. However, the vast amount of existing research deals with optimization structures where unknown parameters are found in the objective function. The primary contribution of this study is to apply a DFL framework to an optimization problem where unknown parameters are found in the constraints. The aim is to apply a DFL approach to the multi-commodity network design (MCND) problem. We aim to explore the ability of DFL to predict the demand for commodities in the MCND. The study focuses on special loss functions such as Smart Predict then Optimize (SPO) and evaluates how a model makes predictions while accounting for the downstream optimization where target variables are in the constraints. Through computational experimentation and modifications, we demonstrate the performance of the framework. SPO tends to artificially underpredict demand such that it designs networks that increase operation costs due to its reliance on overflow penalties for realized demands. The underprediction of demand stems from the SPO loss function that focuses on decreasing regret more than prediction errors in this setting. It is clear from the results that SPO is able to learn how to reduce the cost of networks low demand predictions but does not accurately represent the true demand. In conclusion, this thesis explores the use of DFL in the MCND context. Our research highlights potential developments that DFL could have in mathematical optimization with a motivating example while also testing one of the popular DFL approaches, SPO. While the approach we used was not able to show very promising results, it suggests that DFL does have potential in these types of problems if approaches can be better customized. / Cette thèse présente une exploration du thème de l’apprentissage centré sur la décision (DFL) pour la conception de réseaux. L’approche représente une nouvelle solution combinant l’apprentissage automatique et la programmation mathématique. Ces dernières années, les progrès de l’apprentissage axé sur les décisions ont été couronnés de succès dans des problèmes d’optimisation clés tels que le problème du sac à dos. Cependant, la plupart des recherches existantes traitent des structures d’optimisation où des paramètres inconnus se trouvent dans la fonction objectif. La principale contribution de cette étude est d’appliquer un cadre DFL à un problème d’optimisation où des paramètres inconnus se trouvent dans les contraintes. Plus précisement, l’objectif est d’appliquer une approche DFL au problème Multi-Commodity Network Design (MCND). L’étude se concentre sur des fonctions de perte spéciales telles que Smart Predict then Optimize (SPO) et évalue comment un modèle fait des prédictions tout en tenant compte de l’optimisation en aval où les variables cibles sont dans les contraintes. Nous démontrons les performances de ce cadre par le biais d’expérimentations et de modifications informatiques. SPO a tendance à sous-estimer artificiellement la demande, de sorte qu’il conçoit des réseaux qui augmentent les coûts d’exploitation en raison de sa dépendance à l’égard des pénalités de débordement pour les demandes réalisées. La sous-estimation de la demande est due à la fonction de perte SPO qui se concentre sur la diminution du regret plutôt que sur les erreurs de prédiction dans ce contexte. Les résultats montrent clairement que SPO est capable d’apprendre à réduire le coût des réseaux en prédisant une faible demande, mais qu’il ne représente pas fidèlement la demande réelle. En conclusion, cette thèse explore l’utilisation du DFL dans le contexte de SPO pour MCND. Notre recherche met en évidence les développements potentiels que la DFL pourrait avoir pour des problèmes de conception de réseau avec un exemple illustratif tout en testant l’une des approches DFL populaires, SPO. Bien que l’approche que nous avons utilisée n’ait pas été en mesure de montrer des résultats très prometteurs, elle suggère que le DFL a du potentiel dans ces types de problèmes si les approches peuvent être mieux adaptés.

No description available.