Le problème de location-routage des véhicules

Thèmes abordés

Problème de location-routage des véhicules, intérêts, approches heuristiques, acheminement de produits, dépôts, usines, entrepôts, localisation d'un objet, système de distribution, travaux de Laporte et Dejax, phase de routage

Résumé du document

Le routage est un mécanisme par lequel des chemins sont sélectionnés dans un réseau pour acheminer les produits d'un expéditeur jusqu'à un ou plusieurs destinataires. La localisation d'un objet consiste en la détermination de sa position géographique. L'emplacement de l'installation et le routage des véhicules sont des domaines interdépendants. Il s'agit de placer des installations (dépôts, usines) sur un ensemble de sites possibles et de déterminer des tournées desservant un ensemble de clients à partir des installations construites. L'objectif est de minimiser le coût total du système de distribution (coûts de construction ou d'exploitation des entrepôts, coûts des véhicules et coûts des tournées).

Extraits

[...] Problème de location-routage 2014-2015 Laporte et al. (1986) En prenant L un nombre arbitraire relativement grand, le modèle peut se formuler ainsi : Variables de décision Les variables de décision suivantes sont utilisées : yi = 1 si et seulement si le dépôt i est ouvert. xij = 1 ∈ V ) si et seulement si un véhicule utilise l'arête une et une seule fois, xij = 2 ∈ i ∈ si et seulement si un véhicule utilise une même arête deux fois (si un véhicule ne sert qu'un seul client j à partir du dépôt i). [...]

[...] Intensification ou diversification de la recherche. Problème de location-routage 2014-2015 III – Variantes Problème de location-routage 2014-2015 De récents travaux commencent à intégrer d'autres contraintes, par exemple Lin et Kwok proposent des méta heuristiques pour une version dans laquelle les dépôts et les véhicules sous soumis à des contraintes de capacité. De plus, un même véhicule peut être utilisé pour effectuer plusieurs tournées. III – Variantes Problème de location-routage 2014-2015 Les coûts du LRP représentent une part importante aussi bien d'un point de vue financier que d'un point de vue environnemental. [...]

[...] Extension du FLP Problème de location-routage 2014-2015 I – Introduction Le routage: mécanisme par lequel des chemins sont sélectionnés dans un réseau pour acheminer les produits d'un expéditeur jusqu'à un ou plusieurs destinataires. la localisation d'un objet consiste en la détermination de sa position géographique. L'emplacement de l'installation et le routage des véhicules sont des domaines interdépendants. Problème de location-routage 2014-2015 II – Définitions Les problèmes de localisation-routage (location-routing problem ou LRP): Objectif Minimiser le coût total du système de distribution (coûts de construction ou d'exploitation des entrepôts + coûts des véhicules + coûts des tournées). [...]

[...] Les coûts portent sur l'ouverture de dépôts et sur l'élaboration des tournées (sans coût fixe d'ouverture). couts-logistique.jpg Une capacité limitée et une distance maximale contraignent ces dernières. ILLUS_ForteContrainte.jpg Déterminer le nombre des dépôts à ouvrir, le nombre de véhicules à utiliser, ainsi que de construire des tournées. téléchargement.jpg Capacité limitée sur les véhicules ou les dépôts uniquement Srivastava 1993 Capacité limitée sur les véhicules ou les dépôts uniquement Les premiers sont utilisés pour construire des tournées, dans lesquelles les seconds sont ensuite insérés si les capacités le permettent. [...]

[...] les coûts des dépôts et des ouvertures de tournées. Albareda-Sambola et al. (2005) Problème de location-routage 2014-2015 VI – Approches heuristiques Problème de location-routage 2014-2015 La plupart des travaux, en particulier récents, sont des approches de résolution de type heuristique. On peut cependant distinguer les recherches selon les contraintes de capacité utilisées. carte_heuristique_by_zimmermann.jpg L'étude de Chien 1993 images.jpgEMR-An-All-in-One-Solution.jpg Les meilleures solutions obtenues sont améliorées par une recherche locale Problème de location-routage 2014-2015 En utilisant un estimateur des distances parcourues par les véhicules En résolvant un TSP VI – Approches heuristiques Capacité limitée sur les véhicules ou les dépôts uniquement Problème de location-routage 2014-2015 Srivastava 1993 Ouvrir tous les dépôts au départ, puis les fermer un par un en choisissant celui offrant le meilleur gain estimé. [...]