pith. sign in

arxiv: 2604.16149 · v4 · pith:HLPEXUWKnew · submitted 2026-04-17 · 💻 cs.DS

Fast and Memory Efficient Multimodal Journey Planning with Delays

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

Pith reviewed 2026-05-19 16:53 UTC · model grok-4.3

classification 💻 cs.DS
keywords multimodal journey planningdelaysULTRACSARAPTORpublic transportearliest arrivalbicriteria optimization
0
0 comments X

The pith

Adapting ULTRA, CSA and RAPTOR for delays yields faster and more memory-efficient multimodal journey planning.

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

The paper extends recent adaptations of multimodal journey-planning algorithms to handle delays in public transport networks. It focuses on making these extensions more memory-efficient and faster while preserving or improving accuracy. The authors apply the improved approach to ULTRA and also adapt the same ideas to CSA and RAPTOR. In single-objective searches for earliest arrival time the new versions run between 1.9 and 4.2 times faster than previous delay-aware methods. The bicriteria versions deliver competitive speed with higher accuracy and scale more gracefully as the allowed delay buffer grows.

Core claim

By refining the graph representations and delay models used in ULTRA, CSA and RAPTOR, the authors obtain algorithms that compute earliest-arrival journeys and bicriteria trade-offs more quickly and with smaller memory footprints than existing delay-aware implementations, while reporting higher accuracy on the tested instances and better scaling with larger delay buffers.

What carries the argument

Refined adaptations of the ULTRA, CSA and RAPTOR frameworks that incorporate delay models and compact graph representations to support delay-aware multimodal queries.

If this is right

  • Single-objective earliest-arrival queries complete 1.9-4.2 times faster than prior delay-aware algorithms.
  • Bicriteria searches maintain competitive run times while returning more accurate results.
  • Query performance degrades less severely when the delay buffer Delta is increased.
  • Memory consumption drops compared with earlier adaptations of the same base algorithms.

Where Pith is reading between the lines

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

  • The reduced memory footprint could allow deployment of delay-aware planners directly on mobile devices or embedded systems.
  • The same refinement pattern might transfer to additional journey-planning algorithms or to related problems such as dynamic ride-sharing with uncertainty.
  • Improved scaling with larger delay buffers suggests the methods could remain practical in networks that experience frequent or widespread disruptions.

Load-bearing premise

The delay model and graph representations used in the adaptations of ULTRA, CSA, and RAPTOR are sufficient to maintain correctness and the claimed accuracy improvements on the evaluated instances.

What would settle it

Running the new implementations on a large real-world public-transport dataset with recorded actual delays and measuring whether the reported speedups, memory savings and accuracy gains still appear relative to the prior delay-aware baselines.

Figures

Figures reproduced from arXiv: 2604.16149 by Andrii Rohovyi, Denys Katkalo, Toby Walsh.

Figure 1
Figure 1. Figure 1: Projection π from event-level to stop-level shortcuts. (a) Trips T1, T2 serve stops s1, s2, s3 and trips T3, T4 serve stops s3, s4, s5. Six event-level shortcuts (dashed arrows) connect individual stop events across the two trip groups. (b) The projection merges all shortcuts between the same pair of stops into a single edge with the minimum travel time, yielding two stop-level shortcuts. The travel times … view at source ↗
read the original abstract

State-of-the-art multimodal journey-planning algorithms, such as ULTRA, have recently been adapted to account for delays. In this work, we extend this approach to be more memory-efficient, faster, and accurate. We also adapt this framework to other state-of-the-art algorithms, like CSA and RAPTOR. We demonstrate a speedup of 1.9-4.2x over existing algorithms in the single-objective search (earliest arrival time). In the bicriteria setting, we achieve competitive speedup results but greater accuracy. We also find that our method scales much better as the delay buffer Delta increases.

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.

Referee Report

2 major / 2 minor

Summary. The paper extends recent adaptations of ULTRA (and similarly CSA and RAPTOR) for handling delays in multimodal journey planning. It introduces memory-efficient data structures and query modifications that use a delay buffer Delta, claiming 1.9-4.2x speedups for single-objective earliest-arrival queries, competitive bicriteria performance with higher accuracy, and improved scaling as Delta grows.

Significance. If the adaptations preserve correctness and the reported speedups and accuracy gains are reproducible, the work would offer practical improvements for real-time multimodal routing under uncertainty, which is relevant for transit applications. The scaling behavior with Delta is a potentially useful empirical observation.

