No description available.

Random disruptions resulting in loss of functionality in service legs or intermodal terminals of transportation networks are an inevitable part of operations, and considering the crucial role of aforementioned networks, it is prudent to strive towards avoiding high-consequence disruption events. The magnitude of the negative impact of a disruption is dependent on component criticality; therefore, limited resources of disruption mitigation should be assigned to the infrastructure with the highest priority. However, categorizing the service legs and terminals based on their actual post-disruption impact is computationally heavy and inefficient. We propose a methodology based on the combination of a bi-objective hazmat shipment planning optimization model and machine learning to identify critical infrastructure more efficiently. The proposed methodology is applied to part of CSX Corporation’s intermodal rail-truck network in the United States as a realistic size problem instance, in order to gain managerial insight and to evaluate the performance of the methodology. / Thesis / Master of Science (MSc)

Matching people to their preferences is an algorithmic topic with real world applications. One such application is the kidney exchange. The best "cure" for patients whose kidneys are failing is to replace it with a healthy one. Unfortunately, biological factors (e.g., blood type) constrain the number of possible replacements. Kidney exchanges seek to alleviate some of this pressure by allowing donors to give their kidney to a patient besides the one they most care about and in turn the donor for that patient gives her kidney to the patient that this first donor most cares about. Roth et al.~first discussed the classic kidney exchange problem. Freedman et al.~expanded upon this work by optimizing an additional objective in addition to maximal matching. In this work, I implement the traditional kidney exchange algorithm as well as expand upon more recent work by considering multi-objective optimization of the exchange. In addition I compare the use of 2-cycles to 3-cycles. I offer two hypotheses regarding the results of my implementation. I end with a summary and a discussion about potential future work.

