La ruta a pie más corta para recorrer los 81,998 bares de Corea

• El problema del viajante (TSP) consiste en encontrar la ruta más corta para visitar 81,998 bares de Corea, y se resolvió usando Open Source Routing Machine (OSRM)
• Esta ruta es una ruta óptima que toma más de 178 días, y quedó demostrada mediante los cálculos de OSRM
• Se aplicó el cutting-plane method usando código LKH y código Concorde para resolver un problema TSP a gran escala
• La optimización matemática y la investigación de operaciones se enfocan en desarrollar herramientas para aumentar la eficiencia de los recursos
• La investigación se llevó a cabo en Roskilde University y University of Waterloo, utilizando IBM CPLEX Optimizer y la librería Leaflet

---

La ruta más corta para visitar los 81,998 bares de Corea

• El problema del viajante (TSP) consiste en encontrar la ruta más corta para visitar 81,998 bares de Corea, y se resolvió usando Open Source Routing Machine (OSRM)
• Esta ruta es una ruta óptima que toma más de 178 días, y quedó demostrada mediante los cálculos de OSRM
• Se aplicó el cutting-plane method usando código LKH y código Concorde para resolver un problema TSP a gran escala

Resolver un problema TSP a gran escala

• La optimización matemática y la investigación de operaciones se enfocan en desarrollar herramientas para aumentar la eficiencia de los recursos
• La investigación se llevó a cabo en Roskilde University y University of Waterloo, utilizando IBM CPLEX Optimizer y la librería Leaflet

Equipo de investigación y agradecimientos

• El equipo de investigación está conformado por William Cook, Daniel Espinoza, Marcos Goycoolea y Keld Helsgaun
• La investigación se realizó utilizando CPLEX Optimizer de IBM y la librería Leaflet
• La ubicación de los bares de Corea se obtuvo a través de la base de datos de la Agencia Nacional de Policía de Corea

[xguru]

Publiqué en Hacker News con la cuenta de GeekNews el post La ruta a pie más corta para recorrer los 81,998 bares de Corea en 178 días.
Recibió muchos votos, se mantuvo en la cima durante 6 horas y se volvió popular, así que terminó siendo reimportado a GN+ también.

Como ese post también tenía versión en inglés, probé hacerlo así; de vez en cuando voy a intentar publicar en Hacker News los posts que incluyan texto en inglés.

[GN⁺]

Opiniones de Hacker News

• Impresionante la solución de TSP que incluye 133 millones de estrellas
  • Ese tour mide 1.0038 veces la longitud de la ruta más corta
  • Me pregunto qué tan malo sería el resultado usando el algoritmo probabilístico de Bell Labs
• Explicación del enfoque clásico para TSP
  • Se conectan todos los nodos con una ruta aleatoria
  • Se corta la ruta en dos lugares para formar tres partes
  • Se reordenan las tres partes de las seis maneras posibles y se elige la más corta
  • Se repiten los pasos 2-3 hasta que ya no haya mejoras
  • No garantiza el resultado óptimo, pero en la mayoría de los problemas reales da el óptimo o algo muy cercano
• Es raro que no mencionen la distancia total
  • El objetivo es resolver el tiempo de traslado, pero también sería interesante conocer la distancia real recorrida
  • Se podría calcular el gasto de calorías o verificar cuánto se desvía de la ruta de distancia mínima
• Me abruma pensar que hay casi 82 mil bares en un país del tamaño de Ohio
• Durante COVID me puse la meta de caminar todas las calles de mi pueblo usando CityStrides
  • Lleva registro de cuánto has caminado y te dice qué porcentaje del pueblo ya recorriste
  • No optimizaba la ruta, pero era un rompecabezas mental divertido intentar caminar la mayor distancia posible sin repetir
  • Las herramientas de automatización también pueden ser divertidas, pero hacerlo a mano era parte del viaje
  • Explorando el sitio de CityStrides puedes ver los LifeMaps de la gente
  • Algunas personas caminan una cantidad impresionante
• Me recordó una pregunta que hacía el ejército irlandés en los años 60
  • "¿Cómo ir de Bachelor's Walk a Collins Barracks sin pasar por ningún bar?"
  • La respuesta era: "Entrando a todos los bares"
• Es impresionante haber encontrado este dataset, aunque no es necesariamente más difícil
  • Es un equilibrio sutil entre romper el récord actual del viajante y no lograr terminar el cálculo
• Otra vez parece que NP fuera P
  • En la escuela me enseñaron que 13 era el máximo, y en los 80 un profesor lo había llevado a 15
  • Luego vinieron 20, 20,000, y ahora se demuestra con 80,000
  • En la página de World TSP, el récord es de 1 millón
  • El valor óptimo demostrado más grande actualmente es 3,178,031
  • Hay que hacerlo con CUDA, no con C común
• Branch-and-bound es un algoritmo "de libro"
  • Si ves al solver de LP como una caja negra, en el fondo es muy simple, pero muy útil
• Parece que abrieron algunos bares nuevos y otros cerraron
  • Ya es hora de recalcularlo