c# - リアルに理想のフォルム。物流におけるダイクストラ

Question

Dijkstra によって最適なルートが計算された運送会社向けのプログラムがあります。頂点としての都市とエッジとしてのルート。エッジの重みを見つける。地図の都市を線でつないで測ってみました。次に、エッジの重みとして受け入れます。しかし、実際のルートはまっすぐではありません。どうすれば修正できますか？ここに画像の説明を入力

私のプロジェクトでは、ソフトウェアの作成に関する物流の問題を解決する必要があります。誰が何を解決すればよいか教えてもらえますか?

Answer 1

すでにわかっているように、問題は思ったほど単純ではありません。まず第一に、主要都市だけを接続するのは悪い考えです。なぜなら、それらはおそらく高速道路に直接接続されていないからです (それが米国か何かでない場合)。

それがあなたの現在の考えです：

私が提案するのは、意味のあるすべての方法ですべての小都市を取得し、それをあなたの頂点として追加しようとすることですDijkstra:

さて、現実世界にどの道が実際に存在するかを見ることができるようになりました。グラフを見るだけで、下のパスを使用する方が効率的であると推測できます。しかし、次のことがわかったらどうでしょう。

下の方の 2 倍の速度を達成できるため、上のほうが実際にははるかに優れていると簡単に結論付けることができます。それは非常に正確な分類ですか？いいえ、ちがいます。往路ごとにどのような交通量があるかを考えて、エッジの重みを動的に変更したい場合があります。しかし、それはおそらく基本的な実装には多すぎます。

最終的に私がすることは、ほとんど一人で、またはほとんど助けを借りずに、どのようなデータを収集できるかを考えることです. だから私は間違いなくできる：

• ポイントAからポイントBに到達する実際の方法に関するデータを何らかの方法で破棄します。適切なリファレンスは、Google Maps APIまたはBing Maps APIです。
• ポイントAからBへの現実世界の道を見つけながら、途中で小さな都市を集めます。
• 速度制限がどこにあるかを調べてみてください（データベースがある場合）

Google Maps実際、あなたはどちらかを完全に使いたいと思うかもしれませんBing Maps. どちらも、必要な道路の実際のデータを持っています。彼らほど多くのデータを収集できる方法はありません。それがあなたにできる方法だと感じれば、あなたは皿の上にすべてを持っています。

そうでない場合は、ハイブリッドな方法を使用します。任意のマップ API から重要なデータを取得し、それをDijkstraアルゴリズムに使用してから、このデータを使用して、考えられる修飾子 (速度制限、交通量) に基づいて各エッジの実際の重みを測定するための単純なアルゴリズムを記述します。 API が提供する場合など)。