problème du voyageur de commerce

Imaginez cinq villes reliées deux à deux, avec une distance inscrite sur chaque liaison. Un livreur doit partir de A, passer une seule fois par B, C, D et E, puis revenir à A. Plusieurs ordres de visite sont possibles : ils peuvent donner des distances totales différentes, mais certains peuvent aussi avoir la même longueur.

Le problème du voyageur de commerce demande de choisir l’ordre qui rend le tour complet aussi court que possible. Le défi ne vient pas du calcul d’un trajet, mais du nombre de trajets à comparer lorsque le nombre de villes augmente.

On modélise les villes par les sommets d’un graphe et la distance entre deux villes par le poids de l’arête qui les relie. Lorsque chaque paire de villes est reliée, le support est un graphe complet pondéré. Une solution du TSP, pour Travelling Salesman Problem, est un cycle hamiltonien : il visite chaque sommet exactement une fois, puis revient au sommet initial. L’objectif est de minimiser la somme des poids de ses arêtes.

Dans la version symétrique, la distance de A à B est la même que celle de B à A. Pour un graphe complet non orienté de n villes, avec n ≥ 3, identifier les circuits qui ne diffèrent que par une rotation du point de départ ou par l’inversion du sens de parcours laisse $\frac{(n-1)!}{2}\backslash frac\{(n-1)!\}\{2\}$ circuits à examiner. Dans une version asymétrique, les deux sens peuvent avoir des coûts différents et les parcours inverses ne sont plus équivalents.

La version de décision demande s’il existe un circuit dont le coût ne dépasse pas un seuil donné ; elle est NP-complète. La recherche du coût minimal, qui est la version d’optimisation, est NP-difficile. Des méthodes exactes garantissent l’optimum, tandis que des heuristiques, des choix gloutons ou des métaheuristiques privilégient une bonne solution obtenue plus vite. L’histoire du problème est liée aux travaux de William Hamilton et Thomas Kirkman au XIX^e siècle.

Une tournée doit relier cinq villes A, B, C, D et E. Les distances, en kilomètres, sont symétriques ; le graphe indique les dix valeurs sans prétendre représenter leur échelle géographique.

Données :
AB = 4, AC = 7, AD = 6, AE = 8 ;
BC = 5, BD = 3, BE = 6 ;
CD = 4, CE = 3, DE = 5.

1. Fixer A comme ville de départ.
2. Choisir le circuit A–B–D–C–E–A, qui visite chaque autre ville une fois.
3. Additionner les cinq distances de ce circuit :4. Comparer ce total aux onze autres circuits distincts, le sens inverse n’étant pas recompté. Aucun n’a un coût inférieur à 22.

La longueur minimale vaut donc 22 km. Le circuit A–B–D–E–C–A atteint aussi 22 km : l’optimum n’est pas unique. Pour contrôler le premier résultat, on vérifie qu’il comporte cinq liaisons, visite B, C, D et E une fois chacune et revient bien à A.

Pour une petite instance, une méthode exacte peut comparer les circuits ou éliminer progressivement ceux qui ne peuvent plus battre la meilleure solution connue. On la préfère lorsqu’une preuve d’optimalité est indispensable.

Lorsque le nombre de villes rend la recherche exacte trop coûteuse, une heuristique construit ou améliore rapidement un circuit. On la choisit lorsque le temps de calcul compte davantage qu’une garantie absolue d’atteindre l’optimum.

Le TSP sert de modèle en logistique, en planification d’itinéraires et en optimisation de trajectoires. Dès qu’il faut plusieurs véhicules, respecter des capacités ou des plages horaires, le problème de tournées de véhicules, ou VRP pour Vehicle Routing Problem, devient le cadre adapté.

Un cycle hamiltonien est n’importe quel cycle qui visite tous les sommets une fois. Le TSP ajoute un critère d’optimisation : dans l’exemple, un circuit de 25 km est hamiltonien, mais il ne résout pas le TSP puisque le minimum vaut 22 km.

Un plus court chemin relie habituellement un sommet de départ à un sommet d’arrivée sans imposer la visite de tous les autres. Le TSP exige au contraire un circuit fermé passant une fois par chaque ville.

Le problème de tournées de véhicules répartit les visites entre plusieurs véhicules et peut ajouter capacités ou horaires. Une seule tournée sans ces contraintes relève du TSP ; une flotte avec des limites de chargement relève du VRP.

NP-complet qualifie la version de décision. Dire sans nuance que le problème d’optimisation est NP-complet mélange deux formulations. Pour la recherche du minimum, le terme exact est NP-difficile.

Une heuristique ne certifie pas toujours l’optimum. Un circuit court reste seulement la meilleure solution trouvée tant qu’une borne ou une méthode exacte n’établit pas qu’aucun circuit plus court n’existe.

La symétrie ne va pas de soi. Le comptage $\frac{(n-1)!}{2}\backslash frac\{(n-1)!\}\{2\}$ suppose qu’un trajet et son inverse ont le même coût. Avec des rues à sens unique ou des coûts directionnels, il faut conserver les deux sens et utiliser le modèle asymétrique.

Plusieurs circuits peuvent partager le minimum. Dans l’exemple à cinq villes, deux circuits non équivalents coûtent 22 km. Il faut donc annoncer une valeur optimale ou un circuit optimal, sans prétendre à l’unicité sans preuve.

La fiche Graphe complet précise le support où chaque paire de villes est reliée.

La fiche NP situe la version de décision du TSP dans le vocabulaire de la complexité.

La fiche algorithme revient sur la notion de procédure finie mobilisée par les méthodes exactes et approchées.