pgr_trsp - Camino más corto con giros restringidos (TRSP)¶
Nombre¶
pgr_trsp — Devuelve el camino más corto con soporte para restricciones de giros
Sinopsis¶
El Camino más corto con giros restringido (TRSP), es un algoritmo de camino más corto que puede tomar en cuenta complicadas restricciones de giro, como las encontrados en las redes de carreteras navegables reales. El rendimiento es casi tan rápido como la búsqueda A*, pero tiene muchas características adicionales como funcionalidad en base a los bordes en vez de basarse en los nodos de la red. Devuelve un conjunto de registros pgr_costResult (seq, id1, id2, costo) que conforman un camino.
pgr_costResult[] pgr_trsp(sql text, source integer, target integer,
directed boolean, has_rcost boolean [,restrict_sql text]);
pgr_costResult[] pgr_trsp(sql text, source_edge integer, source_pos double precision,
target_edge integer, target_pos double precision, directed boolean,
has_rcost boolean [,restrict_sql text]);
Descripción¶
El algoritmo del Camino más corto con giros restringidos (TRSP) es similar al de Algoritmo Shooting Star en cuanto a que puede uno especificar restricciones de giros.
La configuración del TRSP es parecido al del camino más corto de Dijkstra con el añadido de una tabla de restricciones de giros que es opcional. Esto hace que añadir restricciones de giro a una red de carreteras sea más fácil en comparación con del algoritmo de estrella fugaz en la que había que agregar los bordes varias veces cuando estaba involucrado en una restricción.
sql: | Consulta SQL que debe proporcionar un conjunto de registros con los siguientes campos: SELECT id, source, target, cost, [,reverse_cost] FROM edge_table
|
||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
source: | int4 identificador del nodo de partida |
||||||||||
target: | int4 identificador del nodo de llegada |
||||||||||
directed: | true Si la gráfica es direccionada |
||||||||||
has_rcost: | Si es True, el campo reverse_cost del conjunto de registros generados se utilizan para el calcular el costo de la travesía del borde en la dirección opuesta. |
||||||||||
restrict_sql: | (opcional) una consulta SQL, que debe proporcionar un conjunto de registros con los siguientes campos: SELECT to_cost, target_id, via_path FROM restrictions
|
Otra variante de TRSP que permite especificar el Identificador del borde de partida y de llegada junto con una fracción para interpolar la posición:
source_edge: | int4 identificador del borde de partida |
---|---|
source_pos: | float8 fracción de 1 que define la posición del sobre el borde de partida. |
target_edge: | int4 Identificador del borde de llegada |
target_pos: | float8 fracción de 1 que define la posición del sobre el borde de llegada. |
Devuelve un conjunto del tipo de datos pgr_costResult[]:
seq: | Secuencia de registros |
---|---|
id1: | Identificador del nodo visitado |
id2: | identificador del borde (-1 para el último borde) |
cost: | Costo para el recorrido desde el nodo id1 usando el borde id2 hasta su otro extremo |
Historia
- Nuevo en la versión 2.0.0
Ejemplos¶
- Sin restricción de giros
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_trsp(
'SELECT id, source, target, cost FROM edge_table',
7, 12, false, false
);
seq | node | edge | cost
----+------+------+------
0 | 7 | 6 | 1
1 | 8 | 7 | 1
2 | 5 | 8 | 1
3 | 6 | 11 | 1
4 | 11 | 13 | 1
5 | 12 | -1 | 0
(6 rows)
- Con restricción de giros
Las restricciones de giro requieren de información adicional, que puede ser almacenado en una tabla por separado:
CREATE TABLE restrictions (
rid serial,
to_cost double precision,
to_edge integer,
from_edge integer,
via text
);
INSERT INTO restrictions VALUES (1,100,7,4,null);
INSERT INTO restrictions VALUES (2,4,8,3,5);
INSERT INTO restrictions VALUES (3,100,9,16,null);
Entonces una consulta con restricciones de giro es creada de la siguiente forma:
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_trsp(
'SELECT id, source, target, cost FROM edge_table',
7, 12, false, false,
'SELECT to_cost, to_edge AS target_id,
from_edge || coalesce('','' || via, '''') AS via_path
FROM restrictions'
);
seq | node | edge | cost
-----+------+------+------
0 | 7 | 6 | 1
1 | 8 | 7 | 1
2 | 5 | 8 | 1
3 | 6 | 11 | 1
4 | 11 | 13 | 1
5 | 12 | -1 | 0
(6 rows)
Las consultas usan la red de ejemplo Datos Muestra