6

I have a large graph that contains edges of Europe. I want to calculate the shortest path between two points on this graph with pgRouting that have a function pgr_trsp for shortest path calculations.

This pgr_trsp needs a sql query as a text that filters the edges of the graph for a specified shortest path calculation. Since the calculation is very slow if I give the whole Europe graph to the pgr_trsp, I want to give only the specified territory that is used by the shortest path.

But I have to be careful, because pgr_trsp will calculate the shortest path only on the filtered graph. If this filtered graph does not contain edges that are necessary for finding the real shortest path, then I will get a false shortest path.

So the trade-off is to filter the graph to contain as few edges as it is possible, but do not miss any edge that is necessary for calculating the real shortest path.

My edges are classified into 6 classes regarding to its importance:

  • 0 : roads of international importance (most important highways)
  • 1 : roads of national importance (highways and most important roads)
  • 2 : roads of regional importance (making larger settlements and parts of settlements accessible)
  • 3 : local roads of high importance (making minor settlements accessible)
  • 4 : local roads
  • 5 : local roads of minor importance (unpaved roads, roads in 30km/h zones, back roads etc.)
  • 6 : restricted roads (roads that are not accessible for normal traffic)

I made a quick demonstration about the roads class(0,1,2,3). On the picture below you can see that how the road class(0,1,2,3) graph looks:

Roads of class 0,1,2,3

It is a continuous graph of course, but here I show only smaller circles due to the performance of the visualization tool.

All of these colorful edges belong to class(0,1,2,3). You can see on the very left part of the picture a green circle with several blue markers. This is a big city where the edges (class(0,1,2,3)) are very dense: average distance between edges about 1.5km. They are much rarer in the country where the average distance between two edges about 20km.

It means that if I put a point anywhere on the map, I can find a more important road within 1.5km in the city, and 20km in the country. So if I find the closest edge for the point, I need to involve every roads in 1.5km diameter circle around the closest edge in the city and 20km diameter circle in the country into shortest path calculation. I make this step for the second point as well, and after that I involve the class(0,1,2,3) roads between the two points around the line that connects them.

Now it is clear that if I use a 1.5 km diameter in the country it is very possible that I will not find the link to the roads class(0,1,2,3) that are between the two points around the connecting line. If I use 20km diameter for finding the link between the surroundings of the points and the higher classified roads, then I will involve too many edges in the city and the calculation will be slow.

I can complicate the query if I try to find whether a point is in a city or not, and belongs to this use a longer or shorter diameter. But now it is difficult to decide whether a point is in the city or out of it. And it seems to me that this solution is not the best way.

Does anybody know how the Titans (big companies) do this? What is the best practice? You can suggest me a book, or article as well. But if you know the best solution, you are welcome of course! :-)

1

You can create a query to select all edges within some distance of the start and end points and then only the major roads in the bbox between the the start and end points. So something like:

select * from edges where st_dwithin(the_geom, start_pt, radius) union select * from edges where st_dwithin(the_geom, end_pt, radius) union select * from edges where st_expand(st_setsrid(st_makeline(start_pt, end_point), st_srid(start_pt)), radius) && the_geom and road_class < 4;

As an alternative to the third select you could try:

select * from edges where st_dwithin(st_buffer(st_setsrid(st_makeline(start_pt, end_point), st_srid(start_pt)), radius) && the_geom and road_class < 4;

This will make a "sausage" of radius "radius" between the start and end and only select the segments the intersect with that sausage, you might need to increase the diameter by using something like 1.5*radius or 3.0*radius to make sure you are getting all the segments you need for the solution.

  • Thank you Stephen. This is similar to our present solution. But I am not sure that this is the most powerful solution. I mean that for calculating a route between two points that are about 200 km away from each other we need about 3-500 milisec. I want to use something better I can reach less than 100 milisec with. – Peter Vida Oct 5 '13 at 20:42
  • And the running time mainly depends on the number of edges that are involve into the trsp calculation. So if we can decrease the number of edges that involved, than the running time will be alse decreased. But the more we decrease the number of edges the more it will not find route between the points. So it seems we have to find a cleverer way (a more compleceted WHERE clause) to decrease the number of edges with the solution you suggested, or we find a completely different method. – Peter Vida Oct 5 '13 at 20:54
  • One of our Google Summer of Code students implemented a AStar search that dynamically loads the graph as required. I designed this to use a partitioning algorithm that allows you to partition your graph into chunk of N nodes based on a quad-tree partitioning algorithm. The trade off with this is that you want to pick a partition size that optimizes the trade offs between having to stop and load incrementally and the related bookkeeping vs just being able to solve the graph. Look in github for branch gsoc-partition. I have not had time to test it much, but it might be an option. – Stephen Woodbridge Oct 6 '13 at 22:02

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.