- El profesor William Cook de la Universidad de Waterloo calculó un caso inédito en el mundo del problema del viajante (TSP) para la ruta más corta que visita los 81,998 bares de Corea
- Utilizando Open Source Routing Machine (OSRM), calculó aproximadamente 3,300 millones de pares de tiempos de caminata y demostró matemáticamente que es óptima
- El resultado indica que, caminando sin detenerse, toma un total de 15,386,177 segundos, es decir, 178 días, 1 hora, 56 minutos y 17 segundos
- Para la optimización del TSP se usaron las herramientas LKH y Concorde, aplicando el método de planos de corte
- Supera la anterior ruta con más visitas, la de 57,912 recorridos en los Países Bajos, y se convierte en el mayor caso resuelto de TSP basado en carreteras del mundo
El problema del viajante caminando por todos los bares de Corea
- Se calculó la ruta más corta para visitar los 81,998 bares de Corea y regresar al punto de partida
- Es la primera vez en el mundo que se resuelve de forma óptima un problema de TSP con tantos lugares
- Se calcularon los tiempos de caminata de un total de 3,361,795,003 pares entre bares con OSRM - Open Source Routing Machine
- Está demostrado matemáticamente que no existe una ruta más corta que esta
- Este problema es el más grande de la historia entre los TSP por número de puntos a visitar
Tiempo que toma la ruta más corta
- Si se sigue la ruta óptima calculada caminando sin descanso, el tiempo total es de 15,386,177 segundos
- Esto equivale a 178 días, 1 hora, 56 minutos y 17 segundos
- En la práctica, como habría que descansar o beber durante el trayecto, sería difícil terminarla exactamente así
- Es una ruta óptima basada en tiempos de caminata de OSRM a la que no se le puede recortar ni un segundo
Contexto histórico del TSP y nuevo récord
- El récord anterior era una ruta en bicicleta por 57,912 puntos en los Países Bajos
- Esta ruta korea81998 es un caso de resolución de TSP de mayor escala que aquel
- El cálculo se realizó entre diciembre de 2024 y marzo de 2025 en la Universidad de Roskilde y la Universidad de Waterloo
- Los detalles del cálculo pueden consultarse en una página de cálculo aparte
Cómo visualizar la ruta
- La ruta puede verse en un mapa interactivo y explorarse dividida en 7 regiones
- Se ofrecen varios modos de visualización (mapa de distancias en color, escala de grises, etc.)
- También se proporcionan por separado algunas imágenes de alta resolución de partes de la ruta
- Las vistas ampliadas por ciudad están disponibles en la página de ciudades
Estrategia para resolver el TSP y malentendidos comunes
- Algunos medios informan que incluso con solo 22 ciudades tomaría 1000 años, pero eso se refiere a probar todas las rutas al azar
- En la práctica, con técnicas avanzadas de optimización sí es posible resolver problemas con muchos puntos
- En el caso de
korea81998, la cantidad de rutas posibles es un número con 367,308 ceros después del 2
- Para resolverlo se combinó el algoritmo LKH (Lin-Kernighan Heuristic) con el Concorde TSP Solver - método de planos de corte
Resumen del concepto del método de planos de corte
- Se basa en programación lineal
- En lugar de indicar si se usa o no una carretera, expresa el grado de conexión con valores entre 0 y 1
- Va agregando restricciones por etapas para encontrar la ruta más corta
- Una explicación más detallada puede verse en Scientific American y en una charla de YouTube
El problema P vs NP
- El TSP es un problema NP-completo, un ejemplo representativo del problema P vs NP
- Una discusión interesante relacionada se presenta en un artículo del profesor Lance Fortnow
- Este es uno de los problemas abiertos más famosos de la informática
El significado de la optimización matemática
- Este proyecto es tanto un experimento de métodos de optimización de propósito general como una base para su avance
- Tiene un alto potencial de aplicación en industria, comercio, medicina y medio ambiente
- El modelado matemático es una herramienta importante para usar recursos finitos de forma eficiente
Presentación del equipo de investigación
- William Cook: Universidad de Waterloo, Canadá
- Daniel Espinoza: Alicanto Labs, Chile
- Marcos Goycoolea: Universidad Adolfo Ibáñez, Chile
- Keld Helsgaun: Universidad de Roskilde, Dinamarca
Agradecimientos
- IBM CPLEX Optimizer: agradecimiento por su disponibilidad gratuita para investigación académica
- El mapa fue creado con Leaflet, OpenStreetMap, Carto y Stadia Maps
- Dr. Eom Sang-il proporcionó datos de ubicación de bares basados en datos de la Agencia Nacional de Policía de Corea
- Para el cálculo de tiempos de caminata se utilizó OSRM
Casos de proyectos TSP en otros países
- Japón: 40,426 tiendas de conveniencia
- Reino Unido: 49,687 bares
- Estados Unidos: 49,603 sitios históricos
- Países Bajos: 57,912 monumentos
Material adicional de aprendizaje
10 comentarios
La página en inglés es https://www.math.uwaterloo.ca/tsp/korea/index.html.
Sin duda, el recorrido es poco realista. No parece que se estén considerando las rutas marítimas en ferry al desplazarse desde el continente hacia Jeju o Ulleungdo. Basta con ver esta imagen: https://www.math.uwaterloo.ca/tsp/korea/img/full_line.png
Más que calcular con precisión el tiempo estimado de la visita, el punto es darle valor a que resolvieron el TSP con datos del mundo real.
¿Y cómo se desplazan hacia las islas? ¿Caminando?
Como dice
walking and ferry, parece que van en ferry.¿Qué se puede hacer con los casos que aparecen y cierran en tiempo real?
> Tenía previsto dar una clase sobre TSP en KAIST, ubicado en Daejeon, en marzo de 2024, y estaba buscando un conjunto de datos locales para un tour TSP de Daejeon. En diciembre de 2023, el Dr. Eom Sang-il me envió un correo diciendo: "¿Necesita el conjunto de datos nacional de bares creado por la Agencia Nacional de Policía? El archivo más reciente cuesta 1,000 wones y tiene 90,680 registros". Guau. Después de comprobar primero si 1,000 wones eran menos de 1 dólar (fue bueno verificar que el tipo de cambio no estuviera al revés), respondí: "¡Gracias!"
https://www.math.uwaterloo.ca/tsp/korea/sk_data.html
Vaya, no sabía que había todo ese trasfondo. Gracias por resumirlo y compartirlo.
También me da curiosidad saber por qué eligieron a Corea 👀
Probablemente también influyó el hecho de que se podía obtener datos de buena calidad por 1,000 wones :)
Supongo que estaba buscando información relacionada porque iba a dar una charla en Corea.
¿Será que eligieron ese tema porque en Corea hay muchísimos bares..