Le plus court itinéraire à pied pour visiter les 81 998 bars de Corée prend 178 jours
(math.uwaterloo.ca)- 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
- In Pursuit of the Traveling Salesman : histoire et applications du TSP
- Traveling Salesman Problem : étude sur l’application de la méthode des plans de coupe
- The Golden Ticket : introduction au problème P vs. NP
- Opt Art : création d’images artistiques à l’aide du TSP
- Approximation Algorithms : recherches récentes sur les algorithmes d’approximation du TSP
- Computational Solutions for TSP Applications : ouvrage de 1994 sur des cas d’application
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 ?
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é :)
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…