Conceptos de pgRouting


Comenzando a trabajar

Esta es una guía simple para llevarte a través de los pasos básicos para trabajar con pgRouting. Esta guía cubre:


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

Hay varias maneras de cargar los datos en pgRouting. La forma más directa es cargar un dataset de Open Street Maps (OSM) utilizando osm2pgrouting. Esta es una herramienta, integrada en el proyecto pgRouting, que carga datos OSM en postgresql con requisitos pgRouting, incluida la estructura de datos y la topología de enrutamiento.

Si tiene otros requisitos, puede probar varias herramientas de OpenSource que pueden ayudarle, como:

shp2pgsql
  • Este es un cargador de archivo shape a postgresql

ogr2ogr
  • Esta es una utilidad de conversión de datos vectoriales

osm2pgsql
  • Esta es una herramienta para cargar los datos de OSM a postgresql

Tenga en cuenta que estas herramientas no importarán los datos en una estructura compatible con pgRouting y es posible que deba adaptarlos.

Estas herramientas y probablemente otras le permitirán leer datos vectoriales para poder cargar esos datos en la 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 manera fácil de navegar por su nueva tabla de datos es con pgAdmin o phpPgAdmin.


Construir una Topología de Ruteo

Nota

este paso no es necesario si los datos se cargan con  osm2pgrouting

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);

donde debe reemplazar “myroads” con el nombre de su tabla almacenando los bordes.

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);

donde debe reemplazar “myroads” por el nombre de la tabla que almacena los bordes (“ways”, en caso de que haya utilizado osm2pgrouting para importar los datos).

Calcular una Ruta

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