major comments (2)
  1. [§4] §4 (Algorithm Adaptations): The manuscript does not supply an explicit invariant or proof sketch showing that the modified graph representations and query procedures in the ULTRA/CSA/RAPTOR adaptations return journeys that remain feasible for every possible delay realization inside the buffer Delta. Without this, the claimed accuracy gains and speedups rest on an unverified assumption that the augmentation exactly captures the feasible set rather than approximating it.
  2. [§5.2] Experimental Evaluation (around Table 3 and §5.2): The abstract and results state concrete speedups (1.9-4.2x) and greater accuracy in the bicriteria case, yet the text provides no definition of the accuracy metric, no description of how ground-truth Pareto sets were obtained, and no statistical significance tests. This makes it impossible to assess whether the accuracy improvement is robust or an artifact of the chosen instances.
minor comments (2)
  1. [§3] Notation for the delay buffer Delta is introduced without a clear forward reference to its precise semantics in the query procedure; a small diagram or pseudocode snippet would improve readability.
  2. [§1] The paper should cite the original ULTRA paper and the prior delay-adaptation work explicitly in the introduction when stating the baseline.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. We address each major comment below and indicate where revisions will be made to improve clarity and completeness.

read point-by-point responses

  1. Referee: [§4] §4 (Algorithm Adaptations): The manuscript does not supply an explicit invariant or proof sketch showing that the modified graph representations and query procedures in the ULTRA/CSA/RAPTOR adaptations return journeys that remain feasible for every possible delay realization inside the buffer Delta. Without this, the claimed accuracy gains and speedups rest on an unverified assumption that the augmentation exactly captures the feasible set rather than approximating it.

    Authors: We agree that an explicit statement of the invariant would strengthen the presentation. The adaptations extend the delay-aware versions of ULTRA, CSA, and RAPTOR by augmenting the graph with a delay buffer Delta that conservatively bounds the maximum delay on each connection. The query procedures then propagate earliest-arrival labels while respecting this bound, ensuring that every returned journey remains feasible under any delay realization ≤ Delta and that no feasible journey is omitted. To address the concern directly, we will insert a short paragraph in §4 stating the invariant ('Any journey returned by the modified query is feasible for all delay values in [0, Delta]') together with a brief inductive proof sketch over the label-setting steps. This addition will make the correctness argument self-contained. revision: yes

  2. Referee: [§5.2] Experimental Evaluation (around Table 3 and §5.2): The abstract and results state concrete speedups (1.9-4.2x) and greater accuracy in the bicriteria case, yet the text provides no definition of the accuracy metric, no description of how ground-truth Pareto sets were obtained, and no statistical significance tests. This makes it impossible to assess whether the accuracy improvement is robust or an artifact of the chosen instances.

    Authors: We acknowledge the omission of explicit definitions. The accuracy metric is the fraction of journeys in the computed bicriteria Pareto set that exactly match journeys in the ground-truth Pareto set; ground-truth sets were generated by exhaustive enumeration of all delay realizations up to Delta using the unmodified base algorithms on the same instances. We will add a precise definition of the metric and a description of the ground-truth procedure in §5.2. The reported improvements were uniform across all networks and query batches; we did not perform formal statistical tests because the algorithms are deterministic and the effect sizes were large and consistent, but we will include a short note on observed variability and offer to add significance tests if the referee considers them necessary. revision: partial

Circularity Check

0 steps flagged

No circularity: empirical speedups and accuracy claims are measured outcomes on test instances

full rationale

The paper presents algorithmic adaptations of ULTRA, CSA, and RAPTOR to incorporate a delay buffer Delta, followed by empirical evaluation of runtime and solution quality on standard networks. Reported speedups (1.9-4.2x) and scaling behavior are stated as observed performance numbers rather than quantities derived from the paper's equations or fitted parameters. No self-definitional steps, fitted-input predictions, or load-bearing self-citations appear in the derivation chain; the central claims rest on external experimental validation instead of reducing to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard domain assumptions about how public-transport networks are modeled as time-dependent graphs and how delays are represented by a fixed buffer Delta; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Multimodal transport networks can be represented as graphs with time-dependent connections and a uniform delay buffer Delta that captures possible late arrivals.
    This modeling choice is inherited from the cited prior adaptations of ULTRA and is required for the efficiency claims to apply.

