Conceptos de pgRouting ¶

Contenido

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
Cargar Datos
Construir una Topología de Ruteo
Compruebe la Topología de Ruteo
Calcular una Ruta

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.

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

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.

pgr_dijkstra

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:

Uno a Uno
Uno a Muchos
Muchos a Uno
Muchos a Muchos
Combinaciones

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 ¶

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

Hay varios tipos de consultas internas válidas y también las columnas devueltas dependen de la función. El tipo de consulta interna dependerá de los requisitos de las funcion(es). Para simplificar la variedad de tipos, se utiliza ANY-INTEGER y ANY-NUMERICAL.

Donde:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

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

Columna	Tipo	Valores predeterminados	Descripción
id	`ANY-INTEGER`		Identificador de la arista.
origen	`ANY-INTEGER`		Identificador del primer punto final en el vértice de la arista.
objetivo	`ANY-INTEGER`		Identificador del segundo punto final en el vértice de la arista.
cost	`ANY-NUMERICAL`		Peso de la arista (source, target) Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_cost	`ANY-NUMERICAL`	-1	Peso de la arista (target, source), En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

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

edges_sql: Una consulta SQL, que debe regresar un conjunto de filas con las siguientes columnas:

Columna	Tipo	Valores predeterminados	Descripción
origen	`ANY-INTEGER`		Identificador del primer punto final en el vértice de la arista.
objetivo	`ANY-INTEGER`		Identificador del segundo punto final en el vértice de la arista.
cost	`ANY-NUMERICAL`		Peso de la arista (source, target) Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_cost	`ANY-NUMERICAL`	-1	Peso de la arista (target, source), En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Parámetros ¶

Parámetro	Tipo	Valores predeterminados	Descripción
edges_sql	`TEXT`		Consulta SQL como se describió anteriormente.
via_vertices	`ARRAY[ANY-INTEGER]`		Arreglo de identificadores de vértices ordenados que serán visitados.
dirigido	`BOOLEAN`	`true`	Cuando `true` el gráfo se considera Dirigido Cuando `false` el gráfico se considera como No Dirigido
strict	`BOOLEAN`	`false`	En caso de `false`, ignora las rutas faltantes y devuelve todas las rutas encontradas en caso de `true` si falta una ruta de acceso se detiene y devuelve EMPTY SET
U_turn_on_edge	`BOOLEAN`	`true`	En caso de `true` saliendo de un vértice visitado no intentará evitar el uso de la arista utilizada para alcanzarlo. En otras palabras, se permite el giro U utilizando la arista con el mismo “id”. En caso de `false` cuando una salida de un vértice visitado intenta evitar el uso de la arista utilizada para alcanzarlo. En otras palabras, se utiliza el giro U utilizando el borde con el mismo id cuando no se encuentra ninguna otra ruta.

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

edges_sql: Una consulta SQL, que debe regresar un conjunto de filas con las siguientes columnas:

Columna	Tipo	Valores predeterminados	Descripción
id	`ANY-INTEGER`		Identificador de la arista.
origen	`ANY-INTEGER`		Identificador del primer punto final en el vértice de la arista.
objetivo	`ANY-INTEGER`		Identificador del segundo punto final en el vértice de la arista.
cost	`ANY-NUMERICAL`		Peso de la arista (source, target) Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_cost	`ANY-NUMERICAL`	-1	Peso de la arista (target, source), En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.
x1	`ANY-NUMERICAL`		Coordenada X del vértice source.
y1	`ANY-NUMERICAL`		Coordenada Y del vértice source.
x2	`ANY-NUMERICAL`		Coordenada X del vértice objetivo.
y2	`ANY-NUMERICAL`		Coordenada Y del vértice target.

Donde:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Para pgr_pushRelabel, pgr_edmondsKarp, pgr_boykovKolmogorov :

Edges SQL: Consulta SQL de un grafo dirigido de capacidades, que debe devolver un conjunto de filas con las siguientes columnas:

Columna	Tipo	Valores predeterminados	Descripción
id	`ANY-INTEGER`		Identificador de la arista.
origen	`ANY-INTEGER`		Identificador del primer punto final en el vértice de la arista.
objetivo	`ANY-INTEGER`		Identificador del segundo punto final en el vértice de la arista.
capacidad	`ANY-INTEGER`		Peso de la arista (source, target) Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_capacity (capacidad inversa)	`ANY-INTEGER`	-1	Peso de la arista (target, source), En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT

Para pgr_maxFlowMinCost - Experimental and pgr_maxFlowMinCost_Cost - Experimental:

Edges SQL: Consulta SQL de un grafo dirigido de capacidades, que debe devolver un conjunto de filas con las siguientes columnas:

