The Traveling Salesman Problem : le problème du voyageur de commerce

The Traveling Salesman Problem (TSP), en français : le problème du voyageur de commerce, est un nouveau projet de mathématiques lancé il y a tout juste un mois par Markus Weltin (un habitant des Samoa Américaines).  Quelques précisions techniques : Une unité dure environ 1h sur un processeur Q6600, et utilise seulement 900 Ko de mémoire vive. C'est donc encore un projet parfaitement adapté pour les plus petites configurations. INSCRIPTION       -     Article détaillé

Explication du problème : Le problème du voyageur de commerce n'est pas très difficile à expliquer. En partant d'un groupe de villes données, il consiste à visiter une fois chacune des villes (une seule et unique fois) tout en minimisant la distance de vos déplacements. Ce problème qui paraît à tort élémentaire est effectivement anodin pour un petit nombre de villes, mais, lorsque vous ajoutez d'autres villes, le nombre de chemins possibles crève le plafond. Il ne faut donc pas s'étonner si le problème du voyageur de commerce est classé dans la catégorie des problèmes NP-complets. Dans ce problème, le nombre de chemins hamiltoniens est égal à n!/2 où n correspond au nombre de villes qui composent le problème. 

Une solution générale efficiente n'a pas encore été découverte. Les mathématiciens ont conclu que le meilleur moyen était d'utiliser un algorithme avec des polynômes variant en rapport avec le nombre de villes. À l'heure actuelle, la meilleure solution varie de façon exponentielle en fonction du nombre de villes.
C'est là qu'intervient le projet BOINC-TSP. Le projet TSP se voit confier la lourde tâche qui consiste à trouver une solution optimale pour un TSP de 48 villes en utilisant la méthode par force brute. Une fois que le ou les chemins optimaux seront connus, nous pourrons débuter la résolution du problème à l'aide d'autres algorithmes  (algorithmes génétiques, méthode des plus proches voisins, recuit simulé et algorithme par colonies de fourmis).

Le projet utilise 48 villes des États-Unis, un point de départ à Washington et un point d'arrivé à Montgomey dans l'Alabama. Voici une représentation du chemin le plus court trouvé par les premiers calculs (solution provisoire). 

Vos commentaires (0)