Problème du voyageur de commerce

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le problème du voyageur de commerce est un problème mathématique qui consiste, étant donné un ensemble de villes séparées par des distances données, à trouver le plus court chemin qui relie toutes les villes. Il s'agit d'un problème d'optimisation pour lequel on ne connait pas d'algorithme permettant de trouver une solution exacte en un temps polynomial. De plus, la version décisionnelle de l'énoncé (pour une distance D, existe-t-il un chemin plus court que D passant par toutes les villes ?) est connue comme étant un problème NP-complet.

Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ?

Approche simplifiée[modifier | modifier le code]

L'énoncé du problème du voyageur de commerce est le suivant : étant donné n points (des « 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 est plus compliqué qu'il n'y paraît ; on ne connaît pas de méthode de résolution permettant d'obtenir des solutions exactes en un temps raisonnable pour de grandes instances (grand nombre de villes) du problème. Pour ces grandes instances, on devra donc souvent se contenter de solutions approchées, car on se retrouve face à une explosion combinatoire : le nombre de chemins possibles passant par 71 villes est déjà un nombre d'une longueur de 100 chiffres, sachant qu'un nombre d'une longueur de 80 chiffres permettrait déjà de représenter le nombre d'atomes dans tout l'univers connu.

Ce problème peut servir tel quel à l'optimisation de trajectoires de machines-outils : par exemple, pour minimiser le temps total que met une fraiseuse à commande numérique pour percer n points dans une plaque de tôle. Il se posait également pour optimiser la vitesse de tracé d'une structure (en BTP, par exemple) par une table traçante à l'époque où ces périphériques étaient mécaniques, et non électroniques comme aujourd'hui.

Plus généralement, divers problèmes de recherche opérationnelle se ramènent au voyageur de commerce. Un voyageur de commerce peu scrupuleux serait intéressé par le double problème du chemin le plus court (pour son trajet réel) et du chemin le plus long (pour sa note de frais).

Formalisation et variantes[modifier | modifier le code]

Voici un énoncé plus formel du problème du voyageur de commerce sous forme constatée de problème d'optimisation combinatoire.

Soit un graphe complet G = (V,A,\omega) avec V un ensemble de sommets, A un ensemble d'arêtes et \omega une fonction de coût sur les arcs. Le problème est de trouver le plus court cycle hamiltonien dans le graphe.

On présente ensuite quelques variantes.

Orientation[modifier | modifier le code]

Rien n'interdit au graphe donné en entrée d'être orienté. Dans ce cas, on considère qu'un chemin existe dans un sens mais pas dans l'autre (exemple : routes à sens unique).

Asymétrie[modifier | modifier le code]

On parle parfois de problème symétrique ou asymétrique.

Problème du voyageur de commerce symétrique :

Étant donnés un ensemble de n nœuds et de distances pour chaque paire de nœuds, trouver un cycle de longueur minimale qui visite chaque nœud exactement une fois. Pour i et j deux nœuds d'une arête, la distance de i à j est la même que celle de j à i.

Problème du voyageur de commerce asymétrique :

Étant donnés un ensemble de n nœuds et de distances pour chaque paire de nœuds, trouver un cycle de longueur minimale qui visite chaque nœud exactement une fois. Cette fois-ci la distance entre deux nœuds i et j d'une arête n'est pas forcément la même qu'on aille de i à j ou bien de j à i.

Complexité et résolution exacte[modifier | modifier le code]

Complexité du problème[modifier | modifier le code]

Le problème du voyageur de commerce est un problème NP-difficile et le problème de décision associé est un problème NP-complet[1].

Algorithmes[modifier | modifier le code]

L'approche de résolution la plus naïve serait l'énumération de tous les chemins possibles, la complexité en temps de cet algorithme est en O(n!), ce qui devient vite impraticable même pour de petites instances. Held et Karp ont montré que la programmation dynamique permettait de résoudre le problème en O(n22n)[2].

