Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Le but de cette thèse est l'exploration du domaine de l'optimisation de la topologie radiale d'un réseau de distribution en temps réel pour différents régimes d'exploitation. Nous avons ainsi développé différents outils de calcul performants, en particulier une approche unifiée qui se prête d'une part pour l'optimisation pour le régime normal d'exploitation, d'autre part pour établir un plan de reprise de service pour les zones îlotées suite à la défaillance d'un élément du réseau. Afin de satisfaire la contrainte temps réel, nous nous sommes basés sur des méthodes heuristiques permettant de s'approcher au plus de l'optimum global en un temps de calcul très court. La vérification de la qualité des solutions obtenues par des méthodes heuristiques est effectuée à l'aide d'autres méthodes d'optimisation plus dédiées à la recherche de l'optimum global. En validant la méthodologie proposée sur des réseaux de distribution réels à grande taille, nous avons montré l'efficacité de notre approche tant au niveau de la qualité des résultats qu'au niveau du temps de calcul.

Avec l’augmentation progressive de la population dans les grandes villes, comme Paris, nous prévoyons d’ici 2050 une augmentation de 50% du trafic routier. En considérant les embouteillages et la pollution que cette augmentation va générer, on voit clairement la nécessité de nouveaux système de mobilité plus durables, comme le covoiturage, ou plus généralement toute la mobilité partagée. En parlant de mobilité partagée, ce n’est pas seulement le partage de trajets de personnes qui ont le même itinéraire au même temps, elle inclut aussi les marchandises.Cette thèse aborde le défi de la synchronisation des flux de passagers et de marchandises dans les systèmes de mobilité urbaine et elle vis à développer des méthodes d’optimisation pour que cette synchronisation dans la mobilité partagée soit faisable. Plus précisément, elle aborde les questions de recherche suivantes:*Q1: Quelles sont les variantes des systèmes de mobilité partagée et comment les optimiser?*Q2: Comment synchroniser les déplacements de personnes et quels gains cette synchronisation peut-elle générer?*Q3: Comment combiner les flux de passagers et de fret et quels sont les avantages attendus?*Q4: Quels sont les effets de l'incertitude sur la planification et l'exploitation de systèmes de mobilité partagée?Dans un premier temps, nous étudions les différentes variantes des systèmes de mobilité partagée et nous les classifions en fonction de leurs modèles, caractéristiques, approches de résolution et contexte d'application. En se basant sur cette revue de littérature, nous identifions deux problèmes de mobilité partagés, que nous considérons en détails dans cette thèse et nous développons des méthodes d'optimisation pour les résoudre.Pour synchroniser les flux de passagers, nous étudions un modèle de covoiturage en utilisant les véhicules autonomes, personnels et partagés, et des points de rencontre où la synchronisation entre passagers peut avoir lieu. Pour cela, une méthode heuristique en deux phases est proposée et une étude de cas sur la ville de New York est présentée.Ensuite, nous développons un modèle d’optimisation qui combine les flux de passagers et de marchandises dans une région urbaine. Le but de ce modèle est d’utiliser les capacités disponibles sur une ligne de transport fixe pour transporter les passagers et des robots transportant des petits colis à leurs destinations finales en considérant que la demande de passagers est stochastique. Les résultats obtenus montrent que les solutions proposées par ces deux modèles peuvent conduire à une meilleure utilisation des systèmes de transport dans les régions urbaines. / The rise of research into shared mobility systems reflects emerging challenges, such as rising urbanization rates, traffic congestion, oil prices and environmental concerns. The operations research community has turned towards more sharable and sustainable systems of transportation. Although shared mobility comes with many benefits, it has some challenges that are restricting its widespread adoption. More research is thus needed towards developing new shared mobility systems so that a better use of the available transportation assets can be obtained.This thesis aims at developing efficient models and optimization approaches for synchronizing people and freight flows in an urban environment. As such, the following research questions are addressed throughout the thesis:*Q1: What are the variants of shared mobility systems and how to optimize them?*Q2: How can people trips be synchronized and what gains can this synchronization yields?*Q3: How can people and freight flows be combined and what are the intended benefits?*Q4: What impacts uncertainty can have on planning and operating shared mobility systems?First, we review different variants of the shared mobility problem where either (i) travelers share their rides, or (ii) the transportation of passengers and freight is combined. We then classify these variants according to their models, solution approaches and application context and We provide a comprehensive overview of the recently published papers and case studies. Based on this review, we identify two shared mobility problems, which we study further in this thesis.Second, we study a ridesharing problem where individually-owned and on-demand autonomous vehicles (AVs) are used for transporting passengers and a set of meeting points is used for synchronizing their trips. We develop a two-phase method (a pre-processing algorithm and a matching optimization problem) for assessing the sharing potential of different AV ownership models, and we evaluate them on a case study for New York City.Then, we present a model that integrates freight deliveries to a scheduled line for people transportation where passengers demand, and thus the available capacity for transporting freight, is assumed to be stochastic. We model this problem as a two-stage stochastic problem and we provide a MIP formulation and a sample average approximation (SAA) method along with an Adaptive Large Neighborhood Search (ALNS) algorithm to solve it. We then analyze the proposed approach as well as the impacts of stochastic passengers demand on such integrated system on a computational study.Finally, we summarize the key findings, highlight the main challenges facing shared mobility systems, and suggest potential directions for future research.

