Robust Optimization for Supply Chain Applications: Facility Location and Drone Delivery Problems

Les décisions concernant la localisation des infrastructures dans les chaînes d'approvisionnement sont d'une importance stratégique: la construction d'une nouvelle infrastructure est généralement coûteuse et l'impact de cette décision est durable. Une fois qu'une nouvelle installation sera ouverte, elle devrait rester opérationnelle pendant plusieurs années. Cependant, des facteurs environnementaux, tels que les déplacements de population et les catastrophes naturelles, peuvent affecter le fonctionnement des installations. Par exemple, le déplacement de la population peut modifier les modèles de demande, ce qui influence davantage les décisions d'allocation entre les clients et les installations. Les catastrophes naturelles peuvent diminuer partiellement ou complètement la capacité d'une installation, entraînant des décisions de réaffectation ou des pertes de ventes. Toutes ces incertitudes peuvent faire en sorte qu'une décision optimale d'aujourd'hui ne donne pas de bons résultats à l'avenir. Ainsi, il est important de considérer les incertitudes potentielles dans la phase de conception des chaînes d'approvisionnements, tout en prenant explicitement en compte les réaffectations possibles des clients comme décisions de recours dans la phase d'exécution. Dans la première moitié de cette thèse, nous étudions trois problèmes de localisation d'établissements sous risques de perturbations, où chaque travail a un objectif différent. Plus précisément, l'étude du chapitre 3 se concentre principalement sur l'amélioration des algorithmes; le travail du chapitre 4 considère simultanément plusieurs types d'incertitudes; et le chapitre 5 étudie un problème de conception de réseau à trois échelons soumis à des perturbations. Nous adoptons des méthodes d'optimisation robuste (OR) en deux étapes, où les décisions de localisation des installations sont prises ici et maintenant et les décisions de recours pour réaffecter les clients sont prises après que les informations d'incertitude sur la disponibilité des installations et la demande des clients ont été révélées. Nous implémentons des méthodes exactes et approximatives pour résoudre les modèles robustes. Les résultats démontrent que le cadre OR proposé peut améliorer la fiabilité des systèmes de chaîne d'approvisionnement avec seulement une légère augmentation du coût normal (le coût du scénario sans interruption). Les différents modèles construits dans cette thèse peuvent également être utilisés comme outils d'aide à la décision pour voir le compromis entre coût et fiabilité. Outre la planification stratégique, nous avons étudié également les problèmes de niveau opérationnel : problèmes de livraison à l'aide de drones. La livraison par drone est connue comme contributeur potentiel à l'amélioration de l'efficacité et à la résolution des problèmes de livraison du dernier kilomètre. Pour cette raison, le routage des drones est devenu un domaine de recherche très actif ces dernières années. Contrairement au problème de routage des véhicules, cependant, la conception des itinéraires des drones est difficile en raison de multiples caractéristiques opérationnelles, notamment les opérations multi-voyages, la planification de la recharge et le calcul de la consommation d'énergie. Pour combler certaines lacunes importantes dans la littérature, le chapitre 6 résout un problème de routage de drone multi-voyages, où la consommation d'énergie des drones est affectée par la charge utile et la distance de déplacement alors que de telles relations sont non linéaires. Pour aborder la fonction d'énergie non linéaire (convexe), nous proposons deux types de coupes (cuts) qui sont incorporées dans le schéma de branchement et de coupes (branch-and-cut). Nous utilisons une formulation à 2 indices pour modéliser le problème et également générer des instances de référence pour l'évaluation d'algorithmes. Les tests numériques indiquent que même si le modèle d'origine est non linéaire, notre approche est efficace à la fois en termes d'algorithme et de qualité de solution. La livraison par drones peut également être affectée par diverses incertitudes, telles que des conditions de vent incertaines et des obstacles imprévisibles. Motivé par les problèmes de retard des drones résultant de l'incertitude du vent, notre travail dans le chapitre 7 vise à optimiser de manière robuste le risque de retard pour un problème de programmation de drones avec des temps de voyage incertains. À cette fin, nous utilisons un cadre d'optimisation robuste aux distributions pour modéliser le problème. Comme les données historiques sur le vent sont souvent disponibles, nous utilisons des techniques d'apprentissage automatique pour partitionner les données pour la construction de l'ensemble d'ambiguïté. À partir des données météorologiques réelles, nous observons que les conditions de vent l'après-midi dépendent des conditions de vent du matin. Par conséquent, nous proposons une description de l'ambiguïté en ensemble à deux périodes pour modéliser la distribution conjointe des temps de parcours incertains. Nous proposons également un modèle de planification des drones à deux périodes, où les décisions de programmation dans l'après-midi s'adapteraient aux résultats des informations météorologiques observées le matin. En utilisant des données météorologiques réelles, nous validons que le modèle d'optimisation robuste adaptatif peut réduire efficacement le retard dans les tests hors échantillon par rapport à d'autres méthodes de référence.

