論文の概要: Timetable Nodes for Public Transport Network

• arxiv url: http://arxiv.org/abs/2410.15715v2
• Date: Wed, 23 Oct 2024 05:02:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-24 09:54:59.403327
• Title: Timetable Nodes for Public Transport Network
• Title（参考訳）: 公共交通ネットワークのためのタイムテーブルノード
• Authors: Andrii Rohovyi, Peter J. Stuckey, Toby Walsh,
• Abstract要約: 時間依存トランスポートネットワークにおける高速パスフィニングは、ナビゲーションシステムにおいて重要かつ困難な問題である。 本稿では,計算幾何学と異なる最適化手法を用いて,グラフベースのアプローチを進化させる手法を提案する。 我々のソリューションは他の時間依存ネットワークに適合し、他のパスフィンディングアルゴリズムに統合できる。
• 参考スコア（独自算出の注目度）: 31.793066412010468
• License:
• Abstract: 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\times \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.
• Abstract（参考訳）: 時間依存トランスポートネットワークにおける高速パスフィニングは、ナビゲーションシステムにおいて重要かつ困難な問題である。 交通網には、自動車運転のための道路網と公共交通機関網の2種類がある。 時間依存のContraction Hierarchiesや他のグラフベースのアプローチのような、ロードネットワークでうまく機能するソリューションは、通常、トランスポートネットワークには適用されない。 トランスポートネットワークでは、CSAやRAPTORのような非グラフソリューションがグラフベースの手法と比較して最良の結果を示している。 本研究では,移動ネットワークにおける探索処理を高速化するために,計算幾何学から異なる最適化手法を用いてグラフベースのアプローチを進化させる手法を提案する。 タイムテーブルノード(TTN)と呼ばれる新しい計算前ステップを適用します。 私たちのインスピレーションは、計算幾何学における反復探索問題から来ています。 TTNの2つのバージョンを実装している: 1つは複合探索木(TTN-CST)、もう1つはフラクショナルカスケーディング(TTN-FC)である。 どちらのアプローチも、新しいノードに到達する際の漸近的な複雑さを$O(k\times \log|C|)$から$O(k + \log(k) + \log(|C|)$に減少させる。 我々のソリューションは他の時間依存ネットワークに適合し、他のパスフィンディングアルゴリズムに統合できる。 実験により,この事前計算は高密度グラフの性能を著しく向上させることが示された。 本研究では,計算幾何学の活用が輸送ネットワークのパスフィニングをいかに向上させるかを示し,多数のエッジを含むシナリオにおけるパスフィニングの高速化を実現する。

関連論文リスト

• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  時間グラフは連続時間を通してノード間の動的相互作用を示す。 本研究では,周辺地域全体と時間的グラフ畳み込みの新たな手法を提案する。 提案するTAP-GNNは,予測性能とオンライン推論遅延の両面で,既存の時間グラフ手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2023-04-15T08:17:18Z)
• Learning Graph Search Heuristics [48.83557172525969]
  本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。 我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
  論文  参考訳（メタデータ） (2022-12-07T22:28:00Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• RNGDet++: Road Network Graph Detection by Transformer with Instance Segmentation and Multi-scale Features Enhancement [19.263691277963368]
  道路網のグラフ構造は、グローバルな計画、動き予測、制御など、自律運転システムの下流業務に不可欠である。 これまでは、道路ネットワークグラフは人の専門家によって手動で注釈付けされていた。 前者は、プロセス後セマンティックセグメンテーションマップや、ロードネットワークグラフを直接予測するグラフベースのアルゴリズムを提案している。 それまでの作業は、ハードコードされた処理アルゴリズムと劣った最終性能に悩まされていた。 提案されたアプローチはRNGDetから改善されているため、RNGDet++と呼ばれている。
  論文  参考訳（メタデータ） (2022-09-21T07:06:46Z)
• tBDFS: Temporal Graph Neural Network Leveraging DFS [33.762062743040495]
  本稿では,新しい時間的GNNアーキテクチャであるtBDFSを提案する。 tBDFSは、グラフ内の所定の(ターゲット)ノードへの時間的パスから情報を効率的に集約する層を適用します。 全体として、私たちの目標は、ノードに新しい情報を追加するのではなく、新しい視点で同じ正確な情報を観察することにあります。
  論文  参考訳（メタデータ） (2022-06-12T08:38:06Z)
• GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
  3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。 提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
  論文  参考訳（メタデータ） (2022-05-30T16:22:53Z)
• Waypoint Planning Networks [66.72790309889432]
  本稿では,ローカルカーネル(A*のような古典的アルゴリズム)と学習アルゴリズムを用いたグローバルカーネルを用いたLSTMに基づくハイブリッドアルゴリズムを提案する。 我々は、WPNとA*を比較し、動き計画ネットワーク(MPNet)やバリューネットワーク(VIN)を含む関連する作業と比較する。 WPN の探索空間は A* よりもかなり小さいが、ほぼ最適な結果が得られることが示されている。
  論文  参考訳（メタデータ） (2021-05-01T18:02:01Z)
• A Study of Performance of Optimal Transport [16.847501106437534]
  本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。 古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-03T20:37:05Z)

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

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