La optimización de rutas va un paso más allá con Google Maps
Muchos usuarios confiamos en Google Maps para encontrar la ruta óptima para llegar de un punto a otro, independientemente del medio de transporte empleado. ¿Y si lo que tengo que recorrer son múltiples puntos y después volver al lugar de origen?
El problema del vendedor ambulante (Travelling Salesman Problem, TSP) para la optimización de rutas es una cuestión bien conocida en de las ciencias de la computación debido a su ubicuidad y utilidad. Este fue formulado por primera vez en 1930, y tiene multitud de aplicaciones: logística, planificación, fabricación de microchips, y hasta aparece en la secuenciación del ADN.
Se trata básicamente de buscar la optimización de las rutas para visitar una serie de localizaciones definidas en el mapa, y volver finalmente al punto de partida; pero no hablamos de acudir solamente a un par de puntos. Aunque el planteamiento es simple, el TSP es uno de los problemas que se han estudiado con más intensidad en la matemática computacional y a pesar de ello todavía no se conoce una solución efectiva para el caso general. De hecho, su resolución obtendría un premio de 1 millón de dólares del Clay Mathematics Institute, puesto que daría con la respuesta al problema de P contra NP.
La solución de Google para optimizar rutas complejas
Google no quiso quedarse sin aportar su particular solución a la optimización de rutas y el TSP, y calculó su propuesta empleando la API Google Directions. ¿A qué ejemplo la aplicó en concreto? El problema planteado fue el de dar con la ruta a pie más corta con la que visitar unos 24.727 pubs a lo largo del Reino Unido. ¿Y qué fuente de datos tomó como referencia? Para tener en cuenta la lista de lugares a visitar -y que esta lista estuviera lo más actualizada posible-, tomó la Guía de Pubs del Reino Unido, la Pubs Galore.
Empleando las coordenadas geográficas de los 24.727 pubs, se midió la distancia entre cada pareja de ellos a partir de la ruta producida por Google Maps. ¿Y cómo emparejarlos? La tarea tampoco es sencilla, porque combinando todos los establecimientos saldrían nada menos que 305.699.901 combinaciones de parejas de bares.
La conclusión fue la siguiente: la ruta óptima supone recorrer una longitud de 45.495.239 metros. Google asegura que no existe un camino más corto entre todos ellos, tomando como referencia, eso sí, las medidas que el propio servicio de Google proporciona. Según los técnicos de Google, el cálculo de la ruta óptima entre pubs es el TSP más complejo y extenso que se ha calculado hasta el momento, multiplicando por 100 el número de paradas respecto las consideradas en cualquier otro ejemplo anterior llevado a cabo por otros grupos de investigación.
En Intelligence Partner nos encantan los retos, y este que hemos traído a nuestro blog nos ha parecido interesantísimo. Afortunadamente, nuestros clientes nos piden cosas más sencillas, y ciertamente nuestra experiencia tecnológica nos permite abordarlos con agilidad y solvencia. Concretamente en el área de la geolocalización como Google Maps Premier Partner, y aplicando tecnologías como Google App Engine, las APIs de Google, Android, Google Maps, Force.com, desarrollando con JAVA, JAVASCRIPT PYTHON, PHP y .NET.
Contacta con nosotros si tienes un reto en áreas como la logísitica, navegación, geoposicionamiento, visualización avanzada de mapas, etc. y necesitas un compañero de viaje para resolverlo.
