Return to search

Multi-attribute deterministic and stochastic two echelon location routing problems

Les problèmes de localisation-routage à deux échelons (2E-LRP) sont devenus un domaine de recherche important dans le domaine de la logistique et de la gestion de la chaîne d'approvisionnement. Le 2E-LRP représente un problème d'optimisation dans les systèmes de distribution non dirigés, visant à organiser le transport de marchandises entre les plateformes et les clients par le biais d'installations intermédiaires appelées satellites. Ce problème implique de prendre des décisions simultanées concernant l'emplacement d'un ou deux niveaux d'installations (plateformes et/ou satellites) et de créer un ensemble limité d'itinéraires aux deux échelons afin de répondre efficacement à toutes les demandes des clients. Récemment, la communauté scientifique s'est intéressée de plus en plus à l'étude et à la résolution de problèmes plus réalistes. Cet intérêt provient de la reconnaissance du fait que les systèmes de distribution du monde réel sont caractérisés par une multitude de complexités et d'incertitudes qui ont un impact significatif sur l'efficacité opérationnelle, la rentabilité et la satisfaction des clients. Les chercheurs ont reconnu la nécessité d'aborder ces complexités et incertitudes pour développer des solutions pratiques et efficaces.

Cette thèse comprend trois études différentes, chacune correspondant à un article de recherche autonome. Dans les trois articles, nous nous concentrons sur différents 2E-LRP riches qui comprennent plusieurs attributs en interaction. Ces variantes du problème sont appelées problèmes de localisation-routage à deux échelons et à attributs multiples (2E-MALRP). Pour analyser l'influence des incertitudes sur les solutions optimales et les processus de prise de décision, nous considérons à la fois les perspectives déterministes et stochastiques. Cette approche nous permet de mieux comprendre le comportement de ces problèmes complexes.

Le premier document de recherche abordé dans cette thèse se concentre sur un problème de localisation-routage déterministe à deux échelons et à attributs multiples avec synchronisation de la flotte dans les installations intermédiaires (2E-MALRPS). Le cadre du problème comprend divers facteurs, notamment la demande de marchandises multiples dépendant du temps, les fenêtres temporelles, le manque de capacité de stockage dans les installations intermédiaires et la nécessité de synchroniser les flottes opérant à différents échelons. Dans le 2E-MALRPS, tous les paramètres, tels que les demandes des clients, les temps de trajet et les coûts, sont connus avec certitude.
Dans cet article, nous introduisons le cadre du problème, présentons une formulation de programmation en nombres entiers mixtes et proposons un cadre de découverte de discrétisation dynamique comme méthode de résolution du problème.

Le deuxième article de cette thèse traite du problème de localisation-routage à deux échelons en cas de demandes stochastiques et corrélées (2E-MLRPSCD). Contrairement au 2E-MALRPS, le 2E-MLRPSCD prend en compte les incertitudes liées aux demandes des clients, ainsi que la corrélation entre ces demandes. Nous formulons le problème sous la forme d'un modèle de programmation stochastique en deux étapes. Au cours de la première étape, des décisions sont prises concernant la conception des installations satellites, tandis qu'au cours de la deuxième étape, des décisions de recours déterminent la manière dont les demandes observées sont servies.
Nous proposons une métaheuristique de couverture progressive comme méthode de résolution. Dans cette approche, nous incorporons deux structures de population dans le cadre de la couverture progressive. Ces structures renforcent la diversité des décisions de conception obtenues pour chaque sous-problème de scénario et fournissent des informations pertinentes pour améliorer la qualité de la solution. En outre, nous introduisons et comparons trois nouvelles stratégies différentes pour accélérer la recherche de l'espace de solution pour le problème stochastique.

Finalement, le troisième article présenté dans cette thèse se concentre sur un problème de localisation-routage multi-attributs à deux échelons avec des temps de trajet stochastiques (2E-MALRPSTT). Le 2E-MALRPSTT combine un problème multi-attributs riche avec des éléments stochastiques, en particulier en considérant des temps de trajet stochastiques. Pour traiter le problème stochastique complet, un cadre de couverture progressive (PH) est proposé en s'appuyant sur les lignes directrices méthodologiques définies dans notre deuxième article pour le 2E-MLRPSCD. En outre, une heuristique basée sur la décomposition est introduite pour accélérer le cadre PH, et deux nouvelles stratégies d'agrégation sont présentées pour accélérer le processus de consensus concernant les décisions de la première étape.

