L’extension pgrouting propose divers algorithmes pour rechercher le meilleur itinéraire :Dijkstra, A*,Ksp,Trsp,…
Dans cet article nous allons voir en détail l’utilisation de a* (A-star).
Nous continuerons à utiliser la base de données et les outils décrits dans l’article précédent (Développer une application avec pgrouting sous Windows (1)).
L’algorithme A* est un algorithme de recherche de chemin dans un graphe entre un nœud initial et un nœud final. Il utilise une évaluation heuristique sur chaque nœud pour estimer le meilleur chemin y passant, et visite ensuite les nœuds par ordre de cette évaluation heuristique.
Avec l’algorithme de Dijkstra, ce sont les algorithmes les plus utilisés pour le calcul du plus court chemin entre deux points d’un réseau linéaire.
Requête A*
La syntaxe de l’algorithme A* est la suivante:
pgr_astar(sql text, source integer, target integer,directed boolean, has_rcost boolean);
Où source est le point de départe souhaité de l’itinéraire, target le point d’arrivée de l’itinéraire et la chaîne sql est de type:
SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM réseau
Nous verrons plus loin les deux variables booléennes et leur utilisation.
La commande retourne un élément pgr_costResult qui contient (seq, id1, id2, cost), où seq est l’ordre du tronçon dans l’itinéraire, id1 le point de départ du tronçon, id2 le point d’arrivée du tronçon et cost le coût associé à ce tronçon.
Préparation de la base de données
Contrairement aux autres algorithmes de pgrouting, pour utiliser A* il faut ajouter, si nécessaire, les coordonnées en latitude/longitude des nœuds début et fin de chaque tronçon.
Si vous avez suivi la création de la base de données dans l’article précédent en important des données OpenStreeMap avec osm2pgrouting, vous n’avez rien à faire car ce programme génère les champs x1, y1, x2, y2 nécessaires à la méthode A*
Si ces champs ne sont pas présents dans votre couche réseau, il va falloir les créer.
Mais au préalable il faut vérifier le type de géométrie de votre réseau. Dans pgAdmin III, sélectionnez le champ géométrie de votre table:
Problème: géométrie MultiLineString ou LineString?
Vous pouvez retrouver deux types de géométrie: LineString et MultiLineString. Les commandes utilisées pour calculer les coordonnées des nœuds ne marchent que sur des géométries LineString. Si vous avez une géométrie MultiLineString, inutile d’essayer. Vous n’aurez pas de message d’erreur, mais vos colonnes resteront désespérément vides.
Ceci est d’autant plus bête, que vous avez 99.99% de probabilités de ne pas avoir réellement une géométrie MultiLine String! Si vous utilisez l’utilitaire PostGis Shapefile and DBF loader, vous aurez par défaut ce type de géométrie, même si vos données sont des LineString.
SOLUTION:
Testez la géométrie pour vérifier qu’elle n’est pas forcément MultiLineString avec la commande SQL suivante
SELECT COUNT(
CASE WHEN ST_NumGeometries(the_geom) > 1 THEN 1 END
) AS multi, COUNT(the_geom) AS total
FROM ways;
Si le résultat de Multi est 0, vous n’avez pas de multilignes et vous pouvez changer le type de géométrie en LineString avec la commande SQL
ALTER TABLE ways
ALTER COLUMN the_geom TYPE geometry(LineString, 4326)
USING ST_GeometryN(the_geom, 1);
Maintenant vous pouvez créer les champs x1, y1, x2, y2 avec les commandes sql suivantes:
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 = ST_x(ST_PointN(the_geom, 1));
UPDATE ways SET y1 = ST_y(ST_PointN(the_geom, 1));
UPDATE ways SET x2 = ST_x(ST_PointN(the_geom, ST_NumPoints(the_geom)));
UPDATE ways SET y2 = ST_y(ST_PointN(the_geom, ST_NumPoints(the_geom)));
Problème: choix du « coût » d’un tronçon.
L’algorithme de routage recherche le chemin avec le coût le plus faible. En fonction de vos objectifs, vous devez décider quel élément de coût vous allez prendre en charge.
Reprenons notre base OpensStreetMap. Vous avez un champ « cost » qui reprend la longueur du tronçon en degrés. Si vous utilisez ce champ dans l’algorithme A* comme valeur de coût, l’itinéraire proposé sera le plus court chemin entre les deux points choisis. Voyons un exemple.
La commande suivante calcule l’itinéraire entre les points 69072 et 64204 en utilisant le champ « cost » qui correspond à la longueur du tronçon.
SELECT seq, id1 AS node, id2 AS edge, di.cost, the_geom
FROM pgr_astar(
‘SELECT gid as id, source::integer, target::integer, cost::double precision, x1, y1, x2, y2 FROM public.ways’,
69072, 64204, false, false
) as di
JOIN public.ways ways_vertices_pgr
ON di.id2 = ways_vertices_pgr.gid ;
Le résultat, une fois chargé dans QGis, est le suivant:
A pied, c’est le meilleur chemin. Mais en voiture on ne le prendrait jamais! Des petites rues avec des zones 30km/h en lieu et place d’une voie rapide à 110km/h…
Dans la table OSM vous trouvez un autre champ, dénommé cost_s. Celui-ci est le résultat du calcul du temps de parcours en secondes , en prenant les informations de longueur et de vitesse autorisée pour chaque tronçon.
Si on modifie la requête sql pour utiliser ce champ:
SELECT seq, id1 AS node, id2 AS edge, di.cost, the_geom
FROM pgr_astar(
‘SELECT gid as id, source::integer, target::integer, cost_s::double precision as cost, x1, y1, x2, y2 FROM public.ways’,
69072, 64204, false, false
) as di
JOIN public.ways ways_vertices_pgr
ON di.id2 = ways_vertices_pgr.gid ;
Le résultat, une fois chargé dans QGis est le suivant (tracé en rouge)
Problème : cost_s a des valeurs nulles
Il y a des fortes chances pour que la dernière requête SQL vous retourne une erreur disant que cost_s a des valeurs nulles.
Ceci vient du fait que le champ qui est utilisé par osm2pgrouting pour calculer le coût en secondes est la longueur du tronçon en m (length_m), et que ce champ n’est pas toujours renseigné.
SOLUTION:
Avec QGis en ayant chargé la couche ways, sélectionnez Projet->propriétés du projet->SCR
Cochez la case Projection à la volée et sélectionnez une projection plane, Lambert 95 par exemple.
Ouvrez la table attributaire de ways, passez la table en mode édition.
Sélectionnez tous les enregistrements avec cost_s nuls
Vous constaterez que les enregistrements sélectionnés ont une length_m nulle aussi.
Avec la calculatrice de champ cochez la case Mettre à jour un champ existant, sélectionnez le champ lenght_m et dans Expression tapez $length
Ceci renseignera le champ avec la longueur du tronçon, calculée selon le système de coordonnées actuel de QGis (lambert95 par exemple).
Maintenant vous pouvez mettre à jour le champ cost_s avec l’expression
(« length_m » * 3600) / (« maxspeed_forward » * 1000)
Problème: l’itinéraire fonctionne à contresens
Avec les requêtes utilisées jusqu’à présent, vous pouvez obtenir des résultats tels que le suivant:
L’itinéraire calculé vous propose de sortir de la voie rapide et de la réemprunter à contresens!
Dans les données OSM, un champ oneway indique, s’il est égal à 1, que le tronçon n’a qu’un sens de parcours. Les algorithmes de pgrouting n’utilisent pas directement ce champ. Ils utilisent le champ reverse_cost.
Vous avez donc un champ cost et un champ reverse_cost. Si la valeur de ces deux champs est la même, ceci est compris par l’algorithme comme une route à double sens. L’itinéraire proposé pourra donc aller dans les deux sens.
Si reverse_cost a une valeur négative, il n’empruntera jamais ce tronçon dans le sens inverse mais toujours du nœud source vers le nœud target. Le tronçon est immédiatement écarté du graphe résultat. Si non, vous pouvez aussi affecter une valeur extrêmement grande (par exemple 1000000) aux reverse_costs des tronçons à sens unique. Dans ce cas le tronçon sera évalué (défavorablement) mais pas écarté d’emblée.
Pour que l’algorithme prenne en compte ces valeurs il faut modifier les deux paramètres booléens de la requête SQL directed et has_reverse. Il y a quelques subtilités qui dépassent le cadre de cet article en ce qui est de modifier seulement un des deux paramètres (true,false et false,true). Globalement, vous mettez les deux paramètres à true pour que l’algorithme fonctionne en prenant en compte les sens interdits.
Voici la requête telle qu’elle doit être pour ne pas avoir le problème de contresens sur la voie express:
Problème: reverse_costs_s a des valeurs nulles
Comme pour le champ cost_s, ceci vient du fait que le champ qui est utilisé par osm2pgrouting pour calculer le coût en secondes est la longueur du tronçon en m (length_m), et que ce champ n’est pas toujours renseigné.
SOLUTION
Comme vous avez en principe rempli toutes les valeurs de costs_s, il suffit de sélectionner dans la table de QGis tous les enregistrements avec des valeurs reverse_costs_s nulles, puis avec la calculatrice de champs affecter la valeur de costs_s à reverse_costs_s.
Nous avons donc, nous mêmes, généré le problème suivant:
Problème: reverse_costs_s ne prend pas en compte les sens interdits (même valeur que les costs_s correspondants)
SOLUTION
Sélectionnez les enregistrements avec oneway = 1, puis affectez la valeur -costs_s au champ reverse_costs_s
Les solutions aux deux derniers problèmes partent de la base que vous utilisez les données OSM et font que les tous les enregistrements soient cohérents. Bien évidement, si vous avez un réseau particulier et que vous avez adopté d’autres spécifications, il faudra adapter les requêtes pour respecter vos définitions.
Nous avons fini le tour de l’algorithme A* et de ses problèmes les plus courants. Si vous en trouvez d’autres (je vous fais confiance), n’hésitez pas à laisser un commentaire.
Dans le prochain article nous verrons comment(ne) fonctionnent (pas) les autres algorithmes de routage sous Windows.
Bonjour,
Comment faire si ma géométrie est MultiLineString ? J’ai en effet importé mes données avec l’utilitaire PostGis Shapefile and DBF loader car je n’arrivais à importer mes données avec l’invite de commande (Message d’erreur : fe_sendauth no password supplied).
Merci
C’est décrit dans l’article:
ALTER TABLE nom_de_votre_table
ALTER COLUMN the_geom TYPE geometry(LineString, 4326)
USING ST_GeometryN(the_geom, 1);
Bonjour,
Je vous remercie pour ce tutoriel détaillé.
Je souhaite calculer l’itinéraire entre 2 points et afficher la distance entre ces 2 points. Auriez des consignes à me donner ??
J’ai essayé la première requête de l’algorithme A* et j’ai l’erreur suivante:
ERROR: syntax error at or near « gid »
LINE 3: ‘SELECT gid as id, source::integer, target::integer, cost, x…
^
********** Error **********
ERROR: syntax error at or near « gid »
SQL state: 42601
Character: 81
Pouvez-vous m’aider ?
Merci
Désolé, mais le message dit simplement que la syntaxe n’est pas bonne. cela peut venir de plein de choses. Déjà, vérifiez que le caractère ‘ est bien l’apostrophe de la touche numérique 4. Si vous avez copié-collé la requête depuis la page de l’article, c’est une autre apostrophe que celle-là.
Pour ce qui est de calculer la longueur de l’itinéraire, soit vous utilisez comme ‘cost’ la longueur du tronçon, et vous faites une addition de tous les costs renvoyés par la requête, soit vous chargez une table avec le résultat de la requête et vous faites une jointure avec la table des tronçons pour récupérer la longueur de chaque tronçon et les additionner.
Je vous remercie pour votre réponse si rapide.
J’ai une erreur car les champs source et target sont de type bigint, J’ai lu votre article 3 dans lequel vous parlez de ce problème. La version de pgrouting que j’ai est la v2.3.2.
De tête, pour modifier le type d’un champ de la table:
ALTER TABLE nomdelatable ALTER COLUMN source SET DATA TYPE integer;
Bon, j’ai toujours la même erreur malgré que j’ai changé le type des champs concernés et j’ai actualisé:
NOTICE: Deprecated signature of function pgr_astar
ERROR: Error, columns ‘source’, ‘target’ must be of type int4, ‘cost’ must be of type float8
CONTEXT: PL/pgSQL function pgr_astar(text,integer,integer,boolean,boolean) line 7 at assignment
********** Error **********
ERROR: Error, columns ‘source’, ‘target’ must be of type int4, ‘cost’ must be of type float8
SQL state: XX000
Context: PL/pgSQL function pgr_astar(text,integer,integer,boolean,boolean) line 7 at assignment
Est-ce que vous utilisez la syntaxe suivante?
pgr_astar( ‘SELECT gid::integer as id, source::integer, target::integer, cost::double precision , x1, y1, x2, y2 FROM …
Avec cette syntaxe il y’a plus d’erreur.
Merci pour votre aide et temps 🙂
bonjour;
par curiosité est il possible de calculer des itinéraires en prenant en compte des contraintes de poids et de gabarits ???
je realise actuellement une cartographie d’accés pour poids lourd et je dispose de trois couches de routes une couche « route nationale », une « départementale » et une « communale » faut il les regrouper en une seul est unique couche ???
et toute mes contraintes de gabarits sont également sur plusieurs couches différentes avec une couche pour les contraintes tonnages et une autre pour les dimensions la aussi y a t’il besoin de les regrouper en une couche ?????
et surtout dernière question est il possible lors de la recherche d’itinéraire de lui donner des critères de gabarits ????
rémi
A la question s’il faut regrouper les trois couches en une, la réponse est OUI. L’algorithme est conçu pour interroger une seule table de tronçons.
Les contraintes, c’est un peu plus compliqué. Les algorithmes de routage fonctionnent en calculant le trajet avec le « coût » le plus bas. Si vous voulez le trajet le plus court, vous paramétrez la requête en utilisant la longueur des tronçons comme élément de coût. Si vous souhaitez le trajet le plus rapide, vous configurez l’algorithme pour utiliser la longueur en km divisée par la vitesse autorisée (ça vous donne le temps de parcours du tronçon).
Si vous voulez utiliser des contraintes de gabarit et de poids, il faut trouver comment les traduire en une fonction de coût. Et ça, c’est un peu plus compliqué…
Quelles sont les types de contrainte que vous souhaitez? C’est des interdictions de tronçons en fonction d’un poids ou d’un gabarit? ou alors des tronçons à ne prendre qu’en dernier recours?
En ce qui concerne le gabarit c’est une interdiction (par exemple un tunel de 4 metres ne peu pas laissé passer un camion de 4m80 ) en ce qui concerne les tonnages des dérogations sont possible selon les cas ….
Par contre est il possible d’effectuer une recherche d’itinéraires en renseignant des contraintes ? Je n’ai pas vue cette possibilitée dans votre tutoriel ?
Merci pour votre première réponse si rapide
Rémi
dans la partie sql SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM réseau on remplace cost par une formule
Bonjour,
Si j’ai bien compris, pour calculer l’itinéraire il faut la table ways et ways_vertices_pgr.
Comment serait-il possible de calculer l’itinéraire entre 2 restaurants qui se trouvent dans une table restaurant géocodée ??
Merci
Il faut structurer la table restaurant pour qu’elle contienne toutes les informations (champs) nécessaires à pgrouting, s’assurer que le réseau est compatible géométriquement avec une recherche d’itinéraire(tronçons continus, noeuds à toutes les intersections,etc), puis créer la table de vertices avec pgr_createtopology
Merci.
Je vois pas vraiment comment structurer la table restaurant pour qu’elle contienne les champs nécessaires à pgrouting.
Avez-vous un tuto qui peut m’aider à faire ça ?
Commencez par vous assurer que la projection (SCR) de votre table est bien géographique WGS84 (code 4326). Si ce n’est pas le cas, vous devez créer une nouvelle table en reprojetant celle que vous avez en 4326. pgrouting ne fonctionne qu’avec des tables en 4326.
Deuxièmement, vérifiez que chaque tronçon se termine bien là où un autre commence. La table de vertices créée par pgr_createtopology va créer une table de points (nœuds) et c’est cette table qui va servir à créer l’itinéraire. Si deux tronçons se croisent, il faut qu’ils aient un noeud au croisement, si non la recherche d’itinéraire considère que les deux tronçons n’ont pas de communication (comme si l’un passait sur un pont par dessus l’autre)
Pour les champs (de tête, il faudra que je vérifie) il faut un champ identifiant (numérique, automatique, unique), un champ numérique « source » et un champ numérique « target », qui doivent être à NULL au départ. Ils seront remplis par la commande pgr_createtopology
Il faut aussi un champ qui va représenter le « coût » de prendre chaque tronçon: la longueur de chaque tronçon, si vous voulez le trajet le plus court, ou le temps de parcours théorique de chaque tronçon si vous voulez le trajet le plus rapide, etc.
et si vous voulez utiliser l’algo a-star il vous faut les x et y des points début et fin de chaque tronçon (pas nécessaires si vous utilisez l’algo pgr_dijkstra)
Bonjour,
J’ai fait le suivant:
select UpdateGeometrySRID(‘public’, ‘finale’, ‘the_geom’, 4326) ;
ALTER table public.restaurant add column source integer;
ALTER table public.restaurant add column target integer;
ALTER table public.restaurant add column length_m double precision;
ALTER table public.restaurant add column cost double precision;
SELECT pgr_createtopology(‘public.restaurant’, 0.00001, ‘the_geom’, ‘id’)
Et tous mes nouveaux champs que je viens de créer sont nuls, même la table de vertices est vide.
Je précise que la table restaurant est une table de points.
Que faut-il faire?
Vous ne pouvez pas rechercher un itinéraire sur une table de points! Il vous faut une table avec les rues (lignes). Pourquoi vous ne suivez pas la démarche du premier article pour télécharger la zone de vos restaurants à partir d’openstreetmaps?
Après vous pourrez cliquer sur un point de départ et un point « restaurant » et utiliser pgrouting avec la table openstreetmap pour trouver l’itinéraire.
J’ai déjà fait ça en suivant votre tuto 1.
J’ai extrait la zone de mes restaurants de OSM, et ça marche en testant le calcul d’itinéraire.
Il y’a deux tables (ways et ways_vertices_pgr).
Apres j’ai téléchargé la base sirene à partir de la quelle j’ai créé ma table où il y’a uniquement les restaurants de ma zone.
Sauf que je vois pas vraiment comment calculer l’itinéraire entre 2 restaurants.
Si vous avez fait les étapes précédentes, maintenant il faut faire les étapes suivantes: si vous voulez une page html il faudra geoserver puis OpenLayers. La seule chose à ajouter dans l’appli de ce tuto c’est d’afficher la couche de restaurants par dessus les autres dans la page html, de manière à cliquer sur un restaurant, puis sur un autre.
Merci pour cette idée.
J’ai besoin de calculer l’itinéraire entre 2 restautants pour avoir la distance en m (le champs length_m). est ce possible ?
Il faut avoir un champ length_m avec la longueur en mètres dans la table ways. Dans l’appel de l’algorithme de recherche d’itinéraire (a-star ou dijkstra) vous utilisez la formule length_m as cost pour utiliser cette longueur comme facteur de coût. Vous aurez le coût de chaque tronçon dans le résultat.Il suffit de calculer la somme des coûts des tronçons résultat pour avoir la distance entre les deux restaurants.