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.

SELECT id, source, target, cost, [,reverse_cost] FROM edge_table

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:

Devuelve un conjunto del tipo de datos pgr_costResult[]:

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

Véase también¶

• pgr_costResult[]