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 the database and tools described in the previous article (How to develop an application with pgrouting inWindows (1)).
The algorithm A * is a path search algorithm in a graph between an initial node and an end node. It uses a heuristic evaluation on each node to estimate the best path passing through it, and then visits the nodes according to their order in this heuristic evaluation.
Together with the Dijkstra’s algorithm, these are the most used algorithms for calculating the shortest path between two points of a linear network.
Request A *
The syntax of the A * algorithm is as follows:
pgr_astar ( sql text, source integer, target integer, directed boolean, has_rcost boolean);
Where source is the desired departure point of the route, target the end point of the route and the sql chain is of the following type:
SELECT id, source, target, cost, x1, y1, x2, y2 [, reverse_cost] FROM network
We will discuss later the two Boolean variables and their use.
The command returns a pgr_costResult element that includes (seq, id1, id2, cost), where seq is the order of the section in the route, id1 the starting point of the section, id2 the point of arrival of the section and cost the cost associated with this stretch.
Preparation of the database
Unlike other pgrouting algorithms, to use A * you must add, if necessary, the latitude / longitude coordinates of the beginning and end nodes of each section. If you followed the creation of the database in the previous article by importing OpenStreeMap data with osm2pgrouting, you have nothing to do because this program generates the fields x1, y1, x2, y2 needed for method A *
If these fields are not present in your network layer, you will have to create them. But, firstly, you have to check the type of geometry of your network. In pgAdmin III, select the geometry field of your table:
Problem: MultiLineString geometry or LineString?
You can find two types of geometry: LineString and MultiLineString. Commands used to compute node coordinates only work with LineString geometries. If you have a MultiLineString geometry, not a chance!. You will not get an error message, but your columns will remain desperately empty.
This is particularly silly since you have 99.99% probability of not really having a MultiLine String geometry! If you use the PostGis Shapefile utility and DBF loader, you will have this type of geometry by default, even if your data is LineString.
SOLUTION:
Test the geometry to verify that it is not necessarily MultiLineString
with the following SQL command SELECT COUNT (
CASE WHEN ST_NumGeometries (the_geom)> 1 THEN 1 END
) AS multi, COUNT (the_geom) AS total
FROM ways;
If the result of Multi is 0 , you do not have multilines and you can change the geometry type to LineString with the SQL command
ALTER TABLE ways
ALTER COLUMN the_geom geometry TYPE (LineString, 4326)
USING ST_GeometryN (the_geom, 1);
Now you can create the fields x1, y1, x2, y2 with the following sql commands:
ALTER TABLE ways COLUMN ADD 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)));
Problem: choosing the “cost” of a section.
The routing algorithm looks for the path with the lowest cost. Depending on your goals, you have to decide which cost item you will support.
Let’s take our OpenStreetMap database. You have a field “cost” that gets back the length of the section in degrees. If you use this field in the A * algorithm as the cost value, the proposed route will be the shortest path between the two chosen points. Let’s see an example.
The following command calculates the route between points 69072 and
64204 using the “cost” that corresponds to the length of the section. 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;
Once loaded into QGis, the result is as follows:
On foot, it’s the best route. But by car we would never take it! Small streets with 30km / h zones instead of a 110km / h fast track…
In the OSM table you find another field, called cost_s. This is the result of calculating the travel time in seconds, by using the length and speed allowed for each section.
If you modify the sql query to use this field: 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;
Once loaded in QGis, the result is the following (red line)
Problem: cost_s has null values
There is a good chance that the last SQL query will return an error saying that cost_s has null values.
This is because the field that is used by osm2pgrouting to calculate the cost in seconds is the length of the section in m (length_m), and this field is not always filled in.
SOLUTION:
After loading the ways layer , select Project-> project properties-> SCR with QGis.
Check the Projection on the fly box and select a flat projection, Lambert 95 for example.
Open the attributes table of ways , pass the table in edit mode. Select all records with zero cost_s
You will notice that the selected records have a zero length_m as well.
Using the field calculator check the box Update an existing field , select the field lenght_m and in Expression type $ length
This will inform the field the length of the section, calculated according the current QGis coordinate system (lambert95 for example).
Now you can update the cost_s field with the expression ( ‘length_m“* 3600) / (“maxspeed_forward* 1000)
Problem: The route works in the opposite direction With the queries used so far, you can get results such as the following:
The calculated route suggests you to get out of the fast lane and follow it in the opposite direction!
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 field .
So you have a field cost and a reverse_cost field . If the value of these two fields is the same, the algorithm reads it as a two-way street. The proposed route can, therefore, go both ways.
If reverse_cost has a negative value, it will never take this section in the opposite direction but, always, from the source node to the target node . The section is, immediately, removed from the resulting graph. If not, you can also assign an extremely large value (for example 1000000) to the reverse_costs of the one-way sections. In this case the section will be evaluated (unfavorably) but not rejected immediately.
For the algorithm to take into account these values, you must modify the two boolean parameters of the SQL query directed and has_reverse . There are some subtleties that go beyond the scope of this article concerning the change of only one of the two parameters (true, false and false, true). Overall, you set both parameters as true so that the algorithm works by taking into consideration the forbidden directions. Here is the request as it should be to avoid the misinterpretation problem in the expressway:
Problem: reverse_costs_s has null values
As for the field cost_s , this problem arises due to the fact that the field being used by osm2pgrouting to calculate the cost in seconds is the length of the section in m ( length_m ), and, that this field is not always filled.
SOLUTION
Since you have, in theory, filled all the values of costs_s , just select in the QGis table all the records with null reverse_costs_s values , then, using the field calculator set the value of costs_s to reverse_costs_s .
But now, we have generated the following problem:
Problem: reverse_costs_s does not take into account the forbidden direction (same value as the corresponding costs_s)
SOLUTION
Select the records with oneway = 1, then set the -costs_s value to the reverse_costs_s field
The solutions to the last two problems start up in the base you are using for the OSM data and render all the records consistent. Of course, if you have a particular network and have adopted other specifications, you will need to adapt the queries to meet your definitions.
We have finished the tour of the algorithm A * and its most common problems. If you find others (I trust you), do not hesitate to leave a comment.
In the next article we will discuss how (do/do not) work the other routing algorithms with Windows.
