4

I need to develop the shortest path routing query in PostgreSQL. I have my own map data that is a shapefile. From that shapefile I have made PostgreSQL database. It is a large database with around 60k entries. I have made one edge table from the dataset and then created the topology. Lastly tried with astar and dijkstra algorithm (pgr_astar and pgr_dijkstra). It is giving the shortest path but the pgr_astar or pgr_dijkstra query takes at least 3 to 4 sec to provide the result. But I need it faster, may be in msec.

There are lots of applications with routing in market and in those cases routing results come within fraction of seconds. What are the tricks to make it faster?

I have checked a few tricks to speed up. There are highway hierarchies, busy node hierarchies. But I can't use these to my application as most of my roads are forest roads. And my start and/or destination point is a point somewhere in between forests; not a city centre of a big city (so, not a busy node).

I tried to generate clusters and then to pre-compute routes between clusters. But thus the database is growing significantly. So, I am not sure whether it will increase the speed or not.

Can you give any more easy idea to solve this problem?

Improve this question
13
  • 1
    A lot of the tricks are due to heuristics for pruning possible paths. In pgRouting, you pass a table name into say, pgr_dijkstra, from which a graph is created. So, if you were just searching in California, it would be pointless to pass in a table representing roads in New York, for example. So, one thing you can do is pass a subset of the 60k entries into the function, if you know you will only be searching in a certain area.
    – John Powell
    Commented Feb 14, 2017 at 13:35
  • Ok, but I don't know my searching area
    – LSG
    Commented Feb 14, 2017 at 13:36
  • There are other tricks as well, such as pre-computing main routes between major nodes, eg, San Francisco and New York. If you are starting from somewhere in rural Nebraska, once you hit this trunk, you don't need to explore up into New Hampshire or down into Florida. When you say there are lots of applications, you are talking about the Googles, Heres and Tomtoms of this world, who will have lots of other tricks, such as pre-computed routes, parallellized searches, and giant datacentres with fast cores. So, while they might use A* or Djikstra at some level, there are other things going on.
    – John Powell
    Commented Feb 14, 2017 at 14:17
  • 1
    Modern routing tools like Graphhopper and Open Source Routing Machine use Contraction Hierachies, which is some kind of pre-computing. With CH calculating a route takes much less than 1 sec, using ordinary hardware. Unfortunately, pgRouting has not implemented this algorithm yet.
    – Mesa
    Commented Apr 4, 2018 at 8:06
  • 2
    pgRouting has the ability the pre-process data and do some sort of contraction. But it's not an out-of-the-box tool. It's a library, where you need to specify, how you want to contract your graph. Furthermore it's rather new functionality and therefor marked as "experimental": docs.pgrouting.org/latest/en/…
    – dkastl
    Commented Apr 5, 2018 at 3:37

0

Reset to default

Browse other questions tagged or ask your own question.