Problème du voyageur de commerce

Le problème du voyageur de commerce (souvent appelé TSP) est un problème algorithmique classique dans le domaine de l'informatique et de la recherche opérationnelle. Il est axé sur l'optimisation. Dans ce contexte, une meilleure solution signifie souvent une solution moins chère, plus courte ou plus rapide. Le TSP est un problème mathématique. Il s'exprime le plus facilement sous la forme d'un graphe décrivant les emplacements d'un ensemble de nœuds.

Le problème du voyageur de commerce a été défini dans les années 1800 par le mathématicien irlandais W. R. Hamilton et par le mathématicien britannique Thomas Kirkman. Le jeu Icosian de Hamilton était un puzzle récréatif basé sur la découverte d'un cycle hamiltonien. La forme générale du TSP semble avoir été étudiée pour la première fois par des mathématiciens dans les années 1930 à Vienne et à Harvard, notamment par Karl Menger. Menger définit le problème, considère l'algorithme de force brute évident et observe la non-optimalité de l'heuristique du plus proche voisin :

Nous désignons par problème de messagerie (puisque dans la pratique cette question devrait être résolue par chaque facteur, de toute façon aussi par de nombreux voyageurs) la tâche de trouver, pour ﬁnitely de nombreux points dont les distances par paires sont connues, le chemin le plus court reliant les points. Bien entendu, ce problème peut être résolu par de nombreux essais. On ne connaît pas de règles qui feraient passer le nombre d'essais en dessous du nombre de permutations des points donnés. La règle selon laquelle il faut d'abord aller du point de départ au point le plus proche, puis au point le plus proche de celui-ci, etc. ne permet généralement pas d'obtenir l'itinéraire le plus court.

Hassler Whitney, de l'université de Princeton, a introduit peu après le problème des vendeurs itinérants de noms.

Un vendeur veut visiter toutes les villes, A, B, C et D. Quelle est la meilleure façon de le faire (billets d'avion les moins chers, et temps de voyage minimal) ?

Itinéraire optimal d'un vendeur visitant les 15 plus grandes villes d'Allemagne. L'itinéraire indiqué est le plus court des 43 589 145 600 possibles.

William Rowan Hamilton

Énoncer le problème

Le problème du vendeur itinérant décrit un vendeur qui doit se déplacer entre N villes. L'ordre dans lequel il le fait ne l'intéresse pas, à condition qu'il se rende dans chacune d'entre elles une fois au cours de son voyage et qu'il termine là où il était au début. Chaque ville est reliée aux autres par des villes proches, ou des nœuds, par des avions, ou par la route ou le chemin de fer. Chacune de ces liaisons entre les villes a un ou plusieurs poids (ou le coût) qui lui est attaché. Le coût décrit la "difficulté" de franchir cette limite sur le graphique, et peut être donné, par exemple, par le coût d'un billet d'avion ou de train, ou peut-être par la longueur de la limite, ou le temps nécessaire pour effectuer la traversée. Le vendeur veut que les frais de voyage, ainsi que la distance parcourue, soient aussi bas que possible.

Le problème du voyageur de commerce est typique d'une grande classe de problèmes d'optimisation "durs" qui intriguent les mathématiciens et les informaticiens depuis des années. Plus important encore, il a des applications dans le domaine des sciences et de l'ingénierie. Par exemple, dans la fabrication d'une carte de circuit imprimé, il est important de déterminer le meilleur ordre dans lequel un laser va percer des milliers de trous. Une solution efficace à ce problème permet de réduire les coûts de production du fabricant.

Difficulté

En général, le problème des vendeurs itinérants est difficile à résoudre. S'il existe un moyen de décomposer ce problème en problèmes de composants plus petits, les composants seront au moins aussi complexes que le composant d'origine. C'est ce que les informaticiens appellent les problèmes NP-durs.

De nombreuses personnes ont étudié ce problème. La solution la plus simple (et la plus coûteuse) est d'essayer toutes les possibilités. Le problème est que pour N villes, vous avez des possibilités factorielles (N-1). Cela signifie que pour seulement 10 villes, il y a plus de 180 000 combinaisons à essayer (puisque la ville de départ est définie, il peut y avoir des permutations sur les neuf autres). Nous ne comptons que la moitié puisque chaque route a un parcours identique à l'envers avec la même longueur ou le même coût. 9 ! / 2 = 181 440

Il est possible de trouver des solutions exactes au problème, en utilisant des algorithmes de branche et de liaison. Cela est actuellement possible pour 85 900 villes.
Les approches heuristiques utilisent un ensemble de règles directrices pour la sélection du nœud suivant. Mais comme les heuristiques donnent lieu à des approximations, elles ne donneront pas toujours la solution optimale, bien que des heuristiques admissibles de haute qualité puissent trouver une solution utile en une fraction du temps nécessaire pour une force brute complète du problème. Un exemple d'heuristique pour un nœud serait la somme du nombre de nœuds non visités qui sont "proches" d'un nœud connecté. Cela pourrait encourager le vendeur à visiter un groupe de nœuds proches regroupés en grappe avant de passer à une autre grappe naturelle dans le graphe. Voir les algorithmes de Monte Carlo et les algorithmes de Las Vegas

Questions et réponses

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

R : Le problème du voyageur de commerce est un problème algorithmique classique dans le domaine de l'informatique et de la recherche opérationnelle. Il est axé sur l'optimisation, de meilleures solutions signifiant souvent des solutions moins chères, plus courtes ou plus rapides.

Q : Comment s'exprime le TSP ?

R : Le TSP s'exprime le plus facilement sous la forme d'un graphe décrivant les emplacements d'un ensemble de nœuds.

Q : Qui a été le premier à définir le TSP ?

R : Le problème du voyageur de commerce a été défini dans les années 1800 par le mathématicien irlandais W. R. Hamilton et par le mathématicien britannique Thomas Kirkman.

Q : Qui l'a étudié plus avant dans les années 1930 ?

R : Dans les années 1930, les mathématiciens Karl Menger, à Vienne et à Harvard, l'ont étudiée plus avant.

Q : Qu'a introduit Hassler Whitney peu après ?

R : Hassler Whitney, de l'université de Princeton, a introduit le nom de "problème du voyageur de commerce" peu après sa définition.

Q : Que signifie "meilleure solution" dans ce contexte ?

R : Dans ce contexte, une meilleure solution signifie souvent une solution moins chère, plus courte ou plus rapide.

Q : Quel algorithme était considéré comme évident par Menger lorsqu'il étudiait le TSP ?

R : Menger a considéré un algorithme de force brute évident lors de l'étude de TSP et a observé que l'utilisation de l'heuristique du plus proche voisin ne donne pas toujours des résultats optimaux.