Les projets d'Ingénierie Structurale doivent s’adapter aux critères de performance, de sécurité, de fonctionnalité, de durabilité et autres, établis dans la phase d’avant-projet. Traditionnellement, les projets utilisent des informations de nature déterministe comme les dimensions, les propriétés des matériaux et les charges externes. Toutefois, la modélisation des systèmes structuraux complexes implique le traitement des différents types et niveaux d'incertitudes. Dans ce sens, la prévision du comportement doit être préférablement faite en termes de probabilités puisque l'estimation de la probabilité de succès d'un certain critère est une nécessité primaire dans l’Ingénierie Structurale. Ainsi, la fiabilité est la probabilité rapportée à la parfaite opération d'un système structural donné durant un certain temps en des conditions normales d'opération pour trouver le meilleur compromis entre coût et sécurité pour l’élaboration des projets. Visant à pallier les désavantagés des méthodes traditionnelles FORM et SORM (First and Second Order Reliability Method), cette thèse propose une méthode d’analyse de fiabilité basée sur des techniques d’optimisation heuristiques (HBRM, Heuristic-based Reliability Method). Les méthodes heuristiques d’optimisation utilisées par cette méthode sont : Algorithmes Génétiques (Genetic Algorithms), Optimisation par Essaims Particulaires (Particle Swarm Optimisation) et Optimisation par Colonie de Fourmis (Ant Colony Optimization). La méthode HBRM ne requiert aucune estimation initiale de la solution et opère selon le principe de la recherche multi-directionnelle, sans besoin de calculer les dérivées partielles de la fonction d’état limite par rapport aux variables aléatoires. L’évaluation des fonctions d’état limite est réalisée en utilisant modèles analytiques, semi analytiques et numériques. Dans ce but, la mise en oeuvre de la méthode de Ritz (via MATLAB®), la méthode des éléments finis (via MATLAB® et ANSYS®) et la méthode sans maillage de Galerkin (Element-free Galerkin sous MATLAB®) a été nécessaire. La combinaison d’analyse de fiabilité, des méthodes d’optimisation et méthodes de modélisation, ci-dessus mentionnées, configure la méthodologie de conception fiabiliste proposée dans ce mémoire. L’utilisation de différentes méthodes de modélisation et d’optimisation a eu pour objectif de mettre en évidence leurs avantages et désavantages pour des applications spécifiques, ainsi pour démontrer l’applicabilité et la robustesse de la méthodologie de conception fiabiliste en utilisant ces techniques numériques. Ce qui a été possible grâce aux bons résultats trouvés dans la plupart des applications. Dans ce sens, des applications uni, bi et tridimensionnelles en statique, stabilité et dynamique des structures explorent l’évaluation explicite et implicite des fonctions d’état limite de plusieurs variables aléatoires. Procédures de validation déterministe et analyses stochastiques, et la méthode de perturbation de Muscolino, donnent les bases de l’analyse de fiabilité des applications en problèmes d’interaction fluide-structure bi et tridimensionnelles. La méthodologie est particulièrement appliquée à une structure industrielle. Résultats de applications uni et bidimensionnelles aux matériaux composites stratifiés, modélisés par la méthode EFG sont comparés avec les obtenus par éléments finis. A la fin de la thèse, une extension de la méthodologie à l’optimisation fiabiliste est proposée à travers la méthode des facteurs optimaux de sûreté. Pour cela, sont présentes des applications pour la minimisation du poids, en exigent un indice de fiabilité cible, aux systèmes modélisés par la méthode de EF et par la méthode EFG. / Structural Engineering designs must be adapted to satisfy performance criteria such as safety, functionality, durability and so on, generally established in pre-design phase. Traditionally, engineering designs use deterministic information about dimensions, material properties and external loads. However, the structural behaviour of the complex models needs to take into account different kinds and levels of uncertainties. In this sense, this analysis has to be made preferably in terms of probabilities since the estimate the probability of failure is crucial in Structural Engineering. Hence, reliability is the probability related to the perfect operation of a structural system throughout its functional lifetime; considering normal operation conditions. A major interest of reliability analysis is to find the best compromise between cost and safety. Aiming to eliminate main difficulties of traditional reliability methods such as First and Second Order Reliability Method (FORM and SORM, respectively) this work proposes the so-called Heuristic-based Reliability Method (HBRM). The heuristic optimization techniques used in this method are: Genetic Algorithms, Particle Swarm Optimization and Ant Colony Optimization. The HBRM does not require initial guess of design solution because it’s based on multidirectional research. Moreover, HBRM doesn’t need to compute the partial derivatives of the limit state function with respect to the random variables. The evaluation of these functions is carried out using analytical, semi analytical and numerical models. To this purpose were carried out the following approaches: Ritz method (using MATLAB®), finite element method (through MATLAB® and ANSYS®) and Element-free Galerkin method (via MATLAB®). The combination of these reliability analyses, optimization procedures and modelling methods configures the design based reliability methodology proposed in this work. The previously cited numerical tools were used to evaluate its advantages and disadvantages for specific applications and to demonstrate the applicability and robustness of this alternative approach. Good agreement was observed between the results of bi and three-dimensional applications in statics, stability and dynamics. These numerical examples explore explicit and implicit multi limit state functions for several random variables. Deterministic validation and stochastic analyses lied to Muscolino perturbation method give the bases for reliability analysis in 2-D and 3-D fluidstructure interaction problems. This methodology is applied to an industrial structure lied to a modal synthesis. The results of laminated composite plates modelled by the EFG method are compared with their counterparts obtained by finite elements. Finally, an extension in reliability based design optimization is proposed using the optimal safety factors method. Therefore, numerical applications that perform weight minimization while taking into account a target reliability index using mesh-based and meshless models are proposed. / Os projectos de Engenharia Estrutural devem se adaptar a critérios de desempenho, segurança, funcionalidade, durabilidade e outros, estabelecidos na fase de anteprojeto. Tradicionalmente, os projectos utilizam informações de natureza deterministica nas dimensões, propriedades dos materiais e carregamentos externos. No entanto, a modelagem de sistemas complexos implica o tratamento de diferentes tipos e níveis de incertezas. Neste sentido, a previsão do comportamento deve preferivelmente ser realizada em termos de probabilidades dado que a estimativa da probabilidade de sucesso de um critério é uma necessidade primária na Engenharia Estrutural. Assim, a confiabilidade é a probabilidade relacionada à perfeita operação de um sistema estrutural durante um determinado tempo em condições normais de operação. O principal objetivo desta análise é encontrar o melhor compromisso entre custo e segurança. Visando a paliar as principais desvantagens dos métodos tradicionais FORM e SORM (First and Second Order Reliability Method), esta tese propõe um método de análise de confiabilidade baseado em técnicas de optimização heurísticas denominado HBRM (Heuristic-based Reliability Method). Os métodos heurísticos de otimização utilizados por este método são: Algoritmos Genéticos (Genetic Algorithms), Optimização por Bandos Particulares (Particle Swarm Optimisation) e Optimização por Colónia de Formigas (Ant Colony Optimization). O método HBRM não requer de uma estimativa inicial da solução e opera de acordo com o princípio de busca multidirecional, sem efetuar o cálculo de derivadas parciais da função de estado limite em relação às variáveis aleatórias. A avaliação das funções de estado limite é realizada utilizando modelos analíticos, semi analíticos e numéricos. Com este fim, a implementação do método de Ritz (via MATLAB®), o método dos elementos terminados (via MATLAB® e ANSYS®) e o método sem malha de Galerkin (Element-free Galerkin via MATLAB®) foi necessária. A combinação da análise de confiabilidade, os métodos de optimização e métodos de modelagem, acima mencionados, configura a metodologia de projeto proposta nesta tese. A utilização de diferentes métodos de modelagem e de otimização teve por objetivo destacar as suas vantagens e desvantagens em aplicações específicas, assim como demonstrar a aplicabilidade e a robustez da metodologia de análise de confiabilidade utilizando estas técnicas numéricas. Isto foi possível graças aos bons resultados encontrados na maior parte das aplicações. As aplicações foram uni, bi e tridimensionais em estática, estabilidade e dinâmica de estruturas, as quais exploram a avaliação explícita e implícita de funções de estado limite de várias variáveis aleatórias. Procedimentos de validação déterministica e de análises estocásticas, aplicando o método de perturbação de Muscolino, fornecem as bases da análise de confiabilidade nas aplicações de problemas de iteração fluído-estrutura bi e tridimensionais. A metodologia é testada com uma estrutura industrial. Resultados de aplicações bidimensionais em estratificados compostos, modelados pelo método EFG são comparados com os obtidos por elementos finitos. No fim da tese, uma extensão da metodologia à optimização baseada em confiabilidade é proposta aplicando o método dos factores óptimos de segurança. Finalmente são apresentadas as aplicações para a minimização do peso em sistemas modelados pelo método de EF e o método EFG que exigem um índice de confiabilidade alvo.

