while working with ALT, we came across minor differences that sometimes occur while routing. It seems ALT does not guarantee finding the optimal route. It seems like the stopping criterion used in bidirectional AStar, which is used for ALT, is not complete. According to Slides from KIT (Slide 34), it is necessary to have additional summands for the start and target node potential. In the current GH implementation, the stopping criterion is the same as in a bidir dijkstra, which does not seem to be sufficient.
To clarify, currently the stopping criterion is:
currFrom.weight + currTo.weight >= bestPath.getWeight()
But we think it should be
currFrom.weight + currTo.weight >= bestPath.getWeight() + weightApprox.approximate(start) - weightApprox.approximate(goal)
Any idea why the current implementation does not respect this? We found that ALT produces different routes for the same start and goal nodes if we use different numbers of landmarks. We think this might be the cause for that problem.