Longueur de la tournée
Plus courte trouvée
Étapes
Tournées possibles
  • Tournée
  • Plus courte trouvée
  • Départ

Méthode Longueur Écart à la plus courte Étapes
- - -
- - -
- - -
- - -
- - -

En savoir plus sur le problème du voyageur de commerce

Problème du voyageur de commerce

Un voyageur de commerce doit visiter chaque ville une fois et rentrer chez lui. Dans quel ordre le trajet est-il le plus court ? La question est simple à poser mais, à mesure que le nombre de villes augmente, il devient sans espoir d'y répondre en essayant tous les ordres : 30 villes permettent déjà environ 4,4 × 10³⁰ tournées. Dispersez des villes sur une carte ou placez les vôtres d'un clic, puis regardez des règles empiriques rapides, des améliorations astucieuses et une méthode exacte construire leurs tournées pas à pas, et voyez à quel point les méthodes rapides s'approchent du but. Choisissez la disposition des villes et leur nombre, choisissez une méthode et appuyez sur Résoudre pour la voir construire une tournée étape par étape, ou sur Pas à pas pour avancer d'un coup à la fois. Cliquez sur la carte pour ajouter une ville, ou sur une ville pour la retirer. Tout comparer lance chaque méthode sur les mêmes villes et montre l'écart de chacune par rapport à la plus courte tournée trouvée. La ville rouge est le point de départ du voyage.

Comment ça marche

  1. Choisissez une disposition et le nombre de villes, ou cliquez sur la carte pour placer les vôtres et sur une ville pour la retirer.
  2. Choisissez une méthode et appuyez sur Résoudre pour la suivre étape par étape, ou sur Pas à pas pour avancer d'un coup à la fois.
  3. Appuyez sur Tout comparer pour lancer chaque méthode sur les mêmes villes et lisez de combien chaque tournée dépasse la plus courte trouvée.

Pourquoi c'est difficile

Avec n villes, il existe (n − 1)! / 2 tournées différentes, car peu importe où l'on part et dans quel sens on tourne. Cela fait 12 pour 5 villes, 181 440 pour 10 et environ 6 × 10¹⁶ pour 20. On ne connaît aucune méthode qui trouve la tournée la plus courte pour toute carte en un temps qui ne croît que comme une puissance de n : le problème est NP-difficile. La meilleure méthode exacte de cette application, la programmation dynamique de Held–Karp datant de 1962, demande encore environ n² · 2ⁿ étapes ; elle est donc limitée ici à 12 villes.

De bonnes tournées, vite

En pratique, on trouve rapidement des tournées presque optimales. Le plus proche voisin va toujours à la ville non visitée la plus proche et finit typiquement environ 25 % au-dessus de la meilleure tournée. L'insertion la moins chère fait grandir une boucle en y ajoutant la ville qui l'allonge le moins. 2-opt part d'une tournée quelconque et remplace sans cesse deux arêtes par deux plus courtes, ce qui supprime tous les croisements et s'approche en général à environ 5 % près. Le recuit simulé fait des coups 2-opt aléatoires et, tant qu'il est encore « chaud », en accepte certains qui allongent la tournée, de sorte qu'il peut sortir des impasses avant de se stabiliser.

Questions fréquemment posées

Existe-t-il une formule pour l'itinéraire le plus court ?

Non. La tournée la plus courte dépend des positions exactes de toutes les villes, et aucune méthode connue ne la trouve pour toute carte sans, dans le pire des cas, une quantité de travail qui croît exponentiellement. Pour quelques centaines ou milliers de villes, des solveurs exacts spécialisés comme Concorde prouvent tout de même des tournées optimales en combinant la programmation linéaire et un élagage astucieux, et la plus grande instance résolue exactement à ce jour compte 85 900 points.

Pourquoi 2-opt supprime-t-il tous les croisements ?

Si deux arêtes d'une tournée se croisent, les quatre villes qu'elles relient forment un quadrilatère dont les diagonales sont ces deux arêtes. Les remplacer par deux côtés opposés du quadrilatère est toujours plus court, d'après l'inégalité triangulaire, et inverse la portion de tournée située entre elles. 2-opt continue de faire de tels échanges jusqu'à ce qu'aucun n'aide plus ; sa tournée finale ne se croise donc jamais elle-même.

Qu'est-ce que la température dans le recuit simulé ?

Elle règle la facilité avec laquelle la méthode accepte un coup qui allonge la tournée. Un coup qui ajoute d à la longueur est accepté avec la probabilité e^(−d/T). À haute température T, presque tout passe, ce qui permet à la tournée d'échapper à un mauvais agencement ; quand T baisse, la méthode devient gloutonne et se stabilise. Le nom vient du refroidissement lent d'un métal, qui permet à ses atomes de trouver un arrangement de basse énergie.

Pourquoi la méthode exacte est-elle limitée à 12 villes ?

Held–Karp mémorise le plus court chemin pour chaque sous-ensemble de villes et chaque dernière ville possible, soit environ n · 2ⁿ nombres, et calcule chacun avec n comparaisons. Pour 12 villes, cela fait quelques centaines de milliers d'étapes ; pour 25 villes, ce seraient des milliards. C'est tout de même énormément plus rapide que d'essayer les (n − 1)! / 2 tournées : pour 12 villes, il y en aurait près de 20 millions.

Des données sont-elles envoyées à un serveur ?

Non. Les villes et les cinq méthodes s'exécutent dans votre navigateur. Les villes que vous placez d'un clic restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur