Ruteo óptimo con herramientas de código abierto

Contribución:
Ing. Sist. Mauricio Márquez Goa
IDECOR


27 de abril de 2022

Seguramente has buscado cómo llegar a una dirección en auto, bici o a pie, usando el GPS de un dispositivo móvil ¿Te has preguntado cómo funcionan las aplicaciones que nos permiten conocer la ruta y la distancia entre una ubicación y otra? En esta nota te contamos qué ocurre detrás de dichos requerimientos y cómo funciona pgRouting, la herramienta de ruteo de código abierto de PostGIS.

El software PostgreSQL/PostGIS cuenta con la extensión pgRounting que permite añadir capacidades geoespaciales para realizar consultas y procesos de análisis de redes y planificación a través de rutas, de forma rápida y segura, optimizando los tiempos de respuesta y el trabajo de los usuarios.

Para calcular una distancia, la librería de pgRouting contiene el algoritmo de Dijkstra, conocido como “algoritmo de caminos mínimos”, ya que determina la ruta más corta desde un nodo de origen hacía otros nodos de la red. Te explicamos su funcionamiento con un caso práctico.

Hagamos un ejercicio juntos

Para realizar este ejercicio debes contar con PostgreSQL, PostGIS y pgRouting previamente instalados en tu equipo y trabajar con la versión de QGIS 3.0 o superior.  Utilizaremos datos de la ciudad Villa María, disponibles en MapasCórdoba.

Una vez descargados e implementados en la base de datos (siguiendo los pasos de la nota previa) se procede a construir la topología de red de los ejes de calle de Villa María. La estructura requerida es una capa de líneas con calidad topológica. Esto significa que, para cualquier arista dentro de los ejes de calle, los extremos de la misma se conectarán a un nodo único y a otras que también están conectados a ese mismo nodo. Una vez que todas las aristas están vinculadas a los nodos, se obtiene un grafo, que se puede utilizar para el ruteo con pgRouting:

select pgr_createTopology(‘vialidad_villa_maria’, 0.0001, ‘geom’, ‘id’);

Este proceso asignará un valor (ID) a cada uno de los nodos, que servirán para determinar los caminos entre y a través de ellos.

Imagen 1. Vista de los datos descargados e implementados en un proyecto QGIS.

Observemos de cerca este proceso de asignación de valores ID a los nodos. En el software QGIS se etiquetaron aquellos en los alrededores de la Plaza Centenario de Villa María, ubicada entre las intersecciones de las calles Santa Fé y General Paz, así como los de la Terminal de Ómnibus de Villa María, y en las intersecciones del Bv. Sarmiento y el Bv. Marcelo T. de Alvear.

El valor asignado a los nodos entre las intersecciones indicadas son el 718 y el 1435 ¿Cuál es la distancia y el recorrido óptimo entre entre ambos?

Cálculo de recorridos y distancias

La función pgr dijkstra utiliza el algoritmo de Dijkstra. Para visualizar cómo se realiza el cálculo en QGIS utilizaremos el complemento pgRoutingLayer, que ejecuta las sentencias SQL en la base de datos PostgreSQL/PostGIS, apoyándose en la topología de ruteo creada con pgRouting.

Imagen 2. Vista de la ejecución de la consulta pgr_dijkstra en el complemento pgRoutingLayer.

El resultado de la consulta es una tabla, con columnas que permiten conocer los nodos, las calles y sus alturas, la secuencia del recorrido y la distancia, entre otras variables.

Imagen 3. Vista de la tabla de atributos con los registros a través del recorrido de los nodos.

En la Imagen 3 puede verse cómo la función pgr_dijkstra calcula la distancia a través de la red, también conocida como “distancia de Manhattan”, entre las intersecciones de las calles Santa Fe y General Paz hasta las intersecciones de Bv. Sarmiento y Bv. Marcelo T. de Alvear.

La función pgr_dijkstra se puede utilizar uno a uno, uno a muchos, muchos a uno y muchos a muchos.

A partir del principio anterior, es posible calcular cualquier distancia dentro de Villa María, por ejemplo, desde cualquier punto de la ciudad hasta los centros de salud. El valor de ese cálculo se puede guardar dentro de un campo de cada nodo y generar, por ejemplo, una simbología de valores graduados por cuantiles (Imagen 4).

Imagen 4. Vista de nodos con simbología con valores graduados.

Cálculo de los tiempos de traslado 

Siguiendo con el ejemplo anterior, podemos determinar el tiempo que tardaría caminando una persona desde cualquier localización (nodo) hasta un centro de salud. Para ello usaremos el valor promedio de velocidad peatonal, de 5.000 m caminados en 60 minutos. Una vez calculado el tiempo y trasladado a cada nodo, con el panel de control temporal de QGIS podemos generar una animación de los tiempos  de traslado.

Con los resultados obtenidos es posible determinar las distancias y tiempos promedios por barrios, mediante intersecciones espaciales de la capa de barrios de Villa María y los valores de cada uno de los nodos.

Con estos resultados se pueden construir mapas de coropletas que permitan visualizar de forma sencilla cada uno de los barrios, clasificados por distancia y/o tiempo de traslado a un centro de salud en la ciudad (Imagen 5).

Imagen 5. Vista de distancias promedio por barrio.

¿Te interesa indagar más sobre pgRouting? Podés visitar  https://pgrouting.org/ ¿Te quedaste con dudas o querés hacernos alguna sugerencia? Escribinos a [email protected].

Te compartimos otras notas que hemos publicado relacionadas con este contenido, como Paso a paso: cómo añadir capas PostGIS en QGIS, Cómo hacer consultas espaciales con PostGIS y Cómo hacer consultas espaciales con PostGIS – Parte 2.

Para mantenerte informado sobre las novedades de IDECOR, seguirnos por Instagram en idecor.ok y por nuestro canal de YouTube.

Categorías: Novedades