26

バス/電車/...の停留所と各日付の到着/出発時刻などのデータベースがあります。2つの場所の間で最速（最短/最安/最短のトランジション）の旅行を検索する方法を探しています。将来的には、OpenStreetMapデータを使用して、停車地間や停車地から開始/終了までの歩行を行う任意の場所が必要ですが、当面は、データベース内の2つの停車地間のパスを見つけたいだけです。

問題は、この主題に関する多くの情報を見つけることができないように思われることです。たとえば、このWikipediaページには、有用な情報がまったく含まれていないテキストがたくさんあります。

私が見つけたのは、GoogleTransitで使用されているGTFS形式です。私の街はパブリックデータフィードを提供していませんが（プライベートデータフィードも提供していません）、GTFSに含まれるすべての重要な情報をすでに持っているので、変換を行うのは簡単です。

OpenStreetMapを使用して歩行者/車/自転車のルーティングを実行できるOpenTripPlannerなどのGTFSベースのソフトウェアがいくつかあります。

ただし、ルーティングコードは（少なくとも私が見つけた限りでは）十分に文書化されておらず、すべてを必要としているわけではありません。

私が探しているのは、使用できるアルゴリズムの概要、それらのパフォーマンス、おそらくいくつかの擬似コードです。

それで、問題は、停車地、ルート、到着/出発/移動時間のリストを考えると、どうすれば停車地Aから停車地Bまでの最速のパスを簡単に見つけることができるかということです。

4

1 に答える 1

16
  1. 問題をグラフとしてモデル化します。各ステーションは頂点になり、各バス/電車はエッジになります。
  2. w:Edges->R各エッジの時間/お金/...を示す関数を作成します。
  3. これで、典型的な最小経路問題が発生し ました。これは、特定のソースからすべての頂点への最小経路を見つけるダイクストラアルゴリズムによって解決できます。

（*）「最小遷移」の場合、重みは実際には各エッジで1であるため、この投稿で説明したように、ダイクストラの代わりにBFSまたは双方向BFSを実行することで、これを最適化することもできます[ソーシャル向けに説明されています距離ですが、実際には同じアルゴリズムです]。

コメントで言及したグラフの非静的な性質の編集
として編集[価格と遷移​​の数については、これらのグラフは静的であるため、上記の内容が引き続き適用されます]、距離ベクトルを使用できますルーティングアルゴリズム。これは、実際には動的グラフで機能することを目的としており、ベルマンフォードアルゴリズムの分散型バリエーションです。
アルゴリズムのアイデア：

  • 定期的に、すべての頂点はその「距離ベクトル」を隣接する頂点に送信します[ベクトルは、送信する頂点から他の頂点に移動するのに「コスト」がかかることを示します。
  • そのネイバーは、ルーティングテーブルを更新しようとします[各ターゲットに移動するのに最適なエッジはどれですか]
  • あなたの場合、各ノードは隣接ノードに到達するための最速の方法を知っており、[移動時間+待機時間]そして[頂点/ステーション]は距離ベクトルの各メインディッシュにこの番号を追加して、目的地に到着するまでにかかる時間。バスが出発するとき、移動時間は[このソースから]すべてのノードに再計算され、新しいベクトルがその隣接ノードに送信される必要があります
于 2011-08-30T15:43:34.770 に答える