Problème du voyageur de commerce

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Le problème de voyageur de commerce ː calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes).

En informatique, le problème du voyageur de commerce est un problème d'optimisation qui, étant donné une liste de villes, et des distances entre toutes les paires de villes, détermine un plus court chemin qui visite chaque ville une et une seule fois et qui termine dans la ville de départ.

Malgré la simplicité de son énoncé, il s'agit d'un problème d'optimisation pour lequel on ne connait pas d'algorithme permettant de trouver une solution exacte rapidement dans tous les cas. Plus précisément, on ne connait pas d'algorithme en temps polynomial, et sa version décisionnelle (pour une distance D, existe-t-il un chemin plus court que D passant par toutes les villes et qui termine dans la ville de départ ?) est un problème NP-complet, ce qui est un indice de sa difficulté.

C'est un problème algorithmique célèbre, qui a généré beaucoup de recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité. Il présente de nombreuses applications que ce soit en planification et en logistique, ou bien dans des domaines plus éloignés comme la génétique (en remplaçant les villes par des gènes et la distance par la similarité).

Description du problème[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. Formellement, une instance est un graphe complet avec un ensemble de sommets, un ensemble d'arêtes et une fonction de coût sur les arcs. Le problème est de trouver le plus court cycle hamiltonien dans le graphe G.

Exemple[modifier | modifier le code]

On considère la liste des villes A, B, C, D et les distances données par le dessin c-dessous à gauche. Un premier chemin qui part de A, revient en A et qui visite toutes les villes est ABDCA. Un chemin plus court est ACBDA. Le chemin ACBDA est optimal.


Instance du problème du voyageur de commerce
Le chemin ABDCA de longueur 4+2+5+3 = 14 km.
Le chemin ACBDA est un chemin le plus court qui part de A, revient A et passe par toutes les villes. Il est de longueur 3+1+2+1=7 km.

Explosion combinatoire[modifier | modifier le code]

Nombre de chemins candidats en fonction du nombre de villes
nombre de villes Nombre de chemins candidats
3 1
4 3
5 12
6 60
7 360
8 2520
9 20 160
10 181 440
15 43 589 145 600
20 6×1016
71 5,9×10102

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

Pour un ensemble de points, il existe au total chemins possibles (factorielle de ). Le point de départ ne changeant pas la longueur du chemin, on peut choisir celui-ci de façon arbitraire, on a ainsi chemins différents. Enfin, chaque chemin pouvant être parcouru dans deux sens et les deux possibilités ayant la même longueur, on peut diviser ce nombre par deux. Par exemple, si on nomme les points, , les chemins ont tous la même longueur, seul le point de départ et le sens de parcours change. On a donc chemins candidats à considérer[1].

Par exemple, pour 71 villes, le nombre de chemins candidats est supérieur à 5×1080 qui est environ le nombre d'atomes dans l'univers connu[réf. nécessaire].

Variantes[modifier | modifier le code]

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.

Aussi, 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).

Résolution exacte[modifier | modifier le code]

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

Le problème de décision associé au problème d'optimisation du voyageur de commerce est un problème NP-complet[2].

Algorithmes[modifier | modifier le code]

Une approche de résolution naïve mais qui donne un résultat exact est l'énumération de tous les chemins possibles par recherche exhaustive. La complexité en temps de cet algorithme est en O(n!), ce qui devient vite impraticable même pour de petites instances. Par exemple, si le calcul d'un chemin prend une microseconde, alors le calcul de tous les chemins pour 10 points est de 181 440 microsecondes soit 0,18 seconde mais pour 15 points, cela représente déjà 43 589 145 600 microsecondes soit un peu plus de 12 heures et pour 20 points de 6×1016 microsecondes soit presque deux millénaires (1 927 années).

Held et Karp ont montré que la programmation dynamique permettait de résoudre le problème en O(n22n)[3].

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[4]), moyennant éventuellement un temps de calcul important.

Approximation[modifier | modifier le code]

Dans certains cas des algorithmes d'approximation existent, 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[5]. Dans ce cas le problème est APX-difficile même avec des poids 1 ou 2[6].

Formulation par optimisation linéaire[modifier | modifier le code]

Dans cette partie on donne une formalisation en terme d'optimisation linéaire en nombres entiers du problème. On note , l'ensemble des arêtes sortant de l'ensemble de sommet S.

La relaxation de ce programme pour un problème d'optimisation linéaire (c'est-à-dire sans les contraintes d'intégralité), est appelée relaxation de Held et Karp[7] ou subtour LP. Cette relaxation a un nombre exponentiel de contraintes, mais peut-être résolu en temps polynomial en résolvant le problème de séparation, qui se révèle être le calcul d'une coupe minimum[8]. Il est conjecturé que la relaxation de Held et Karp a un trou d'intégralité (integrality gap) de 4/3[7].

Cas euclidien[modifier | modifier le code]

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[9] et Joseph S. B. Mitchell[10], et leur a valu le prix Gödel en 2010[11].

