problème du voyageur de commerce

problème VRP
problème TSP
problème de tournées de véhicules

COMBINATOIRE

Le problème du voyageur de commerce ou problème TSP (Travelling Salesman Problem) est un problème d’optimisation, proposé en 1800 par William Hamilton et Thomas Kirkman, dont un énoncé est : Etant donné n points (les « villes ») et les distances séparant chaque point, trouver un chemin de longueur totale minimale qui passe exactement une fois par chaque point et revienne au point de départ.

Ce problème peut être modélisé dans le cadre de la théorie des graphes. Il fait partie de la classe des problèmes NP-complets . On ne connaît pas de méthode de résolution donnant la solution exacte en un temps raisonnablement court pour n grand car le nombre de trajets augmente de façon exponentielle.

Ce problème trouve des applications dans des problèmes de recherche opérationnelle ou dans l’optimisation de trajectoires.

Le problème des tournées de véhicules ou problème VRP (Vehicle Routing Problem) est une extension du problème précédent. Il s’agit cette fois d’optimiser les tournées d’une flotte de véhicules en minimisant le coût des livraisons. Il peut s’y ajouter des contraintes comme la capacité des véhicules, ou les heures de passage à chaque point.
.