Problème du voyageur de commerce
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
Si un voyageur part du point A et que les distances entre toutes les ville sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ?
Si un voyageur part du point A et que les distances entre toutes les ville sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ?

Le problème du voyageur de commerce consiste, étant donné un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) de villes séparées par des distances données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.), à trouver le plus court chemin qui relie toutes les villes. C'est un problème NP-complet.

Approche simplifiée

L'énoncé du problème du voyageur de commerce est le suivant : étant donné n points (des " villes ") et les distances séparant chaque point (Graphie), trouver un chemin de longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus éloignées. Lorsque l’objet est filiforme ou en forme de lacet, sa longueur...) totale minimale qui passe exactement une fois par chaque point et revienne au point de départ.

Ce problème est plus compliqué qu'il n'y paraît ; on ne connaît pas de méthode de résolution permettant d'obtenir des solutions exactes en un temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) raisonnable pour de grandes instances (grand nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de villes) du problème. Pour ces grandes instances, on devra donc souvent se contenter de solutions approchées, car on se retrouve face à une explosion (Une explosion est la transformation rapide d'une matière en une autre matière ayant un volume plus grand, généralement sous forme de gaz. Plus cette transformation s'effectue...) combinatoire : Le nombre de chemins possibles passant par 69 villes est déjà un nombre de 100 chiffres. Pour comparaison, un nombre de 80 chiffres permettrait déjà de représenter le nombre d'atomes (Un atome (du grec ατομος, atomos, « que l'on ne peut diviser ») est la plus petite partie d'un corps simple pouvant se combiner...) dans tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) l'univers (L'Univers est l'ensemble de tout ce qui existe et les lois qui le régissent.) connu !

Ce problème peut servir tel quel à l'optimisation de trajectoires de machines-outils  par exemple, pour minimiser le temps total ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une somme. Exemple : "Le...) que met une fraiseuse (Une fraiseuse est une machine-outil utilisée pour usiner tous types de pièces mécaniques, à l'unité ou en série, par enlèvement de matière à partir de blocs ou parfois...) à commande (Commande : terme utilisé dans de nombreux domaines, généralement il désigne un ordre ou un souhait impératif.) numérique (Une information numérique (en anglais « digital ») est une information ayant été quantifiée et échantillonnée, par opposition à une...) pour percer n points dans une plaque de tôle. Il se posait également pour optimiser la vitesse (On distingue :) de tracé d'une structure (en BTP, par exemple) par une table traçante (Une table traçante est un outil de dessin industriel. Elle se compose d'une table horizontale et d'un porte-stylo motorisé, le tout étant commandé par ordinateur (mais connecté à une unité...) à l'époque où ces périphériques étaient mécaniques, et non électroniques comme aujourd'hui.

Plus généralement, divers problèmes de recherche opérationnelle (La recherche opérationnelle (aussi appelée aide à la décision) peut être définie comme l'ensemble des méthodes et techniques rationnelles d'analyse et de synthèse des phénomènes d'organisation utilisables pour élaborer de meilleures...) se ramènent au voyageur de commerce. Un voyageur de commerce peu scrupuleux serait intéressé par le double problème du chemin le plus court (pour son trajet réel) et du chemin le plus long (pour sa note de frais).

Problème détaillé

Voici un énoncé plus formel du problème du voyageur de commerce sous forme constatée de problème de décision (En logique mathématique, on appelle problème de la décision le fait de déterminer de façon mécanique, par un algorithme, si un énoncé est un théorème de la logique égalitaire du premier ordre,...).

Données :

  • un graphe complet (Un graphe complet est un graphe dont les sommets sont tous reliés deux à deux par une arête. Dans un graphe G, on nomme clique un sous-graphe complet de G, c'est-à-dire une partie de l'ensemble des sommets de G telle que le...) G = (V,A,ω) avec V un ensemble de sommets, A un ensemble d'arcs et \omega : A \rightarrow \mathbb{N} une fonction de coût sur les arcs ;
  • un entier B \in \mathbb{N}

Question :

Existe-t-il un cycle passant une et une seule fois par chaque sommet tel que la somme des coûts des arcs utilisés soit inférieure à B ?

Approches de résolution

De nombreux travaux de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche scientifique...) ont concerné le problème du voyageur de commerce. La programmation linéaire (En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d'optimisation où la fonction objectif et les contraintes sont toutes...) permet désormais de résoudre des problèmes de grande taille (à l'échelle d'un pays (Pays vient du latin pagus qui désignait une subdivision territoriale et tribale d'étendue restreinte (de l'ordre de quelques centaines de km²), subdivision de la civitas gallo-romaine. Comme la civitas qui subsiste...)[1]), moyennant éventuellement un temps de calcul important. Lorsque le temps alloué à la résolution est faible on utilisera plutôt des heuristiques et des méta-heuristiques.

Page générée en 0.054 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique