4

地点 A から地点 B に行きたいとします。Google 乗換案内を使用すると、次のように表示されます。

Route 1:
1. Wait 5 minutes
2. Walk from point A to Bus stop 1 for 8 minutes
3. Take bus 69 till stop 2 (15 minues)
4. Wait 2 minutes
5. Take bus 6969 till stop 3(12 minutes)
6. Walk 7 minutes from stop 3 till point B for 3 minutes.

合計時間 = 5 待機 + 40 分。

Route 2:
1. Wait 10 minutes
2. Walk from point A to Bus stop I for 13 minutes
3. Take bus 96 till stop II (10 minues)
4. Wait 17 minutes
5. Take bus 9696 till stop 3(12 minutes)
6. Walk 7 minutes from stop 3 till point B for 8 minutes.

合計時間 = 10 待機 + 50 分。

全体として、国道 1 号線の方がずっと良く見えます。しかし実際には、69 番バスが交通渋滞で 3 分遅れており、結局 6969 番バスに乗り遅れてしまいます。次の 6969 番バスは少なくとも 30 分後に来るため、5 待ち時間 + 70 分 (30 m を含む)寒さや暑さの中で待ちます）。Google が実際にこの可能性を宣伝してくれたらいいと思いませんか? 私の質問は次のとおりです。スケジュールの不確実性を考慮して、上位 3 つのルートを表示するためのより良いアルゴリズムは何ですか?

ありがとう！

4

5 に答える 5

3

さまざまな種類の旅の要素の不確実性のレベルを表す重み付けを追加するのはどうでしょうか。

ダブリン市のバス サービスはタイムリーではないことで有名です。ダブリン バスのスケジュールに関係するあらゆることに 40% の誤差を加えることができ、最良と最悪のシナリオが示されます。ラッシュアワーの慢性的な交通渋滞も考慮に入れることができます。その後、ユーザーは、実際に接続できる可能性が 20% または 80% であることがわかります。

「最も正しい」要因で「最良」の旅を並べ替え、ユーザーに表示される結果にこのデータを含めることができます。

私の2セント:)

于 2010-02-11T00:59:03.423 に答える
2

英国の鉄道システムでは、各インターチェンジ ノードに「許容される最小乗り換え時間」が関連付けられています。ここでのルート プランナーへのインターフェイスには、ユーザーがデフォルトを受け入れるか、30 分の増分を追加できるようにする詳細オプションがあります。

あなたの例では、ステップ 2 で「許可する最小転送時間」を 10 分に設定すると、示されているようにルート 1 が提案されなくなります。もちろん、これは最短移動時間が長くなることを意味しますが、それはトレードオフです。

于 2010-02-11T11:36:34.877 に答える
1

経験的に。実際の到着時間と予定の到着時間を記録し、それぞれの平均と標準偏差を計算します。可能なルートを検討するときは、特定の区間の到着が遅れて次の区間に乗り遅れる確率を計算し、平均待ち時間を としP(on time)*T(first bus) + (1-P(on time))*T(second bus)ます。複数のレグを考慮しなければならない場合、これはさらに複雑になります。それぞれが独立して遅れる可能性があり、次のレグを逃す可能性がある複数の可能性がありますが、一般的な原則は成り立ちます。

于 2010-02-11T11:24:14.137 に答える
1

不確実性を考慮に入れると、「最適なルート」はなくなりますが、代わりに、移動の合計時間を最小限に抑える「最適な戦略」が存在する可能性があります。しかし、それは一連の指示として表すことはできず、より一般的な計画の形式に近いものです。つまり、「バスステーション X に行き、バス Y を 10:00 まで待ってください。バスが到着しない場合は、駅まで歩いてください。」 Z..." これは、ユーザーに提示するのが非常に難しいことで有名です (さらに、作成には計算コストがかかります)。

命令の固定シーケンスについては、それが実際にうまくいく確率を計算することができます。しかし、ユーザーが受け入れたいと思う確実性のレベルはどうなるでしょうか? たとえば、80% の成功率で満足できますか? 次に接続の 1 つを逃すと、最悪の場合、トランプの家は崩壊します。

私は何年もの間、フィンランドの長距離バスの移動を計算する同様のプログラムを作成しましたが、すべてのバスがスケジュールどおりに運行されていると仮定して、乗り換え時間を報告しました。その後、基本的に乗り換え時間が 15 分未満のすべての計画は、リスクが高すぎるため無視されました (特定のルートで 1 日に 1 つか 2 つの長距離バスしかないこともありました)。

于 2010-02-11T02:15:38.260 に答える
1

壊滅的な障害は、最初のチェックである必要があります。

これは、ルートの重要な部分であるその日の最後のバスに接続しようとしている場合に特に重要です。ライダーは、それが起こっていることを知る 必要があります。そうすれば、気が散りすぎず、リスクを知ることができます。

その後、最悪の場合のシングル ミスを評価できます。

そして、あなたが本当に夢中になりたいのなら、待機場所がある近所やトランジットステーションの犯罪統計を見てみましょう.

于 2010-02-11T11:30:44.137 に答える