Le problème d'approvisionnement de stations d'essence consiste à livrer des carburants à l'aide d'une flotte de camions-citernes compartimentés en maximisant une fonction de revenu du transporteur. Il convient essentiellement de déterminer les quantités à livrer de chaque produit, de les affecter aux compartiments des véhicules et de construire les routes permettant leur livraison. Cette thèse comporte trois articles présentant chacun une version différente de ce problème d'approvisionnement. / Nous proposons, dans le premier article, une méthode exacte de résolution applicable au cas où la flotte est illimitée et le nombre de stations par route limité à deux. Le problème y est décomposé en un sous-problème d'affectation des produits aux compartiments des véhicules et un sous-problème de routage. L'affectation des produits aux compartiments repose sur un algorithme classique d'affectation dans un graphe bipartite suivi d'un test d'optimalité, et recourt éventuellement à la résolution d'un programme linéaire en nombres entiers. Puisqu'un voyage ne peut desservir plus de deux stations, le problème de routage est réduit à un problème de couplage de coût minimal clans un graphe non bipartite. Deux stratégies sont alors proposées : rechercher un chargement admissible des produits dans les compartiments pour tous les couples possibles de stations, puis résoudre le problème de couplage correspondant, ou générer les routes en résolvant le problème de couplage a priori pour ensuite tester l'existence d'un chargement admissible pour chacune, cette procédure étant répétée aussi longtemps qu'une route non admissible est générée. / Nous présentons dans le second article une heuristique appliquée au problème d'approvisionnement sur plusieurs périodes avec cette fois un nombre limité de camions-citernes. Dans cette version du problème d'approvisionnement, l'objectif est de déterminer pour chacjue période, les stations, les produits et les quantités à livrer, d'affecter les pioduits aux compartiments des camions-citernes et de construire les routes. L'affectation des stations aux différentes périodes est déterminée par un algorithme récursif incluant une procédure d'anticipation des livraisons. Nous proposons par ailleurs une procédure d'affectation des routes aux véhicules (route packing) par laquelle les routes sont affectées aux véhicules. / Dans le troisième article, nous nous intéressons à nouveau au problème monopé¬riode en intégrant cette fois la gestion des fenêtres de temps en dehors desquelles les livraisons ne peuvent avoir lieu. Nous y considérons par ailleurs le cas d'une flotte limitée et relaxons l'hypothèse de limitation des routes à deux stations. Une formulation différente de celle proposée dans le premier article est présentée. Elle repose sur une sélection de routes respectant les contraintes horaires à partir d'un ensemble de routes admissibles générées a priori et éventuellement présélectionnées. De cette formulation, deux heuristiques sont développées reposant sur une présélection des arcs du graphe c
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/19084 |
| Date | 12 April 2018 |
| Creators | Cornillier, Fabien |
| Contributors | Boctor, Fayez Fouad, Laporte, Gilbert |
| Source Sets | Université Laval |
| Language | French |
| Detected Language | French |
| Type | thèse de doctorat, COAR1_1::Texte::Thèse::Thèse de doctorat |
| Format | xii, 190 f., application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
Page generated in 0.0026 seconds