Conceptos de pgRouting¶

Crear una Base de Datos de Ruteo¶

Lo primero que hay que hacer es crear una base de datos y cargar pgRouting a la base de datos. Típicamente se creará una base de datos para cada proyecto. Una vez que se tiene una base de datos donde trabajar, se pueden cargar los datos y construir la aplicación en la base de datos. Esto hace que sea sencillo de mover el proyecto en el futuro, como por ejemplo, a un servidor de producción.

Para Postgresql 9.2 y versiones posteriores

createdb mydatabase
psql mydatabase -c "create extension postgis"
psql mydatabase -c "create extension pgrouting"

Cargar Datos¶

El cómo cargar los datos dependerá de el formato que tienen. Existen varias herramientas de Código Abierto que le pueden ayudar, como:

Así, estas herramientas y probablemente otras le permitirán leer datos vectoriales para que luego pueda cargar esos datos en su base de datos como una tabla de algún tipo. En este punto, necesita saber un poco sobre su estructura de datos y contenido. Una forma fácil de navegar por su nueva tabla de datos es con pgAdmin3 o phpPgAdmin.

Construir una Topología de Ruteo¶

A continuación, tenemos que construir una topología para nuestros datos de calle. Esto significa que para cualquier arista dada dentro de los datos de calle, los extremos de la arista se conectarán a un nodo único y a otras aristas que también están conectados a ese mismo nodo único. Una vez que todas las aristas están conectados a los nodos tenemos un grafo que se puede utilizar para el ruteo con pgRouting. Proporcionamos una herramienta que le ayudará con esto:

select pgr_createTopology('myroads', 0.000001);

• pgr_createTopology

Compruebe la Topología de Ruteo¶

Hay muchas fuentes posibles de errores en un grafo. Es posible que los datos con los que comenzó no se hayan diseñado teniendo en cuenta el ruteo. Un grafo tiene algunos requisitos muy específicos. Una es que es NODED, esto significa que, a excepción de algunos casos de usos muy específicos, cada segmento de carretera comienza y termina en un nodo y, en general, no cruza otro segmento de carretera al que debería estar conectado.

Puede haber otros errores como en una calle de un solo sentido tener el sentido equivocado. No contamos con herramientas para buscar todos los errores posibles, pero tenemos algunas herramientas básicas que pueden ayudar.

select pgr_analyzegraph('myroads', 0.000001);
select pgr_analyzeoneway('myroads',  s_in_rules, s_out_rules,
                                     t_in_rules, t_out_rules
                                     direction)
select pgr_nodeNetwork('myroads', 0.001);

• pgr_analyzeGraph
• pgr_analyzeOneWay
• pgr_nodeNetwork

Calcular una Ruta¶

Una vez que haya realizado todo el trabajo de preparación realizado anteriormente, calcular una ruta es bastante fácil. Tenemos una gran cantidad de algoritmos diferentes que pueden funcionar con su red de carreteras preparada. La forma general de una consulta de ruta es:

