Adapting Dijkstra for Buffers and Unlimited Transfers

• URL: http://arxiv.org/abs/2603.11729v1
• Date: Thu, 12 Mar 2026 09:36:50 GMT
• Title: Adapting Dijkstra for Buffers and Unlimited Transfers
• Abstract summary: 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.
• Score: 10.403354331320516
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• You Only Index Once: Cross-Layer Sparse Attention with Shared Routing [61.29627714699688]
  Cross-layer sparse attention (A) is built on top of KV-sharing architectures such as YOCO.<n>A single indexer computes token-level top-k selection once and reuses the resulting index across layers.<n>Results show CLSA is both accurate and efficient, achieving up to 7.6x decoding speedup and 17.1x overall throughput improvement at 128K context.
  arXiv  Detail & Related papers  (2026-06-04T17:54:04Z)
• Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM [0.0]
  In structured multi-agent projects, agents often must follow predefined routes, making rerouting or impossible.<n>This paper addresses route-constrained multi-agent coordination by optimizing waypoint times while preserving each agent's assigned waypoint order and nominal route assignment.
  arXiv  Detail & Related papers  (2026-03-23T12:34:18Z)
• Early Pruning for Public Transport Routing [10.403354331320516]
  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%.
  arXiv  Detail & Related papers  (2026-03-13T02:49:32Z)
• Traffic-Aware Navigation in Road Networks [0.0]
  This project compares three graph search approaches for the task of traffic-aware navigation in Kingston's road network.<n>Dijkstra's and A* resulted in the most traffic-aware optimal solutions with minimal preprocessing required.<n>Floyd-Warshall-Ingerman was the fastest in real time but provided distance based paths with no traffic awareness.
  arXiv  Detail & Related papers  (2026-02-02T14:35:49Z)
• Timetable Nodes for Public Transport Network [31.793066412010468]
  Faster pathfinding in time-dependent transport networks is an important and challenging problem in navigation systems. We propose a method that advances graph-based approaches by using different optimization techniques from computational geometry. Our solution suits any other time-dependent networks and can be integrated into other pathfinding algorithms.
  arXiv  Detail & Related papers  (2024-10-21T07:34:04Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  We propose an algorithm called Mild-OGD for the full-information case, where delayed gradients are available.<n>We show that the dynamic regret of Mild-OGD can be automatically bounded by $O(sqrtbardT(P_T+1))$ under the in-order assumption.<n>We also develop a bandit variant of Mild-OGD for a more challenging case with only delayed loss values.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• Multitask Weakly Supervised Learning for Origin Destination Travel Time Estimation [8.531695291898815]
  This paper starts to estimate the OD trips travel time combined with the road network. A novel route recovery function has been proposed to maximize the current route's co occurrence probability. We conduct experiments on a wide range of real world taxi datasets in Xi'an and Chengdu.
  arXiv  Detail & Related papers  (2023-01-13T00:11:56Z)
• CITADEL: Conditional Token Interaction via Dynamic Lexical Routing for Efficient and Effective Multi-Vector Retrieval [72.90850213615427]
  Multi-vector retrieval methods combine the merits of sparse (e.g. BM25) and dense (e.g. DPR) retrievers. These methods are orders of magnitude slower and need much more space to store their indices compared to their single-vector counterparts. We propose conditional token interaction via dynamic lexical routing, namely CITADEL, for efficient and effective multi-vector retrieval.
  arXiv  Detail & Related papers  (2022-11-18T18:27:35Z)
• Deep Reinforcement Learning based Dynamic Optimization of Bus Timetable [4.337939117851783]
  We propose a Deep Reinforcement Learning based bus Timetable dynamic Optimization method (DRL-TO) A Deep Q-Network (DQN) is employed as the decision model to determine whether to dispatch a bus service during each minute of the service period. DRL-TO can dynamically determine the departure intervals based on the real-time passenger flow, saving 8$%$ of vehicles and reducing 17$%$ of passengers' waiting time on average.
  arXiv  Detail & Related papers  (2021-07-15T01:22:49Z)
• ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks [124.33353902111939]
  We propose ADOM - an accelerated method for smooth and strongly convex decentralized optimization over time-varying networks. Up to a constant factor, which depends on the network structure only, its communication is the same as that of accelerated Nesterov method.
  arXiv  Detail & Related papers  (2021-02-18T09:37:20Z)
• Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
  We propose to use backward mode linear relaxation based analysis (LiRPA) to replace Linear Programming (LP) during the BaB process. Unlike LP, LiRPA when applied naively can produce much weaker bounds and even cannot check certain conflicts of sub-domains during splitting. We demonstrate an order of magnitude speedup compared to existing LP-based approaches.
  arXiv  Detail & Related papers  (2020-11-27T16:42:12Z)
• Stochastic Optimization with Laggard Data Pipelines [65.20044914532221]
  We show that "dataechoed" extensions of common optimization methods exhibit provable improvements over their synchronous counterparts. Specifically, we show that in convex optimization with minibatches, data echoing affords speedups on the curvature-dominated part of the convergence rate, while maintaining the optimal statistical rate.
  arXiv  Detail & Related papers  (2020-10-26T14:55:31Z)
• 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.