Problème de tournées de véhicules (VRP) : définition, variantes et exemples concrets
Définition rapide : Le problème de tournées de véhicules (VRP) consiste à affecter de nombreux arrêts à un ou plusieurs véhicules et à ordonner chaque tournée afin de minimiser le coût (généralement le temps ou la distance), tout en respectant des contraintes comme les fenêtres horaires, la capacité, le temps de service et les horaires de travail des conducteurs.
VRP = affecter des arrêts aux véhicules + choisir l’ordre des arrêts sous contraintes (le cœur de l’optimisation des tournées).
Résolvez un routage de type VRP dans votre navigateur
Ajoutez des arrêts, ajoutez des véhicules, appliquez des fenêtres horaires et des capacités, puis générez instantanément des tournées optimisées.
Essayer l’outil d’optimisation des tournées
Lire le guide de l’optimisation des tournées
Qu’est-ce que le problème de tournées de véhicules (VRP) ?#
Le VRP est le problème général de routage de flotte derrière les livraisons, la planification des interventions terrain et la planification d’itinéraires multi-conducteurs. La question est : comment construire une ou plusieurs tournées qui visitent efficacement tous les arrêts requis ?
En pratique, le VRP consiste à décider :
- Quel véhicule doit desservir chaque arrêt
- Dans quel ordre chaque véhicule doit visiter ses arrêts attribués
- Quand chaque arrêt doit être visité (ETA), tout en respectant les contraintes
C’est exactement ce que fait un logiciel d’optimisation des tournées. Pour une vue pratique, commencez par l’article pilier :
Optimisation des tournées : guide complet
.
VRP vs TSP : quelle est la différence ?#
Une confusion fréquente oppose le VRP au problème du voyageur de commerce (TSP).
- TSP : un seul véhicule doit visiter tous les arrêts une fois et revenir (ou terminer) — la meilleure tournée unique.
- VRP : plusieurs véhicules peuvent exister, les arrêts doivent être affectés aux véhicules, et les contraintes sont courantes (fenêtres horaires, capacité, horaires de travail).
Autrement dit : le VRP est le TSP du monde réel.
Pourquoi le VRP est difficile#
Le VRP devient rapidement difficile car le nombre de solutions possibles explose : il ne s’agit pas seulement de choisir un ordre d’arrêts, mais aussi de choisir quel véhicule dessert quels arrêts.
Ajoutez des contraintes comme les fenêtres horaires et la capacité, et de nombreuses tournées candidates deviennent invalides. C’est pourquoi les optimiseurs de production se concentrent sur des solutions de haute qualité rapidement, et non sur une optimalité parfaite.
Variantes courantes du VRP (types que vous verrez en pratique)#
La plupart des problèmes d’optimisation des tournées correspondent à l’une de ces variantes du VRP, ou à une combinaison de celles-ci.
Tableau des variantes courantes du problème de tournées de véhicules et de leur signification
| Variante |
Signification |
Exemple concret |
| VRPTW |
VRP avec fenêtres horaires (il faut arriver dans une plage horaire autorisée) |
Livraisons avec créneaux de rendez-vous (9:00–12:00) |
| CVRP |
VRP capacitaire (le véhicule a des limites de poids/volume) |
Limites de charge des camions, planification de capacité des utilitaires |
| MDVRP |
VRP multi-dépôts (les véhicules partent de dépôts différents) |
Agences / hubs régionaux |
| SDVRP |
VRP à livraison fractionnée (un arrêt peut être desservi par plus d’un véhicule) |
Grosses commandes réparties sur plusieurs camions |
| PDVRP |
VRP de collecte et livraison (la collecte doit avoir lieu avant la livraison) |
Collectes + livraisons de messagerie |
| Open VRP |
Les tournées n’ont pas besoin de revenir au dépôt |
Tournées en aller simple se terminant au domicile / à la base du conducteur |
| Backhauls |
Livrer en sortie puis récupérer des charges au retour |
Livraison + collecte de retours |
Si votre activité fonctionne avec des créneaux horaires, voir :
Optimisation des tournées avec fenêtres horaires
.
Si vous utilisez plusieurs conducteurs, voir :
Optimisation des tournées avec plusieurs véhicules
.
Contraintes du monde réel prises en charge par les modèles VRP#
Dans les opérations réelles, la tournée la plus courte n’est souvent pas faisable. Les contraintes définissent ce qui est autorisé.
- Fenêtres horaires : arriver uniquement pendant la disponibilité du client
- Temps de service : temps passé à chaque arrêt (livraison, inspection, paperasse)
- Capacité véhicule : limites de poids/volume et demande par arrêt
- Horaires de travail : début/fin de service pour chaque véhicule/conducteur
- Lieux de départ/arrivée : dépôt, entrepôt ou base du conducteur
- Priorités : arrêts urgents d’abord ou règles de livraison garanties
C’est pourquoi le simple réordonnancement des arrêts n’est pas la même chose que l’optimisation pour des flottes. Pour le workflow pratique, lisez :
Comment fonctionne l’optimisation des tournées
.
Les grandes instances de VRP sont rarement résolues par force brute. À la place, les moteurs d’optimisation des tournées :
- Construisent rapidement une solution initiale (un plan de tournée faisable)
- L’améliorent itérativement en échangeant des arrêts, en déplaçant des arrêts entre tournées et en réordonnant les séquences
- Équilibrent vitesse et qualité afin de retourner des résultats assez rapidement pour la planification quotidienne
À retenir : les meilleurs outils de routage se concentrent sur des tournées faisables que les conducteurs peuvent réellement exécuter, et pas seulement sur la distance la plus courte.
Si vous voulez le volet résultats métier, voir :
Les avantages de l’optimisation des tournées
.
Quelles données faut-il pour résoudre le VRP#
Pour obtenir des tournées et des ETA précis, il faut de bonnes données d’entrée. Voici la checklist minimale :
Arrêts
- Adresse ou latitude/longitude
- Optionnel : temps de service (minutes à l’arrêt)
- Optionnel : fenêtres horaires (heure la plus tôt / la plus tard)
- Optionnel : demande (poids/volume)
Véhicules / conducteurs
- Lieu de départ (et éventuellement lieu d’arrivée)
- Horaires de travail (Time In / Time Out)
- Optionnel : limites de capacité
TrackRoad prend en charge ces entrées (y compris l’import Excel) ici :
Optimiseur de tournées
.
Exemple simple de VRP#
Imaginez 30 arrêts de livraison et 3 véhicules. L’optimiseur doit décider quels arrêts vont à quel véhicule, puis ordonner les arrêts sur chaque tournée pour minimiser le temps de trajet, tout en veillant à ce que chaque conducteur termine dans ses horaires de travail et que les fenêtres horaires soient respectées.
Cette combinaison affectation + ordre + contraintes, c’est le VRP — et c’est pourquoi l’optimisation des tournées va au-delà de la simple navigation.
FAQ#
Quel est le type de VRP le plus courant en livraison ?
Le VRPTW (fenêtres horaires) et le CVRP (capacité) sont les plus courants en livraison et en routage de service terrain.
Que signifie VRPTW ?
VRPTW signifie Vehicle Routing Problem with Time Windows — chaque arrêt doit être visité dans une plage horaire autorisée.
Le VRP peut-il inclure plusieurs véhicules et dépôts ?
Oui. De nombreuses flottes réelles sont multi-véhicules et souvent multi-dépôts (MDVRP), selon la structure des opérations.
Le VRP est-il la même chose que l’optimisation des arrêts ?
Pas vraiment. Le réordonnancement des arrêts n’est qu’une petite partie. Le VRP inclut généralement l’affectation des arrêts aux véhicules et le respect de contraintes telles que les fenêtres horaires, la capacité, le temps de service et les horaires de travail.
Quel est le meilleur point de départ si je débute ?
Essayez l’optimisation de tournées de type VRP
Importez des arrêts depuis Excel, ajoutez des véhicules, appliquez fenêtres horaires et capacités, puis optimisez vos tournées en quelques secondes.
Commencer l’optimisation
Voir les avantages de l’optimisation des tournées