25 Sep 2018 Cálculo de rutas óptimas con PostGIS

Detrás de cualquier algoritmo de enrutamiento se esconde una estructura de grafo. Estas estructuras son, pués, imprescindibles para el cálculo de rutas óptimas. En este post vamos a centrarnos en la generación de grafos para su utilización desde la base de datos espacial PostgreSQL/PostGIS.

Para entender mejor que es un grafo, vamos a partir del callejero de nuestra ciudad y vamos a imaginarnos un grafo como una lista completa de todas las calles de la ciudad, donde, para cada calle conocemos el nodo inicial y el nodo final. Lógicamente, el nodo final de una calle puede coincidir con el nodo inicial de otra. De esta forma tan sencilla podemos definir un grafo y, a partir de aquí, calcular todas las conexiones existentes entre todas las calles de nuestra ciudad.

La realidad es un poco más compleja, ya que, una misma calle (de cierta longitud) puede conectar con varias calles. Por este motivo, debemos descomponer todas las calles en sus puntos de intersección con otras calles. De este modo, en lugar de calles hablaremos de segmentos de calle o arcos con sus nodos iniciales y finales.

En la siguiente imagen podemos ver la representación gráfica de un pequeño grafo. Los números representan los nodos y las letras las calles. Podemos ver como las calles A y B están compuestas por distintos arcos.

El grafo anterior, en formato de tabla:

Tabla 1.1: Callejero en formato tabulado

Una vez definido qué es y como se organiza, nos queda por ver cómo podemos crear un grafo a partir de una cartografía previamente existente. A continuación vamos a ver tres formas distintas de crear un grafo.

• osm2pgrouting:
  Esta herramienta, incluida en la instalación de PostGIS, permite crear un grafo a partir de cartografía en formato OSM. Dispone de un fichero de configuración que permite personalizar los parámetros de importación y configuración del grafo. Lamentablemente solo podemos utilizar osm2pgrouting con datos en formato de OpenStreetMap.

• pgr_nodeNetwork: Esta función de PostGIS está diseñada, precisamente, para generar un grafo a partir de datos existentes en una base de datos. Lamentablemente, a día de hoy, esta función contiene numerosos bugs y no produce los resultados deseados.

• Uso combinado de funciones PostGIS: En tercer lugar, y siendo un poco imaginativos, podemos combinar distintas funciones de PostGIS para generar nuestro grafo. Más concretamente, podemos combinar las funciones St_Union() y St_Dump().

La función St_Union() permite llevar a cabo una operación de tipo dissolve, es decir, unir un conjunto de geometrías en una sola geometría de tipo MULTI (en nuestro caso MULTILINESTRING). Por su parte, la función St_Dump() permite obtener todas las geometrías simples que componen una geometría de tipo MULTI. St_Dump() retorna un tipo compuesto de datos formado por un atributo numérico (path) y un atributo de tipo geometry (geom).

Para este ejemplo vamos a reproducir el callejero que aparece en la siguiente imagen:

Para ello, creamos la tabla callejero:

CREATE TABLE  callejero (
id SERIAL PRIMARY KEY,
nombre VARCHAR(25),
geom GEOMETRY
);

Y añadimos las siguientes calles.

INSERT INTO callejero (nombre, geom) VALUES (‘A’, St_GeomFromText(‘LINESTRING(-3.6967738 40.4227273,-3.6966589 40.4231664,-3.6965874 40.4234147,-3.6965117 40.4236891,-3.6965125 40.4237212)’));
INSERT INTO callejero (nombre, geom) VALUES (‘B’, St_GeomFromText(‘LINESTRING(-3.6955342 40.4236784,-3.6955697 40.4231059,-3.6956075 40.4225342)’));
INSERT INTO callejero (nombre, geom) VALUES (‘C’, St_GeomFromText(‘LINESTRING(-3.6965125 40.4237212,-3.6955342 40.4236784)’));
INSERT INTO callejero (nombre, geom) VALUES (‘D’, St_GeomFromText(‘LINESTRING(-3.6966025 40.4226957,-3.6956075 40.4225342)’));
INSERT INTO callejero (nombre, geom) VALUES (‘E’, St_GeomFromText(‘LINESTRING(-3.6955697 40.4231059,-3.6966589 40.4231664)’));
INSERT INTO callejero (nombre, geom) VALUES (‘F’, St_GeomFromText(‘LINESTRING(-3.6965874 40.4234147,-3.6965469 40.4234098,-3.6963418 40.4233812)’));
INSERT INTO callejero (nombre, geom) VALUES (‘G’, St_GeomFromText(‘LINESTRING(-3.6967738 40.4227273,-3.6966025 40.4226957)’));

Combinando St_Union y St_Dump obtenemos los 10 arcos de nuestro grafo. Podemos, además, crear una nueva tabla callejero_grafo en la misma sentencia SQL:

CREATE TABLE callejero_grafo AS
SELECT (ST_DUMP(St_Union(geom))).geom
FROM callejero

El último paso consiste en crear una nueva tabla de nodos donde almacenar la información equivalente a la tabla 1.1. Para ello, añadimos las columnas SOURCE y TARGET a la tabla callejero_grafo. Estas columnas están inicialmente vacías.

ALTER TABLE callejero_grafo ADD COLUMN source INTEGER;
ALTER TABLE callejero_grafo ADD COLUMN target INTEGER;

Finalmente utilizaremos la función pgr_createTopology(nombre_tabla, tolerancia, columna_geom, columna_id) del siguiente modo:

SELECT pgr_createTopology(‘callejero_grafo’, 0.00001, ‘geom’,’id’);

El comando anterior y, más concretamente la función pgr_createTopology, creará la tabla callejero_grafo_vertices_pgr y actualizará las columnas source y target de la tabla callejero_grafo.

Ahora sí, ya tenemos nuestro grafo listo para llevar a cabo nuestras consultas de enrutamiento.

Nota: St_Union() es una función de agregado. Esto significa que, si queremos agrupar TODAS las geometrías debemos ignorar el resto de atributos de las calles ya que, en caso contrario, la agrupación será incompleta. Para recuperar los atributos de cada arco se debe establecer una relación espacial de tipo St_Contains() entre calles y arcos de calle.