• Un compilateur C et C++
• Une version de PostgreSQL >= 8.0
• Une version de PostGIS >= 1.0
• Une version de PROJ >= 4.0
• Une version de la librairie GEOS >= 2.0 (voir http://geos.refractions.net)
• Une version de la librairie Boost Graph (BGL) >= 1.33 qui contient le astar.hpp (voir http://www.boost.org/libs/graph/doc/index.html)
• La librairie Genetic Algorithm Utility (GAUL). (voir http://gaul.sourceforge.net)

Étape 1 : intallation des libraries
Compiler et installer PostgreSQL, PostGIS, Proj, GEOS, BGL et GAUL. Il est habituellement suffisant d'utiliser : ./configure; make; make install dans les répertoires correspondants.

Si vous avez installé BGL mais que la version est inférieure à la 1.33.0, téléchargez simplement le fichier astar.hpp depuis http://www.boost.org/boost/graph/astar_search.hpp et copiez le dans le répertoire BOOST_PATH/graph.

La librairie GAUL doit être compilée avec l'option --no-slang. Sinon assurez-vous d'avoir le fichier slang.h installé dans le répertoire /usr/include. Pour plus de détails merci de vous référer au fichier README ou INSTALL.

Pour CGAL, les options de compilation suivantes peuvent être utilisés pour créer la librairie :

./install_cgal --prefix=/usr/local/cgal --with-boost=n --without-autofind -ni /usr/bin/g++

Étape 2 : compilation de la librairie pgRouting

Dans le cas où il y aurait 2 versions dePostgreSQL installés sur l'ordinateur (par exemple une 7.4 et une 8.1), assurez-vous que le pg_config de la version que vous souhaitez utiliser est dans la variable d'environnement PATH.

Pour compiler pgRouting, lancer la commande "configure" devrait suffir. Si les librairies BOOST, GAUL ou CGAL ne sont pas dans les chemins par défaut, il sera alors necéssaire de spécifier à configure où elles peuvent être trouvées. Taper ./configure --help listera l'ensemble des options de configuration.

Tapez ./configure --with-cgal=/usr/local/cgal --with-gaul=/usr/local

Taper make install

Étape 3: installation de la base de données

Pour créer une base de données de routage exemple utilisez les commandes suivantes :

Pour augmenter la rapiditer d'exécution, créez des index pour la table kanagawa.

Chargez le fichier sql routing.sql pour installer les fonctions dans votre base de données

Charger le fichier routing_postgis.sql qui créera les fonctions PostGIS d'import et de manipulation des données.

Le fonctionnalités essentielles sont définies dans le fichier routing.sql. Ces fonctions attendent en entrée des données dans un format spécifique.

Pour renvoyer des données elles utilisent le type suivant :

Cela renvoit un type qui peut être utilisé pour générer des résultats géographiques qui seront décrits plus tard.

Les logiciels de routage requièrent toujours un noeud source et destination pour chaque arc afin de créer une recherche du plus court chemin. La création de ces données sur des réseaux de lignes implique la création de la topologie de ce réseau. Bien que pgDijkstra donne la possibilité de créer les noeuds sources et destinations dans PostgreSQL, les performances ne sont pas bonne, parfois cette opération peut prendre un jour ou plus pour un grand nombre de données (le paramétrage de la base de donnée peux réduire le temps necéssaire).

Il y a d'autre logiciel qui peuvent être utilisés pour créer une topologie plus rapidement.

Certains d'entre eux sont :

PostGIS

Lors de la rédaction de cette documentation, la dernière version de PostGIS (1.1.2), a commencé à ajouter des fonctionnalités topologiques. Mais cela reste dans un état de développement très primaire et il y a encore très peu de documentation sur la création de topologies. Cette page sera mise à jour lorsque les fonctionnalités topologiques de PostGIS seront dans un état suffisament stable pour être utilisées.

ArcInfo

Pour ceux qui possède un licence ArcInfo, la création de topologie est faite simplement en utilisant la commend build: build line {Coverage Name} et en exportant ensuite la couverture dans un fichier vecteur, qui peut être ensuite importé dans PostGIS. La commande build va créer les colonnes fnode_,tnode_,length qui peuvent être renommées dans PotgreSQL comme source,target, et la colonne length peut être utilisé comme le coût intial.

GRASS

GRASS peut aussi être utilisé pour créer une topologie, mais l'extraction de l'information topologique et l'insertion dans PostgreSQL n'est pas aussi simple que dans ArcInfo puisque l'information topologique n'est pas inclue dans l'ensemble des donnée lors de l'export dans un fichier vecteur.

La commande de création de topologie, v.build, a un option dump qui permet d'afficher l'information dans un flux qui peut être redirigé dans un fichier. Par exemple :

La sortie devrait ressembler à cela :

Un programme perl comme celui-ci (table_topo.pl) peut être utilisé pour convertir la sortie de GRASS dans un fichier SQL qui créera les table de noeuds et d'arcs contenant l'imformation topologique. Ces tables peuvent ensuite être liés dans la table réseau de PostGIS pour créer les information source-destination.

La fonction shortest_path est définie de la manière suivante :

CREATE OR REPLACE FUNCTION shortest_path(sql text, source_id integer, 
       target_id integer, directed boolean, has_reverse_cost boolean) 
    RETURNS SETOF path_result

sql

une requête SQL qui doit renvoyer les champs suivants :

SELECT id, source, target, cost FROM edge_table;

• id: l'identifiant entier (int4) de l'arc
• source: un identifiant entier (int4) du noeud de départ
• target: un identifiant entier (int4) du noeud d'arrivée
• cost: le coût de la traversée d'un arc (float8, un coût négatif permet de s'assurer qu'on ne passera jamais par cette arc)
• reverse_cost : (optionel) le coût de la traversée de l'arc en sens invers. Cela n'estutilisé que lorsque la fonction est appelé avec l'argument has_reverse_cost à vrai.

source_id

identifiant du noeud de départ.

target_id

identifiant du noeud d'arrivée.

directed

vrai si le graphe est orienté.

has_reverse_cost

vrai si la colonne reverse_cost doit être considérée lors de la recherche du plus court chemin, dans le cas où lma traversée de l'arc se fait en sens invers.

• vertext_id : l'identifiant du noeud source de chaque arc. Il y a une ligne supplémentaire contenant l'identifiant du noeud d'arrivée,
• edge_id : l'identifiant de l'arc traversé,
• cost : le coût de la traversée de l'arc. Cette valeur vaut 0 pour la dernière ligne renvoyée. Donc le coût total du parcour peut être calculé en faisant la somme des valeurs de cette colonne.

SELECT * FROM shortest_path('SELECT gid AS id, source::int4, 
          target::int4, length::double precision AS cost,
    FROM dourol',3, 7, false, false);

 vertex_id | edge_id | cost 
-----------+---------+------------------------
         3 |       2 |    0.000763954363701041
         4 |      21 |    0.00150254971056274
         6 |       5 |    0.000417442425988342
         7 |      -1 |    0
(4 rows)

SELECT * FROM shortest_path('SELECT gid AS id, source::int4, 
         target::int4, length::double precision AS cost,length::double precision 
    AS reverse_cost FROM dourol', 3, 7, true, true);

La fonction shortest_path_astar est définie de la façon suivante :

Les arguments sont :

sql
une requête SQL, qui doit renvoyer un ensemble de lignes ayant les colonnes suivantes :

• id: une entier (int4), l'identifiant de l'arc
• source: un entier (int4), l'identifiant du noeud source
• target: un entier (int4), l'identifiant du noeud destination
• cost: une valeur flotante (float8) représentant le coût de la traversé de l'arc. (un coût négatif permettra d'empécher l'insertion de l'arc dans le graphe).
• x1: coordonée x du noeud source de l'arc
• y1: coordonée y du noeud source de l'arc
• x2: coordonée x du noeud destination de l'arc
• y2: coordonée x du noeud destination de l'arc
• reverse_cost (optional): le coût de la traversée dans le sens inverse de l'arc. Cela est uniquement utilisé lorsque le graphe est orienté et que les paramètres has_reverse_cost sont à vrai (voir la remarque ci-dessous concernant les coûts inverses).

source_id
int4 identifiant du point de départ
target_id
int4 identifiant du point d'arrivé
directed
vrai si le graphe est orienté
has_reverse_cost
si sa valeur est vrai, la colonne reverse_cost du résultat SQL généré sera utilisé pour le coût de la traversé d'un arc dans la direction oposée.

La fonction renvoie un ensemble de lignes. Il y a une ligne pour chaque arc traversé et une en plus contenant le noeud terminal. Les colonnes de chaque lignes sont :

• vertex_id: l'identifiant du noeud origine de chaque arc. Il y a une ligne supplémentaire après le dernier arc qui contient le noeud de la destination du chemin.
• edge_id: l'identifiant de l'arc croisé
• cost: le coût associé à l'arc courant. Il vaut 0 pour les lignes après le dernier arc. Donc, le coût total du chemin peut être calculé en utilisant la somme de la colonne coût de toutes le lignes.

Exemple:

SELECT * from shortest_path_astar('SELECT gid as id, source::int4,
target::int4, length::double precision as cost, x1, y1, x2, y2
FROM dourol',3, 7, false, false);
vertex_id | edge_id | cost
----------+---------+------------------------
        3 |       2 | 0.000763954363701041
        4 |      21 | 0.00150254971056274
        6 |       5 | 0.000417442425988342
        7 |      -1 | 0
(4 rows)
SELECT * from shortest_path_astar('SELECT gid as id, source::int4,
target::int4, length::double precision as cost,length::double precision
as reverse_cost, x1, y1, x2, y2 FROM dourol', 3, 7, true, true);
haut de la page | table des matières

La fonction shortest_path_shooting_star est définie de la façon suivante :

Les arguments sont :

sql

une requête SQL, qui doit renvoyer un ensemble de lignes ayant les mêmes colonnes que celles nécessaires à A* plus :

• rule: une chaîne de caractère contenant une liste d'identifiants d'arcs, séparés par une virgule, qui décrit le sens giratoir (si je suis sur tel tronçon je peux aller sur tel tronçon avec le coût décrit dans la colonne to_cost)
• to_cost : le coût d'un passage restrain (peut être très élevé dans le cas où le fait de tourner vers tel arc entraine le passage par un feu)
  

source_id

int4 identifiant de l'arc de départ

target_id

int4 identifiant de l'arc d'arrivé

directed

vrai si le graphe est orienté

has_reverse_cost

si sa valeur est vrai, la colonne reverse_cost du résultat SQL généré sera utilisé pour le coût de la traversé d'un arc dans la direction oposée.

La fonction renvoie un ensemble de lignes équivalent à celui renvoyé par A* mis à part que le dernier coût retourné n'est pas -1.

Exemple:

La fonction driving_distance est définie comme suit :

Les arguments sont :

sql

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

• id: un identifiant (int4) de l'arc
• source: un identifiant (int4) du noeud origine
• target: un identifiant (int4) du noeud destination
• cost: une valeur float8 représentant le coût de traversé d'un arc. (un coût négatif entrainera la non insertion de l'arc dans le graphe).

source_id

un identifiant (int4) du point de départ id of the start point

distance

une valeur float8 de la distance en degrés

La focntion renvoie un ensemble de lignes. Il y a une ligne pour chaque arc tranversés et un ligne supplémentaire contenant le noeud terminal. Les colonnes de chaque lignes sont :

• vertex_id: l'identifiant du noeud source de chaque arc. Il y a une ligne supplémentaire contenant l'identifiant du noeud final du chemin.
• edge_id: l'identifiant de l'arc traversé
• cost: le coût associé à l'arc. Il vaut 0 pour la ligne après le dernier arc. Donc, le cou^t total du chemin peut être calculé comme la somme de la colonne cost de toutes les lignes.

  Exemple:
  

  SELECT * from driving_distance('select gid as id,source,target,
  length::double precision as cost from dourol',10549,0.01);
  vertex_id | edge_id |            cost
  -------------+------------+--------------------------
          6190 |   120220 | 0.00967666852
          6205 |    118671 | 0.00961557335
          6225 |   119384 | 0.00965668162
          6320 |   119378 | 0.00959826176
           ...
           ...
           ...
          15144 |   122612 | 0.00973386526
          15285 |   120471 | 0.00912965866
          15349 |  122085 | 0.00944814966
           15417 |   120471 | 0.00942316736
          15483 |   121629 | 0.00972957546
  (293 rows)
  haut de la page | table des matières

La fonction tsp est définie comme suit :

Les arguments sont :

sql

un requête SQL qui devrait retourner un ensemble de lignes ayant les colonnes suivantes :

• source_id: un int4 identifiant du noeud
• x: la coordonée x du noeud
• y: la coordonée y du noeud

ids

une chaîne de charactères contenant les idetifiants (int4) des noeuds séparés par une virgule.

source_id

identifiant (int4) du point de départ

La fonction renvoie un ensemble de lignes. Il y a une ligne pour chaque arc travsersé et une en plus contenant le noeud final. Les colonnes de chaques lignes sont les suivantes :

• vertex_id: l'identidiant du noeud source de chaque arc. Il y a une ligne supplémentaire après le dernier arc qui contient l'identifiant du noeud final du chemin.
• edge_id: innutilisé, vaut toujours 0
• cost: innutilisé, vaut toujours 0

Exemple:

Ensuite la colonne vertex_id peut être utilisée pour le calcul du plus court chemin.

Il y a de nombreuses fonctions dans le fichier routing_postgis.sql qui renvoient le résultat sous la forme d'une geometrie (objet de type geometry). Vous pouvez trouver leur noms facilement - elles contiennent "as_geometry".

Vous trouverez ici de courts articles et des tutoriels.
(Pour commencer il n'y a pas de structuration spéciale du contenue, simplement une listes de liens)

Les deux algorithmes Dijkstra et A* permettent de calculer le coût pour chaque orientation de l'arc d'un graphe, ce qui peut être très utile lors de la recherche de chemins avec un réseau routier qui a des rues en sens uniques.

Ce petit exemple illustrera comment cela est fait. Les données utilisées dans cet exemple ont été créées en utilisant OpenJump et ont ensuite été charger dans une base de données PostGIS pour laquelle pgRouting à aussi été installlé.

Le graphe ressemble à ceci; remarquez que l'arc #2 à été arienté de droite à gauche, contrairement à la plupart des arcs qui ont été orienté de gauche à droite. Cela a été fait comme cela pour simuler une route à sens unique.

Lors du calcul pour le coût de chaque coté d'un arc, un champ représentant le coût inverse (rcoast) doit être passer en argument à l'olgorithme de routage.

Intiallement, les deux coût (coast,rcoast) ont la même valeur qui est la longueur de l'arc.

Ensuite, pour agmenter le coût inverse de l'arc n°2 , une valeur de 1000000 sera ajouter à la valeur de la colonne rcoast.

gid |        cost      |         rcost       | source | target
----+------------------+---------------------+--------+--------
 1  | 90.4777391240398 | 90.4777391240398    |      1 |      2
 2  | 266.663211021467 | 000266.663211021467 |      3 |      2
 3  | 74.7975644284963 | 74.7975644284963    |      2 |      4
 4  | 264.887335603738 | 264.887335603738    |      4 |      5
 5  | 49.0618009646755 | 49.0618009646755    |      3 |      5
(5 rows)

Le dernier argument passé aux algoithmes Dijkstra et A* détermine si le coût inverse doit aussi être calculé lors de la recherche d'un chemin à travers le graphe.

Lorsque vous lui attribué la valeur faux, les deux algorithmes effectueront la recherche en utilisant uniquement le paramètre coût, qui est simplement dans ce cas la longueur de chaque arc. Avec notre exemple, nous trouverons un chemin partant du noeud n°1 jusqu'au noeud n°3.

routing=# select * 
          from shortest_path_astar(
            'select gid as id,
                    source::int4,
                    target::int4,
                    cost::double precision,
                    rcost::double precision as reverse_cost,
                    x1,y1,x2,y2 
             from rtest',
             1,3,false,false);

 vertex_id | edge_id |      cost
-----------+---------+------------------
       1   |     1   | 90.4777391240398
       2   |     2   | 266.663211021467 
       3   |    -1   |  0
(3 rows)

Maintenant, si nous attribuons la valeur vrai au paramètre inverse, les algorithmes utilseront alors le coût inverse, ils constateront que le noeud 2 de l'arc n°2 a un coup très élevé et chercheront donc un autre chemin.

routing=# select * 
          from shortest_path_astar(
            'select gid as id,
                    source::int4,
                    target::int4,
                    cost::double precision,
                    rcost::double precision as reverse_cost,
                    x1,y1,x2,y2 
             from rtest',
             1,3,false,true);

vertex_id | edge_id |       cost
----------+---------+------------------
       1  |      1  |  90.4777391240398           
       2  |      3  |  74.7975644284963           
       4  |      4  |  264.887335603738
       5  |      5  |  49.0618009646755
       3  |     -1  |   0
(5 rows)

Bien que nous ayons la possibilité de calculer le coût de chaque sens de l'arc, c'est très astucieux, cela reste néanmoins très couteux puisqu'il influera fortement sur les performances et devrait donc être utilisé seulement lorsque c'est vraiment nécessaire.

routing=# explain analyze 
          from shortest_path_astar(
            'select gid as id,
                    source::int4,
                    target::int4,
                    cost::double precision,
                    rcost::double precision as reverse_cost,
                    x1,y1,x2,y2 
             from rtest',
             1,3,false,false);

                               QUERY PLAN 
--------------------------------------------------------------------------------
Function Scan on shortest_path_astar  (cost=0.00..12.50 rows=1000 width=16) 
(actual time=0.954..0.958 rows=3 loops=1)  Total runtime: 1.020 ms
(2 rows)

routing=# explain analyze 
          from shortest_path_astar(
            'select gid as id,
                    source::int4,
                    target::int4,
                    cost::double precision,
                    rcost::double precision as reverse_cost,
                    x1,y1,x2,y2 
             from rtest',
             1,3,false,false);

                               QUERY PLAN 
--------------------------------------------------------------------------------
Function Scan on shortest_path_astar  (cost=0.00..12.50 rows=1000 width=16) 
(actual time=11.088..11.093 rows=5 loops=1)  Total runtime: 11.155 ms
(2 rows)

Dans cette section nous allons vous expliquer comment utiliser l'exemple mis à notre disposition sur le site de postlbs (cf. ce lien).

Prérequis :

Afin de mettre en pratique ce petit tutoriel, il est nécessaire que vous ayez installé les logiciels listés ci-dessous :

• le support php_mapscript
• PostGIS avec son outils shp2pgsql
• la librairie pgRouting

Création initiale de la base de données de test :

La première étape consiste à créer une base de données nommée routing et d'y importé les fonctionnalités de PostGIS et de pgRouting. Pour ce faire je vous conseil de vous référer à la section "Installation" du présent manuel (l'étape 3).

Afin de pas avoir à faire trop de modifications dans la mapfile dont nous parlerons plus loin, je vous conseil aussi de créer cette base de données en tant qu'utilisateur postgres sans quoi vous devrez éditer la mapfile routing.map se trouvant dans routingj/maps/ afin d'y modifier le nom d'utilisateur utilisé dans la chaîne de connection des deux couches PostGIS.

Décompression du projet de démonstration de postlbs :

Avant d'aller plus loin, nous allons télécharger l'archive de démonstration du projet postlbs puis la décompresser dans le répertoire racine de votre aborescence apache, j'utiliserais dans la suite de ce tutoriel /var/www/localhost/htdocs comme répertoire racine.

Télécharger l'archive au format bzip2, puis rendez-vous dans le repertoire /var/www/localhost/htdocs afin d'y décompressez le fichier fraîchement téléchargé à l'aide de la commande suivante : tar -xvf pgRouting-sampleapp.tar.bz.
Une fois ceci fait vous êtes fin prêt pour intrégrer les données contenues dans le répertoire : /var/www/localhost/htdocs/routingj/data.

Cette partie peut donc être résumé par les lignes de commande suivantes :

Convertion d'un réseau routier en une couche PostGIS et créationd es indexes :

Maintenant que nous avons une base avec PostGIS et pgRouting d'activé et que nous avons décompresser l'archive contenant la démonstration de postlbs, nous pouvons charger nos données de tests. Pour ce faire, il suffit de se rendre dans le répertoire routingj/data à la racine de votre serveur web afin de créer le fichier sql correspondant au fichier vecteur kanagawa.shp. Pour ce faire nous utilisons l'outils shp2pgsql comme nous en avons l'habitude, nous chargeons ensuite ce fichier dans notre base de données routing et nous finissons par créer les indexes nécessaires :

Voilà nous venons d'intégrer les données de démonstration de postlbs dans notre base de données nommée routing, nous pouvons maintenant passé à la configuration de notre application de démonstration.

Modifications nécessaires au bon fonctionnement de l'application :

Pour ma part je paramettre toujours mon php.ini pour qu'il charge php_mapscript, c'est ce qui explique que je doive supprimer les chargement dynamique contenus dans les diverses pages du projet de démonstration, cette manipulation n'est donc à faire que dans le cas où vous avez php_mapscript d'activé dans votre php.ini. Pour réaliser cette modification, il suffit de lancer la commande suivante :

De même les références à la mapfile dont nous avons parlé plus tôt ne fonctionnaient pas avec un chemin relatif, c'est pourquoi j'ai pour ma part modifier ces références de la manière suivantes :

J'ai aussi due modifier le fichier maps/routing.map afin d'y modifier les valeurs pour le répertoire où seront stoquées les images générées dans la section WEB.
J'ai donc la section WEB suivante :

Consultation de l'application de démonstration :
Une fois que vous avez réalisé toutes les étpaes précédantes, vous devriez pouvoir tester l'application en vous rendant sur la page de votre serveur web, en supposant que ce soit sur localhost, rendez-vous sur la page : http://localhost/routingj/ et utilisez les liens présents sur cette pages afin de tester les diverses fonctionnalités.

Si vous voulez un exemple en "live", j'ai installé l'application de démonstration de postlbs sur un portable sous gentoo, librement accessible ici.

(Author: Camptocamp/ pgDijkstra)

La fonction shortest_path_as_geometry() peut être utilisée dans la définition d'une couche MapServer pour afficher directement le plus court chemin :

Notez cependant que cette fonction est appelée à chaque affichage de la carte, calculant le plus court chemin à chaque fois.

Une meilleur approche serait de générée le plus court chemin et de le stoquer dans une table temporaire.