Wikipédia

Problème de tournées de véhicules

(Redirigé depuis Algorithme de Clarke et Wright)

Le problème de tournées de véhicules (aussi appelé VRP pour Vehicle Routing Problem) 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],[2]. 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.

Figure illustrant une des solutions d'un problème de tournées avec un dépôt central et 3 véhicules disponibles.

Variantes

modifier

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

  • tournées de véhicules avec profits (aussi appelé VRPP pour Vehicle Routing Problem with Profits) : Un problème de maximisation de collecte de profits où il faut sélectionner quels clients visiter tout en respectant les capacités limitées des véhicules [3].
  • contraintes de capacité (aussi appelé CVRP pour Capacitated Vehicle Routing Problem) : Les véhicules ont une capacité d'emport limitée (quantité, taille, poids, etc.) ;
  • contraintes liées aux ressources et aux clients : disponibilité, localisation, compétences requises, etc. ;
  • 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 ;
  • 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é[4].

Méthodes de résolution

modifier

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 et Wright[5]. 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[6] 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 nombres 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[7], ou plus récemment de génération de colonnes[8].

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

Applications

modifier

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, informatique, etc.), d’équipements collectifs (ascenseurs, tapis roulants) ou d’entreprises (distributeurs automatiques, équipements industriels, informatique, etc.) ;
  • interventions d’expertises, de contrôle, d’audit (certification, prélèvements, etc.) ;
  • tournée d'affichage (publicitaire, campagne d’élection, etc.) ;
  • tournées de soins (infirmières/aide-soignants à domicile, ou autre personnel soignant itinérant, etc.) ;
  • tournées commerciales (visites de commerciaux/technico-commerciaux itinérants à leurs clients/prospects dans le cadre d'activités de prospection, démonstrations, etc.).

Références

modifier
  1. ↑ (en) G.B. Dantzig et J.H. Ramser, « The Truck Dispatching Problem », Management Science, vol. 6, no 1,‎ , p. 80–91 (DOI 10.1287/mnsc.6.1.80).
  2. ↑ (en) Burak Eksioglu, Arif Volkan Vural et Arnold Reisman, « The vehicle routing problem: A taxonomic review », Computers & Industrial Engineering, vol. 57, no 4,‎ , p. 1472–1483 (ISSN 0360-8352, DOI 10.1016/j.cie.2009.05.009).
  3. ↑ Farouk Hammami, Monia Rekik et Leandro C. Coelho, « A hybrid adaptive large neighborhood search heuristic for the team orienteering problem », Computers & Operations Research, vol. 123,‎ , p. 105034 (DOI 10.1016/j.cor.2020.105034)
  4. ↑ (en) « What is VRP? », sur dorronsoro.es.
  5. ↑ (en) G. Clarke et J. W. Wright, « Scheduling of Vehicles from a Central Depot to a Number of Delivery Points », Operations Research, vol. 12, no 4,‎ , p. 568–581 (DOI 10.1287/opre.12.4.568).
  6. ↑ (en) S. Lin et B. W. Kernighan, « An Effective Heuristic Algorithm for the Traveling-Salesman Problem », Operations Research, vol. 21, no 2,‎ , p. 498–516 (DOI 10.1287/opre.21.2.498).
  7. ↑ (en) Denis Naddef et Giovanni Rinaldi, chap. 3 « Branch-And-Cut Algorithms for the Capacitated VRP », dans Paolo Toth (dir.) et Daniele Vigo (dir.), The Vehicle Routing Problem, Philadelphie, Society for Industrial and Applied Mathematics, coll. « Discrete Mathematics and Applications », , 358 p. (ISBN 0-89871-498-2, DOI 10.1137/1.9780898718515.ch3), p. 53–84.
  8. ↑ (en) Roberto Baldacci et Aristide Mingozzi, « A unified exact method for solving different classes of vehicle routing problems », Mathematical Programming, vol. 120, no 2,‎ , p. 347–380 (DOI 10.1007/s10107-008-0218-9).
  9. ↑ (en) Nacima Labadie, Christian Prins et Caroline Prodhon, Metaheuristics for Vehicle Routing Problems, Wiley-ISTE, , 194 p. (ISBN 978-1-84821-811-6, lire en ligne).
  10. ↑ (en) Jean-François Cordeau et Gilbert Laporte, « A tabu search heuristic for the static multi-vehicle dial-a-ride problem », Transportation Research Part B: Methodological, vol. 37, no 6,‎ , p. 579–594 (DOI 10.1016/S0191-2615(02)00045-0).
  11. ↑ (en) Jari Kytöjoki, Teemu Nuortio, Olli Bräysy et Michel Gendreau, « An efficient variable neighborhood search heuristic for very large scale vehicle routing problems », Computers & Operations Research, vol. 34, no 9,‎ , p. 2743–2757 (DOI 10.1016/j.cor.2005.10.010).

Liens externes

modifier
Ce document provient de « https://fr.wiki.x.io/w/index.php?title=Problème_de_tournées_de_véhicules&oldid=199862541 ».