{"id":7895,"date":"2019-01-24T02:01:24","date_gmt":"2019-01-24T01:01:24","guid":{"rendered":"http:\/\/www.sigterritoires.fr\/?p=7895"},"modified":"2019-01-24T08:27:37","modified_gmt":"2019-01-24T07:27:37","slug":"how-to-develop-an-application-with-pgrouting-in-windows-2-the-a-star-algorithm","status":"publish","type":"post","link":"https:\/\/www.sigterritoires.fr\/index.php\/en\/how-to-develop-an-application-with-pgrouting-in-windows-2-the-a-star-algorithm\/","title":{"rendered":"How to develop an application with pgrouting in Windows (2): the A-star algorithm"},"content":{"rendered":"\n

The pgrouting extension offers various algorithms to find the best\nroute: Dijkstra, A *, Ksp, Trsp, … <\/p>\n\n\n\n

In this article we will discuss in detail the use of a * (A-star). <\/p>\n\n\n\n

We will continue to use the database and tools described in the previous\narticle (How to develop an application with pgrouting inWindows (1)). <\/p>\n\n\n\n

The algorithm A * is a path search algorithm in a graph between an\ninitial node and an end node. It uses a heuristic evaluation on each node to\nestimate the best path passing through it, and then visits the nodes according\nto their order in this heuristic evaluation. <\/p>\n\n\n\n\n\n\n\n

Together with the Dijkstra’s algorithm, these are the most used\nalgorithms for calculating the shortest path<\/a> between two points of a linear\nnetwork. <\/p>\n\n\n\n

Request A *<\/strong> <\/p>\n\n\n\n

The syntax of the A * algorithm is as follows: <\/p>\n\n\n\n

pgr_astar ( sql<\/em><\/strong> text, source<\/em><\/strong> integer, target<\/em><\/strong>\ninteger, directed<\/em><\/strong> boolean, has_rcost<\/em><\/strong> boolean); <\/p>\n\n\n\n

Where source<\/em><\/strong> is the desired departure point of the route, target<\/em><\/strong>\nthe end point of the route and the sql<\/em><\/strong> chain is of the following type:\n<\/p>\n\n\n\n

SELECT id, source, target, cost, x1, y1, x2, y2 [, reverse_cost] FROM\nnetwork <\/p>\n\n\n\n

We will discuss later the two Boolean variables and their use. <\/p>\n\n\n\n

The command returns a pgr_costResult<\/em><\/strong> element that includes\n(seq, id1, id2, cost), where seq<\/em><\/strong> is the order of the section in\nthe route, id1<\/em><\/strong> the starting point of the section, id2<\/em><\/strong>\nthe point of arrival of the section and cost<\/em><\/strong> the cost associated\nwith this stretch. <\/p>\n\n\n\n

Preparation of the database<\/strong> <\/p>\n\n\n\n

Unlike other pgrouting algorithms, to use A * you must add, if\nnecessary, the latitude \/ longitude coordinates of the beginning and end nodes\nof each section. \n\nIf you followed the creation of the database in\nthe previous article by importing OpenStreeMap data with osm2pgrouting, you\nhave nothing to do because this program generates the fields x1, y1, x2, y2 needed\nfor method A *   \n\n\n\n<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

If these fields are not present in your network layer, you will have to\ncreate them. \n\nBut, firstly, you have to check the type of\ngeometry of your network. In pgAdmin III, select the geometry field of your\ntable:  \n\n\n\n<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Problem: MultiLineString geometry or LineString?<\/strong> <\/p>\n\n\n\n

You can find two types of geometry: LineString and MultiLineString. Commands\nused to compute node coordinates only work with LineString geometries. If you\nhave a MultiLineString geometry, not a chance!. You will not get an error\nmessage, but your columns will remain desperately empty. <\/p>\n\n\n\n

This is particularly silly since you have 99.99% probability of not\nreally having a MultiLine String geometry! If you use the PostGis<\/a> Shapefile<\/a>\nutility and DBF loader, you will have this type of geometry by default, even if\nyour data is LineString. <\/p>\n\n\n\n

SOLUTION:<\/strong> <\/p>\n\n\n\n

Test the geometry to verify that it is not necessarily MultiLineString\nwith the following SQL command SELECT COUNT (<\/strong>
CASE WHEN ST_NumGeometries (the_geom)> 1 THEN 1 END<\/strong>
) AS multi, COUNT (the_geom) AS total<\/strong>
FROM ways;<\/strong><\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

If the result of Multi is 0<\/strong> , you do not have multilines and you\ncan change the geometry type to LineString with the SQL command <\/p>\n\n\n\n

ALTER TABLE ways<\/strong>
\nALTER COLUMN the_geom geometry TYPE (LineString, 4326)<\/strong>
\nUSING ST_GeometryN (the_geom, 1);<\/strong> <\/p>\n\n\n\n

Now you can create the fields x1, y1, x2, y2 with the following sql\ncommands: <\/p>\n\n\n\n

ALTER TABLE ways COLUMN ADD x1 double precision;<\/strong>
\nALTER TABLE ways ADD COLUMN y1 double precision;<\/strong>
\nALTER TABLE ways ADD COLUMN x2 double precision;<\/strong>
\nALTER TABLE ways ADD COLUMN y2 double precision;<\/strong> <\/p>\n\n\n\n

UPDATE ways SET x1 = ST_x (ST_PointN (the_geom,\n1));<\/strong>
\nUPDATE ways SET y1 = ST_y (ST_PointN (the_geom, 1));<\/strong> UPDATE ways SET x2 = ST_x (ST_PointN (the_geom,\nST_NumPoints (the_geom)));<\/strong>
UPDATE ways SET y2 = ST_y (ST_PointN (the_geom, ST_NumPoints (the_geom)));<\/strong><\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Problem: choosing the \u201ccost\u201d<\/strong> of a section.<\/strong> <\/p>\n\n\n\n

The routing algorithm looks for the path with the lowest cost. Depending\non your goals, you have to decide which cost item you will support. <\/p>\n\n\n\n

Let’s take our OpenStreetMap database. You have a field   \u201ccost\u201d\n  that gets back the length of the section in degrees. If you use this\nfield in the A * algorithm as the cost value, the proposed route will be the\nshortest path between the two chosen points. Let’s see an example. <\/p>\n\n\n\n

The following command calculates the route between points 69072 and\n64204 using the \u201ccost\u201d   that corresponds to the length of the section. SELECT seq, id1 AS node, id2 AS edge, di.cost,\nthe_geom<\/strong>
FROM pgr_astar (<\/strong>
‘SELECT gid as id, source :: integer, target :: integer, cost :: double\nprecision, x1, y1, x2, y2 FROM public.ways’,<\/strong>
69072, 64204, false, false<\/strong>
) as di<\/strong>
JOIN public.ways ways_vertices_pgr<\/strong>
ON di.id2 = ways_vertices_pgr.gid;<\/strong><\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nOnce\nloaded into QGis, the result is as follows:   \n\n\n\n<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

On foot, it’s the best route. But by car we would never take it! Small\nstreets with 30km \/ h zones instead of a 110km \/ h fast track… <\/p>\n\n\n\n

In the OSM table you find another field, called cost_s. This is the\nresult of calculating the travel time in seconds, by using the length and speed\nallowed for each section. <\/p>\n\n\n\n

If you modify the sql query to use this field: SELECT seq, id1 AS node, id2 AS edge, di.cost,\nthe_geom<\/strong>
FROM pgr_astar (<\/strong>
‘SELECT gid as id, source :: integer, target :: integer, cost_s :: double\nprecision as cost, x1, y1, x2, y2 FROM public.ways’,<\/strong>
69072, 64204, false, false<\/strong>
) as di<\/strong>
JOIN public.ways ways_vertices_pgr<\/strong>
ON di.id2 = ways_vertices_pgr.gid;<\/strong><\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nOnce\nloaded in QGis, the result is the following (red line)\n\n\n\n<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Problem: cost_s has null values<\/strong> <\/p>\n\n\n\n

There is a good chance that the last SQL query will return an error\nsaying that cost_s has null values. <\/p>\n\n\n\n

This is because the field that is used by osm2pgrouting to calculate the\ncost in seconds is the length of the section in m (length_m), and this field is\nnot always filled in. <\/p>\n\n\n\n

SOLUTION:<\/strong> <\/p>\n\n\n\n

After loading the ways<\/em><\/strong> layer , select Project-> project\nproperties-> SCR<\/em><\/strong> with QGis.<\/p>\n\n\n\n

Check the Projection<\/a> on the fly box<\/em><\/strong> and select a flat\nprojection, Lambert 95 for example. <\/p>\n\n\n\n

Open the attributes table of ways<\/em><\/strong> , pass the table in edit\nmode. \n\nSelect all records with zero cost_s<\/em><\/strong><\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nYou\nwill notice that the selected records have a zero length_m<\/em><\/strong>  as well.  \n\n\n\n<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nUsing\nthe field calculator check the box Update an existing field<\/em><\/strong> ,\nselect the field lenght_m<\/em><\/strong> and in Expression<\/strong> type $\nlength<\/em><\/strong><\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

This will inform the field the length of the section, calculated\naccording the current QGis coordinate system (lambert95 for example). <\/p>\n\n\n\n

Now you can update the cost_s<\/em><\/strong> field with the expression ( ‘<\/strong>length_m<\/strong>\u00ab\u00a0*\n3600) \/ (\u00ab\u00a0<\/strong>maxspeed_forward<\/strong>*\n1000)<\/strong><\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Problem: The route works in the opposite direction<\/strong> \n\nWith the queries used so far, you can get\nresults such as the following: \n\n\n\n<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

The calculated route suggests you to get out of the fast lane and follow\nit in the opposite direction! <\/p>\n\n\n\n

In the OSM data, a oneway field indicates, if it is equal to 1, that the section has only one direction of travel. Pgrouting algorithms do not use this field directly. They use the reverse_cost<\/em><\/strong> field . <\/p>\n\n\n\n

So you have a field cost<\/em><\/strong> and a reverse_cost<\/em><\/strong>\nfield . If the value of these two fields is the same, the algorithm reads it as\na two-way street. The proposed route can, therefore, go both ways. <\/p>\n\n\n\n

If reverse_cost<\/em><\/strong> has a negative value, it will never take\nthis section in the opposite direction but, always, from the source<\/em><\/strong>\nnode to the target<\/em><\/strong> node . The section is, immediately, removed\nfrom the resulting graph. If not, you can also assign an extremely large value\n(for example 1000000) to the reverse_costs of the one-way sections. In this\ncase the section will be evaluated (unfavorably) but not rejected immediately. <\/p>\n\n\n\n

For the algorithm to take into account these values, you must modify the\ntwo boolean parameters of the SQL query directed<\/em><\/strong> and has_reverse<\/em><\/strong>\n. There are some subtleties that go beyond the scope of this article concerning\nthe change of only one of the two parameters (true, false   and false,\ntrue). Overall, you set both parameters as true<\/strong> so that the algorithm\nworks by taking into consideration the forbidden directions. \n\nHere is the request as it should be to avoid the\nmisinterpretation problem in the expressway:  \n\n\n\n<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Problem: reverse_costs_s has null values<\/strong> <\/p>\n\n\n\n

As for the field cost_s<\/em><\/strong> , this problem arises due to  the fact that the field being used by osm2pgrouting\nto calculate the cost in seconds is the length of the section in m ( length_m<\/em><\/strong>\n), and, that this field is not always filled. <\/p>\n\n\n\n

SOLUTION<\/strong> <\/p>\n\n\n\n

Since you have, in theory,  filled\nall the values \u200b\u200bof costs_s<\/em><\/strong> , just select in the QGis table all the\nrecords with null reverse_costs_s<\/em><\/strong> values , then, using the field\ncalculator set the value of costs_s<\/em><\/strong> to reverse_costs_s<\/em><\/strong>\n. <\/p>\n\n\n\n

But now, we have generated the following problem: <\/p>\n\n\n\n

Problem: reverse_costs_s does not take into account\nthe forbidden direction (same value as the corresponding costs_s)<\/strong> <\/p>\n\n\n\n

SOLUTION<\/strong> <\/p>\n\n\n\n

Select the records with oneway<\/em><\/strong> = 1, then set the -costs_s<\/em><\/strong>\nvalue to the reverse_costs_s<\/em><\/strong> field <\/p>\n\n\n\n

The solutions to the last two problems start up in the base you are\nusing for the OSM data and render all the records consistent. Of course, if you\nhave a particular network and have adopted other specifications, you will need\nto adapt the queries to meet your definitions. <\/p>\n\n\n\n

We have finished the tour of the algorithm A * and its most common\nproblems. If you find others (I trust you), do not hesitate to leave a comment.\n<\/p>\n\n\n\n

In the next article we will discuss how (do\/do not) work the other\nrouting algorithms with Windows. <\/p>\n","protected":false},"excerpt":{"rendered":"

The pgrouting extension offers various algorithms to find the best route: Dijkstra, A *, Ksp, Trsp, … In this article we will discuss in detail the use of a * (A-star). We will continue to use…<\/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":[1260],"tags":[],"class_list":["post-7895","post","type-post","status-publish","format-standard","hentry","category-non-classe-en"],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p6XU0A-23l","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/posts\/7895","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=7895"}],"version-history":[{"count":0,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/posts\/7895\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/media?parent=7895"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/categories?post=7895"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/tags?post=7895"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}