{"id":3261,"date":"2016-05-31T07:50:21","date_gmt":"2016-05-31T06:50:21","guid":{"rendered":"http:\/\/www.sigterritoires.fr\/?p=3261"},"modified":"2023-06-28T12:51:09","modified_gmt":"2023-06-28T10:51:09","slug":"developper-une-application-avec-pgrouting-sous-windows-2lalgorithme-a-star","status":"publish","type":"post","link":"https:\/\/www.sigterritoires.fr\/index.php\/developper-une-application-avec-pgrouting-sous-windows-2lalgorithme-a-star\/","title":{"rendered":"D\u00e9velopper une application avec pgrouting sous Windows (2):l’algorithme A-star"},"content":{"rendered":"

Nous continuerons \u00e0 utiliser la base de donn\u00e9es et les outils d\u00e9crits dans l’article pr\u00e9c\u00e9dent (D\u00e9velopper une application avec pgrouting sous Windows (1)).<\/p>\n

L’algorithme A* est un algorithme de recherche de chemin dans un graphe entre un n\u0153ud initial et un n\u0153ud final. Il utilise une \u00e9valuation heuristique sur chaque n\u0153ud pour estimer le meilleur chemin y passant, et visite ensuite les n\u0153uds par ordre de cette \u00e9valuation heuristique.<\/p>\n

Avec l’algorithme de Dijkstra, ce sont les algorithmes les plus utilis\u00e9s pour le calcul du plus court chemin entre deux points d’un r\u00e9seau lin\u00e9aire.<\/p>\n

Requ\u00eate A<\/h2>\n
La syntaxe de l’algorithme A est la suivante:<\/p>\n
pgr_astar(sql<\/strong><\/em> text, source<\/strong> <\/em>integer, target<\/strong> <\/em>integer,directed<\/strong> <\/em>boolean, has_rcost<\/strong><\/em> boolean);<\/p>\n
O\u00f9 source<\/strong> <\/em>est le point de d\u00e9parte souhait\u00e9 de l’itin\u00e9raire, target<\/strong> <\/em>le point d’arriv\u00e9e de l’itin\u00e9raire et la cha\u00eene sql<\/strong> <\/em>est de type:<\/p>\n
SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM r\u00e9seau<\/p>\n
Nous verrons plus loin les deux variables bool\u00e9ennes et leur utilisation.<\/p>\n
La commande retourne un \u00e9l\u00e9ment pgr_costResult<\/strong><\/em> qui contient (seq, id1, id2, cost), o\u00f9 seq<\/strong> <\/em>est l’ordre du tron\u00e7on dans l’itin\u00e9raire, id1<\/strong> <\/em>le point de d\u00e9part du tron\u00e7on, id2<\/strong> <\/em>le point d’arriv\u00e9e du tron\u00e7on et cost<\/strong> <\/em>le co\u00fbt associ\u00e9 \u00e0 ce tron\u00e7on.<\/p>\n
Pr\u00e9paration de la base de donn\u00e9es<\/h2>\n
Contrairement aux autres algorithmes de pgrouting, pour utiliser A* il faut ajouter, si n\u00e9cessaire, les coordonn\u00e9es en latitude\/longitude des n\u0153uds d\u00e9but et fin de chaque tron\u00e7on.<\/p>\n
Si vous avez suivi la cr\u00e9ation de la base de donn\u00e9es dans l’article pr\u00e9c\u00e9dent en important des donn\u00e9es OpenStreeMap avec osm2pgrouting, vous n’avez rien \u00e0 faire car ce programme g\u00e9n\u00e8re les champs x1, y1, x2, y2 n\u00e9cessaires \u00e0 la m\u00e9thode A<\/p>\n
$\"champs$ <\/a>Si ces champs ne sont pas pr\u00e9sents dans votre couche r\u00e9seau, il va falloir les cr\u00e9er.<\/p>\n
Mais au pr\u00e9alable il faut v\u00e9rifier le type de g\u00e9om\u00e9trie de votre r\u00e9seau. Dans pgAdmin III, s\u00e9lectionnez le champ g\u00e9om\u00e9trie de votre table:<\/p>\n
$\"type$ <\/a>Probl\u00e8me: g\u00e9om\u00e9trie MultiLineString ou LineString?<\/h3>\n
Vous pouvez retrouver deux types de g\u00e9om\u00e9trie: LineString et MultiLineString. Les commandes utilis\u00e9es pour calculer les coordonn\u00e9es des n\u0153uds ne marchent que sur des g\u00e9om\u00e9tries LineString. Si vous avez une g\u00e9om\u00e9trie MultiLineString, inutile d’essayer. Vous n’aurez pas de message d’erreur, mais vos colonnes resteront d\u00e9sesp\u00e9r\u00e9ment vides.<\/p>\n
Ceci est d’autant plus b\u00eate, que vous avez 99.99% de probabilit\u00e9s de ne pas avoir r\u00e9ellement une g\u00e9om\u00e9trie MultiLine String! Si vous utilisez l’utilitaire PostGis<\/a> Shapefile<\/a> and DBF loader, vous aurez par d\u00e9faut ce type de g\u00e9om\u00e9trie, m\u00eame si vos donn\u00e9es sont des LineString.<\/p>\n
SOLUTION:<\/h3>\n
Testez la g\u00e9om\u00e9trie pour v\u00e9rifier qu’elle n’est pas forc\u00e9ment MultiLineString avec la commande SQL suivante<\/p>\n
SELECT COUNT(<\/strong>
\n CASE WHEN ST_NumGeometries(the_geom) > 1 THEN 1 END<\/strong>
\n ) AS multi, COUNT(the_geom) AS total<\/strong>
\n FROM ways;<\/strong><\/p>\n
$\"test$ <\/a><\/p>\n
Si le r\u00e9sultat de Multi est 0<\/strong>, vous n’avez pas de multilignes et vous pouvez changer le type de g\u00e9om\u00e9trie en LineString avec la commande SQL<\/p>\n
ALTER TABLE ways<\/strong>
\n ALTER COLUMN the_geom TYPE geometry(LineString, 4326)<\/strong>
\n USING ST_GeometryN(the_geom, 1);<\/strong><\/p>\n
Maintenant vous pouvez cr\u00e9er les champs x1, y1, x2, y2 avec les commandes sql suivantes:<\/p>\n
ALTER TABLE ways ADD COLUMN x1 double precision;<\/strong>
\n ALTER TABLE ways ADD COLUMN y1 double precision;<\/strong>
\n ALTER TABLE ways ADD COLUMN x2 double precision;<\/strong>
\n ALTER TABLE ways ADD COLUMN y2 double precision;<\/strong><\/p>\n
UPDATE ways SET x1 = ST_x(ST_PointN(the_geom, 1));<\/strong>
\n UPDATE ways SET y1 = ST_y(ST_PointN(the_geom, 1));<\/strong><\/p>\n
UPDATE ways SET x2 = ST_x(ST_PointN(the_geom, ST_NumPoints(the_geom)));<\/strong>
\n UPDATE ways SET y2 = ST_y(ST_PointN(the_geom, ST_NumPoints(the_geom)));<\/strong><\/p>\n
$\"cr\u00e9ation$ <\/a>Probl\u00e8me: choix du \u00ab\u00a0co\u00fbt\u00a0\u00bb d’un tron\u00e7on.<\/h3>\n
L’algorithme de routage recherche le chemin avec le co\u00fbt le plus faible. En fonction de vos objectifs, vous devez d\u00e9cider quel \u00e9l\u00e9ment de co\u00fbt vous allez prendre en charge.<\/p>\n
Reprenons notre base OpensStreetMap. Vous avez un champ \u00ab\u00a0cost\u00a0\u00bb qui reprend la longueur du tron\u00e7on en degr\u00e9s. Si vous utilisez ce champ dans l’algorithme A comme valeur de co\u00fbt, l’itin\u00e9raire propos\u00e9 sera le plus court chemin entre les deux points choisis. Voyons un exemple.<\/p>\n
La commande suivante calcule l’itin\u00e9raire entre les points 69072 et 64204 en utilisant le champ \u00ab\u00a0cost\u00a0\u00bb qui correspond \u00e0 la longueur du tron\u00e7on.<\/p>\n
SELECT seq, id1 AS node, id2 AS edge, di.cost, the_geom<\/strong>
\n FROM pgr_astar(<\/strong>
\n ‘SELECT gid as id, source::integer, target::integer, cost::double precision, x1, y1, x2, y2 FROM public.ways’,<\/strong>
\n 69072, 64204, false, false<\/strong>
\n ) as di<\/strong>
\n JOIN public.ways ways_vertices_pgr<\/strong>
\n ON di.id2 = ways_vertices_pgr.gid ;<\/strong><\/p>\n
$\"calcul$ <\/a>Le r\u00e9sultat, une fois charg\u00e9 dans QGis, est le suivant:<\/p>\n
$\"r\u00e9sultat$ <\/a>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 \u00e0 110km\/h…<\/p>\n
Dans la table OSM vous trouvez un autre champ, d\u00e9nomm\u00e9 cost_s. Celui-ci est le r\u00e9sultat du calcul du temps de parcours en secondes , en prenant les informations de longueur et de vitesse autoris\u00e9e pour chaque tron\u00e7on.<\/p>\n
Si on modifie la requ\u00eate sql pour utiliser ce champ:<\/p>\n
SELECT seq, id1 AS node, id2 AS edge, di.cost, the_geom<\/strong>
\n FROM pgr_astar(<\/strong>
\n ‘SELECT gid as id, source::integer, target::integer, cost_s::double precision as cost, x1, y1, x2, y2 FROM public.ways’,<\/strong>
\n 69072, 64204, false, false<\/strong>
\n ) as di<\/strong>
\n JOIN public.ways ways_vertices_pgr<\/strong>
\n ON di.id2 = ways_vertices_pgr.gid ;<\/strong><\/p>\n
$\"utilisation$ <\/a>Le r\u00e9sultat, une fois charg\u00e9 dans QGis est le suivant (trac\u00e9 en rouge)<\/p>\n
$\"r\u00e9sultat$ <\/a>Probl\u00e8me : cost_s a des valeurs nulles<\/h3>\n
Il y a des fortes chances pour que la derni\u00e8re requ\u00eate SQL vous retourne une erreur disant que cost_s a des valeurs nulles.<\/p>\n
Ceci vient du fait que le champ qui est utilis\u00e9 par osm2pgrouting pour calculer le co\u00fbt en secondes est la longueur du tron\u00e7on en m (length_m), et que ce champ n’est pas toujours renseign\u00e9.<\/p>\n
SOLUTION:<\/h3>\n
Avec QGis en ayant charg\u00e9 la couche ways<\/strong><\/em>, s\u00e9lectionnez Projet->propri\u00e9t\u00e9s du projet->SCR<\/strong><\/em><\/p>\n
Cochez la case Projection<\/a> \u00e0 la vol\u00e9e<\/strong><\/em> et s\u00e9lectionnez une projection plane, Lambert 95 par exemple.<\/p>\n
Ouvrez la table attributaire de ways<\/strong><\/em>, passez la table en mode \u00e9dition.<\/p>\n
S\u00e9lectionnez tous les enregistrements avec cost_s<\/strong><\/em> nuls<\/p>\n
$\"s\u00e9lection$ <\/a>Vous constaterez que les enregistrements s\u00e9lectionn\u00e9s ont une length_m<\/strong><\/em> nulle aussi.<\/p>\n
$\"length_m$ <\/a><\/p>\n
Avec la calculatrice de champ cochez la case Mettre \u00e0 jour un champ existant<\/strong><\/em>, s\u00e9lectionnez le champ lenght_m<\/strong><\/em> et dans Expression<\/strong> tapez $length<\/strong><\/em><\/p>\n
$\"calcul$ <\/a>Ceci renseignera le champ avec la longueur du tron\u00e7on, calcul\u00e9e selon le syst\u00e8me de coordonn\u00e9es actuel de QGis (lambert95 par exemple).<\/p>\n
Maintenant vous pouvez mettre \u00e0 jour le champ cost_s<\/strong> <\/em>avec l’expression<\/p>\n
**(\u00ab\u00a0length_m\u00a0\u00bb * 3600) \/ (\u00ab\u00a0maxspeed_forward\u00a0\u00bb * 1000)<\/strong><\/p>\n
$\"2pg4\"$ <\/a><\/p>\n
Probl\u00e8me: l’itin\u00e9raire fonctionne \u00e0 contresens<\/h3>\n
Avec les requ\u00eates utilis\u00e9es jusqu’\u00e0 pr\u00e9sent, vous pouvez obtenir des r\u00e9sultats tels que le suivant:<\/p>\n
$\"itin\u00e9raire$ <\/a>L’itin\u00e9raire calcul\u00e9 vous propose de sortir de la voie rapide et de la r\u00e9emprunter \u00e0 contresens!<\/p>\n
Dans les donn\u00e9es OSM, un champ oneway indique, s’il est \u00e9gal \u00e0 1, que le tron\u00e7on n’a qu’un sens de parcours. Les algorithmes de pgrouting n’utilisent pas directement ce champ. Ils utilisent le champ reverse_cost<\/strong><\/em>.<\/p>\n
Vous avez donc un champ cost<\/strong> <\/em>et un champ reverse_cost<\/strong><\/em>. Si la valeur de ces deux champs est la m\u00eame, ceci est compris par l’algorithme comme une route \u00e0 double sens. L’itin\u00e9raire propos\u00e9 pourra donc aller dans les deux sens.<\/p>\n
Si reverse_cost<\/strong><\/em> a une valeur n\u00e9gative, il n’empruntera jamais ce tron\u00e7on dans le sens inverse mais toujours du n\u0153ud source<\/strong> <\/em>vers le n\u0153ud target<\/strong><\/em>. Le tron\u00e7on est imm\u00e9diatement \u00e9cart\u00e9 du graphe r\u00e9sultat. Si non, vous pouvez aussi affecter une valeur extr\u00eamement grande (par exemple 1000000) aux reverse_costs des tron\u00e7ons \u00e0 sens unique. Dans ce cas le tron\u00e7on sera \u00e9valu\u00e9 (d\u00e9favorablement) mais pas \u00e9cart\u00e9 d’embl\u00e9e.<\/p>\n
Pour que l’algorithme prenne en compte ces valeurs il faut modifier les deux param\u00e8tres bool\u00e9ens de la requ\u00eate SQL directed<\/strong> <\/em>et has_reverse<\/strong><\/em>. Il y a quelques subtilit\u00e9s qui d\u00e9passent le cadre de cet article en ce qui est de modifier seulement un des deux param\u00e8tres (true,false et false,true). Globalement, vous mettez les deux param\u00e8tres \u00e0 true<\/strong> pour que l’algorithme fonctionne en prenant en compte les sens interdits.<\/p>\n
Voici la requ\u00eate telle qu’elle doit \u00eatre pour ne pas avoir le probl\u00e8me de contresens sur la voie express:<\/p>\n
$\"modifications$ <\/a><\/p>\n
Probl\u00e8me: reverse_costs_s a des valeurs nulles<\/h3>\n
Comme pour le champ cost_s<\/strong><\/em>, ceci vient du fait que le champ qui est utilis\u00e9 par osm2pgrouting pour calculer le co\u00fbt en secondes est la longueur du tron\u00e7on en m (length_m<\/strong><\/em>), et que ce champ n’est pas toujours renseign\u00e9.<\/p>\n
SOLUTION<\/h3>\n
Comme vous avez en principe rempli toutes les valeurs de costs_s<\/strong><\/em>, il suffit de s\u00e9lectionner dans la table de QGis tous les enregistrements avec des valeurs reverse_costs_s<\/strong><\/em> nulles, puis avec la calculatrice de champs affecter la valeur de costs_s<\/strong><\/em> \u00e0 reverse_costs_s<\/strong><\/em>.<\/p>\n
Nous avons donc, nous m\u00eames, g\u00e9n\u00e9r\u00e9 le probl\u00e8me suivant:<\/p>\n
Probl\u00e8me: reverse_costs_s ne prend pas en compte les sens interdits (m\u00eame valeur que les costs_s correspondants)<\/h3>\n
SOLUTION<\/h3>\n
S\u00e9lectionnez les enregistrements avec oneway<\/strong> <\/em>= 1, puis affectez la valeur -costs_s<\/strong><\/em> au champ reverse_costs_s<\/strong><\/em><\/p>\n**
Les solutions aux deux derniers probl\u00e8mes partent de la base que vous utilisez les donn\u00e9es OSM et font que les tous les enregistrements soient coh\u00e9rents. Bien \u00e9videment, si vous avez un r\u00e9seau particulier et que vous avez adopt\u00e9 d’autres sp\u00e9cifications, il faudra adapter les requ\u00eates pour respecter vos d\u00e9finitions.<\/p>\n
Nous avons fini le tour de l’algorithme A* et de ses probl\u00e8mes les plus courants. Si vous en trouvez d’autres (je vous fais confiance), n’h\u00e9sitez pas \u00e0 laisser un commentaire.<\/p>\n
Dans le prochain article nous verrons comment(ne) fonctionnent (pas) les autres algorithmes de routage sous Windows.<\/p>\n","protected":false},"excerpt":{"rendered":"
L’extension pgrouting propose divers algorithmes pour rechercher le meilleur itin\u00e9raire :Dijkstra, A,Ksp,Trsp,… Dans cet article nous allons voir en d\u00e9tail l’utilisation de a (A-star).<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"give_campaign_id":0,"_bbp_topic_count":0,"_bbp_reply_count":0,"_bbp_total_topic_count":0,"_bbp_total_reply_count":0,"_bbp_voice_count":0,"_bbp_anonymous_reply_count":0,"_bbp_topic_count_hidden":0,"_bbp_reply_count_hidden":0,"_bbp_forum_subforum_count":0,"sfsi_plus_gutenberg_text_before_share":"","sfsi_plus_gutenberg_show_text_before_share":"","sfsi_plus_gutenberg_icon_type":"","sfsi_plus_gutenberg_icon_alignemt":"","sfsi_plus_gutenburg_max_per_row":"","_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[311,62],"tags":[329,327,326,227,312,58],"class_list":["post-3261","post","type-post","status-publish","format-standard","hentry","category-postgresql","category-qgis-2","tag-a-star","tag-itineraire","tag-pgrouting","tag-postgis","tag-postgresql","tag-qgis"],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p6XU0A-QB","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/posts\/3261","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/comments?post=3261"}],"version-history":[{"count":0,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/posts\/3261\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/media?parent=3261"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/categories?post=3261"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/tags?post=3261"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

SOLUTION:<\/h3>\nAvec QGis en ayant charg\u00e9 la couche ways<\/strong><\/em>, s\u00e9lectionnez Projet->propri\u00e9t\u00e9s du projet->SCR<\/strong><\/em><\/p>\n