Solveur du Voyageur de Commerce (TSP)

Solveur du Voyageur de Commerce (TSP)

Le Solveur du Voyageur de Commerce TSP est un calculateur pratique et éducatif pour le classique problème du voyageur de commerce (TSP) : étant donné un ensemble de villes et de distances par paires, trouver le parcours le plus court possible qui visite chaque ville exactement une fois et revient au point de départ. Ce solveur accepte soit des coordonnées planes, soit une matrice de distance personnalisée, sélectionne automatiquement le meilleur algorithme en fonction de la taille du problème et affiche le parcours résultant sous forme de carte SVG animée.

Qu'est-ce que le problème du voyageur de commerce ?

Formellement, étant donné un graphe complet pondéré G = (V, E) avec un ensemble de sommets V = {1, 2, ..., n} et des poids d'arêtes d(i, j), le TSP recherche une permutation π des sommets qui minimise :

Le dernier terme ferme la boucle. Le TSP est l'un des problèmes les plus anciens et les plus étudiés en optimisation combinatoire — il est NP-difficile dans le cas général, ce qui signifie qu'aucun algorithme connu ne résout toutes les instances en temps polynomial. Malgré cela, il apparaît dans d'innombrables applications du monde réel : logistique des véhicules, perçage de PCB, séquençage d'ADN, itinéraires de préparation de commandes en entrepôt, programmes d'observation astronomique et même distribution postale rurale.

Comment fonctionne ce solveur

Programmation dynamique de Held–Karp (Exacte)

Pour les petites instances (jusqu'à 12 villes), le solveur calcule le parcours prouvé optimal à l'aide de l'algorithme Held–Karp, publié indépendamment par Richard Bellman et Michael Held & Richard Karp en 1962. La récurrence clé, où C(S, j) est le chemin le plus court du sommet 1 au sommet j visitant exactement le sous-ensemble S :

Le coût du parcours optimal est alors min_j [C({1,...,n}, j) + d(j, 1)]. Held–Karp s'exécute en temps O(2ⁿ · n²) et en mémoire O(2ⁿ · n) — une amélioration énorme par rapport à la force brute n!, mais toujours exponentielle. Au-delà d'environ 20 villes, l'empreinte mémoire devient impraticable.

Plus proche voisin + 2-opt (Heuristique)

Pour les instances plus grandes, le solveur utilise une heuristique en deux étapes. Tout d'abord, le Plus proche voisin construit un parcours rapide en marchant avidement vers la ville non visitée la plus proche à partir de chaque sommet de départ. Le solveur essaie plusieurs sommets de départ et garde le meilleur parcours. Ensuite, la recherche locale 2-opt améliore le parcours en supprimant itérativement deux arêtes et en reconnectant les deux chemins résultants de la seule autre manière possible :

Géométriquement, le 2-opt élimine chaque « croisement » dans le parcours : deux segments qui se croisent peuvent toujours être décroisés pour une longueur totale plus courte. L'algorithme s'arrête à un optimum local où aucun échange unique n'aide, appelé parcours 2-optimal. Sur des instances euclidiennes réalistes, le 2-opt trouve généralement des parcours à moins de 2–5 % de l'optimum réel en quelques millisecondes.

Formats d'entrée

Mode Coordonnées (x, y)

Une ville par ligne. Chaque ligne est étiquette, x, y — l'étiquette est facultative. Le solveur calcule automatiquement les distances euclidiennes et visualise les villes à leurs positions réelles.

Mode Matrice de distance

Une matrice carrée n × n de distances non négatives, une rangée par ligne, les valeurs étant séparées par des espaces ou des virgules. Les matrices peuvent être symétriques ou asymétriques — les matrices asymétriques modélisent les rues à sens unique, les prix des vols avec une disponibilité variable et les trajets dépendant du vent. Fournissez éventuellement des étiquettes dans le champ Étiquettes de matrice.

Comparaison des algorithmes

Comment utiliser ce solveur

1. Choisissez un mode de saisie. Coordonnées si vos villes ont des positions (x, y) significatives ; Matrice de distance si vos coûts sont non euclidiens ou asymétriques.
2. Collez ou tapez vos données. Une ville ou une rangée par ligne. Cliquez sur un bouton d'exemple rapide au-dessus du formulaire pour pré-remplir un exemple valide.
3. Choisissez l'algorithme. Laissez sur Auto pour le bon réglage par défaut : Held–Karp lorsque l'instance est assez petite pour une optimalité prouvée, PPV + 2-opt sinon. Forcez un algorithme spécifique si vous souhaitez comparer.
4. Choisissez fermé ou ouvert. Un parcours fermé revient au départ — le TSP traditionnel. Le mode chemin ouvert résout le problème connexe du chemin hamiltonien où le voyageur finit dans une ville différente.
5. Cliquez sur Résoudre. La page de résultats affiche la longueur totale du parcours, un SVG animé de l'itinéraire (cliquez sur « Rejouer l'animation » pour le revoir), la séquence complète des villes, un détail par arête et la matrice de distance avec les arêtes du parcours mises en évidence.

