Cálculo de rutas: una aproximación a la actualidad

¿Cuál es la ruta más rápida de Barcelona a Sevilla? Mañana, a las 9: 00h, seguirá siendo la misma? ¿Y si voy con un vehículo de gran tonelaje? ¿Desde donde estoy ahora, hasta dónde puedo llegar en 30 minutos? ¿Tengo que visitar esta la lista de clientes, qué ruta debo seguir para hacerlo lo más rápidamente posible? De esta lista de vehículos que se encuentran en unas posiciones determinadas ¿Cuál es lo que tardará menos en llegar a este cliente?

Estas y otras preguntas similares son las que es capaz de responder la librería de cálculo de rutas de Nexus Geographics. Internamente la llamamos NGRouteNet5.

La primera versión apareció alrededor del año 2003. Hasta ese momento utilizábamos una librería comercial. El número de tramos de la red de carreteras había aumentado mucho (si mal no recuerdo, unos 150.000 tramos) y entonces tardaba más de 45 segundos para calcular una ruta de punta a punta de España. Con la nueva librería conseguimos reducirlo a unos segundos ... las máquinas, en aquellos tiempos,  estaban bastante limitadas en cuanto a memoria y rendimiento.

A lo largo de los años, el número de tramos en la red no ha parado de crecer, o bien porque ha ido aumentando la cobertura dentro de los países, o bien porque hemos añadido de nuevos. Las características de las máquinas han ido mejorando mucho pero ha sido necesario ir modificando los algoritmos para aprovechar su rendimiento.

Actualmente llegamos a tratar redes con más de 100 millones de tramos.

Por otra parte, el número de peticiones de cálculo por minuto de nuestros clientes no ha parado de crecer y ha sido necesario estudiar soluciones para calcularlas en paralelo, dentro de una misma máquina (multi thread) y fuera.

La librería ha ido incorporando cada vez más funcionalidades: matrices de costes entre muchos orígenes y destinos; rutas con restricciones para camiones y vehículos especiales; rutas con restricciones temporales; cálculo de isócronas, rutas calculadas en función del tráfico previsto en cierta fecha y hora o rutas calculadas teniendo en cuenta el estado del tráfico actual.

La mayoría de las características anteriores requieren que se pueda modificar dinámicamente los costes de los tramos. Esta flexibilidad limita la elección de los algoritmos que se pueden aplicar para optimizar el cálculo de rutas. Por ejemplo, en el mundo open source se utiliza habitualmente Contractions Hierarchies que proporciona unos tiempos de cálculo inmejorables. Pero para aplicar este algoritmo es necesario ejecutar antes un proceso de preparación en que se debe conocer el coste final para cruzar los tramos. Esta preparación puede llegar a tardar más de 24 horas en redes de 100 millones de tramos y si se modifica el coste de un solo tramo hay que volver a ejecutar la preparación. En nuestro caso, aplicamos otros tipos de optimizaciones más enfocadas hacia la topología de la red, en vez del coste específico de los tramos, ¿será por nuestro ADN GIS? Con este tipo de algoritmos un cambio de coste en un tramo no implica tener que volver a precalcular toda la red.

Dado que cada vez hay más interés por la optimización de flotas en tiempo real, prevemos que el volumen de peticiones irá creciendo. Sobre todo el de cálculo de matrices. Es aquí donde destinamos nuestros esfuerzos para optimizarlo aún más.

Albert Rovira. Jefe de producto de Cercalia.