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