Abstract

Facility location decision is strategic: The construction of a new facility is typically costly and the impact of the decision is long-lasting. Once a new facility is opened, it is expected to remain in operation for several years. However, environmental factors, such as population shift and natural disasters, may affect facilities' operations. For example, population shift may change demand patterns, which further influence the allocation decisions between customers and facilities. Natural disasters may diminish a facility's capacity partially or completely, resulting in reassignment decisions or lost sales. All these uncertainties may cause today's optimal decision to perform poorly in the future. Thus, it is important to consider potential uncertainties in the supply chain design phase, while explicitly taking into account the possible customer reassignments as recourse decisions in the execution phase. In the first half of this thesis, we study three facility location problems under disruption risks, where each work has a different focus. Specifically, the study in Chapter 3 mainly focuses on algorithmic improvement; the work in Chapter 4 considers multiple types of uncertainties simultaneously; and Chapter 5 studies a three-echelon network design problem under disruptions. We adopt the two-stage robust optimization (RO) method for these problems, where facility location decisions are made here-and-now and recourse decisions to reassign customers are made after the uncertainty information on the facility availability and customer demand has been revealed. We implement both exact and approximate methods to solve the robust models. Results demonstrate that the proposed RO framework can improve supply chain systems' reliability with only a slight increase in the nominal cost (the cost of the disruption-free scenario). The various robust models constructed in this thesis can also be used as decision support tools to see the trade-off between cost and reliability. Besides strategic planning, we also study operational level problems in this thesis—drone delivery problems. Drone delivery is known as a potential contributor in improving efficiency and alleviating last-mile delivery problems. For this reason, drone routing and scheduling has become a highly active area of research in recent years. Unlike the vehicle routing problem, however, designing drones' routes is challenging due to multiple operational characteristics including multi-trip operations, recharge planning, and energy consumption calculation. To fill some important gaps in the literature, Chapter 6 solves a multi-trip drone routing problem, where drones' energy consumption is affected by payload and travel distance whereas such relationships are nonlinear. To tackle the nonlinear (convex) energy function, we propose two types of cuts that are incorporated into the branch-and-cut scheme. We use a 2-index formulation to model the problem and also generate benchmark instances for algorithm evaluation. Numerical tests indicate that even though the original model is nonlinear, our approach is effective in both computational efficiency and solution quality. Drone delivery can also be affected by various uncertainties, such as uncertain wind conditions and unpredictable obstacles. Motivated by the drone lateness issues resulting from wind uncertainty, our work in Chapter 7 aims to robustly optimize the lateness risk for a drone scheduling problem with uncertain travel times. To that end, we use a distributionally robust optimization framework to model the problem. As historical wind data is often available, we use machine learning techniques to partition the data for the construction of the ambiguity set. From the actual weather data, we observe that the wind conditions in the afternoon are dependent on the wind conditions in the morning. Accordingly, we propose a two-period cluster-wise ambiguity set to model the joint distribution of uncertain travel times. We also propose a two-period drone scheduling model, where the scheduling decisions in the afternoon would adapt to the outcome of the weather information observed in the morning. Using actual weather data, we validate that the adaptive robust optimization model can effectively reduce lateness in out-of-sample tests in comparison with other benchmark methods. Keyword: Facility location; disruption risk; demand uncertainty; two-stage robust optimization; column-and-constraint generation; drone delivery; nonlinear energy consumption; branch-and-cut; uncertain weather condition; cluster-wise ambiguity set; distributionally robust optimization