Questions about the "A more complex solution..." paragraph in the "The enhancements" section of the blog post which explains the algorithm used for map-matching

Open Source Routing Engine Map Matching
1

Hi all,

I am reading the blog post which explains the algorithm used for map-matching, and I find the following paragraph in the “The enhancements” section a bit unclear:

A more complex solution could be to maintain a list of e.g. 3 alternative end-results. As you already get 3 edge candidates for every GPX point you can then try to find all routes between them. You could think that this will slow down the search a lot but with GraphHopper you can tweak e.g. the Dijkstra or DijkstraOneToMany algorithm to do this in an efficient manner. E.g. if you want to get the best result but you want to search from multiple destinations you can do: DijkstraBidirectionRef dijkstra = new DijkstraBidirectionRef(hopper.getGraph(), flagEncoder, weighting); dijkstra.initFrom(nodeFrom, distanceToPossibility1); dijkstra.initFrom(node, distanceToPossibility2); … dijkstra.initTo(nodeTo, distanceToEndPossibility1); dijkstra.initTo(nodeTo, distanceToEndPossibility2); …

Does it mean that 1) between each two consecutive GPX points, I find 3*3 = 9 paths; 2) for the complete GPX points list (assuming N points), I will have 3^N paths; and 3) somehow I maintain a list of 3 alternative paths for the complete GPX points list as end results? I think I must have misunderstood something as this seems quite inefficient.

I am also not clear about the example at the end of the paragraph. After I have done .initFrom() and .initTo() for all 3 edge candidates for both GPX points, how do I get the 9 paths connecting each pair of them? Do I still need to run .calcPath() for 9 times?

Could you please help clarify? Thank you very much.

Best regards,
He

2

between each two consecutive GPX points, I find 3*3 = 9 paths

yes

for the complete GPX points list (assuming N points), I will have 3^N paths;

It is more 33N or if you also span across non-directly adjacent GPX points you get double more.

You do not calculate all combinations you calculate all combinations from GPX points that are near to each other and then reduce to 3 likely versions which you keep when you go to the next point where you find out how the 3 paths are expanded further.

E.g. for 3 GPX points you fetch: 3*3 QueryResults and calculate 9 paths between the first and second and another 9 between the second and 3rd.

somehow I maintain a list of 3 alternative paths for the complete GPX points list as end results

yes, 3 or more. Also you could maintain not just 3 paths but e.g. 3 alternatives for every part and combine the best at the end or something.

3

Hi Peter,

I see. So it is always like 1) having 3 paths in hand before dealing with the next GPX point (0 if at the 1st GPX point); 2) obtaining 3*3 paths b/w the current GPX point and the next; and 3) combining the 3 paths in hand with the new 9 paths and finding the best 3 and then moving on to the next GPX point.

Thanks a lot for your explanation!

Best regards,
He

4

Yes, kind of this. But real world is sometimes more complex and one also has to play with omitting paths etc