Why my mobile GPS routing calculates routes almost instantly and using pgRouting in my robust PC is so time costly ?


My test:

In my cellphone (Android 4.2.2 - 1G RAM - Dual core - Arm v9) I have iGo Primo. In my PC ( 8G RAM - Core i5 ) I have Postgre + PostGIS + pgRouting

Table OSM Planet "planet_osm_line" with previous work:

alter table planet_osm_line add column source integer;
alter table planet_osm_line add column target integer;
select pgr_createTopology('planet_osm_line', 0.0001, 'way', 'osm_id');

select * from planet_osm_line where name like '%BR-040%' // (source : 2751784)
select * from planet_osm_line where name like '%BR-101%' // (target : 2040999)

SELECT seq, id1 AS node, id2 AS edge, cost, name, way
  FROM pgr_dijkstra('SELECT osm_id as id, source, target, st_length(way) as cost FROM planet_osm_line',  2751784, 2040999, false, false  ) as di 
  JOIN planet_osm_line pt
  ON di.id2 = pt.osm_id ;

The route is (both Brazil Highway):

Source: BR-040

Target: BR-101

My cellphone do the job in less than two seconds and my PC takes more than 3 minutes (only the SELECT route - pgr_dijkstra - part).

  • 4
    Because your mobile routing is being done on google's cloud (or similar infrastructure)? Could your 'robust PC' search something the size of the internet as quickly as google? – Spacedman Jan 22 '14 at 13:49
  • I don't think so. Even I'm not connected (like iGo Amigo/Primo Maps/Routing GPS), the route calculation is much more faster than my PC. – Magno C Jan 22 '14 at 14:01
  • Does your mobile app have a simpler data set than your pgRouting data? Or maybe you need some optimisations/spatial indexing. Oh well... – Spacedman Jan 22 '14 at 14:05
  • 1
    Have you tried various things? eg: gis.stackexchange.com/questions/16886/… – Spacedman Jan 22 '14 at 14:06
  • 2
    Please people, STOP upvoting google's cloud comment. I'm OFFLINE for sure! – Magno C Jan 22 '14 at 15:42

Probably because it uses pre-calculated routes.

As an example of an open source routing app with pre-calculated routes, OSRM uses contraction hierarchies to create shortcuts: http://algo2.iti.kit.edu/routeplanning.php

PgRouting just creates the relations between source and target with the pgr_network_topology function. http://workshop.pgrouting.org/chapters/topology.html

pgRouting allows you to change conditions in real time. Does your phone app allow you to do that? Like, for example, add traffic data and recalculate the route depending on this new data?

  • 1
    I think Waze do that. waze.com – Magno C Jan 22 '14 at 15:24
  • 1
    Nowadays, almost all routing apps do it offline with a pre-calculated graph. Like OsmAnd too. – María Arias de Reyna Domínguez Jan 22 '14 at 15:25
  • 2
    IMO, pre-calculated graph in one thing and pre-calculated route is another thing. pgr_createTopology creates a pre-calculated graph (source and target columns connects the points). A pre-calculated route needs to "guess" where I want to go. – Magno C Jan 22 '14 at 15:31
  • 1
    I'm sure iGo is offline. Here in Brasil 3G is expensive and low quality (if you coming for World Cup don't try to use it!) and I must keep my mobile offline almost all the time. – Magno C Jan 22 '14 at 15:34
  • Then it should be something related to pre-calculated graphs. If you are looking for something faster on the server side, take a look at project-osrm.org – María Arias de Reyna Domínguez Jan 22 '14 at 15:42

I think the best answer was pointed by @Spacedman here in this post:

How can I optimize pgrouting for speed?

Mario Miler says:

In my experience, if using pgrouting on all dataset (table) then there is no great benefit from Postgres engine. Index is not even used so its useless. On every query whole table is loaded into memory. shared buffers and caches also didn't give any performance benefit because every query loads all the table into memory. If anyone has succeed to reuse loaded data in memory for subsequent queries, please tell us. Only possible performance increase I see in SDD drives, but I have never tested it. More memory only allows more concurrent queries, not performance. – Mario Miler Nov 15 '11 at 16:27

pgRouting "modus operandi" (pgr_dijkstra function) is the source of bad performance.

  • 2
    A couple of years ago I tried to improve pgRouting performance. We improved it a little with a custom algorithm that relied on pgRouting (Shooting Star) as background. The documentation is in Spanish, but maybe it can be useful for you: delawen.github.io/Taller-Routing On slide 7 you can see that Dijkstra is not even the best of pgRouting. (From slide 36 on is the idea we tried to implement) – María Arias de Reyna Domínguez Jan 22 '14 at 16:04
  • Thank you so much for your effort. I need to find new ways to improve my application and you help a lot. – Magno C Jan 22 '14 at 16:06

It takes a long time to solve the network, but once it is done you "just" need to query the graph. Finding the route is thus very fast if you store the graph of your network and it is well indexed.

  • Indeed. Graph creation consumes a huge amount of time, but even this, the routing calculation is too slow. – Magno C Jan 22 '14 at 14:03
  • I've edited my question. Give a look. – Magno C Jan 22 '14 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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