（アーカイブ）所要時間ベース旅客経路探索仕様案

⚠現行の所要時間ベース旅客経路探索の仕様は、所要時間ベース旅客経路探索についてを参照してください。⚠

目的

ある路線において優等列車が運行されている場合、一般に旅客等は優等列車を必要に応じて活用して、期待される所要時間が最小になるように経路選択を行う。
しかし、現行のSimutrans standard系ではRoute Costによって経路選択が行われており、優等列車が有効に活用されにくい。優等列車を活用しやすくする様々なRoute Cost調整機能が実装されているが、どれも万能ではない。

そこで、Extendedのように所要時間ベースにするオプションをもうけたい。ただし、Extendedでは厳密なフィードバックを実装した結果経路選択の振動現象が見られることが知られている。したがって、優等列車を適切に利用する安定的な経路選択が行われるロジックを実装することを目的とする。

概要

優等列車が有効に活用され、所要時間が最小になるよう経路選択が行われるためには、次の2つの要素について検討が必要である。

経路選択における経路グラフの重み基準

実績所要時間を使用する。実績所要時間 = 停留所での待機時間 + 移動時間

待機時間

同一目的地の積載対象物のかたまり（以下、パケットと呼ぶ）が列車に積載されるまでの時間を用いる。

1. パケットが停留所に到着する。パケットが停留所に到着した時間を記録しておく。
2. パケットを列車に積載する。このとき、積載されたパケットに対してパケットが待機した時間の加重平均を求める。これを1積載に対する待機時間とする。
3. 5積載分（？）の待機時間を記録し、その平均値を経路グラフにおける待機時間として用いる。（中央値を用いると、列車間隔が不均等な路線において待機時間が不安定になる。）

待機時間の実績がない場合は、待機時間0とする。

備考

• 待機時間のヒストリは、schedule_entry_t に対して蓄積する。
  • 列車の接続の良し悪しなどを考慮できる。
• 積むまで待機設定を使うと、積載されたタイミングと出発するタイミングは異なる。待機時間の算出には出発するタイミングが必要なので、haltが loading_here に対して積載したパケットを管理し、出発するタイミングで計算し、コミットする。
  • スケジュール変更などで正規ルート以外で発車した場合は、結果を破棄してよい。 loading_here に編成を追加するときに初期化するのがラク。

移動時間

OTRPではすでに停留所間の所要時間（移動時間）が過去5回分保存されているので、これを活用する。

• 現在はセーブデータに保存されていないので、保存するようにする。
• ticksのオーバーフロー対策を実装する
• 移動時間の記録のうち、中央値を採用する。
  • 何らかの要因により一時的に所要時間が伸びた場合、平均値だとその影響を受けて経路選択が不安定になってしまう。

移動時間の実績がない場合は、目的地までのユークリッド距離/路線の1番目の編成の最高速度を暫定値として用いる。

重み基準の更新タイミング

そこまで頻繁に更新する必要はない。計算コストを考えると、適度に減らしたい。

• 待機時間 ... 積載が発生した時
• 移動時間 ... 編成が停留所に到着した時
• スケジュールの変更時

計算コスト

• パケットの停留所到着時間記録 ... 停留所到着処理に対して定数時間
• パケット待機時間の加重平均算出 ... パケット積載処理に対して定数時間
• 経路グラフにおける待機時間の更新 ... 定数時間（5個の値の中央値を求める）
• 移動時間の中央値算出 ... 定数時間

最適経路の探索タイミング

standard由来のロジックから原則変更は行わない。

• 新規パケット（旅客）発生時
• パケットが停留所に到着した時（この場合、キャッシュが効く）
• スケジュールの変更や停留所の変更が発生した時

Extendedのような大規模なキャッシュテーブルの構築は行わない。従って、探索コストをRoute Cost法から極力増やさないことが必要。

停留所における積載ルール

• 現行は、目的の停留所にたどり着ける列車であれば、そこに至るまでの停車駅数に関わらず積載。
• 所要時間ベース経路選択においては、（待機時間を含め）最短時間で目的駅に到達できる路線の列車のみに積載する。
  • これをやらないと、急行に乗るべき客が先に来た各駅停車に乗り込んでしまう。
  • （混雑対策）ただし、積み残しを起こしたときは、積み残しが解消するまで積載路線の限定を取りやめる。（目的地に到達できるのであれば積載する。）
  • （懸念事項）これをやると、競合関係の路線があるときに、速いほうの路線が一人勝ちしてしまう。また、1系統を複数のスケジュールで構成してもそのうち1つのスケジュールだけに積載される。
    • 最短時間路線でなくても、期待到達時間がある一定以下であれば積載を認める？
      • 積載しようとしている路線の「移動時間」 < 最短距離路線の「待機時間 + 移動時間」　のとき
    • 有料特急にみんな乗ってしまう現象をどうするか？
• 積載しきれない時
  • standardの場合は"nearest first"ポリシに従って積載する。
  • OTRPはそれに加えて"first come first serve"ポリシを提供する。
  • 所要時間ベース経路選択においては、"first come first serve"ポリシのみ提供する。
    • 「停留所での待機時間」が経路選択に必要な情報になるが、"nearest first"では「停留所での待機時間」を測定できない。

検討事項

• 新幹線への集中を防ぐために、速度に応じて定数のペナルティをかける
  • 京都-新大阪間は新幹線を使ってほしくないが、大宮-仙台間は新幹線を使ってほしい。
• 有料特急への集中を防ぐ ... 定数ペナルティをスケジュールか車両に対してつける