Solveur TSP en Ligne

Pseudocode

Il n'existe pas d'algorithme exact rapide pour le problème du voyageur de commerce, la réponse pratique tient donc en deux étapes: construire vite un circuit correct, puis l'améliorer localement jusqu'à ce que plus rien ne progresse.

// Étape 1: plus proche voisin, construit un circuit en O(n^2)
circuit = [depart]
tant qu une ville reste non visitee:
    suivante = ville non visitee la plus proche de circuit.derniere
    circuit.ajouter(suivante)
circuit.ajouter(depart)          // fermer la boucle

// Étape 2: 2-opt, supprime les croisements
repeter jusqu a absence d amelioration:
    pour chaque paire d aretes (a,b) et (c,d) du circuit:
        si dist(a,c) + dist(b,d) < dist(a,b) + dist(c,d):
            inverser le segment entre b et c

// Exact, pour petit n: programmation dynamique de Held-Karp
dp[S][j] = min sur k dans S\{j} de dp[S\{j}][k] + dist(k, j)

Le mouvement 2-opt gagne à être compris géométriquement. Si deux arêtes d'un circuit se croisent, échanger leurs extrémités et inverser le segment intermédiaire raccourcit toujours le circuit, par l'inégalité triangulaire. 2-opt est donc littéralement l'opération qui défait les nœuds d'une boucle de ficelle.

Exemple détaillé, étape par étape

Applique le plus proche voisin puis 2-opt à quatre villes placées aux coins d'un rectangle, là où le choix glouton peut démontrablement se tromper.

Graphe d'exemple: Villes A(0,0), B(0,3), C(4,3), D(4,0). Distances: A-B 3, B-C 4, C-D 3, A-D 4, et les deux diagonales A-C et B-D valent 5.

1. Plus proche voisin depuis A. La ville la plus proche de A est B, à 3. On passe à B.
2. Depuis B. Restent non visitées C à 4 et D à 5. On prend C.
3. Depuis C. Il ne reste que D, à 3. On la prend, puis on referme vers A pour 4.
4. Résultat glouton. Le circuit A vers B vers C vers D vers A coûte 3 + 4 + 3 + 4 = 14. Il se trouve qu'il est optimal ici, alors perturbons-le: suppose que l'heuristique ait produit A vers C vers B vers D vers A, coûtant 5 + 4 + 5 + 4 = 18, un circuit dont les arêtes se croisent.
5. Réparation par 2-opt. Examine les arêtes A-C et B-D. Elles contribuent actuellement 5 + 5 = 10. Les reconnecter en A-B et C-D donne 3 + 3 = 6, une amélioration de 4, on inverse donc le segment entre C et B. Le circuit devient A vers B vers C vers D vers A pour 14, et aucun autre mouvement 2-opt n'aide.

Le circuit optimal est le périmètre du rectangle à 14, et non l'un des circuits à diagonales croisées à 18. C'est toute l'histoire des heuristiques du TSP en miniature: une passe constructive rapide s'approche du but, et la recherche locale supprime les croisements introduits par le choix glouton.

Complexité et son origine

Temps: O(n^2) heuristique, O(n^2 · 2^n) exact · Espace: O(n^2) heuristique, O(n · 2^n) exact

Le plus proche voisin parcourt toutes les villes restantes à chacune des n étapes, d'où O(n au carré). Chaque passe de 2-opt teste les O(n au carré) paires d'arêtes et se répète tant qu'il y a amélioration, ce qui est rapide en pratique mais sans borne utile dans le pire cas. Held-Karp est exact et remplit une table indexée par sous-ensemble et extrémité: il y a 2 puissance n sous-ensembles fois n extrémités, et chaque entrée coûte O(n), d'où O(n au carré fois 2 puissance n) en temps et O(n fois 2 puissance n) en mémoire. C'est un mur net autour de n = 20 à 25, puisque 2 puissance 25 fois 25 dépasse déjà le milliard d'entrées. La force brute sur toutes les permutations est bien pire, en O(n factorielle).

Quand utiliser Problème du Voyageur de Commerce, et quand l'éviter

La bonne méthode dépend presque entièrement du nombre de villes et du fait que tu exiges ou non un optimum démontrable.

Pièges fréquents

• Attendre une réponse exacte à grande échelle. Le TSP est NP-difficile. Aucun algorithme connu ne résout exactement 1 000 villes en temps raisonnable, et en trouver un trancherait P contre NP. Si un outil prétend donner rapidement l'optimum exact sur une grande instance, il renvoie un circuit heuristique.
• Se fier au seul plus proche voisin. La construction gloutonne dépasse typiquement l'optimum de 25 pour cent et peut être arbitrairement mauvaise dans le pire cas, car les dernières villes restantes imposent des arêtes très longues. Fais toujours suivre d'une recherche locale.
• Appliquer Christofides à des distances non métriques. Sa garantie d'approximation à 1,5 repose sur l'inégalité triangulaire. Avec des sens uniques, des coûts asymétriques ou des trajets interdits, la borne ne tient tout simplement pas.
• Confondre TSP et problème de tournées de véhicules. Le TSP, c'est un véhicule, sans capacité ni fenêtre horaire. Dès qu'apparaissent une flotte ou des limites de charge, il faut des méthodes VRP ou CVRP; un circuit TSP découpé en morceaux n'est pas une solution VRP valide.
• Oublier que la ville de départ est sans importance. Un circuit TSP est un cycle, le faire pivoter ne change donc rien. Les implémentations qui traitent le départ comme significatif gaspillent du travail et peuvent annoncer des coûts différents pour des circuits identiques.

Questions fréquentes

Quel est le problème du voyageur de commerce?

Étant donné un ensemble de villes et la distance entre chaque paire, le TSP demande la route la plus courte visitant chaque ville exactement une fois et revenant au point de départ. C'est l'un des problèmes les plus étudiés de l'optimisation combinatoire et il est NP-difficile, ce qui signifie qu'aucun algorithme exact en temps polynomial n'est connu.

Pourquoi le TSP est-il si difficile à résoudre?

Le nombre de circuits distincts croît comme (n-1)!/2, si bien que 20 villes autorisent déjà environ 60 millions de milliards de circuits. Aucun algorithme connu n'évite un travail exponentiel dans le pire cas. La meilleure méthode exacte, la programmation dynamique de Held-Karp, tourne en O(n au carré fois 2 puissance n) et devient impraticable au-delà d'environ 25 villes.

Quel est le meilleur algorithme pour le TSP?

Cela dépend de la taille. En dessous d'une vingtaine de villes, Held-Karp donne l'optimum exact. Pour des instances métriques, Christofides garantit un circuit à moins de 1,5 fois l'optimum. Pour de grandes instances réelles, Lin-Kernighan ou le plus proche voisin suivi de 2-opt donnent en quelques secondes des circuits à quelques pour cent de l'optimum.

Que fait réellement 2-opt?

Il retire à répétition deux arêtes du circuit et reconnecte les deux chemins obtenus dans l'autre sens, en conservant le changement si le circuit raccourcit. Géométriquement il supprime les croisements: dès que deux arêtes d'un circuit se croisent, la reconnexion sans croisement est plus courte par l'inégalité triangulaire.

Quelle est la différence entre le TSP et le problème de tournées de véhicules?

Le TSP achemine un seul véhicule à travers toutes les villes sans autre contrainte que de visiter chacune une fois. Le VRP achemine une flotte depuis un dépôt, généralement avec des limites de capacité et souvent des fenêtres horaires et des services de conducteurs. Le TSP est le cas particulier du VRP à un véhicule et capacité illimitée.