Les contributions présentées dans cette thèse couvrent divers aspects de la modélisation et des méthodologies de solution pour les 2E-MALRP riches, à la fois d'un point de vue déterministe et d'un point de vue stochastique. Les trois articles inclus dans cette thèse démontrent l'efficacité des approches proposées à travers des campagnes expérimentales étendues, mettant en évidence leur efficacité de calcul et la qualité des solutions, en particulier dans les cas difficiles. En abordant les aspects déterministes et stochastiques de ces 2E-MALRP, cette thèse vise à contribuer à l'ensemble des connaissances en optimisation de la logistique et de la chaîne d'approvisionnement, à répondre aux besoins importants de la littérature actuelle et à fournir des informations importantes pour les systèmes de distribution à deux échelons dans divers contextes. / The Two-Echelon Location-Routing Problems (2E-LRPs) have emerged as a prominent research area within the field of logistics and supply chain management. The 2E-LRP represents an optimization problem in undirected distribution systems, aiming to streamline freight transportation between platforms and customers through intermediate facilities known as satellites. This problem involves making simultaneous decisions concerning the location of one or two levels of facilities (platforms and/or satellites) and creating a limited set of routes at both echelons to effectively serve all customer demands. In recent years, there has been a growing interest among the scientific community in studying and solving more realistic problem settings. This interest arises from the recognition that real-world distribution systems are characterized by a multitude of complexities and uncertainties that significantly impact operational efficiency, cost-effectiveness, and customer satisfaction. Researchers have acknowledged the need to address these complexities and uncertainties to develop practical and effective solutions.

This dissertation comprises three distinct studies, each serving as a self-contained research article. In all three articles, we focus on different rich 2E-LRPs that encompass multiple interacting attributes. These problem variants are referred to as two-echelon multi-attribute location-routing problems (2E-MALRPs). To analyze the influence of uncertainties on optimal solutions and decision-making processes, we consider both deterministic and stochastic perspectives. This approach allows us to gain insights into the behavior of these complex problem settings.

The first research paper addressed in this thesis focuses on a deterministic two-echelon multi-attribute location-routing problem with fleet synchronization at intermediate facilities (2E-MALRPS). The problem setting encompasses various factors, including time-dependent multicommodity demand, time windows, lack of storage capacity at intermediate facilities, and the need for synchronization of fleets operating at different echelons. In the 2E-MALRPS, all parameters, such as customer demands, travel times, and costs, are known with certainty.
In this paper, we introduce the problem setting, present a mixed-integer programming formulation, and propose a dynamic discretization discovery framework as the solution method to address the problem.


The second paper in this thesis addresses the two-echelon multicommodity location-routing problem with stochastic and correlated demands (2E-MLRPSCD). In contrast to the 2E-MALRPS, the 2E-MLRPSCD takes into account uncertainties related to customer demands, as well as the correlation among these demands. We formulate the problem as a two-stage stochastic programming model. In the first stage, decisions are made regarding the design of satellite facilities, while in the second stage, recourse decisions determine how the observed demands are allocated and served.
We propose a progressive hedging metaheuristic as the solution method. In this approach, we incorporate two population structures within the progressive hedging framework. These structures enhance the diversity of the design decisions obtained for each scenario subproblem and provide valuable insights for improving the solution quality. Additionally, We also introduce and compare three different novel strategies to accelerate the search for the solution space for the stochastic problem.

Finally, the third paper presented in this thesis focuses on a multi-attribute two-echelon location-routing problem with stochastic travel times (2E-MALRPSTT). The 2E-MALRPSTT combines a rich multi-attribute problem setting with stochastic elements, specifically considering stochastic travel times. To address the complete stochastic problem, a progressive hedging metaheuristic is proposed building on the methodological guidelines defined in our second paper for the 2E-MLRPSCD. Furthermore, a decomposition-based heuristic is introduced to accelerate the PH framework, and two novel selection strategies are presented to expedite the consensus process regarding the first-stage decisions.

The contributions presented in this thesis encompass various aspects of modeling and solution methodologies for rich 2E-MALRPs from both deterministic and stochastic perspectives. The three articles included in this thesis demonstrate the effectiveness of the proposed approaches through extensive experimental campaigns, highlighting their computational efficiency and solution quality, particularly in challenging instances. By addressing the deterministic and stochastic aspects of these 2E-MALRPs, this thesis aims to contribute to the broader body of knowledge in logistics and supply chain optimization, fill important gaps in the present literature and provide valuable insights for two-echelon distribution systems in diverse settings.

Identiferoai:union.ndltd.org:umontreal.ca/oai:papyrus.bib.umontreal.ca:1866/32309
Date10 1900
CreatorsEscobar Vargas, David
ContributorsCrainic, Teodor Gabriel, Rei, Walter
Source SetsUniversité de Montréal
LanguageEnglish
Detected LanguageFrench
Typethesis, thèse
Formatapplication/pdf

Page generated in 0.0021 seconds