3

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?

closed as too broad by Ian Turton Apr 4 '18 at 9:45

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 Feb 14 '17 at 13:35
  • Ok, but I don't know my searching area – LSG Feb 14 '17 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 Feb 14 '17 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 Apr 4 '18 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 Apr 5 '18 at 3:37