最短路プロジェクト 共同研究 中間報告 2007年 10月 久保 幹雄 プロジェクト概要 前処理による クエリ高速化 階層化メッシュ 疎化法 2次元ビット ベクトル法 モデルの拡張 時刻依存 多目的 確率的 動的 メモリ階層の考慮 高速化＋ 拡張モデル ・a priori strategy ・robust optimization メモリ階層を考慮した高速化 • 従来の「前処理＋クエリ」アルゴリズム 数GBの主記憶にネットワークデータ＋補 助データが保管されていることを仮定 • 実際には．．． レベル１キャッシュ 1ナノ秒 10 KB レベル2キャッシュ 10ナノ秒 512KB 主記憶 100ナノ秒 MB-GB フラッシュ，ディスク 10ミリ秒 数GB メモリ階層と最短路クエリ ２０００万点の ネットワーク フラッシュ ディスク 主記憶 キャッシュ 補助データ クエリに必要な 補助データ 最短路 2次元ビットベクトル法 領域間のネットワーク（数K） Transit Pointsへの最短路木（数十K） 拡張モデル 従来の最短路モデルをナビ用に拡張する． • 時刻依存最短路 • 高速費用（＋時刻依存）の考慮 • 多目的 • 渋滞情報と動的確率的最短路 時刻依存の移動時間をもつ最短路 • 時間帯別の平均速度の情報が利用可能 • 現在の商用システムでは，現時点における各道 路の移動時間の推定値をもとに，最短路を計算 • 道路だと追い越し不可（FIFO）で待ちは許さない （no-wait） ⇒Dijkstra法の自明な拡張 時刻依存最短路 お客さん この先はいつも ８時から９時は 渋滞ですよ 現在時刻 現在の時速＝４０ｋｍ 到着時＝２０km 現状のナビゲーションでは現在時刻での最短時間パス ->到着時の時速を予測し，時刻依存の最短時間パス 解法のアイディア • 移動時間のかわりに到着時刻関数を使う ->通常のダイクストラ法と（ほぼ）同じ計算量の解法 時刻依存の移動費用 • 深夜割引（30%）：午前０時～午前４時の間の走行 • 早朝・深夜割引（50%）：夜間22時～翌6時までの間 に 大都市近郊区間を利用し、かつ総利用距離が 100km以内 • 通勤割引（50%）：朝夕の通勤時間帯（朝6～9時ま たは夕方17時～20時の間）に入口もしくは出口料 金所を通過し、かつ総利用距離が100km以内（大 都市近郊区間は除く） 重複適用不可．他に社会実験と称した特例あり． 通勤割引の例 http://www.go-etc.jp より引用 割引適用回数を 状態空間に保管する 土日祝日 20:00-22:００にＩＣを通過 50% オフ 検索したルートに対してETC割引料金を表示した例（MapFan HP） 時刻依存の移動費用をもつ 最短路 • 移動時間の場合と異なり，待ちを許す． • 発時刻も変数として扱う可能性あり． => NP-hard • 現在のシステムでは，求めた最短時間路 に対して費用を計算するだけ． • 高速ネットワークのみ時刻依存の移動費 用を付加したアルゴリズムの提案 時刻依存の移動費用をもつ 最短路アルゴリズム (1) 料金所 発時刻固定 高速ネットワーク （完全有向グラフ） 時刻依存の移動費用をもつ 最短路アルゴリズム (2) 待ちを 表す枝 6:00 時間 到着時刻関数より 着時刻計算 =>枝の費用が決まる （e.g., 9:00前なら通勤 割引が適用される） 移動費用が変化する切れ目の時刻 発時刻が変数のとき 2次元ビットベクトル法などで求めた 経由点（Transit Nodes) 着時刻を切れ目の 時刻とした逆向きの最短路 移動費用が変化する切れ目の時刻 多目的の最短路問題 • 現実では意思決定者は最短時間のパスより，種々 の目的のバランスを要求 • 移動時間，費用（高速，ガソリン），距離，移動時間 のばらつき，安全性，運転のしやすさなど，複数の 目的を有する最短路問題 • 大規模問題でも大丈夫な近似アルゴリズムの開発 ・目的関数のスカラー化による解法 ・メタ解法 • 厳密解法（動的計画） • ユーザの指定したターゲット値を用いた解法（劣勾 配法） スカラー化による非劣解の 部分集合の生成 費用 時間 動的計画 • 点上の情報（状態空間）として， （到着時刻，費用，通勤割引適用回数，右 折回数，・・・） を保持 • 非劣解を除去しながら探索 • 二次元ビットベクトル法によって疎化され たグラフと共通する点をもつ高速道路グラ フ上で探索 劣勾配法 • 各指標のターゲット値（ユーザーが指定） からの逸脱をペナルティとして，目的関数 に組み込む • 二次元ビットベクトル法による疎化グラフ 上で探索 • パスが決まれば高速料金が決まるので， メタ解法で探索しながら，料金を評価 確率的最短路 渋滞情報の分類 • なぜ渋滞しているのか？ – 自然渋滞（毎度，この地点は渋滞する） – 事故渋滞（どの程度の規模の事故か？何分く らいで復旧するのか？） – 工事渋滞（どの程度の工事規模か？何時から 何時まで行うのか？） – 天候渋滞（豪雨のためのスピード低下） – その他のイベント渋滞 • =>双方向通信により入手可能 分類ごとの情報の違い • 自然：予測可能だが，ばらつき大． • 事故：事故の事前予測は困難だが，発生した 事故の復旧までの時間は，事故の規模と発 生地点から予測可能 • 工事：事前に通知されているが，どの程度の 渋滞が発生するかは予測する必要がある． • 天候：天気予報からある程度は分かるが，渋 滞に与える影響は予測する必要がある． 対処法 • 動的確率的時刻依存最短路として定式化 • 再ルート計算の可否（ルートの先の方なら 変更可能だが，目先のルートの頻繁な更 新は避ける） =>ローリング・ホライズン方 式におけるfreezing • 事故渋滞 => 寿命モデル（発生時から終了 時までの時間の予測） • 他の渋滞 =>外部情報から道路速度の予 測の精度の向上 拡張モデルに対する前処理 • 時刻依存：発時刻をサンプリング • 多目的：目的間の重みをスカラー化法で決 定 • 確率的：確率分布の推定が困難 & 生起可能なシナリオの数が膨大 ＝＞ロバスト最適化 ロバスト最短路による前処理 (1) • G=(V,E), 枝(i,j)に対して移動時間の幅 [Lij,Uij] • 実現したシナリオ R に対して移動時間 Tij(R) ∈ [Lij,Uij] が定まる． • シナリオの数が膨大！=> 現在の最短路 P に対する最も悪いシナリオ を順次生成 Pに含まれる枝が最大値，その他の枝が最小値 ロバスト最短路による前処理 (2) • Bertsimasのロバスト最短路モデル （高々Γ本の枝の長さが増加する） • 双対定理を用いて，増加量 Uij-Lijがθ以上の 枝だけ移動時間を Uij として最短路を解く問 題に帰着． • ロバストな a priori network: 様々なΓに対して使われる最短路の和集合 =>様々なθに対する最短路の和集合 再最適化の利用 • 初期最短路：θ=0（すべての枝を上限値とし たネットワーク上で最短路を解く） • 次の閾値までθを増やす=> 幾つかの枝の距離が減少する => 再最適化の手法により計算量削減 再最適化 • １つの点 s に接続する枝の距離が減少： – s に入る枝の最小の被約費用を点のポテンシ ャル p(s) とする． – s からでる枝(s,j)のポテンシャルを p(s)+被約 費用(s,j) とする． – 他の点のポテンシャルを0とする． – 負のポテンシャルの点がなくなるまで，被約費 用を枝長としたDijkstra法を行う． ロバスト a priori network の例 （最悪シナリオ生成法1） [10,16] [1,4] [1,5] [3,3] t [2,4] s [3,5] [2,3] [20,23] [Lij,Uij] 下限値を用いた最短時間路を求める ロバスト a priori network の例 （最悪シナリオ生成法2） 16 5 4 最短時間路 [3,3] t [2,4] s [3,5] [2,3] [20,23] 最短路上の枝だけを上限値に固定，それ以外を下限値 にして最短路を求解 ロバスト a priori network の例 （最悪シナリオ生成法3） 16 5 4 最短時間路 [3,3] t 4 s [3,5] 3 [20,23] 最短路上の枝だけを上限値に固定，それ以外を下限値 にして最短路を求解 解が変わらないので終了 ロバスト a priori network の例 （Bertsimasモデルによる方法1） [10,16] [1,4] [1,5] [3,3] t [2,4] s [3,5] [2,3] [20,23] [Lij,Uij] 下限値を用いた最短時間路を求める． ロバスト a priori network の例 （Bertsimasモデルによる方法2） 16 [1,4] [1,5] [3,3] t [2,4] s [3,5] [2,3] [20,23] 幅の大きいものから上限値に変えて，最短路を 求める．（変化なし） ロバスト a priori network の例 （Bertsimasモデルによる方法3） 16 [1,4] 5 [3,3] t [2,4] s [3,5] [2,3] [20,23] 幅の大きいものから上限値に変えて，最短路を 求める．（以下同様；ネットワーク変化なし）
© Copyright 2024 ExpyDoc
