Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithme de résolution du problème d’approvisionnement des stations d’essence

Algorithme de résolution du problème d’approvisionnement des stations d’essence An Exact Algorithm for the Petrol Station Replenishment Problem Fabien Cornillier CENTOR, Université Laval fabien.cornillier@centor.ulaval.ca Fayez F . Boctor CENTOR, Université Laval Gilbert Laporte CRT, HEC Montréal Jacques Renaud CENTOR, Université Laval Journées de l’optimisation 2005 - Montréal Déﬁnition et caractéristiques du problème d’approvisionnement des stations Revue de la littérature Formulation mathématique Méthodes de résolution 2 méthodes proposées Génération des problèmes-tests Résultats Résolution d’un cas réel Résultats Plan de la présentation Caractéristiques du problème d’approvisionnement des stations d’essence Le problème d’approvisionnement des stations d’essence possède deux caractéristiques particulières: Les clients: stations d’essence Les véhicules: camions-citernes 0 km 5 10 15 20 Caractéristiques du problème d’approvisionnement des stations d’essence – Un ensemble S de stations à approvisionner – Pour chaque station i, un nombre T de produits correspondant à au- tant de réservoirs souterrains – Pour chaque réservoir souterrain t ∈{1, . . . , T} de la station i, on connaît : – le niveau de stock initial sit ; – la capacité totale Pit ; – le niveau de stock minimal mit pour répondre à la demande sur la période ; – et l’on peut calculer : – la quantité minimale ait à livrer : ait = max{0, mit −sit} ; – la quantité maximale bit à livrer : bit = Pit −sit Ch éhi l di d C ti t d ité Q 0 km 5 10 15 20 Caractéristiques du problème d’approvisionnement des stations d’essence – Un ensemble S de stations à approvisionner – Pour chaque station i, un nombre T de produits correspondant à au- tant de réservoirs souterrains – Pour chaque réservoir souterrain t ∈{1, . . . , T} de la station i, on connaît : – le niveau de stock initial sit ; – la capacité totale Pit ; – le niveau de stock minimal mit pour répondre à la demande sur la période ; – et l’on peut calculer : – la quantité minimale ait à livrer : ait = max{0, mit −sit} ; – la quantité maximale bit à livrer : bit = Pit −sit Chaque véhicule dispose de C compartiments de capacités Qc Les compartiments ne sont pas équipés de débitmètre : – on transvide la totalité du contenu d’un compartiment dans un seul réservoir souterrain (on peut cependant utiliser plusieurs comparti- ments pour remplir un réservoir) ; – on ne peut livrer qu’un maximum de C demandes et de C stations. On dispose d’une flotte homogène et illimitée Chaque véhicule dispose de C compartiments de capacités Qc L’objectif est de minimiser les coûts de transport pour un ensemble de stations donné, sur une seule période, en disposant d’une flotte illimitée de véhicules. Étant donné un ensemble de stations à approvisionner pour une période données: 1. Affecter chaque station à une tournée 2. Construire et affecter chaque tournée à un véhicule 3. Pour chaque tournée, déterminer le produit et la quantité à affecter à chacun des compartiments du camion Déﬁnition du problème d’approvisionnement Brown & Graves Real-Time Dispatch of Petroleum Tank Trucks. Management Science, 1981 Planification de tournées constituées d’une seule station avec fenêtres de temps. Brown, Ellis, Graves & Ronen Real-Time, Wide Area Dispatch of Mobil Tank Trucks. Interfaces, 1987 Conception d’un outils de planification assistée par ordinateur pour un problème similaire, combinant les solutions du planificateur aux heuristiques dans un environnement temps-réel. Revue de la littérature Brown & Graves (1981) Brown, Ellis, Graves & Ronen (1987) Malépart, Boctor, Renaud & Labilois Nouvelles approches pour l’approvisionnement des stations d’essence. Revue Française de Gestion Industrielle, 2003 Conception d’heuristiques simples pour le problème général d’approvisionnement des stations d’essence avec livraisons multiples par tournée et gestion des contraintes de ressources humaines. Taqa Allah, Renaud & Boctor Le problème d’approvisionnement des stations d’essence Journal Européen des Systèmes Automatisés, 2000 Quatres heuristiques sont proposées tenant compte des coûts de transport, des heures supplémentaires, sur plusieurs périodes. Ce travail consiste plus particulièrement à simuler sur plusieurs périodes l’impact des politiques d’approvisionnement. Revue de la littérature Malépart, Boctor, Renaud & Labillois (2003) Taqa Allah, Renaud & Boctor (2000) Formulation mathématique – Déﬁnissons un sous-ensemble S ⊆V de stations. – On peut calculer dS, le coût du trajet visitant les stations de S en résolvant un problème de voyageur de commerce. Le problème peut être formulé comme un problème de partitionne- ment : (SPP) Minimiser ∑ S⊆V,S̸=Ø dSxS (1) S.c. : ∑ S:i∈S xS = 1 (i ∈V) (2) xS = 0 ou 1 (S ⊆V, S ̸= Ø). (3) avec xS, variable binaire égale à 1 si S est dans la solution optimale, 0 sinon. Résoudre ce problème de partionnement est en général impossible : – le nombre de sous-ensembles S est trop élevé ; – identiﬁer le véhicule optimal est difﬁcile ; – identiﬁer la tournée optimale est difﬁcile. 0 km 5 10 15 20 Complexe... Sans contrainte sur la taille des routes : 1. Nombre combinatoire sous- ensembles de stations 2. On doit résoudre le problème de voyageur de commerce associé Plus simple ! En pratique, la taille des routes dépasse exceptionnellement 2 stations: 0 km 5 10 15 20 1. Le nombre de sous-ensembles de stations est limité 2. Aucun problème de voyageur de commerce 0 km 5 10 15 20 On utilise une méthode basée sur la génération de colonnes (de routes) 1. Générer l’ensemble des routes possibles 2. Pour chaque route, trouver un chargement optimal (affecter les produits demandés aux compartiments d’un camion) 3. Sélectionner les routes : résoudre le problème de partition Méthodologie générale sans contrainte sur la taille des routes 0 km 5 10 15 20 Le problème de partitionnement correspond à un problème de couplage de poids minimal dans un graphe non-bipartite. Le graphe doit être modifié de manière à autoriser des stations non couplées (des routes d’une seule station). Le problème de couplage est résolu par l’algorithme d’Edmonds (1964). Résolution avec routes limitées à 2 stations Formulation mathématique du problème de chargement Le problème de chargement consiste à maximiser la quantité chargée dans le camion-citerne à partir d’un ensemble de demandes : – respecter les bornes minimales et maximales des quantités deman- dées – respecter les capacités des compartiments – n’allouer qu’une seule demande par compartiment (absence de dé- bitmètre) – t : index des commandes (t ∈{1, . . . , T}) ; – c index des compartiments (c ∈{1, . . . , C}) ; – xt variable représentant la quantité livrée dans le réservoir t ; – ytc, variable binaire égale à 1 si le compartiment c est utilisé pour livrer le réservoir t, 0 sinon. (TTLP) Maximiser T ∑ t=1 xt (1) s.c. : at ≤xr ≤bt (t ∈{1, . . . , T}) (2) xt ≤ C ∑ c=1 Qcytc (t ∈{1, . . . , T}) (3) T ∑ t=1 ytc ≤1 (c ∈{1, . . . , C}) (4) ytc = 0 ou 1 (t ∈{1, . . . , T}; c ∈{1, . . . , C}). (5) (2) : Commandes minimales et maximales (3) : Limite de capacité des compartiments (4) : Pas plus d’un produit par compartiment Étape 1 : Identiﬁcation rapide de conditions sufﬁsantes de non réalisa- bilité Résolution optimale des problèmes de chargement Heuristique Problème de chargement Solution réalisable ? Solution optimale ? Programmation linéaire en nombres entiers Solution optimale, si elle existe oui oui non non Résolution Méthode I 1. Éliminer toutes les paires de stations facilement identiﬁables comme étant non réalisables (quantités minimales demandées, nombre de demandes, etc.) 2. Générer toutes les (n2 + n)/2 routes possibles 3. Résoudre le problème de chargement pour chaque route générée 4. Résoudre le problème de couplage permettant de sélectionner les routes optimales dans l’ensemble des routes générées. Le poids as- socié à chaque singleton ou paire de station(s) est le coût du trajet les visitant. 1. Résoudre le problème de couplage de poids minimal en considérant toutes les routes possibles de une ou deux stations 2. Si une route sélectionnée n’est pas réalisable, modiﬁer le graphe en conséquence et résoudre le nouveau problème de couplage 3. Si toutes les routes sont réalisables une solution optimale est iden- tiﬁée. 1. Éliminer toutes les paires de stations facilement identifiables comme étant non réalisables (quantités minimales demandées, nombre de demandes, etc.) 2. Résoudre initialement le problème de couplage en se basant uniquement sur les coûts (aucun problème de chargement n’est résolu); 3. Pour chaque paire (route) sélectionnée dans le problème de couplage, déterminer si un chargement existe (optimal ou non); 4. WHILE(au moins une route sélectionnée est non réalisable) ‣ Interdire les arcs associés aux paires non réalisables ‣ Résoudre le problème de couplage WEND Résolution Méthode II Comparaison des méthodes Méthode I Méthode II Problème de chargement : une fraction de seconde Problème de couplage : quelques secondes (200 stations) Temps approximatifs de résolution (n2 + n)/2 problèmes de chargement + 1 problème de couplage [n problèmes de chargement + 1 problème de couplage] ×nombre d’itérations (n2 + n)/2 uploads/Litterature/ presentation-psrp3.pdf