- 著者
-
飯村 伊智郎
加藤誠巳
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.35, no.12, pp.2831-2841, 1994-12-15
- 被引用文献数
-
6
2
近年車載ナビゲーション・システムの普及が著しいが、目的地までの最適経路を提供するものは少ない。最適経路を算出するためには道路ネットワーク・データを必要とするが、例えば(財)日本デジタル遺路地図協会の作成した目本全国の基本遺路は約23万個のノード、約52万本のリンクより成り、その経路探索用データのデータ容量は約8MBと大きく、ディスクヘのアクセス・読み込み時間、探索を実行するために必要なRAM領域,ならびにCPU時間が増大し、実用に耐えなくなることがある。従来からこれらの問題点を解決するためいくつかの方法が提案されているが、種々の問題点があった。本論文では日本全国の道路ネットワークを復数個の領域に分割し、任意の2つの領域間の最適経路を算出するために必要にして十分な領域の集合をオフラインで算出してテーブル化することにより上述の問題点を解決している。このようなルックアップ・テーブルを用いることそれ自体は審易に考え得るところであるが、本論文ではこれを日本全国の道路網に対し実際に適用した場合について、実用的な領域分割数を明らかにすると共に、領域分割の仕方として郡レベルの行政区域に分割すると、テーブル作成に要する時間を多少なりと減少させるのに有利であることを示している、すなわち郡レベルの行政界は一般に河川や山脈等の地形的特性と密接な関係を有していることが多く、このような行政区界を横切る道路は少ないと考えられるためである。本論文ではこのように領域分割の仕方に一つの示唆を与えると共に、ここで採用したルックアップ・テーブル法により探索頒域を限定した経路探索法が、やはり最適経路を与えることが保証されている従来のDijkstra法およびA*アルゴリズムと比較し、総所要時間および必要とするRAM容量の面で現用のハードウェァの下では大幅に有利であることを示している。