Exemple pratique

Considérons cinq villes — un rectangle plus un sommet : A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5). Le solveur renvoie :

• Parcours : A → D → E → C → B → A
• Longueur : 3 + √8 + √8 + 3 + 4 ≈ 15,66
• Optimal ? Oui — Held–Karp prouve qu'aucun parcours plus court n'existe.
• Pourquoi cet ordre ? L'itinéraire trace l'enveloppe convexe des cinq points (A → D → E → C → B → A). Une propriété classique du TSP euclidien est qu'un parcours optimal visite les points de l'enveloppe convexe dans leur ordre cyclique ; les points intérieurs s'insèrent entre les voisins adjacents de l'enveloppe. Tout parcours qui croise son propre chemin, comme A → C → B → D → E → A (longueur ≈ 21,8), peut toujours être décroisé par le 2-opt pour un résultat plus court.

Applications dans le monde réel

• Logistique et livraison — optimiser le parcours quotidien d'un conducteur sur 15 arrêts pour minimiser le carburant et le temps.
• Fabrication — ordonner les trous qu'une perceuse CNC doit faire sur un PCB pour minimiser le déplacement de la tête.
• Assemblage de génome — ordonner les fragments d'ADN par similarité de chevauchement, encodée sous forme de matrice de distance.
• Astronomie — planifier les rotations d'un télescope entre les étoiles cibles pour maximiser le temps d'observation.
• Préparation de commandes — séquencer les visites d'allées pour exécuter une commande en un minimum d'étapes.
• Planification touristique — planifier un voyage multi-villes qui minimise le temps de trajet et le coût du transport.

Foire aux questions

Qu'est-ce que le problème du voyageur de commerce ?

Le problème du voyageur de commerce (TSP) consiste à trouver le parcours le plus court possible qui visite chaque ville exactement une fois et revient à la ville de départ. C'est l'un des problèmes les plus célèbres en optimisation combinatoire et il est NP-difficile dans le cas général, ce qui signifie qu'aucun algorithme connu ne résout toutes les instances en temps polynomial.

Qu'est-ce que l'algorithme de Held–Karp ?

Held–Karp est un algorithme de programmation dynamique qui résout le TSP exactement en temps O(2ⁿ · n²) et en mémoire O(2ⁿ · n). Il est considérablement plus rapide que la force brute (n factoriel) mais reste exponentiel, donc en pratique il n'est utilisé que pour des instances allant jusqu'à environ 20 villes. Ce solveur utilise Held–Karp lorsqu'il y a 12 villes ou moins.

Qu'est-ce que le 2-opt et pourquoi est-il utilisé ?

Le 2-opt est une heuristique de recherche locale qui supprime à plusieurs reprises deux arêtes du parcours actuel et reconnecte les deux chemins résultants de l'autre manière possible. Lorsque le nouveau parcours est plus court, l'échange est conservé. Le 2-opt s'exécute en temps polynomial par itération et trouve systématiquement des parcours à quelques points de pourcentage de l'optimal, c'est pourquoi c'est l'heuristique classique par excellence pour les instances TSP plus larges.

Quand dois-je utiliser des coordonnées par rapport à une matrice de distance ?

Utilisez les coordonnées lorsque vos villes se situent dans un plan avec des distances en ligne droite — par exemple des points sur une carte, des emplacements d'entrepôts ou des trous de perçage sur un circuit imprimé. Utilisez une matrice de distance lorsque le coût par paire n'est pas euclidien — par exemple les prix des vols, les temps de trajet avec trafic, les distances routières à sens unique ou les coûts asymétriques. Le mode matrice accepte toutes les distances non négatives, même asymétriques.

La solution 2-opt est-elle optimale ?

