pith. sign in

arxiv: 1906.08971 · v1 · pith:4HLNRFULnew · submitted 2019-06-21 · 💻 cs.NI · cs.DS

Fast Public Transit Routing with Unrestricted Walking through Hub Labeling

Duc-Minh Phan , Laurent Viennot (GANG , IRIF , LINCS , UPD7) This is my paper

Pith reviewed 2026-05-25 18:38 UTC · model grok-4.3

classification 💻 cs.NI cs.DS
keywords public transit routinghub labelingunrestricted walkingRAPTORCSAjourney planningcontraction hierarchies
0
0 comments X

The pith

Hub labeling encodes all walking transfers between stops to answer public transit routing queries faster.

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

The paper shows how hub labeling can stand in for every possible walking path between stops so that existing transit algorithms keep working when walking is unrestricted. The same labeling plugs into both RAPTOR and CSA and produces clear speed gains over the contraction-hierarchy baseline on earliest-arrival, Pareto, and profile queries. A reader would care because most real trips mix riding and walking, yet prior methods either forbid walking or slow down when they allow it.

Core claim

Hub labels precomputed for foot travel let the algorithms treat any pair of stops as directly connected by walking without enumerating paths at query time. The labels integrate directly into the RAPTOR and CSA frameworks, preserving correctness for earliest arrival, multi-criteria Pareto sets, and full profile queries while cutting running time relative to contraction hierarchies on the same unrestricted-walking model.

What carries the argument

Hub labeling for foot transfers, which stores compact reachability information at each stop so that walking connections can be resolved in constant time during the main search.

If this is right

  • Earliest-arrival queries finish faster even when every stop pair may be linked by walking.
  • Pareto sets that trade arrival time, transfers, and walking time become practical to compute.
  • Profile queries that list all optimal journeys inside a time window run at interactive speeds.
  • Both the RAPTOR and CSA families inherit the same performance lift without separate redesign.

Where Pith is reading between the lines

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

  • Mobile journey planners could add unrestricted walking by default without extra latency.
  • Similar label structures might handle other slow modes such as cycling if distance oracles are available.
  • The preprocessing cost could become the new bottleneck once query time is no longer limiting.

Load-bearing premise

A hub labeling scheme exists that captures every valid walking transfer between stops without dropping journeys or using more memory than the network can store.

What would settle it

Run the hub-label version and a verified slow enumeration of all walking paths on the same city network and check whether every reported journey is identical and whether the reported speedups disappear.

read the original abstract

We propose a novel technique for answering routing queries in public transportation networks that allows unrestricted walking. We consider several types of queries: earliest arrival time, Pareto-optimal journeys regarding arrival time, number of transfers and walking time, and profile, i.e. finding all Pareto-optimal journeys regarding travel time and arrival time in a given time interval. Our techniques uses hub labeling to represent unlimited foot transfers and can be adapted to both classical algorithms RAPTOR and CSA. We obtain significant speedup compared to the state-of-the-art approach based on contraction hierarchies.

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 manuscript proposes using hub labeling (HL) to encode unrestricted walking transfers between stops in public transit networks. It adapts the approach to both RAPTOR and CSA, supporting earliest-arrival queries, multi-criteria Pareto queries (arrival time, transfers, walking time), and profile queries over a time interval. The central claim is that the resulting algorithms deliver significant query-time speedups relative to the contraction-hierarchy baseline while preserving correctness.

Significance. If the reported speedups and correctness arguments hold, the work supplies a practical route to handling unlimited foot transfers inside established transit algorithms without the preprocessing or query overhead of prior CH-based methods. The explicit integration into RAPTOR/CSA rounds and the experimental results on real networks constitute a concrete, falsifiable advance for multimodal journey planning.

major comments (2)
  1. [§4.2] §4.2 (RAPTOR-HL): the replacement of the walking phase by HL label lookups is described at a high level; it is not shown how the label intersection is performed inside the round-based structure while still guaranteeing that the earliest-arrival property is preserved when walking time is part of the multi-criteria Pareto set.
  2. [Table 2] Table 2 (query times): the reported speedups are given only as geometric means; without per-query or per-network variance and without an ablation that isolates the contribution of HL versus other engineering choices, it is difficult to assess whether the central claim of 'significant speedup' is robust across all query types.
minor comments (2)
  1. [§2] The notation for label size (bytes per stop) and the definition of 'unrestricted walking' should be stated once in §2 before being used in the algorithm descriptions.
  2. [Figure 3] Figure 3 caption does not indicate whether the plotted curves include walking time in the Pareto front or only transfer count; this affects interpretation of the multi-criteria results.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the recommendation of minor revision. We address each major comment below.

read point-by-point responses

  1. Referee: [§4.2] §4.2 (RAPTOR-HL): the replacement of the walking phase by HL label lookups is described at a high level; it is not shown how the label intersection is performed inside the round-based structure while still guaranteeing that the earliest-arrival property is preserved when walking time is part of the multi-criteria Pareto set.

    Authors: We agree that the description in §4.2 is at a high level. In the revised version we will expand the section to show the concrete label-intersection step inside each RAPTOR round, including how the earliest-arrival labels are merged with the current Pareto set while correctly accounting for walking time as a criterion. revision: yes

  2. Referee: [Table 2] Table 2 (query times): the reported speedups are given only as geometric means; without per-query or per-network variance and without an ablation that isolates the contribution of HL versus other engineering choices, it is difficult to assess whether the central claim of 'significant speedup' is robust across all query types.

    Authors: Geometric means are the conventional summary statistic for query-time speedups on heterogeneous query sets in this literature. We will add a short discussion of observed variance and, space permitting, a brief ablation isolating the HL component from other implementation choices. revision: partial

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents an algorithmic technique integrating existing hub labeling into RAPTOR and CSA for handling unrestricted walking transfers in transit networks. The derivation consists of replacing walking phases with label lookups and arguing correctness from the base algorithms' properties plus hub labeling guarantees; no equations, predictions, or uniqueness claims reduce by construction to fitted parameters or self-referential definitions. Experiments on real networks and comparisons to independent contraction-hierarchy baselines provide external validation, making the central claims self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces an algorithmic technique that relies on standard graph properties of hub labeling and existing transit algorithms; no free parameters, new axioms beyond standard math, or invented entities are described in the abstract.

