Route Calculation - Performance Optimisation using Epsilon

Open Source Routing Engine
1

Hi,

I was wondering how to use the epsilon optimisation discussed here: https://github.com/graphhopper/graphhopper/issues/506

I am using the motorcycle profile and the curvature weighting. I did a quick speed comparison between bidir dijkstra and bidir astar using epsilon. The bidir astar took actuall longer. Here is a shortened Log:

point=53.550341%2C10.000654&point=48.363822%2C10.686649&vehicle=motorcycle&weighting=curvature&algorithm=astarbi&epsilon=1.5 took:25.673935, astarbi, curvature, motorcycle, distance: 740691.8320022689, time:581min, points:9546, debug - idLookup:0.004571758s, algoInit:0.1865954s, astarbi-routing:25.415829s, extract time:0.015294029, simplify (13234->9546)
point=53.543764%2C10.009913&point=48.363822%2C10.686649&vehicle=motorcycle&weighting=curvature&algorithm=dijkstrabi&epsilon=1.5  took:22.49385, dijkstrabi, curvature, motorcycle, distance: 740324.632848138, time:581min, points:9537, debug - idLookup:0.004589747s, algoInit:1.49673E-4s, dijkstrabi-routing:22.461428s, extract time:0.001995847, simplify (13216->9537)

I tried with different routes and also changing the minValue heuristic of astar (because the theoretical minimum of the curvature weighting will mostly happen in rather unrealistic cases). The dijkstrabi is still faster in my experiments (about 20%, depends on the route).

What could be done about this? Am I doing something wrong?

BTW: I just started to think if it may be possible to extend CH to the curvature routing?

2

Hi,

indeed the minValue could be the reason why A* is slower. You can find out via looking at the visited nodes in the JSON.

Also compare both response times for the ‘pure fastest’ weighting instead.

BTW: bidir A* with CH is slower (to be investigated but probably due to the distance calculation overhead and only few nodes)

Regarding your BTW: what do you mean here? Any weighting should work with CH without doing anything special.

4

Hi Peter,

Thanks for the above route Dijkstra visits 6182868 nodes. Astar visits 5799248 nodes. Not much better, but Astar has the heuristically overhead.

Astar is about 20% faster when using the fastest weighting.

Really? I thought this would be only available for the fastest weighting. I tried to enable it in the properties file like: prepare.chWeighting=fastest which produced an exception when using it with the curvature weighting. When I set it to prepare.chWeighting=curvature nothing happens. I can route, but there is no real speed difference.

5

This also looks like the minValue for this weighting is not that good and leads to more nodes visited. But when you accept heuristic solutions the A* results should have a higher quality so you should be able to increase the epsilon value to higher values compared to bidir Dijkstra. (BTW: 25s seems to be a lot for just 700km air distance)

Really? I thought this would be only available for the fastest weighting.

It should work out of the box for all weighting, yes.

I tried to enable it in the properties file like: prepare.chWeighting=fastest which
produced an exception when using it with the curvature weighting.

This is expected. What exception in detail do you get?

When I set it to prepare.chWeighting=curvature nothing happens. I can route,
but there is no real speed difference.

Hmmh, it should be a lot faster :slight_smile:
Do you see the preparation done after the import and actual shortcuts created? (Did you remove the GH folder before?) And what is the log message you see?

6

Thanks, I figured it out. In the GraphHopper.java we do: chEnabled = "fastest".equals(tmpCHWeighting) || "shortest".equals(tmpCHWeighting); I had to extend that. Now my routing is blazingly fast, but I cannot change anything in the weighting anymore, like increase bendiness impact, right? So I thought I’d just create two Weightings and run CH on both. Is this possible without major code changes?

I’ve seen this test, so it seems to be possible. But I guess this would mean several changes in the current code, right?

ERROR com.graphhopper.http.GHErrorHandler - No weighting found for request

Edit:
Would it be at least possible to do a fallback to a different weighting, that does not use CH?

7

Ah, yes. This needs an improvement.

but I cannot change anything in the weighting anymore

Yes, you have to make sure that nothing changes.

So I thought I’d just create two Weightings and run CH on both. Is this possible without major code changes?

Yes, two or more weightings are supported since 0.5

But I guess this would mean several changes in the current code, right?

Why do you think so? Currently what works out of the box are multiple vehicles with the same weighting, but same vehicle with multiple weightings should work. If not, we should make it working and it should not be hard.

Yes, this is already possible but not yet with the GraphHopper class. Again: we should make this possible&easy and it should not take too much effort.

8

Currently we get a string from the properties file. This string is set it as CHWeighting:

    /**
     * Enables the use of contraction hierarchies to reduce query times. Enabled by default.
     * <p>
     *
     * @param weighting can be "fastest", "shortest" or your own weight-calculation type.
     */
    public GraphHopper setCHWeighting( String weighting )
    {
        ensureNotLoaded();
        chWeightingStr = weighting.toLowerCase();
        return this;
    }

Then we get this string and create the AlgoFactories for each vehicle:

    private void initCHAlgoFactories()
    {
        if (algoFactories.isEmpty())
            for (FlagEncoder encoder : encodingManager.fetchEdgeEncoders())
            {
                Weighting weighting = createWeighting(new WeightingMap(chWeightingStr), encoder);
                algoFactories.put(weighting, null);
            }
    }

Probably this implies a lot more changes. Therefore, I thought it is not easily possible.

Definitely! :slightly_smiling:

9

That this requires indeed a substantial change - in the sense of a breaking Java API - but moving from one weighting to multiple should be relatively easy.

Here another loop over the weightingList would be necessary.

10

I created PRs for both features. Thanks :slightly_smiling:

1 Like