論文の概要: Adapting Dijkstra for Buffers and Unlimited Transfers

• arxiv url: http://arxiv.org/abs/2603.11729v1
• Date: Thu, 12 Mar 2026 09:36:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-13 14:46:25.997997
• Title: Adapting Dijkstra for Buffers and Unlimited Transfers
• Title（参考訳）: バッファと無制限転送に対するDijkstraの適応
• Authors: Denys Katkalo, Andrii Rohovyi, Toby Walsh,
• Abstract要約: 我々は、無制限の転送を伴う公共交通機関ルーティングのための古典的なジクストラに基づくアプローチを再検討する。 TD-Dijkstraの実装は、前処理中に支配的な接続をフィルタリングすることに依存している。 Transfer Aware Dijkstra (TAD)を導入し、個々のエッジではなく、旅行シーケンス全体をスキャンする。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 近年、RAPTORベースのアルゴリズムは、前処理なしで無制限の転送を行うパスフィンディングの最先端と見なされている。 しかし、この状態はルーティング研究の進化に大きく起因しており、ダイクストラベースのソリューションは体系的な比較なしにタイムテーブルベースのアルゴリズムに取って代わられた。 本研究では,従来のDijkstraをベースとした公共交通ルーティングのアプローチを無制限転送で再検討し,TD-Dijkstra(Time-Dependent Dijkstra)がMRより優れていることを示す。しかし,効率的なTD-Dijkstraの実装は前処理時に支配的な接続をフィルタリングすることに依存しており,常により高速な接続に切り替えることができると仮定している。 このフィルタリングは,バッファを尊重しなければならない乗客の待機や移動を伴わずに継続するかもしれない着席客を区別できないため,バッファ時間を持つ場合には不適切であることを示す。 この制限に対処するために、Transfer Aware Dijkstra (TAD)を導入し、個々のエッジではなく、旅行シーケンス全体をスキャンし、バッファタイムを正しく処理し、MRよりもパフォーマンス上の優位性を保ちながら、バッファタイムを正しく処理する。ロンドンとスイスのネットワークでの実験では、バッファタイムのない両方のネットワーク上で最適な結果を生成しながら、MRよりも2倍以上のスピードアップを実現できることが示されている。

関連論文リスト

• Traffic-Aware Navigation in Road Networks [0.0]
  本研究は,キングストンの道路網における交通認識ナビゲーションの課題に対する3つのグラフ探索手法を比較した。 Dijkstra と A* は、最小限の事前処理を必要とする最もトラフィック対応の最適ソリューションとなった。 フロイド=ワースホール=インガーマン(Floyd-Warshall-Ingerman)は、リアルタイムでは最速であったが、交通の注意を払わず、距離に基づく経路を提供した。
  論文  参考訳（メタデータ） (2026-02-02T14:35:49Z)
• Timetable Nodes for Public Transport Network [31.793066412010468]
  時間依存トランスポートネットワークにおける高速パスフィニングは、ナビゲーションシステムにおいて重要かつ困難な問題である。 本稿では,計算幾何学と異なる最適化手法を用いて,グラフベースのアプローチを進化させる手法を提案する。 我々のソリューションは他の時間依存ネットワークに適合し、他のパスフィンディングアルゴリズムに統合できる。
  論文  参考訳（メタデータ） (2024-10-21T07:34:04Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Multitask Weakly Supervised Learning for Origin Destination Travel Time Estimation [8.531695291898815]
  本論文は,道路網とOD旅行時間とを組み合わせて推定し始める。 現在の経路の共発生確率を最大化する新たな経路回復関数が提案されている。 我々は、Xi'anとChengduで、幅広い現実世界のタクシーのデータセットの実験を行っている。
  論文  参考訳（メタデータ） (2023-01-13T00:11:56Z)
• CITADEL: Conditional Token Interaction via Dynamic Lexical Routing for Efficient and Effective Multi-Vector Retrieval [72.90850213615427]
  マルチベクター検索法はスパース(例えばBM25)と高密度(例えばDPR)レトリバーの利点を組み合わせたものである。 これらの手法は桁違いに遅く、単ベクトルの手法に比べてインデックスを格納するのにはるかに多くのスペースを必要とする。 動的語彙ルーティング(CITADEL)による条件付きトークンの相互作用を,効率的かつ効率的なマルチベクタ検索のために提案する。
  論文  参考訳（メタデータ） (2022-11-18T18:27:35Z)
• Deep Reinforcement Learning based Dynamic Optimization of Bus Timetable [4.337939117851783]
  深層強化学習に基づくバス時刻動的最適化法(DRL-TO)を提案する。 DQN(Deep Q-Network)は、サービス期間中にバスサービスをディスパッチするかどうかを決定する決定モデルとして使用される。 DRL-TOは、リアルタイムの乗客フローに基づいて出発間隔を動的に決定し、車両の8$%を節約し、乗客の待ち時間の平均17$%を削減できる。
  論文  参考訳（メタデータ） (2021-07-15T01:22:49Z)
• ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks [124.33353902111939]
  本稿では,時間変動ネットワーク上の滑らかかつ強凸分散最適化のための高速化手法である adom を提案する。 ネットワーク構造のみに依存する一定の要因まで、その通信は加速されたNesterovメソッドのそれと同じです。
  論文  参考訳（メタデータ） (2021-02-18T09:37:20Z)
• Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
  BaB プロセス中に線形計画法 (LP) を置き換えるために, 逆モード線形緩和に基づく解析法 (LiRPA) を提案する。 LPとは異なり、LiRPAを適用すると、より弱い境界が得られ、分割時にサブドメインのコンフリクトをチェックすることもできない。 既存のLPベースのアプローチと比較して、桁違いのスピードアップを示す。
  論文  参考訳（メタデータ） (2020-11-27T16:42:12Z)
• Stochastic Optimization with Laggard Data Pipelines [65.20044914532221]
  共通最適化手法の「データ抽出」拡張は同期手法よりも優れた性能を示すことを示す。 具体的には、ミニバッチによる凸最適化において、データエコーは、最適統計率を維持しながら収束率の曲率に支配される部分の高速化をもたらすことを示す。
  論文  参考訳（メタデータ） (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]
  複数の自動誘導車両 (AGV) が共通作業空間をナビゲートし, 様々な作業を行う。 一つのアプローチは、Action Dependency Graph (ADG)を構築し、そのルートに沿って進むとAGVの順序を符号化する。 ワークスペースが人間やサードパーティロボットのような動的障害によって共有されている場合、AGVは大きな遅延を経験することができる。 本稿では,各AGVの経路完了時間を最小限に抑えるために,非循環ADGを繰り返し修正するオンライン手法を提案する。
  論文  参考訳（メタデータ） (2020-10-11T14:39:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。