Qu'est-ce que le VRP ? Problème de tournées de véhicules, expliqué

Le VRP (vehicle routing problem, problème de tournées de véhicules) est le problème mathématique consistant à trouver le meilleur ensemble de tournées pour une flotte de véhicules qui doit desservir un groupe de clients. C'est la question centrale derrière tout outil de planification de livraisons.

Le VRP généralise le plus ancien problème du voyageur de commerce, qui fait passer un seul véhicule par de nombreux arrêts. Le VRP ajoute une flotte, des capacités de véhicules, des créneaux horaires, des services de chauffeurs et d'autres contraintes réelles, puis demande les tournées qui coûtent le moins en distance, en temps ou en argent. Il est NP-difficile : le nombre de combinaisons de tournées explose dès qu'on ajoute des arrêts, si bien que les systèmes réels utilisent des heuristiques et des solveurs qui trouvent une très bonne solution plutôt qu'une solution prouvée optimale.

Chaque exploitant en résout une version, le plus souvent à la main et par habitude. Un transporteur express avec trente camionnettes et quatre cents points de livraison affronte chaque matin des milliards de plans possibles. Un logiciel qui rogne ne serait-ce que cinq pour cent de la distance totale réduit le carburant, les heures supplémentaires et l'usure sur toute la flotte, chaque jour.

Les variantes collent aux opérations réelles : tournées avec créneaux horaires pour les livraisons sur rendez-vous, collecte-livraison pour la messagerie, et tournées sous contrainte de capacité où chaque véhicule a une limite de poids ou de volume. Un TMS ou un outil de gestion des interventions embarque souvent un moteur de tournées qui résout une variante du VRP.

Pourquoi c'est important pour le logiciel sur mesure

Les optimiseurs de tournées génériques présument des contraintes génériques. Les flottes réelles en ont de très précises : un chauffeur habilité aux matières dangereuses, un client qui ne reçoit qu'avant midi, une camionnette interdite de zone à faibles émissions. Une couche de routage sur mesure encode vos règles réelles plutôt que des règles moyennes. Nous l'intégrons au logiciel logistique, au-dessus des données cartographiques et de télématique qu'une flotte collecte déjà.