Le travail que nous présentons dans cette thèse porte sur le problème d'affectation dans une place de marché de prospects Internet. Plus précisément, ce travail a pour ambition de répondre à la problématique de l'adéquation de l'offre et de la demande, dans un contexte caractérisé par des flux continus faisant évoluer en temps réel l'ensemble des offres disponibles et les demandes à satisfaire. Pour ce faire, nous proposons dans un premier temps un modèle mono-période qui optimise le problème d'affectation à un instant donné et en considérant une seule période de temps, tout en permettant la prise en compte instantanée des nouvelles offres et demandes et leur adéquation en temps réel. Ce modèle permet d'optimiser deux objectifs à savoir: la maximisation du chiffre d'affaires et la satisfaction des clients.Par la suite nous proposons d'étendre ce modèle sur plusieurs périodes de temps futures afin de prendre en compte l'aspect temps réel de l'activité de la place de marché et donc le fait que des flux continus font évoluer en temps réel l'ensemble des offres et des demandes. L'objectif étant de tirer profit de la connaissance concernant cette évolution, par le biais de l'intégration d'un modèle de prévision dans un modèle d'optimisation multi-période.Ainsi, nous proposons un modèle d'optimisation multi-période permettant d'envisager à un instant donné des affectations sur plusieurs périodes de temps futures afin de réaliser les meilleures affectations possibles. Aussi, nous proposons un modèle de prévision des nouveaux flux tout en considérant les caractéristiques du modèle d'optimisation multi-période.Construire un modèle de prévision nécessite de définir les données à prévoir avant d'envisager toute méthode de prévision. En d'autres termes, nous devons choisir les paramètres du modèle de prévision, à savoir: les données historiques appropriées, le pas de temps de la prévision ainsi que l'horizon de la prévision. Le défi consiste donc à définir les paramètres du modèle de prévision qui conviendront au fonctionnement du modèle de l'optimisation multi-période.Par ailleurs, une des caractéristiques de la place de marché est la temporalité de son système. Ainsi, nous proposons un algorithme assurant l'aspect temps réel et donc le fait que les affectations s'effectuent toutes les minutes. L'algorithme que nous proposons fonctionne de manière continue à longueur de journée en optimisant à chaque instant l'adéquation offre/demande de prospects Internet tout en considérant instantanément les flux continus de prospects Internet ainsi que la mise à jour régulière de la demande Enfin, pour mettre en évidence l'efficacité et les bénéfices que la place de marché peut en tirer par l'utilisation des modèles et de l'algorithme proposés, nous avons mené des tests et différentes expérimentations sur des données réelles. Ces tests nous ont permis de valider nos travaux et d'évaluer la qualité des résultats obtenus.L'objectif de ce travail est double, d'une part, donner un cadre solide et formel pour répondre à la problématique de la place de marché de prospects Internet. D'autre part, le cadre proposé devrait être aussi générique que possible afin de résoudre tout autre problème analogue à celui de la place de marché de prospects Internet. / The work that we present in this thesis focuses on the assignment problem in a marketplace of Internet prospects. More precisely, this work aims to address the problem of matching offers and demands in a context characterized by a continuous flows. These latter evolve inreal time the set of available offers and demands to satisfy. To do this, we propose initially a mono-period model which optimizes the assignment problem at a given instant and taking into account asingle period of time while allowing the instantaneous consideration of new offers and demands and their adequacy in real time. This model considers two objectives to optimize, namely: maximization of turnover as well as clients satisfaction.Thereafter, we propose to extend this model over several future time periods in order to take into account the real time aspect of the marketplace activity and so the fact that a continuous flows evolve in real time the set of offers en demands. The objective is to take advantage of knowledge about this evolution, through the integration of a forecasting model in a multi-period optimization model. Thus,we propose a multi-period optimization model for considering at agiven instant assignments over several future time periods. Also, we propose a forecasting model for new flows while considering the characteristics of the multi-period optimization model.Building a forecasting model requires defining the data before considering any forecasting method. In other words, we have to choose the parameters of the forecasting model, namely the appropriate historical data, the forecasting time step and the forecasting horizon. The challenge is to define the parameters of the forecasting model which agree with the functioning the multi-period optimization model.Furthermore, a feature of the marketplace is the temporality of its system. Thus, we propose an algorithm ensuring real-time aspect and so the fact that assignments are made every minute. The proposed algorithm works continuously all day long while optimizing every instant the offer/demand adequacy of Internet prospects and instantly considering the continuous flux of Internet prospects as well as the regular updating demand. Finally, in order to show the efficiency and the benefits that the marketplace can reap by the use of the proposed models, we conducted tests and various experiments on real data. These tests have allowed us to validate the proposed models and evaluate the quality of the results.The aim is twofold, giving a strong and formal framework to address the issue of the marketplace of Internet prospects but also proposing a generic framework to solve any problem similar to that of the marketplace of Internet prospects.

Les activités de transport jouent un rôle crucial autant dans le domaine de la production que dans celui des services. En particulier, elles permettent d’assurer la distribution de biens et de services entre fournisseurs, unités de production, entrepôts, distributeurs, et clients finaux. Plus spécifiquement, les problèmes de tournées de véhicules (VRP) considèrent la mise au point d’un ensemble de tournées de coût minimal servant la demande en biens ou en services d’un ensemble de clients distribués géographiquement, tout en vérifiant un ensemble de contraintes opérationnelles. Alors qu’il s’agissait d’un problème statique, des avancées technologiques récentes permettent aux organisations de gérer leur flotte de véhicules en temps réel. Cependant, ces nouvelles technologies introduisent également une plus grande complexité dans les tâches de gestion de flotte, révélant une demande pour des outils d’aide à la décision dédiés aux problèmes de tournées de véhicules dynamiques. Dans ce contexte, les contributions de la présente thèse de doctorat s’organisent autour de trois axes : (i) elle présente un état de l’art détaillé des problèmes de tournées dynamiques; (ii) elle introduit des frameworks d’optimisation génériques adaptés à une grande variété de problèmes ; (iii) elle définit un problème de tournées novateur et aux nombreuses applications. / Within the wide scope of logistics management,transportation plays a central role and is a crucialactivity in both production and service industry.Among others, it allows for the timely distributionof goods and services between suppliers, productionunits, warehouses, retailers, and final customers.More specifically, Vehicle Routing Problems(VRPs) deal with the design of a set of minimal costroutes that serve the demand for goods orservices of a set of geographically spread customers,satisfying a group of operational constraints.While it was traditionally a static problem, recenttechnological advances provide organizations withthe right tools to manage their vehicle fleet in realtime. Nonetheless, these new technologies alsointroduce more complexity in fleet managementtasks, unveiling the need for decision support systemsdedicated to dynamic vehicle routing. In thiscontext, the contributions of this Ph.D. thesis arethreefold : (i) it presents a comprehensive reviewof the literature on dynamic vehicle routing ; (ii)it introduces flexible optimization frameworks thatcan cope with a wide variety of dynamic vehiclerouting problems ; (iii) it defines a new vehicle routingproblem with numerous applications.

