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.