Cette thèse s’intéresse aux algorithmes adaptés aux architectures mémoire hiérarchiques, rencontrées notamment dans le contexte des processeurs multi-cœurs.Nous étudions d’abord le produit de matrices sur les processeurs multi-cœurs. Nous modélisons le processeur, bornons le volume de communication, présentons trois algorithmes réduisant ce volume de communication et validons leurs performances. Nous étudions ensuite la factorisation QR, dans le contexte des matrices ayant plus de lignes que de colonnes. Nous revisitons les algorithmes existants afin d’exploiter les processeurs multi-cœurs, analysons leurs chemins critiques, montrons que certains sont asymptotiquement optimaux, et analysons leurs performances.Nous étudions ensuite les applications pipelinées sur une plate-forme hétérogène, le QS 22. Nous modélisons celle-ci et appliquons les techniques d’ordonnancement en régime permanent. Nous introduisons un programme linéaire mixte permettant d’obtenir une solution optimale. Nous introduisons en outre un ensemble d’heuristiques.Puis, nous minimisons la mémoire nécessaire à une application modélisée par un arbre, sur une plate-forme à deux niveaux de mémoire. Nous présentons un algorithme optimal et montrons qu’il existe des arbres tels que les parcours postfixes sont arbitrairement mauvais. Nous étudions alors la minimisation du volume d’E/S à mémoire donnée, montrons que ce problème est NP-complet, et présentons des heuristiques. Enfin, nous comparons plusieurs politiques d’archivage pour BLUE WATERS. Nous introduisons deux politiques d’archivage améliorant les performances de la politique RAIT, modélisons la plate-forme de stockage et simulons son fonctionnement. / This thesis focus on memory-aware algorithms tailored for hierarchical memory architectures, found for instance within multicore processors. We first study the matrix product on multicore architectures. We model such a processor, and derive lower bounds on the communication volume. We introduce three ad hoc algorithms, and experimentally assess their performance.We then target a more complex operation: the QR factorization of tall matrices. We revisit existing algorithms to better exploit the parallelism of multicore processors. We thus study the critical paths of many algorithms, prove some of them to be asymptotically optimal, and assess their performance.In the next study, we focus on scheduling streaming applications onto a heterogeneous multicore platform, the QS 22. We introduce a model of the platform and use steady-state scheduling techniques so as to maximize the throughput. We present a mixed integer programming approach that computes an optimal solution, and propose simpler heuristics. We then focus on minimizing the amount of required memory for tree-shaped workflows, and target a classical two-level memory system. I/O represent transfers from a memory to the other. We propose a new exact algorithm, and show that there exist trees where postorder traversals are arbitrarily bad. We then study the problem of minimizing the I/O volume for a given memory, show that it is NP-hard, and provide a set of heuristics.Finally, we compare archival policies for BLUE WATERS. We introduce two archival policies and adapt the well known RAIT strategy. We provide a model of the tape storage platform, and use it to assess the performance of the three policies through simulation.

