 Le
problème du voyageur de commerce (TSP) est résolu
lorsque le "commercial" visite chacune des n villes en couvrant la
distance la plus faible. Le chemin le plus court est ce que
l'on appelle un circuit hamiltonien. Il
n'existe aucune méthode
généralisée permettant de trouver les
solutions TSP.
Image : Wolfram Mathworld |
En mathématique, le problème du voyageur de commerce (Traveling Salesman Problem, TSP) est ce que l'on appelle un classique : quel chemin permet de visiter une seule et unique fois un nombre de villes donné tout en minimisant la distance parcourue. Lorsque l'on réfléchit au problème pour un petit nombre de villes, la solution parait simpliste. Cependant, au fur et à mesure que le nombre de villes s'élève, la résolution du problème surpasse rapidement la capacité de la plupart des micro-ordinateurs. Il faudrait par exemple 1047 années pour vérifier de manière exhaustive toutes les possibilités permettant de relier 48 villes, et ce en considérant que vous puissiez passer en revue un million de possibilités par seconde.
Malgré de nombreuses recherches, aucune solution générale n'a encore pu être apportée pour résoudre le problème TSP.
Mais qui se soucie réellement du voyageur de commerce ?
Avons nous vraiment besoin de savoir quel est l'itinéraire le plus court pour qu'un voyageur de commerce vienne sonner à votre porte ? Non, mais la forme générique du problème est utilisé dans la conception des circuits imprimés, le partitionnement des données, l'analyse des structures cristallines, l'ordonnancement, pour découper les matériaux et bien plus encore.
Représentant distribué
L'étape suivante consistera à observer si la combinaison d'algorithmes de recherche et de tactiques par force brute peuvent aboutir à un résultat optimal. Ensuite, viendra le temps du banc d'essai de toutes théories en s'intéressant à de très grands problèmes TSP.
Les débuts
Le projet TSP a débuté comme une sorte d'étude de faisabilité. Je (Markus Weltin) voulais juste prouver que je pouvais être capable de lancer ce genre de projet. Quelques-uns de mes amis se sont joint au projet.
