ルックアップ・テーブルにより探索領域を限定した日本全国道路網における経路探索手法
スポンサーリンク
概要
- 論文の詳細を見る
近年車載ナビゲーション・システムの普及が著しいが, 目的地までの最適経路を提供するものは少ない. 最適経路を算出するためには道路ネットワーク・データを必要とするが, 例えば(財)日本デジタル道路地図協会の作成した日本全国の基本道路は約23万個のノード, 約52万本のリンクより成り, その経路探索用データのデータ容量は約8MBと大きく, ディスクへのアクセス・読み込み時間, 探索を実行するために必要なRAM領域, ならびにCPU時間が増大し, 実用に耐えなくなることがある. 従来からこれらの間題点を解決するためいくつかの方法が提案されているが, 種々の問題点があった. 本論文では日本全国の道路ネットワークを複数個の領域に分割し任意の2つの領域間の最適経路を算出するために必要にして十分な領域の集合をオフラインで算出してテープル化することにより上述の問題点を解決している. このようなルックアップ・テープルを用いることそれ自体は容易に考え得るところであるが, 本論文ではこれを日本全国の道路に対し実際に適用した場合について, 実用的な領域分割数を明らかにすると共に, 領域分割の仕方として郡レベルの行政区に分割すると, テーブル作成に要する時間を多少なりと減少させるのに有利であることを示している. すなわち郡レベルの行政界は一般に河川や山脈等の地形的特性と密接な関係を有していることが多く, このような行政区界を横切る道路は少ないと考えられるためである. 本論文ではこのように領域分割の仕方に一つの示唆を与えると共に, ここで採用したルックアップ・テーブル法により探索領域を限定した経路探索法が, やはり最適経路を与えることが保証されてる従来のDijkstra法およぴA^*アルゴリズムと比較し, 総所要時間および必要とするRAM容量の面で現用のハードウェアの下では大幅に有利であることを示している.
- 社団法人情報処理学会の論文
- 1994-12-15
著者
関連論文
- ルックアップ・テーブルにより探索領域を限定した日本全国道路網における経路探索手法
- 5H-3 VRMLを用いた屋外から屋内までの連続的な3次元建物案内システム
- 大規模ベクトル線データの一元的管理方式とその評価 : 日本列島の詳細な海岸線ベクトルデータへの適用
- 階層構造を有する複数縮尺地図ベクトルデータの一元的管理方式
- 地形的特性により探索領域を限定した日本全国道路網における経路探索手法
- GPS測位とテレターミナルを用いた配車および経路案内システム
- 音声操作によるマルチメディア・タウン・マップ
- パーソナルコンピュータを用いたマルチメディア・アルバム
- 高速自動車道向けリアルタイム地理情報案内システムに関する検討
- 車載ナビゲーション・システムにおけるコマ図の自動生成に関する基礎検討
- 首都高速道路経路案内システム
- ICラベルからの位置ID取得によるモバイルインターネットを用いた位置関連情報取得システム
- 3次元経路案内システム用 Java VRML ビューアの試作
- 3次元経路案内システム用Java VRMLビューアの試作
- 経路探索問題とその応用
- 自動車の経路誘導 I.概要
- 都市交通における最適経路情報提供システム
- 有向ネットワークにおいて閉路を含まないk個の最短径路を求めるための手法
- DWFの概念を用いた多分岐多線条論理布線網の過渡解析手法
- 単分岐プリント配線の設計基準
- ディジタル計算機を用いた多分岐信号伝送線路の過渡解析手法
- 多分岐線路における多重反射波の相反現象について(技術談話室)
- 多分岐線路における直列そう入抵抗値の立上り時間に及ぼす影響について(技術談話室)
- 直列抵抗そう入による多分岐線路の波形ひずみ改善の一方法(技術談話室)
- 画像細線化を援用した市街地地図データからの道路ネットワーク抽出
- 地形的特性により探索領域を限定した日本全国道路網における経路探索手法
- ICラベルからの位置ID取得によるモバイルインターネットを用いた位置関連情報取得システム
- ニューラルネットを用いたピッチ抽出の一手法
- リアルタイム入力された手書き楽譜記号のパターン認識
- 複数の異種類似度を入力とするニューラルネットによる手書き数字認識
- 3次元CG連続画像による図書館利用案内システム