概要

　最短経路を高速に算出する方法を開発しています。
　与えられた地図データなどに対して前処理を施し補助的なデータを用意することによって、従来のダイクストラ法よりも少なくとも1000倍以上速く（最適性が保証された）最短経路を計算できます。
　これは有名なA＊アルゴリズムでは到底追いつけないほどのスピードアップです。
　しかも、使用するメモリ量は普通にダイクストラ法で計算する場合とさほど変わりません。
　同様の研究（アルゴリズム開発）は主にドイツで先行して研究されましたが、我々のアルゴリズムはそれら先行研究と比べてとてもシンプルであり、とても実装しやすいものとなっています。

応用例

カーナビゲーションシステムにおける最短路検索や、Web上での経路検索に応用できます。
道路網だけでなく、鉄道などの交通機関の乗り換えを考慮した経路検索にも使えます。

今後の発展性

現在は、普通の最短路を高速に検索出来るだけですが、複雑な制約条件が盛り込まれた最短路や多目的最短路を高速に検索できるようアルゴリズムを改善する予定です。
また、計算時に使用するメモリ量のさらに少なくすることも目指しています。

研究設備

研究設備として特筆するべきものはありません。普通のパソコンを使っています。
普通程度のパソコンを用いて高性能コンピューターを使っている人以上の結果を出すことが、アルゴリズム研究の醍醐味です。

共同研究・外部機関との連携への期待

すでに実用化されている最短経路検索システムへの本手法の適用、新しい応用分野の発見、など。

関連特許・論文等

• Yuichiro MIYAMOTO, Takeaki Uno and Mikio KUBO. Levelwise mesh sparsification for shortest path queries. In Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC2010), Lecture Notes in Computer Science 6506, Springer, pp. 121-132.
• 特許第4997597号（最短経路探索方法）