論文の概要: Early Pruning for Public Transport Routing

• arxiv url: http://arxiv.org/abs/2603.12592v1
• Date: Fri, 13 Mar 2026 02:49:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-16 17:38:11.859849
• Title: Early Pruning for Public Transport Routing
• Title（参考訳）: 公共交通機関の早期運行
• Authors: Andrii Rohovyi, Abdallah Abuaisha, Toby Walsh,
• Abstract要約: 本稿では、最適性を損なうことなくルーティングアルゴリズムを高速化する低オーバーヘッド手法であるEarly Pruningを紹介する。 転送接続を継続時間でプリソートし、転送ループ内にプルーニングルールを適用することにより、現在の最適解よりも早く到着できないと、停止時に長い転送を破棄する。 複数の最先端のRAPTORベースのソリューションで、クエリ時間を最大57%削減しました。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: パブリックトランスポートのためのルーティングアルゴリズム、特に広く使われているRAPTORとその変種は、転送緩和フェーズ、特に無制限転送をサポートする場合、特に高密度転送グラフにおいてパフォーマンスボトルネックに直面している。 この非効率性は、多くの潜在的なインターストップ接続(ウォーク、自転車、eスクータなど)を繰り返すことによって生じる。 許容可能な性能を維持するため、実践者は移動距離を制限したり、特定の移動オプションを除外したりすることが多く、経路の最適性を低減し、旅行者に提示されるマルチモーダルオプションを制限することができる。 本稿では、最適性を損なうことなくルーティングアルゴリズムを高速化する低オーバーヘッド手法であるEarly Pruningを紹介する。 転送接続を継続時間でプリソートし、転送ループ内にプルーニングルールを適用することにより、現在の最適解よりも早く到着できないと、停止時に長い転送を破棄する。 早期のPruningは、既存のコードベースへの最小限の変更と統合することができ、ワンタイムの事前処理ステップのみを必要とする。 RAPTOR, ULTRA-RAPTOR, McRAPTOR, BM-RAPTOR, ULTRA-McRAPTOR, UBM-RAPTORなど複数の最先端RAPTORベースのソリューションをスイスとロンドンの交通ネットワークでテストし, 最大57%のクエリ時間短縮を実現した。 このアプローチは、トランジットパスフィニングアルゴリズムの効率を一般化可能な改善を提供する。 アルゴリズムの性能以外にも、アーリープルーニングは輸送計画に実用的な意味を持っている。 計算コストを削減することにより、交通機関は転送ラジイを拡張し、追加のサーバーインフラを必要とせずに、旅行プランナーに追加の移動モードを組み込むことができる。 これは、郊外や小さな町など、交通量が少ない地域での乗客にとって特に重要であり、よりリッチなマルチモーダル・ルーティングによって、私用車の代替手段が明らかになる。

関連論文リスト

• Adapting Dijkstra for Buffers and Unlimited Transfers [10.403354331320516]
  我々は、無制限の転送を伴う公共交通機関ルーティングのための古典的なジクストラに基づくアプローチを再検討する。 TD-Dijkstraの実装は、前処理中に支配的な接続をフィルタリングすることに依存している。 Transfer Aware Dijkstra (TAD)を導入し、個々のエッジではなく、旅行シーケンス全体をスキャンする。
  論文  参考訳（メタデータ） (2026-03-12T09:36:50Z)
• Dynamic Replanning for Improved Public Transport Routing [4.883358772168188]
  公共交通機関のルーティングにおける動的計画問題の定式化を行う。 ユーザが手動でリプランをリクエストする"プル"アプローチと,サーバが積極的に経路を監視し,調整する"プッシュ"アプローチの2つの方法を提案する。
  論文  参考訳（メタデータ） (2025-05-20T10:50:58Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  車両ルーティング問題 (VRP) は進化的最適化における基本的なNPハード問題である。 本稿では、強化学習エージェントを事前のインスタンスで訓練し、初期解を迅速に生成する最適化フレームワークを提案する。 このフレームワークは、様々な時間予算において、現在の最先端のソルバよりも一貫して優れています。
  論文  参考訳（メタデータ） (2025-04-08T15:21:01Z)
• Short Run Transit Route Planning Decision Support System Using a Deep Learning-Based Weighted Graph [0.0]
  本稿では,公共交通機関の計画立案者が短期間の経路改善を迅速に特定できるような,意思決定支援システムのための新しいディープラーニング手法を提案する。 本手法は,日中の2つの停留所間の経路をシームレスに調整することにより,時間を短縮し,PTサービスを増強する。 本研究では,道路セグメントの遅延値を予測するためのディープラーニングモデルを訓練し,これらの遅延値を輸送グラフのエッジ重みとして利用することにより,効率的な経路探索を実現する。
  論文  参考訳（メタデータ） (2023-08-24T14:37:55Z)
• No Transfers Required: Integrating Last Mile with Public Transit Using Opti-Mile [3.073046540587735]
  我々は、ラストマイルサービスと公共交通機関を組み合わせた新しい旅行計画手法「オプティマイル」を提案し、転送は不要である。 従来の最短経路に比べて18%の値上げで、オプティマイル走行が10%距離移動の減少につながることが実証された。
  論文  参考訳（メタデータ） (2023-06-28T06:05:14Z)
• Correlating sparse sensing for large-scale traffic speed estimation: A Laplacian-enhanced low-rank tensor kriging approach [76.45949280328838]
  本稿では,Laplacian enhanced Low-rank tensor (LETC) フレームワークを提案する。 次に,提案したモデルをネットワークワイド・クリグにスケールアップするために,複数の有効な数値手法を用いて効率的な解アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-10-21T07:25:57Z)
• Road Network Guided Fine-Grained Urban Traffic Flow Inference [108.64631590347352]
  粗いトラフィックからのきめ細かなトラフィックフローの正確な推測は、新たな重要な問題である。 本稿では,道路ネットワークの知識を活かした新しい道路対応交通流磁化器(RATFM)を提案する。 提案手法は,高品質なトラフィックフローマップを作成できる。
  論文  参考訳（メタデータ） (2021-09-29T07:51:49Z)
• Time-Optimal Planning for Quadrotor Waypoint Flight [50.016821506107455]
  立方体の作動限界における時間-最適軌道の計画は未解決の問題である。 四重項のアクチュエータポテンシャルをフル活用する解を提案する。 我々は、世界最大規模のモーションキャプチャーシステムにおいて、実世界の飛行における我々の方法を検証する。
  論文  参考訳（メタデータ） (2021-08-10T09:26:43Z)
• 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)

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

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