最短路問題とその拡張久保幹雄東京海洋大学プロジェクト概要 • 大規模最短路問題に対する高速アルゴリズム目標：2000万点を対象とした実問題例を一瞬で，かつ厳密に解く！ターゲットは米国と欧州（データは無償で提供される；日本のは無償） • 最短路問題の実務的な拡張に関する研究 – – – – 時刻依存の移動時間をもつ最短路不確実性をもつ移動時間をもつ最短路多目的を有する最短路制約付き最短路 ⇒これらの拡張に対しても，高速アルゴリズムが必要ディズニーランドからダラス空港までの最短路（Google Earthで数秒）大規模問題に対するアルゴリズム（現状調査） 1. 2. 3. 4. 5. A*探索（古典）両方向探索（古典）到達限界（reach）を事前に計算しておく方法多階層のネットワークを作成しておく方法到達点に最短で行くためには使用しない枝の情報（ビットベクトル）を利用する方法 ⇒実装が容易でまずまずの効果前処理（preprocessing）とクエリ（query）を分離することによって，高速なクエリを達成前処理とクエリの分離（１）２０００万点のネットワーク最短路ダイクストラ法１回（数十秒）旧来の方式前処理とクエリの分離（２）前処理（preprocessing）２０００万点のネットワーク補助データダイクストラ法たくさん（数時間；並列で数分）クエリ（query）補助データ最短路２０００万点のネットワーク高速探索（数ミリ秒）開発したアルゴリズム • ビットベクトル法の改良 – アイディア：１次元ベクトルを２次元にする – １次元と同じオーダーの計算時間で構成可能（ここに新案） – 終点を含む領域内での無駄な探索を減らす – クエリ時に必要なメモリが少ない – 実験結果ビットベクトルを用いた解法の例探索範囲の限定による高速化が実現問題点：特許が出されている２次元ビットベクトル法例)West Virginia州 (300146点 ) 前処理なし 292557 97.5% 1D前処理 2D前処理 7634 2.5% 5918 2.0% 従来の方法提案法時刻依存の移動時間をもつ最短路 • 時間帯別の平均速度の情報が利用可能 • 現在の商用システムでは，現時点における各道路の移動時間の推定値をもとに，最短路を計算 • 道路だと追い越し不可（FIFO）で待ちは許さない（no-wait） ⇒Dijkstra法の自明な拡張（１対全の最短路を想定） • P2P型に対する高速なアルゴリズムの開発（前処理＋クエリ）時刻依存最短路お客さんこの先はいつも８時から９時は渋滞ですよ現在時刻現在の時速＝４０ｋｍ到着時＝２０km 現状のナビゲーションでは現在時刻での最短時間パス ->到着時の時速を予測し，時刻依存の最短時間パス解法のアイディア • 移動時間のかわりに到着時刻関数を使う ->通常のダイクストラ法と（ほぼ）同じ計算量の解法不確実性な移動時間をもつ最短路問題 • 道路のIT化により，道路の移動速度の予測が可能になりつつある • ただし予測なので，当たるも八卦（不確実性をもつ） • 現在の商用システムでは，現在の走行時間の推定値を用いて最短路を計算 • 確率計画を用いた研究もあるが大規模問題では実用的でない • ロバスト最適化：移動時間がある範囲内で変化しても到着予定時刻が大きく変わることがない，いわゆる頑強な最短路を求めるロバスト最短路混んでなければ１時間ですが，渋滞に巻き込まれると３時間かかりますよ１時間では無理ですが，悪くても２時間あればつきますよ多目的の最短路問題 • 現実では意思決定者は最短時間のパスより，種々の目的のバランスを要求 • 移動時間，費用（高速，ガソリン），距離，移動時間のばらつき，安全性，運転のしやすさなど，複数の目的を有する最短路問題 • 大規模問題でも大丈夫な近似アルゴリズムの開発・目的関数のスカラー化による解法（すべての非劣解が求まる訳ではない）・メタ解法の開発多目的最短路（１）高速を使えば１時間で着くけど，お金がかかるなー１万円，５０分０円，１００分１万円，１０分０円，２０分多目的最短路（２）費用２万２万円，６０分１万円，７０分１万円，１１０分（優越されている）０円，１２０分 60分１万円，５０分０円，１００分１万円，１０分０円，２０分時間スカラー化による非劣解の部分集合の生成費用時間 30×30の格子グラフの非劣解 2500 2400 2300 2200 2100 2000 1900 1800 1700 1600 1500 3500 3700 3900 4100 4300 4500 4700 4900 どちらが良いか分からない！ユーザーが選べない！ -> 制約付き最短路，目標計画 5100 5300 制約付き最短路に対する誘導局所探索 750 700 時間制約=1400 反復 1000 回 650 600 550 500 1000 1100 1200 1300 1400 1500 1600 今後の方針 • 並列計算機を用いた前処理の高速化（産総研のスーパークラスター利用） • メタ解法の開発 • アルゴリズム開発（２次元ビットベクトル法以外） • 拡張モデル（確率的＋時刻依存＋多目的）