Title Image

Blog

Ruta óptima

Cálculo de rutas óptimas mediante SpatiaLite

  |   Bases de datos, Redes, SIG

En esta entrada vamos a ver como podemos realizar un sencillo análisis de redes para el cálculo de rutas óptimas a partir de datos provenientes de OpenStreetMap (OSM), con una base de datos SpatiaLite y su módulo de enrutamiento VirtualNetwork, sin necesidad de matar moscas a cañonazos configurando, por ejemplo, una base de datos PostGIS con pgRouting.

SpatiaLite es una extensión para la base de datos SQLite que da soporte a geometrías espaciales, ajustándose a los estándares del Open Geospatial Consortium (OGC). Es considerado por muchos «el shapefile del futuro» al ser uno de los formatos abiertos mejor posicionados para remplazar al venerable, vetusto y limitado shapefile. Está soportado por importantes librerías como OGR, FDO, Geotools o SharpMap y permite el almacenamiento y manejo de datos ráster (entre otras características y, por qué no decirlo, también debilidades) .

No obstante es difícil modificar hábitos de trabajo con un formato ampliamente asentado como es el shapefile (la Santísima Trinidad), que desde comienzos de la década de 1990, y a pesar de todos sus inconvenientes, ha dado muestras de su competencia a los largo de todos estos años. Un cambio que además implica en su adopción tanto a desarrolladores como a usuarios. Quizá la popularización de SQLite como base de datos de referencia en plataformas móviles como Android ayude a ello, el tiempo lo dirá. Por lo pronto el OGC ya lo considera un buen candidato como formato moderno y neutral en su contenedor GeoPackage.

Al hilo de la serie de entradas que hemos dedicado a la importación de datos de OpenStreetMap, en este sencillo ejemplo utilizaremos spatialite_osm_net, una de las herramientas que soporta SpatialLite para la importación de datos de OSM.

La colección de herramientas spatialite-tools para importar datos provenientes de OSM son cuatro:

  • spatialite_osm_raw: importa los datos en bruto proveniente del archivo XML, volcándolos a tablas tal cual.
  • spatialite_osm_map: permite importar datos OSM generando tantas tablas espaciales como tipos de etiquetas existan.
  • spatialite_osm_filter: permite importar datos OSM aplicando un máscara al conjunto de datos, esto es, indicando una archivo en texto plano que recoja la expresión WKT de un polígono que será usado como filtro espacial.
  • spatialite_osm_net: permite importar arcos ya dispuestos para al análisis de redes.

La peculiaridad que posee spatialite_osm_net para nuestro caso es que nos facilita crear ya lista una tabla  con las columnas necesarias para usarla en funcionalidades de ruteo.

Importando datos y construyendo la topología de redes

Extracto de Cantabria de Metro Extracts

Extracto de datos OSM de Cantabria de Metro Extracts

El primer paso que necesitamos es instalar SpatialLite. Utilizaremos el entorno gráfico que nos proporciona spatialite-gui. Los usuarios de Windows pueden bajarse el ejecutable. En mi caso utilizaré Linux Kubuntu, por lo que simplemente tendremos que instalar el paquete spatialite-gui desde el centro de software o bien mediante consola (si no te aparece probablemente no tengas instalado el repositorio de UbuntuGIS):

sudo apt-get install spatialite-gui

Los usuarios de Windows necesitarán además bajarse aparte la colección de herramientas spatialite-tools.

El siguiente paso es obtener unos datos de ejemplo en formato osm. Para ello usaremos la web de HOT Export Tools, que permite generar tus propios extractos periódicos en diferentes formatos de la base de datos de OpenStreetMap. En este ejemplo descargaremos un extracto de la región de Cantabria en formato binario PBF, de menor tamaño y más rápido de procesar que el XML:

wget https://export.hotosm.org/downloads/3858ac4e-2edc-41b9-987b-085767ba2db9/Cantabria.osm.pbf

A continuación utilizaremos la herramienta spatialite_osm_net para importar los datos a una base de datos SQLite con el siguiente comando por consola:

spatialite_osm_net -o Cantabria.osm.pbf -d cantabria_roads.sqlite -T vias

Donde los parámetros:

-o  | Indica el archivo de OSM de entrada.
-d  | Indica el nombre de la base SQLite que daremos al archivo de salida.
-T  | Indica el prefijo que asignaremos a las tablas creadas.

Aparte merece la pena comentar un par de opciones de interés:

–roads  | Señala que extraeremos únicamente la red de carreteras (parámetro por defecto).
–railways  | Señala que extraeremos únicamente la red de ferrocarriles.
–undirectional  | Genera arcos dobles.

Las opciones roads y railways son excluyentes.

Es probable que al procesar el archivo aparezcan numerosas advertencias del tipo Unresolved-Node o Unresolved-Way. No hay que preocuparse demasiado porque son solo eso, avisos que pueden ignorarse de objetos no válidos que no se procesarán. Para que los resultados sean óptimos cabe decir que se requiere una fuerte integridad topológica de la red, mejores cuanto mayor sea esta. Para detectar inconsistencias en los datos provenientes de OSM son útiles herramientas como Keep Right.

El resultado será una base de datos SQLite que si la abrimos con el programa spatialite-gui que instalamos con anterioridad o con cualquier otro SIG que soporte SpatiaLite, veremos dos tablas espaciales de arcos y nodos de la red. En la primera se recogen la longitud de los tramos, nodos de inicio/fin, coste de desplazamiento (en función de la distancia), sentidos y tipo de vial. En la segunda se almacena los nodos de extremo de cada arco y su cardinalidad, es decir cuantos arcos conectan con ese nodo (útil porque puede indicar errores topológicos en la red).

SpatialLite permite utilizar directamente estas tablas con las que usar el motor de enrutamiento VirtualNetwork y poder realizar en SpatiaLite consultas de routing. Para ello utilizaremos la herramienta Build Network a la que se puede acceder pulsando el icono en la barra de herramientas de spatialite-gui. Configurar la red fijando impedancias como el coste de desplazamientro, las restricciones de giro o sentidos de desplazamiento no tienen gran misterio como vemos a continuación:

VirtualNetwork

El módulo VirtualNetwork extiende las capacidades de una base de datos SpatiaLite proporcionando funcionalidades de enrutamiento.

Durante el proceso nos habrá creado dos nuevas tablas en la base de datos: una física denominada vias_net_data, que contiene datos binarios,  y otra virtual llamada vias_net que aparentemente se encuentra vacía. La primera contiene un grafo de nuestra red sin procesar generado a partir de los datos en bruto procesados de la tabla vias. Lógicamente si se modificase estos datos sería necesario volver a generar esta tabla volviendo a construir la red. La tabla virtual o vista simplemente es un intefaz para soportar las consultas de enrutamiento.

 Si realizamos la siguiente consulta SQL:

SELECT * FROM vias_net WHERE NodeFrom = 27903 AND NodeTo = 10239;

El resultado devuelve todos los arcos del camino más corto entre Santander y Reinosa en función de la resistencia al paso recogida en la columna cost, utilizando en nuestro ejemplo el clásico algoritmo de Dijkstra.

Ruta óptima entre Santander y Reinosa

Camino de menor coste entre Santander y Reinosa. En este caso la consulta SQL se ha realizado a través del administrador de bases de datos de QGIS, que facilita mostrar directamente el resultado en la vista del mapa.