GraphHopper.com | Forum | GitHub | Maps | Blog

Turn costs with CHs - current status?


#1

Hi, I was wondering what the current status of Turn Costs (not restrictions but preferring routes with less turns) is. I read through https://github.com/graphhopper/graphhopper/issues?utf8=✓&q=turn%20cost%20 but couldn’t get a clue - so I guess it is not supported, yet? (Or only without CHs?)

Jan


#2

Turn costs and turn restrictions are handled identically. The status is still in this incomplete PR

For fast routing with turn costs or turn restrictions we recommend the new hybrid mode.


#3

Hey Peter,

I was dealing with other issues first, coming back to this rather old post:
If I switch to hybrid mode I have to accept that the Euope/Asia/Africa network gets disconnected correct? Or is it “solvable” by more RAM (if yes, what would that mean for a world graph) ?

Thanks,

Jan


#4

Yes. And yes, this would be solveable via more RAM. Instead of 6-10GB per profile you’ll have to plan for at least 2x of the original size IMO and also the speed could be slower (or you would have to further increase RAM usage). To save a bit RAM we can implement this optimization.


#5

Thanks, that helps to get an Idea. So if the base graph is around 20GB that would be an additional 40GB per profile or more.

I tried to understand the current turn cost implementation. So far I found:

Here I can store turn costs between two edges - it looks like this implementation is made for for sparse turn restrictions? Less efficient for turn restrictions for all edges and all tower nodes, Needed space is roughly 10GB for a full graph 4-byte * 4 ints * 3 edges per tower node * number of nodes?

Also https://github.com/graphhopper/graphhopper/blob/0a2ae97c087d8152b78430885fd52cc427b5b6c7/core/src/main/java/com/graphhopper/routing/util/AbstractFlagEncoder.java contains turn cost storing code.

What I was looking for is the place where you have two edges and calculate the turn cost between them, i.e. depending on the angle and orientation. Where would that place be?

Thanks,

Jan


#6

It is not optimized yet, yes.

What I was looking for is the place where you have two edges and calculate the turn cost between them, i.e. depending on the angle and orientation. Where would that place be?

Currently we do not do this, just turn restrictions via OSM relations. But it works according to some users and our tests, find usages of “addTurnInfo” -> EdgeBasedRoutingAlgorithmTest


#7

I think my estimation was not correct (cc @boldtrn) :

Based on the log of my latest import:

details:edges:230 649 596(7919MB), nodes:178 082 355(2718MB), name:(458MB), geo:1 859 653 157(7095MB), bounds:-180.0,180.0,-79.81499965820461,83.66130796062889,-987.7899780273438,8800.7802734375

I would estimate that the tower node cardinality is on average “somewhere between 3 and 4”. For a regular 4-way intersection we have to save 8 turn cost entries, so the size of the TurnCost table would be:

(3 * int + 1 * byte) * 8 entries * nodes = (3 * 4 + 1) * 8 * 180,000,000 ~= 18GB

In practise this will be less. Also, the full byte wouldn’t be necessary to store cost levels but I assume this is the minimal size we have to deal with.


#8

Thanks for the update @jankomoot and thanks for the ping.

Yes probably the cardinality is somewhere between 3-4 for tracks, paths, etc. I would assume it might be a bit lower for regular streets, as we see a lot of cuts for different road rules (max speed change, etc.), but I think this is not common for tracks and paths.

Cheers,
Robin


#9

fyi: we now have a useable solution of CH+turn costs here: https://github.com/graphhopper/graphhopper/pull/1247 Import is still a lot slower and query time also a bit but the end result is correct and it already works for Germany-wide and potentially bigger areas.