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.