L'objectif de cette recherche est de développer des modèles aussi bien conceptuels, analytiques et managériaux en analysant un maillon de la supply chain, à savoir la relation entre un distributeur et deux fournisseurs opérant dans un environnement incertain. Dans la première partie de la thèse, nous considérons un seul produit, plutôt haut de gamme et/ou périssable, et nous faisons l’analyse sur un horizon d’une période. Dans ce cas précis, les caractéristiques unitaires du produit sont toutes non linéaires, à savoir : le prix, le coût de production, le coût de rupture, le coût de reprise. La demande est supposée être une variable aléatoire. Dans la deuxième partie de la thèse, nous nous inspirons des pratiques de firmes internationales qui s’approvisionnent, pour une partie de leur offre, dans des pays à bas coûts. Nous développons plusieurs modèles mais dont la structure de base est similaire, à savoir : deux produits (un haut gamme acheté localement et l’autre bas de gamme acheté dans les pays à bas coûts), un horizon de trois périodes, deux fournisseurs à capacité de production limitée et un distributeur ayant des capacités de stockage limitées. Une panoplie de résultats théoriques, numériques ainsi que des insights sont présentés.Les modèles développés peuvent être utilisés comme des outils d’aide { la prise de décision dans les environnements décrits dans cette thèse / The objective of this research is to develop conceptual, analytical, and managerial models and insights by analyzing a portion of the supply chain made up of a retailer dealing with two suppliers in an uncertain environment. In the first part of this thesis, we consider a single high-end (or perishable) product, single period, variable unit price, variable unit production cost, variable unit shortage cost, variable unit salvagevalue, stochastic demand problem. In a second part of the thesis, we consider settings inspired by the case of large international companies sourcing some of their products from low cost countries. This structure is as follows: two products (one sourced locally and the other sourced abroad), a three-period, two-stages, two capacitated suppliers, and a single capacitated retailer. Both analytical and numerical results are provided. Important theoretical results and insights are developed for these types of settings. These models can be used as decision-making aid tools in such environments