Turn costs with CHs - current status?

jankomoot · July 18, 2017, 3:11pm

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

karussell · July 18, 2017, 3:44pm

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.

jankomoot · September 15, 2017, 12:08pm

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

karussell · September 15, 2017, 12:28pm

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.

jankomoot · September 20, 2017, 4:08pm

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:

github.com

graphhopper/graphhopper/blob/0a2ae97c087d8152b78430885fd52cc427b5b6c7/core/src/main/java/com/graphhopper/storage/TurnCostExtension.java

/*
 *  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.storage;

import com.graphhopper.util.EdgeIterator;

This file has been truncated. show original

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

karussell · September 21, 2017, 8:25am

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

jankomoot · September 27, 2017, 9:08am

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.

boldtrn · September 27, 2017, 9:57am

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

karussell · May 29, 2018, 5:56pm

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.

PGWelch · March 18, 2019, 10:39pm

Hi! Have you got any stats on the number of shortcuts in the CH graph with and without turn costs enabled, for the latest release? i.e. do you have 2x roughly the shortcuts, or 10x or X?

The last mention I could find discussed in the PR on github was:

For just Berlin I get ~500K shortcuts compared to 84K for master…"

Thanks!

easbar · March 19, 2019, 8:00am

The number of shortcuts with turn costs enabled is about 4x higher than without. For Berlin it is more like 250k now. In terms of memory note also that for turn costs we store two more ints (2x4bytes) for each shortcut.

easbar · March 19, 2019, 8:35am

Also see this issue: https://github.com/graphhopper/graphhopper/issues/1565