axioms (1)
  • standard math Hub labeling correctly encodes shortest paths or transfers in the underlying graph model
    Implicit in the claim that hub labeling represents unlimited foot transfers.

pith-pipeline@v0.9.0 · 5618 in / 1160 out tokens · 23310 ms · 2026-05-25T18:38:23.940262+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Goldberg, and Renato F onseca F

    Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F onseca F. Werneck. A hub- based labeling algorithm for shortest paths in road networks. In Experimental Algorithms - 10th International Symposium, SEA , volume 6630 of Lecture Notes in Computer Science , pages 230–241, 2011

    work page 2011

  2. [2]

    Goldberg, and Renato F onseca F

    Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F onseca F. Werneck. Hierarchical hub labelings for shortest paths. In Algorithms - ESA European Symposium , volume 7501 of Lecture Notes in Computer Science , pages 24–35, 2012

    work page 2012

  3. [3]

    Fast routing in very large public transportation ne tworks using transfer patterns

    Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger, Chris Harrelson, Veselin Raychev, and Fabien Viger. Fast routing in very large public transportation ne tworks using transfer patterns. 7 In Algorithms - ESA 2010, 18th Annual European Symposium , volume 6346 of Lecture Notes in Computer Science , pages 290–301. Springer, 2010

    work page 2010

  4. [4]

    Goldberg, Matthias M¨ uller -Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F

    Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias M¨ uller -Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Rout e planning in transportation net- works. In Algorithm Engineering - Selected Results and Surveys , volume 9220 of Lecture Notes in Computer Science , pages 19–80. Springer, 2016

    work page 2016

  5. [5]

    Scalable tr ansfer patterns

    Hannah Bast, Matthias Hertel, and Sabine Storandt. Scalable tr ansfer patterns. In Proceedings of the Eighteenth Workshop on Algorithm Engineering and Exper iments, ALENEX 2016 , pages 15–29. SIAM, 2016

    work page 2016

  6. [6]

    Reachabilit y and distance queries via 2-hop labels

    Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachabilit y and distance queries via 2-hop labels. SIAM J. Comput. , 32(5):1338–1355, 2003

    work page 2003

  7. [7]

    Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, an d Renato F. Werneck. Comput- ing multimodal journeys in practice. In Experimental Algorithms, 12th International Symposium, SEA, volume 7933 of Lecture Notes in Computer Science , pages 260–271, 2013

    work page 2013

  8. [8]

    Wernec k

    Daniel Delling, Julian Dibbelt, Thomas Pajor, and Renato F. Wernec k. Public transit labeling. In Experimental Algorithms - 14th International Symposium, S EA 2015, Paris, France, June 29 - July 1, 2015, Proceedings, volume 9125 of Lecture Notes in Computer Science , pages 273–285. Springer, 2015

    work page 2015

  9. [9]

    Goldberg, Thomas Pajor, and Renato F

    Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Robust distance queries on massive networks. In Algorithms - ESA European Symposium , volume 8737 of Lecture Notes in Computer Science , pages 321–333, 2014

    work page 2014

  10. [10]

    Goldberg, and Renato F

    Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Hub labeling (2-hop labeling). In Encyclopedia of Algorithms , pages 932–938. Springer, 2016

    work page 2016

  11. [11]

    Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-b ased public transit routing. Trans- portation Science, 49(3):591–604, 2015

    work page 2015

  12. [12]

    Connection scan algorithm

    Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wag ner. Connection scan algorithm. ACM Journal of Experimental Algorithmics , 23, 2018

    work page 2018

  13. [13]

    User-con strained multimodal route planning

    Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. User-con strained multimodal route planning. ACM Journal of Experimental Algorithmics , 19(1), 2014

    work page 2014

  14. [14]

    Exact routing in large road networks using contraction hierarchies

    Robert Geisberger, Peter Sanders, Dominik Schultes, and Chr istian Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388–404, 2012

    work page 2012

  15. [15]

    http://download.geofabrik.de/

    Geofabrik. http://download.geofabrik.de/

    work page

  16. [16]

    https://data.ratp.fr/

    Open Data RATP. https://data.ratp.fr/

    work page

  17. [17]

    https://www.openstreetmap.org/

    OpenStreetMap. https://www.openstreetmap.org/

    work page

  18. [18]

    https://api.tfl.gov.uk/

    Transport for London Unified API. https://api.tfl.gov.uk/

    work page

  19. [19]

    Public transit routing w ith unrestricted walking

    Dorothea Wagner and Tobias Z¨ undorf. Public transit routing w ith unrestricted walking. In 17th Workshop on Algorithmic Approaches for Transportation Mod elling, Optimization, and Systems, ATMOS, volume 59 of OASICS, pages 7:1–7:14, 2017

    work page 2017

  20. [20]

    Efficient route planning on public transportation networks: A labelling approach

    Sibo Wang, Wenqing Lin, Yi Yang, Xiaokui Xiao, and Shuigeng Zhou . Efficient route planning on public transportation networks: A labelling approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data , SIGMOD ’15, pages 967–982, New York, NY, USA, 2015. ACM. 8

    work page 2015