Bienvenue sur PostGIS.fr

Bienvenue sur PostGIS.fr , le site de la communauté des utilisateurs francophones de PostGIS.

PostGIS ajoute le support d'objets géographique à la base de données PostgreSQL. En effet, PostGIS "spatialise" le serverur PostgreSQL, ce qui permet de l'utiliser comme une base de données SIG.

Maintenu à jour, en fonction de nos disponibilités et des diverses sorties des outils que nous testons, nous vous proposons l'ensemble de nos travaux publiés en langue française.

source: trunk/workshop-routing-foss4g/chapters/shortest_path.rst @ 75

Revision 75, 15.7 KB checked in by djay, 13 years ago (diff)

Traduction du chapitre 6

Plus courts chemins

pgRouting été initialement appelé pgDijkstra, puisque il implémentait seulement la recherche de plus court chemin à l'aide de l'agorithme de Dijkstra. Plus tard, d'uatres fonctions se sont ajoutées et la bibliotÚque fut renommée.

images/route.png

Ce chapitre explique les trois différents algorithmes et les attributs nécessaires.

Note

Si vous lancez l'outils :doc:`osm2pgrouting <osm2pgrouting>` pour importer des données OpenStreetMap, la table des chemins (ways) contient déjà tout les attributs nécessaires pour utiliser les fonctions de recherche de plus court chemins. Au contraire, la table ways de la base de données pgrouting-workshop du :doc:`chapitre précédent <topology>` manque d'un certain nombre d'attributs, qui sont présentés dans ce chapitre dans les Prérequis.

System Message: ERROR/3 (<string>, line 16); backlink

Unknown interpreted text role "doc".

System Message: ERROR/3 (<string>, line 16); backlink

Unknown interpreted text role "doc".

Dijkstra

L'algorithme de Dijkstraa été la premiÚre implémentation disponible dans pgRouting. Il ne nécessite pas d'autre attributs que les champs source et target, les attributs id et cost. Il peut être utilisé sur des graphes orientés ou non. Vous pouvez spécifier que votre réseau à un coût de parcours inverse (reverse cost) ou non.

Prérequis

Pour être en mesure d'utiliser un coût de parcuors invers, vous devez ajouter une colonne de coût. Nous pouvons affecter la longuer au coût de parcours inverse.

ALTER TABLE ways ADD COLUMN reverse_cost double precision;
UPDATE ways SET reverse_cost = length;

Fonction avec paramÚtres

shortest_path( sql text,
                   source_id integer,
                   target_id integer,
                   directed boolean,
                   has_reverse_cost boolean )

Note

  • Les identifiant pour source et target sont les identifiant des noeuds.
  • Graphes non-orientés ("directed=false") implique que le paramÚtre "has_reverse_cost" est ignoré

Bases

Chaque algorithme a une fonction de base.

SELECT * FROM shortest_path('
                SELECT gid as id,
                         source::integer,
                         target::integer,
                         length::double precision as cost
                        FROM ways',
                5700, 6733, false, false);

 vertex_id | edge_id |        cost
-----------+---------+---------------------
      5700 |    6585 |   0.175725539559539
      5701 |   18947 |   0.178145491343884
      2633 |   18948 |   0.177501253416424
       ... |     ... |                 ...
      6733 |      -1 |                   0
 (38 rows)

Enveloppe

Enveloppe SANS limite d'étendue

les fonctions enveloppes sont des fonctions qui étendent les fonctions de bases en y ajoutant des transformations, ajoutant des limites de l'étendue géograhpique de la recherhe, etc.. Les enveloppes peuvent changer le format et l'ordre des résultats. Il affectent aussi automatiquement certains paramÚtre et rend l'utilisation de pgRouting encore plsu simple.

SELECT gid, AsText(the_geom) AS the_geom
        FROM dijkstra_sp('ways', 5700, 6733);

  gid   |                              the_geom
--------+---------------------------------------------------------------
   5534 | MULTILINESTRING((-104.9993415 39.7423284, ... ,-104.9999815 39.7444843))
   5535 | MULTILINESTRING((-104.9999815 39.7444843, ... ,-105.0001355 39.7457581))
   5536 | MULTILINESTRING((-105.0001355 39.7457581,-105.0002133 39.7459024))
    ... | ...
  19914 | MULTILINESTRING((-104.9981408 39.7320938,-104.9981194 39.7305074))
(37 rows)

Note

Il est possible de visualiser le chemin dans QGIS. Cela fonctionne pour la requête de recherche du plus court chemin qui retourne une colonne géométrique.

  • Créer la connexion à la base de données et ajoutez la table route comme couche de fond.
  • Ajoutez une autre couche de la table "ways" mais selectionnez l'option Build query avant de l'ajouter.
  • Saissez "gid"  IN ( SELECT gid FROM dijkstra_sp('ways',5700,6733)) dans le champ SQL where clause.

