Problème de tournées de véhicules

Problème de tournées de véhicules
Figure illustrant un problème de tournées de véhicules avec un dépot central.

Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d'optimisation combinatoire. Il s'agit de déterminer les tournées d'une flotte de véhicules afin de livrer une liste de clients, ou de réaliser des tournées d'interventions (maintenance, réparation, contrôles) ou de visites (visites médicales, commerciales, etc.)[1]. Le but est de minimiser le coût de livraison des biens. Ce problème est une extension classique du problème du voyageur de commerce, et fait partie de la classe des problèmes NP-complet.

Sommaire

Variantes

Quelques variantes classiques du problème de tournées de véhicules:

  • Problème de tournées de véhicules avec contraintes de capacité: Les véhicules ont une capacité d'emport limitée (quantité, taille, poids, etc.).
  • Problème de tournées de véhicules avec contraintes liées aux ressources et aux clients: disponibilité, localisation, compétences requises, etc.
  • Problème de tournées de véhicules avec fenêtre de temps: Pour chaque client on impose une fenêtre de temps dans laquelle la livraison doit être effectuée.
  • Problème de tournées de véhicules avec collecte et livraison: Un certain nombre de marchandises doivent être déplacées de sites de collecte vers des sites de livraisons.

La résolution du problème peut devenir très difficile lorsque les sous-problèmes interagissent entre eux, par exemple, le problème de bin packing interagit avec l'allocation et la création de tournées dans le cas d'un problème avec contraintes de capacité[2].

Méthodes de résolution

Comme pour la plupart des problèmes NP-complet il est difficile de résoudre des instances de grande taille de façon optimale. On se contente alors de trouver des solutions de « bonne qualité ». Afin d'obtenir des solutions dans des temps de calculs raisonnables, on se tourne généralement vers des méthodes approchées à base d'heuristique tel que l'algorithme de Clarke and Wright[3] pour construire une première solution que l'on améliore ensuite avec d'autres heuristiques ou des méthodes de recherche locale. On peut remarquer que les méthodes d'amélioration utilisées pour le problème du voyageur de commerce tel que l'algorithme de Lin-Kernighan [4] peuvent souvent être appliquées à chacune des tournées individuellement afin d'améliorer le coût global de la solution.

L'optimisation linéaire en nombre entiers permet de résoudre de façon exacte certains problèmes de tournées de véhicules de taille relativement réduite (jusque environ 200 clients à l'heure actuelle). Les méthodes développées sont des applications de Branch and cut[5] , ou plus récemment de génération de colonnes[6].

De nombreuses métaheuristiques ont enfin été appliquées à ce problème, comme la recherche tabou[7], mais aussi les algorithmes génétiques, recherches à voisinage variable etc... Certains problèmes possédant jusque 20000 clients ont ainsi pu être traités de façon efficace[8].

Applications

Les algorithmes de calcul de tournées sont utilisés dans les moteurs des logiciels d’optimisation de tournées. Ces solutions sont utilisées par des entreprises qui souhaitent rationaliser leur flotte de véhicules, réduire leurs coûts ou encore optimiser l’occupation de leur personnel mobile. La fonction d’optimisation de tournée peut aussi être intégrée dans des solutions de planification de ressources mobiles. Ces solutions ont pour vocation de planifier des tâches ou missions avec ou sans prise de rendez-vous, et de les répartir entre les ressources en fonction de leurs contraintes (disponibilité, localisation, compétences requises, durées d’interventions, etc.) Les entreprises concernées par l’optimisation de tournées peuvent appartenir aux secteurs d’activités suivants :

  • Livraison de biens à des entreprises ou à des particuliers : transporteurs, messageries (distribution de presse), grandes surfaces (livraison de marchandises des entrepôts aux magasins, livraison et installation d’équipement à domicile), etc.
  • Réparation et maintenance d’équipements de particuliers (électroménager, chaudières), d’équipements collectifs (ascenseurs, tapis roulants) ou d’entreprises (distributeurs automatiques, équipements industriels)
  • Interventions d’expertises, de contrôle, d’audit (certification, prélèvements, etc.)

Références

  1. Dantzig, G.B.; Ramser, J.H. (1959). "The Truck Dispatching Problem". Management Science 6 (1): 80-91.
  2. (en) What is VRP?, The VRP Web
  3. G. Clarke and J. W. Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12:568–581, 1964.
  4. S. Lin and B. W. Kernighan (1973). An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Res. 21, 498-516.
  5. D. Naddef, G. Rinaldi (2001), "Branch-and-cut algorithms for the capacitated VRP". The vehicle routing problem 53-84 ISBN:0-89871-498-2
  6. R. Baldacci, A. Mingozzi (2009), "A unified exact method for solving different classes of vehicle routing problems". Math. Program. 120:347-380
  7. Cordeau, J. F., & Laporte, G. (2003). A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B, 37, 579-594
  8. Kytojoki, J., Nuortio, T., Braysy, O., & Gendreau, M. (2007). An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Computers & Operations Research, 34(9), 2743-2757

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème de tournées de véhicules de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Probleme de tournees de vehicules — Problème de tournées de véhicules Figure illustrant un problème de tournées de véhicules avec un dépot central. Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d optimisation combinatoire. Il s agit …   Wikipédia en Français

  • Problème de livraison et de collecte — Problème de tournées de véhicules Figure illustrant un problème de tournées de véhicules avec un dépot central. Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d optimisation combinatoire. Il s agit …   Wikipédia en Français

  • Probleme du voyageur de commerce — Problème du voyageur de commerce Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ? Le problème du voyageur de commerce …   Wikipédia en Français

  • Problème du voyageur de commerce — Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ? Le problème du voyageur de commerce consiste, étant donné un… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Generation de colonnes — Génération de colonnes La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille. Elle repose sur la décomposition de Dantzig et Wolfe, qui consiste à décomposer l ensemble des contraintes en… …   Wikipédia en Français

  • Génération De Colonnes — La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille. Elle repose sur la décomposition de Dantzig et Wolfe, qui consiste à décomposer l ensemble des contraintes en deux sous ensembles. L… …   Wikipédia en Français

  • Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La …   Wikipédia en Français

  • Génération de colonnes — La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille[1]. Elle repose sur la décomposition de Dantzig Wolfe (en), qui consiste à décomposer l ensemble des contraintes en deux sous… …   Wikipédia en Français

  • Liste De Problèmes NP-Complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”