select pgr_dijkstra(`SELECT * FROM myroads', <start>, <end>)

Este algoritmo solo requiere id, source, target y cost como los atributos mínimos, que de forma predeterminada se considerarán columnas en la tabla de caminos. Si los nombres de columna de la tabla de caminos no coinciden exactamente con los nombres de estos atributos, puede usar alias. Por ejemplo, si importara datos de OSM mediante osm2pgrouting, el nombre de la columna id sería gid y la tabla de caminos sería ways, por lo que consultaría una ruta del id 1 del nodo al id 2 del nodo escribiendo:

select pgr_dijkstra('SELECT gid AS id, source, target, cost FROM ways', 1, 2)

Como puede ver, esto es bastante sencillo y también permite una gran flexibilidad, tanto en términos de estructura de base de datos como en la definición de funciones de coste. Puede probar la consulta anterior utilizando length_m AS cost para calcular la ruta de acceso más corta en metros o cost_s / 60 AS cost para calcular la ruta de acceso más rápida en minutos.

Puede buscar y los algoritmos específicos para los detalles de las firmas y cómo utilizarlas. Estos resultados tienen información como el id de borde y/o el id del nodo junto con el costo o la geometría del paso en la ruta de acceso de start a end. Con los identificadores puede volver a unir estos resultados a la tabla perimetral para obtener más información sobre cada paso de la ruta de acceso.

Grupo de Funciones

Una función puede tener diferentes sobrecargas. A través de esta documentación, para indicar qué sobrecarga usamos los siguientes términos:

Dependiendo de la sobrecarga son los parámetros utilizados, manteniendo la coherencia en todas las funciones.

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.


Consultas Internas

There are several kinds of valid inner queries and also the columns returned are depending of the function. Which kind of inner query will depend on the function(s) requirements. To simplify variety of types, ANY-INTEGER and ANY-NUMERICAL is used.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT


SQL de aristas

General

Edges SQL for

Columna

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice extremo de la arista.

target

ANY-INTEGER

Identificador del segundo vértice extremo de la arista.

cost

ANY-NUMERICAL

Weight of the edge (source, target)

reverse_cost

ANY-NUMERICAL

-1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

General without id

Edges SQL for

Columna

Tipo

x Defecto

Descripción

source

ANY-INTEGER

Identificador del primer vértice extremo de la arista.

target

ANY-INTEGER

Identificador del segundo vértice extremo de la arista.

cost

ANY-NUMERICAL

Weight of the edge (source, target)

reverse_cost

ANY-NUMERICAL

-1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

General with (X,Y)

Edges SQL for

Parámetro

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice extremo de la arista.

target

ANY-INTEGER

Identificador del segundo vértice extremo de la arista.

cost

ANY-NUMERICAL

Weight of the edge (source, target)

  • When negative: edge (source, target) does not exist, therefore it’s not part of the graph.

reverse_cost

ANY-NUMERICAL

-1

Weight of the edge (target, source),

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

x1

ANY-NUMERICAL

X coordinate of source vertex.

y1

ANY-NUMERICAL

Y coordinate of source vertex.

x2

ANY-NUMERICAL

X coordinate of target vertex.

y2

ANY-NUMERICAL

Y coordinate of target vertex.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Flow

Edges SQL for Flow - Familia de funciones.

Edges SQL for

Columna

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice extremo de la arista.

target

ANY-INTEGER

Identificador del segundo vértice extremo de la arista.

capacity

ANY-INTEGER

Weight of the edge (source, target)

reverse_capacity

ANY-INTEGER

-1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Edges SQL for the following functions of Flow - Familia de funciones.

Columna

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice extremo de la arista.

target

ANY-INTEGER

Identificador del segundo vértice extremo de la arista.

capacity

ANY-INTEGER

Capacity of the edge (source, target)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

reverse_capacity

ANY-INTEGER

-1

Capacity of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

cost

ANY-NUMERICAL

Weight of the edge (source, target) if it exist

reverse_cost

ANY-NUMERICAL

\(-1\)

Weight of the edge (target, source) if it exist

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Combinations SQL

Used on combination signatures

Parámetro

Tipo

Descripción

source

ANY-INTEGER

Identifier of the departure vertex.

target

ANY-INTEGER

Identifier of the arrival vertex.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT


Points SQL

Points SQL for

Parámetro

Tipo

x Defecto

Descripción

pid

ANY-INTEGER

value

Identifier of the point.

  • Use with positive value, as internally will be converted to negative value

  • If column is present, it can not be NULL.

  • If column is not present, a sequential negative value will be given automatically.

edge_id

ANY-INTEGER

Identificador de la arista «más cercano» al punto.

fraction

ANY-NUMERICAL

El valor en <0,1> que indica la posición relativa desde el primer punto final de la arista.

side

CHAR

b

Value in [b, r, l, NULL] indicating if the point is:

  • In the right r,

  • In the left l,

  • In both sides b, NULL

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Parámetros

The main parameter of the majority of the pgRouting functions is a query that selects the edges of the graph.

Parámetro

Tipo

Descripción

Edges SQL

TEXT

Edges SQL as described below.

Depending on the family or category of a function it will have additional parameters, some of them are compulsory and some are optional.

The compulsory parameters are nameless and must be given in the required order. The optional parameters are named parameters and will have a default value.

Parameters for the Via functions

Parámetro

Tipo

x Defecto

Descripción

Edges SQL

TEXT

SQL query as described.

via vertices

ARRAY[ ANY-INTEGER ]

Arreglo ordenados de identificadores de vértices que serán visitados.

directed

BOOLEAN

true

  • Cuando true el gráfo se considera Dirigido

  • Cuando false el gráfico se considera como No Dirigido

strict

BOOLEAN

false

  • When true if a path is missing stops and returns EMPTY SET

  • En caso de false, ignora las rutas faltantes y devuelve todas las rutas encontradas

U_turn_on_edge

BOOLEAN

true

  • When true departing from a visited vertex will not try to avoid using the edge used to reach it. In other words, U turn using the edge with same identifier is allowed.

  • When false when a departing from a visited vertex tries to avoid using the edge used to reach it. In other words, U turn using the edge with same identifier is used when no other path is found.

Return columns

Hay varios tipos de columnas devueltas que dependen de la función.


Return columns for a path

Used on functions that return one path solution

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

Columna

Tipo

Descripción

seq

INTEGER

Valor secuencial a partir de 1.

path_seq

INTEGER

Posición relativa en la ruta. Tiene el valor 1 para el principio de una ruta.

start_vid

BIGINT

Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta.

end_vid

BIGINT

Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta.

node

BIGINT

Identificador del nodo en la ruta de start_vid a end_vid.

edge

BIGINT

Identifier of the edge used to go from node to the next node in the path sequence. -1 for the last node of the path.

cost

FLOAT

Costo del desplazamiento desde node usando `` edge`` hasta el siguiente nodo en la secuencia de ruta.

agg_cost

FLOAT

Aggregate cost from start_vid to node.

Used on functions the following:

Returns set of (seq, path_seq [, start_pid] [, end_pid], node, edge, cost, agg_cost)

Columna

Tipo

Descripción

seq

INTEGER

Valor secuencial a partir de 1.

path_seq

INTEGER

Relative position in the path.

  • 1 For the first row of the path.

start_pid

BIGINT

Identifier of a starting vertex/point of the path.

  • When positive is the identifier of the starting vertex.

  • When negative is the identifier of the starting point.

  • Returned on Many to One and Many to Many

end_pid

BIGINT

Identifier of an ending vertex/point of the path.

  • When positive is the identifier of the ending vertex.

  • When negative is the identifier of the ending point.

  • Returned on One to Many and Many to Many

node

BIGINT

Identifier of the node in the path from start_pid to end_pid.

  • When positive is the identifier of the a vertex.

  • When negative is the identifier of the a point.

edge

BIGINT

Identifier of the edge used to go from node to the next node in the path sequence.

  • -1 for the last row of the path.

cost

FLOAT

Costo del desplazamiento desde node usando `` edge`` hasta el siguiente nodo en la secuencia de ruta.

  • 0 For the first row of the path.

agg_cost

FLOAT

Aggregate cost from start_vid to node.

  • 0 For the first row of the path.

Used on functions the following:

Returns set of (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

Columna

Tipo

Descripción

seq

INTEGER

Valor secuencial a partir de 1.

path_seq

INTEGER

Posición relativa en la ruta. Tiene el valor 1 para el principio de una ruta.

start_vid

BIGINT

Identifier of the starting vertex of the current path.

end_vid

BIGINT

Identifier of the ending vertex of the current path.

node

BIGINT

Identificador del nodo en la ruta de start_vid a end_vid.

edge

BIGINT

Identifier of the edge used to go from node to the next node in the path sequence. -1 for the last node of the path.

cost

FLOAT

Costo del desplazamiento desde node usando `` edge`` hasta el siguiente nodo en la secuencia de ruta.

agg_cost

FLOAT

Aggregate cost from start_vid to node.


Return columns for multiple paths

Used on functions that return many paths solutions

Set of (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)

Columna

Tipo

Descripción

seq

INTEGER

Valor secuencial a partir de 1.

path_id

INTEGER

Path identifier.

  • Has value 1 for the first of a path from start_vid to end_vid.

path_seq

INTEGER

Posición relativa en la ruta. Tiene el valor 1 para el principio de una ruta.

start_vid

BIGINT

Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta.

end_vid

BIGINT

Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta.

node

BIGINT

Identificador del nodo en la ruta de start_vid a end_vid.

edge

BIGINT

Identifier of the edge used to go from node to the next node in the path sequence. -1 for the last node of the path.

cost

FLOAT

Costo del desplazamiento desde node usando `` edge`` hasta el siguiente nodo en la secuencia de ruta.

agg_cost

FLOAT

Aggregate cost from start_vid to node.


Return columns for cost functions

Used in the following

Set of (start_vid, end_vid, agg_cost)

Columna

Tipo

Descripción

start_vid

BIGINT

Identificador del vértice inicial.

end_vid

BIGINT

Identificador del vértice final.

agg_cost

FLOAT

Coste agregado de start_vid a end_vid.

Used in the following

Set of (start_vid, end_vid, agg_cost)

Columna

Tipo

Descripción

start_vid

BIGINT

Identifier of the starting vertex or point.

  • When positive: is a vertex’s identifier.

  • When negative: is a point’s identifier.

end_vid

BIGINT

Identifier of the ending vertex or point.

  • When positive: is a vertex’s identifier.

  • When negative: is a point’s identifier.

agg_cost

FLOAT

Coste agregado de start_vid a end_vid.


Return columns for flow functions

Edges SQL for the following

Columna

Tipo

Descripción

seq

INT

Valor secuencial a partir de 1.

edge

BIGINT

Identificador de la arista en la consulta original(edges_sql).

start_vid

BIGINT

Identificador del primer vértice extremo de la arista.

end_vid

BIGINT

Identificador del segundo vértice extremo de la arista.

flujo

BIGINT

Flujo a través del arista en la dirección (start_vid, end_vid).

residual_capacity (capacidad residual)

BIGINT

Capacidad residual del arista en la dirección (start_vid, end_vid).

Edges SQL for the following functions of Flow - Familia de funciones.

Columna

Tipo

Descripción

seq

INT

Valor secuencial a partir de 1.

edge

BIGINT

Identificador de la arista en la consulta original(edges_sql).

origen

BIGINT

Identificador del primer vértice extremo de la arista.

objetivo

BIGINT

Identificador del segundo vértice extremo de la arista.

flujo

BIGINT

Flujo a través de la arista en la dirección (origen, destino).

residual_capacity (capacidad residual)

BIGINT

Capacidad residual de la arista en la dirección (origen, destino).

cost

FLOAT

El costo de enviar este flujo a través de la arista en la dirección (origen, destino).

agg_cost

FLOAT

El costo agregado.

Return columns for spanning tree functions

Edges SQL for the following

Returns SET OF (edge, cost)

Columna

Tipo

Descripción

edge

BIGINT

Identificador de la arista.

cost

FLOAT

Cost to traverse the edge.

Tópicos avanzados

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.

Ejemplo

Supongamos que tenemos una tabla «st» de bordes y una columna «one_way» que podría tener valores como:

  • “FT” - dirección unidireccional de la fuente para el nodo de destino.

  • “TF” - dirección unidireccional desde el nodo destino hasta el nodo fuente.

  • “B” - calle de doble sentido.

  • “”- campo vacío, suponer doble sentido.

  • <NULL> - Campo NULL, usar bandera de two_way_if_null, es decir, doble sentido cuando nulo.

Entonces se puede formar la siguiente consulta para analizar las calles unidireccionales para errores.

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;

Normalmente estos problemas son generados por una rotura en la red, la dirección un camino equivocado, quizás un error relacionado con niveles z o una red que no esté debidamente indicada con nodos.

Las herramientas anteriores no detectan todos los problemas de la red, pero identifican algunos problemas comunes. Hay otros problemas que son difíciles de detectar porque son más globales en su naturaleza como múltiples redes desconectadas. Piense usted en una isla con una red de carreteras que no está conectada a la red del continente porque faltan las rutas del puente o del ferry.

Consejos de Rendimiento

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');

Cómo contribuir

Wiki

Agregar funcionalidad a pgRouting

Consultar developer’s documentation

Índices y tablas