SQL query peut aussi être sélectionné depuis le menu contextuel de la couche.

Enveloppe AVEC une étendue limite

Vous pouvez limiter votre recherche à une zone précise en ajoutant un cadre limite. Cela améliorera les performances tout spécialement pour les réseaux volumineux.

SELECT gid, AsText(the_geom) AS the_geom
        FROM dijkstra_sp_delta('ways', 5700, 6733, 0.1);

  gid   |                              the_geom
--------+---------------------------------------------------------------
   5534 | MULTILINESTRING((-104.9993415 39.7423284, ... ,-104.9999815 39.7444843))
   5535 | MULTILINESTRING((-104.9999815 39.7444843, ... ,-105.0001355 39.7457581))
   5536 | MULTILINESTRING((-105.0001355 39.7457581,-105.0002133 39.7459024))
    ... | ...
  19914 | MULTILINESTRING((-104.9981408 39.7320938,-104.9981194 39.7305074))
(37 rows)

Note

La projection des données OSM est en "degrés", donc nous définirons un cadre limite contenant le point de départ et celui d'arrivée plus une zone tampon de 0.1 degrés par exemple.

A-Étoile

L'algortihme A-Étoile est un autre algrithme bien connu. Il ajoute l'information de la position géographique du début et la fin de chaque tronçon. Cela permet une recherche privilégiant les tronçons proches du point d'arrivée de la recherche.

Prérequis

Pour A-* vous avez besoin de préparer votre table de réseau et d'y ajouter les colonnes latitute/longitude (x1, y1 et x2, y2) et de calculer leur valeurs.

ALTER TABLE ways ADD COLUMN x1 double precision;
ALTER TABLE ways ADD COLUMN y1 double precision;
ALTER TABLE ways ADD COLUMN x2 double precision;
ALTER TABLE ways ADD COLUMN y2 double precision;
UPDATE ways SET x1 = x(ST_startpoint(the_geom));
UPDATE ways SET y1 = y(ST_startpoint(the_geom));
UPDATE ways SET x2 = x(ST_endpoint(the_geom));
UPDATE ways SET y2 = y(ST_endpoint(the_geom));
UPDATE ways SET x1 = x(ST_PointN(the_geom, 1));
UPDATE ways SET y1 = y(ST_PointN(the_geom, 1));
UPDATE ways SET x2 = x(ST_PointN(the_geom, ST_NumPoints(the_geom)));
UPDATE ways SET y2 = y(ST_PointN(the_geom, ST_NumPoints(the_geom)));

Note

La fonction endpoint() ne fonctionne pas avec certaines versions de PostgresQL (par exemple les version 8.2.5 et 8.1.9). Un moyen de résoudre ce problÚme consiste à utiliser la fonction PointN() à la place:

Fonction avec paramÚtres

La fonction de recherche de plus court chemin A-* est trÚs semblable à la fonction Dijkstra, bien qu'elle préfÚre les tronçons qui sont plus proche du point d'arrivée de la recherche. Les heuristiques de cette recherche sont prédéfinis, donc vous aurez besoin de recompiler pgRouting si vous souhaitez modifier ces heuristiques.

shortest_path_astar( sql text,
                   source_id integer,
                   target_id integer,
                   directed boolean,
                   has_reverse_cost boolean )

Note

  • Les identifiants source et target sont les identifiant des sommets IDs.
  • Graphes non-orienté ("directed=false") ne prennent pas en compte le paramÚtre "has_reverse_cost"

Bases

SELECT * FROM shortest_path_astar('
                SELECT gid as id,
                         source::integer,
                         target::integer,
                         length::double precision as cost,
                         x1, y1, x2, y2
                        FROM ways',
                5700, 6733, false, false);

 vertex_id | edge_id |        cost
-----------+---------+---------------------
      5700 |    6585 |   0.175725539559539
      5701 |   18947 |   0.178145491343884
      2633 |   18948 |   0.177501253416424
       ... |     ... |                 ...
      6733 |      -1 |                   0
 (38 rows)

Enveloppe

Fonction envelopper AVEC cadre limite

SELECT gid, AsText(the_geom) AS the_geom
        FROM astar_sp_delta('ways', 5700, 6733, 0.1);

  gid   |                              the_geom
--------+---------------------------------------------------------------
   5534 | MULTILINESTRING((-104.9993415 39.7423284, ... ,-104.9999815 39.7444843))
   5535 | MULTILINESTRING((-104.9999815 39.7444843, ... ,-105.0001355 39.7457581))
   5536 | MULTILINESTRING((-105.0001355 39.7457581,-105.0002133 39.7459024))
    ... | ...
  19914 | MULTILINESTRING((-104.9981408 39.7320938,-104.9981194 39.7305074))
(37 rows)