Heuristiques[modifier | modifier le code]

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[12] 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[13].

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 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 puis on cherche la position d'insertion et de cycle qui minimise l'augmentation totale des coûts :

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

Histoire et importance[modifier | modifier le code]

Origines et cas particuliers[modifier | modifier le code]

Le principe d'un tel voyage est décrit dès 1832, dans un écrit d'un commis-voyageur et des itinéraires efficaces étaient référencés dans des guides[14]. Plusieurs problèmes anciens peuvent être vus comme des cas particuliers du problème ; par exemple, en 1856, William Rowan Hamilton s'était intéressé à un problème géométrique de ce type sur un dodécaèdre, d'ailleurs le terme cycle hamiltonien désigne un cycle passant par tous les sommets dans un graphe[14].

Terminologie[modifier | modifier le code]

Le terme problème du voyageur de commerce, vient de la traduction de l'anglais américain Traveling salesman problem, qui est apparu dans les années 1930 ou 40, sans doute à l'université Princeton où plusieurs chercheurs s'y intéressaient[14]. C'est aussi à cette période que le problème est formulé indépendamment dans plusieurs communautés de chercheurs, notamment autour de Karl Menger[14].

Développements[modifier | modifier le code]

Le problème a alors intéressé une plus large communauté et a notamment été à l'origine de la découverte de plusieurs techniques, comme l'optimisation linéaire mixte (mixed integer programming), et la méthode de séparation et évaluation (branch-and-bound)[14].

En 1972, Richard Karp montra que le problème de décision associé était est NP-complet[15].

Importance dans l'enseignement et la recherche[modifier | modifier le code]

Le voyageur de commerce est aujourd'hui l'un des problèmes algorithmiques ayant le plus été étudiés[14]. De plus, grâce à la simplicité de son énoncé, il est souvent utilisé pour introduire l'algorithmique, d'où une relative célébrité[14].

Applications[modifier | modifier le code]

Le problème du voyageur du commerce a de nombreuses applications[14], et a d'ailleurs été motivé par des problèmes concrets, par exemple le parcours des bus scolaires[16].

Un premier type d'application classique est bien sûr dans la logistique, par exemple pour la poste, le distribution de repas à domicile, inspection d'installation etc[16]. On peut aussi optimiser les mouvements de machines, par exemple, pour minimiser le temps total que met une fraiseuse à commande numérique pour percer n points dans une plaque de tôle[17], ou minimiser les mouvements des grands télescopes (qui sont très lents)[16].

On peut citer des applications plus surprenantes, par exemple : en biologie, le problème aide au séquençage du génome (pour relier des petits fragments en des chaînes plus grandes), et en production il est utilisé pour le test des circuits imprimés[16].

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. Patrick Siarry, Métaheuristiques: Recuits simulé, recherche avec tabous, recherche à voisinages variables, méthodes GRASP, algorithmes évolutionnaires, fourmis artificielles, essaims particulaires et autres méthodes d'optimisation, Eyrolles, (ISBN 978-2-212-26621-4, lire en ligne), p. 182
  2. 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, (lire en ligne), p. 85-103.
  3. (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
  4. Voir par exemple le site de l'université Georgia Tech
  5. 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,‎
  6. Christos H. Papadimitriou et Mihalis Yannakakis, « The traveling salesman problem with distances one and two », Mathematics of Operations Research, INFORMS, vol. 18, no 1,‎ , p. 1--11
  7. a et b Robert D. Carr et Santosh Vempala, « On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems », Math. Program., vol. 100, no 3,‎ , p. 569-587
  8. Rene Beier, « The Traveling Salesman Problem, the Subtour LP, and the Held-Karp Lower Bound », sur MPII.
  9. Sanjeev Arora, « Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems », Journal of the ACM, vol. 45, no 5,‎ , p. 753–782 (DOI 10.1145/290179.290180)
  10. 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,‎ , p. 1298–1309 (ISSN 1095-7111, DOI 10.1137/S0097539796309764)
  11. « The Gödel Prize 2010, Laudatio for S. Arora and J.S.B. Mitchell », sur EATCS.
  12. (en) S. Lin and B. W. Kernighan (1973). An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Res. 21, 498-516.
  13. (en) J. H. Holland: Adaptation In Natural And Artificial Systems, University of Michigan Press (1975)
  14. a, b, c, d, e, f, g et h David L. Applegate, Robert E. Bixby, Václav Chvátal et William J. Cook, « The Problem », dans The traveling Salesman Problem: A Computational Study, Princeton University Press, , chap. 1.
  15. Modèle:Reducibility Karp 1972
  16. a, b, c et d David L. Applegate, Robert E. Bixby, Václav Chvátal et William J. Cook, « Applications », dans The traveling Salesman Problem: A Computational Study, Princeton University Press, , chap. 2.
  17. (en) William Timothy Gowers (dir.), « The Influence of Mathematics:The Mathematics of Algorithm Design », dans The Princeton companion to Mathematics, Princeton et Oxford, Princeton University Press, (ISBN 978-0-691-11880-2), chap. VII.5, p. 871-878

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]