Early Pruning for Public Transport Routing

• URL: http://arxiv.org/abs/2603.12592v1
• Date: Fri, 13 Mar 2026 02:49:32 GMT
• Title: Early Pruning for Public Transport Routing
• Abstract summary: This paper introduces Early Pruning, a low-overhead technique that accelerates routing algorithms without compromising optimality.<n>By pre-sorting transfer connections by duration and applying a pruning rule within the transfer loop, the method discards longer transfers at a stop once they cannot yield an earlier arrival than the current best solution.<n>Across multiple state-of-the-art RAPTOR-based solutions, we achieved query time reductions of up to 57%.
• Score: 10.403354331320516
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Routing algorithms for public transport, particularly the widely used RAPTOR and its variants, often face performance bottlenecks during the transfer relaxation phase, especially on dense transfer graphs, when supporting unlimited transfers. This inefficiency arises from iterating over many potential inter-stop connections (walks, bikes, e-scooters, etc.). To maintain acceptable performance, practitioners often limit transfer distances or exclude certain transfer options, which can reduce path optimality and restrict the multimodal options presented to travellers. This paper introduces Early Pruning, a low-overhead technique that accelerates routing algorithms without compromising optimality. By pre-sorting transfer connections by duration and applying a pruning rule within the transfer loop, the method discards longer transfers at a stop once they cannot yield an earlier arrival than the current best solution. Early Pruning can be integrated with minimal changes to existing codebases and requires only a one-time preprocessing step. Across multiple state-of-the-art RAPTOR-based solutions, including RAPTOR, ULTRA-RAPTOR, McRAPTOR, BM-RAPTOR, ULTRA-McRAPTOR, and UBM-RAPTOR and tested on the Switzerland and London transit networks, we achieved query time reductions of up to 57%. This approach provides a generalizable improvement to the efficiency of transit pathfinding algorithms. Beyond algorithmic performance, Early Pruning has practical implications for transport planning. By reducing computational costs, it enables transit agencies to expand transfer radii and incorporate additional mobility modes into journey planners without requiring extra server infrastructure. This is particularly relevant for passengers in areas with sparse direct transit coverage, such as outer suburbs and smaller towns, where richer multimodal routing can reveal viable alternatives to private car use.

Related papers

• Preference-Conditioned Multi-Objective Reinforcement Learning for Runtime-Tunable Transit Signal Priority [0.0]
  Transit signal priority (TSP) requires balancing competing objectives: reducing bus delay while limiting adverse impacts on non-bus traffic and avoiding extreme waits for a subset of vehicles.<n>We present a preference-conditioned TSP controller that selects the next signal phase under minimum/maximum green and transition-feasibility constraints.<n>Experiments show that a single learned conditioned policy spans a smooth empirical trade-off frontier across preferences, outperforms fixed-time and rule-based baselines, and maintains constraint feasibility.
  arXiv  Detail & Related papers  (2026-06-30T09:57:39Z)
• Adapting Dijkstra for Buffers and Unlimited Transfers [10.403354331320516]
  We revisit classical Dijkstra-based approaches for public transit routing with unlimited transfers.<n> TD-Dijkstra implementations rely on filtering dominated connections during preprocessing.<n>We introduce Transfer Aware Dijkstra (TAD), a modification that scans entire trip sequences rather than individual edges.
  arXiv  Detail & Related papers  (2026-03-12T09:36:50Z)
• Dynamic Replanning for Improved Public Transport Routing [4.883358772168188]
  We formalise the dynamic replanning problem in public transport routing.<n>We propose two solutions: a "pull" approach, where users manually request replanning, and a novel "push" approach, where the server proactively monitors and adjusts journeys.
  arXiv  Detail & Related papers  (2025-05-20T10:50:58Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  Vehicle Routing Problems (VRP) are a fundamental NP-hard challenge in Evolutionary optimization.<n>We introduce an optimization framework where a reinforcement learning agent is trained on prior instances and quickly generates initial solutions.<n>This framework consistently outperforms current state-of-the-art solvers across various time budgets.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• Short Run Transit Route Planning Decision Support System Using a Deep Learning-Based Weighted Graph [0.0]
  We propose a novel deep learning-based methodology for a decision support system that enables public transport planners to identify short-term route improvements rapidly. By seamlessly adjusting specific sections of routes between two stops during specific times of the day, our method effectively reduces times and enhances PT services. Using self-supervision, we train a deep learning model for predicting lateness values for road segments. These lateness values are then utilized as edge weights in the transportation graph, enabling efficient path searching.
  arXiv  Detail & Related papers  (2023-08-24T14:37:55Z)
• No Transfers Required: Integrating Last Mile with Public Transit Using Opti-Mile [3.073046540587735]
  We propose opti-mile," a novel trip planning approach that combines last-mile services with public transit such that no transfers are required. We demonstrate that opti-mile trips lead to a 10% reduction in distance travelled for 18% increase in price compared to traditional shortest paths.
  arXiv  Detail & Related papers  (2023-06-28T06:05:14Z)
• Correlating sparse sensing for large-scale traffic speed estimation: A Laplacian-enhanced low-rank tensor kriging approach [76.45949280328838]
  We propose a Laplacian enhanced low-rank tensor (LETC) framework featuring both lowrankness and multi-temporal correlations for large-scale traffic speed kriging. We then design an efficient solution algorithm via several effective numeric techniques to scale up the proposed model to network-wide kriging.
  arXiv  Detail & Related papers  (2022-10-21T07:25:57Z)
• Road Network Guided Fine-Grained Urban Traffic Flow Inference [108.64631590347352]
  Accurate inference of fine-grained traffic flow from coarse-grained one is an emerging yet crucial problem. We propose a novel Road-Aware Traffic Flow Magnifier (RATFM) that exploits the prior knowledge of road networks. Our method can generate high-quality fine-grained traffic flow maps.
  arXiv  Detail & Related papers  (2021-09-29T07:51:49Z)
• Time-Optimal Planning for Quadrotor Waypoint Flight [50.016821506107455]
  Planning time-optimal trajectories at the actuation limit of a quadrotor is an open problem. We propose a solution while exploiting the full quadrotor's actuator potential. We validate our method in real-world flights in one of the world's largest motion-capture systems.
  arXiv  Detail & Related papers  (2021-08-10T09:26:43Z)
• Frustratingly Easy Transferability Estimation [64.42879325144439]
  We propose a simple, efficient, and effective transferability measure named TransRate. TransRate measures the transferability as the mutual information between the features of target examples extracted by a pre-trained model and labels of them. Despite its extraordinary simplicity in 10 lines of codes, TransRate performs remarkably well in extensive evaluations on 22 pre-trained models and 16 downstream tasks.
  arXiv  Detail & Related papers  (2021-06-17T10:27:52Z)
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
  We consider multiple Automated Guided Vehicles (AGVs) navigating a common workspace to fulfill various intralogistics tasks. One approach is to construct an Action Dependency Graph (ADG) which encodes the ordering of AGVs as they proceed along their routes. If the workspace is shared by dynamic obstacles such as humans or third party robots, AGVs can experience large delays. We present an online method to repeatedly modify acyclic ADG to minimize route completion times of each AGV.
  arXiv  Detail & Related papers  (2020-10-11T14:39:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.