select pgr_dijkstra(`SELECT * FROM myroads', 1, 2)

Como puede ver esto es bastante sencillo y puede buscar los algoritmos específicos para los detalles de las firmas y cómo usarlos. Estos resultados tienen información como edge id y/o el identificador de nodo junto con el costo o la geometría del paso en la ruta de acceso de start a end. Con los identificadores puede unir estos resultados a la tabla de aristas para obtener más información sobre cada paso de la ruta.

• pgr_dijkstra

Uno a Uno¶

Cuando se rutea desde:

• Desde el vértice inicial one
• al vértice final one

Uno a Muchos¶

Cuando se rutea desde:

• Desde el vértice inicial one
• a los vértices finales many

Muchos a Uno¶

Cuando se rutea desde:

• Desde vértices iniciales many
• al vértice final one

Muchos a Muchos¶

Cuando se rutea desde:

• Desde vértices iniciales many
• a los vértices finales many

Combinaciones¶

Cuando se rutea desde:

• A partir de muchos diferentes vértices de inicio
• a muchos diferentes vértices finales
• Cada tupla especifica un par de vértices iniciales y un vértice final
• Los usuarios pueden definir las combinaciones como deseen.

Descripción de la consulta edges_sql para funciones similares a dijkstra¶

Donde:

Descripción de la consulta edges_sql (no es necesarioun id)

Donde:

consulta edges_sql para las funciones aStar - Familia de Funciones y aStar - Familia de Funciones¶

Donde:

Para pgr_pushRelabel, pgr_edmondsKarp, pgr_boykovKolmogorov :

Donde:

Para pgr_maxFlowMinCost - Experimental and pgr_maxFlowMinCost_Cost - Experimental:

Donde:

Descripción de la consulta SSQL de Puntos

Donde:

Descripción de la consulta de combinaciones_sql para funciones similares a dijkstra¶

Donde:

Valores devueltos para una ruta¶

Devuelve el conjunto de (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)

Valores devueltos para varias rutas desde el mismo origen y destino¶

Devuelve el conjunto de (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)

Descripción de los valores devueltos para una función Cost Matrix - Categoría¶

Devuelve SET OF (start_vid, end_vid, agg_cost)

Descripción de los valores devueltos¶

Para pgr_pushRelabel, pgr_edmondsKarp, pgr_boykovKolmogorov :

Para pgr_maxFlowMinCost - Experimental

Topología para Ruteo¶

Resumen

Normalmente cuando se cargan archivos GIS en la base de datos para su uso con pgRouting no tienen información de la topología asociada a ellos. Para crear una topología útil, los datos debe ser «noded». Esto significa que donde dos o más caminos forman una intersección allí debe existir y todos los segmentos de carretera necesitan estar partidos en la intersección, eso suponiendo que puede navegar a cualquier otro segmento mediante la intersección de cualquiera de estos segmentos.

Puedes utilizar graph analysis functions para ayudarte a visualizar dónde podría haber problemas de topología en tus datos. Si necesitas crear nodos a partir de tus datos, también tenemos una función pgr_nodeNetwork () que deberían funcionarte. Esta función divide TODOS los segmentos cruzados y los une. Hay algunos casos en los que esto podría NO ser lo correcto.

Por ejemplo, cuando se tiene un cruce de puente o de un túnel, no quieres estos contengan un nodo, pero pgr_nodeNetwork no sabe que ese es el caso y va a crear un nodo, entonces el enrutador interpretará el puente o el paso a desnivel como si fuera una intersección plana en 2D. Para lidiar con este problema, se debe utilizar niveles z ya se para estos tipos de intersecciones o para otros casos en donde crear el nodo de la intersección no sea lo correcto.

Para los casos donde la topología debe construirse, las siguientes funciones pueden ser de utilidad. Una forma de preparar los datos para pgRouting es agregar los siguientes campos a la tabla y luego poblarlas según corresponda. Este ejemplo tiene como supuestos: que la tabla original ya tiene columnas como one_way, fcc y posiblemente otras y que contienen valores de datos específicos. Esto es sólo para darle una idea de lo que se puede hacer con los datos.

ALTER TABLE edge_table
    ADD COLUMN source integer,
    ADD COLUMN target integer,
    ADD COLUMN cost_len double precision,
    ADD COLUMN cost_time double precision,
    ADD COLUMN rcost_len double precision,
    ADD COLUMN rcost_time double precision,
    ADD COLUMN x1 double precision,
    ADD COLUMN y1 double precision,
    ADD COLUMN x2 double precision,
    ADD COLUMN y2 double precision,
    ADD COLUMN to_cost double precision,
    ADD COLUMN rule text,
    ADD COLUMN isolated integer;

SELECT pgr_createTopology('edge_table', 0.000001, 'the_geom', 'id');

La función pgr_createTopology crea la tabla vertices_tmp y llena las columnas de source y target. El siguiente ejemplo llenó las columnas restantes. Aquí, la columna fcc contiene código de clase de entidad y las declaraciones CASE lo convierten a una velocidad promedio.

UPDATE edge_table SET x1 = st_x(st_startpoint(the_geom)),
                      y1 = st_y(st_startpoint(the_geom)),
                      x2 = st_x(st_endpoint(the_geom)),
                      y2 = st_y(st_endpoint(the_geom)),
  cost_len  = st_length_spheroid(the_geom, 'SPHEROID["WGS84",6378137,298.25728]'),
  rcost_len = st_length_spheroid(the_geom, 'SPHEROID["WGS84",6378137,298.25728]'),
  len_km = st_length_spheroid(the_geom, 'SPHEROID["WGS84",6378137,298.25728]')/1000.0,
  len_miles = st_length_spheroid(the_geom, 'SPHEROID["WGS84",6378137,298.25728]')
              / 1000.0 * 0.6213712,
  speed_mph = CASE WHEN fcc='A10' THEN 65
                   WHEN fcc='A15' THEN 65
                   WHEN fcc='A20' THEN 55
                   WHEN fcc='A25' THEN 55
                   WHEN fcc='A30' THEN 45
                   WHEN fcc='A35' THEN 45
                   WHEN fcc='A40' THEN 35
                   WHEN fcc='A45' THEN 35
                   WHEN fcc='A50' THEN 25
                   WHEN fcc='A60' THEN 25
                   WHEN fcc='A61' THEN 25
                   WHEN fcc='A62' THEN 25
                   WHEN fcc='A64' THEN 25
                   WHEN fcc='A70' THEN 15
                   WHEN fcc='A69' THEN 10
                   ELSE null END,
  speed_kmh = CASE WHEN fcc='A10' THEN 104
                   WHEN fcc='A15' THEN 104
                   WHEN fcc='A20' THEN 88
                   WHEN fcc='A25' THEN 88
                   WHEN fcc='A30' THEN 72
                   WHEN fcc='A35' THEN 72
                   WHEN fcc='A40' THEN 56
                   WHEN fcc='A45' THEN 56
                   WHEN fcc='A50' THEN 40
                   WHEN fcc='A60' THEN 50
                   WHEN fcc='A61' THEN 40
                   WHEN fcc='A62' THEN 40
                   WHEN fcc='A64' THEN 40
                   WHEN fcc='A70' THEN 25
                   WHEN fcc='A69' THEN 15
                   ELSE null END;

-- UPDATE the cost information based on oneway streets

UPDATE edge_table SET
    cost_time = CASE
        WHEN one_way='TF' THEN 10000.0
        ELSE cost_len/1000.0/speed_kmh::numeric*3600.0
        END,
    rcost_time = CASE
        WHEN one_way='FT' THEN 10000.0
        ELSE cost_len/1000.0/speed_kmh::numeric*3600.0
        END;

-- clean up the database because we have updated a lot of records

VACUUM ANALYZE VERBOSE edge_table;

Ahora su base de datos debe estar lista para usarse en cualquiera (mayoría?) de los algoritmos de pgRouting.

Análisis de gráficas¶

Resumen

Es común encontrar problemas con los gráficos que no se han construido completamente ligados con nodos o con gráficos con niveles z en intersecciónes que se han introducido incorrectamente. Otro problema es que las calles han sido introducidas en la dirección equivocada. No podemos detectar errores con respecto a la verdad respecto a la «tierra», pero podemos buscar inconsistencias y algunas anomalías en un gráfico y les reportarlas para inspecciones adicionales.

Nosotros no tenemos herramientas de visualización para estos problemas, pero se ha utilizado MapServer para reproducir la gráfica y poner en relieve las áreas con problemas potenciales. Alguien familiarizado con graphviz podría contribuir con herramientas para generar imágenes para este propósito.

Analizar un gráfico¶

Con pgr_analyzeGraph el grafo puede revisarse en busca de errores. Por ejemplo, para la tabla «mytab» que incluye a «mytab_vertices_pgr» como la tabla de vértices:

SELECT pgr_analyzeGraph('mytab', 0.000002);
NOTICE:  Performing checks, pelase wait...
NOTICE:  Analyzing for dead ends. Please wait...
NOTICE:  Analyzing for gaps. Please wait...
NOTICE:  Analyzing for isolated edges. Please wait...
NOTICE:  Analyzing for ring geometries. Please wait...
NOTICE:  Analyzing for intersections. Please wait...
NOTICE:              ANALYSIS RESULTS FOR SELECTED EDGES:
NOTICE:                    Isolated segments: 158
NOTICE:                            Dead ends: 20028
NOTICE:  Potential gaps found near dead ends: 527
NOTICE:               Intersections detected: 2560
NOTICE:                      Ring geometries: 0
pgr_analyzeGraph
----------
   OK
(1 row)

En la tabla de vértices «mytab_vertices_pgr»:

• Los callejones están identificados por cnt=1
• Se identifican problemas potenciales brecha con``chk=1``.

SELECT count(*) as deadends  FROM mytab_vertices_pgr WHERE cnt = 1;
deadends
----------
    20028
 (1 row)

SELECT count(*) as gaps  FROM mytab_vertices_pgr WHERE chk = 1;
 gaps
 -----
   527
 (1 row)

Si se tienen segmentos aislados de caminos, por ejemplo, un segmento en el cual los dos extremos son callejones sin salida, se pueden encontrar con la siguiente consulta:

SELECT *
    FROM mytab a, mytab_vertices_pgr b, mytab_vertices_pgr c
    WHERE a.source=b.id AND b.cnt=1 AND a.target=c.id AND c.cnt=1;

Si quieren visualizar en una imagen gráfica, entonces usted puede utilizar algo como MapServer para representar los bordes y los vértices y el estilizar en base a cnt o si están aislados, etc. También se puede hacer esto con una herramienta como graphviz o geoserver u otras herramientas similares.

Analizar las calles unidireccionales¶

pgr_analyzeOneWay analiza las calles unidireccionales de un grafo e identifica los segmentos volteados. Básicamente, si cuenta las aristas que entran en un nodo y las aristas bordes que salen de un nodo, el número tiene que ser mayor que uno.

Esta consulta agrega dos columnas a la tabla vertices_tmp ein int y eout int (ein = borde de entrada, eout=borde de salida) y las rellena con los conteos correspondientes. Después de su ejecución, en un grafo se pueden identificar los nodos con problemas potenciales utilizando la siguiente consulta.

Las reglas se definen como un conjunto de cadenas de texto que si coinciden con el valor de col se considera como válido para el origen o destino dentro o fuera de la condición.

SELECT pgr_analyzeOneway('mytab',
            ARRAY['', 'B', 'TF'],
            ARRAY['', 'B', 'FT'],
            ARRAY['', 'B', 'FT'],
            ARRAY['', 'B', 'TF'],
            );

-- now we can see the problem nodes
SELECT * FROM mytab_vertices_pgr WHERE ein=0 OR eout=0;

-- and the problem edges connected to those nodes
SELECT gid FROM mytab a, mytab_vertices_pgr b WHERE a.source=b.id AND ein=0 OR eout=0
UNION
SELECT gid FROM mytab a, mytab_vertices_pgr b WHERE a.target=b.id AND ein=0 OR eout=0;

Para las funciones de Ruteo¶

Para obtener resultados más rápidos, las consultas enlazan el área de interés para tener, por ejemplo, no más de un millón de filas.

Utilice una consulta SQL interna que no incluya algunas aristas en la función de ruteo

SELECT id, source, target from edge_table WHERE
        id < 17 and
        the_geom  && (select st_buffer(the_geom,1) as myarea FROM  edge_table where id = 5)

Integración de la consulta interna a la función pgRouting:

SELECT * FROM pgr_dijkstra(
        'SELECT id, source, target from edge_table WHERE
            id < 17 and
            the_geom  && (select st_buffer(the_geom,1) as myarea FROM  edge_table where id = 5)',
    1, 2)

Para las funciones de topología:¶

Cuando «sabe» que va a eliminar un conjunto de bordes de la tabla de bordes, y sin esos bordes va a utilizar una función de enrrutamiento puede hacer el siguiente:

Analizar la topología nueva basada en la topología actual:

pgr_analyzegraph('edge_table',rows_where:='id < 17');

O crear una nueva topología si el cambio es permanente:

pgr_createTopology('edge_table',rows_where:='id < 17');
pgr_analyzegraph('edge_table',rows_where:='id < 17');