最短路プロジェクトのホーム
最短路アルゴリズムとその応用に関する研究プロジェクトです.
通常の教科書に掲載されている最短路アルゴリズムは,1つの点から他のすべての点(もしくは他のすべての点から1つの点)への最短路を求めることを目的としたものである.これについては,研究しつくされた感がある.道路ネットワークを想定した最短路問題は,非負の枝長をもつ点対点(Point-to-Point: P2P)最短路問題となる.道路ネットワークの規模はヨーロッパで 2000万点,北米で 3000万点のものが整備されており,これらの大規模ネットワークを想定し,高速な最短路アルゴリズムを開発することを目的とする.
道路ネットワークのデータには,制限速度と平均速度が入っている.実際には,道路を通過する時間帯によって速度は大きく変化するので,それを考慮した最短路アルゴリズムが必要になる.現在の商用システムでは,現時点における各道路の移動時間の推定値をもとに,最短路を計算していると思われる.道路を通過する予定時刻における移動時間を考慮したモデルは,時刻依存の移動時間をもつ最短路問題(time-dependent shortest path)とよばれ,幾つかの研究があるが,ここではP2P型の最短路問題を想定し,高速なアルゴリズムを開発する.
実際には将来の時点における速度は予測値であり,正確な値は分からない.このような不確実性を正確に(確率計画として)取り扱うことは,ネットワークの規模やデータの精度から考えると,現実的には難しい.ここでは,ロバスト最適化とよばれる比較的新しい枠組みを利用することによって,現実的な計算時間とデータで,不確実性を(近似的にではあるが)考慮する方法を提案する.
我が国のネットワークの特徴として高速道路がすべて有料であることがあげられる(欧米でも一部の道路は有料である).そのため,実際には最短時間路ではなく,費用も考慮した最短路が要求される.ここでは,移動時間と費用,さらには上で取り上げた移動時間の期待値とばらつきなど,複数の目的を有する最短路問題を取り上げ,高速なアルゴリズムを開発する.