Adapting Dijkstra for Buffers and Unlimited Transfers

Andrii Rohovyi; Denys Katkalo; Toby Walsh

arxiv: 2603.11729 · v5 · pith:PQOSP4EQnew · submitted 2026-03-12 · 💻 cs.DS · cs.AI· cs.RO

Adapting Dijkstra for Buffers and Unlimited Transfers

Denys Katkalo , Andrii Rohovyi , Toby Walsh This is my paper

Pith reviewed 2026-05-25 06:29 UTC · model grok-4.3

classification 💻 cs.DS cs.AIcs.RO

keywords public transit routingDijkstra algorithmbuffer timesunlimited transferstime-dependent graphsRAPTORpath findingtransfer aware

0 comments

The pith

Transfer Aware Dijkstra correctly handles buffer times by scanning entire trip sequences and outperforms MR by more than 2x on real networks.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper revisits time-dependent Dijkstra for public transit routing with unlimited transfers and shows it can beat RAPTOR-based methods like MR when implemented carefully. Standard dominance filtering in TD-Dijkstra breaks down once stops impose buffer times, because it cannot tell apart passengers already on a vehicle from those who must wait to transfer. The fix is to replace edge-by-edge checks with full trip sequence scans inside Transfer Aware Dijkstra, which restores correctness without losing the speed advantage. Experiments confirm the new method produces optimal results on London and Switzerland data both with and without buffers while running more than twice as fast as MR.

Core claim

Time-Dependent Dijkstra outperforms MR on unlimited-transfer queries, yet its preprocessing filter of dominated connections is unsound under buffer times because it assumes any passenger can switch to a faster connection. Transfer Aware Dijkstra fixes the problem by scanning complete trip sequences rather than individual edges, thereby distinguishing seated passengers who need no buffer from transferring passengers who do, and this yields optimal paths with a measured speed-up greater than two times over MR on both London and Switzerland networks.

What carries the argument

Transfer Aware Dijkstra (TAD), which replaces single-edge dominance checks with scans over entire trip sequences to enforce buffer constraints correctly.

If this is right

Dijkstra-style algorithms become viable again for unlimited-transfer routing once buffer times are present.
Preprocessing that discards dominated connections must be replaced or augmented when buffer times appear at stops.
Full trip sequence inspection preserves the performance edge of connection-based methods over timetable-based ones.
The same optimality and speed-up hold on large real networks whether buffers are required or not.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Sequence scanning may extend to other constraints such as vehicle capacity or seat reservations that also depend on whether a passenger is already aboard.
The seated-versus-transferring distinction points to a broader need to revise dominance relations in any multi-criteria routing setting that mixes continuous and discrete waiting rules.
Re-examining other older graph algorithms that were set aside in favor of RAPTOR could uncover further practical gains under realistic passenger rules.

Load-bearing premise

Scanning entire trip sequences is sufficient to guarantee optimality and to separate seated passengers from transferring ones under buffer constraints.

What would settle it

A small transit network containing a superior path that requires switching to a faster connection after a buffer time, where TAD returns a suboptimal result while a correctly implemented edge-filtering method finds the better path.

read the original abstract

In recent years, RAPTOR based algorithms have been considered the state-of-the-art for path-finding with unlimited transfers without preprocessing. However, this status largely stems from the evolution of routing research, where Dijkstra-based solutions were superseded by timetable-based algorithms without a systematic comparison. In this work, we revisit classical Dijkstra-based approaches for public transit routing with unlimited transfers and demonstrate that Time-Dependent Dijkstra (TD-Dijkstra) outperforms MR. However, efficient TD-Dijkstra implementations rely on filtering dominated connections during preprocessing, which assumes passengers can always switch to a faster connection. We show that this filtering is unsound when stops have buffer times, as it cannot distinguish between seated passengers who may continue without waiting and transferring passengers who must respect the buffer. To address this limitation, we introduce Transfer Aware Dijkstra (TAD), a modification that scans entire trip sequences rather than individual edges, correctly handling buffer times while maintaining performance advantages over MR. Our experiments on London and Switzerland networks show that we can achieve a greater than two time speed-up over MR while producing optimal results on both networks with and without buffer times.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

TAD fixes the buffer-time soundness gap in TD-Dijkstra by scanning full trip sequences and backs the fix with speedups on London and Switzerland data.

read the letter

The core advance is a concrete fix for an unsound filtering step that standard TD-Dijkstra uses. When stops impose buffer times, edge-by-edge dominance checks cannot tell seated passengers (who keep going without waiting) from transferring ones (who must respect the buffer). TAD replaces that check with a scan over entire trip sequences, which restores correctness while keeping the performance edge over MR. The experiments report more than 2x speedup on both networks, with and without buffers, and claim optimality in each case. That is a useful, targeted improvement for the transit-routing subfield where unlimited transfers matter and preprocessing is undesirable. The work also usefully revisits why RAPTOR-style methods became dominant without a head-to-head comparison against a properly adjusted Dijkstra baseline. The main limitation is that optimality is asserted from the two-network runs rather than from a proof or exhaustive small-instance check. The paper does not spell out why sequence-level dominance is guaranteed to preserve every better buffered path, so the result rests on the empirical claim that no counter-example appeared in London or Switzerland. That is acceptable for a practical paper but leaves the theoretical guarantee thinner than the abstract suggests. No circularity or invented parameters show up. This is a paper for people who implement or compare timetable algorithms on real transit data. It is narrow enough that most readers outside that niche will not need it, but the fix is clean enough and the experiments are direct enough that a serious editor should send it to referees rather than desk-reject. I would bring it to a reading group focused on routing or transit if the group already covers RAPTOR and TD-Dijkstra variants.

