Solveur du Voyageur de Commerce (TSP)

Trouvez le trajet le plus court qui visite chaque ville exactement une fois et revient au point de départ. Programmation dynamique exacte (Held-Karp) pour les petits cas et heuristiques du plus proche voisin + 2-opt pour les plus grands. Accepte des coordonnées ou une matrice de distance et génère un tour SVG animé.

Exemples rapides :

Carré 5 villes + sommet 8 villes aléatoires 8 capitales de l'UE Matrice 4×4 Benchmark 10 villes Triangle (chemin ouvert)

⌖ Coordonnées (x, y) ▦ Matrice de distance

Villes ou matrice

Lignes de coordonnées : A, 10, 20 ou 10 20. Rangées de matrice : 0 10 15 20 — une ligne par rangée, carrée, non négative. Max 40 villes.

Étiquettes de matrice (optionnel)

Étiquettes séparées par des virgules ou des espaces, une par ligne de matrice. Par défaut A, B, C… si omis.

Algorithme

Type de parcours

Embed Solveur du Voyageur de Commerce (TSP) Widget

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 :

minimiser Σ_i=1^n-1 d(π(i), π(i+1)) + d(π(n), π(1))

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 :

C(S, j) = min_{k ∈ S \ {j}} [ C(S \ {j}, k) + d(k, j) ]

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 :

Avant : ... a — b ... c — d ... Après l'échange 2-opt : ... a — c ... b — d ... Si d(a,c) + d(b,d) < d(a,b) + d(c,d) → accepter l'échange, inverser le sous-parcours b..c

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.

A, 10, 20 B, 40, 70 C, 75, 30 Paris : 2.35, 48.86 10 20 ← étiqueté auto C1

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.

0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0

Comparaison des algorithmes

Algorithme	Complexité temporelle	Mémoire	Qualité du résultat	Taille pratique
Force brute	O(n!)	O(n)	Optimal	n ≤ 10
DP de Held–Karp	O(2ⁿ · n²)	O(2ⁿ · n)	Optimal	n ≤ 20
Plus proche voisin	O(n²)	O(n)	~25 % de moins que l'optimal	n ≤ milliers
PPV + 2-opt	O(n² · passes)	O(n)	~2–5 % de moins que l'optimal	n ≤ centaines

Comment utiliser ce solveur

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.
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.
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.
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.
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

Citez ce contenu, cette page ou cet outil comme suit :

"Solveur du Voyageur de Commerce (TSP)" sur https://MiniWebtool.com/fr/solveur-du-voyageur-de-commerce-tsp/ de MiniWebtool, https://MiniWebtool.com/

par l'équipe miniwebtool. Mis à jour : 21 avr. 2026

Vous pouvez également essayer notre Résolveur Mathématique IA GPT pour résoudre vos problèmes mathématiques grâce à des questions-réponses en langage naturel.

Autres outils connexes:

Calculateur de Matrice d'AdjacenceNouveau

Calculateur de plus court chemin de Dijkstra

Calculateur de Coloration de GraphesNouveau

Validateur de séquence de degrés de graphe

Vérificateur de Chemin HamiltonienNouveau

Solveur de Programmation LinéaireNouveau

Calculateur de Flot Maximal dans un RéseauNouveau

Solveur du Problème des Mariages StablesNouveau

Calculateur de Tri TopologiqueNouveau

Solveur du Voyageur de Commerce (TSP)

Solveur du Voyageur de Commerce (TSP)

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

Comment fonctionne ce solveur

Programmation dynamique de Held–Karp (Exacte)

Plus proche voisin + 2-opt (Heuristique)

Formats d'entrée

Mode Coordonnées (x, y)

Mode Matrice de distance

Comparaison des algorithmes

Comment utiliser ce solveur

Exemple pratique

Applications dans le monde réel

Foire aux questions

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

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

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

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

La solution 2-opt est-elle optimale ?

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

Lectures complémentaires

Autres outils connexes:

Opérations mathématiques avancées:

Outils en vedette: