Broken Routing for Loops on One-Way Streets

[MoKob]

Following up the research on https://github.com/Project-OSRM/osrm-backend/issues/1861, it seems like the routing on one-way streets is broken.

Given the simple set-up:

• a --> b
• b --> c
• c --> a

This would translate into an edge based graph (ab) -> (bc), (bc) -> (ca), (ca) -> (ab).

Starting at the end of the one-way street (ab) and going to the beginning, the query has to find a self-loop within the graph (ab) -> (bc) -> (ca) -> (ab), as both nodes map to the same segment (ab).

In the current system, this is partly handled by a special case here. This case works only partly though, as we cannot deduct all neighbours to a vertex in a CH.

If (ab) is contracted last, we cannot find any arcs for (ab) in the CH anymore. This results in the foremost mentioned query to fail. Due to the random nature of the contraction, this can result in random queries to fail, as long as a loop may be required (e.g. due to via points).

A fix for this problem could include self-loops within the graph for one-way streets. Instead of using the dedicated special case handling, we would have to check for self-loop arcs in the search.

[emiltin]

is all cucumber testing disable for os x? why not just disable the offending test, if you can't simply fix the problem yet?

[MoKob]

At the moment it looks like even all builds are disabled for OSX (https://github.com/Project-OSRM/osrm-backend/blob/develop/.travis.yml#L77).

Its not that I've disabled them, its that I found out about that today.

[danpat]

Here's the original ticket for this:

https://github.com/Project-OSRM/osrm-backend/issues/1778

[MoKob]

To document my findings so far. The problem goes even deeper than originally though.

The problem is that in OSRM a path from a node to itself can have non-zero length. These paths originate in the idea that every node represents a path in the original graph, combined with a turn at the end (edge-based graph). When searching, OSRM uses phantom nodes with offsets. Lets name the node we are searching from a. A phantom node contains a reference to a and an offset along the path, L. Now given s = (a,L1) and t = (a, L2), OSRM assumes that we can travel along a if L2 >= L1. In the search, we usually add a, -L1 and a,L2 to the heaps. When looking at a, the sum (L2 + -L1) is positive and we found a direct connection.

In most cases, this is obviously true. However, in the plugin architecture, some cases exist if we do not start at s directly but rather arrive at s with an offset O. In these cases, the heaps are initialise with a,O-L1 and a,L2. This results in L2 + O-L1 >= 0, even if L1 > L2`, enabling us to travel against the arcs direction.

This is an additional problem next to the requirement to include self-loops to find a path from (a,L2) to (a,L1) with L2 > L1 in the first place, in case the path has been contracted prior to a.

[MoKob]

The bug itself is fixed by now. A performance problem remains.

We have to check for self-loops at every node. These are only necessary if the node is a one way street, or for a--b and a--c--b if acb is shorter than ab. The problem here is that a--b translates into a single node in the routing graph and a--c--b can represent a route much longer than a single additional node.

To find out about this, we need to know about the distances in the edge-based-nodes themselves. Sadly, this is related to https://github.com/Project-OSRM/osrm-backend/issues/1857. We need to update them when traffic changes.

To prune many unnecessary self-loops and to reduce the search overhead, we have to write out these offsets and use them during the contraction phase.

In short: for every node, we need to know what distance it represents so to know when not to construct an external loop.

[TheMarex]

Pull request is merged.