pith-pipeline@v0.9.0 · 5625 in / 1376 out tokens · 59869 ms · 2026-05-19T16:53:12.008826+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · 2 internal anchors

  1. [1]

    H. Bast, E. Carlsson, A. Eigenwillig, R. Geisberger, C. Harrelson, V . Raychev, and F. Viger. Fast routing in very large public transportation networks using transfer patterns. InESA 2010, volume 6346, page 290–301,

    work page 2010

  2. [2]

    doi: 10.1007/978-3-642-15775-2

    work page doi:10.1007/978-3-642-15775-2

  3. [3]

    Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Z ¨undorf

    doi: 10.1145/1671970.1671976. Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Z ¨undorf. UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution. InProceedings of the 27th Annual European Symposium on Algorithms (ESA’19), volume 144 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 14:1–14:16. Sc...

    work page doi:10.1145/1671970.1671976 2019

  4. [4]

    Gerth Stølting Brodal and Riko Jacob

    doi: 10.1137/1.9781611977929.8. Gerth Stølting Brodal and Riko Jacob. Time-dependent networks as models to achieve fast exact time-table queries. Electronic Notes in Theoretical Computer Science, 92:3–15,

    work page doi:10.1137/1.9781611977929.8

  5. [5]

    Electronic Notes in Theoretical Computer Science 92, 3–15

    doi: 10.1016/S1571-0661(05)80494-7. URL https://cs.au.dk/∼gerth/papers/atmos03.pdf. Proceedings of the 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS 2003). Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-Based Public Transit Routing. InProceedings of the 14th Meeting on Algorithm Engineering and Experiments ...

    work page doi:10.1016/s1571-0661(05)80494-7 2003

  6. [6]

    Round-Based Public Transit Routing,

    doi: 10.1137/ 1.9781611972924.12. URL https://doi.org/10.1137/1.9781611972924.12. Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato F. Werneck. Computing multimodal journeys in practice. InProceedings of the 12th International Symposium on Experimental Algorithms (SEA’13), volume 7933 ofLecture Notes in Computer Science (LNCS), pag...

    work page doi:10.1137/1.9781611972924.12

  7. [7]

    doi: 10.1007/978-3- 642-38527-8

    work page doi:10.1007/978-3-

  8. [8]

    First passage times for subordinate Brownian motions

    doi: 10.1287/trsc.1110.0401. Denys Katkalo, Andrii Rohovyi, and Toby Walsh. Adapting dijkstra for buffers and unlimited transfers.arXiv preprint arXiv:2603.11729,

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1287/trsc.1110.0401

  9. [9]

    Duc-Minh Phan and Laurent Viennot

    doi: 10.5555/2791188.2791192. Duc-Minh Phan and Laurent Viennot. Fast public transit routing with unrestricted walking through hub labeling.arXiv preprint arXiv:1906.08971,

    work page doi:10.5555/2791188.2791192 1906

  10. [10]

    Early Pruning for Public Transport Routing

    13 Andrii Rohovyi, Abdallah Abuaisha, and Toby Walsh. Early pruning for public transport routing.arXiv preprint arXiv:2603.12592,

    work page internal anchor Pith review Pith/arXiv arXiv

  11. [11]

    Public Transit Routing with Unrestricted Walking

    Dorothea Wagner and Tobias Z¨undorf. Public Transit Routing with Unrestricted Walking. In Gianlorenzo D’Angelo and Twan Dollevoet, editors,17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimiza- tion, and Systems (ATMOS 2017), volume 59 ofOpen Access Series in Informatics (OASIcs), pages 7:1–7:14, Dagstuhl, Germany,

    work page 2017

  12. [12]

    doi: 10.4230/OASIcs.ATMOS

    Schloss Dagstuhl – Leibniz-Zentrum f ¨ur Informatik. doi: 10.4230/OASIcs.ATMOS. 2017.7. Sascha Witt. Trip-based public transit routing. In Nikhil Bansal and Irene Finocchi, editors,Algorithms — ESA 2015, volume 9294 ofLecture Notes in Computer Science, pages 1025–1036. Springer,

    work page doi:10.4230/oasics.atmos 2017

  13. [13]

    doi: 10.1007/978-3-662-48350-3

    ISBN 978-3-662-48350-3. doi: 10.1007/978-3-662-48350-3

    work page doi:10.1007/978-3-662-48350-3

  14. [14]

    Trip-based public transit routing using condensed search trees

    Sascha Witt. Trip-based public transit routing using condensed search trees. In16th Workshop on Algorithmic Ap- proaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), volume 54 ofOpen Access Series in Informatics (OASIcs), pages 10:1–10:12, Dagstuhl, Germany,

    work page 2016

  15. [15]

    doi: 10.4230/OASIcs.ATMOS.2016.10

    Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik. doi: 10.4230/OASIcs.ATMOS.2016.10. URL https://drops.dagstuhl.de/opus/volltexte/2016/6534/. 14

    work page doi:10.4230/oasics.atmos.2016.10 2016