5

Recently, I wanted to test pgRouting ver. 2.0. I created the database structure with osm2po and imported UK map from geofabrik. The data was imported correctly.

When I execute a sample query in order to find the shortest path with dijkstra algorithm I receive the result in ~70 sec. When I do the same with astar algorigthm I get the result in over 145 sec. Theoritically, the result of astar should be faster than dijkstra's one but it's not.

Queries I execute:

Dijkstra

SELECT seq, id1 AS node, id2 AS edge, cost 
    FROM pgr_dijkstra(
        'SELECT id::integer, source::integer, target::integer, cost::double precision AS cost 
             FROM hh_2po_4pgr'::text, 60, 80, false, false);

Astar

SELECT seq, id1 AS node, id2 AS edge, cost 
FROM pgr_astar(
    'SELECT id AS id, source::integer, target::integer, cost::double precision AS cost, x1, y1, x2, y2 
        FROM hh_2po_4pgr', 60, 80, false, false);

I checked the Astar implementation in pgRouting and it seems that it uses this heuristic: (|dx|+|dy|)/2.

Am I doing something wrong in my queries or there is something wrong with pgr_astar() implementation in pgRouting?

6
  • Are you sure that (|dx|+|dy|)/2 is the heuristic? This seems strange. What are dx, dy? The heuristic must be added somewhere to the costs before inserted into the PQ.
    – Carsten
    Commented Feb 10, 2014 at 16:19
  • I took it straight from: github.com/pgRouting/pgrouting/blob/master/src/astar/src/… lines 71-74 (comment section) Commented Feb 11, 2014 at 20:14
  • The heuristic looks very strange.
    – Carsten
    Commented Feb 19, 2014 at 18:48
  • So what is your guess? That heuristic is wrong in official implementation of pgRouting? Commented Mar 11, 2014 at 6:53
  • looks like a heuristic based on the Manhattan-Distance. If not, the data must be projected somewhere before. Nevertheless, I would have expected a distance calculation. Some Euklidian function or sth. like that.
    – Carsten
    Commented Mar 14, 2014 at 19:32

1 Answer 1

0

Do you have whole europe ? If so, those times are probably what you can expect. I have experience only from Finnish osm dataset , with that i got under 1 sec constantly without limiting dataset.

Few performance pointer: Double check that you have indexes, if you have not tuned base postgresql.conf to use more memory , do it (defaults are very very low ). If you really need max performance from database , consider tablespace on RAMDISK. And last but not least limit your data. Why is any pgr_* routing function taking forever based on OSM data in an pgrouting enabled DB had some converstation about it.

2
  • 1
    As I wrote above I imported UK not europe. But the question was not about time of execution of the each query (in meaning that they are executing too long) but rather about why the Astar algorithm is slower than Dijkstra. Commented Jan 30, 2014 at 19:08
  • @KamilKubacki If that is your question then I think you need to edit your question to make that clearer.
    – PolyGeo
    Commented Dec 4, 2017 at 22:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.