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.

Abstract

Petroleum is still a major source of energy in most modern societies, even though other alternative sources of energy (gas, electricity, solar) are increasingly used. One of the key success factors in the petroleum industry is the efficiency of its complex distribution system. However, the management of its different activities is a constant and a real challenge. These activities include procurement, transportation of petrol products from depots to petrol stations, and inventory management at both (depots and petrol stations) points. In this thesis, we propose exact decomposition methods for solving the petrol station replenishment problems (PRP), which are often solved in the literature with heuristics, while very few works have used exact methods. We fill this gap by introducing exact methods based mainly on Benders decomposition, and column generation embedded in the Branch-and-Price framework.In the first contribution, we address a new variant of PRP, which is a rich real-world multidepot multi-period (MDMPPRP). We show that it is possible to solve this complex variant with an exact Branch-and-Price approach and some derived heuristics. On one side, this problem could be modeled as a set partitioning type problem with low to moderate density (the number of ones per column, i.e., clients to visit, is not large). Such problems have some nice polyhedral properties to consider for favoring integrality. On the other side, some complex handling rules apply due to the problem’s context. A natural way is to address them in the column generation subproblem as an elementary shortest path problem with resource constraints, which constitutes the major bottleneck. To succeed in this challenge, we need to design some sophisticated techniques i) for branching to profit from the polyhedral properties and ii) for solving the column generation subproblem. Direct use of on-the-shelf algorithms does not work, unfortunately. Numerical results on a real network (four depots, five types of petrol products, four main groups of clients, heterogeneous fleet of highly compartmented tank trucks) prove the effectiveness and high potential of the proposed approach. In the second contribution, we extend the techniques developed to solve another variant of MDMPPRP with the integration of inventory management (MDMPPRPIM). We investigate a petrol station replenishment problem (PRP) that integrates the tank truck loading problem (TTLP) and inventory routing problem (IRP). We introduce a compact mixed integer linear program (MILP) formulation for the problem. Given its complexity, the compact formulation cannot be solved by general-purpose solvers, even for small instances. We develop an exact two-phase solution approach that combines Benders decomposition and column genxeration. In the first phase, we solve relaxed (integrality) Benders subproblems until the inventory levels stabilize. In the second phase, we solve to optimality Benders decomposition subproblems using a Branch-and-Price framework. We enhance our approach with various acceleration strategies, including warm-start, parallelism, and primal diving heuristics. Extensive computational results using real-world instances from one of the major companies in West Africa highlight the strength of our approach. We reach near-optimal solutions in most of these instances and note that acceleration strategies significantly boost the performance of our two-phase method. We generate several managerial insights that highlight the benefits achieved through integrated optimization. In the third contribution, we capitalize on our experience through a comprehensive overview of our case study at a fast-growing petroleum company in West Africa. This study explains how we used the work done in the first and second contributions to help this petroleum company optimize its distribution network using operational research tools. We approach this study in two steps. In the first step, we use the BP method to solve the weekly case where each customer can be visited more than once within a specified interval of days within the horizon (one week). In the second step, we use Benders decomposition to solve the case with a horizon of up to 12 weeks. The numerical results on a real network (up to four depots, five types of petrol products, four main customer groups, and a fleet of 44 heterogeneous and highly compartmented tank trucks) prove the efficiency and high potential of the proposed approach. They also highlight the impact of optimization on Africa and the practice of refueling service stations on the African continent. This thesis has successfully showcased the viability of decomposition methods that rely on exact approaches in addressing the MDMPPRPIM problem. The results obtained from our research have been highly promising. Furthermore, the techniques developed during this study are not only applicable to the MDMPPRPIM problem but can also be extended to other problems within the multi-compartment vehicle routing problem family.