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.