How to filter the graph on which I want to find the shortest path

Question

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:

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! :-)

Answer 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.5radius or 3.0radius to make sure you are getting all the segments you need for the solution.