best road trip major landmarks

Encontré muy interesante y educativo el trabajo de Randal S. Olson, un investigador de la Universidad de Pensilvania, acerca de las rutas óptimas, uno de los mayores problemas matemáticos de optimización. Básicamente se refiere al cálculo de la «ruta óptima» que visita una serie de puntos en un mapa (por ejemplo, las capitales de un continente) recorriendo la menor distancia posible. La tarea es fácil de definir, pero muy compleja de concretar cuando el número de ciudades aumenta, pues las posibles rutas aumentan exponencialmente y ni siquiera los superordenadores pueden calcularlas todas. Es conocido en computación como el problema del viajante.

No obstante, para cantidades razonables como pueden ser 50 ciudades y utilizando ciertos atajos y técnicas matemáticas la potencia de los equipos actuales resulta suficiente – garantizando además de que el resultado está tal vez tan solo un uno por ciento alejado del «perfecto». Y no solo «en teoría»: Olson ha desarrollado un software que busca esas rutas a través de calles y carreteras reales con la ayuda de Google Maps. De este modo calculó que la ruta óptima a través de los Estados Unidos para recorrer 50 lugares emblemáticos, uno por cada estado, volviendo al lugar de origen, supone 22.046 kilómetros de conducción. Otro tanto hizo con Europa, donde con 26.211 km se pueden recorrer otros 50 sitios recomendados por las guías.

Manhattan andando / Randal S. Olson

El mismo software es capaz de trazar una ruta optimizada para recorrer diversos puntos de una ciudad, por ejemplo para visitar 20 monumentos andando o entregar 40 paquetes en furgoneta. Tan solo hay que alimentar previamente el software con los puntos geoposicionados que hay que recorrer. Como ejemplo, en este mapa interactivo para turistas que quieren visitar Manhattan paseando se puede ver el resultado: 22 kilómetros (en este caso el principio y el final no tiene por qué ser el mismo).

Las posibilidades de software de este estilo son enormes y es fácil entender que a menor espacio recorrido mayor ahorro de combustible y menor contaminación producida.

Las empresas de logística utilizan soluciones de este estilo constantemente, incluso en tiempo real gracias al geoposicionamiento de los vehículos por GPS: algunos pueden interactuar con los destinatarios en caso de que una incidencia vaya a impedir la entrega (por ejemplo, por ausencia) de modo que la ruta se reajuste y siga siendo óptima. En otros, se puede incluso modificar el punto de entrega contactando electrónicamente con el destinatario en caso de que la dirección sea incorrecta. Esto permite resolver las incidencias sobre la marcha y mejorar un factor importantísimo en logística: la llamada «entrega al primer intento».


Tags: