Audit car routing (especially turn restrictions)

[abyrd]

We have a whole series of issues from 2016 (five years ago) about the speed and details of car routing, with a lot of references specifically to turn restrictions: #87, #89, #155, #189. I am closing all these issues and consolidating them into this one new issue with the goal to perform an audit of logic specific to car routing and determine if there are indeed inefficiencies or design flaws that should be resolved.

[abyrd]

Coming back to this issue as I look at turn restrictions as something that could potentially handle barrier nodes. I'm seeing some things that require attention:

• A comment in canTurnFrom method says: "This is also coded in traverse, so change it both places if/when it gets changed." We do not want to have any duplicate code that needs to be kept in sync. On first inspection I don't actually see any duplicate code. This should be verified, and if we no longer need to factor it out then the comment should be changed/deleted.
• The canTurnFrom method replicates a list of turn restrictions and stores them in newly created hash maps in the result state. This seems potentially quite inefficient.
• There is also no mention in the comments on this method that it's not a pure function and modifies its parameters. The behavior should be changed, or the comments updated to warn about this behavior.

[abyrd]

Note also #806 reported more recently.

[ansoncfit]

I've had these on my reading list for a bit (also related to handling intersections with bike LTS); may be worth reviewing before we get underway:

• https://doi.org/10.1016/j.orl.2012.06.001
• https://doi.org/10.1023/A:1020853410145
• https://doi.org/10.1177/0361198118783109

[abyrd]

I was seeing some rather slow car routing times today and did some investigation. The specific case was a full Netherlands street graph, while performing single point analyses. For various reasons, the travel time limit is set to the maximum value of 120 minutes in this situation. It is not affected by maxCarTime, which only applies on transit access legs, nor by maxTripDurationMinutes, which in single point analyses only overwrites the TravelTimeSurfaceTask default value of 120 in special cases (fare-constrained multi-criteria routing).

Base case (no changes to code): Car routing single point from central Amsterdam takes 11.9 sec.
Sampling two such car searches with VisualVM, two threads each show about 14.5 sec of total CPU time. About 13.6 sec is in AnalysisWorkerController.handleSinglePoint. (The other 700 msec is spent in Body.serializeTo(). This is not really expected, but is a separate subject - is some spurious compression happening?)

Strikingly, only 3.5 sec of this 13.6 sec total is the initial car router. The vast majority (9.6 sec) is actually spent in keepRoutingOnFoot. Routing on foot is intended to be a tiny final step just in case some crucial street is pedestrian only (e.g. access to a train station), and in fact is not relevant at all in a pure car routing case where the destination cells can be selectively linked to car roads.

(A notable smaller 500 msec chunk is spent in linkedPointSet.eval, which seems to be mostly spent in StreetRouter.getStateAtEdge streams, which again is a separate subject but may be subject to optimizations).

There's a real question as to why keepRoutingOnFoot would do anything at all here. Almost all vertices should be already reached by car, and nearly every pedestrian edge traversal should be immediately rejected as no better than the existing car states. It may simply be that even though every one of these traversals fails, at this point in a 120 minute car search the search has covered the entire graph, meaning every single edge must be enqueued and traversed at least once (only to fail). This is definitely a potential problem for longer distance searches (as opposed to short access/egress searches). But even so, its not clear why these spurious traversals take several times longer than the car traversals. Just re-enqueueing all the states between car and foot routing takes 400 msec, but that's still only 2% of the total foot routing time. The rest of it (over 9 seconds) is really just normal queue and street traversal actions.

Checking the impact of co-dominant states (search branching primarily for turn restrictions): after the car routing, 330 edges have more than one state, of which 17 edges have more than 2 states. After the walk routing stage, this grows to 4800 edges with more than one state, of which 42 edges have more than 2 states. I am wondering why continuing on foot would ever cause the number of co-dominant states to increase. Something is suspicious there. Nonetheless, this is out of 8.6 million edges in this graph. The fact only 17 have more than 2 states highlights how infrequently all this multi-state machinery is used, to handle a few cases in an entire country. Other than use of multimaps for state storage, the logic is mostly just skipped in all but those 17 cases.

Independent of whether I change the enqueuing mechanism to only enqueue one best state at each edge:
CAR: States handled 4491706, edges traversed 10956259, total edges 8678416
Queue length before street routing 3634714
WALK: States handled 8477493, edges traversed 20891074, total edges 8678416

So in the walk phase, every edge in the graph is being traversed more than twice. In every search, the last traversal from many locations is useless. When the graph is totally explored, every final state will explore all its outgoing edges including some u-turns and they will all fail, just like these walk traversals. But for an unclear reason there are 2x more of them in the walk search.

On the disable-turn-restrictions branch I tried several simplifications including disabling multi-state storage and turn restrictions (25% speedup), no turn restrictions and no backtrack edges including legitimate u-turns (35% speedup) etc. but nothing comes close to the huge 76% speedup from just skipping the continueOnFoot phase.

I think historically what happened is that these street routing mechanisms were mostly examined in the context of transit access searches, which are always time-limited and absolutely require a check for final pedestrian access to transit stops. Pure car or pure bicycle searches without transit were seen as somewhat of a special case. But if these unnecessary walk checks are carrying over to non-transit searches run in large regional batches, perhaps 50-70% of the total computation is unnecessary.

Proposed fix

The simplest possible fix is to move the keepRoutingOnFoot call inside the if (request.hasTransit()) conditional below it. It will then only be applied on time-limited transit access legs where its impact is much smaller. That change already exists as commit cdd0f25on branchdisable-turn-restrictions`.

Additionally, we could consider applying the per-mode and global travel time limits even for direct (non-transit) street searches. Only in very specific cases do we actually want or need to analyze driving travel times out to 120 minutes.