最短路プロジェクト 共同研究 中間報告 2007年 10月 久保　幹雄.

Presentation on theme: "最短路プロジェクト 共同研究 中間報告 2007年 10月 久保　幹雄."— Presentation transcript:

1 最短路プロジェクト 共同研究 中間報告 2007年 10月 久保　幹雄

2 プロジェクト概要 階層化メッシュ 疎化法 高速化＋ 拡張モデル ・a priori strategy
クエリ高速化 前処理による 階層化メッシュ 疎化法 2次元ビットベクトル法 モデルの拡張 時刻依存 多目的 確率的 動的 高速化＋ 拡張モデル ・a priori strategy ・robust optimization メモリ階層の考慮

3 メモリ階層を考慮した高速化 従来の「前処理＋クエリ」アルゴリズム 数GBの主記憶にネットワークデータ＋補助データが保管されていることを仮定
実際には．．． レベル１キャッシュ 1ナノ秒 KB レベル2キャッシュ 10ナノ秒 KB 主記憶 ナノ秒 MB-GB フラッシュ，ディスク 10ミリ秒 数GB

4 Transit Pointsへの最短路木（数十K）
メモリ階層と最短路クエリ ２０００万点の ネットワーク 補助データ フラッシュ ディスク 主記憶 キャッシュ クエリに必要な 補助データ 最短路 2次元ビットベクトル法 領域間のネットワーク（数K） Transit Pointsへの最短路木（数十K）

5 拡張モデル 従来の最短路モデルをナビ用に拡張する． 時刻依存最短路 高速費用（＋時刻依存）の考慮 多目的 渋滞情報と動的確率的最短路

6 時刻依存の移動時間をもつ最短路 時間帯別の平均速度の情報が利用可能
現在の商用システムでは，現時点における各道路の移動時間の推定値をもとに，最短路を計算 道路だと追い越し不可（FIFO）で待ちは許さない （no-wait）　⇒Dijkstra法の自明な拡張

7 時刻依存最短路 お客さん この先はいつも ８時から９時は 渋滞ですよ 現在時刻 現在の時速＝４０ｋｍ 到着時＝２０km
現状のナビゲーションでは現在時刻での最短時間パス ->到着時の時速を予測し，時刻依存の最短時間パス

8 解法のアイディア 移動時間のかわりに到着時刻関数を使う ->通常のダイクストラ法と（ほぼ）同じ計算量の解法

9 時刻依存の移動費用 深夜割引（30%）：午前０時～午前４時の間の走行
早朝・深夜割引（50%）：夜間22時～翌6時までの間に 大都市近郊区間を利用し、かつ総利用距離が100km以内 通勤割引（50%）：朝夕の通勤時間帯（朝6～9時または夕方17時～20時の間）に入口もしくは出口料金所を通過し、かつ総利用距離が100km以内（大都市近郊区間は除く） 重複適用不可．他に社会実験と称した特例あり．

10 通勤割引の例 http://www.go-etc.jp より引用
通勤割引の例　 より引用 割引適用回数を 状態空間に保管する

11 土日祝日 20:00-22:００にＩＣを通過 50% オフ

12 検索したルートに対してETC割引料金を表示した例（MapFan HP）

13 時刻依存の移動費用をもつ 最短路 移動時間の場合と異なり，待ちを許す． 発時刻も変数として扱う可能性あり． => NP-hard
現在のシステムでは，求めた最短時間路に対して費用を計算するだけ． 高速ネットワークのみ時刻依存の移動費用を付加したアルゴリズムの提案

14 時刻依存の移動費用をもつ 最短路アルゴリズム (1)
高速ネットワーク（完全有向グラフ） 料金所 発時刻固定

15 時刻依存の移動費用をもつ 最短路アルゴリズム (2)
待ちを 表す枝 到着時刻関数より 着時刻計算 　=>枝の費用が決まる （e.g., 9:00前なら通勤 割引が適用される） 6:00 時間 移動費用が変化する切れ目の時刻

16 発時刻が変数のとき 2次元ビットベクトル法などで求めた 経由点（Transit Nodes) 着時刻を切れ目の 時刻とした逆向きの最短路
移動費用が変化する切れ目の時刻

17 多目的の最短路問題 現実では意思決定者は最短時間のパスより，種々の目的のバランスを要求
移動時間，費用（高速，ガソリン），距離，移動時間のばらつき，安全性，運転のしやすさなど，複数の目的を有する最短路問題 大規模問題でも大丈夫な近似アルゴリズムの開発 　・目的関数のスカラー化による解法 　・メタ解法 厳密解法（動的計画） ユーザの指定したターゲット値を用いた解法（劣勾配法）

18 スカラー化による非劣解の 部分集合の生成

