バスのルートを見つけることができるオフライン C# アプリケーションに取り組んでいます。時刻表/バス/路線データを抽出できます。基本データで機能する最も単純なソリューションを探しています。
バス停「A」からバス停「B」までの経路を見つけるために使用できるアルゴリズムは? C#/Java に対応したオープンソース ソリューションはありますか? データベースの Google GTFS 形式は単純なソリューションに適していますか? http://code.google.com/transit/spec/transit_feed_specification.html
助けてくれてありがとう。私はこれで立ち往生しています。どこから始めればいいのかわからない - データを保存する方法とルートを見つける方法。Dijkstra/A* については知っていますが、時間に依存しないグラフでのみ使用しました...
あなたが取り組んでいる問題は簡単な作業ではありません。これには、混合整数非線形計画問題 (MINLP) という名前があります。ある著者の言葉 (Deb 1998):
「数学的に定式化すると、時間スケジューリング問題は、多数のリソースおよびサービス関連の制約を持つ混合整数非線形計画問題 (MINLP) になります。古典的な最適化手法 (Bookbinder & DCsilets, 1992; Kikuchi & Parameswaran, 1993) によると、これは小さなトランジット ネットワークでも非常に困難な作業であることが観察されています. 困難は主に多数の変数と制約、離散的な性質のために発生します.変数、および目的関数と制約に含まれる非線形性。」
Deb の論文で、彼は遺伝的アルゴリズムを提案しています。
他のオプションは、シミュレーションを使用することです。何かをすぐに試してみることができます。出発地から出発する何千ものランダムなルートを選択し、目的地に到達するのに十分に機能するルートを探し出します。
アルゴリズムを次のように想像してください。特定の時刻に開始して、ストップ A からストップ B までの最短ルートを見つけようとしています。あなたは 1,000 人を雇い、4 分の 1 で彼らを武装させます。バスに乗り降りする機会があるたびにコインを投げるように言います。頭、降りてください（または、すでに降りている場合は乗ってください）。テール、オンのまま (オフの場合は待機し続ける)。彼らはそれぞれ、自分が行った選択を書き留めるためのインデックスカードを持っています。ポイント B に行き、最初の男が現れてカードを受け取るのを待ちます。
これを読む：
マルチモーダルルート計画。修士論文、Universität Karlsruhe (TH)、Fakultät für Informatik、2009 年。オンラインで入手可能http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf
鉄道ルートのセクションは、バスのルートにも適用されます。
要点: 空間と時間を単一のグラフに拡張する単純なアプローチは、大規模なネットワークでは機能しません。よりスマートなソリューションがあります。
この問題に対する私の最終的なアプローチを共有したかっただけです。これは大学のプロジェクトの一部であったため、実際の使用には完全に適していない可能性があります。Windows Mobile デバイスで実行するには、かなり高速である必要がありました。
最終的に4つのテーブル（SQLite）を使用しました。1 つのテーブルにはバスのリストが保持され、2 つ目のテーブルには駅のリストが保持されます。別のテーブルには、特定の駅に停車するバスと、この駅からどこに行き、所要時間 (分) の組み合わせが保持されます。すべての組み合わせを保存する必要があります。最後の表は簡単な時刻表です。すべての駅について、そこに停車するすべてのバスと時刻がリストされます（比較のために高速化するために、時刻を整数値として保存しました-14:34は1434です）。
双方向の幅優先探索アルゴリズムを使用しました。始発駅、終着駅は隣接駅（直通）を検索します。これらの 2 つの「グラフ」がステーションで重なる場合、ステーション A からステーション X へのパスがあります。たとえば、駅 A から駅 B、C、D、E に行くことができます (特定のバスを使用)。目的地の駅 X からは、N、C、Z に直接行くことができます。これらの 2 つのグラフはステーション C で重なります。したがって、パス A -> C -> X が存在します。この最初の反復でパスが見つからない場合、アルゴリズムは続行され、グラフ (BFS) が再び展開されます。
最初のステップでは時間が考慮されていません。これにより、十分に高速になります。これらのパスを取るために使用する必要があるバスのリストを含む、可能なパスのリストのみを取得します。時間は最後のステップで評価されます。可能なパスのリストを調べて、バスが特定の時間内に移動するかどうかを確認します (停車ごとに時間を増やします)。
250 の駅と 100 以上のバス/鉄道がある小さな都市では、これらのアプローチは最大 3 回の乗り換え (移動中にバスを乗り換える必要がある場合) まで機能します。計算にかかる時間はわずか数秒です。しかし、時間がかかりすぎるクエリを高速化するために、データベース全体をメモリ (辞書) にロードする必要がありました。
ただし、これは大規模なネットワークでは機能しないと思います。しかし、単一の中小規模都市の公共交通機関では機能します。
概念的には、A と B の間の距離を評価するために同じ基本アルゴリズムを使用しますが、距離の代わりに時間を評価する必要があります。適切な入力を与えれば、Dijkstra は両方を行うことができます。
地図を距離の尺度として見ることに慣れています。ただし、同じマップを時間の尺度にすることもできます。必要なのは平均速度に関するデータを追加することだけで、特定の道路の特定の距離をカバーするのにかかる時間は自動的に変動します。マップを時間で視覚化することもできます。時間がかかるルートは長くなります。Dijkstra は、どちらを評価しているかは気にしません。最小の数字で連続ルートを見つけることだけに関心があり、その数字が長さを表すか時間を表すかは重要ではありません。
速度を組み込むために、素朴なアルゴリズムは単純に日中の速度制限を使用し、A から B に移動するときに停止する必要がないと仮定します。より高度なアルゴリズムは、時間帯と交通パターン (その時点でその道路を移動する平均速度に影響を与える) に関する情報、および道路が高速道路であるか一般道であるかに関する情報を組み込むことができます (したがって、停止に費やした時間についての知識に基づいた推測を行うことができます)。交差点で）。何を使用するかは、利用可能なものによって異なりますが、基本的な 4 層または 5 層の時刻ディメンションは、最もタイム クリティカルなアプリケーションを除くすべてのアプリケーションに適しています。マップ内の各道路の方向ごとに、朝のラッシュ時、日中、夕方のラッシュ時、および夜間の平均速度が必要であり、場合によってはランチタイムの数値も必要です。あなたがそれを手に入れたら、それは'
時間情報に関心がある場合は、物理的な距離の代わりに時間情報を使用して、グラフ エッジの距離値にラベルを付けてみませんか。そうすれば、最短ルートではなく、最短ルートを検索できます。その後、結果を計算するために Dijkstra/A* を使用できます。
時間依存の意味がちょっとわかりません。「午前 10 時前に x から y に行く」という形式のクエリに答える必要があるということであれば、データの単純なフィルターのように、午前 10 時前に到着するバス ルートを計算できます。次に、Dijkstra/A* をデータに適用します。
これをデータモデルとして試してください。
バス 1 は A、B、C の停留所に行きます。バス 2 は B、D、E の停留所に行きます。
バスと停留所の両方に基づいて一意のノードを保存し、ノードまでの距離は時間に基づいています。ノード A1、B1、C1、B2、D2、および E2 があります。転送の特殊なケースでは、ノード間の距離として次のバスの待機を適用します。たとえば、バス 1 がバス 2 の 30 分前に停留所 B に到着した場合、B1 から B2 までの移動時間は 30 分です。
ダイクストラのアルゴリズムを適用できるはずです。