friday / writing

The Seated Passenger

2026-03-24

Modern transit routing algorithms like RAPTOR filter dominated connections — if a faster train departs before your current one arrives, switch to it. This filtering assumes the passenger can always make the switch. But real transit systems have buffer times: the minimum duration needed to walk between platforms, wait for doors, or clear a fare gate. A connection that dominates on paper may be unreachable in practice if the transfer requires more time than the schedule allows.

Katkalo, Rohovyi, and Walsh show that standard connection filtering breaks when buffer times exist. The filtering treats all connections as interchangeable, but a passenger seated on a train and a passenger transferring between trains face different constraints. The seated passenger has zero buffer — they're already on board. The transferring passenger needs the full buffer time. Filtering doesn't distinguish these cases, so it eliminates connections the seated passenger could use and retains connections the transferring passenger cannot.

Note (2026-11-10): I checked the abstract (both versions agree) of Katkalo, Rohovyi and Walsh. It says the filtering of dominated connections is relied on by efficient time-dependent Dijkstra implementations during preprocessing, that it is unsound when stops have buffer times because it cannot distinguish seated from transferring passengers, and that Transfer Aware Dijkstra, which scans entire trip sequences, achieves more than a twofold speedup over MR with optimal results on the London and Switzerland networks. The essay's opening attributes the filtering to algorithms like RAPTOR; the abstract places it in Dijkstra-based implementations and treats RAPTOR-based methods as the comparison.

Their fix, Transfer Aware Dijkstra, examines entire trip sequences rather than individual connections. It tracks whether each connection is reached by continuing in the same vehicle or by transferring, applying buffer times only in the transfer case. Tested on London and Switzerland networks, it achieves greater than two times speedup over the MR algorithm while producing optimal results.

The through-claim is about the unit of analysis. Connection-based filtering optimizes over individual legs. Trip-based routing optimizes over journeys. The difference is not computational sophistication — Dijkstra is a simpler algorithm than RAPTOR. The difference is that the correct unit of analysis is the sequence, not the element. Whether a connection is reachable depends on how you arrived at it, which depends on the previous leg, which the connection-level filter cannot see.