Repository: graphhopper/graphhopper
Pull request #1749 (2019-10-13 21:00:04)

Makes all tests pass for LM
1. Sorry, but this reverts #1376. I just couldn't get it to work. Like others have pointed out, it _may_ be possible, but the numerics involved are totally not clear to me, and in its current state, it's demonstrably wrong.

2. I also add a treatment of the virtual edge at the target node in the LM-approximator[1]. This is different to what was there before. Before, the _current_ node got a special treatment, which is _not_ necessary.

I now also test _unidirectional_ LM, which catches (2). In bidirectional LM, apparently the stopping criterion is loose enough so (2) doesn't show up.

EDIT (added):

3. `LMApproximator` now rounds down, so it always underapproximates.

4. It also tells the bidirectional A* algorithm that it needs a certain slack for the stopping criterion. This is necessary _in addition_ to 3, because `LMApproximator`'s rounding makes it violate the triangle inequality ("consistency"), and this probably can't be fixed locally in the approximator.

5. I shifted the `BalancedWeightApproximator` (which also has a new name) by constants so that both sides are '0' at their destinations. (Recommended by one of the papers, mainly for clarity, doesn't change the algorithm's behavior if the stopping criterion (6.) is also adapted.)

6. I changed the stopping criterion in A* so it works with 5. (found the new formulation in one of the papers, and couldn't find the previous one; possibly the previous one was correct for the previous approximator, but I suspect it was slightly wrong). 

Supercedes #1747.

[1] Goldberg, A.V., Kaplan, H., Werneck, R.F.: Better Landmarks Within Reach. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 38–51. Springer, Heidelberg (2007)

michaz: This still doesn't mean the rounding errors discussed in #1557 are gone. Maybe, maybe not.
karussell: I removed the todonow and replaced CarFlagEncoder with MotorcycleFlagEncoder. Then to remove several log warnings I changed the default maximum weight, but still I get exceptions ala:

```
randomGraph_withQueryGraph seed: 96076558697230
expected: [51, 44, 14, 5, 38, 22, 35, 50]
given:    [51, 44, 14, 8, 17, 32, 35, 50]

java.lang.AssertionError: wrong weight: 51->50, expected: 161.94306753707676, given: 162.04722980980404

	at org.junit.Assert.fail(Assert.java:88)
	at com.graphhopper.routing.weighting.RandomizedRoutingTest.comparePaths(RandomizedRoutingTest.java:322)
	at com.graphhopper.routing.weighting.RandomizedRoutingTest.randomGraph_withQueryGraph(RandomizedRoutingTest.java:280)
	at sun.reflect.GeneratedMethodAccessor2.invoke(Unknown Source)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
	at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
	at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
	at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
	at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:26)
```

Is this expected as those errors are not fixed in this PR (e.g. still rounding errors) or is this unexpected?
michaz: > Then to remove several log warnings I changed the default maximum weight

Careful please, I would say that's not really a minor thing when the PR is about landmark precision.

I still stand by this:

> This still doesn't mean the rounding errors discussed in #1557 are gone. Maybe, maybe not. But they're not what has been failing the randomized tests.

So the answer is apparently 'not'. But perhaps now the change that is discussed in #1557 can be applied? (I wanted to remove only one rounding error source at a time..)

And I put the unidirectional LM test back in, because

> I now also test unidirectional LM, which catches (2). In bidirectional LM, apparently the stopping criterion is loose enough so (2) doesn't show up.
michaz: Maybe we should remove the warning? A too large "max value" is much worse than a too small one, it will just quietly produce wrong routes.
michaz: We should write an `LMApproximatorTest` that verifies that the `LMApproximator` _always underestimates_ the remaining weight, and then go through the code until it does.
karussell: > Careful please, I would say that's not really a minor thing when the PR is about landmark precision

Isn't the underlying problem here more that the max weight guessing procedure is not good enough? I.e. it relies on some distances instead of the weights? We could try to make this better and e.g. go through the graph "from one end to the other". This could be easily done when selecting the first landmark or first 2 landmarks for example.

> encoder = new MotorcycleFlagEncoder(5, 5, 1);
> // todonow: make this work with speed_both_directions=true!
> encoder = new CarFlagEncoder(5, 5, 1);

I replaced this with the MotorcycleFlagEncoder because it uses `speed_both_directions=true` and the todonow could be removed. In one branch I made this easy for CarFlagEncoder too, so we could also wait for that change. But in several tests MotorcycleFlagEncoder is already used in this case already.

> This still doesn't mean the rounding errors discussed in #1557 are gone. Maybe, maybe not. But they're not what has been failing the randomized tests.

Probably I misunderstood this part. The randomized tests are failing occasionally now. How would applying the fix proposed in #1557 help with them, when you say they are not related to the random test failures?

I think it is a good idea to apply the fix and yes, let's do this in a separate PR.
michaz: > The randomized tests are failing occasionally now.

Are they randomly failing on this branch in this state, without `setMaxValue`?

My current hypothesis is that the remaining random failures are due to #1557, and they don't happen with a low `maxValue` and happen more often, or always, with a high `maxValue`.
michaz: > Isn't the underlying problem here more that the max weight guessing procedure is not good enough?

I don't know! Is the rounding supposed to be always correct as long as the `maxValue` is really the maximum value, or is it still heuristic even then?
michaz: Even when I put back ` lm.setMaximumWeight(1000);`, which is currently in there on master (not 10000), I can run it a lot of times without failing.

So what I meant was that the troubles that we were having back then (it's already a long time ago..) with randomly failing tests on master should be fixed with this PR.

michaz: Now the API client live test is failing. ,-)
michaz: So this is the test that tests if `LMApproximator` is actually a valid A*-Approximator.

It systematically overestimates. The better the landmarks, the more.
michaz: Oh. I think the case where it overestimates by a tiny bit is actually the case where it doesn't use landmarks at all, but the beeline fallback approximator.
michaz: Done.
easbar: Very nice! Now that we were on it I added unidir Dijkstra&AStar as well to the randomized test. There seem to be some rare cases with failing AStar/LM still, but the weight difference always seems to be very small, e.g.

```
expected: [19, 16, 35, 38]
given:    [19, 61, 81, 3, 28, 43, 79, 38]
seed: 39316239491387

java.lang.AssertionError: wrong weight: 19->38
expected: 106.36985678961038
given:    106.7326455944056
seed: 39316239491387
```

Looks like there are two paths with very similar weight. Is this expected ? Maybe we can increase the weight tolerance for LM/AStar a bit so we can differentiate between real bugs and such small errors (in case its not possible or not worth the effort to get rid of) ?
easbar: > except for non-Euclidean edges; 

`buildRandomGraph` does this:

```java
  double fwdSpeed = 10 + random.nextDouble() * 120;
  double bwdSpeed = 10 + random.nextDouble() * 120;
```

So the speed  might turn out as 130 even though the motor cycle encoder has max speed 120 (?). Is this what you mean with non-euclidean edges ? It certainly seems to be problematic for AStar/LM.

>  it doesn't use landmarks at all, but uses the beeline fallback approximator,

Did you check / can we be sure the random tests cover cases with the LM *and* the fallback approximator ?
michaz: Thanks!!

> Looks like there are two paths with very similar weight. Is this expected ? Maybe we can increase the weight tolerance for LM/AStar a bit so we can differentiate between real bugs and such small errors (in case its not possible or not worth the effort to get rid of them) ?

If I'm not mistaken, the `BeelineApproximator` _cannot_ be a reliable underapproximator at the moment. It doesn't know how much slack it has to subtract from its approximation to correct for rounding, because that depends on the number of edges of the path it will be compared against (because the link of every edge could be rounded down), and it doesn't know that.

I would say that's a real bug (in our engineering), and we must sort it out.
michaz: Arrgh, those are _really_ good test cases. They keep failing even when I set the beeline approximator to 0 and let the LM approximator round down by more than the number of terms that are rounded. :-)
easbar: I think its most likely because of the distance/speed deviations we **explicitly** add in `GHUtility#randomGraph`, don't you think ? 

michaz: Err, ah, okay, wait.
michaz: Nope, I can edit MotorCycleFlagEncoder and change maxSpeed to 200 and it still fails.
easbar: Ok and did you remove the code that manipulates the distance ?

michaz: > Hmm or maybe not because it only increases distance

Exactly. Strangely, it _does_ make fail1 and fail2 pass, but it _doesn't_ make it pass the LMApproximatorTest when I put it in there. 
easbar: > Strangely, it does make fail1 and fail2 pass,

Be careful here, if you comment out the `nextDouble()` calls the same seed might produce another graph / example

Patch:
diff --git a/core/files/changelog.txt b/core/files/changelog.txt
index a2a446476..50fa9cfb7 100644
--- a/core/files/changelog.txt
+++ b/core/files/changelog.txt
@@ -1,4 +1,5 @@
 1.0
+    revert compression of landmark preparation data, see #1749 and #1376
     removed GenericWeighting and DataFlagEncoder as a normal CarFlagEncoder does the job too
     add required EncodedValues like road_class to EncodingManager if not added from user
     removed PathNative,PathBidirRef,Path4CH,EdgeBasedPathCH and moved path extraction code out of Path class, added PathExtractor,BidirPathExtractor(+subclasses for CH) instead, #1730
diff --git a/core/src/main/java/com/graphhopper/routing/AStarBidirection.java b/core/src/main/java/com/graphhopper/routing/AStarBidirection.java
index 218428309..0d23e4a95 100644
--- a/core/src/main/java/com/graphhopper/routing/AStarBidirection.java
+++ b/core/src/main/java/com/graphhopper/routing/AStarBidirection.java
@@ -19,8 +19,8 @@ package com.graphhopper.routing;
 
 import com.graphhopper.routing.AStar.AStarEntry;
 import com.graphhopper.routing.util.TraversalMode;
+import com.graphhopper.routing.weighting.BalancedWeightApproximator;
 import com.graphhopper.routing.weighting.BeelineWeightApproximator;
-import com.graphhopper.routing.weighting.ConsistentWeightApproximator;
 import com.graphhopper.routing.weighting.WeightApproximator;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.Graph;
