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,

**integer,**

*source*

*target*integer,

**boolean,**

*directed***boolean);**

*has_rcost*Where ** source** is the desired departure point of the route,

*target*the end point of the route and the

**chain is of the following type:**

*sql*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

**is the order of the section in**

*seq*the route,

**the starting point of the section,**

*id1*

*id2*the point of arrival of the section and

**the cost associated**

*cost*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)));

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’,

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’,

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

**with QGis.**

*Project-> project*

properties-> SCRproperties-> SCR

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

**and in**

*lenght_m***Expression**type

*$*

lengthlength

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) / (“

3600) / (“

**maxspeed_forward**

*****

1000)

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

**node . The section is, immediately, removed**

*target*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

**values , then, using the field**

*reverse_costs_s*calculator set the value of

**to**

*costs_s*

*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

**field**

*reverse_costs_s*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.