ScheduleSlack

Schedule Slack

Upon arriving at a station, whether transferring or boarding for the first time, if we find and take the very next departure we may end up with zero-tolerance transfers, where the user is told to alight from one vehicle and board another at the exact same minute or second.

The notion of requiring a bit of time to pass before boarding has been referred to as "schedule slack" or "minimum transfer time", and seems relatively simple to implement, but we run into conflicts in two places: back-optimization and timed (i.e. synchronized) transfers.

1. back-optimization

Say we insert some additional wait time (either based on a transfers.txt-derived table or a default minimum over and above walk time from one stop to another) before searching for the next vehicle departure, to avoid instantaneous transfers where the user is told to board the second vehicle within seconds of alighting from the first.

This "schedule slack" is applied at board edges in depart-after searches, and at alight edges in arrive-by searches, because we need to do it at a point in the search where we know which two stops are involved in the transfer, so as to check against the transfer table.

When you re-traverse all the edges backward to optimize, you will always fail to board the last transit leg because some "schedule slack" is inserted when its alight edge (the first alight edge) is encountered, where it was not inserted the forward search. By advancing the clock a bit at the end of the search, we were able to arrive at that alight edge at the right time to board the final transit leg.

However, this amounts to having a transit specific kludge in what is supposed to be generalized routing code, and the extra time offset also complicates simply reversing the path rather than optimizing it.

One apparent solution is to insert the slack time only on board edges, independent of the traversal direction. Another is to insert the same amount of 'slack' at both board and alight time, in both search directions. Both of these approaches bring us to the second problem:

2. timed (synchronized) transfers

"Timed transfers" is the GTFS term for what might also be called "synchronized transfers". This is where vehicles at one stop are guaranteed to wait for passengers from another.

If timed transfers are implemented as zero-second transfer table entries for certain stop pairs, the standard minimum transfer slack must be inserted when the search arrives at the second station in the pair, so that it can be skipped as needed for timed transfer station pairs.

Potential solution:

If timed transfers are implemented as special edges that connect arrival and departure nodes, bypassing stops, pre-board edges (where transfer slack is added in) etc. then we can implement default schedule slack however we like, without compromising timed transfers.

In order to also assure that both GraphPath reversing and optimizing work, schedule slack could then either be applied only on board edges (independent of search direction) or equally on board and alight edges, in both search directions. The advantage of the latter is that it will provide some slack in both the first and the last walk legs of the trip (only if transit is used), whether or not the resulting itinerary is optimized, and the amount of slack will be proportional to the number of vehicles involved in the boarding event (twice as much for transfers as for initial or final boards/alights).

The latter is the solution that has been implemented in this commit.

This implementation has the following characteristics: There is always at least minTransferTime seconds between alighting any vehicle and boarding another, except for timed (synchronized) transfers, which are represented with edges bypassing the street network entirely. GTFS timetable.txt (via the TransferTable) can only increase the minTransferTime specfied in the TraverseOptions.

Time precision

Another issue we have encountered related to back-optimization is the precision with which time is represented in states (milliseconds) and timetables (seconds). This can cause problems when a date/time is not provided in the request, and the system time is used.

The fractional part of the millisecond-precision system time propagates forward all the way to the end of the search. During reverse-optimization, that fractional part is rounded off when searching for an arrival time in PatternAlight.traverse, causing the correct trip to be missed by less than one second.

The State constructor now rounds fractional seconds toward zero (to the nearest second), which should avoid these missed trips. However, this bug points out an implementation detail we are likely to encounter again in future bugs.