pgRouting Manual (2.0.0)

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

«  pgr_tsp - Voyageur du commerce   ::   Contenu   ::   With Driving Distance Enabled  »

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_tsp - Voyageur du commerce   ::   Contenu   ::   With Driving Distance Enabled  »