Strange routes with very small custom weights

Developers
1

Hi,

I have a custom weighting and I’m seeing some sub-optimal routes being generated when very small weights are used. Whilst troubleshooting this, I’ve found that the sub-optimal routes occur when all edges are assigned a custom weight of 0.03125. If I use a slightly larger weight at 0.05, the problem vanishes.

(Obviously this is a contrived scenario and in reality not all edges have the same weight. But in this case there were lots of edges near one another with the same very small weight, and that’s how I noticed this issue).

For example (on the left is the sub-optimal route, on the right is the optimal one. Only difference is the weights of 0.03125 vs 0.05):

gh-weight-issue
gh-weight-issue2551×1316 430 KB

I can reproduce this reliably using GH 4.0 and the default foot profile. I’m not using CH or LM.

A minimal example of my custom weighting that can reproduce this is as follows:

public class MyWeightingFactory implements WeightingFactory {

    public Weighting createWeighting(Profile profile, PMap requestHints, boolean disableTurnCosts) {
        PMap hints = new PMap();
        hints.putAll(profile.getHints());
        hints.putAll(requestHints);

        FlagEncoder encoder = encodingManager.getEncoder(profile.getVehicle());
        TurnCostProvider turnCostProvider = NO_TURN_COST_PROVIDER;

        Weighting parentWeighting = new PriorityWeighting(encoder, hints, turnCostProvider);
        Weighting myWeighting = new MyWeighting(parentWeighting);
        return myWeighting;
    }
}

public class MyWeighting extends AbstractAdjustedWeighting {

    public double calcEdgeWeight(EdgeIteratorState edgeState, boolean reverse) {

        double superWeight = super.calcEdgeWeight(edgeState, reverse);

        // This triggers the issue
        return superWeight * 0.03125;

        // But this does not
        //return superWeight * 0.05;
    }
}

Any ideas? Thanks!

Update: I’ve found that the issue occurs with AStarBi, but not with DijkstraBi.

2

You need to update Weighting.getMinWeight with your formula too, otherwise the beeline heuristic (BeelineWeightApproximator) might return values where an optimal route can no longer be guaranteed.

1 Like
3

Thanks!! Will give this a try in the morning.

4

Why don’t you use the CustomWeighting? It is intended for these changes and we consider most of the challenges already and you would also be able to try and play around directly in the UI and you could easily apply CH or LM later if necessary.

If your use case does not work with the CustomWeighting - please let us know!

5

I’m not sure if I can… My edge weights can change on each request. For example, a user can express a greenery preference (scaling from 0-100%) and other preferences as well. Each of these is implemented as a different weighting. These weightings are all combined together with a “stacked weighting”.

These weightings generally use some pre-processing and custom storage too. For example, the green weighting uses a CSV of OSM way IDs and greenery index mappings, and imports that at startup. The “avoid repetition weighting” uses a IntSet of edges visited on previous legs to work out if we should apply a penalty to visiting the same edge again.

Is something like that possible with CustomWeighting?

I am switching to use LM (at last), and it looks like that’s going to have a sizeable performance improvement. In fact, I have one quick question regarding LM: I recall from reading the GH blog post when LM/hybrid mode was first introduced that if you’re using custom weightings with LM, then these must always increase and never decrease. Is this still the case?

It seems to work with my decreasing weights, at least mostly.

6

Can you send the different parameters via a single custom_model? See graphhopper/docs/core/custom-models.md at master · graphhopper/graphhopper · GitHub

For example, the green weighting uses a CSV of OSM way IDs and greenery index mappings, and imports that at startup.

You can feed this data into your own encoded values and then (per-request) combine them with user preferences (in the example below I used the constant 0.87 to simulate some arbitrary user submitted value). But currently this would be only possible in the form of

{"priority":[
   { "if": "myenc_green_val * 0.87 < 0.5", 
     "multiply_by": 0.5 },
   { "else_if": "myenc_green_val * 0.87 < 0.7", 
     "multiply_by": 0.7 },
   { ... }]
}

I have a branch where you could directly use this custom_model on the server side

{"priority":[
   { "if": "true", 
     "multiply_by": "myenc_green_val" }]
}

And then the following custom_model on the client side via the user-submitted data (0.87):

{"priority":[
   { "if": "true", 
     "multiply_by": 0.87 }]
}

This results in a combined weight of 0.87*myenc_green_val for the priority.

The “avoid repetition weighting” uses a IntSet of edges visited on previous legs to work out if we should apply a penalty to visiting the same edge again.

This is indeed not possible with CustomWeighting. For which use case are you using this, i.e. what do you mean with repetition? Alternative routes?

I am switching to use LM (at last), and it looks like that’s going to have a sizeable performance improvement. In fact, I have one quick question regarding LM: I recall from reading the GH blog post when LM/hybrid mode was first introduced that if you’re using custom weightings with LM, then these must always increase and never decrease. Is this still the case?

Yes, it is a limitation of LM that in order to still use the pre-calculated weights the weight per edge must only increase (i.e. the priority of the custom_model must not be larger than 1 as the priority is inverse proportional to the weight)

But usually you can still make it working via negating the case i.e. instead of:

"priority": [{ "if": "TOLL != YES", "multiply_by": 2 }]

you do:

"priority": [{ "if": "TOLL == YES", "multiply_by": 0.5 }]

(as 1/2=0.5 )

7

Can you send the different parameters via a single custom_model?

Thanks for the detailed explanation! So I can encode my custom values (e.g. greenery, or slope), and then use those in the model. Yes, I think that would work for almost all the preferences. Very cool feature.

This is indeed not possible with CustomWeighting. For which use case are you using this, i.e. what do you mean with repetition? Alternative routes?

The use case for the ‘avoid repetition’ weighting is this: Often runners want to run from A → B → A, but they don’t want to run the same path on the return leg (B->A). I.e. they want to make it into a loop, rather than an out-and-back route. The ‘avoid repetition’ achieves this. For each leg that’s calculated, the set of visited edges is added to the AvoidRepetitionWeighting’s ‘seen edges’ set, and then this is used in subsequent legs to apply a penalty if that edge has already been used on a previous leg.

I guess I could perhaps achieve the same thing by asking for alternative routes and picking an alternative if the first route has already been used - right?

Yes, it is a limitation of LM that in order to still use the pre-calculated weights the weight per edge must only increase (i.e. the priority of the custom_model must not be larger than 1 as the priority is inverse proportional to the weight)

To be clear, given that I’m not using a cutom_model right now, I should make sure that my calcEdgeWeight method always returns super.calcEdgeWeight(edgeState, reverse) * n, where n >= 1 if I want it to work correctly with LM - correct?

Thanks again!

8

Ok, I see. Will think about if we can/should integrate such a feature.

I guess I could perhaps achieve the same thing by asking for alternative routes and picking an alternative if the first route has already been used - right?

Yes, that would be the only workaround I could think about at the moment.

I should make sure that my calcEdgeWeight method always returns super.calcEdgeWeight(edgeState, reverse) * n, where n >= 1 if I want it to work correctly with LM - correct?

Yes (with n ∈ R)

1 Like
9

We do this for the round trip routing, too:

In principle, we could use the edge IDs of one routing request to setup a custom model for another routing request. So we would have to increase the priority for certain edge IDs, or similar for some kind of area that covers the first route. Using edge (or OSM Way) IDs can be a bit harmful, because they will change over time.

1 Like
10

Thanks again both. Just wanted to confirm that implementing Weighting.getMinWeight resolved the issue with A*.

1 Like