Referee Report

2 major / 2 minor

Summary. The paper claims that standard connection filtering in efficient Time-Dependent Dijkstra (TD-Dijkstra) implementations is unsound when buffer times are present at stops, because it cannot distinguish seated passengers (who may continue without buffer) from transferring passengers. It introduces Transfer Aware Dijkstra (TAD), which replaces per-edge filtering with per-trip-sequence scanning to correctly handle buffers while preserving performance. Experiments on the London and Switzerland networks are reported to show >2× speedup over MR while producing optimal results both with and without buffers.

Significance. If the optimality claim holds, the work revives and strengthens Dijkstra-based methods for unlimited-transfer public-transit routing, offering a practical alternative to RAPTOR/MR when buffer times must be respected. The use of two large real-world networks for both performance and optimality validation is a concrete strength.

major comments (2)

[§3] §3 (TAD description): the argument that full-trip-sequence scanning suffices to guarantee optimality (by correctly encoding the seated/transfer distinction and never discarding a better buffered path) is presented without a formal invariant, dominance proof, or reduction to a known correct algorithm; this is load-bearing for the central claim that TAD is both sound and faster than MR.
[§5] §5 (Experiments): the statement that TAD 'produces optimal results' on London and Switzerland is given without describing the verification procedure (e.g., comparison against an exhaustive or independently verified exact solver on the same instances), so the experimental support for the optimality claim cannot be assessed independently of the unproven scanning assumption.

minor comments (2)

The abstract and introduction could more explicitly contrast the new per-sequence dominance rule with the per-connection rule used in prior TD-Dijkstra work.
Figure captions and table headers should clarify whether 'optimal' refers to earliest arrival, number of transfers, or both.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and constructive feedback. We address the two major comments below. We agree that both points identify areas where the manuscript can be strengthened and will revise accordingly.

read point-by-point responses

Referee: [§3] §3 (TAD description): the argument that full-trip-sequence scanning suffices to guarantee optimality (by correctly encoding the seated/transfer distinction and never discarding a better buffered path) is presented without a formal invariant, dominance proof, or reduction to a known correct algorithm; this is load-bearing for the central claim that TAD is both sound and faster than MR.

Authors: We acknowledge that §3 presents the correctness argument for trip-sequence scanning informally, relying on the observation that scanning entire sequences correctly distinguishes seated passengers (who may continue without buffer) from transfers (who must respect buffers) and avoids discarding superior buffered paths. While this reasoning underpins the claim that TAD is sound, we agree a formal invariant, dominance relation, or reduction to standard TD-Dijkstra would make the argument rigorous. In the revised version we will add a formal proof of optimality for TAD. revision: yes
Referee: [§5] §5 (Experiments): the statement that TAD 'produces optimal results' on London and Switzerland is given without describing the verification procedure (e.g., comparison against an exhaustive or independently verified exact solver on the same instances), so the experimental support for the optimality claim cannot be assessed independently of the unproven scanning assumption.

Authors: We agree that §5 should explicitly describe how optimality was verified. Our experiments compared TAD arrival times and paths against those produced by MR (a known optimal algorithm) on identical query sets for both networks, with and without buffers; we will expand the section to detail this comparison procedure, the instance sizes used, and any additional checks performed on smaller subnetworks. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithmic adaptation validated on external networks

full rationale

The paper introduces Transfer Aware Dijkstra (TAD) as a modification to TD-Dijkstra that scans full trip sequences to handle buffer times correctly, then reports experimental speedups and optimality on London and Switzerland networks. No load-bearing step reduces a claimed result to a fitted parameter, self-definition, or self-citation chain; the central claims rest on direct comparison against MR and standard TD-Dijkstra on independent real-world data rather than any internal renaming or construction that forces the outcome.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters, invented entities, or non-standard axioms are introduced; the work relies on standard graph search assumptions and domain knowledge of transit networks.

axioms (1)

standard math Standard assumptions of correctness for shortest-path algorithms on time-dependent graphs with FIFO properties.
The paper extends Dijkstra without proving new mathematical properties beyond the described modification.

pith-pipeline@v0.9.0 · 5726 in / 1168 out tokens · 29557 ms · 2026-05-25T06:29:55.820822+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Early Pruning for Public Transport Routing
cs.DS 2026-03 conditional novelty 7.0

Early Pruning accelerates RAPTOR-based public transport routing by up to 57% via pre-sorting transfers by duration and pruning longer ones that cannot improve arrival times, while preserving Pareto optimality when ext...
Early Pruning for Public Transport Routing
cs.DS 2026-03 conditional novelty 6.0

Early Pruning accelerates RAPTOR-based public transport routers by up to 57% on Switzerland and London networks via duration-sorted transfer pruning while preserving Pareto optimality under monotonic criteria.