Le problème du voyageur de commerce expliqué
Donnez à un voyageur de commerce une liste de villes et demandez-lui le trajet le plus court qui visite chacune d'elles une fois et le ramène chez lui. Tout le monde peut vérifier un itinéraire proposé, et tout le monde peut en améliorer un mauvais à l'œil, mais personne ne connaît de méthode rapide qui trouve toujours le meilleur. Le problème du voyageur de commerce est devenu l'exemple type d'un problème difficile, et les méthodes inventées pour l'attaquer planifient aujourd'hui des livraisons, percent des circuits imprimés et assemblent des génomes.
Le problème
Une tournée visite chaque ville exactement une fois et se termine là où elle a commencé ; sa longueur est la somme des distances parcourues. Il s'agit de trouver la tournée la plus courte. Dans la version proposée ici, les distances sont des lignes droites sur une carte, donc aller de A à C n'est jamais plus long que passer par B : c'est le problème du voyageur de commerce métrique. Le mathématicien Karl Menger a évoqué cette énigme vers 1930, et le nom s'est répandu dans les décennies suivantes, lorsque des mathématiciens de la RAND Corporation s'y sont intéressés.
L'explosion des itinéraires
Fixez la ville de départ. Il y a n − 1 choix pour la ville suivante, n − 2 pour celle d'après, et ainsi de suite, et chaque tournée peut être parcourue dans deux sens : il y a donc (n − 1)! / 2 tournées. Pour 10 villes, cela fait 181 440, un jeu d'enfant pour un ordinateur. Pour 20, c'est environ 6 × 10¹⁶, et pour 70, cela dépasse le nombre d'atomes de l'univers observable. Des ordinateurs plus rapides n'y changent pas grand-chose : chaque ville supplémentaire multiplie le travail par environ n.
NP-difficile
En 1972, Richard Karp a montré que la question de savoir si un graphe possède un circuit passant par tous ses sommets, un cycle hamiltonien, appartient à une famille de problèmes NP-complets tous aussi difficiles les uns que les autres. Le problème du voyageur de commerce la contient, il est donc NP-difficile. Une méthode rapide pour le résoudre donnerait des méthodes rapides pour des milliers d'autres problèmes d'ordonnancement, de logistique et de cryptographie. L'existence d'une telle méthode est la question P contre NP, l'un des problèmes du prix du millénaire.
Une méthode exacte : Held–Karp
En 1962, Michael Held et Richard Karp, et indépendamment Richard Bellman, ont utilisé la programmation dynamique. Pour chaque ensemble S de villes et chaque ville j de S, on calcule le plus court chemin qui part de la ville de départ, visite exactement les villes de S et se termine en j. Chaque valeur se déduit des valeurs pour S privé de j, de sorte que la table se remplit des petits ensembles vers les grands, et la tournée la plus courte apparaît à la fin. Il faut environ n² · 2ⁿ étapes au lieu de n!, ce qui, pour 30 villes, fait la différence entre quelques minutes et l'âge de l'univers, mais cela croît toujours exponentiellement.
Règles de construction rapides
Le plus proche voisin va toujours à la ville la plus proche pas encore visitée. C'est simple et rapide, mais il a tendance à laisser de côté quelques villes qu'il faut ensuite aller chercher par de longs détours à la fin, si bien que ses tournées sont typiquement environ 25 % plus longues que la meilleure. Les méthodes d'insertion, elles, gardent une boucle fermée et y ajoutent les villes restantes une à une, là où elles coûtent le moins. En 1976, Nicos Christofides a trouvé une construction qui garantit au plus 1,5 fois l'optimum sur toute carte métrique, une borne restée presque imbattue pendant plus de quarante ans.
Améliorer une tournée : 2-opt
La recherche locale part d'une tournée quelconque et y apporte sans cesse de petites modifications qui la raccourcissent. Le coup classique, 2-opt, retire deux arêtes et reconnecte les deux morceaux dans l'autre sens, ce qui inverse la portion située entre elles. Chaque fois que deux arêtes se croisent, ce coup les décroise et économise de la longueur ; une tournée que 2-opt ne peut plus améliorer ne se croise donc jamais elle-même. Sur des cartes aléatoires, les tournées 2-opt sont typiquement environ 5 % au-dessus de l'optimum. Des coups plus puissants qui échangent trois arêtes, ou la méthode à profondeur variable de Lin et Kernighan de 1973, s'en approchent encore davantage.
Le recuit simulé
La recherche locale peut rester bloquée sur une tournée où chaque coup isolé l'aggrave, alors qu'il existe une tournée bien meilleure. Le recuit simulé, appliqué à ce problème par Scott Kirkpatrick, Daniel Gelatt et Mario Vecchi en 1983, s'inspire de la métallurgie : il accepte un coup moins bon avec une probabilité qui dépend d'une température, élevée au départ puis abaissée lentement. Au début, la tournée erre librement ; à la fin, seules les améliorations sont acceptées. Avec un refroidissement suffisamment lent, il trouve de façon fiable de très bonnes tournées.
À vous d'explorer
Ouvrez la démo du voyageur de commerce pour placer jusqu'à 200 villes au hasard, sur un cercle, en groupes, sur une grille ou là où vous cliquez. Regardez le plus proche voisin délaisser ses dernières villes, voyez 2-opt démêler chaque croisement, suivez la température du recuit simulé à mesure qu'il refroidit, et laissez Held–Karp prouver la tournée la plus courte jusqu'à 12 villes. Tout comparer lance chaque méthode sur la même carte et montre de combien chaque tournée dépasse la plus courte trouvée.
Questions fréquemment posées
Où utilise-t-on le problème du voyageur de commerce ?
Partout où quelque chose doit visiter de nombreux endroits dans un ordre efficace : les tournées de livraison et de collecte, le trajet d'un foret ou d'un laser sur un circuit imprimé, l'ordre dans lequel un télescope observe les étoiles, l'ordre de préparation des commandes dans un entrepôt et, avec d'autres distances, l'ordre des fragments lors de l'assemblage d'une séquence d'ADN.
Quel est le plus grand problème jamais résolu exactement ?
En 1954, George Dantzig, Ray Fulkerson et Selmer Johnson ont prouvé la tournée la plus courte passant par 49 villes des États-Unis. En 2006, le solveur Concorde de David Applegate, Robert Bixby, Vašek Chvátal et William Cook a prouvé la tournée optimale passant par 85 900 points issus de la conception d'une puce, après des années de temps de calcul.
La tournée la plus courte est-elle toujours sans croisement ?
Oui, sur une carte plane avec des distances en ligne droite. Si deux arêtes se croisaient, les remplacer par deux côtés du quadrilatère qu'elles forment raccourcirait la tournée ; une tournée qui se croise ne peut donc pas être la plus courte.
Les heuristiques donnent-elles toujours la même tournée ?
Le plus proche voisin, l'insertion la moins chère et 2-opt, tels qu'ils sont utilisés ici, sont déterministes : sur les mêmes villes, ils donnent la même tournée. Le recuit simulé part d'une tournée aléatoire et fait des coups aléatoires, si bien que deux exécutions peuvent aboutir à des tournées différentes, généralement de longueur presque identique.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Ouvrir la démo du voyageur de commerce