pgr_trsp - Plus court chemin avec restriction de virage (TRSP)¶

Nom¶

pgr_trsp — Retourne le plus court chemin avec support pour les restrictions de virage.

Synopsis¶

Le plus court chemin avec restriction de virage (TRSP) est un algorithme de plus court chemin qui peut optionnellement prendre en compte les restrictions comme celles trouvées dans les réseaux routiers navigables réels. La performance est pratiquement aussi rapide que la recherche A* mais a beaucoup de fonctionnalités additionnelles puisque fonctionnant avec des arêtes plus qu’avec des nœuds du réseau. Retourne un ensemble de lignes pgr_costResult (seq, id1, id2, cost), qui constituent un chemin.

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

Description¶

L’algorithme de plus court chemin avec restriction de virage (TRSP) est similaire au Algorithme Shooting Star dans lequel vous pouvez spécifier les restrictions de virage.

La configuration TRSP est essentiellement la même que Dijkstra shortest path avec l’addition d’une table optionnelle de restrictions de virage. Cela rend plus facile l’ajout des restrictions de virage à un réseau routier, que d’essayer de les ajouter au Shooting Star où vous aviez à ajouter les mêmes arêtes plusieurs fois si vous étiez impliqués dans une restriction.

sql:

une requête SQL, qui devrait retourner un ensemble de lignes avec les colonnes suivantes :

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

id:	`int4` identifiant de l’arête
source:	`int4` identifiant du sommet source
target:	`int4` identifiant du sommet cible
cost:	`float8` valeur, du coût de l’arête traversée. Un coût négatif va prévenir l’arête d’être insérée dans le graphe.
reverse_cost:	(optionnel) le coût pour la traversée inverse de l’arête. Ceci est seulement utilisé quand les paramètres `directed` et `has_rcost` sont `true` (voir la remarque ci-dessus sur les coûts négatifs).

source:

int4 NODE id du point de départ

target:

int4 NODE id du point final

directed:

true si le graphe est dirigé

has_rcost:

si true, la colonne reverse_cost du SQL générant l’ensemble des lignes va être utilisé pour le coût de la traversée de l’arête dans la direction opposée.

restrict_sql:

(optionnel) une requête SQL, qui devrait retourner un ensemble de lignes avec les colonnes suivantes :

SELECT to_cost, target_id, via_path FROM restrictions

to_cost:	`float8` coût de restriction de virage
target_id:	`int4` id cible
via_path:	`text` liste séparée par virgule d’arêtes dans l’ordre inverse de `rule`

Un autre variante de TRSP autorise de spécifier EDGE id de source et cible ensemble avec une fraction pour interpoler la position :

source_edge:	`int4` EDGE id d’une arête de départ
source_pos:	`float8` fraction de 1 définit la position de l’arête de départ
target_edge:	`int4` EDGE id de l’arête finale
target_pos:	`float8` fraction de 1 définit la position de l’arête finale

Retourne un ensemble de pgr_costResult[]:

seq:	séquence de ligne
id1:	ID noeud
id2:	ID arête (`-1` pour la dernière ligne)
cost:	coût pour traverser à partir de `id1` en utilisant `id2`

Histoire

Nouveau depuis la version 2.0.0

Exemples¶

Sans restrictions de virage

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)

Avec restrictions de virage

Les restrictions de virage requièrent des informations additionnelles, qui peuvent être stockées dans une table séparée :

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

Ensuite une requête avec des restrictions de virage est créée comme :

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)

Les requêtes utilisent le réseau Données d’échantillon.

Voir aussi¶

pgr_costResult[]

pgRouting Manual (2.0.0)