0

私は現在、Android でナビゲーション システムを開発しており、ダイクストラの最短パス アルゴリズムを使用しています。私の Vertex クラスには、以下に示すようなメンバーが含まれています。

-------------------------------------
|                 Vertex            |
-------------------------------------
|    |      |           |           |
| id | name | longitude | latitude  |
-------------------------------------

および以下に示すメンバーを持つエッジ:

---------------------------------------------
|                Edge                       |
---------------------------------------------
|    |      |        |             |        |
| id | name | source | destination | weight |
---------------------------------------------

頂点とエッジは具体的には実際のデータに基づいているため、頂点としての交差点とエッジとしての交差点と別の交差点を簡単に言えば、私のアプリケーションのグラフ全体は私の都市の道路網です。

ここでの問題は、ある交差点から別の交差点までの距離と、ある交差点から別の交差点までの時間に基づいてエッジの重みを計算する際のアルゴリズムまたは算術方程式をまだ思いつかないことです。

4

1 に答える 1

1

何を最適化するかによって異なります (ユーザーに選択させることもできます)。

最短ルートが必要な場合、エッジのコストは単に通りの長さです。

最速のルートが必要な場合、コストは道路を移動する予想時間になります。

燃料消費の観点から最も経済的なルートが必要な場合、コストは「道路の長さ/ガロンあたりのマイル (予想速度)」になります。

燃費は車によって異なりますが、経済性 (ガロンあたりのマイル数) は、特定の速度まで速度が上がると直線的に増加し、その後低下し始めると想定できます[ Wikipedia ]。常に最大速度よりも遅く移動できるため。速度、一定の効率を仮定します。(miles/gallon) / (miles/hour) = (hours/gallon)であるため、コストは時間にほぼ比例し、車の最も効率的な速度 (ユーザーが入力できます) で速度制限が適用されます。

準備された渋滞データのソースがある場合は、それを使用して予測される車の速度を決定します。

車を観察して予想移動時間を測定する方法の 1 つは、過去 {間隔} (時間? 分? 最後の車だけ? 最後の 10 台の車?) に通りを離れたすべての車の平均を取ることです。ただし、これで混雑がすぐに解消されるわけではありません。速度にまだ存在するすべての車の平均速度を取得できます。ただし、これは信号機の影響を過大評価します。

過去 1 時間に通りに出たすべての車の平均速度を求めることができます。average(distance traveled/time spent)またはaverage(distance traveled)/average(time spent)。通りに人がいない場合は、単純に制限速度を取るか、測定間隔を長くしてください。

予想される速度は両方向で異なる可能性があることに注意してください (データ ソースによって異なります)。そのため、常に有向エッジのペアを使用し、各方向を個別に測定してください。

[1] http://en.wikipedia.org/wiki/File:Fuel_economy_vs_speed_1997.png

于 2012-10-14T09:13:38.080 に答える