最短路プロジェクト - 久保's ホームページ

最短路アルゴリズムとその応用に関する研究プロジェクトです．

大規模最短路問題に対する高速アルゴリズム

通常の教科書に掲載されている最短路アルゴリズムは，1つの点から他のすべての点（もしくは他のすべての点から1つの点）への最短路を求めることを目的としたものである．これについては，研究しつくされた感がある．道路ネットワークを想定した最短路問題は，非負の枝長をもつ点対点（Point-to-Point: P2P）最短路問題となる．道路ネットワークの規模はヨーロッパで 2000万点，北米で 3000万点のものが整備されており，これらの大規模ネットワークを想定し，高速な最短路アルゴリズムを開発することを目的とする．

メモリ階層を用いた高速化

計算機は，レジスタ，L1メモリ，L2メモリ，RAM，HDやフラッシュのように，速度が異なる階層構造の記憶装置から構成される．本研究では，このようなメモリの階層構造を利用した最短路問題に対する高速プログラムを設計する．

時刻依存の移動時間をもつ最短路

道路ネットワークのデータには，制限速度と平均速度が入っている．実際には，道路を通過する時間帯によって速度は大きく変化するので，それを考慮した最短路アルゴリズムが必要になる．現在の商用システムでは，現時点における各道路の移動時間の推定値をもとに，最短路を計算していると思われる．道路を通過する予定時刻における移動時間を考慮したモデルは，時刻依存の移動時間をもつ最短路問題（time-dependent shortest path）とよばれ，幾つかの研究があるが，ここではP2P型の最短路問題を想定し，高速なアルゴリズムを開発する．

不確実性をもつ移動時間をもつ最短路

実際には将来の時点における速度は予測値であり，正確な値は分からない．このような不確実性を正確に（確率計画として）取り扱うことは，ネットワークの規模やデータの精度から考えると，現実的には難しい．ここでは，ロバスト最適化とよばれる比較的新しい枠組みを利用することによって，現実的な計算時間とデータで，不確実性を（近似的にではあるが）考慮する方法を提案する．

多目的を有する最短路

我が国のネットワークの特徴として高速道路がすべて有料であることがあげられる（欧米でも一部の道路は有料である）．そのため，実際には最短時間路ではなく，費用も考慮した最短路が要求される．ここでは，移動時間と費用，さらには上で取り上げた移動時間の期待値とばらつきなど，複数の目的を有する最短路問題を取り上げ，高速なアルゴリズムを開発する．

本プロジェクトは，2006-2007にかけて船井電機（株）によってサポートされていました．現在，スポンサーを募集中です．

ドキュメント類

Levelwise Mesh Sparsification for Shortest Path Queries, Takeaki Uno, Yuichiro Miyamoto, and Mikio Kubo （draft) PDF
SSOR発表用スライド PPT
2007 中間報告（2-dim. bit vector, LMS, 関連特許など） PPT
2007 中間報告（メモリ階層，時刻依存，多目的，動的など） PPT
2次元ビットベクトルのPythonによる実装 PPT
2007年最終報告書 PDF
2007年最終報告会資料 PPT

プログラム類

Levelwise Mesh Sparsification 　C
Dial法（宮本作） C
Dial法（高速化版） C
Transit Node Routingと分割プログラム（Python+networkX） python（zip圧縮）