# Timetable Nodes for Public Transport Network

arXiv: https://arxiv.org/abs/2410.15715 · HTML: https://mlsanity.com/paper/2410.15715/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 21 references that are in the map.
- First posted on arXiv 21 Oct 2024.

## Builds on (most cited first, 2 of 2)

- [Route Planning in Transportation Networks](https://mlsanity.com/paper/1504.05140/) (2015)
- [Connection Scan Algorithm](https://mlsanity.com/paper/1703.05997/) (2017)

## Built on by (most cited first, 2 of 2)

- [Adapting Dijkstra for Buffers and Unlimited Transfers](https://mlsanity.com/paper/2603.11729/) (2026)
- [Early Pruning for Public Transport Routing](https://mlsanity.com/paper/2603.12592/) (2026)

## Abstract (arXiv)

Faster pathfinding in time-dependent transport networks is an important and challenging problem in navigation systems. There are two main types of transport networks: road networks for car driving and public transport route network. The solutions that work well in road networks, such as Time-dependent Contraction Hierarchies and other graph-based approaches, do not usually apply in transport networks. In transport networks, non-graph solutions such as CSA and RAPTOR show the best results compared to graph-based techniques. In our work, we propose a method that advances graph-based approaches by using different optimization techniques from computational geometry to speed up the search process in transport networks. We apply a new pre-computation step, which we call timetable nodes (TTN). Our inspiration comes from an iterative search problem in computational geometry. We implement two versions of the TTN: one uses a Combined Search Tree (TTN-CST), and the second uses Fractional Cascading (TTN-FC). Both of these approaches decrease the asymptotic complexity of reaching new nodes from O(k× log|C|) to O(k + log(k) + log(|C|)), where k is the number of outgoing edges from a node and |C| is the size of the timetable information (total outgoing edges). Our solution suits any other time-dependent networks and can be integrated into other pathfinding algorithms. Our experiments indicate that this pre-computation significantly enhances the performance on high-density graphs. This study showcases how leveraging computational geometry can enhance pathfinding in transport networks, enabling faster pathfinding in scenarios involving large numbers of outgoing edges.