Le plus court itinéraire à pied pour parcourir les 81 998 bars de Corée

• Le problème du voyageur de commerce (TSP) consiste ici à trouver le plus court itinéraire visitant 81 998 bars coréens, et a été résolu à l’aide de Open Source Routing Machine (OSRM)
• Cet itinéraire est une route optimale qui demande plus de 178 jours, comme l’ont démontré les calculs d’OSRM
• Le code LKH et le code Concorde ont été utilisés pour appliquer la cutting-plane method afin de résoudre un problème de TSP à très grande échelle
• L’optimisation mathématique et la recherche opérationnelle se concentrent sur le développement d’outils visant à améliorer l’efficacité des ressources
• La recherche a été menée à Roskilde University et à University of Waterloo, en utilisant IBM CPLEX Optimizer et la bibliothèque Leaflet

---

Le plus court itinéraire pour visiter les 81 998 bars de Corée

• Le problème du voyageur de commerce (TSP) consiste à trouver le plus court itinéraire visitant 81 998 bars coréens, et a été résolu à l’aide de Open Source Routing Machine (OSRM)
• Cet itinéraire est une route optimale qui demande plus de 178 jours, comme l’ont démontré les calculs d’OSRM
• Le code LKH et le code Concorde ont été utilisés pour appliquer la cutting-plane method et résoudre ce problème de TSP à très grande échelle

Résolution d’un problème de TSP à grande échelle

• L’optimisation mathématique et la recherche opérationnelle mettent l’accent sur le développement d’outils visant à améliorer l’efficacité des ressources
• La recherche a été menée à Roskilde University et à University of Waterloo, en utilisant IBM CPLEX Optimizer et la bibliothèque Leaflet

Équipe de recherche et remerciements

• L’équipe de recherche est composée de William Cook, Daniel Espinoza, Marcos Goycoolea et Keld Helsgaun
• L’étude a été menée à l’aide de CPLEX Optimizer d’IBM et de la bibliothèque Leaflet
• Les emplacements des bars coréens ont été obtenus via la base de données de l’Agence nationale de la police coréenne

[xguru]

J’ai publié sur Hacker News avec le compte GeekNews l’article Le plus court itinéraire à pied pour visiter les 81 998 bars de Corée en 178 jours.
Il a reçu beaucoup de votes, a occupé la première place pendant 6 heures, puis est devenu un article populaire, au point d’être réimporté sur GN+ en sens inverse (?).

Comme l’article contenait aussi une version anglaise, j’ai essayé ainsi, et je pense publier de temps en temps sur Hacker News les articles qui incluent une version anglaise.

[GN⁺]

Commentaires Hacker News

• Une solution du TSP incluant 133 millions d’arêtes, c’est impressionnant
  • Cette tournée fait 1,0038 fois la longueur du plus court trajet
  • Je me demande à quel point le résultat serait moins bon avec l’algorithme probabiliste de Bell Labs
• Explication de l’approche classique du TSP
  • Relier tous les nœuds par un chemin arbitraire
  • Couper le chemin en deux endroits pour former trois segments
  • Réorganiser les trois segments selon les six possibilités et choisir la plus courte
  • Répéter les étapes 2 et 3 jusqu’à ce qu’il n’y ait plus d’amélioration
  • Cela ne garantit pas le résultat optimal, mais pour la plupart des problèmes réels, on obtient l’optimum ou quelque chose de très proche
• C’est étrange de ne pas mentionner la distance totale
  • Le but est de résoudre le temps de déplacement, mais connaître la distance réelle serait aussi intéressant
  • On pourrait calculer les calories dépensées ou voir à quel point on s’écarte du trajet le plus court
• Je suis dépassé par l’idée qu’il y ait presque 82 000 bars dans un pays de la taille de l’Ohio
• Pendant le COVID, je m’étais fixé comme objectif de marcher dans toutes les rues de ma ville avec CityStrides
  • Il suit les distances parcourues et indique quel pourcentage de la ville a été couvert à pied
  • Il n’optimisait pas l’itinéraire, mais essayer de marcher le plus possible sans doublons était un casse-tête mental amusant
  • Les outils d’automatisation peuvent être amusants aussi, mais le faire à la main faisait partie du voyage
  • En parcourant le site de CityStrides, on peut voir les LifeMaps des gens
  • Certaines personnes marchent des quantités étonnantes
• Cela me rappelle une question posée dans l’armée irlandaise dans les années 60
  • « Comment aller de Bachelor's Walk à Collins Barracks sans passer devant un bar ? »
  • La réponse était : « en entrant dans tous les bars »
• C’est impressionnant d’avoir trouvé ce jeu de données, mais ce n’est pas plus difficile
  • C’est un équilibre subtil entre battre le dernier record du voyageur de commerce et ne pas réussir à finir le calcul
• Le NP recommence à ressembler à P
  • À l’école, j’avais appris que 13 était le maximum, puis dans les années 80, un prof l’avait fait passer à 15
  • Ensuite, il y a eu 20, 20 000, et cette fois 80 000 ont été démontrés
  • Sur la page World TSP, le record est d’un million
  • La plus grande valeur optimale actuellement prouvée est 3 178 031
  • Il faut le faire en CUDA, pas en C classique
• Le branch-and-bound est un algorithme « tiré des manuels »
  • Si l’on considère le solveur LP comme une boîte noire, c’est fondamentalement très simple, mais très utile
• Il semble que quelques nouveaux bars aient ouvert et que quelques autres aient fermé
  • Il est temps de recalculer