Contraction Hierarchies with blocked edges

Hello, I want to build a CH graph for two countries. But I want to be able to ban travel across the border for some requests. Is there any way to do this?
The problem, as far as I understand, if you prohibit travel cross the border during CH preparation, then the road to the border will be considered as a dead end and will have a low priority, so we will not be able to route to the border when use bidirection algo.
And if you make the border crossing available when prepare CH, and then ban some edges which crossing the border when routing in runtime, it will still violate the hierarchy and routes within the country will be broken - it will choose the road towards the border, although it should be a low priority dead end.
Any idea how to make it?

Currently you could block it with a custom model that forbids access to this border area. (You could create this border area e.g. from a buffer around the country border with some other tool.)

Another possibility could be to use a preprocessing that blocks all edges where the one node is in one country and the adjacent node is in another country via some java code.

We plan to make this easier with a custom model where you could just specify something like { "if": "prev_country != country", "multiply_by":"0"} but this is currently not yet possible.

Hello, thanks for answer!
But unfortunatly the problem is not just to find border edges. It easy to block border crossing for simple algo - just not to accept border edges and I know border edge ids.
Problem exactly with CH. If we block border edges when prepare CH, then the road to the border will be considered as a dead end and will have a low priority, so we will not be able to route to the border when use bidirection algo, because two points in different countries and algo find the path upward from low priority roads to high, but the road throw the border have low priority and they skipped by algo.
If when prepare CH make border edges accesible, and after when run algo skip border edges and shortcuts with border edge, this will disrupt the hierarchy of roads and routes within the country will be broken.
As far as I understand)
Maybe it is possible to do something in the preparation of CH or solve this problem in some other way?

You always need to re-run the CH preparation after you have changed edge weights.

So, there is no, even theoretically, way to build one CH graph for two countries and forbid or not forbid crossing the border when calculate path and do not broke routes inside of country?

Do you want to forbid crossing the border or allow crossing the border?

If start and finish at the same country - forbid, if different countries - allow. At the same CH graph.

You probably mean the other way around?

I have two countries A and B merged together and the graph builded for this osm.pbf.
When build graph I save border edges so I know their ids.
When start and finish points in country “A” we should ban crossing the border. When start point in country A and finish point in country B we should accept cross-border routes.
In non-CH algo it is not a broblem - just skip border edges or not skip.
But with CH its not possible.
The goal is to have one CH for merged countries A and B and be able to ban crossing border or accept by start and finish points location for current request.
Or maybe two different CH for countries A and B but to be able to find route by CH algo from A country to B.
Maybe some ideas to achieve this?

I still do not understand your use case.

But if you want to block the border edges: block them and do the CH preparation afterwards. If you do not want that the border edges block, just do the CH preparation for country A and B but do it after you merged the two countries.

You can also create two profiles (with a CH preparation for every profile): one that allows the border crossing and one that forbids this.

The rule of thumb in most cases is: as soon as you change the graph you need to redo the CH preparation(s).

Start point and finish point at the same country and the correct route is:

We should not to crossing the border even it will be shortest or fastest route because on the ground people can’t travel throw borders without problems.

When finish point in other country:

We should cross the border.

To achieve this behaviour, now I forced to have:

  1. CH for country A.
  2. CH for country B.
  3. CH for merged country AB.

And I am trying to find the way when it will be single CH for merged AB, but with correct logic with crossing borders: crossinf borders when points in different countries, ban crossing when in single.

Another example, maybe more obvoius)
Wrong route if two points in the same country:

Correct route that should be if two points in the same country:

But if points in different countries, it will be correct route:

Ok I think I get it now. You want to avoid border crossings, unless they are absolutely required because the start and destinations are located in different countries. A common way to tackle such cases is to apply a large (but finite!) penalty for the border crossing edges (it sounds like you already have some code that finds them). The routing algorithm will then rather choose a route that does not cross the border, because it would be very costly. But if there is no other way it will eventually find the route that crosses the border. So in essence all you need to do is increase the weights of the border crossing edges (but do not set the weight to be infinite).

Yes, for non-CH it should works fine. But the problem with CH)
If we want to ban some border edges by weights, some shortcuts which cross the borders will have a giant weight. And then, when we will find the route inside the single country they will be ignored because of weight and final route will be not optimal. As I understand.

No, there might be some implications regarding performance, but otherwise CH should produce the exact same routes as non-CH, even when you use large weights for the border edges. Why do you think it does not work. Did you try it yet?

Yes, you were right, looks like it’s working)
Just added additional big weight for border edges and CH works fine now. And almost no effect at the speed.

1 Like