Utilisateur:PierreSelim/VRP
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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[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.
Variantes[modifier | modifier le code]
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 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 marchandise doivent être déplacer de sites de collecte vers des sites de livraisons.
Méthodes de résolution[modifier | modifier le code]
Comme pour la plus part 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 raisonnable on se tourne généralement vers des méthodes approchées à base d'heuristique tel que l'algorithme de Clarke et Wright[2] 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 [3] peuvent souvent être appliquées à chacune des tournées individuellement afin d'améliorer le coût globale de la solution.
La programmation linéaire permet de résoudre de façon exacte[4] les problèmes de tournées de véhicules à l'aide de la méthode dite Branch and cut.
Références[modifier | modifier le code]
- Dantzig, G.B.; Ramser, J.H. (1959). "The Truck Dispatching Problem". Management Science 6 (1): 80-91.
- 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.
- S. Lin and B. W. Kernighan (1973). An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Res. 21, 498-516.
- D. Naddef, G. Rinaldi (2001), "Branch-and-cut algorithms for the capacitated VRP". The vehicle routing problem 53-84 ISBN:0-89871-498-2