Les méthodes d'optimisation linéaire sont à ce jour parmi les plus efficaces pour la résolution du problème de voyageur de commerce et permettent[N 1] désormais de résoudre des problèmes de grande taille (à l'échelle d'un pays[3]), moyennant éventuellement un temps de calcul important.

Complexité et résolution approchée[modifier | modifier le code]

Algorithmes d'approximation[modifier | modifier le code]

Dans certains cas des algorithmes d'approximation existent, par exemple l'algorithme de Christofides est une approximation de facteur 3/2 dans le cas métrique (c'est-à-dire lorsque les poids des arêtes respectent l'inégalité triangulaire)[4].

Dans le cas d'une métrique euclidienne, il existe un schéma d'approximation en temps polynomial. Il a été découvert indépendamment par Sanjeev Arora[5] et Joseph S. B. Mitchell (en)[6], et leur a valu le prix Gödel en 2010[7].

Heuristiques générales[modifier | modifier le code]

Lorsque le temps alloué à la résolution est faible on utilisera plutôt des heuristiques tel que l'algorithme de Lin-Kernighan[8] et des méta-heuristiques. Toutefois les méthodes heuristiques ne donnent en général aucune preuve justifiant qu'elles obtiennent la meilleure solution, et même si elles peuvent en pratique être très bonnes, en toute généralité elles ne fournissent qu'une solution approchée.

Les algorithmes génétiques peuvent aussi être adaptés au problème du voyageur de commerce. L'idée a été proposée la première fois par John Holland au début des années 1970[9].

L'algorithme 2-opt est une heuristique de recherche locale.

Heuristiques gloutonnes[modifier | modifier le code]

Pour le problème du voyageur de commerce, une heuristique gloutonne construit une seule solution, par une suite de décisions définitives sans retour arrière, parmi ces méthodes on cite le plus proche voisin, la plus proche insertion, la plus lointaine insertion et la meilleure insertion.

Dans la méthode du plus proche voisin, on part d'un sommet quelconque et à chacune des (n-1) itérations on relie le dernier sommet atteint au sommet le plus proche au sens coût, puis on relie finalement le dernier sommet au premier sommet choisi.

Dans les méthodes d'insertion, on part d'un cycle réduit à une boucle au départ, à chaque itération on choisit un sommet libre j puis on cherche la position d'insertion i et j de cycle qui minimise l'augmentation totale des coûts :

  • dans la plus lointaine insertion j est le sommet libre le plus loin du cycle au sens des coûts;
  • dans la plus proche insertion j est le plus proche du cycle;
  • enfin dans la meilleure insertion on teste tous les sommets j non encore insérés et on choisit celui qui donne la plus faible augmentation du coût.

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. En général par le biais de la méthode du branch and cut.

Références[modifier | modifier le code]

  1. Présent notamment dans la liste des 21 problèmes NP-complets de Karp : (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Complexity of Computer Computations, Plenum,‎ 1972 (lire en ligne), p. 85-103.
  2. (en) Held, M.; Karp, R. M. (1962), "A Dynamic Programming Approach to Sequencing Problems", Journal of the Society for Industrial and Applied Mathematics 10 (1): 196–210
  3. Voir par exemple le site de l'université Georgia Tech
  4. Nicos Christofides, « Worst-case analysis of a new heuristic for the travelling salesman problem », Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh,‎ 1976
  5. Sanjeev Arora, « Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems », Journal of the ACM, vol. 45, no 5,‎ 1998, p. 753–782 (DOI 10.1145/290179.290180)
  6. Joseph S. B. Mitchell, « Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems », SIAM Journal on Computing, vol. 28, no 4,‎ 1999, p. 1298–1309 (ISSN 1095-7111, DOI 10.1137/S0097539796309764)
  7. « The Gödel Prize 2010, Laudatio for S. Arora and J.S.B. Mitchell », sur EATCS.
  8. (en) S. Lin and B. W. Kernighan (1973). An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Res. 21, 498-516.
  9. (en) J. H. Holland: Adaptation In Natural And Artificial Systems, University of Michigan Press (1975)

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]