Méthodes de décomposition pour l'optimisation de la distribution des produits pétroliers.

Le pétrole demeure une source d’énergie majeure dans la plupart des sociétés modernes, même si d’autres sources d’énergie alternatives (gaz, électricité et énergie solaire) s’avèrent de plus en plus utilisées. Les stations-service quant à elles sont des nœuds cruciaux dans la chaîne d’approvisionnement mondiale. Elles n’ont cessé d’évoluer depuis plus de quarante ans. En raison de cette croissance, le nombre et la taille des véhicules utilisant des produits pétroliers de stations-service ont augmenté de façon significative. Par conséquent, les entreprises du secteur pétrolier y ont investi massivement. Pour tirer parti de ces investissements, ces entreprises cherchent à optimiser leurs opérations. Celles-ci comprennent le réapprovisionnement, le stockage et le transport depuis les dépôts jusqu’aux points de vente. Dans cette thèse, nous proposons des méthodes de décomposition exactes pour résoudre le problème d’optimisation du réapprovisionnement des stations-service (PRP : Petrol Replenishment Problem). Il fait partie de la famille des problèmes des tournées de véhicules compartimentés (MCVRP : Multi-Compartment Vehicle Routing Problem) bien connue pour se montrer NP-difficile. Dans la littérature, les variantes du PRP sont souvent résolues par des méthodes heuristiques, alors que très peu de travaux ont été consacrés à la création de méthodes exactes. Le but de cette thèse consiste à combler cette lacune en utilisant des méthodes exactes basées principalement sur la décomposition de Benders (BD : Benders Decomposition) et la décomposition de Dantzig-Wolfe (la génération de colonnes (CG : Column Generation) dans un encadrement de BP : Branch-and-Price). Dans une première contribution à cette thèse, nous traitons une variante riche du problème de réapprovisionnement de stations-service avec multi-dépôts et multi-périodes (MDMPPRP : Multi-Depot Multi-Period Petrol Replenishment Problem), ce qui implique la planification des tournées de plusieurs camions-citernes fortement compartimentés (jusqu’à 15 compartiments),afin de livrer des produits pétroliers à des stations-service pendant plusieurs périodes. L’objectif est de minimiser les coûts de transport tout en respectant les contraintes de capacité des camions-citernes et de temps de livraison. Afin de résoudre ce problème, nous avons engagé une nouvelle méthode primale de branchement en profondeur (PDH : Primal Diving Heuristic) efficace pour les problèmes de partitionnement d’ensembles peu ou moyennement denses. Cette méthode permet de résoudre à chaque noeud de branchement un problème plus petit et donc plus facile. Nous avons également utilisé une approche BP exacte pour évaluer la qualité des solutions générées par PDH. Celle-ci nous a permis de trouver des solutions optimales ou presque optimales. Quant à la génération de colonnes, nous avons résolu des sous-problèmes, chacun constituant un problème de plus court chemin élémentaire, avec contraintes de ressources(ESPPRC:Elementary Shortest Path Problem with Resource Constraints), où des centaines de millions d’extensions d’étiquettes sont effectuées ; chaque extension exige la résolution d’un programme en nombre entiers mixtes (MILP : Mixed-Intger Linear Program) qui s’assure de la faisabilité du chargement des commandes des stations-service dans le camion citerne à chaque extension (un compartiment doit être affecté au plus à une seule station-service) appelé problème de chargement des camions-citernes (TTLP : Tank Truck Loading Problem). Cela rend la résolution de cette variante impossible par les méthodes standards. Afin d’y remédier, nous proposons une technique de hachage réduisant drastiquement le nombre de MILP à résoudre, en utilisant l’intuition voulant que plusieurs patterns de TTLP puissent se répéter dans la génération de certaines étiquettes. Enfin, nous avons réalisé une étude de cas pour démontrer l’implantabilité de l’approche que nous avons proposée. Cette étude se distingue de ce qui se fait dans le contexte nord américain, dans lequel une tournée contient une ou deux stations-service, car on livre relativement de petites quantités, ce qui augmente le nombre de stations-service par tournée (jusqu’à 7 par tournée), rendant ainsi la résolution difficile dans un réseau cyclique. Les résultats ont montré que notre méthode s’avère capable de résoudre efficacement des instances de taille réelle, dans un temps de calcul raisonnable. Les techniques de branchement primal, BP et de génération de tournées nous ont permis d’obtenir des résultats de haute qualité, tout en garantissant la faisabilité et l’efficacité de la méthode. L’article intitulé "Solving a real-world multi-depot multi-period petrol replenishment problem with complex loading constraints" qui décrit cette contribution, a été publié dans la revue European Journal of Operational Research, en 2023.En guise de deuxième contribution, nous étendons les techniques développées dans le premier objectif afin de résoudre le MDMPPRP avec une gestion d’inventaire appelé (MDMPPRPIM :Multi-Depot Multi-Period Petrol Replenishment Problem with Inventory Management). Nous introduisons aussi la gestion du stock hebdomadaire au niveau des dépôts. Dans un premier temps, nous utilisons une formulation compacte (MILP) intégrant à la fois le TTLP et le problème des tournées de véhicules avec gestion de stock (IRP : Inventory Routing Problem). Compte tenu de sa complexité, qui provient essentiellement de l’écart d’intégralité élevé, cette formulation demeure très difficile à résoudre par des solveurs commerciaux, même pour de petites instances. Nous créons ainsi une approche de résolution exacte en deux phases combinant la décomposition de BD et de BP. Le problème maître de BD décide du niveau des stocks dans les dépots et les stations-service, alors que les sous-problèmes de BD cherchent à résoudre le problème de réapprovisionnement en tenant compte du niveau des stocks. Avec cette hybridation, le l’écart d’intégralité n’est plus problématique. Dans la première phase, nous résolvons des sous-problèmes de BD relaxés (sans contraintes d’intégralité) jusqu’à ce que les niveaux de stocks se stabilisent. Dans la seconde phase, nous résolvons à l’optimalité les sous-problèmes de BD à l’aide d’un algorithme de BP. Nous améliorons notre approche par diverses stratégies d’accélération, y compris les coupes initiales, le parallélisme et PDH. Des résultats étendus sur des instances réelles mettent en évidence la force de notre approche. Nous parvenons à des solutions quasi-optimales dans la plupart des cas et nous constatons que les stratégies d’accélération augmentent considérablement les performances de l’approche en deux phases. Nous générons plusieurs aperçus managériaux qui soulignent les avantages obtenus grâce à l’optimisation intégrée. Enfin, l’article intitulé "Combining Benders Decomposition and Column Generation for the Petrol Station Replenishment Problem with Inventory Management" traitant cette contribution, a été soumis à la revue Management Science, en 2024.Dans une troisième contribution, nous capitalisons les connaissances acquises dans les deux premiers articles, afin de répondre à un cas d’étude réel chez une entreprise de distribution de produits pétroliers souhaitant optimiser son réseau de distribution. Nous avons montré qu’en utilisant adéquatement notre outil d’aide à la décision, nous pouvons évaluer la politique de tarification, le design du réseau, par exemple, en augmentant de 15% la capacité des réservoirs, que nous pouvons réduire le coût de 354 K$ par trimestre et que cela est plus intéressant que d’aller plus loin que 25%, que nous pouvons aussi diminuer le nombre de camions-citernes à un ensemble minimal sans trop impacter le coût total. Les résultats numériques sur un réseau réel (jusqu’à quatre dépôts, cinq types de produits pétroliers, quatre groupes principaux de stations-service et une flotte de 44 camions-citernes hétérogènes et fortement compartimentée) prouvent l’efficacité et le potentiel élevé de l’approche proposée. Ils mettent également en évidence l’impact de l’optimisation en Afrique et de la pratique du réapprovisionnement des stations-service sur le continent africain. Enfin, l’article intitulé "The Petrol Station Replenishment Problem : A Case Study from West Africa" résumant cette contribution a été soumis, à la revue African Transport Studies, en 2024.Dans cette thèse, nous avons montré, avec des résultats très prometteurs, que les méthodes de décomposition fondées sur des approches exactes constituent des solutions viables pour résoudre le problème MDMPPRPIM, et que les techniques crées deviennent génériques et peuvent être étendues à d’autres problèmes de la famille du MCVRP.