Routing issues with Landmarks

[easbar]

As noticed in #1665 I found some cases where A-Star with LM does not find the shortest path. I tried to figure out why and here: https://github.com/graphhopper/graphhopper/tree/lm_issue (Update: branch got deleted, but the tests were added with #1745 and 76d37e3). I created a similar test that does not use the new feature of restricted source/target edges as in #1665 (and so far does not use edge-based routing either) and the tests still fail in some cases.

There might be different issues at play:

This test:

graphhopper/core/src/test/java/com/graphhopper/routing/BidirectionalRoutingTest.java

Line 128 in bfc6878

public void lm_problem_to_node_of_fallback_approximator() {

seems to fail, because the LMApproximator uses its fallBackApproximator, but the toNode of the fallBackApproximator is never set leading to an overestimation of the minimum distance. This might be easy to fix and we should do first.

This one:

graphhopper/core/src/test/java/com/graphhopper/routing/BidirectionalRoutingTest.java

Line 181 in bfc6878

public void lm_issue2() {

also fails with a very large weight difference compared to Dijkstra, but I do not know why yet (have not really looked into it).

Not sure if this is related to #1557.

TODOs:

• fix bug(s)
• include tests for LM that were introduced in Adds AbstractBidirAlgo#calcPath with restricted source/target edges. #1665

[karussell]

I have fixed some issues in this branch: https://github.com/graphhopper/graphhopper/tree/lm_bug_1687

• your mentioned missing initialization of the fallbackApproximator
• separate factor for from and delta
• use double instead int for weights for cleaner API and virtual node addition (otherwise unclear which factor applies)
• skip infinite weight when selecting maximum weights of all landmarks
• set unclear subnetwork for smaller subnetworks (and handle smaller subnetworks first <-> sort list). This avoids that a landmark is created in such a smaller subnetwork leading to many maxed out weights as one direction is not reachable to or from the bigger subnetwork
• test performance on bigger instances
• try fallbackApproximator if weight is 0 or less
• we could explore the graph from the landmarks and use the maximum weight there to call setMaximumWeight, instead of the guess based on the area

Unfortunately some of the raised issues from random tests are not that critical because often just the factor is incorrectly guessed and so increasing prepareLandmarks.setMaximumWeight(1000) to 10000 helped. It seems that also a too small max weight leads to incorrect routes (too much heuristic) not only too small like already documented in the javadocs.

[easbar]

Unfortunately some of the raised issues from random tests are not that critical

Hmm yes I can imagine, maybe we need more realistic random graphs for LM...