pgr_trspVia¶
pgr_trspVia Route that goes through a list of vertices with restrictions.
Disponibilidad
Version 4.0.0
Function promoted to official.
Versión 3.4.0
New proposed function.
Descripción¶
Given a list of vertices and a graph, this function is equivalent to finding the shortest path between \(vertex_i\) and \(vertex_{i+1}\) for all \(i < size\_of(via\;vertices)\) trying not to use restricted paths.
Las trayectorias representan los tramos de la ruta.
The general algorithm is as follows:
Execute a pgr_dijkstraVia - Propuesto.
For the set of sub paths of the solution that pass through a restriction then
Execute the TRSP algorithm with restrictions for the paths.
NOTE when this is done,
U_turn_on_edgeflag is ignored.
Boost Graph Inside
Firmas¶
Una Vía¶
[directed, strict, U_turn_on_edge](seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost, route_agg_cost)- Ejemplo:
Encontrar la ruta que visita los vértices \({5, 1, 8\}\) en ese orden en un grafo dirigido.
SELECT * FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 1, 8]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 5 | 1 | 5 | 1 | 1 | 0 | 0
2 | 1 | 2 | 5 | 1 | 6 | 4 | 1 | 1 | 1
3 | 1 | 3 | 5 | 1 | 7 | 10 | 1 | 2 | 2
4 | 1 | 4 | 5 | 1 | 8 | 12 | 1 | 3 | 3
5 | 1 | 5 | 5 | 1 | 12 | 13 | 1 | 4 | 4
6 | 1 | 6 | 5 | 1 | 17 | 15 | 1 | 5 | 5
7 | 1 | 7 | 5 | 1 | 16 | 9 | 1 | 6 | 6
8 | 1 | 8 | 5 | 1 | 11 | 8 | 1 | 7 | 7
9 | 1 | 9 | 5 | 1 | 7 | 7 | 1 | 8 | 8
10 | 1 | 10 | 5 | 1 | 3 | 6 | 1 | 9 | 9
11 | 1 | 11 | 5 | 1 | 1 | -1 | 0 | 10 | 10
12 | 2 | 1 | 1 | 8 | 1 | 6 | 1 | 0 | 10
13 | 2 | 2 | 1 | 8 | 3 | 7 | 1 | 1 | 11
14 | 2 | 3 | 1 | 8 | 7 | 10 | 101 | 2 | 12
15 | 2 | 4 | 1 | 8 | 8 | -2 | 0 | 103 | 113
(15 rows)
Parámetros¶
Parámetro |
Tipo |
Descripción |
|---|---|---|
|
SQL de aristas como se describen. |
|
|
SQL de restricciones consulta como se describe. |
|
vértices |
|
Arreglo ordenado de identificadores de vértices que serán visitados. |
Donde:
- ENTEROS:
SMALLINT, INTEGER, BIGINT
Parámetros opcionales¶
Columna |
Tipo |
x Defecto |
Descripción |
|---|---|---|---|
|
|
|
|
Parámetros opcionales Vía¶
Parámetro |
Tipo |
x Defecto |
Descripción |
|---|---|---|---|
|
|
|
|
|
|
|
|
Consultas Internas¶
SQL aristas¶
Columna |
Tipo |
x Defecto |
Descripción |
|---|---|---|---|
|
ENTEROS |
Identificador de la arista. |
|
|
ENTEROS |
Identificador del primer vértice de la arista. |
|
|
ENTEROS |
Identificador del segundo vértice de la arista. |
|
|
FLOTANTES |
Peso de la arista ( |
|
|
FLOTANTES |
-1 |
Peso de la arista (
|
Donde:
- ENTEROS:
SMALLINT,INTEGER,BIGINT- FLOTANTES:
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
SQL restricciones¶
Columna |
Tipo |
Descripción |
|---|---|---|
|
|
Secuencia de identificadores de aristas que forman un camino que no se permite tomar. - Arreglos vacios o |
|
FLOTANTES |
Costo de tomar el camino prohibido. |
Donde:
- ENTEROS:
SMALLINT,INTEGER,BIGINT- FLOTANTES:
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Columnas de resultados¶
Columna |
Tipo |
Descripción |
|---|---|---|
|
|
Valor secuencial a partir de 1. |
|
|
Identificador del camino. Tiene valor 1 para el primer camino. |
|
|
Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta. |
|
|
Identificador del vértice inicial de la ruta. |
|
|
Identificador del vértice final de la ruta. |
|
|
Identificador del nodo en la ruta de |
|
|
Identificador de la arsita utilizada para ir del
|
|
|
Costo para atravesar desde |
|
|
Costo agregado desde |
|
|
Costo total desde |
Ejemplos Adicionales¶
Todos estos ejemplos son sobre la ruta que visita los vértices \(\{5, 7, 1, 8, 15\}\) en ese orden, en un grafo dirigido.
La consulta principal¶
SELECT * FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 5 | 7 | 5 | 1 | 1 | 0 | 0
2 | 1 | 2 | 5 | 7 | 6 | 4 | 1 | 1 | 1
3 | 1 | 3 | 5 | 7 | 7 | -1 | 0 | 2 | 2
4 | 2 | 1 | 7 | 1 | 7 | 7 | 1 | 0 | 2
5 | 2 | 2 | 7 | 1 | 3 | 6 | 1 | 1 | 3
6 | 2 | 3 | 7 | 1 | 1 | -1 | 0 | 2 | 4
7 | 3 | 1 | 1 | 8 | 1 | 6 | 1 | 0 | 4
8 | 3 | 2 | 1 | 8 | 3 | 7 | 1 | 1 | 5
9 | 3 | 3 | 1 | 8 | 7 | 10 | 101 | 2 | 6
10 | 3 | 4 | 1 | 8 | 8 | -1 | 0 | 103 | 107
11 | 4 | 1 | 8 | 15 | 8 | 12 | 1 | 0 | 107
12 | 4 | 2 | 8 | 15 | 12 | 13 | 1 | 1 | 108
13 | 4 | 3 | 8 | 15 | 17 | 15 | 1 | 2 | 109
14 | 4 | 4 | 8 | 15 | 16 | 16 | 1 | 3 | 110
15 | 4 | 5 | 8 | 15 | 15 | -2 | 0 | 4 | 111
(15 rows)
Costo agregado de la tercera ruta.¶
SELECT agg_cost FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge < 0;
agg_cost
----------
103
(1 row)
Costo agregado al final de la tercera ruta.¶
SELECT route_agg_cost FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge < 0;
route_agg_cost
----------------
107
(1 row)
Nodos visitados en la ruta.¶
SELECT row_number() over () as node_seq, node
FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE edge <> -1 ORDER BY seq;
node_seq | node
----------+------
1 | 5
2 | 6
3 | 7
4 | 3
5 | 1
6 | 3
7 | 7
8 | 8
9 | 12
10 | 17
11 | 16
12 | 15
(12 rows)
Costo agregado de la ruta al llegar a los vértices visitados.¶
SELECT path_id, route_agg_cost FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE edge < 0;
path_id | route_agg_cost
---------+----------------
1 | 2
2 | 4
3 | 107
4 | 111
(4 rows)
Estado de «pasa enfrente» o «visita» los nodos.¶
SELECT seq, route_agg_cost, node, agg_cost ,
CASE WHEN edge = -1 THEN $$visits$$
ELSE $$passes in front$$
END as status
FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[5, 7, 1, 8, 15])
WHERE agg_cost <> 0 or seq = 1;
seq | route_agg_cost | node | agg_cost | status
-----+----------------+------+----------+-----------------
1 | 0 | 5 | 0 | passes in front
2 | 1 | 6 | 1 | passes in front
3 | 2 | 7 | 2 | visits
5 | 3 | 3 | 1 | passes in front
6 | 4 | 1 | 2 | visits
8 | 5 | 3 | 1 | passes in front
9 | 6 | 7 | 2 | passes in front
10 | 107 | 8 | 103 | visits
12 | 108 | 12 | 1 | passes in front
13 | 109 | 17 | 2 | passes in front
14 | 110 | 16 | 3 | passes in front
15 | 111 | 15 | 4 | passes in front
(12 rows)
Sumulación del functionamiento del algoritmo.¶
The algorithm performs a pgr_dijkstraVia - Propuesto
SELECT * FROM pgr_dijkstraVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
ARRAY[6, 3, 6]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 6 | 3 | 6 | 4 | 1 | 0 | 0
2 | 1 | 2 | 6 | 3 | 7 | 7 | 1 | 1 | 1
3 | 1 | 3 | 6 | 3 | 3 | -1 | 0 | 2 | 2
4 | 2 | 1 | 3 | 6 | 3 | 7 | 1 | 0 | 2
5 | 2 | 2 | 3 | 6 | 7 | 4 | 1 | 1 | 3
6 | 2 | 3 | 3 | 6 | 6 | -2 | 0 | 2 | 4
(6 rows)
Detects which of the sub paths pass through a restriction in this case is for
the path_id = 5 from 6 to 3 because the path \(15 \rightarrow 1\)
is restricted.
Executes the pgr_trsp algorithm for the conflicting paths.
SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
6, 3);
path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 3 | 6 | 4 | 1 | 0
1 | 2 | 6 | 3 | 7 | 10 | 1 | 1
1 | 3 | 6 | 3 | 8 | 12 | 1 | 2
1 | 4 | 6 | 3 | 12 | 13 | 1 | 3
1 | 5 | 6 | 3 | 17 | 15 | 1 | 4
1 | 6 | 6 | 3 | 16 | 9 | 1 | 5
1 | 7 | 6 | 3 | 11 | 8 | 1 | 6
1 | 8 | 6 | 3 | 7 | 7 | 1 | 7
1 | 9 | 6 | 3 | 3 | -1 | 0 | 8
(9 rows)
From the pgr_dijkstraVia - Propuesto result it removes the conflicting paths and builds the solution with the results of the pgr_trsp algorithm:
WITH
solutions AS (
SELECT path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_dijkstraVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
ARRAY[6, 3, 6]) WHERE path_id != 1
UNION
SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
6, 3)),
with_seq AS (
SELECT row_number() over(ORDER BY path_id, path_seq) AS seq, *
FROM solutions),
aggregation AS (SELECT seq, SUM(cost) OVER(ORDER BY seq) AS route_agg_cost FROM with_seq)
SELECT with_seq.*, COALESCE(route_agg_cost, 0) AS route_agg_cost
FROM with_seq LEFT JOIN aggregation ON (with_seq.seq = aggregation.seq + 1);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 6 | 3 | 6 | 4 | 1 | 0 | 0
2 | 1 | 2 | 6 | 3 | 7 | 10 | 1 | 1 | 1
3 | 1 | 3 | 6 | 3 | 8 | 12 | 1 | 2 | 2
4 | 1 | 4 | 6 | 3 | 12 | 13 | 1 | 3 | 3
5 | 1 | 5 | 6 | 3 | 17 | 15 | 1 | 4 | 4
6 | 1 | 6 | 6 | 3 | 16 | 9 | 1 | 5 | 5
7 | 1 | 7 | 6 | 3 | 11 | 8 | 1 | 6 | 6
8 | 1 | 8 | 6 | 3 | 7 | 7 | 1 | 7 | 7
9 | 1 | 9 | 6 | 3 | 3 | -1 | 0 | 8 | 8
10 | 2 | 1 | 3 | 6 | 3 | 7 | 1 | 0 | 8
11 | 2 | 2 | 3 | 6 | 7 | 4 | 1 | 1 | 9
12 | 2 | 3 | 3 | 6 | 6 | -2 | 0 | 2 | 10
(12 rows)
Getting the same result as pgr_trspVia:
SELECT * FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[6, 3, 6]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 6 | 3 | 6 | 4 | 1 | 0 | 0
2 | 1 | 2 | 6 | 3 | 7 | 10 | 1 | 1 | 1
3 | 1 | 3 | 6 | 3 | 8 | 12 | 1 | 2 | 2
4 | 1 | 4 | 6 | 3 | 12 | 13 | 1 | 3 | 3
5 | 1 | 5 | 6 | 3 | 17 | 15 | 1 | 4 | 4
6 | 1 | 6 | 6 | 3 | 16 | 9 | 1 | 5 | 5
7 | 1 | 7 | 6 | 3 | 11 | 8 | 1 | 6 | 6
8 | 1 | 8 | 6 | 3 | 7 | 7 | 1 | 7 | 7
9 | 1 | 9 | 6 | 3 | 3 | -1 | 0 | 8 | 8
10 | 2 | 1 | 3 | 6 | 3 | 7 | 1 | 0 | 8
11 | 2 | 2 | 3 | 6 | 7 | 4 | 1 | 1 | 9
12 | 2 | 3 | 3 | 6 | 6 | -2 | 0 | 2 | 10
(12 rows)
- Ejemplo 8:
Sometimes
U_turn_on_edgeflag is ignored when is set tofalse.
The first step, doing a pgr_dijkstraVia - Propuesto does consider not making a U turn on the same edge. But the path \(16 \rightarrow 13\) (Rows 4 and 5) is restricted and the result is using it.
SELECT * FROM pgr_dijkstraVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
ARRAY[6, 7, 6], U_turn_on_edge => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 6 | 7 | 6 | 4 | 1 | 0 | 0
2 | 1 | 2 | 6 | 7 | 7 | -1 | 0 | 1 | 1
3 | 2 | 1 | 7 | 6 | 7 | 8 | 1 | 0 | 1
4 | 2 | 2 | 7 | 6 | 11 | 9 | 1 | 1 | 2
5 | 2 | 3 | 7 | 6 | 16 | 16 | 1 | 2 | 3
6 | 2 | 4 | 7 | 6 | 15 | 3 | 1 | 3 | 4
7 | 2 | 5 | 7 | 6 | 10 | 2 | 1 | 4 | 5
8 | 2 | 6 | 7 | 6 | 6 | -2 | 0 | 5 | 6
(8 rows)
When executing the pgr_trsp algorithm for the conflicting path, there is
no U_turn_on_edge flag.
SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
7, 6);
path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 7 | 6 | 7 | 4 | 1 | 0
1 | 2 | 7 | 6 | 6 | -1 | 0 | 1
(2 rows)
Therefore the result ignores the U_turn_on_edge flag when set to false.
SELECT * FROM pgr_trspVia(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$,
$$SELECT path, cost FROM restrictions$$,
ARRAY[6, 7, 6], U_turn_on_edge => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 6 | 7 | 6 | 4 | 1 | 0 | 0
2 | 1 | 2 | 6 | 7 | 7 | -1 | 0 | 1 | 1
3 | 2 | 1 | 7 | 6 | 7 | 4 | 1 | 0 | 1
4 | 2 | 2 | 7 | 6 | 6 | -2 | 0 | 1 | 2
(4 rows)
Ver también¶
Índices y tablas