Problème de tournées de véhicules (VRP)
Le problème de tournées de véhicules (VRP, Vehicle Routing Problem) est le problème d'optimisation qui consiste à répartir un ensemble de livraisons entre les véhicules d'une flotte et à ordonner les arrêts pour minimiser les coûts, tout en respectant des contraintes comme la capacité et les créneaux horaires.
Qu'est-ce que le problème de tournées de véhicules (VRP) ?
VRP signifie Vehicle Routing Problem. Il généralise le problème du voyageur de commerce (TSP), qui cherche la tournée la plus courte pour un seul véhicule, à toute une flotte soumise à des contraintes réelles : capacité des véhicules, créneaux de livraison, temps de travail des chauffeurs, types de véhicules, etc. Dantzig et Ramser l'ont décrit pour la première fois en 1959 sous le nom de « truck dispatching problem », et il reste l'un des problèmes les plus étudiés de la recherche opérationnelle.
La plupart des problèmes pratiques en sont des variantes. Le VRP avec capacités (CVRP) limite ce que chaque véhicule peut transporter ; le VRP avec fenêtres de temps (VRPTW) ajoute un créneau d'enlèvement ou de livraison par arrêt ; le problème d'enlèvement et de livraison (PDP) associe chaque enlèvement à sa livraison sur le même véhicule ; et les versions multi-dépôts ou à flotte hétérogène permettent aux véhicules de partir de lieux différents ou de différer par la taille et l'équipement.
Le VRP est NP-difficile : le nombre de solutions possibles explose à chaque arrêt ajouté. Un seul véhicule avec dix arrêts peut déjà les visiter dans 3 628 800 ordres différents. Les méthodes exactes ne fonctionnent que pour de petites instances : les solveurs en production utilisent donc des heuristiques. Une méthode de construction comme le plus proche voisin ou l'algorithme des économies de Clarke-Wright établit un premier plan réalisable, puis une recherche locale l'améliore avec des mouvements comme 2-opt, relocate et swap, souvent guidée par une métaheuristique comme le recuit simulé.
Exemple : un distributeur dispose de 3 fourgons d'une charge utile de 1 000 kg et de 45 livraisons, chacune avec un créneau horaire. Un planificateur peut établir à la main un plan exploitable ; un solveur respecte chaque créneau et chaque charge utile tout en minimisant la distance totale, et rend son plan en quelques secondes. Les livraisons qui ne trouvent pas de place sont signalées comme non planifiées, pour que le planificateur puisse ajouter de la capacité ou assouplir un créneau.
L'optimisation des trajets de Transportial fait du solveur un paramètre de la plateforme : PTV OptiFlow, PTV xTour, OSRM pour l'ordonnancement d'un seul véhicule, CloverOpt, ou le solveur propre à Transportial, qui construit les trajets par la méthode du plus proche voisin, les améliore avec des mouvements relocate, swap, merge et split, puis affine chaque itinéraire avec 2-opt. L'optimiseur respecte les créneaux horaires, le poids, le type de véhicule et les contraintes d'équipement, peut insérer les pauses de conduite réglementaires dans les itinéraires et les ETA, et fournit un aperçu que le planificateur ajuste avant d'enregistrer.
Questions fréquentes
Que signifie VRP en logistique ?
VRP signifie Vehicle Routing Problem (problème de tournées de véhicules) : décider quel véhicule dessert quels clients et dans quel ordre, de façon à réduire au maximum la distance, le temps ou le coût total, tout en maintenant chaque véhicule dans sa capacité et chaque arrêt dans son créneau horaire.
Quelle est la différence entre le TSP et le VRP ?
Le problème du voyageur de commerce (TSP) cherche le meilleur ordre d'arrêts pour un seul véhicule. Le VRP décide en plus comment répartir les arrêts entre plusieurs véhicules sous des contraintes de capacité et de temps ; une fois cette répartition faite, l'itinéraire de chaque véhicule est son propre TSP.
Comment un solveur VRP aide-t-il les planificateurs ?
Il construit automatiquement des trajets efficaces (en affectant les envois aux véhicules et en ordonnant les arrêts) : les planificateurs passent moins de temps à planifier à la main et la flotte parcourt moins de kilomètres à vide ou inutiles, tout en respectant la capacité, les créneaux horaires et les règles de temps de conduite.
Un solveur VRP peut-il garantir le meilleur plan possible ?
Pas pour des flottes de taille réaliste : prouver l'optimum prendrait beaucoup trop de temps. Les solveurs pratiques visent un très bon plan en quelques secondes ou minutes et indiquent les arrêts qu'ils n'ont pas pu placer, ce dont les planificateurs ont besoin au quotidien.
Découvrez Problème de tournées de véhicules (VRP) dans un vrai TMS
Transportial met ces concepts en pratique dans une seule plateforme opérationnelle : planification, suivi, documents et finances.