国内のすべての公共交通機関 (バス/電車/飛行機) のジャーニー プランナー (または一般的な時刻表アプリケーション) を作成しています。
プロジェクトの状態は中間点にあり、アプリケーションのより難しい部分を完成させるのに少し苦労しています。
現在のステータスを説明するには:
データは、GTFS (General (Google) Transit Feed Specification) としてモデル化された MySQL データベースに保存されます。
データベースにクエリを実行するだけで直接ルートを取得しています（2つの一時テーブルを結合すると、十分に効率的です）
現在は PHP で行っていますが、必要に応じて Java でやり直すこともできます。
したがって、2 点間に直接接続がある場合は、すべて問題ありません。難しいのは、直行便がない場合に完全な旅をすることです。
ユーザーが から に移動したいとしますがcity A、city Dこれらの都市間に直通の路線がないため、 と を通過する必要がcity Bありcity Cます。
この状況で最適化されたルートと乗り換えを取得するにはどうすればよいですか?
これまでの私のアイデアは、グラフの使用に引き寄せられていますが、その場合はTime-Dependant Directed Weighted Multigraphが必要であり、現時点ではTime-Dependant部分を実装する方法が本当にわかりません。
Dijkstra、A*またはアルゴリズムを使用してルートを取得することはできますがFloyd–Warshall、さまざまな時間に出発があるため、最適なソリューションを取得するためにこれをどのように実装するかはわかりません。区間の長さ (A から B、B から C)、乗り換えの待ち時間、距離も考慮する必要があります。
明確にするために、単一の結果は必要ありません。必要に応じて乗り換えも含めcity Aて、ユーザーを に到達させることができるからのすべての出発の毎日のリストを取得したいと考えています。city D
基本的に、私が取得しようとしているのは、次のようなものです (ブルガリア鉄道、またはその点については、鉄道サイトから取得)、必要に応じて乗り換えSofiaを行うために選択した日のすべての出発のリスト:KystendilRadomir
グラフを解く部分については、jGraphTを使用して Java でアプリケーションを作成し、結果をキャッシュし (数か月に 1 回変更される可能性があります)、PHP で使用します (または PHP を介してアプリケーションを呼び出します)。
よくわからない場合は、お尋ねください。
これが何度も行われていることは知っていますが (ほとんどすべての鉄道 Web サイトに解決策があります)、どの用語で検索すればよいかさえわかりません。
それで、私の質問は、このタイプの問題がどのように解決されるかについて、誰かが私にガイダンスを与えることができますか?
または、少なくともどの用語でアイデアを検索する必要があり、どのように行う必要がありますか。
StackExchange ネットワーク内の他のサイトに関するいくつかの提案かもしれません。
ありがとうございました。