Artículo aportado por Ignacio “Nacho” Correas, Director de Innovación Tecnológica de Skymantics –
Hay dos pros y contras que se deben sopesar cuidadosamente: precisión y rendimiento. No sirve de nada que un motor de enrutamiento genere rápidamente rutas subóptimas, pero tampoco resulta práctico generar rutas óptimas que requieran mucho tiempo para su cálculo. El primer punto crítico que se debe considerar en el motor de enrutamiento es el algoritmo de enrutamiento.
Algoritmos de enrutamiento
Skymantics ha experimentado con algoritmos de ruta más corta, en particular Dijkstra y A* (A-star), en tres modos: unidireccional, bidireccional y con optimización de jerarquías de contracción (CH). Implementar una versión básica unidireccional de estos algoritmos es bastante simple, y hay muchos tutoriales en Internet para ayudar a entender cómo hacerlo. Como regla general, construir algoritmos bidireccionales (en otras palabras, la ruta se calcula simultáneamente desde el origen y el destino) proporcionará la ruta óptima de 5 a 10 veces más rápido que un algoritmo unidireccional, aunque elegir el nodo de unión óptimo (donde la ruta desde el origen se encuentra con la ruta desde el destino) tiene sus propios problemas. Sin embargo, elegir entre Dijkstra y A* y entre bidireccional o con CH no es simple.
Cuándo utilizar A*
En teoría, A* debería ser un algoritmo más eficiente, ya que requiere menos cálculos: es básicamente un Dijkstra dirigido que solo tiene en cuenta los nodos del grafo que ayudan a moverse en la dirección hacia el destino. Sin embargo, esto requiere calcular la dirección y las distancias heurísticas, lo que es una operación computacionalmente más costosa que una iteración de Dijkstra y puede ser contraproducente. En general, para mallas muy densas de calles/carreteras de la misma jerarquía, A* puede ser una mejor opción. Para todo lo demás, Dijkstra probablemente será suficiente.
Cuándo utilizar CH
Para rutas largas que atraviesan el país, se necesita algún tipo de optimización, como las jerarquías de contracción. Esta optimización priorizará las rutas de jerarquía superior e ignorará las alternativas de jerarquía inferior, lo que reducirá drásticamente los cálculos para encontrar la ruta más corta de manera muy eficiente. Aquí se muestra un ejemplo de una ruta de 265 km (165 millas) que cruza Bélgica: se necesitan 35 segundos para calcularla con el algoritmo bidireccional de Dijkstra, pero solo 0.1 segundos utilizando la optimización de jerarquías de contracción.
Cuándo utilizar la técnica Dijkstra bidireccional
En el caso de rutas urbanas más cortas, las jerarquías de contracción pueden generar una ruta subóptima, ya que el algoritmo puede tomar desvíos si encuentra una ruta cercana de jerarquía superior. Es posible reducir este efecto o incluso eliminarlo por completo modificando cuidadosamente las jerarquías de carreteras y permitiendo que el algoritmo realice algunas iteraciones adicionales. Pero si la aplicación de enrutamiento es solo para un área urbana específica, puede ser más simple usar un Dijkstra bidireccional. Aquí hay un ejemplo de una ruta en el centro de Providence, Rhode Island, que debería ser solo una línea recta, pero que las jerarquías de contracción engañan y toman un desvío por la calle principal cercana. El tiempo de cálculo para CH es de 1 milisegundo frente a 1.5 milisegundos para Dijkstra bidireccional, lo que demuestra que hay margen para iteraciones adicionales para evitar este efecto de desvío.
Los algoritmos de enrutamiento pueden garantizar la precisión y mejorar el rendimiento hasta cierto punto. Lo cierto es que trazan rutas a través de una malla de carreteras definidas en un conjunto de datos de mapas, y los resultados dependen en gran medida de la precisión de estos conjuntos de datos y de la forma en que se hayan preprocesado.
Preprocesamiento de conjuntos de datos
Los conjuntos de datos y el preprocesamiento son la forma más importante de mejorar la precisión y el rendimiento de un algoritmo de enrutamiento. Es difícil enfatizar este punto lo suficiente. Intentaré resumir los principales aspectos a tener en cuenta en los siguientes puntos:
- No todos los conjuntos de datos tienen el mismo nivel de precisión. OpenStreetMap es un gran ejemplo; cubre prácticamente todo el mundo y se puede descargar y usar de forma gratuita, pero carece de información importante, como muchos límites de velocidad, límites de altura/peso o maniobras prohibidas. En algunos casos, incluso puede contener información falsa con respecto a la direccionalidad de las calles de un solo sentido o las conexiones, por nombrar un par. Otros mapas, como AQUÍ, ofrecen un nivel de precisión mucho mejor, pero tienen un costo. Curiosamente, las coordenadas de las calles no coinciden al 100 % entre los distintos conjuntos de datos y es posible que descubras que las mismas coordenadas se consideran parte de distintas calles según el conjunto de datos que utilices.
- Según la aplicación de su motor de enrutamiento, muchos segmentos de calles o carreteras incluidos en un conjunto de datos se pueden fusionar en un único borde, lo que a veces reduce el tamaño del gráfico hasta en un 90 %. Por ejemplo, se pueden crear atajos para saltar intersecciones de menor jerarquía, lo que acelera el cálculo de la ruta en distancias largas.
- Una parte fundamental del preprocesamiento es decidir cómo clasificar la jerarquía de los enlaces viales: ¿conectan carreteras de jerarquía inferior con otras de jerarquía superior? ¿Conectan carreteras de la misma jerarquía? Este es un aspecto particularmente importante para los cruces de autopistas, ya que las carreteras que unen autopistas deben tener la jerarquía más alta (para acelerar las jerarquías de contracción), pero configurar todos los enlaces viales de una autopista en la jerarquía más alta ralentizará los cálculos debido a demasiadas intersecciones.
Los algoritmos de enrutamiento, los conjuntos de datos y el preprocesamiento son aspectos clave que se deben tener en cuenta para crear un algoritmo de enrutamiento preciso y de alto rendimiento. Pero hay otros aspectos que pueden marcar la diferencia entre un motor de enrutamiento útil y uno inútil.
Mejores prácticas de programación
Doy por sentado que se han implementado buenas prácticas de programación y que se ha elegido un lenguaje de programación adecuado para la tarea. Hay tres puntos críticos que se deben tener en cuenta al implementar y operar un motor de enrutamiento:
- Los datos de los gráficos deben residir en la memoria para obtener el máximo rendimiento. Puede haber algunas partes en una base de datos, por ejemplo, datos geográficos que ayuden a encontrar los nodos más cercanos al origen y al destino, pero el algoritmo de enrutamiento debe funcionar con datos en memoria o corre el riesgo de tener un rendimiento inferior al de los mapas que son apenas más grandes que el centro de una ciudad.
- El motor de enrutamiento debe cargar previamente todos los datos necesarios y debe utilizar subprocesos para tareas secundarias que consumen mucho tiempo, como guardar la ruta generada en el disco. De lo contrario, estos tiempos se acumularán y reducirán el rendimiento general.
- Puede parecer obvio, pero si el motor de enrutamiento se va a ofrecer como un servicio remoto, la velocidad de conexión será crucial. No tiene sentido acelerar el cálculo del enrutamiento si el cuello de botella está en el canal de comunicación. La latencia y el rendimiento son esenciales para un servicio API de alto rendimiento.
Y eso es básicamente todo. Construir un motor de enrutamiento puede ser una tarea emocionante, llena de desafíos y divertida. Incluso si tu objetivo no es construir uno, pero necesitas usar el enrutamiento de manera intensiva, es bueno entender sus aspectos clave. Espero que hayas disfrutado tanto leyendo esta serie de artículos como yo lo hice escribiéndolos. ¡Saludos!