@@ -59,7 +59,8 @@ import java.util.PriorityQueue;
  * @author jansoe
  */
 public class AStarBidirection extends AbstractNonCHBidirAlgo implements RecalculationHook {
-    private ConsistentWeightApproximator weightApprox;
+    private BalancedWeightApproximator weightApprox;
+    double stoppingCriterionOffset;
 
     public AStarBidirection(Graph graph, Weighting weighting, TraversalMode tMode) {
         super(graph, weighting, tMode);
@@ -70,11 +71,19 @@ public class AStarBidirection extends AbstractNonCHBidirAlgo implements Recalcul
 
     @Override
     void init(int from, double fromWeight, int to, double toWeight) {
-        weightApprox.setFrom(from);
-        weightApprox.setTo(to);
+        weightApprox.setFromTo(from, to);
+        stoppingCriterionOffset = weightApprox.approximate(to, true) + weightApprox.getSlack();
         super.init(from, fromWeight, to, toWeight);
     }
 
+    @Override
+    protected boolean finished() {
+        if (finishedFrom || finishedTo)
+            return true;
+
+        return currFrom.weight + currTo.weight >= bestWeight + stoppingCriterionOffset;
+    }
+
     @Override
     protected SPTEntry createStartEntry(int node, double weight, boolean reverse) {
         double heapWeight = weight + weightApprox.approximate(node, reverse);
@@ -109,22 +118,14 @@ public class AStarBidirection extends AbstractNonCHBidirAlgo implements Recalcul
         return weightApprox.getApproximation();
     }
 
-    /**
-     * @param approx if true it enables approximate distance calculation from lat,lon values
-     */
     public AStarBidirection setApproximation(WeightApproximator approx) {
-        weightApprox = new ConsistentWeightApproximator(approx);
+        weightApprox = new BalancedWeightApproximator(approx);
         return this;
     }
 
-    void setFromDataStructures(AStarBidirection astar) {
-        super.setFromDataStructures(astar);
-        weightApprox.setFrom(astar.currFrom.adjNode);
-    }
-
-    void setToDataStructures(AStarBidirection astar) {
-        super.setToDataStructures(astar);
-        weightApprox.setTo(astar.currTo.adjNode);
+    @Override
+    void setToDataStructures(AbstractBidirAlgo other) {
+        throw new UnsupportedOperationException();
     }
 
     @Override
@@ -137,7 +138,7 @@ public class AStarBidirection extends AbstractNonCHBidirAlgo implements Recalcul
         return Parameters.Algorithms.ASTAR_BI + "|" + weightApprox;
     }
 
-    public static void updatePriorityQueues(PriorityQueue<SPTEntry> pqOpenSetFrom, PriorityQueue<SPTEntry> pqOpenSetTo, ConsistentWeightApproximator weightApprox, boolean forward, boolean backward) {
+    public static void updatePriorityQueues(PriorityQueue<SPTEntry> pqOpenSetFrom, PriorityQueue<SPTEntry> pqOpenSetTo, BalancedWeightApproximator weightApprox, boolean forward, boolean backward) {
         if (forward) {
             // update PQ due to heuristic change (i.e. weight changed)
             if (!pqOpenSetFrom.isEmpty()) {
diff --git a/core/src/main/java/com/graphhopper/routing/AStarBidirectionCH.java b/core/src/main/java/com/graphhopper/routing/AStarBidirectionCH.java
index ecf6f01b4..effc78f97 100644
--- a/core/src/main/java/com/graphhopper/routing/AStarBidirectionCH.java
+++ b/core/src/main/java/com/graphhopper/routing/AStarBidirectionCH.java
@@ -18,8 +18,8 @@
 package com.graphhopper.routing;
 
 import com.graphhopper.routing.util.TraversalMode;
+import com.graphhopper.routing.weighting.BalancedWeightApproximator;
 import com.graphhopper.routing.weighting.BeelineWeightApproximator;
-import com.graphhopper.routing.weighting.ConsistentWeightApproximator;
 import com.graphhopper.routing.weighting.WeightApproximator;
 import com.graphhopper.storage.RoutingCHEdgeIteratorState;
 import com.graphhopper.storage.RoutingCHGraph;
@@ -31,7 +31,7 @@ import com.graphhopper.util.Helper;
  * @see AStarBidirection
  */
 public class AStarBidirectionCH extends AbstractBidirCHAlgo implements RecalculationHook {
-    private ConsistentWeightApproximator weightApprox;
+    private BalancedWeightApproximator weightApprox;
 
     public AStarBidirectionCH(RoutingCHGraph graph) {
         super(graph, TraversalMode.NODE_BASED);
@@ -42,8 +42,7 @@ public class AStarBidirectionCH extends AbstractBidirCHAlgo implements Recalcula
 
     @Override
     void init(int from, double fromWeight, int to, double toWeight) {
-        weightApprox.setFrom(from);
-        weightApprox.setTo(to);
+        weightApprox.setFromTo(from, to);
         super.init(from, fromWeight, to, toWeight);
     }
 
@@ -85,20 +84,10 @@ public class AStarBidirectionCH extends AbstractBidirCHAlgo implements Recalcula
      * @param approx if true it enables approximate distance calculation from lat,lon values
      */
     public AStarBidirectionCH setApproximation(WeightApproximator approx) {
-        weightApprox = new ConsistentWeightApproximator(approx);
+        weightApprox = new BalancedWeightApproximator(approx);
         return this;
     }
 
-    void setFromDataStructures(AStarBidirectionCH astar) {
-        super.setFromDataStructures(astar);
-        weightApprox.setFrom(astar.currFrom.adjNode);
-    }
-
-    void setToDataStructures(AStarBidirectionCH astar) {
-        super.setToDataStructures(astar);
-        weightApprox.setTo(astar.currTo.adjNode);
-    }
-
     @Override
     public void afterHeuristicChange(boolean forward, boolean backward) {
         AStarBidirection.updatePriorityQueues(pqOpenSetFrom, pqOpenSetTo, weightApprox, forward, backward);
diff --git a/core/src/main/java/com/graphhopper/routing/AStarBidirectionEdgeCHNoSOD.java b/core/src/main/java/com/graphhopper/routing/AStarBidirectionEdgeCHNoSOD.java
index 384778cc5..8156c5cbf 100644
--- a/core/src/main/java/com/graphhopper/routing/AStarBidirectionEdgeCHNoSOD.java
+++ b/core/src/main/java/com/graphhopper/routing/AStarBidirectionEdgeCHNoSOD.java
@@ -18,8 +18,8 @@
 package com.graphhopper.routing;
 
 import com.graphhopper.routing.ch.AStarCHEntry;
+import com.graphhopper.routing.weighting.BalancedWeightApproximator;
 import com.graphhopper.routing.weighting.BeelineWeightApproximator;
-import com.graphhopper.routing.weighting.ConsistentWeightApproximator;
 import com.graphhopper.routing.weighting.WeightApproximator;
 import com.graphhopper.storage.RoutingCHEdgeIteratorState;
 import com.graphhopper.storage.RoutingCHGraph;
@@ -31,7 +31,7 @@ import com.graphhopper.util.Helper;
  */
 public class AStarBidirectionEdgeCHNoSOD extends AbstractBidirectionEdgeCHNoSOD {
     private final boolean useHeuristicForNodeOrder = false;
-    private ConsistentWeightApproximator weightApprox;
+    private BalancedWeightApproximator weightApprox;
 
     public AStarBidirectionEdgeCHNoSOD(RoutingCHGraph graph) {
         super(graph);
@@ -40,8 +40,7 @@ public class AStarBidirectionEdgeCHNoSOD extends AbstractBidirectionEdgeCHNoSOD
 
     @Override
     public void init(int from, double fromWeight, int to, double toWeight) {
-        weightApprox.setFrom(from);
-        weightApprox.setTo(to);
+        weightApprox.setFromTo(from, to);
         super.init(from, fromWeight, to, toWeight);
     }
 
@@ -84,7 +83,7 @@ public class AStarBidirectionEdgeCHNoSOD extends AbstractBidirectionEdgeCHNoSOD
     }
 
     public AStarBidirectionEdgeCHNoSOD setApproximation(WeightApproximator weightApproximator) {
-        weightApprox = new ConsistentWeightApproximator(weightApproximator);
+        weightApprox = new BalancedWeightApproximator(weightApproximator);
         return this;
     }
 
diff --git a/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java b/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
index 84af50442..fd3e23e21 100644
--- a/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
+++ b/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
@@ -246,17 +246,6 @@ public abstract class AbstractBidirAlgo implements BidirRoutingAlgorithm {
         return visitedCountFrom + visitedCountTo;
     }
 
-    void setFromDataStructures(AbstractBidirAlgo other) {
-        from = other.from;
-        fromOutEdge = other.fromOutEdge;
-        pqOpenSetFrom = other.pqOpenSetFrom;
-        bestWeightMapFrom = other.bestWeightMapFrom;
-        finishedFrom = other.finishedFrom;
-        currFrom = other.currFrom;
-        visitedCountFrom = other.visitedCountFrom;
-        // outEdgeExplorer
-    }
-
     void setToDataStructures(AbstractBidirAlgo other) {
         to = other.to;
         toInEdge = other.toInEdge;
diff --git a/core/src/main/java/com/graphhopper/routing/AlternativeRoute.java b/core/src/main/java/com/graphhopper/routing/AlternativeRoute.java
index a7b238bdd..e52eff3d6 100644
--- a/core/src/main/java/com/graphhopper/routing/AlternativeRoute.java
+++ b/core/src/main/java/com/graphhopper/routing/AlternativeRoute.java
@@ -277,7 +277,7 @@ public class AlternativeRoute implements RoutingAlgorithm {
                 return true;
 
             // increase overlap of both searches:
-            return currFrom.weight + currTo.weight > explorationFactor * bestWeight;
+            return currFrom.weight + currTo.weight > explorationFactor * (bestWeight + stoppingCriterionOffset);
             // This is more precise but takes roughly 20% longer: return currFrom.weight > bestWeight && currTo.weight > bestWeight;
             // For bidir A* and AStarEdge.getWeightOfVisitedPath see comment in AStarBidirection.finished
         }
diff --git a/core/src/main/java/com/graphhopper/routing/lm/LMApproximator.java b/core/src/main/java/com/graphhopper/routing/lm/LMApproximator.java
index eb7bf98dc..b6c3a8914 100644
--- a/core/src/main/java/com/graphhopper/routing/lm/LMApproximator.java
+++ b/core/src/main/java/com/graphhopper/routing/lm/LMApproximator.java
@@ -17,12 +17,12 @@
  */
 package com.graphhopper.routing.lm;
 
-import com.graphhopper.coll.GHIntObjectHashMap;
-import com.graphhopper.routing.querygraph.QueryGraph;
+import com.graphhopper.routing.Dijkstra;
+import com.graphhopper.routing.util.TraversalMode;
 import com.graphhopper.routing.weighting.BeelineWeightApproximator;
 import com.graphhopper.routing.weighting.WeightApproximator;
+import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.Graph;
-import com.graphhopper.util.EdgeIteratorState;
 
 import java.util.Arrays;
 
@@ -32,35 +32,24 @@ import java.util.Arrays;
  * @author Peter Karich
  */
 public class LMApproximator implements WeightApproximator {
-    private static class VirtEntry {
-        private int towerNode;
-        private int weight;
-
-        @Override
-        public String toString() {
-            return towerNode + ", " + weight;
-        }
-    }
 
     private final LandmarkStorage lms;
-    // store node ids
-    private int[] activeLandmarks;
-    // store weights as int
-    private int[] activeFromIntWeights;
-    private int[] activeToIntWeights;
+    private final Weighting weighting;
+    private int[] activeLandmarkIndices;
+    private int[] weightsFromActiveLandmarksToT;
+    private int[] weightsFromTToActiveLandmarks;
     private double epsilon = 1;
-    private int toTowerNode = -1;
-    // do activate landmark recalculation
-    private boolean doALMRecalc = true;
+    private int towerNodeNextToT = -1;
+    private double weightFromTToTowerNode;
+    private boolean recalculateActiveLandmarks = true;
     private final double factor;
     private final boolean reverse;
     private final int maxBaseNodes;
     private final Graph graph;
     private final WeightApproximator fallBackApproximation;
     private boolean fallback = false;
-    private final GHIntObjectHashMap<VirtEntry> virtNodeMap;
 
-    public LMApproximator(Graph graph, int maxBaseNodes, LandmarkStorage lms, int activeCount,
+    public LMApproximator(Graph graph, Weighting weighting, int maxBaseNodes, LandmarkStorage lms, int activeCount,
                           double factor, boolean reverse) {
         this.reverse = reverse;
         this.lms = lms;
@@ -69,41 +58,15 @@ public class LMApproximator implements WeightApproximator {
             throw new IllegalArgumentException("Active landmarks " + activeCount
                     + " should be lower or equals to landmark count " + lms.getLandmarkCount());
 
-        activeLandmarks = new int[activeCount];
-        Arrays.fill(activeLandmarks, -1);
-        activeFromIntWeights = new int[activeCount];
-        activeToIntWeights = new int[activeCount];
+        activeLandmarkIndices = new int[activeCount];
+        Arrays.fill(activeLandmarkIndices, -1);
+        weightsFromActiveLandmarksToT = new int[activeCount];
+        weightsFromTToActiveLandmarks = new int[activeCount];
 
         this.graph = graph;
-        this.fallBackApproximation = new BeelineWeightApproximator(graph.getNodeAccess(), lms.getWeighting());
+        this.weighting = weighting;
+        this.fallBackApproximation = new BeelineWeightApproximator(graph.getNodeAccess(), weighting);
         this.maxBaseNodes = maxBaseNodes;
-        int idxVirtNode = maxBaseNodes;
-        virtNodeMap = new GHIntObjectHashMap<>(graph.getNodes() - idxVirtNode, 0.5f);
-        // virtual nodes handling: calculate the minimum weight for the virtual nodes, i.e. pick the correct neighbouring node
-        if (graph instanceof QueryGraph) {
-            QueryGraph qGraph = (QueryGraph) graph;
-            // there are at least two virtual nodes (start & destination)
-            for (; idxVirtNode < qGraph.getNodes(); idxVirtNode++) {
-                // we need the real underlying edge as neighboring nodes could be virtual too
-                EdgeIteratorState edge = qGraph.getOriginalEdgeFromVirtNode(idxVirtNode);
-
-                int weight = lms.calcWeight(edge, reverse);
-                int reverseWeight = lms.calcWeight(edge, !reverse);
-                VirtEntry virtEntry = new VirtEntry();
-                if (weight < Integer.MAX_VALUE && (reverseWeight >= Integer.MAX_VALUE || weight < reverseWeight)) {
-                    virtEntry.weight = weight;
-                    virtEntry.towerNode = reverse ? edge.getBaseNode() : edge.getAdjNode();
-                } else {
-                    virtEntry.weight = reverseWeight;
-                    if (reverseWeight >= Integer.MAX_VALUE)
-                        throw new IllegalStateException("At least one direction of edge (" + edge + ") should be accessible but wasn't!");
-
-                    virtEntry.towerNode = reverse ? edge.getAdjNode() : edge.getBaseNode();
-                }
-
-                virtNodeMap.put(idxVirtNode, virtEntry);
-            }
-        }
     }
 
     /**
@@ -115,101 +78,128 @@ public class LMApproximator implements WeightApproximator {
     }
 
     @Override
-    public double approximate(final int queryNode) {
-        if (!doALMRecalc && fallback || lms.isEmpty())
-            return fallBackApproximation.approximate(queryNode);
+    public double approximate(final int v) {
+        if (!recalculateActiveLandmarks && fallback || lms.isEmpty())
+            return fallBackApproximation.approximate(v);
 
-        int towerNode = queryNode;
-        int virtEdgeWeightInt = 0;
-        if (queryNode >= maxBaseNodes) {
+        if (v >= maxBaseNodes) {
             // handle virtual node
-            VirtEntry virtEntry = virtNodeMap.get(queryNode);
-            towerNode = virtEntry.towerNode;
-            virtEdgeWeightInt = virtEntry.weight;
+            return 0;
         }
 
-        if (towerNode == toTowerNode)
+        if (v == towerNodeNextToT)
             return 0;
 
         // select better active landmarks, LATER: use 'success' statistics about last active landmark
         // we have to update the priority queues and the maps if done in the middle of the search http://cstheory.stackexchange.com/q/36355/13229
-        if (doALMRecalc) {
-            doALMRecalc = false;
-            boolean res = lms.initActiveLandmarks(towerNode, toTowerNode, activeLandmarks, activeFromIntWeights, activeToIntWeights, reverse);
-            if (!res) {
+        if (recalculateActiveLandmarks) {
+            recalculateActiveLandmarks = false;
+            if (lms.chooseActiveLandmarks(v, towerNodeNextToT, activeLandmarkIndices, reverse)) {
+                for (int i = 0; i < activeLandmarkIndices.length; i++) {
+                    weightsFromActiveLandmarksToT[i] = lms.getFromWeight(activeLandmarkIndices[i], towerNodeNextToT);
+                    weightsFromTToActiveLandmarks[i] = lms.getToWeight(activeLandmarkIndices[i], towerNodeNextToT);
+                }
+            } else {
                 // note: fallback==true means forever true!
                 fallback = true;
-                return fallBackApproximation.approximate(queryNode);
+                return fallBackApproximation.approximate(v);
             }
         }
+        return Math.max(0.0, (getRemainingWeightUnderestimationUpToTowerNode(v) - weightFromTToTowerNode) * epsilon);
+    }
+
+    private double getRemainingWeightUnderestimationUpToTowerNode(int v) {
+        int maxWeightInt = 0;
+        for (int i = 0; i < activeLandmarkIndices.length; i++) {
+            int resultInt = approximateForLandmark(i, v);
+            maxWeightInt = Math.max(maxWeightInt, resultInt);
+        }
+        // Round down, we need to be an underestimator.
+        return (maxWeightInt - 1) * factor;
+    }
 
-        int maxWeightInt = getMaxWeight(towerNode, virtEdgeWeightInt, activeLandmarks, activeFromIntWeights, activeToIntWeights);
-        if (maxWeightInt < 0) {
-            // allow negative weight for now until we have more precise approximation (including query graph)
-            return 0;
-//                throw new IllegalStateException("Maximum approximation weight cannot be negative. "
-//                        + "max weight:" + maxWeightInt
-//                        + "queryNode:" + queryNode + ", node:" + node + ", reverse:" + reverse);
+    private int approximateForLandmark(int i, int v) {
+        // ---> means shortest path, d means length of shortest path
+        // but remember that d(v,t) != d(t,v)
+        //
+        // Suppose we are at v, want to go to t, and are looking at a landmark LM,
+        // preferably behind t.
+        //
+        //   ---> t -->
+        // v ---------> LM
+        //
+        // We know distances from everywhere to LM. From the triangle inequality for shortest-path distances we get:
+        //  I)  d(v,t) + d(t,LM) >= d(v,LM), so d(v,t) >= d(v,LM) - d(t,LM)
+        //
+        // Now suppose LM is behind us:
+        //
+        //    ---> v -->
+        // LM ---------> t
+        //
+        // We also know distances from LM to everywhere, so we get:
+        //  II) d(LM,v) + d(v,t) >= d(LM,t), so d(v,t) >= d(LM,t) - d(LM,v)
+        //
+        // Both equations hold in the general case, so we just pick the tighter approximation.
+        // (The other one will probably be negative.)
+        //
+        // Note that when routing backwards we want to approximate d(t,v), not d(v,t).
+        // When we flip all the arrows in the two figures, we get
+        //  III)  d(t,v)  + d(LM,t) >= d(LM,v), so d(t,v) >= d(LM,v) - d(LM,t)
+        //   IV)  d(v,LM) + d(t,v)  >= d(t,LM), so d(t,v) >= d(t,LM) - d(v,LM)
+        //
+        // ...and we can get the right-hand sides of III) and IV) by multiplying those of II) and I) by -1.
+
+        int rhs1Int = weightsFromActiveLandmarksToT[i] - lms.getFromWeight(activeLandmarkIndices[i], v);
+        int rhs2Int = lms.getToWeight(activeLandmarkIndices[i], v) - weightsFromTToActiveLandmarks[i];
+
+        int resultInt;
+        if (reverse) {
+            resultInt = Math.max(-rhs2Int, -rhs1Int);
+        } else {
+            resultInt = Math.max(rhs1Int, rhs2Int);
         }
+        return resultInt;
+    }
 
-        return maxWeightInt * factor * epsilon;
+    @Override
+    public void setTo(int t) {
+        this.fallBackApproximation.setTo(t);
+        findClosestRealNode(t);
     }
 
-    int getMaxWeight(int node, int virtEdgeWeightInt, int[] activeLandmarks, int[] activeFromIntWeights, int[] activeToIntWeights) {
-        int maxWeightInt = -1;
-        for (int activeLMIdx = 0; activeLMIdx < activeLandmarks.length; activeLMIdx++) {
-            int landmarkIndex = activeLandmarks[activeLMIdx];
-
-            // 1. assume route from a to b: a--->v--->b and a landmark LM.
-            //    From this we get two inequality formulas where v is the start (or current node) and b is the 'to' node:
-            //    LMv + vb >= LMb therefor vb >= LMb - LMv => 'getFromWeight'
-            //    vb + bLM >= vLM therefor vb >= vLM - bLM => 'getToWeight'
-            // 2. for the case a->v the sign is reverse as we need to know the vector av not va => if(reverse) "-weight"
-            // 3. as weight is the full edge weight for now (and not the precise weight to the virt node) we can only add it to the subtrahend
-            //    to avoid overestimating (keep the result strictly lower)
-            int fromWeightInt = activeFromIntWeights[activeLMIdx] - (lms.getFromWeight(landmarkIndex, node) + virtEdgeWeightInt);
-            int toWeightInt = lms.getToWeight(landmarkIndex, node) - activeToIntWeights[activeLMIdx];
-            if (reverse) {
-                fromWeightInt = -fromWeightInt;
-                // we need virtEntryWeight for the minuend
-                toWeightInt = -toWeightInt - virtEdgeWeightInt;
-            } else {
-                toWeightInt -= virtEdgeWeightInt;
+    private void findClosestRealNode(int t) {
+        Dijkstra dijkstra = new Dijkstra(graph, weighting, TraversalMode.NODE_BASED) {
+            @Override
+            protected boolean finished() {
+                towerNodeNextToT = currEdge.adjNode;
+                weightFromTToTowerNode = currEdge.weight;
+                return currEdge.adjNode < maxBaseNodes;
             }
 
-            int tmpMaxWeightInt = Math.max(fromWeightInt, toWeightInt);
-//                if (tmpMaxWeightInt < 0)
-//                {
-//                    int lm = lms.getLandmarks()[landmarkIndex];
-//                    throw new IllegalStateException("At least one weight should be positive but wasn't. "
-//                            + "activeFromWeight:" + activeFromIntWeights[activeLMIdx] + ", lms.getFromWeight:" + lms.getFromWeight(landmarkIndex, node)
-//                            + "lms.getToWeight:" + lms.getToWeight(landmarkIndex, node) + ", activeToWeight:" + activeToIntWeights[activeLMIdx]
-//                            + ", virtEdgeWeight:" + virtEdgeWeightInt
-//                            + ", lm:" + lm + " (" + getCoord(lm) + ")"
-//                            + ", queryNode:" + queryNode + " , node:" + node + " (" + getCoord(node) + "), reverse:" + reverse);
-//                }
-            if (tmpMaxWeightInt > maxWeightInt)
-                maxWeightInt = tmpMaxWeightInt;
-        }
-        return maxWeightInt;
+            // We only expect a very short search
+            @Override
+            protected void initCollections(int size) {
+                super.initCollections(2);
+            }
+        };
+        dijkstra.calcPath(t, -1);
     }
 
     @Override
-    public void setTo(int to) {
-        this.fallBackApproximation.setTo(to);
-        this.toTowerNode = to >= maxBaseNodes ? virtNodeMap.get(to).towerNode : to;
+    public WeightApproximator reverse() {
+        return new LMApproximator(graph, weighting, maxBaseNodes, lms, activeLandmarkIndices.length, factor, !reverse);
     }
 
     @Override
-    public WeightApproximator reverse() {
-        return new LMApproximator(graph, maxBaseNodes, lms, activeLandmarks.length, factor, !reverse);
+    public double getSlack() {
+        return lms.getFactor();
     }
 
     /**
      * This method forces a lazy recalculation of the active landmark set e.g. necessary after the 'to' node changed.
      */
     public void triggerActiveLandmarkRecalculation() {
-        doALMRecalc = true;
+        recalculateActiveLandmarks = true;
     }
 
     @Override
diff --git a/core/src/main/java/com/graphhopper/routing/lm/LandmarkStorage.java b/core/src/main/java/com/graphhopper/routing/lm/LandmarkStorage.java
index 8a1f6843f..31cb4e3de 100644
--- a/core/src/main/java/com/graphhopper/routing/lm/LandmarkStorage.java
+++ b/core/src/main/java/com/graphhopper/routing/lm/LandmarkStorage.java
@@ -54,6 +54,12 @@ import java.util.concurrent.atomic.AtomicInteger;
  * @author Peter Karich
  */
 public class LandmarkStorage implements Storable<LandmarkStorage> {
+
+    // Short.MAX_VALUE = 2^15-1 but we have unsigned short so we need 2^16-1
+    private static final int SHORT_INFINITY = Short.MAX_VALUE * 2 + 1;
+    // We have large values that do not fit into a short, use a specific maximum value
+    private static final int SHORT_MAX = SHORT_INFINITY - 1;
+
     private static final Logger LOGGER = LoggerFactory.getLogger(LandmarkStorage.class);
     // This value is used to identify nodes where no subnetwork is associated
     private static final int UNSET_SUBNETWORK = -1;
@@ -62,8 +68,10 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
     // one node has an associated landmark information ('one landmark row'): the forward and backward weight
     private long LM_ROW_LENGTH;
     private int landmarks;
+    private final int FROM_OFFSET;
+    private final int TO_OFFSET;
     private final DataAccess landmarkWeightDA;
-    /* every subnetwork has its own landmark mapping but the count of landmarks is always the same */
+    // every subnetwork has its own landmark mapping but the count of landmarks is always the same
     private final List<int[]> landmarkIDs;
     private double factor = -1;
     private final static double DOUBLE_MLTPL = 1e6;
@@ -78,6 +86,10 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
     private List<LandmarkSuggestion> landmarkSuggestions = Collections.emptyList();
     private SpatialRuleLookup ruleLookup;
     private boolean logDetails = false;
+    /**
+     * 'to' and 'from' fit into 32 bit => 16 bit for each of them => 65536
+     */
+    static final long PRECISION = 1 << 16;
 
     public LandmarkStorage(GraphHopperStorage graph, Directory dir, final Weighting weighting, int landmarks) {
         this.graph = graph;
@@ -112,20 +124,19 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
         this.landmarks = landmarks;
         // one short per landmark and two directions => 2*2 byte
         this.LM_ROW_LENGTH = landmarks * 4;
+        this.FROM_OFFSET = 0;
+        this.TO_OFFSET = 2;
         this.landmarkIDs = new ArrayList<>();
         this.subnetworkStorage = new SubnetworkStorage(dir, "landmarks_" + name);
     }
 
-    public int getVersion() {
-        return 1;
-    }
-
     /**
      * Specify the maximum possible value for your used area. With this maximum weight value you can influence the storage
      * precision for your weights that help A* finding its way to the goal. The same value is used for all subnetworks.
      * Note, if you pick this value too big then too similar weights are stored
-     * (some bits of the storage capability will be left unused) which could lead to suboptimal routes.
-     * If too low then far away values will have the same maximum value associated ("maxed out") leading to bad performance.
+     * (some bits of the storage capability will be left unused).
+     * If too low then far away values will have the same maximum value associated ("maxed out").
+     * Both will lead to bad performance.
      *
      * @param maxWeight use a negative value to automatically determine this value.
      */
@@ -172,10 +183,6 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
         return minimumNodes;
     }
 
-    SubnetworkStorage getSubnetworkStorage() {
-        return subnetworkStorage;
-    }
-
     /**
      * This weighting is used for the selection heuristic and is per default not the weighting specified in the contructor.
      * The special weighting leads to a much better distribution of the landmarks and results in better response times.
@@ -211,8 +218,8 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
         this.landmarkWeightDA.create(2000);
         this.landmarkWeightDA.ensureCapacity(maxBytes);
 
-        for (long pointer = 0; pointer < maxBytes; pointer += 4) {
-            landmarkWeightDA.setInt(pointer, (DELTA_INF << FROM_WEIGHT_BITS) | FROM_WEIGHT_INF);
+        for (long pointer = 0; pointer < maxBytes; pointer += 2) {
+            landmarkWeightDA.setShort(pointer, (short) SHORT_INFINITY);
         }
 
         String additionalInfo = "";
@@ -250,8 +257,7 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
         if (ruleLookup != null && ruleLookup.size() > 0) {
             StopWatch sw = new StopWatch().start();
             blockedEdges = findBorderEdgeIds(ruleLookup);
-            tarjanFilter = new BlockedEdgesFilter(encoder.getAccessEnc(), false, true, blockedEdges);
-
+            tarjanFilter = new BlockedEdgesFilter(encoder.getAccessEnc(), true, false, blockedEdges);
             if (logDetails)
                 LOGGER.info("Made " + blockedEdges.size() + " edges inaccessible. Calculated country cut in " + sw.stop().getSeconds() + "s, " + Helper.getMemInfo());
         }
@@ -306,14 +312,12 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
             }
         }
 
-        // make backward incompatible to force rebuilt (pre 0.11 releases had nodes count at 0)
-        landmarkWeightDA.setHeader(0 * 4, getVersion());
+        landmarkWeightDA.setHeader(0 * 4, graph.getNodes());
         landmarkWeightDA.setHeader(1 * 4, landmarks);
         landmarkWeightDA.setHeader(2 * 4, subnetworkCount);
         if (factor * DOUBLE_MLTPL > Integer.MAX_VALUE)
             throw new UnsupportedOperationException("landmark weight factor cannot be bigger than Integer.MAX_VALUE " + factor * DOUBLE_MLTPL);
         landmarkWeightDA.setHeader(3 * 4, (int) Math.round(factor * DOUBLE_MLTPL));
-        landmarkWeightDA.setHeader(4 * 4, graph.getNodes());
 
         // serialize fast byte[] into DataAccess
         subnetworkStorage.create(graph.getNodes());
@@ -407,9 +411,9 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
             int lmNodeId = tmpLandmarkNodeIds[lmIdx];
             LandmarkExplorer explorer = new LandmarkExplorer(graph, this, weighting, traversalMode, true);
             explorer.setStartNode(lmNodeId);
-            explorer.setFilter(blockedEdges, true, false);
+            explorer.setFilter(blockedEdges, false, true);
             explorer.runAlgo();
-            explorer.initLandmarkWeights(lmIdx, lmNodeId, LM_ROW_LENGTH);
+            explorer.initLandmarkWeights(lmIdx, lmNodeId, LM_ROW_LENGTH, FROM_OFFSET);
 
             // set subnetwork id to all explored nodes, but do this only for the first landmark
             if (lmIdx == 0) {
@@ -419,9 +423,9 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
 
             explorer = new LandmarkExplorer(graph, this, weighting, traversalMode, false);
             explorer.setStartNode(lmNodeId);
-            explorer.setFilter(blockedEdges, false, true);
+            explorer.setFilter(blockedEdges, true, false);
             explorer.runAlgo();
-            explorer.initLandmarkWeights(lmIdx, lmNodeId, LM_ROW_LENGTH);
+            explorer.initLandmarkWeights(lmIdx, lmNodeId, LM_ROW_LENGTH, TO_OFFSET);
 
             if (lmIdx == 0) {
                 if (explorer.setSubnetworks(subnetworks, subnetworkId))
@@ -479,14 +483,16 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
      * a node ID but the internal index of the landmark array.
      */
     int getFromWeight(int landmarkIndex, int node) {
-        //only the right bits of this integer store the backward value
-        int res = landmarkWeightDA.getInt((long) node * LM_ROW_LENGTH + landmarkIndex * 4) & FROM_WEIGHT_INF;
-
-        if (res == FROM_WEIGHT_INF)
-            return Integer.MAX_VALUE;
+        int res = (int) landmarkWeightDA.getShort((long) node * LM_ROW_LENGTH + landmarkIndex * 4 + FROM_OFFSET)
+                & 0x0000FFFF;
+        if (res == SHORT_INFINITY)
+            // TODO can happen if endstanding oneway
+            // we should set a 'from' value to SHORT_MAX if the 'to' value was already set to find real bugs
+            // and what to return? Integer.MAX_VALUE i.e. convert to Double.pos_infinity upstream?
+            return SHORT_MAX;
         // throw new IllegalStateException("Do not call getFromWeight for wrong landmark[" + landmarkIndex + "]=" + landmarkIDs[landmarkIndex] + " and node " + node);
+        // TODO if(res == MAX) fallback to beeline approximation!?
 
-        assert res >= 0 : "Negative backward weight " + res + ", landmark index:" + landmarkIndex + ", node:" + node;
         return res;
     }
 
@@ -494,92 +500,33 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
      * @return the weight from the specified node to the landmark (specified *as index*)
      */
     int getToWeight(int landmarkIndex, int node) {
-        int res = landmarkWeightDA.getInt((long) node * LM_ROW_LENGTH + landmarkIndex * 4);
-
-        //the left bits of "res" store the difference between forward and backward value
-        int delta = res >> FROM_WEIGHT_BITS;
-
-        if (delta == DELTA_INF)
-            return Integer.MAX_VALUE;
-        // throw new IllegalStateException("Do not call getToWeight for wrong landmark[" + landmarkIndex + "]=" + landmarkIDs[landmarkIndex] + " and node " + node);
-
-        // If delta is 'maxed out' (minned out, really), we can only return 0, since we can't give a better
-        // under-approximation of the weight, since it can be arbitrarily smaller than 'from'.
-        if (delta == DELTA_MIN)
-            return 0;
-
-        //the right bits of "res" store the backward value
-        int from = res & FROM_WEIGHT_INF;
-
-        if (from == FROM_WEIGHT_INF) {
-            from = DELTA_INF + 1;
-        }
+        int res = (int) landmarkWeightDA.getShort((long) node * LM_ROW_LENGTH + landmarkIndex * 4 + TO_OFFSET)
+                & 0x0000FFFF;
+        if (res == SHORT_INFINITY)
+            return SHORT_MAX;
 
-        //to get the forward value you have to add the backward to the delta value
-        res = from + delta;
-
-        assert res >= 0 : "Negative forward weight " + res + ", landmark index:" + landmarkIndex + ", node:" + node;
         return res;
     }
 
-    // 'to' and 'from' fit into 32 bit => 16 bit for each of them => 65536
-    static final long PRECISION = 1 << 16;
-    /* This value sets the amount of bits used to store the backward weight.
-    The rest of overall 32 bits stores the difference between forward and backward weight*/
-    private static final int FROM_WEIGHT_BITS = 18;
-    // The backward weight is unsigned --> 2^x - 1
-    private static final int FROM_WEIGHT_INF = (int) Math.pow(2, FROM_WEIGHT_BITS) - 1;
-    // This value will be used if the backward weight is too large
-    private static final int FROM_WEIGHT_MAX = FROM_WEIGHT_INF - 1;
-    /* The difference between forward and backward weight is signed
-    --> 2^(31-x) - 1 instead of 2^(32-x) - 1*/
-    private static final int DELTA_INF = (int) Math.pow(2, 31 - FROM_WEIGHT_BITS) - 1;
-    // This value will be used if the difference between these weights is too large and forward > backward
-    private static final int DELTA_MAX = DELTA_INF - 1;
-    // This value will be used if the difference between these weights is too large and forward < backward
-    private static final int DELTA_MIN = -DELTA_INF - 1;
-
     /**
-     * @return false if the value capacity was reached and instead of the real value the MAX was stored.
+     * @return false if the value capacity was reached and instead of the real value the SHORT_MAX was stored.
      */
-    final boolean setWeight(int lmIdx, int nodeId, long rowSize, double value, boolean from) {
+    final boolean setWeight(long pointer, double value) {
         double tmpVal = value / factor;
         if (tmpVal > Integer.MAX_VALUE)
-            throw new UnsupportedOperationException("Cannot store infinity explicitly, landmark: " + lmIdx + ", node: " + nodeId + ", value: " + value);
+            throw new UnsupportedOperationException("Cannot store infinity explicitely, pointer=" + pointer + ", value: " + value);
 
-        if (from) {
-            if (tmpVal >= FROM_WEIGHT_MAX) {
-                landmarkWeightDA.setInt(nodeId * rowSize + lmIdx * 4, (DELTA_INF << FROM_WEIGHT_BITS) | FROM_WEIGHT_MAX);
-                return false;
-            } else {
-                landmarkWeightDA.setInt(nodeId * rowSize + lmIdx * 4, (DELTA_INF << FROM_WEIGHT_BITS) | (int) tmpVal);
-                return true;
-            }
+        if (tmpVal >= SHORT_MAX) {
+            landmarkWeightDA.setShort(pointer, (short) SHORT_MAX);
+            return false;
         } else {
-            int fromWeight = getFromWeight(lmIdx, nodeId);
-            int delta;
-            if (fromWeight == Integer.MAX_VALUE) {
-                fromWeight = FROM_WEIGHT_INF;
-                delta = (int) tmpVal - DELTA_INF + 1;
-            } else {
-                delta = (int) tmpVal - fromWeight;
-            }
-
-            if (delta >= DELTA_MAX) {
-                landmarkWeightDA.setInt(nodeId * rowSize + lmIdx * 4, (DELTA_MAX << FROM_WEIGHT_BITS) | fromWeight);
-                return false;
-            } else if (delta <= DELTA_MIN) {
-                landmarkWeightDA.setInt(nodeId * rowSize + lmIdx * 4, (DELTA_MIN << FROM_WEIGHT_BITS) | fromWeight);
-                return false;
-            } else {
-                landmarkWeightDA.setInt(nodeId * rowSize + lmIdx * 4, (delta << FROM_WEIGHT_BITS) | fromWeight);
-                return true;
-            }
+            landmarkWeightDA.setShort(pointer, (short) tmpVal);
+            return true;
         }
     }
 
     boolean isInfinity(long pointer) {
-        return (landmarkWeightDA.getInt(pointer) & FROM_WEIGHT_INF) == FROM_WEIGHT_INF;
+        return ((int) landmarkWeightDA.getShort(pointer) & 0x0000FFFF) == SHORT_INFINITY;
     }
 
     int calcWeight(EdgeIteratorState edge, boolean reverse) {
@@ -587,8 +534,7 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
     }
 
     // From all available landmarks pick just a few active ones
-    boolean initActiveLandmarks(int fromNode, int toNode, int[] activeLandmarkIndices,
-                                int[] activeFroms, int[] activeTos, boolean reverse) {
+    boolean chooseActiveLandmarks(int fromNode, int toNode, int[] activeLandmarkIndices, boolean reverse) {
         if (fromNode < 0 || toNode < 0)
             throw new IllegalStateException("from " + fromNode + " and to "
                     + toNode + " nodes have to be 0 or positive to init landmarks");
@@ -638,12 +584,6 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
             }
         }
 
-        // store weight values of active landmarks in 'cache' arrays
-        for (int i = 0; i < activeLandmarkIndices.length; i++) {
-            int lmIndex = activeLandmarkIndices[i];
-            activeFroms[i] = getFromWeight(lmIndex, toNode);
-            activeTos[i] = getToWeight(lmIndex, toNode);
-        }
         return true;
     }
 
@@ -710,13 +650,9 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
             if (!subnetworkStorage.loadExisting())
                 throw new IllegalStateException("landmark weights loaded but not the subnetworks!?");
 
-            int version = landmarkWeightDA.getHeader(0 * 4);
-            if (version != getVersion())
-                throw new IllegalArgumentException("Cannot load landmark data due to incompatible version. Storage used version: " + version + ", expected: " + getVersion());
-            int nodes = landmarkWeightDA.getHeader(4 * 4);
+            int nodes = landmarkWeightDA.getHeader(0 * 4);
             if (nodes != graph.getNodes())
                 throw new IllegalArgumentException("Cannot load landmark data as written for different graph storage with " + nodes + " nodes, not " + graph.getNodes());
-
             landmarks = landmarkWeightDA.getHeader(1 * 4);
             int subnetworks = landmarkWeightDA.getHeader(2 * 4);
             factor = landmarkWeightDA.getHeader(3 * 4) / DOUBLE_MLTPL;
@@ -790,8 +726,8 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
             setUpdateBestPath(false);
         }
 
-        public void setFilter(IntHashSet set, boolean fwd, boolean bwd) {
-            EdgeFilter ef = new BlockedEdgesFilter(flagEncoder.getAccessEnc(), fwd, bwd, set);
+        public void setFilter(IntHashSet set, boolean bwd, boolean fwd) {
+            EdgeFilter ef = new BlockedEdgesFilter(flagEncoder.getAccessEnc(), bwd, fwd, set);
             inEdgeFilter = ef;
             outEdgeFilter = ef;
         }
@@ -830,7 +766,7 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
             }
         }
 
-        boolean setSubnetworks(final byte[] subnetworks, final int subnetworkId) {
+        public boolean setSubnetworks(final byte[] subnetworks, final int subnetworkId) {
             if (subnetworkId > 127)
                 throw new IllegalStateException("Too many subnetworks " + subnetworkId);
 
@@ -858,7 +794,7 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
             return failed.get();
         }
 
-        public void initLandmarkWeights(final int lmIdx, int lmNodeId, final long rowSize) {
+        public void initLandmarkWeights(final int lmIdx, int lmNodeId, final long rowSize, final int offset) {
             IntObjectMap<SPTEntry> map = from ? bestWeightMapFrom : bestWeightMapTo;
             final AtomicInteger maxedout = new AtomicInteger(0);
             final Map.Entry<Double, Double> finalMaxWeight = new MapEntry<>(0d, 0d);
@@ -866,7 +802,7 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
             map.forEach(new IntObjectProcedure<SPTEntry>() {
                 @Override
                 public void apply(int nodeId, SPTEntry b) {
-                    if (!lms.setWeight(lmIdx, nodeId, rowSize, b.weight, from)) {
+                    if (!lms.setWeight(nodeId * rowSize + lmIdx * 4 + offset, b.weight)) {
                         maxedout.incrementAndGet();
                         finalMaxWeight.setValue(Math.max(b.weight, finalMaxWeight.getValue()));
                     }
@@ -875,8 +811,8 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
 
             if ((double) maxedout.get() / map.size() > 0.1) {
                 LOGGER.warn("landmark " + lmIdx + " (" + nodeAccess.getLatitude(lmNodeId) + "," + nodeAccess.getLongitude(lmNodeId) + "): " +
-                        "too many " + (from ? "backward" : "delta") + " weights were maxed out (" + maxedout.get() + "/" + map.size() + "). Factor is too small " + lms.factor
-                        + ". To fix this increase maximum in config.yml: prepare.lm.weighting: " + weighting.getName() + "|maximum=" + finalMaxWeight.getValue() * 1.2);
+                        "too many weights were maxed out (" + maxedout.get() + "/" + map.size() + "). Use a bigger factor than " + lms.factor
+                        + ". For example use the following in the config.yml: weighting=" + weighting.getName() + "|maximum=" + finalMaxWeight.getValue() * 1.2);
             }
         }
     }
@@ -891,7 +827,7 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
         }
     };
 
-    private static GHPoint createPoint(Graph graph, int nodeId) {
+    static GHPoint createPoint(Graph graph, int nodeId) {
         return new GHPoint(graph.getNodeAccess().getLatitude(nodeId), graph.getNodeAccess().getLongitude(nodeId));
     }
 
@@ -915,7 +851,7 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
         private final boolean fwd;
         private final boolean bwd;
 
-        public BlockedEdgesFilter(BooleanEncodedValue accessEnc, boolean fwd, boolean bwd, IntHashSet blockedEdges) {
+        public BlockedEdgesFilter(BooleanEncodedValue accessEnc, boolean bwd, boolean fwd, IntHashSet blockedEdges) {
             this.accessEnc = accessEnc;
             this.fwd = fwd;
             this.bwd = bwd;
@@ -928,17 +864,9 @@ public class LandmarkStorage implements Storable<LandmarkStorage> {
             return fwd && iter.get(accessEnc) && !blocked || bwd && iter.getReverse(accessEnc) && !blocked;
         }
 
-        public boolean acceptsBackward() {
-            return bwd;
-        }
-
-        public boolean acceptsForward() {
-            return fwd;
-        }
-
         @Override
         public String toString() {
             return accessEnc + ", bwd:" + bwd + ", fwd:" + fwd;
         }
     }
-}
\ No newline at end of file
+}
diff --git a/core/src/main/java/com/graphhopper/routing/lm/PerfectApproximator.java b/core/src/main/java/com/graphhopper/routing/lm/PerfectApproximator.java
new file mode 100644
index 000000000..42245de54
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/lm/PerfectApproximator.java
@@ -0,0 +1,67 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for
+ *  additional information regarding copyright ownership.
+ *
+ *  GraphHopper GmbH licenses this file to you under the Apache License,
+ *  Version 2.0 (the "License"); you may not use this file except in
+ *  compliance with the License. You may obtain a copy of the License at
+ *
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package com.graphhopper.routing.lm;
+
+import com.graphhopper.routing.Dijkstra;
+import com.graphhopper.routing.Path;
+import com.graphhopper.routing.util.TraversalMode;
+import com.graphhopper.routing.weighting.WeightApproximator;
+import com.graphhopper.routing.weighting.Weighting;
+import com.graphhopper.storage.Graph;
+
+/**
+ * Just a sanity-check implementation for WeightApproximator, which 'approximates' perfectly.
+ */
+public class PerfectApproximator implements WeightApproximator {
+
+    private Graph graph;
+    private Weighting weighting;
+    private TraversalMode traversalMode;
+    private int to;
+    private boolean reverse;
+
+    public PerfectApproximator(Graph graph, Weighting weighting, TraversalMode traversalMode, boolean reverse) {
+        this.graph = graph;
+        this.weighting = weighting;
+        this.traversalMode = traversalMode;
+        this.reverse = reverse;
+    }
+
+    @Override
+    public double approximate(int currentNode) {
+        Dijkstra dijkstra = new Dijkstra(graph, weighting, traversalMode);
+        Path path = reverse ? dijkstra.calcPath(to, currentNode) : dijkstra.calcPath(currentNode, to);
+        return path.isFound() ? path.getWeight() : Double.POSITIVE_INFINITY;
+    }
+
+    @Override
+    public void setTo(int to) {
+        this.to = to;
+    }
+
+    @Override
+    public WeightApproximator reverse() {
+        return new PerfectApproximator(graph, weighting, traversalMode, !reverse);
+    }
+
+    @Override
+    public double getSlack() {
+        return 0;
+    }
+}
diff --git a/core/src/main/java/com/graphhopper/routing/lm/PrepareLandmarks.java b/core/src/main/java/com/graphhopper/routing/lm/PrepareLandmarks.java
index 383fd1665..ecb311596 100644
--- a/core/src/main/java/com/graphhopper/routing/lm/PrepareLandmarks.java
+++ b/core/src/main/java/com/graphhopper/routing/lm/PrepareLandmarks.java
@@ -143,7 +143,7 @@ public class PrepareLandmarks extends AbstractAlgoPreparation {
 
             double epsilon = opts.getHints().getDouble(Parameters.Algorithms.AStar.EPSILON, 1);
             AStar astar = (AStar) algo;
-            astar.setApproximation(new LMApproximator(qGraph, this.graph.getNodes(), lms, activeLM, lms.getFactor(), false).
+            astar.setApproximation(new LMApproximator(qGraph, weighting, this.graph.getNodes(), lms, activeLM, lms.getFactor(), false).
                     setEpsilon(epsilon));
             return algo;
         } else if (algo instanceof AStarBidirection) {
@@ -152,7 +152,7 @@ public class PrepareLandmarks extends AbstractAlgoPreparation {
 
             double epsilon = opts.getHints().getDouble(Parameters.Algorithms.AStarBi.EPSILON, 1);
             AStarBidirection astarbi = (AStarBidirection) algo;
-            astarbi.setApproximation(new LMApproximator(qGraph, this.graph.getNodes(), lms, activeLM, lms.getFactor(), false).
+            astarbi.setApproximation(new LMApproximator(qGraph, weighting, this.graph.getNodes(), lms, activeLM, lms.getFactor(), false).
                     setEpsilon(epsilon));
             return algo;
         } else if (algo instanceof AlternativeRoute) {
@@ -161,7 +161,7 @@ public class PrepareLandmarks extends AbstractAlgoPreparation {
 
             double epsilon = opts.getHints().getDouble(Parameters.Algorithms.AStarBi.EPSILON, 1);
             AlternativeRoute altRoute = (AlternativeRoute) algo;
-            altRoute.setApproximation(new LMApproximator(qGraph, this.graph.getNodes(), lms, activeLM, lms.getFactor(), false).
+            altRoute.setApproximation(new LMApproximator(qGraph, weighting, this.graph.getNodes(), lms, activeLM, lms.getFactor(), false).
                     setEpsilon(epsilon));
             // landmark algorithm follows good compromise between fast response and exploring 'interesting' paths so we
             // can decrease this exploration factor further (1->dijkstra, 0.8->bidir. A*)
diff --git a/core/src/main/java/com/graphhopper/routing/util/BikeCommonFlagEncoder.java b/core/src/main/java/com/graphhopper/routing/util/BikeCommonFlagEncoder.java
index b5439c139..abdc8ba04 100644
--- a/core/src/main/java/com/graphhopper/routing/util/BikeCommonFlagEncoder.java
+++ b/core/src/main/java/com/graphhopper/routing/util/BikeCommonFlagEncoder.java
@@ -22,8 +22,6 @@ import com.graphhopper.routing.profiles.*;
 import com.graphhopper.routing.weighting.PriorityWeighting;
 import com.graphhopper.storage.IntsRef;
 import com.graphhopper.util.Helper;
-import com.graphhopper.util.InstructionAnnotation;
-import com.graphhopper.util.Translation;
 
 import java.util.*;
 
diff --git a/core/src/main/java/com/graphhopper/routing/weighting/ConsistentWeightApproximator.java b/core/src/main/java/com/graphhopper/routing/weighting/BalancedWeightApproximator.java
similarity index 53%
rename from core/src/main/java/com/graphhopper/routing/weighting/ConsistentWeightApproximator.java
rename to core/src/main/java/com/graphhopper/routing/weighting/BalancedWeightApproximator.java
index a042d6efc..33a240a8e 100644
--- a/core/src/main/java/com/graphhopper/routing/weighting/ConsistentWeightApproximator.java
+++ b/core/src/main/java/com/graphhopper/routing/weighting/BalancedWeightApproximator.java
@@ -18,19 +18,35 @@
 package com.graphhopper.routing.weighting;
 
 /**
- * Turns an unidirectional weight Approximation into a bidirectional consistent one.
+ * Turns an unidirectional weight Approximation into a bidirectional balanced one.
+ * This means it can be used with an A* implementation that uses the stopping criterion
+ * described in [1].
+ *
+ * Note: In the paper, it is called a consistent (rather than balanced)
+ * approximator, but as noted in [2], consistent also means a different property which
+ * an approximator must already have before it should be plugged into this class (!).
+ *
+ * Most literature uses balanced for the property that this class is about.
+ *
  * <p>
- * Ikeda, T., Hsu, M.-Y., Imai, H., Nishimura, S., Shimoura, H., Hashimoto, T., Tenmoku, K., and
+ * [1] Ikeda, T., Hsu, M.-Y., Imai, H., Nishimura, S., Shimoura, H., Hashimoto, T., Tenmoku, K., and
  * Mitoh, K. (1994). A fast algorithm for finding better routes by ai search techniques. In VNIS,
  * pages 291–296.
  *
+ * [2] Pijls, W.H.L.M, & Post, H. (2008). A new bidirectional algorithm for shortest paths (No. EI 2008-25).
+ * Report / Econometric Institute, Erasmus University Rotterdam
+ *
  * @author jansoe
  * @author Peter Karich
  */
-public class ConsistentWeightApproximator {
+public class BalancedWeightApproximator {
+
     private final WeightApproximator uniDirApproximatorForward, uniDirApproximatorReverse;
 
-    public ConsistentWeightApproximator(WeightApproximator weightApprox) {
+    // Constants to shift the estimate (reverse estimate) so that it is actually 0 at the destination (source).
+    double fromOffset, toOffset;
+
+    public BalancedWeightApproximator(WeightApproximator weightApprox) {
         if (weightApprox == null)
             throw new IllegalArgumentException("WeightApproximator cannot be null");
 
@@ -42,22 +58,24 @@ public class ConsistentWeightApproximator {
         return uniDirApproximatorForward;
     }
 
-    public void setFrom(int from) {
+    public void setFromTo(int from, int to) {
         uniDirApproximatorReverse.setTo(from);
-    }
-
-    public void setTo(int to) {
         uniDirApproximatorForward.setTo(to);
+        fromOffset = 0.5 * uniDirApproximatorForward.approximate(from);
+        toOffset = 0.5 * uniDirApproximatorReverse.approximate(to);
     }
 
     public double approximate(int node, boolean reverse) {
-        double weightApproximation = 0.5
-                * (uniDirApproximatorForward.approximate(node) - uniDirApproximatorReverse.approximate(node));
-
-        if (reverse)
-            return -weightApproximation;
+        double weightApproximation = 0.5 * (uniDirApproximatorForward.approximate(node) - uniDirApproximatorReverse.approximate(node));
+        if (reverse) {
+            return fromOffset - weightApproximation;
+        } else {
+            return toOffset + weightApproximation;
+        }
+    }
 
-        return weightApproximation;
+    public double getSlack() {
+        return uniDirApproximatorForward.getSlack();
     }
 
     @Override
diff --git a/core/src/main/java/com/graphhopper/routing/weighting/BeelineWeightApproximator.java b/core/src/main/java/com/graphhopper/routing/weighting/BeelineWeightApproximator.java
index 58129df31..ec06593d6 100644
--- a/core/src/main/java/com/graphhopper/routing/weighting/BeelineWeightApproximator.java
+++ b/core/src/main/java/com/graphhopper/routing/weighting/BeelineWeightApproximator.java
@@ -55,6 +55,11 @@ public class BeelineWeightApproximator implements WeightApproximator {
         return new BeelineWeightApproximator(nodeAccess, weighting).setDistanceCalc(distanceCalc).setEpsilon(epsilon);
     }
 
+    @Override
+    public double getSlack() {
+        return 0;
+    }
+
     @Override
     public double approximate(int fromNode) {
         double fromLat = nodeAccess.getLatitude(fromNode);
diff --git a/core/src/main/java/com/graphhopper/routing/weighting/WeightApproximator.java b/core/src/main/java/com/graphhopper/routing/weighting/WeightApproximator.java
index ddb1a33a1..557c9e52c 100644
--- a/core/src/main/java/com/graphhopper/routing/weighting/WeightApproximator.java
+++ b/core/src/main/java/com/graphhopper/routing/weighting/WeightApproximator.java
@@ -39,4 +39,6 @@ public interface WeightApproximator {
      * towards the 'to'.
      */
     WeightApproximator reverse();
+
+    double getSlack();
 }
diff --git a/core/src/main/java/com/graphhopper/util/GHUtility.java b/core/src/main/java/com/graphhopper/util/GHUtility.java
index 43deaaca0..5b41e882b 100644
--- a/core/src/main/java/com/graphhopper/util/GHUtility.java
+++ b/core/src/main/java/com/graphhopper/util/GHUtility.java
@@ -204,8 +204,8 @@ public class GHUtility {
             // using bidirectional edges will increase mean degree of graph above given value
             boolean bothDirections = random.nextDouble() < pBothDir;
             EdgeIteratorState edge = graph.edge(from, to, distance, bothDirections);
-            double fwdSpeed = 10 + random.nextDouble() * 120;
-            double bwdSpeed = 10 + random.nextDouble() * 120;
+            double fwdSpeed = 10 + random.nextDouble() * 110;
+            double bwdSpeed = 10 + random.nextDouble() * 110;
             if (randomSpeedEnc != null) {
                 edge.set(randomSpeedEnc, fwdSpeed);
                 if (randomSpeedEnc.isStoreTwoDirections())


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java b/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java
deleted file mode 100644
index d28b8e0d4..000000000
--- a/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java
+++ /dev/null
@@ -1,75 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.routing;
-
-import com.graphhopper.routing.util.EncodingManager;
-import com.graphhopper.routing.util.FlagEncoder;
-import com.graphhopper.routing.util.TraversalMode;
-import com.graphhopper.routing.weighting.ShortestWeighting;
-import com.graphhopper.storage.Graph;
-import com.graphhopper.storage.GraphBuilder;
-import com.graphhopper.storage.SPTEntry;
-import org.junit.Test;
-
-import java.util.concurrent.atomic.AtomicReference;
-
-import static com.graphhopper.util.GHUtility.updateDistancesFor;
-import static org.junit.Assert.assertEquals;
-
-/**
- * Run some tests specific for {@link AStarBidirection}
- *
- * @author Peter Karich
- * @see RoutingAlgorithmTest for test cases covering standard node- and edge-based routing with this algorithm
- * @see EdgeBasedRoutingAlgorithmTest for test cases covering routing with turn costs with this algorithm
- */
-public class AStarBidirectionTest {
-    private final EncodingManager encodingManager = EncodingManager.create("car");
-    private final FlagEncoder carEncoder = encodingManager.getEncoder("car");
-
-    @Test
-    public void testInitFromAndTo() {
-        doTestInitFromAndTo(TraversalMode.NODE_BASED);
-        doTestInitFromAndTo(TraversalMode.EDGE_BASED);
-    }
-
-    private void doTestInitFromAndTo(final TraversalMode traversalMode) {
-        Graph g = new GraphBuilder(encodingManager).create();
-        g.edge(0, 1, 1, true);
-        updateDistancesFor(g, 0, 0.00, 0.00);
-        updateDistancesFor(g, 1, 0.01, 0.01);
-
-        final AtomicReference<SPTEntry> fromRef = new AtomicReference<>();
-        final AtomicReference<SPTEntry> toRef = new AtomicReference<>();
-        AStarBidirection astar = new AStarBidirection(g, new ShortestWeighting(carEncoder), traversalMode) {
-            @Override
-            public void init(int from, double fromWeight, int to, double toWeight) {
-                super.init(from, fromWeight, to, toWeight);
-                fromRef.set(currFrom);
-                toRef.set(currTo);
-            }
-        };
-        astar.init(0, 1, 1, 0.5);
-
-        assertEquals(1, ((AStar.AStarEntry) fromRef.get()).weightOfVisitedPath, .1);
-        assertEquals(787.3, fromRef.get().weight, .1);
-
-        assertEquals(0.5, ((AStar.AStarEntry) toRef.get()).weightOfVisitedPath, .1);
-        assertEquals(786.8, toRef.get().weight, .1);
-    }
-}
diff --git a/core/src/test/java/com/graphhopper/routing/lm/LMApproximatorTest.java b/core/src/test/java/com/graphhopper/routing/lm/LMApproximatorTest.java
new file mode 100644
index 000000000..26e7d5bb2
--- /dev/null
+++ b/core/src/test/java/com/graphhopper/routing/lm/LMApproximatorTest.java
@@ -0,0 +1,181 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for
+ *  additional information regarding copyright ownership.
+ *
+ *  GraphHopper GmbH licenses this file to you under the Apache License,
+ *  Version 2.0 (the "License"); you may not use this file except in
+ *  compliance with the License. You may obtain a copy of the License at
+ *
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package com.graphhopper.routing.lm;
+
+import com.graphhopper.Repeat;
+import com.graphhopper.RepeatRule;
+import com.graphhopper.routing.Dijkstra;
+import com.graphhopper.routing.Path;
+import com.graphhopper.routing.util.CarFlagEncoder;
+import com.graphhopper.routing.util.DefaultEdgeFilter;
+import com.graphhopper.routing.util.EncodingManager;
+import com.graphhopper.routing.util.TraversalMode;
+import com.graphhopper.routing.weighting.*;
+import com.graphhopper.storage.Directory;
+import com.graphhopper.storage.GraphBuilder;
+import com.graphhopper.storage.GraphHopperStorage;
+import com.graphhopper.storage.RAMDirectory;
+import com.graphhopper.util.EdgeIterator;
+import com.graphhopper.util.GHUtility;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+
+import java.util.Random;
+
+import static org.junit.Assert.assertEquals;
+
+public class LMApproximatorTest {
+
+    @Rule
+    public RepeatRule repeatRule = new RepeatRule();
+
+    @Before
+    public void init() {
+    }
+
+    @Test
+    @Repeat(times = 5)
+    public void randomGraph() {
+        final long seed = System.nanoTime();
+        System.out.println("random Graph seed: " + seed);
+        run(seed);
+    }
+
+    @Test
+    public void fail7() {
+        run(337586249813919L);
+    }
+
+    private void run(long seed) {
+        Directory dir = new RAMDirectory();
+        CarFlagEncoder encoder = new CarFlagEncoder(5, 5, 1);
+        EncodingManager encodingManager = EncodingManager.create(encoder);
+        GraphHopperStorage graph = new GraphBuilder(encodingManager).setDir(dir).withTurnCosts(true).create();
+
+        Random rnd = new Random(seed);
+        GHUtility.buildRandomGraph(graph, rnd, 100, 2.2, true, true, encoder.getAverageSpeedEnc(), 0.7, 0.8, 0.8);
+
+        Weighting weighting = new FastestWeighting(encoder);
+
+        PrepareLandmarks lm = new PrepareLandmarks(dir, graph, weighting, 16, 8);
+        lm.setMaximumWeight(10000);
+        lm.doWork();
+        LandmarkStorage landmarkStorage = lm.getLandmarkStorage();
+
+        for (int t = 0; t < graph.getNodes(); t++) {
+            LMApproximator lmApproximator = new LMApproximator(graph, weighting, graph.getNodes(), landmarkStorage, 8, landmarkStorage.getFactor(), false);
+            WeightApproximator reverseLmApproximator = lmApproximator.reverse();
+            BeelineWeightApproximator beelineApproximator = new BeelineWeightApproximator(graph.getNodeAccess(), weighting);
+            WeightApproximator reverseBeelineApproximator = beelineApproximator.reverse();
+            PerfectApproximator perfectApproximator = new PerfectApproximator(graph, weighting, TraversalMode.NODE_BASED, false);
+            PerfectApproximator reversePerfectApproximator = new PerfectApproximator(graph, weighting, TraversalMode.NODE_BASED, true);
+            BalancedWeightApproximator balancedWeightApproximator = new BalancedWeightApproximator(new LMApproximator(graph, weighting, graph.getNodes(), landmarkStorage, 8, landmarkStorage.getFactor(), false));
+
+            lmApproximator.setTo(t);
+            beelineApproximator.setTo(t);
+            reverseLmApproximator.setTo(t);
+            reverseBeelineApproximator.setTo(t);
+            perfectApproximator.setTo(t);
+            reversePerfectApproximator.setTo(t);
+            balancedWeightApproximator.setFromTo(0, t);
+            int nOverApproximatedWeights = 0;
+            int nInconsistentWeights = 0;
+            for (int v = 0; v< graph.getNodes(); v++) {
+                Dijkstra dijkstra = new Dijkstra(graph, weighting, TraversalMode.NODE_BASED);
+                Path path = dijkstra.calcPath(v, t);
+                if (path.isFound()) {
+                    // Give the beelineApproximator some slack, because the map distance of an edge
+                    // can be _smaller_ than its Euklidean distance, due to rounding.
+                    double slack = path.getEdgeCount() * (1 / 1000.0);
+                    double realRemainingWeight = path.getWeight();
+                    double approximatedRemainingWeight = lmApproximator.approximate(v);
+                    if (approximatedRemainingWeight - slack > realRemainingWeight) {
+                        System.out.printf("LM: %f\treal: %f\n", approximatedRemainingWeight, realRemainingWeight);
+                        nOverApproximatedWeights++;
+                    }
+                    double beelineApproximatedRemainingWeight = beelineApproximator.approximate(v);
+                    if (beelineApproximatedRemainingWeight - slack > realRemainingWeight) {
+                        System.out.printf("beeline: %f\treal: %f\n", beelineApproximatedRemainingWeight, realRemainingWeight);
+                        nOverApproximatedWeights++;
+                    }
+                    double approximate = perfectApproximator.approximate(v);
+                    if (approximate > realRemainingWeight) {
+                        System.out.printf("perfect: %f\treal: %f\n", approximate, realRemainingWeight);
+                        nOverApproximatedWeights++;
+                    }
+
+                    // Triangle inequality for approximator. This is what makes it 'consistent'.
+                    // That's a requirement for normal A*-implementations, because if it is violated,
+                    // the heap-weight of settled nodes can decrease, and that would mean our
+                    // stopping criterion is not sufficient.
+                    EdgeIterator neighbors = graph.createEdgeExplorer(DefaultEdgeFilter.outEdges(encoder)).setBaseNode(v);
+                    while (neighbors.next()) {
+                        int w = neighbors.getAdjNode();
+                        double vw = weighting.calcWeight(neighbors, false, -1);
+                        double vwApprox = lmApproximator.approximate(v) - lmApproximator.approximate(w);
+                        if (vwApprox - lm.getLandmarkStorage().getFactor() > vw) {
+                            System.out.printf("%f\t%f\n", vwApprox - lm.getLandmarkStorage().getFactor(),vw);
+                            nInconsistentWeights++;
+                        }
+                    }
+
+                    neighbors = graph.createEdgeExplorer(DefaultEdgeFilter.outEdges(encoder)).setBaseNode(v);
+                    while (neighbors.next()) {
+                        int w = neighbors.getAdjNode();
+                        double vw = weighting.calcWeight(neighbors, false, -1);
+                        double vwApprox = balancedWeightApproximator.approximate(v, false) - balancedWeightApproximator.approximate(w, false);
+                        if (vwApprox - lm.getLandmarkStorage().getFactor() > vw) {
+                            System.out.printf("%f\t%f\n", vwApprox - lm.getLandmarkStorage().getFactor(),vw);
+                            nInconsistentWeights++;
+                        }
+                    }
+                }
+                Dijkstra reverseDijkstra = new Dijkstra(graph, weighting, TraversalMode.NODE_BASED);
+                Path reversePath = reverseDijkstra.calcPath(t, v);
+                if (reversePath.isFound()) {
+                    // Give the beelineApproximator some slack, because the map distance of an edge
+                    // can be _smaller_ than its Euklidean distance, due to rounding.
+                    double slack = reversePath.getEdgeCount() * (1 / 1000.0);
+                    double realRemainingWeight = reversePath.getWeight();
+                    double approximatedRemainingWeight = reverseLmApproximator.approximate(v);
+                    if (approximatedRemainingWeight - slack > realRemainingWeight) {
+                        System.out.printf("LM: %f\treal: %f\n", approximatedRemainingWeight, realRemainingWeight);
+                        nOverApproximatedWeights++;
+                    }
+                    double beelineApproximatedRemainingWeight = reverseBeelineApproximator.approximate(v);
+                    if (beelineApproximatedRemainingWeight - slack > realRemainingWeight) {
+                        System.out.printf("beeline: %f\treal: %f\n", beelineApproximatedRemainingWeight, realRemainingWeight);
+                        nOverApproximatedWeights++;
+                    }
+                    double approximate = reversePerfectApproximator.approximate(v);
+                    if (approximate > realRemainingWeight) {
+                        System.out.printf("perfect: %f\treal: %f\n", approximate, realRemainingWeight);
+                        nOverApproximatedWeights++;
+                    }
+                }
+
+            }
+
+            assertEquals(0, nOverApproximatedWeights);
+            assertEquals(0, nInconsistentWeights);
+        }
+    }
+
+}
\ No newline at end of file
diff --git a/core/src/test/java/com/graphhopper/routing/lm/LandmarkStorageTest.java b/core/src/test/java/com/graphhopper/routing/lm/LandmarkStorageTest.java
index 5c1f39b66..d7e830f51 100644
--- a/core/src/test/java/com/graphhopper/routing/lm/LandmarkStorageTest.java
+++ b/core/src/test/java/com/graphhopper/routing/lm/LandmarkStorageTest.java
@@ -95,29 +95,21 @@ public class LandmarkStorageTest {
 
         LandmarkStorage lms = new LandmarkStorage(ghStorage, dir, new FastestWeighting(encoder), 4).
                 setMaximumWeight(LandmarkStorage.PRECISION);
-        /* FROM_WEIGHT_BITS = 18
-        2^18 = 262144, use -1 for infinity and -2 for maximum
-        As the backward weight reaches a too high value it will use the maximum instead of 0 or infinity*/
-        lms.setWeight(0, 0, 16, Math.pow(2, 18), true);
-        assertEquals((int) Math.pow(2, 18) - 2, lms.getFromWeight(0, 0));
-        lms.setWeight(0, 0, 16, 999999, true);
-        assertEquals((int) Math.pow(2, 18) - 2, lms.getFromWeight(0, 0));
-
-        lms.setWeight(0, 0, 16, 999999, false);
-        // The important property is that the weight that is returned
-        // is _not bigger_ than the weight that was set.
-        assertTrue(lms.getToWeight(0, 0) * lms.getFactor() <= 999999);
-        lms.setWeight(0, 0, 16, 1, false);
-        // This is an underrun of the 'delta' field -- but still, the important property is that the weight that is returned
-        // is _not bigger_ than the weight that was set.
-        assertTrue(lms.getToWeight(0, 0) * lms.getFactor() <= 1);
+        // 2^16=65536, use -1 for infinity and -2 for maximum
+        lms.setWeight(0, 65536);
+        // reached maximum value but do not reset to 0 instead use 2^16-2
+        assertEquals(65536 - 2, lms.getFromWeight(0, 0));
+        lms.setWeight(0, 65535);
+        assertEquals(65534, lms.getFromWeight(0, 0));
+        lms.setWeight(0, 79999);
+        assertEquals(65534, lms.getFromWeight(0, 0));
 
         da.setInt(0, Integer.MAX_VALUE);
         assertTrue(lms.isInfinity(0));
         // for infinity return much bigger value
         // assertEquals(Integer.MAX_VALUE, lms.getFromWeight(0, 0));
 
-        lms.setWeight(0, 0, 16, 999999, true);
+        lms.setWeight(0, 79999);
         assertFalse(lms.isInfinity(0));
     }
 
@@ -247,74 +239,4 @@ public class LandmarkStorageTest {
         storage.createLandmarks();
         assertEquals(3, storage.getSubnetworksWithLandmarks());
     }
-
-    @Test
-    public void testDelta() {
-        int distance = 1000000;
-
-        ghStorage.edge(1, 2, distance, false);
-        ghStorage.edge(2, 3, distance, false);
-        ghStorage.edge(3, 1, distance, false);
-
-        ghStorage.edge(2, 4, distance, true);
-        ghStorage.edge(4, 5, distance, true);
-        ghStorage.edge(5, 6, distance, true);
-        ghStorage.edge(6, 7, distance, true);
-        ghStorage.edge(7, 8, distance, true);
-        ghStorage.edge(8, 9, distance, true);
-
-        ghStorage.edge(3, 10, distance, true);
-        ghStorage.edge(10, 11, distance, true);
-        ghStorage.edge(11, 12, distance, true);
-        ghStorage.edge(12, 13, distance, true);
-        ghStorage.edge(13, 14, distance, true);
-        ghStorage.edge(14, 15, distance, true);
-
-        LandmarkStorage storage = new LandmarkStorage(ghStorage, new RAMDirectory(), new FastestWeighting(encoder), 2);
-        storage.createLandmarks();
-
-        assertEquals(15, storage.getLandmarks(1)[0]);
-        assertEquals(9, storage.getLandmarks(1)[1]);
-
-        assertEquals(35680, storage.getFromWeight(0, 1));
-        assertEquals(40777, storage.getToWeight(0, 1));
-        assertEquals(71361, storage.getFromWeight(0, 9));
-        assertEquals(66264, storage.getToWeight(0, 9));
-        assertEquals(15291, storage.getFromWeight(0, 12));
-        assertEquals(15291, storage.getToWeight(0, 12));
-        assertEquals(40777, storage.getFromWeight(1, 1));
-        assertEquals(35680, storage.getToWeight(1, 1));
-        assertEquals(50972, storage.getFromWeight(1, 12));
-        assertEquals(56069, storage.getToWeight(1, 12));
-        assertEquals(66264, storage.getFromWeight(1, 15));
-        assertEquals(71361, storage.getToWeight(1, 15));
-    }
-
-    @Test
-    public void testDeltaWarning() {
-        int distance = 1000000;
-
-        ghStorage.edge(1, 2, distance, false);
-        ghStorage.edge(2, 3, distance, false);
-        ghStorage.edge(3, 4, distance, false);
-        ghStorage.edge(4, 5, distance, false);
-        ghStorage.edge(5, 6, distance, false);
-        ghStorage.edge(6, 1, distance, false);
-
-        ghStorage.edge(1, 7, distance, true);
-        ghStorage.edge(7, 8, distance, true);
-        ghStorage.edge(8, 9, distance, true);
-
-        ghStorage.edge(6, 10, distance, true);
-        ghStorage.edge(10, 11, distance, true);
-        ghStorage.edge(11, 12, distance, true);
-
-        LandmarkStorage storage = new LandmarkStorage(ghStorage, new RAMDirectory(), new FastestWeighting(encoder), 2);
-        storage.createLandmarks();
-
-        assertEquals(12, storage.getLandmarks(1)[0]);
-        assertEquals(9, storage.getLandmarks(1)[1]);
-
-        assertEquals((int) Math.pow(2, 13) - 2, storage.getToWeight(0, 9) - storage.getFromWeight(0, 9));
-    }
 }
diff --git a/core/src/test/java/com/graphhopper/routing/lm/PrepareLandmarksTest.java b/core/src/test/java/com/graphhopper/routing/lm/PrepareLandmarksTest.java
index c7d2361de..9dc003194 100644
--- a/core/src/test/java/com/graphhopper/routing/lm/PrepareLandmarksTest.java
+++ b/core/src/test/java/com/graphhopper/routing/lm/PrepareLandmarksTest.java
@@ -122,11 +122,9 @@ public class PrepareLandmarksTest {
         assertEquals(weight1_47, store.getToWeight(1, 47));
 
         // prefer the landmarks before and behind the goal
-        int activeLandmarkIndices[] = new int[activeLM];
-        int activeFroms[] = new int[activeLM];
-        int activeTos[] = new int[activeLM];
+        int[] activeLandmarkIndices = new int[activeLM];
         Arrays.fill(activeLandmarkIndices, -1);
-        store.initActiveLandmarks(27, 47, activeLandmarkIndices, activeFroms, activeTos, false);
+        store.chooseActiveLandmarks(27, 47, activeLandmarkIndices, false);
         List<Integer> list = new ArrayList<>();
         for (int idx : activeLandmarkIndices) {
             list.add(store.getLandmarks(1)[idx]);
@@ -150,7 +148,7 @@ public class PrepareLandmarksTest {
 
         assertEquals(expectedPath.getWeight(), path.getWeight(), .1);
         assertEquals(expectedPath.calcNodes(), path.calcNodes());
-        assertEquals(expectedAlgo.getVisitedNodes(), oneDirAlgoWithLandmarks.getVisitedNodes() + 142);
+        assertEquals(expectedAlgo.getVisitedNodes() - 133, oneDirAlgoWithLandmarks.getVisitedNodes());
 
         // landmarks with bidir A*
         opts.getHints().put("lm.recalc_count", 50);
@@ -159,7 +157,7 @@ public class PrepareLandmarksTest {
         path = biDirAlgoWithLandmarks.calcPath(41, 183);
         assertEquals(expectedPath.getWeight(), path.getWeight(), .1);
         assertEquals(expectedPath.calcNodes(), path.calcNodes());
-        assertEquals(expectedAlgo.getVisitedNodes(), biDirAlgoWithLandmarks.getVisitedNodes() + 164);
+        assertEquals(expectedAlgo.getVisitedNodes() - 162, biDirAlgoWithLandmarks.getVisitedNodes());
 
         // landmarks with A* and a QueryGraph. We expect slightly less optimal as two more cycles needs to be traversed
         // due to the two more virtual nodes but this should not harm in practise
@@ -174,7 +172,7 @@ public class PrepareLandmarksTest {
         expectedPath = expectedAlgo.calcPath(fromQR.getClosestNode(), toQR.getClosestNode());
         assertEquals(expectedPath.getWeight(), path.getWeight(), .1);
         assertEquals(expectedPath.calcNodes(), path.calcNodes());
-        assertEquals(expectedAlgo.getVisitedNodes(), qGraphOneDirAlgo.getVisitedNodes() + 133);
+        assertEquals(expectedAlgo.getVisitedNodes() - 133, qGraphOneDirAlgo.getVisitedNodes());
     }
 
     @Test
diff --git a/core/src/test/java/com/graphhopper/routing/weighting/DirectedRoutingTest.java b/core/src/test/java/com/graphhopper/routing/weighting/DirectedRoutingTest.java
index fa0a733c5..503e2b91e 100644
--- a/core/src/test/java/com/graphhopper/routing/weighting/DirectedRoutingTest.java
+++ b/core/src/test/java/com/graphhopper/routing/weighting/DirectedRoutingTest.java
@@ -38,7 +38,7 @@ import static org.junit.Assert.fail;
  * target edges, by comparing with {@link DijkstraBidirectionRef}
  *
  * @author easbar
- * @see BidirectionalRoutingTest
+ * @see RandomizedRoutingTest
  * @see DirectedBidirectionalDijkstraTest
  */
 @RunWith(Parameterized.class)
diff --git a/core/src/test/java/com/graphhopper/routing/weighting/BidirectionalRoutingTest.java b/core/src/test/java/com/graphhopper/routing/weighting/RandomizedRoutingTest.java
similarity index 76%
rename from core/src/test/java/com/graphhopper/routing/weighting/BidirectionalRoutingTest.java
rename to core/src/test/java/com/graphhopper/routing/weighting/RandomizedRoutingTest.java
index e987c9166..0788afa38 100644
--- a/core/src/test/java/com/graphhopper/routing/weighting/BidirectionalRoutingTest.java
+++ b/core/src/test/java/com/graphhopper/routing/weighting/RandomizedRoutingTest.java
@@ -4,6 +4,7 @@ import com.graphhopper.Repeat;
 import com.graphhopper.RepeatRule;
 import com.graphhopper.routing.*;
 import com.graphhopper.routing.ch.PrepareContractionHierarchies;
+import com.graphhopper.routing.lm.PerfectApproximator;
 import com.graphhopper.routing.lm.PrepareLandmarks;
 import com.graphhopper.routing.profiles.DecimalEncodedValue;
 import com.graphhopper.routing.querygraph.QueryGraph;
@@ -15,7 +16,6 @@ import com.graphhopper.storage.index.QueryResult;
 import com.graphhopper.util.GHUtility;
 import com.graphhopper.util.shapes.BBox;
 import com.graphhopper.util.shapes.GHPoint;
-import org.junit.Assume;
 import org.junit.Before;
 import org.junit.Rule;
 import org.junit.Test;
@@ -33,14 +33,15 @@ import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
 /**
- * This test compares the different bidirectional routing algorithms with {@link DijkstraBidirectionRef}
+ * This test compares different routing algorithms with {@link DijkstraBidirectionRef}. Most prominently it uses
+ * randomly create graphs to create all sorts of different situations.
  *
  * @author easbar
  * @see RandomCHRoutingTest - similar but only tests CH algorithms
- * @see DirectedRoutingTest - similar but focusses on edge-based algorithms an directed queries
+ * @see DirectedRoutingTest - similar but focuses on edge-based algorithms an directed queries
  */
 @RunWith(Parameterized.class)
-public class BidirectionalRoutingTest {
+public class RandomizedRoutingTest {
     private final Algo algo;
     private final boolean prepareCH;
     private final boolean prepareLM;
@@ -61,25 +62,36 @@ public class BidirectionalRoutingTest {
     @Parameterized.Parameters(name = "{0}, {3}")
     public static Collection<Object[]> params() {
         return Arrays.asList(new Object[][]{
-                {Algo.ASTAR, false, false, NODE_BASED},
+                {Algo.DIJKSTRA, false, false, NODE_BASED},
+                {Algo.ASTAR_UNIDIR, false, false, NODE_BASED},
+                {Algo.ASTAR_BIDIR, false, false, NODE_BASED},
                 {Algo.CH_ASTAR, true, false, NODE_BASED},
                 {Algo.CH_DIJKSTRA, true, false, NODE_BASED},
-                {Algo.LM, false, true, NODE_BASED},
-                {Algo.ASTAR, false, false, EDGE_BASED},
+                {Algo.LM_UNIDIR, false, true, NODE_BASED},
+                {Algo.LM_BIDIR, false, true, NODE_BASED},
+                {Algo.DIJKSTRA, false, false, EDGE_BASED},
+                {Algo.ASTAR_UNIDIR, false, false, EDGE_BASED},
+                {Algo.ASTAR_BIDIR, false, false, EDGE_BASED},
                 {Algo.CH_ASTAR, true, false, EDGE_BASED},
                 {Algo.CH_DIJKSTRA, true, false, EDGE_BASED},
-                {Algo.LM, false, true, EDGE_BASED}
+                {Algo.LM_UNIDIR, false, true, EDGE_BASED},
+                {Algo.LM_BIDIR, false, true, EDGE_BASED},
+                {Algo.PERFECT_ASTAR, false, false, NODE_BASED}
         });
     }
 
     private enum Algo {
-        ASTAR,
+        DIJKSTRA,
+        ASTAR_BIDIR,
+        ASTAR_UNIDIR,
         CH_ASTAR,
         CH_DIJKSTRA,
-        LM
+        LM_BIDIR,
+        LM_UNIDIR,
+        PERFECT_ASTAR
     }
 
-    public BidirectionalRoutingTest(Algo algo, boolean prepareCH, boolean prepareLM, TraversalMode traversalMode) {
+    public RandomizedRoutingTest(Algo algo, boolean prepareCH, boolean prepareLM, TraversalMode traversalMode) {
         this.algo = algo;
         this.prepareCH = prepareCH;
         this.prepareLM = prepareLM;
@@ -89,12 +101,12 @@ public class BidirectionalRoutingTest {
     @Before
     public void init() {
         dir = new RAMDirectory();
-        // todonow: make this work with speed_both_directions=true!
-        encoder = new CarFlagEncoder(5, 5, 1);
+        encoder = new MotorcycleFlagEncoder(5, 5, 1);
         encodingManager = EncodingManager.create(encoder);
         weighting = new FastestWeighting(encoder);
         chProfiles = Arrays.asList(CHProfile.nodeBased(weighting), CHProfile.edgeBased(weighting, INFINITE_U_TURN_COSTS));
         graph = createGraph();
+        chGraph = graph.getCHGraph(!traversalMode.isEdgeBased() ? chProfiles.get(0) : chProfiles.get(1));
     }
 
     private void preProcessGraph() {
@@ -107,26 +119,37 @@ public class BidirectionalRoutingTest {
         }
         if (prepareLM) {
             lm = new PrepareLandmarks(dir, graph, weighting, 16, 8);
-            lm.setMaximumWeight(1000);
+            lm.setMaximumWeight(10000);
             lm.doWork();
         }
     }
 
-    private BidirRoutingAlgorithm createAlgo() {
+    private RoutingAlgorithm createAlgo() {
         return createAlgo(graph);
     }
 
-    private BidirRoutingAlgorithm createAlgo(Graph graph) {
+    private RoutingAlgorithm createAlgo(Graph graph) {
         switch (algo) {
-            case ASTAR:
+            case DIJKSTRA:
+                return new Dijkstra(graph, weighting, traversalMode);
+            case ASTAR_UNIDIR:
+                return new AStar(graph, weighting, traversalMode);
+            case ASTAR_BIDIR:
                 return new AStarBidirection(graph, weighting, traversalMode);
             case CH_DIJKSTRA:
-                return (BidirRoutingAlgorithm) pch.getRoutingAlgorithmFactory().createAlgo(graph instanceof QueryGraph ? graph : chGraph, AlgorithmOptions.start().weighting(weighting).algorithm(DIJKSTRA_BI).build());
+                return pch.getRoutingAlgorithmFactory().createAlgo(graph instanceof QueryGraph ? graph : chGraph, AlgorithmOptions.start().weighting(weighting).algorithm(DIJKSTRA_BI).build());
             case CH_ASTAR:
-                return (BidirRoutingAlgorithm) pch.getRoutingAlgorithmFactory().createAlgo(graph instanceof QueryGraph ? graph : chGraph, AlgorithmOptions.start().weighting(weighting).algorithm(ASTAR_BI).build());
-            case LM:
+                return pch.getRoutingAlgorithmFactory().createAlgo(graph instanceof QueryGraph ? graph : chGraph, AlgorithmOptions.start().weighting(weighting).algorithm(ASTAR_BI).build());
+            case LM_BIDIR:
                 AStarBidirection astarbi = new AStarBidirection(graph, weighting, traversalMode);
-                return (BidirRoutingAlgorithm) lm.getDecoratedAlgorithm(graph, astarbi, AlgorithmOptions.start().build());
+                return lm.getDecoratedAlgorithm(graph, astarbi, AlgorithmOptions.start().build());
+            case LM_UNIDIR:
+                AStar astar = new AStar(graph, weighting, traversalMode);
+                return lm.getDecoratedAlgorithm(graph, astar, AlgorithmOptions.start().build());
+            case PERFECT_ASTAR:
+                AStarBidirection perfectastarbi = new AStarBidirection(graph, weighting, traversalMode);
+                perfectastarbi.setApproximation(new PerfectApproximator(graph, weighting, traversalMode, false));
+                return perfectastarbi;
             default:
                 throw new IllegalArgumentException("unknown algo " + algo);
         }
@@ -172,7 +195,7 @@ public class BidirectionalRoutingTest {
                 .calcPath(source, target);
         Path path = createAlgo()
                 .calcPath(0, 3);
-        comparePaths(refPath, path, source, target);
+        comparePaths(refPath, path, source, target, -1);
     }
 
     @Test
@@ -211,17 +234,17 @@ public class BidirectionalRoutingTest {
                 .calcPath(source, target);
         Path path = createAlgo()
                 .calcPath(source, target);
-        comparePaths(refPath, path, source, target);
+        comparePaths(refPath, path, source, target, -1);
     }
 
     @Test
     @Repeat(times = 5)
     public void randomGraph() {
-        // todo: there are some problems with random graph testing for LM, see #1687
-        Assume.assumeFalse(algo.equals(Algo.LM));
-
         final long seed = System.nanoTime();
-        System.out.println("random Graph seed: " + seed);
+        run(seed);
+    }
+
+    private void run(long seed) {
         final int numQueries = 50;
         Random rnd = new Random(seed);
         GHUtility.buildRandomGraph(graph, rnd, 100, 2.2, true, true, encoder.getAverageSpeedEnc(), 0.7, 0.8, 0.8);
@@ -236,13 +259,13 @@ public class BidirectionalRoutingTest {
                     .calcPath(source, target);
             Path path = createAlgo()
                     .calcPath(source, target);
-            strictViolations.addAll(comparePaths(refPath, path, source, target));
+            strictViolations.addAll(comparePaths(refPath, path, source, target, seed));
         }
         if (strictViolations.size() > Math.max(1, 0.20 * numQueries)) {
             for (String strictViolation : strictViolations) {
                 System.out.println("strict violation: " + strictViolation);
             }
-            fail("Too many strict violations: " + strictViolations.size() + " / " + numQueries);
+            fail("Too many strict violations: " + strictViolations.size() + " / " + numQueries + ", seed: " + seed);
         }
     }
 
@@ -252,13 +275,12 @@ public class BidirectionalRoutingTest {
     @Test
     @Repeat(times = 5)
     public void randomGraph_withQueryGraph() {
-        // todo: there are some problems with random graph testing for LM, see #1687
-        Assume.assumeFalse(algo.equals(Algo.LM));
-
         final long seed = System.nanoTime();
-        System.out.println("randomGraph_withQueryGraph seed: " + seed);
-        final int numQueries = 50;
+        runWithQueryGraph(seed);
+    }
 
+    private void runWithQueryGraph(long seed) {
+        final int numQueries = 50;
         // we may not use an offset when query graph is involved, otherwise traveling via virtual edges will not be
         // the same as taking the direct edge!
         double pOffset = 0;
@@ -271,7 +293,6 @@ public class BidirectionalRoutingTest {
         List<String> strictViolations = new ArrayList<>();
         for (int i = 0; i < numQueries; i++) {
             List<GHPoint> points = getRandomPoints(2, index, rnd);
-
             List<QueryResult> chQueryResults = findQueryResults(index, points);
             List<QueryResult> queryResults = findQueryResults(index, points);
 
@@ -281,19 +302,52 @@ public class BidirectionalRoutingTest {
             int source = queryResults.get(0).getClosestNode();
             int target = queryResults.get(1).getClosestNode();
 
-            Path refPath = new DijkstraBidirectionRef(queryGraph, weighting, traversalMode)
-                    .calcPath(source, target);
-            Path path = createAlgo(chQueryGraph)
-                    .calcPath(source, target);
-            strictViolations.addAll(comparePaths(refPath, path, source, target));
+            Path refPath = new DijkstraBidirectionRef(queryGraph, weighting, traversalMode).calcPath(source, target);
+            Path path = createAlgo(chQueryGraph).calcPath(source, target);
+            strictViolations.addAll(comparePaths(refPath, path, source, target, seed));
         }
         // we do not do a strict check because there can be ambiguity, for example when there are zero weight loops.
         // however, when there are too many deviations we fail
         if (strictViolations.size() > Math.max(1, 0.20 * numQueries)) {
-            fail("Too many strict violations: " + strictViolations.size() + " / " + numQueries);
+            fail("Too many strict violations: " + strictViolations.size() + " / " + numQueries + ", seed: " + seed);
         }
     }
 
+    @Test
+    public void fail1() {
+        run(39457616822163L);
+    }
+
+    @Test
+    public void fail2() {
+        run(39386680060285L);
+    }
+
+    @Test
+    public void fail3() {
+        runWithQueryGraph(39361165106748L);
+    }
+
+    @Test
+    public void fail4() {
+        run(39316239491387L);
+    }
+
+    @Test
+    public void fail5() {
+        run(39449878563251L);
+    }
+
+    @Test
+    public void fail6() {
+        run(39315090735050L);
+    }
+
+    @Test
+    public void fail7() { // fails with CarFlagEncoder
+        run(337586249813919L);
+    }
+
     private List<GHPoint> getRandomPoints(int numPoints, LocationIndex index, Random rnd) {
         List<GHPoint> points = new ArrayList<>(numPoints);
         BBox bounds = graph.getBounds();
@@ -320,14 +374,15 @@ public class BidirectionalRoutingTest {
         return result;
     }
 
-    private List<String> comparePaths(Path refPath, Path path, int source, int target) {
+    private List<String> comparePaths(Path refPath, Path path, int source, int target, long seed) {
         List<String> strictViolations = new ArrayList<>();
         double refWeight = refPath.getWeight();
         double weight = path.getWeight();
         if (Math.abs(refWeight - weight) > 1.e-2) {
             System.out.println("expected: " + refPath.calcNodes());
             System.out.println("given:    " + path.calcNodes());
-            fail("wrong weight: " + source + "->" + target + ", expected: " + refWeight + ", given: " + weight);
+            System.out.println("seed: " + seed);
+            fail("wrong weight: " + source + "->" + target + "\nexpected: " + refWeight + "\ngiven:    " + weight + "\nseed: " + seed);
         }
         if (Math.abs(path.getDistance() - refPath.getDistance()) > 1.e-1) {
             strictViolations.add("wrong distance " + source + "->" + target + ", expected: " + refPath.getDistance() + ", given: " + path.getDistance());
diff --git a/reader-osm/src/test/java/com/graphhopper/routing/RoutingAlgorithmWithOSMIT.java b/reader-osm/src/test/java/com/graphhopper/routing/RoutingAlgorithmWithOSMIT.java
index 3d59c5410..d3e600d7e 100644
--- a/reader-osm/src/test/java/com/graphhopper/routing/RoutingAlgorithmWithOSMIT.java
+++ b/reader-osm/src/test/java/com/graphhopper/routing/RoutingAlgorithmWithOSMIT.java
@@ -324,20 +324,19 @@ public class RoutingAlgorithmWithOSMIT {
         assertEquals(testCollector.toString(), 0, testCollector.errors.size());
     }
 
-    // TODO fix later, see #1525, #1531
-//    @Test
-//    public void testLandmarkBug() {
-//        List<OneRun> list = new ArrayList<>();
-//        OneRun run = new OneRun();
-//        run.add(50.016923, 11.514187, 0, 0);
-//        run.add(50.019129, 11.500325, 0, 0);
-//        run.add(50.023623, 11.56929, 7069, 178);
-//        list.add(run);
-//
-//        runAlgo(testCollector, DIR + "/north-bayreuth.osm.gz", "target/north-bayreuth-gh",
-//                list, "bike", true, "bike", "fastest", false);
-//        assertEquals(testCollector.toString(), 0, testCollector.errors.size());
-//    }
+    @Test
+    public void testLandmarkBug() {
+        List<OneRun> list = new ArrayList<>();
+        OneRun run = new OneRun();
+        run.add(50.016923, 11.514187, 0, 0);
+        run.add(50.019129, 11.500325, 0, 0);
+        run.add(50.023623, 11.56929, 7069, 178);
+        list.add(run);
+
+        runAlgo(testCollector, DIR + "/north-bayreuth.osm.gz", "target/north-bayreuth-gh",
+                list, "bike", true, "bike", "fastest", false);
+        assertEquals(testCollector.toString(), 0, testCollector.errors.size());
+    }
 
     @Test
     public void testBug1014() {
@@ -563,8 +562,8 @@ public class RoutingAlgorithmWithOSMIT {
             // avoid that path.getDistance is too different to path.getPoint.calcDistance
             hopper.setWayPointMaxDistance(0);
 
-            // always enable landmarks, add maximum information to reduce warnings
-            hopper.getLMFactoryDecorator().addWeighting(weightStr + "|maximum=60000").
+            // always enable landmarks
+            hopper.getLMFactoryDecorator().addWeighting(weightStr ).
                     setEnabled(true).setDisablingAllowed(true);
 
             if (withCH)