Note

  • Il n'y a pas actuellement de fonction pour a-* sans cadre limite, étant donnée que le cadre limite permet d'améliorer grandement les performances. Si vous n'avez pas besoin de cadre limite, Dijkstra sera suffisant.

Shooting-Star

L'algorithme Shooting-Star est le dernier algorithme de recherche de plus court chemin. Sa spécialité c'est qu'il recherche un parcours d'un tronçon à un autre, pas d'un sommet à un sommet comme les agorithmes de Dijkstra et A-Star le font. Cela rend possible la définition de relations entre les tronçons par exemple, et cela résoud certains problÚmes liés aux recherches d'un sommets à un autre comme les "tronçons parallÚles", qui ont les même sommet de début et de fin mais des coût différents.

Prérequis

Pour Shooting-Star vous avez besoin de préparer votre table de réseau et d'ajouter les colonnes rule et to_cost. Come l'algorithme A-* il a aussi un fonction heuristique, qui favorise les tronçons plus proche du point d'arrivée.which prefers links closer to the target of the search.

-- Ajouter les colonnes rule et to_cost
ALTER TABLE ways ADD COLUMN to_cost double precision;
ALTER TABLE ways ADD COLUMN rule text;

L'algorithme Shooting-Star introduit deux nouveaux attributs

Attribut Déscription
rule une chaine de caractÚres contenant une liste d'identifiants de tronçno séparés par une virgule, qui décrivent le sens giratoir (si vous venez de cet tronçon, vous pouvez rejoindre le suivant en ajoutant un coût défini dans la colonne to_cost)
to_cost un coût pour passer d'un tronçon à un autre (peut être trÚs élevé s'il est interdit de trouner vers ce tronçon ce qui est comparable au coût de parcours d'un tronçon en cas de feu de signalisation)

Fonction avec paramÚtres

shortest_path_shooting_star( sql text,
                   source_id integer,
                   target_id integer,
                   directed boolean,
                   has_reverse_cost boolean )

Note

  • Identifiant du départ et de l'arrivée sont des identifiants de tronçons.
  • Graphes non-orientés ("directed=false") ne prennent pas en compte le paramÚtre "has_reverse_cost"

Pour décrire une interdiction de tourner :

 gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
-----+--------+--------+------+----+----+----+----+---------+------
  12 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 14

... signifie que le coût pour aller du tronçon 14 au tronçon 12 est de 1000, et

 gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
-----+--------+--------+------+----+----+----+----+---------+------
  12 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 14, 4

... signifie que le coût pour aller du tronçon 14 au tronçon 12 via le tronçon 4 est de 1000.

Si vous avez besoin de plusieurs restrictions pour une arrête donnée you devez ajouter plusieurs enregistrements pour ce tronçon avec un restriction particuliÚre.

 gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
-----+--------+--------+------+----+----+----+----+---------+------
  11 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 4
  11 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 12

... signifie que le coût pour aller soit du tronçon 4 soit du 12 au 11 est de 1000. Et donc vous devez ordoner vos données par gid lorsque vous chargez vos données dans la fonction de recherche de plus court chemin...

Bases

Un exemple d'utilisation de l'algorithme Shooting Star :

SELECT * FROM shortest_path_shooting_star('
                SELECT gid as id,
                         source::integer,
                         target::integer,
                         length::double precision as cost,
                         x1, y1, x2, y2,
                         rule, to_cost
                        FROM ways',
                6585, 8247, false, false);

 vertex_id | edge_id |        cost
-----------+---------+---------------------
     15007 |    6585 |   0.175725539559539
     15009 |   18947 |   0.178145491343884
      9254 |   18948 |   0.177501253416424
       ... |     ... |   ...
      1161 |    8247 |   0.051155648874288
 (37 rows)

Warning

L'lgorithme Shooting Star calcul un chemin d'un tronçon à un autre (pas d'un sommet à un autre). La colonnes vertex_id contienr le point de départ du tronçon de la colonne edge_id.

Envelopper

SELECT gid, AsText(the_geom) AS the_geom
        FROM shootingstar_sp('ways', 6585, 8247, 0.1, 'length', true, true);

  gid   |                              the_geom
--------+---------------------------------------------------------------
   6585 | MULTILINESTRING((-104.9975345 39.7193508,-104.9975487 39.7209311))
  18947 | MULTILINESTRING((-104.9975487 39.7209311,-104.9975509 39.7225332))
  18948 | MULTILINESTRING((-104.9975509 39.7225332,-104.9975447 39.7241295))
    ... | ...
   8247 | MULTILINESTRING((-104.9978555 39.7495627,-104.9982781 39.7498884))
(37 rows)

Note

Il n'y a actuellement pas de fonction enveloppe pour Shooting-Star sans cadre limite, puisque le cadre limite améliore grandement les performances.

Note: See TracBrowser for help on using the repository browser.