19 動的計画 点上の情報（状態空間）として， （到着時刻，費用，通勤割引適用回数，右折回数，・・・） を保持 非劣解を除去しながら探索
二次元ビットベクトル法によって疎化されたグラフと共通する点をもつ高速道路グラフ上で探索

20 劣勾配法 各指標のターゲット値（ユーザーが指定）からの逸脱をペナルティとして，目的関数に組み込む
二次元ビットベクトル法による疎化グラフ上で探索 パスが決まれば高速料金が決まるので，メタ解法で探索しながら，料金を評価

21 確率的最短路 渋滞情報の分類 なぜ渋滞しているのか？ =>双方向通信により入手可能 自然渋滞（毎度，この地点は渋滞する）
事故渋滞（どの程度の規模の事故か？何分くらいで復旧するのか？） 工事渋滞（どの程度の工事規模か？何時から何時まで行うのか？） 天候渋滞（豪雨のためのスピード低下） その他のイベント渋滞 =>双方向通信により入手可能

22 分類ごとの情報の違い 自然：予測可能だが，ばらつき大．
事故：事故の事前予測は困難だが，発生した事故の復旧までの時間は，事故の規模と発生地点から予測可能 工事：事前に通知されているが，どの程度の渋滞が発生するかは予測する必要がある． 天候：天気予報からある程度は分かるが，渋滞に与える影響は予測する必要がある．

23 対処法 動的確率的時刻依存最短路として定式化
再ルート計算の可否（ルートの先の方なら変更可能だが，目先のルートの頻繁な更新は避ける） =>ローリング・ホライズン方式におけるfreezing 事故渋滞 => 寿命モデル（発生時から終了時までの時間の予測） 他の渋滞 =>外部情報から道路速度の予測の精度の向上

24 拡張モデルに対する前処理 時刻依存：発時刻をサンプリング 多目的：目的間の重みをスカラー化法で決定
確率的：確率分布の推定が困難 & 生起可能なシナリオの数が膨大 ＝＞ロバスト最適化

25 ロバスト最短路による前処理 (1) G=(V,E), 枝(i,j)に対して移動時間の幅 [Lij,Uij]
実現したシナリオ R に対して移動時間 Tij(R) ∈ [Lij,Uij] が定まる． シナリオの数が膨大！=> 現在の最短路 P に対する最も悪いシナリオを順次生成 Pに含まれる枝が最大値，その他の枝が最小値

26 ロバスト最短路による前処理 (2) Bertsimasのロバスト最短路モデル （高々Γ本の枝の長さが増加する）
双対定理を用いて，増加量 Uij-Lijがθ以上の枝だけ移動時間を Uij として最短路を解く問題に帰着． ロバストな a priori network: 様々なΓに対して使われる最短路の和集合 =>様々なθに対する最短路の和集合

27 再最適化の利用 初期最短路：θ=0（すべての枝を上限値としたネットワーク上で最短路を解く）
次の閾値までθを増やす=> 幾つかの枝の距離が減少する => 再最適化の手法により計算量削減

28 再最適化 １つの点 s に接続する枝の距離が減少： s に入る枝の最小の被約費用を点のポテンシャル p(s) とする．
s からでる枝(s,j)のポテンシャルを p(s)+被約費用(s,j) とする． 他の点のポテンシャルを0とする． 負のポテンシャルの点がなくなるまで，被約費用を枝長としたDijkstra法を行う．

29 ロバスト a priori network の例 （最悪シナリオ生成法1）
[10,16] [1,4] [1,5] [3,3] t s [2,4] [3,5] [2,3] [20,23] [Lij,Uij] 下限値を用いた最短時間路を求める

30 ロバスト a priori network の例 （最悪シナリオ生成法2）
16 4 5 最短時間路 [3,3] t s [2,4] [3,5] [2,3] [20,23] 最短路上の枝だけを上限値に固定，それ以外を下限値 にして最短路を求解

31 ロバスト a priori network の例 （最悪シナリオ生成法3）
16 4 5 最短時間路 [3,3] t s 4 [3,5] 3 [20,23] 最短路上の枝だけを上限値に固定，それ以外を下限値 にして最短路を求解 解が変わらないので終了

32 ロバスト a priori network の例 （Bertsimasモデルによる方法1）
[10,16] [1,4] [1,5] [3,3] t s [2,4] [3,5] [2,3] [20,23] [Lij,Uij] 下限値を用いた最短時間路を求める．

33 ロバスト a priori network の例 （Bertsimasモデルによる方法2）
16 [1,4] [1,5] [3,3] t s [2,4] [3,5] [2,3] [20,23] 幅の大きいものから上限値に変えて，最短路を求める．（変化なし）

34 ロバスト a priori network の例 （Bertsimasモデルによる方法3）
16 [1,4] 5 [3,3] t s [2,4] [3,5] [2,3] [20,23] 幅の大きいものから上限値に変えて，最短路を求める．（以下同様；ネットワーク変化なし）