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
    Feb 10 '14 at 16:19
  • I took it straight from: github.com/pgRouting/pgrouting/blob/master/src/astar/src/… lines 71-74 (comment section) Feb 11 '14 at 20:14
  • The heuristic looks very strange.
    – Carsten
    Feb 19 '14 at 18:48
  • So what is your guess? That heuristic is wrong in official implementation of pgRouting? Mar 11 '14 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
    Mar 14 '14 at 19:32
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. Jan 30 '14 at 19:08
  • @KamilKubacki If that is your question then I think you need to edit your question to make that clearer.
    – PolyGeo
    Dec 4 '17 at 22:44

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