Forced Heading in CH

Hi,

I have been working on customizing Graphhopper for the past 6 months or so. My implementations include creating graphs from our own databases, creating custom flag encoders, storing additional properties in edges to be returned in the response of the routing request, creating routing response having routes with multiple weightings(shortest, fastest combined in one response), and other similar tweaks to meet our requirements. All this has been running very smoothly on the server using flexibility mode (because heading and alternative routes were required).

We recently moved to offline routing on android and now the calculation of response takes very long. A benchmark route we’re using is between two points separated by about 1500 km having a lot of alternative routes. The route calculation takes about 140-160 seconds on a phone with a good processor and RAM; which is not good at all. I tried using the recently implemented Hybrid mode (LM) but the speed didn’t improve much. Then I tried enabling CH and the same response comes within 1-2 seconds. However, heading parameter is required and CH mode does not fully have that. So I tried enabling forced CH heading and tried to fix the issues coming in that.

The issue I faced in doing so was that the heading parameter was first used in getting to the closest non-virtual node. But after that, the heading was not considered in getting the best path because the weights are pre-stored in the shortcuts file from the starting non-virtual node to the ending non-virtual node. The problem is shown in the two cases shown in figures 1 and 2 (at the end of this post).

As a workaround, I included an additional step in DijkstraBidirectionRef class right before the condition

if (newWeight < bestPath.getWeight())

is checked. What i did was that I added a function in Path4CH class which gets the nodes of the unfavoured edges from the routing graph, unpacks the shortcuts and checks if any edge in the unpacked shortcut has any of the unfavoured edges’ nodes. If true, I added a large constant to the weight of that specific route hence the condition above gets false and this shortcut route isn’t considered as the best. This solved the heading problem in a number of cases as shown in figures 3 and 4 (at the end of this post).

However, it is still failing in some cases with the same initial problem as shown in figure 5 (at the end of this post).

Also, I pulled the latest code and the updates to the Path class are causing troubles. The returned path in this problematic route has an edge from node 75367 to node 87429 and this snippet of code throws the exception:

int prevEdge = -1;
EdgeIterator flagIter = crossingExplorer.setBaseNode(baseNode);
while (flagIter.next()) {
    if (flagIter.getAdjNode() == prevNode || flagIter.getBaseNode() == prevNode)
        prevEdge = flagIter.getEdge();
    }
    if (prevEdge == -1) {
        throw new IllegalStateException("Couldn't find the edges for " + prevNode + "-" + baseNode + "-" + adjNode);
    }

ERROR com.graphhopper.http.GHErrorHandler - Couldn’t find the edges for 75367-87429-107892!

This might be because the graph does not have the virtual nodes and edges and hence the connection between 75367 and 87429 cannot be found. Because upon debugging I checked the flagIter object and saw that it has the edges [78373 87429-107892], [52780 87429-87430], and [87429->1092726] (which is a virtual edge between 87429 and 75367) and no direct connection from node 87429 to node 75367.

I hope i have elaborated enough. I wanted to ask is there any work being done on headings in CH? Or is there anything I’m missing? Thankyou.

Regards,
Asjad

Figures

All this has been running very smoothly on the server using flexibility mode

Nice to hear this :slight_smile: !

It should be roughly 10 times faster.

So I tried enabling forced CH heading and tried to fix the issues coming in that.

This is not a practical issue. It is a theoretical limitation if you require non-heuristic routes.

Also, I pulled the latest code and the updates to the Path class are causing troubles.

See the related issue, this was a serious bug: https://github.com/graphhopper/graphhopper/issues/991 also related is probably this issue: https://github.com/graphhopper/graphhopper/pull/1014 because the CH graph disconnects certain edges and so one can find node B from node A but not A from B for those nodes.

I wanted to ask is there any work being done on headings in CH?

No, we could only provide workarounds that would sometimes fail OR would have to implement a complete new procedure how CH is handled, which is very time consuming.