Non, le 2-opt renvoie un parcours 2-optimal, ce qui signifie qu'aucune paire d'arêtes unique ne peut être échangée pour produire un itinéraire plus court. Il s'agit d'un optimum local et généralement à quelques points de pourcentage de l'optimum global sur des instances bien structurées, mais il n'est pas garanti qu'il soit le meilleur globalement. Pour un parcours prouvé optimal sur de petites instances, choisissez Held–Karp.

Cet outil prend-il en charge les matrices de distance asymétriques ?

Oui. En mode Matrice de distance, vous pouvez saisir n'importe quelle matrice carrée non négative, y compris asymétrique où D[i][j] diffère de D[j][i]. Held–Karp et 2-opt gèrent tous deux correctement les matrices asymétriques. Ceci est utile pour les problèmes de routage réels avec des rues à sens unique, du trafic ou des coûts de vol dépendants du vent.

Lectures complémentaires

• Problème du voyageur de commerce — Wikipédia
• Algorithme de Held–Karp — Wikipédia
• 2-opt — Wikipédia
• Algorithme du plus proche voisin — Wikipédia

Opérations mathématiques avancées:

• Calculateur de Matrice d'Adjacence Nouveau
• Calculatrice d'Antilogarithme
• Calculatrice de la fonction bêta
• Calculateur de Coefficient Binomial
• Calculatrice de distribution binomiale
• Calculatrice de Bit
• Simplificateur d'Algèbre de Boole Nouveau
• Calculateur du Théorème Central Limite
• Calculatrice du Théorème des Restes Chinois
• Calculatrice de Combinaison Populaire
• Calculatrice de Fonction d'Erreur Complémentaire
• Calculatrice de Nombres Complexes
• Calculatrice de fractions continues
• Calculateur de Dérangement (Sous-factorielle)
• Calculateur de plus court chemin de Dijkstra
• Calculatrice d'Entropie
• Calculatrice de fonction d'erreur
• Calculatrice de la fonction indicatrice d'Euler
• Calculatrice de désintégration exponentielle
• Calculatrice de croissance exponentielle
• Calculatrice d'intégrale exponentielle
• Calculatrice des Exposants (Haute Précision) Populaire
• Calculatrice de l'Algorithme Euclidien Étendu
• Calculatrice Factorielle
• Calculatrice de Fonction Gamma
• Calculateur de Nombre d'Or
• Calculateur de Coloration de Graphes Nouveau
• Validateur de séquence de degrés de graphe
• Calculateur d'Ordre en Théorie des Groupes Nouveau
• Calculatrice de demi-vie
• Vérificateur de Chemin Hamiltonien Nouveau
• Calculateur d'Inclusion-Exclusion Nouveau
• Solveur de Tableau de Karnaugh (K-Map) Nouveau
• Solveur de Programmation Linéaire Nouveau
• Calculateur d'état stationnaire de chaîne de Markov
• Calculateur d'arbre couvrant minimum
• Calculateur d'Exponentiation Modulaire Nouveau
• Calculatrice de l'Inverse Multiplicatif Modulaire
• Calculateur de Distribution Binomiale Négative Nouveau
• Calculateur de Flot Maximal dans un Réseau Nouveau
• Calculatrice du Taux de Croissance en Pourcentage Populaire
• Calculatrice de permutation
• Calculateur de Permutations avec Répétition Nouveau
• Calculateur du principe des tiroirs
• Vérificateur de Graphe Planaire Nouveau
• Calculatrice de Distribution de Poisson
• Calculatrice des racines de polynômes avec étapes détaillées
• Calculateur de Racine Primitive
• Calculatrice de probabilité
• Calculatrice de Distribution de Probabilité
• Calculatrice de Proportion
• Calculatrice de Formule Quadratique Populaire
• Calculateur d’Anneaux et de Corps Nouveau
• Calculateur d'Arrondi Nouveau
• Calculatrice Scientifique
• Calculatrice de notation scientifique
• Calculateur de Théorie des Ensembles
• Calculateur de Chiffres Significatifs Nouveau
• Solveur du Problème des Mariages Stables Nouveau
• Calculateur de Nombres de Stirling
• Calculatrice de Somme de Cubes
• Calculatrice de la somme des entiers positifs
• Calculatrice de la somme des carrés
• Calculateur de Tri Topologique Nouveau
• Solveur du Voyageur de Commerce (TSP) Nouveau
• Générateur de table de vérité
• Générateur de Diagramme de Venn (3 Ensembles)