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

Autres outils connexes:

Opérations mathématiques avancées:

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