Within the wide scope of logistics management,transportation plays a central role and is a crucialactivity in both production and service industry.Among others, it allows for the timely distributionof goods and services between suppliers, productionunits, warehouses, retailers, and final customers.More specifically, Vehicle Routing Problems(VRPs) deal with the design of a set of minimal costroutes that serve the demand for goods orservices of a set of geographically spread customers,satisfying a group of operational constraints.While it was traditionally a static problem, recenttechnological advances provide organizations withthe right tools to manage their vehicle fleet in realtime. Nonetheless, these new technologies alsointroduce more complexity in fleet managementtasks, unveiling the need for decision support systemsdedicated to dynamic vehicle routing. In thiscontext, the contributions of this Ph.D. thesis arethreefold : (i) it presents a comprehensive reviewof the literature on dynamic vehicle routing ; (ii)it introduces flexible optimization frameworks thatcan cope with a wide variety of dynamic vehiclerouting problems ; (iii) it defines a new vehicle routingproblem with numerous applications.

Cette thèse porte sur le développement de modèles mathématiques et d’algorithmes d’optimisation pour la conception de chaînes logistiques durables. Nous proposons des modèles mono-périodiques, multi-produits et multi-modes de transport à quatre niveaux (fournisseurs, unités de production, entrepôts et clients) couvrant les piliers économique et environnemental du développement durable. Les variables de décision concernent la localisation des sites logistiques intermédiaires (unités de production et entrepôts), les choix de technologie et de mode de transport, et la détermination des flux de produits. Un premier modèle est basé uniquement sur la minimisation des coûts totaux. Ce modèle est étendu au cas bi-objectif en considérant la minimisation des émissions de CO2. Nous proposons une procédure d’optimisation basée sur la recherche à voisinage large (LNS : Large Neighborhood Search). L’application de cette méthode à un problème à variables mixtes tel que la conception de chaîne logistique est inédite. Notre extension au cas bi-objectif fait intervenir l’algorithme récent de recherche locale multi-directionnelle. Les expérimentations numériques permettent d’évaluer la pertinence de nos modèles et de comparer les performances de nos algorithmes à celles d’un solveur du marché. / This thesis focuses on the development of mathematical models and optimization algorithms for the design of sustainable supply chains. We propose single-period, multi-commodity, multi-mode, four level models (suppliers, production facilities, warehouses and customers) covering economic and environmental pillars of sustainable development. The decision variables are related to the location of the intermediate logistics sites (production units and warehouses), the choice of technology and mode of transport, and the determination of product flow. A first model is based solely on minimizing total costs. This model is extended to bi-objective minimization by considering CO2 emissions. We propose an optimization procedure based on the Large Neighborhood Search (LNS) metaheuristic, which had almost never been applied to problems with mixed variables such as design supply chain. Our extension to the bi-objective case involves the use of the multi-directional local search (MDLS). Extensive numerical experiments assess the relevance of our model and compare the performance of our algorithms to those of a state-of-the-art solver.

