Le problème du voyageur de commerce

Le problème

Un voyageur de commerce doit visiter $n$ villes données en passant par chaque ville exactement une fois. Il commence par une ville quelconque et termine en retournant à la ville de départ. Les distances entre les villes sont connues. Quel chemin faut-il choisir afin de minimiser la distance parcourue ? La notion de distance peut-être remplacée par d'autres notions comme le temps qu'il met ou l'argent qu'il dépense : dans tous les cas, on parle de coût.

Historique

19ième siècle

Les premières approches mathématiques exposées pour le problème du voyageur de commerce ont été traitées au $19^{i\grave{e}me}$ siècle par les mathématiciens Sir William Rowan Hamilton et Thomas Penyngton Kirkman. Hamilton en a fait un jeu : Hamilton's Icosian game. Les joueurs devaient réaliser une tournée passant par 20 points en utilisant uniquement les connections prédéfinies.

années 1930

Le PVC est traité plus en profondeur par Karl Menger à Harvard. Il est ensuite développé à Princeton par les mathématiciens Hassler Whitney et Merril Flood. Une attention particulière est portée sur les connections par Menger et Whitney ainsi que sur la croissance du PVC.

1954

Solution du PVC pour 49 villes par Dantzig, Fulkerson et Johnson par la méthode du cutting-plane[3].

1975

Solution pour 100 villes par Camerini, Fratta and Maffioli

1987

Solution pour 532, puis 2392 villes par Padberg et Rinaldi

1998

Solution pour les 13 509 villes des Etats-Unis.

2001

Solution pour les 15 112 villes d'Allemagne par Applegate, Bixby, Chvàtal et Cook des universités de Rice et Princeton.

Point de vue formel

A partir d'une matrice $C=(C_{ij})$ où $C_{ij}$ représente le coût du déplacement entre la ville $i$ et la ville $j$ $(1\leq i,j\leq n)$, il faut trouver une permutation

$$\sigma=\left\lgroup{^{1}_{{\sigma{(1)}}}\;^{2}_{{\sigma{(2)}}}\;^{\cdots}_{\cdots}\;^{n}_{{\sigma{(n)}}}}\right\rgroup$$

qui minimise la somme des coûts $C_{{\sigma{(1)}}{\sigma{(2)}}}+C_{{\sigma{(2)}}{\sigma{(3)}}}+\cdots+C_{{\sigma{(n-1)}}{{\sigma{(n)}}}}+C_{{\sigma{(n)}}{{\sigma{(1)}}}}$. Autrement dit, il faut trouver un cycle hamiltonien¹ de longueur minimale dans un graphe pondéré complet.

Complexité

Ce problème est un représentant de la classe des problèmes NP-complets. L'existence d'un algorithme de compléxité polynomiale reste inconnue. Un calcul rapide de la complexité montre qu'elle est en $O(n!)$ où $n$ est le nombre de villes. En supposant que le temps pour évaluer un trajet est de 1 $\mu {s}$, le tableau 1 montre l'explosion combinatoire du PCV.

Tableau 1: Nombre de possibilités de chemins et temps de calcul en fonction du nombre de villes (on suppose qu'il faut 1 $\mu {s}$ pour évaluer une possibilité)

Nb villes	Nb possibilités	Temps de calcul
5	12	12 $\mu {s}$
10	181440	0,18 $ms$
15	43 milliards	12 heures
20	60 E+15	1928 ans
25	310 E+21	9,8 milliards d'années

Intérêt

Le PVC fournit un exemple d'étude d'un problème NP-complets dont les méthodes de résolution peuvent s'appliquer à d'autres problèmes de mathématiques discrète. Néanmoins, il a aussi des applications directes, notamment dans les transports et la logistique. Par exemple, trouver le chemin le plus court pour les bus de ramassage scolaire ou, dans l'industrie, pour trouver la plus courte distance que devra parcourir le bras mécanique d'une machine pour percer les trous d'un circuit imprimé (les trous représentent les villes).

Méthodes de résolutions du problème

Les algorithmes pour résoudre le PVC peuvent être répartis en deux classes :

• les algorithmes déterministes qui trouvent la solution optimale
• les algorithmes d'approximation qui fournissent une solution presque optimale

Algorithmes déterministes

Les algorithmes déterministes permettent de trouver la solution optimale, mais leur compléxité est de l'ordre du factoriel. Les algorithmes les plus efficaces sont «cutting-plane»[3] et «facet-finding»[4]. Ces algorithmes complexes ont un code de l'ordre de 10 000 lignes. De plus, ils sont très gourmants en puissance de calcul. Par exemple, il a fallut 27 heures à un puissant super-calculateur pour trouver la solution optimale pour 2392 villes.

Algorithmes d'approximation

Les algorithmes d'approximation permettent de trouver une solution dont le coût est proche du coût de la solution optimale. Ils ont l'avantage de permettre en un temps raisonnable de trouver une solution. De ce fait, ils ne sont à utiliser que dans les cas où une solution aprochée est acceptable.