Columna	Tipo	Valores predeterminados	Descripción
id	`ANY-INTEGER`		Identificador de la arista.
origen	`ANY-INTEGER`		Identificador del primer punto final en el vértice de la arista.
objetivo	`ANY-INTEGER`		Identificador del segundo punto final en el vértice de la arista.
capacidad	`ANY-INTEGER`		Capacidad de la arista (origen, destino) Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_capacity (capacidad inversa)	`ANY-INTEGER`	-1	Capacidad de la arista (destino, origen), En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.
cost	`ANY-NUMERICAL`		Peso de la arista (origen, destino) si existe.
reverse_cost	`ANY-NUMERICAL`	0	Peso de la arista (destino, origen) si existe.

Donde:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL: smallint, int, bigint, real, float

Descripción de la consulta SSQL de Puntos

points_sql: Una consulta SQL, que debe regresar un conjunto de filas con las siguientes columnas:

Columna	Tipo	Descripción
pid	`ANY-INTEGER`	(opcional) Identificador del punto. Si la columna está presente, no puede ser NULL. Si la columna no está presente, se proporcionará automáticamente un identificador secuencial.
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`	(opcional) Valor en [“b”, “r”, “l”, NULL] que indica si el punto es: A la derecha, a la izquierda del borde o Si no importa con “b” o NULL. Si la columna no presente “b” es considerada

Donde:

ANY-INTEGER: smallint, int, bigint
ANY-NUMERICAL: smallint, int, bigint, real, float

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

Columna	Tipo	Valores predeterminados	Descripción
origen	`ANY-INTEGER`		Identificador del primer punto final en el vértice de la arista.
objetivo	`ANY-INTEGER`		Identificador del segundo punto final en el vértice de la arista.

Donde:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT

Devolución de columnas y valores ¶

Valores devueltos para una ruta
Valores devueltos para varias rutas desde el mismo origen y destino
Descripción de los valores devueltos para una función Cost Matrix - Categoría
Descripción de los valores devueltos

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

Valores devueltos para una ruta ¶

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

Columna	Tipo	Descripción
seq	`INT`	Valor secuencial a partir de 1.
path_seq	`INT`	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. Muchos a Uno Muchos a Muchos
end_vid	`BIGINT`	Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta. Uno a Muchos Muchos a Muchos
node	`BIGINT`	Identificador del nodo en la ruta de `start_vid` a `end_vid`.
edge	`BIGINT`	Identificador del borde utilizado para ir del `nodo` al siguiente nodo de la secuencia de ruta. `-1` para el último nodo de la ruta.
cost	`FLOAT`	Costo de desplazamiento desde `node` usando `` edge`` hasta el siguiente nodo en la secuencia de ruta.
agg_cost	`FLOAT`	Coste agregado de `start_v` to `node`.

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)

Columna	Tipo	Descripción
seq	`INT`	Valor secuencial a partir de 1.
path_id	`INT`	Identificador de ruta. Tiene el valor 1 para el primero de una ruta. Se utiliza cuando hay varias rutas para la misma combinación de `start_vid` a `end_vid`.
path_seq	`INT`	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. Muchos a Uno Muchos a Muchos
end_vid	`BIGINT`	Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta. Uno a Muchos Muchos a Muchos
node	`BIGINT`	Identificador del nodo en la ruta de `start_vid` a `end_vid`.
edge	`BIGINT`	Identificador del borde utilizado para ir del `nodo` al siguiente nodo de la secuencia de ruta. `-1` para el último nodo de la ruta.
cost	`FLOAT`	Costo de desplazamiento desde `node` usando `` edge`` hasta el siguiente nodo en la secuencia de ruta.
agg_cost	`FLOAT`	Coste agregado de `start_v` to `node`.

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

Devuelve 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`.

Descripción de los valores devueltos ¶

Para pgr_pushRelabel, pgr_edmondsKarp, pgr_boykovKolmogorov :

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 punto final en el vértice de la arista.
end_vid	`BIGINT`	Identificador del segundo punto final en el vértice 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`).

Para pgr_maxFlowMinCost - Experimental

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 punto final en el vértice de la arista.
objetivo	`BIGINT`	Identificador del segundo punto final en el vértice 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.

Tópicos avanzados ¶

Topología para Ruteo
Análisis de gráficas
Analizar un gráfico
Analizar las calles unidireccionales
- Ejemplo

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.

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

Edita una página existente pgRouting Wiki
O crea una nueva página Wiki
- Crear una página en el pgRouting Wiki
- Asigne al título un nombre apropiado
Example

Agregar funcionalidad a pgRouting

Consultar developer’s documentation

Índices y tablas

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

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