- Le professeur William Cook de l’Université de Waterloo a calculé, dans une première mondiale, le problème du voyageur de commerce (TSP) appliqué au plus court itinéraire visitant 81 998 bars en Corée
- En utilisant Open Source Routing Machine (OSRM), environ 3,3 milliards de temps de trajet à pied par paires ont été calculés, et il a été mathématiquement prouvé que l’itinéraire est optimal
- Le résultat montre qu’en marchant sans s’arrêter, le trajet total prend 15 386 177 secondes, soit 178 jours, 1 heure, 56 minutes et 17 secondes
- Les outils LKH et Concorde ont été utilisés pour l’optimisation du TSP, avec application de la méthode des plans de coupe
- Il s’agit du plus grand cas de résolution d’un TSP sur réseau routier au monde, dépassant le précédent record des 57 912 points aux Pays-Bas
Le problème du voyageur de commerce consistant à parcourir tous les bars de Corée à pied
- Calcul du plus court itinéraire permettant de visiter les 81 998 bars de Corée puis de revenir au point de départ
- Pour la première fois au monde, un problème de TSP de cette taille a été résolu de manière optimale
- Les temps de trajet à pied pour un total de 3 361 795 003 paires entre bars ont été calculés avec OSRM - Open Source Routing Machine
- Il est mathématiquement impossible qu’un itinéraire plus court existe
- Ce problème est le plus grand TSP jamais résolu en nombre de points à visiter
Durée du plus court itinéraire
- En suivant l’itinéraire optimal calculé et en marchant sans interruption, il faut 15 386 177 secondes au total
- Cela correspond à 178 jours, 1 heure, 56 minutes et 17 secondes
- En pratique, il serait difficile de terminer exactement dans ce temps puisqu’il faudrait se reposer ou boire en chemin
- C’est un itinéraire optimal qu’il est impossible de raccourcir d’une seule seconde selon les temps de marche calculés par OSRM
Contexte historique du TSP et nouveau record
- Le précédent record portait sur un itinéraire cyclable néerlandais de 57 912 points
- Ce parcours korea81998 constitue un cas de résolution de TSP à une échelle supérieure
- Les calculs ont été réalisés entre décembre 2024 et mars 2025 à l’Université de Roskilde et à l’Université de Waterloo
- Les détails du calcul peuvent être consultés sur une page dédiée
Méthodes de visualisation de l’itinéraire
- L’itinéraire peut être exploré sur une carte interactive, avec une navigation par 7 régions
- Différents modes de visualisation sont proposés (carte colorée par distance, niveaux de gris, etc.)
- Des images haute résolution de certaines portions du trajet sont également fournies
- Des vues rapprochées par ville sont disponibles sur la page des villes
Stratégie de résolution du TSP et idées reçues
- Certains médias affirment qu’« il faudrait 1 000 ans rien que pour 22 villes », mais cela correspond au cas où tous les itinéraires seraient essayés au hasard
- En réalité, des techniques d’optimisation avancées permettent de résoudre des problèmes avec un grand nombre de points
- Dans le cas de
korea81998, le nombre d’itinéraires possibles est un 2 suivi de 367 308 zéros
- La résolution a combiné l’algorithme LKH (Lin-Kernighan Heuristic) et Concorde TSP Solver - méthode des plans de coupe
Résumé du concept de méthode des plans de coupe
- Elle repose sur la programmation linéaire
- Au lieu d’indiquer si une route est utilisée ou non, on représente le degré de connexion par une valeur comprise entre 0 et 1
- Des contraintes sont ajoutées étape par étape pour déterminer l’itinéraire le plus court
- Des explications détaillées sont disponibles dans Scientific American et une conférence YouTube
Le problème P contre NP
- Le TSP est un problème NP-complet, exemple représentatif de la question P contre NP
- Des discussions intéressantes à ce sujet sont présentées dans un article du professeur Lance Fortnow
- C’est l’un des problèmes non résolus les plus célèbres de l’informatique
Sens de l’optimisation mathématique
- Ce projet constitue une expérimentation des méthodes d’optimisation générales et une base pour leur amélioration
- Les possibilités d’application sont élevées dans l’industrie, le commerce, la médecine et l’environnement
- La modélisation mathématique est un outil important pour utiliser efficacement des ressources limitées
Présentation des chercheurs
- William Cook : Université de Waterloo, Canada
- Daniel Espinoza : Alicanto Labs, Chili
- Marcos Goycoolea : Université Adolfo Ibáñez, Chili
- Keld Helsgaun : Université de Roskilde, Danemark
Remerciements
- IBM CPLEX Optimizer : remerciements pour la mise à disposition gratuite à des fins de recherche académique
- Les cartes ont été réalisées avec Leaflet, OpenStreetMap, Carto et Stadia Maps
- Le Dr Eom Sang-il a fourni les données de localisation des bars, basées sur les données de l’Agence nationale de police coréenne
- Le calcul des temps de marche a utilisé OSRM
Exemples de projets TSP dans d’autres pays
- Japon : 40 426 supérettes
- Royaume-Uni : 49 687 bars
- États-Unis : 49 603 sites historiques
- Pays-Bas : 57 912 monuments
Ressources complémentaires
10 commentaires
La page en anglais est https://www.math.uwaterloo.ca/tsp/korea/index.html.
Le parcours est clairement irréaliste. Il semble qu’il ne prenne pas en compte les liaisons maritimes en ferry pour aller du continent à Jeju ou à Ulleungdo. Il suffit de regarder cette image : https://www.math.uwaterloo.ca/tsp/korea/img/full_line.png
L’objectif n’est sans doute pas de calculer avec précision le temps estimé nécessaire pour la visite, mais plutôt de montrer l’intérêt d’avoir résolu le TSP à partir de données du monde réel.
Et pour les déplacements vers les îles ? À pied aussi ?
Comme il est indiqué « walking and ferry », j’imagine qu’on y va en bateau.
Comment faire pour gérer les cas où des bars ouvrent et ferment en temps réel ?
> En mars 2024, je devais donner un cours sur le TSP au KAIST, situé à Daejeon, et je cherchais un jeu de données local pour un tour TSP de Daejeon. En décembre 2023, le Dr Sang-il Um m’a envoyé un e-mail disant : « Avez-vous besoin du jeu de données national des bars créé par l’Agence nationale de la police ? Le fichier le plus récent coûte 1 000 wons et contient 90 680 entrées. » Waouh. Après avoir d’abord vérifié que 1 000 wons représentaient bien moins d’un dollar (heureux d’avoir vérifié que le taux de change n’était pas inversé), j’ai répondu : « Merci ! »
https://www.math.uwaterloo.ca/tsp/korea/sk_data.html
Waouh, je ne savais pas qu’il y avait ce contexte. Merci pour ce récapitulatif et ce partage.
Je suis aussi curieux de savoir pourquoi la Corée a été choisie 👀
Le fait qu’on puisse obtenir des données de qualité pour 1 000 wons y a probablement aussi contribué :)
> J’avais prévu de donner un cours sur le TSP au KAIST, situé à Daejeon, en mars 2024, et je cherchais un jeu de données local pour une tournée TSP de Daejeon.
Je pense que je cherchais probablement des informations pertinentes parce que j’avais prévu de donner une conférence en Corée.
C’est parce qu’il y a tellement de bars en Corée qu’ils ont choisi ce sujet…