Les ateliers de traitement de surface automatisés, qui utilisent des robots de manutention commandés par ordinateur pour le transport de la pièce, ont été largement mis en place dans différents types d'entreprises industrielles, en raison de ses nombreux avantages par rapport à un mode de production manuel, tels que : une plus grande productivité, une meilleure qualité des produits, et l’impact sur les rythmes de travail. Notre recherche porte sur trois types de problèmes d'ordonnancement associés à ces systèmes, appelés Hoist Scheduling Problems, caractérisés par des contraintes de fenêtres de temps de traitement: (I) un problème à une seule ressource de transport où l’objectif est de minimiser le temps de cycle; (II) un problème bi-objectif avec une seule ressource de transport où il faut minimiser le temps de cycle et la consommation de ressources de traitement (et par conséquent le coût de production); et (III) un problème d'ordonnancement cyclique mono-objectif mais multi-robots.En raison de la NP-complétude des problèmes étudiés et de nombreux avantages de les outils de type quantum-inspired evolutionary algorithm (QEA), nous proposons d'abord un QEA hybride comprenant un mécanisme de décodage amélioré et une procédure réparation dédiée pour trouver le meilleur temps de cycle pour le premier problème. Après cela, afin d'améliorer à la fois la performance économique et environnementale qui constituent deux des trois piliers de la stratégie de développement durable de nos jours déployée dans de nombreuses industries, nous formulons un modèle mathématique bi-objectif pour le deuxième problème en utilisant la méthode de l'intervalle interdit. Ensuite, nous proposons un QEA bi-objectif couplé avec une procédure de recherche locale pour minimiser simultanément le temps de cycle et les coûts de production, en générant un ensemble de solutions Pareto-optimales pour ce problème. Quant au troisième problème, nous constatons que la plupart des approches utilisées dans les recherches actuelles, telles que la programmation entière mixte (MIP), peuvent conduire à l’obtention d’une solution non optimale en raison de la prise en compte courante d’une hypothèse limitant l’exploration de l’espace de recherche et relative aux mouvements en charge des robots. Par conséquent, nous proposons une approche de MIP améliorée qui peut garantir l'optimalité des solutions obtenues pour ce problème, en relaxant l'hypothèse mentionnée ci-dessus.Pour chaque problème, une étude expérimentale a été menée sur des cas industriels ainsi que sur des instances générées aléatoirement. Les résultats obtenus montrent que l’efficacité des algorithmes d'ordonnancement proposés, ce qui justifie les choix que nous avons faits. / Automated treatment surface facilities, which employ computer-controlled hoists for part transportation, have been extensively established in various kinds of industrial companies, because of its numerous advantages over manual system, such as higher productivity, better product quality, and reduced labor intensity. Our research investigates three typical hoist scheduling problems with processing time windows in treatment surface facilities, which are: (I) cyclic single-hoist scheduling problem to minimize the cycle time; (II) cyclic single-hoist scheduling problem to minimize the cycle time and processing resource consumption (and consequently production cost); and (III) cyclic multi-hoist scheduling problem to minimize the cycle time.Due to the NP-completeness of the studied problems and numerous advantages of quantum-inspired evolutionary algorithm (QEA), we first propose a hybrid QEA with improved decoding mechanism and repairing procedure to find the best cycle time for the first problem. After that, to enhance with both the economic and environmental performance, which constitute two of the three pillars of the sustainable strategy nowadays deployed in many industries, we formulate a bi-objective mathematical model for the second problem by using the method of prohibited interval. Then we propose a bi-objective QEA with local search procedure to simultaneously minimize the cycle time and production cost, and we find a set of Pareto-optimal solutions for this problem. As for the third problem, we find that most existing approaches, such as mixed integer programming (MIP) approach, may identify a non-optimal solution to be an optimal one due to an assumption related to the loaded hoist moves which is made in many existing researches. Consequently, we propose an improved MIP approach for this problem by relaxing the above-mentioned assumption. Our approach can guarantee the optimality of its obtained solutions.For each problem, experimental study on industrial instances and random instances has been conducted. Computational results demonstrate that the proposed scheduling algorithms are effective and justify the choices we made.