JPH0256591A - ナビゲーション装置及びそのルート探索方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、地図データを階層構造にして経路を探索する
ナビゲーション装置のルート探索方法に関する。

〔従来の技術〕

ナビゲーション装置は、地理の不案内な運転者に月して
目的地までルート案内を行うものであり、近年、このナ
ビゲーション装置の開発が盛んに行われている。

ナビゲーション装置は、予め走行前に出発地及び目的地
を入力することによって出発地から目的地までのルート
を設定し、その設定されたルートに従ってナビゲーショ
ンを行うものである。ナビゲーションでは、ルートを指
示する場合、ＣＲＴ画面に地図を表示しその上にルート
を重ねて表示したり、また、成るものは、予め設定され
たルートに従って次に曲がるべき交差点に関する情報と
して、次に曲がるべき交差点までの距離を数字やグラフ
、特徴的な写真で表示したりさらには音声出力も併用す
るものもある。

道路網にあっては、一般に出発地から目的地までの間に
複数のルートが存在するのが普通である。

そのため、ナビゲーション装置において、出発地及び目
的地が人力されると、その間における最短時間或いは最
短距離のルート（最短ルート）を探索するルート探索の
手法を採用する試みがなされている。その１つとして、
例えば四叉路の交差点の場合には、右左折、直進、Ｕタ
ーンを表現するために８つのノードと１６本の有向リン
クで交差点を表し、また、交差点相互を接続する道路技
は２木の有向リンクで表す方法が報告されている。

もう１つは、最短ルートを検索した後、進行禁止コース
と比較し進行禁止ルートを含む最短ルートを除去するご
とによって進行禁止ルートを含まない最短ルートを検索
する方法（例えば特開昭６２−９１８１１号公報）が提
案されている。

〔発明が解決しようとする課題］ しかしながら、上記前者の方法は、交差点での右左折情
報を全て有向リンクで表現しているので、データ量が多
くなり記憶容量が多くなるという問題がある。また、従
来のデータ構造では、右左折を検出して右左折により重
み付けを行い最短時間のルート探索を行おうとすると、
右左折の判断の計算が複雑になり、時間がかかる。特に
、四差路を８つのノードと１６本の有向リンクで表現し
ている場合には、１６本の有向リンクに重み付けした距
離又は時間のデータをもたなければならないため、デー
タ量が多くなる。

さらに加えて、ルート探索では、出発地から目的地まで
の距離が長くなると、また、道路網の密度が高くなると
、それだけルート探索の対象となる交差点が多くなる。

そのため、ルート探索に要する計算時間や探索処理時に
用いるメモリの記↑、９容量が増えるという問題がある
。

本発明は、上記の課題を解決するものであって、ルート
探索の計算時間の短縮を図ったルート探索方法を提供す
ることを目的とする。

〔課題を解決するための手段〕

そのために本発明は、指定された出発地から目的地まで
ルートを設定し設定したルートに沿って案内するナビゲ
ーション装置のルート探索方法であって、ルート探索に
用いる地図データを階層化構造にし、幹線道路網の上位
階層に対して幹線道路網に連結される支線道路網を展開
すると共にブロック分割し、下位階層から上位階層の道
路網に連結している交差点までの探索を順次繰り返し行
い出発地から目的地までのルートを探索することを特徴
とするものである。また、地図データとして、各階層の
各ブロック毎に交差点と交差点間の道路に関する連結情
報及び上位階層との連結交差点情報を有し、情報量に応
じて下位階層の分割ブロック数を増やし、出発地のブロ
ックと目的地のブロックが同一ブロック又は隣接ブロッ
クになるまで下位階層から探索を繰り返しながら上位階
層へ上げてゆく。

［作用及び発明の効果］ 本発明のルート探索方法では、まず、最下位の階層で出
発地、目的地を含むブロックでルート探索を行う場合、
それが上位階層の交差点番号を持っているときは、その
階層のブロックでルート探索を行う。上位階層の交差点
番号を持っていない場合には、その交差点から上位階層
の交差点番号を持つ交差点までのルート探索を行い、さ
らに上位階層のブロックに移行する。そして、出発地の
ブロック七目的地のブロックが同一ブロック又は隣接ブ
ロックになると、その間で出発地から目的地までのルー
ト探索を終了させる。

従って、データ量が同程度になるように各階層ともブロ
ック単位を設定することによって、情報量が多く複雑な
道路網であっても常に同し容量の中でルート探索を繰り
返し行うだけでよい。そのため、ルート探索に必要な記
憶容量も少なくてよいし、効率良くルー１−探索を行う
ことができ、ルート探索のための計算時間の短縮を図る
ことができる。

［実施例］ 以下、図面を参照しつつ実施例を説明する。

第１図は本発明に係るルート探索方法の１実施例を説明
するだめの図である。

第１図において、レイヤｌは、交差点番号１、■、■、
・・・・・・を持つ主要幹線道路網の地図であり、１つ
のブロック１で構成している。レイヤ２は、レイヤ１の
主要幹線道路網に連結される支線の道路網も含めた地図
であり、６つのブロック１〜６で構成している。そして
、ブロック間の接続道路には、レイヤ２のブロックｌ、
２間の交差点番号■とＨのように、ブロックで処理単位
を構成することができるように擬似的に交差点を設定し
ている。ブロック数は、それぞれで情報量がほぼ同程度
になるように設定される。従って、レイヤ１のブロック
１とレイヤ２のブロック１〜６は、それぞれが道路網デ
ータとして同程度の情報量を有するものである。

上記のように本発明のルート探索方法は、地図データと
して、下位へ向けて幹線から支線へ展開すると共にブロ
ック分割した各レイヤ１．２、・・・からなる階層化構
造のものを用い、出発地から目的地までのルートを探索
するものである。従って、レイヤ２の道路網の下位にさ
らに支線の道路がある場合には、レイヤ３が設定され、
情報量に応じてブロック数も多くなる。同様に、レイヤ
ｌのブロックｌだけでなくさらにその周囲の道路網も対
象とする場合には、レイヤｌがブロックｌとその周りの
道路網のブロックにより構成される。

そして、この場合には、レイヤ１の上位階層のレイヤが
設定される。

次に第１図の道路データを用いたルート探索方法の１例
を説明する。

例えば出発地と目的地がそれぞれレイヤ２のブロックｌ
にある交差点番号Ｉとブロンクロにある交差点番号■で
あるとする。

まず、ブロック１にある交差点番号Ｉの出発地について
は、上位階層のレイヤ１にない交差点番号である。そこ
で、上位階層のレイヤ１にある交差点番号を見つけ、そ
の交差点番号■と■（レイヤ１では交差点番号Ｉと■）
までのルートを探索して上位階層に上がる。

他方、ブロック６にある交差点番号■は、上位階層のレ
イヤ１に交差点番号■としであるので、そのまま上位階
層に上がる。

上位階層のレイヤ１では、下位階層のレイヤ２で探索し
た情報と合わせて交差点番号Ｉ又は■から交差点番号■
までのルート探索を行う。

上記の例から明らかなように、出発地、目的地が存在す
るブロックにより、■同じブロックの場合と、■隣接ブ
ロックの場合と、■離れたブロックの場合の３種類に分
類できる。そこで、本発明のルート探索方法は、それぞ
れに応じて次のようにルート探索を行う。

まず、■の出発地と目的地が同じブロックにある場合に
は、そのブロックの中でルート探索を行う。また、■の
出発地と目的地の各ブロックが隣接している場合には、
出発地ブロックと目的地ブロックだ接続している交差点
（接続交差点）を検出し、出発地から接続交差点、目的
地から接続交差点の２回に分けてルート探索を行う。し
かし、■の出発地と目的地の各ブロック間が離れている
場合には、上記の例のように出発地ブロックで出発地か
ら上位のレイヤに接続している交差点までの探索を行い
、同様に目的地ブロックで目的地から上位のレイヤに接
続している交差点までの探索を行う。そして、上記■又
は■の条件が満足するまで同様のルー）・探索を上位の
レイヤに上がって行う。

次に上記のルート探索方法に用いるのに好適な道路デー
タの具体的な構造例を示す。

第２図は第１図のレイヤ２におけるブロック１のデータ
構造の例を示す図、第３図は第１図のレイヤ２における
ブロック４のデータ構造の例を示す図、第４図は第１図
のレイヤ２におけるブロック６のデータ構造の例を示す
図、第５図は第１圓のレイヤ１におけるブロック１のデ
ータ構造の例を示す図である。

各ブロック単位のデータは、第２図〜第５図に示すよう
にそれぞれ道路データ（同図（ａ））と交差点データ（
同図（ｂ））からなる。そして、例えば第２図に示すよ
うに道路データは、ブロック内の各道路番号に対応して
、始点の交差点番号、終点の交差点番号、同じ始点をも
つ道路番号、同じ終点をもつ道路番号、案内不要道路、
道路の相対長さ、レイヤ等の情報を有している。道路番
号の単位は、通常、複数個のノードからなる。ノードデ
ータは、図示しないが道路上の１地点に関するデータで
あり、ノード間を接続するものをアークと呼ぶと、複数
のノード列のそれぞれの間をアークで接続することによ
って道路が表現される。また、交差点データは、ブロッ
ク内の交差点番号に対応して、東経、北緯、出る道路番
号、入る道路番号、上のレイヤの交差点番号、下のレイ
ヤの交差点番号、横のブロックの交差点番号（接続交差
点番号）等の情報を有している。

これらのうち、同じ始点（終点）をもつ道路番号や出る
（入る）道路番号は、それぞれ交差点における連結道路
の情報であり、通常、複数の道路番号が存在するので、
そのうちの一番手さい道路番号を登録しておく。このよ
うにすると、後述するように交差点の連結道路の検索が
容易に行える。

また、案内不要道路や道路の相対長さは、走行に要する
実質的な時間を算出する場合に必要となる情報である。

例えば同じ幅や長さの道路であっても案内を要する道路
より案内不要道路の方が実質的な走行時間は短めに換算
することができ、同じ長さの道路であっても走行条件が
悪いとか渋滞がしやすい道路であれば相対長さが長くな
る。レイヤは、道路のランクを示している。つまり、ど
の順位のレイヤでもつ道路かを示す情報である。上（下
）のレイヤの交差点番号、例えば１−１−２は、レイヤ
ｌ−ブロック１−そのレイヤブロックでの交差点番号を
示している。横のフロックの交差点番号も同様である。

次に本発明に係るルート探索方法を処理の流れに従って
説明する。

第６図はワークファイルとインデックスファイルの構造
を示す図、第７図は経路探索における全体の処理の流れ
を説明するための図、第８図は同一プロツク探索ルーチ
ンの例を示す図、第９図は隣接ブロック探索ルーチンの
例を示す図、第１０図は遠隔ブロック探索ルーチンの例
を示す図である。

ワークファイルは、ブロック単位で探索を行う際に、ブ
ロック内の交差点データ及び道路データを読み込んで使
用するものであり、第６図（ａ）に示すように交差点数
、道路数、始点、終点、ブロックの探索結果得られる交
差点に入る道路番号、フロックの探索の出発地と目的地
を示すフラグ等の情報を格納するものである。インデッ
クスファイルはブロックの情報を管理するものであり、
同図（ｂ）に示すようにブロック数とブロック番号等の
情報を有している。

第７図に示すように経路探索では、まず、インデックス
ファイルより出発地、目的地のブロックの位置関係を調
べ、その位置関係により以下の同一ブロック探索、隣接
ブロック探索、遠隔ブロック探索のいずれかの処理ルー
チンに分岐する。

同一ブロック探索では、第８図に示すように交差点デー
タ、道路データを入力すると共に、ワークエリ−を初期
化し、出発地、目的地を設定する。

しかる後、経路探索サブルーチンに分岐し、そこで生成
されたルートを出力する。

隣接ブロック探索は、交差点番号をＣ（レイヤーブロン
クー交差点番号）、道路番号をＲ（レイヤーブロンクー
道路番号）の形式で表し、出発地をＣ（２−１−１）、
目的地をＣ（２−４−４）とすると、第９図に示すステ
ップで次のように処理する。

■、■　出発地のあるレイヤ２、フロック１のデータを
読み込む。

■　接続交差点Ｓを下記のようにメモリに記憶する。

■　ワークエリアにおけるブロック内の全ての交差点を
下記のように設定して初期化する。

交差点に来る道路←０ フラグ　　　　　←未探索 距離　　　　　　←７　Ｆ　Ｆ　Ｆ　Ｆ　Ｆ　Ｆ　Ｆ　
Ｈ■　ワークエリアにおける出発地交差点Ｃ（２−１−
１）のフラグに「仮」、距離に「０」をセントする。

■　目的地として連続交差点（２−１−６）、Ｃ（２−
１−７）を設定する。

■　出発地交差点Ｃ（２−１−１）から仮の目的地であ
る連続交差点（２−１−６）、Ｃ（２−１−７）までの
探索を行う。

■、■　ワークエリアをセーブする。このとき接続交差
点までの距離を下記のようにメモリに記１．復する。

［相］〜■　出発地をＣ（２−４−１）、目的地を接続
交差点Ｃ（２−４−５Ｌ　Ｃ（２−４−４）として■〜
■と同様の探索を行う。

■〜■　最短コースとなる接続交差点を選ぶ。例えば出
発地からの距離、目的地からの距離がであるとすると、
接続交差点は、 （６＋５）＜　（１１＋８） から距離が短い方のＣ（２−１−６＞、Ｃ（２−４−５
）となる。

［相］　目的地ブロックのルートＣ（２−４−１）　−
Ｃ（２−４−５）を作成する。

［相］〜［相］　ワークエリアをロードし、出発地ブロ
ックのルートＣ（２−１−１）　−Ｃ（２−１−３）−
Ｃ（２−１−６）を作成する。

■　上記のそれぞれのルートを合成し、Ｃ（２−１−１
）−Ｃ（２−１−３）−Ｃ（２−１−６）−（２−４−
１）−Ｃ（２−４−５）を出力する。

続いて遠隔ブロック探索を説明する。ここでは、出発地
をＣ（２−１−１）、目的地をＣ（２−６−２）とする
。

■〜■　出発地のあるレイヤ２、ブロック１のデータを
読み込む。

■　上位のレイヤへの接続交差点Ｓ２を検出する。

■〜■　出発地をＣ（２−１−１）、目的地をＣ（２−
１−３）、Ｃ（２−１−４）として探索し、ワークエリ
アをセーブする。

■　出発地から接続交差点Ｓ２までの距離をメモリに記
１０．する。

■〜［相］　目的地のあるレイヤ２、ブロック６のデー
タを読み込む。

■　上位のレイヤへの接続交差点Ｄ２を検出する。

＠〜■　出発地をＣ（２−６−２）、目的地をＣ（２−
６−１）、Ｃ（２−６−３）として探索し、ワークエリ
アをセーブする。

■　出発地から接続交差点Ｄ２までの距離をメモリに記
憶する。

■〜■　上位のレイヤ１、ブロックｌのデータを入力す
る。

［相］　出発地として接続交差点５２（Ｃ（１−１−１
）、Ｃ（１−１−２））を設定する。また、距離の初期
地として出発地から接続交差点Ｓ２までの距離をセント
しておく。

［相］　目的地として接続交差点Ｄ２（Ｃ（１−１−７
）、Ｃ（１−１−８））を設定する。

■　接続交差点Ｓ２　（Ｃ（１−１−１）、Ｃ（１−１
−２））から接続交差点Ｄ２（Ｃ（ｔ−ｔ−７）　、Ｃ
（１−１−８））探索を行う。

＠　出発地から接続交差点Ｄ２までの距離と目的地から
接続交差点Ｄ２までの距離を比較する。例えば出発地か
らの距離、目的地からの距離がであるとすると、接続交
差点は、 （２２＋３）　＜　（２１＋２） から距離が短い方のＣ（２−６−３）、Ｃ（１−１−８
）が最短ルートとなる接続交差点Ｄ２である。

０　レイヤ１のルートＣ（１−１−８）　−Ｃ（１−１
−６）−ｃ　（１−１−５）−Ｃ（１−１２）を取り出
す。

＠〜［相］　出発地ブロックのワークエリアをロードし
、出発地ブロックのルー）　Ｃ（，２−１−４）　−Ｃ
（２−１−２）　−Ｃ（２−１−１）を取り出す。

＠〜［相］　目的地フ゛ロンクのワークエリアをロード
し、目的地ブロックのルートＣ（２−６−３）−Ｃ（２
−６−２）を取り出す。

＠　上記のそれぞれのルートを合成し、Ｃ（２−１−１
）　−Ｃ（２−１−２）　−Ｃ（２−１−４）−Ｃ（１
−１−５）−Ｃ（１−１−６）−Ｃ（２−６−３）　−
Ｃ（２−６−２）を出力する。

次に経路探索サブルーチンを説明する。

第１１図は経路探索サブルーチンの例を示す図である。

ここでＬ　（ｃ）は距離、Ｆ　（ｃ）はフラグ、Ｒ（ｃ
）は通過してきた道路番号、Ｓｌｌ＋ｓｌ　は出発地の
両隣りの交差点番号、ｅｏ、ｅ、は目的地の両隣りの交
差点番号である。また、Ｃは交差点番号、フラグＦ　（
ｃ）は「０」が未探索、「１」が探索中、「２」が探索
終了を示す。

■　全ての交差点について 距離Ｌ　（ｃ）に無限大（■） フラグＦ　（ｃ）に「０」　（未探索）にセントする。

この初期設定によりまず全ての交差点が未探索となり、
出発地からの距離が無限大となる。

■　出発地の両隣りの交差点番号Ｓｏ、Ｓｌ　に対応す
る距離Ｌ（ｓ、）、ｌ、（Ｓ、）に出発地からの距離を
入れ、さらに出発地の両隣りの交差点番号ｓ、、Ｓ、に
対応するフラグＦ　（ｓ、　）。

Ｆ　（ｓ、　）にそれぞれ「ｌ」、通過してきた道路番
号Ｒ（ｃ）に出発地からの道路番号をセントする。

■　フラグＦが「２Ｊでなく且つ距ＭＬ（ｃ）が最小と
なる交差点番号ｃ０を検索する。

■　周囲道路検索サブルーチンを実行し、交差点番号ｃ
０を始点とする周囲道路を検索する。

■　周囲道路があるか否かを調べる。

ＹＥＳの場合には次の処理■に移り、ＮＯの場合には処
理■に移る。

■　最適経路条件設定サブルーチンを実行し、最適経路
を探索するための道路状況その他の条件を設定する。

■　その道路の終点の交差点番号をＣＩ、道路の長さを
２とする。

■　その道路の終点の交差点までの距離Ｐを計算する。

Ｐ　＝Ｌ　（ｃｏ　）　＋　４２を計算する。

ここでｔ−（ｃｏ　）は出発地から交差点番号ｃ０まで
の距離であり、Ｐは交差点番号ｃ０からその道路（探索
中の道路）を通って終点の交差点番号Ｃ２までの距離と
なる。

■　ｐ＜Ｌ（ｃｉ）で且つＦ　（ｃｉ　）≠２か否かを
調べる。

ＹＥＳの場合には次の処理［相］に移り、Ｎｏの場合に
は処理■に戻る。

［相］　出発地から探索中の交差点番号ＣＩ　までの距
離Ｌ　（ＣＩ　）をＰ、その交差点番号Ｃ３のフラグＦ
　（ｃｉ　’）を「１」、交差点番号Ｃ５に至るまでに
通過してきた道路番号Ｒ（ＣＩ　）をその探索中の道路
番号とする。

■　処理■においてＮｏの場合にはＦ（ｃ、）を「２」
にセットする。

■　終了条件確認サブルーチンを実行する。

■　処理終了か否かを調べ、Ｎｏの場合には処理■に戻
り、ＹＥＳの場合には処理を終了とする。

以上の処理を行うことによりそれぞれの交差点番号に対
応して出発地から当該交差点番号に至る最適コースの道
路番号がそれぞれ交差点番号毎に設定される。

第１２図は周囲道路検索サブルーチンの処理の流れを説
明するだめの図、第１ご３図は最適経路条件設定サブル
ーチンの処理の流れを説明するだめの図、第１４図は終
了条件確認サブルーチンの処理の流れを説明するための
図である。

上記処理■の周囲道路検索サブルーチンは、第１２図に
示す処理を行う。すなわち、 ■　周囲道路の検索が１回目か否かを調べる。

ＹＥＳの場合には処理■に移り、ＮＯの場合には処理■
に移る。

■　交差点データから現在いる交差点Ｃ０が始点となっ
ている道路番号を取り出し記憶する。

■　道路データを参照し探索中の当該交差点Ｃ６にくる
道路番号における禁止道路を取り出す。

■　今取り出した道路が禁止道路か否かを調べる。

ＹＥＳの場合には処理■に移り、Ｎｏの場合には次の処
理■に移る。

■　今取り出した道路を周囲道路として記憶し、リター
ンする（第１１図の処理■へ移る）。

■　道路データから前に探索した道路と同じ始点を持ら
、番号が次の道路番号を取り出す。

■　最初探索した道路と今取り出した道路が同じか否か
を調べる。

ＹＥＳの場合には次の処理■に移り、ＮＯの場合には処
理■に戻る。

■　周囲道路なしと判定しリターンする。

また、上記第１１図に示す処理■の最適経路条件設定サ
ブルーチンは、第１３図に示すような処理を行うもので
ある。すなわち、 ■　道路データから相対長さｉを読み込む。

■　道路データから現在探索中の交差点へ通過してきた
道路の案内不要データを読み込む。

■　案内不要データと一致する周囲道路があるか否かを
調べる。

ＹＥＳの場合にはリターンし、ＮＯの場合には次の処理
■に移る。

■　さらに長さ２にｂｍを加算した値を新たな長さ２と
しリターンする。すなわち、案内不要の交差点に対して
、右左折等の案内を要する交差点は、距離に換算してｂ
ｍ加算した評価としている。

終了条件確認サブルーチンでは、第１４図に示すように
探索対象の交差点番号ｃ０と目的等の両隣りの交差点番
号との一致を調べ、一致したことを条件に例えば終了フ
ラグを設定する。

このように経路探索では、周囲道路の大きさや道路の案
内要／不要等の走行条件を考慮して交差点間の距離に重
み付けを行い、最短ルートを探索する。

なお、本発明は、上記の実施例に限定されるものではな
く、種々の変形が可能である。例えば上記の実施例では
、出発地と目的地が同一ブロックになるか、隣接ブロッ
クになるまで上位階層へ上げて探索を行うようにしたが
、隣接ブロンクの場合も探索を行って上位のレイヤに上
げ、最終的には同一ブロック内の探索により出発地と目
的地とを連結するようにしてもよい。ただ、このように
すると、隣接プロンク間で上位のレイヤにはないが、上
位のレイヤでの主要道路のルートよりも適当なルートが
あっても、このルートが設定されなくなる。従って、隣
接ブロックの場合にはその階層でルート探索を終了させ
る方が効率的であるといえる。

以上の説明から明らかなように、本発明によれば、交差
点データ、道路データ等の道路網データを階層化構造に
して持ち、下位階層（レイヤ）から順に下位階層へ上げ
て探索を行うので、探索範囲を限定して処理することが
でき、探索処理の高速化を図ることができる。また、各
階層においてデータ量に応じてブロック分割し、プロン
ク単位で探索を行うので、探索に必要な作業領域を少な
くすることができ、記憶領域の節減を図ることができる
。

【図面の簡単な説明】

第１図は本発明に係るルート探索方法の１実施例を説明
するための図、第２図は第１図のレイヤ２におけるブロ
ック１のデータ構造の例を示す図、第３図は第１図のレ
イヤ２におけるブロック４のデータ構造の例を示す図、
第４図は第１図のレイヤ２におけるブロック６のデータ
構造の例を示す図、第５図は第１図のレイヤ１における
ブロック１のデータ構造の例を示す図、第６図はワーク
ファイルとインデンクスファイルの構造を示す図、第７
図は経路探索における全体の処理の流れを説明するため
の図、第８図は同一ブロック探索ルーチンの例を示す図
、第９図は隣接ブロック探索ルーチンの例を示す図、第
１０図は遠隔ブロック探索ルーチンの例を示す図、第１
１図は経路探索サブルーチンの例を示す図、第１２図は
周囲道路検索サブルーチンの処理の流れを説明するため
の図、第１３図は最適経路条件設定サブルーチンの処理
の流れを説明するための図、第１４図は終了条件ｆ（ｉ
　４９サブルーチンの処理の流れを説明するための図で
ある。 出　願　人　アイシン・エイ・ダブリュ株式会社（外１
名） 代理人　弁理士　　阿　部・龍　吉（外４名）第２図 （ａ） 第１ 図 （ｂ） フＵフフ１ ノＱ−１りｔ ノロ・シソｊ 第３図 （ａ） （ｂ） 第５図 （ａ） （ｂ） 第４図 （ａ） （ｂ） Ｍ６図 第７図 第１１図 第１２図

Claims (3)

【特許請求の範囲】
1. （１）指定された出発地から目的地までルートを設定し
   設定したルートに沿って案内するナビゲーション装置の
   ルート探索方法であって、ルート探索に用いる地図デー
   タを階層化構造にし、幹線道路網の上位階層に対して幹
   線道路網に連結される支線道路網を展開すると共にブロ
   ック分割し、下位階層から上位階層の道路網に連結して
   いる交差点までの探索を順次繰り返し行い出発地から目
   的地までのルートを探索することを特徴とするルート探
   索方法。
2. （２）情報量に応じて下位階層の分割ブロック数を増や
   し、出発地のブロックと目的地のブロックが同一ブロッ
   ク又は隣接ブロックになるまで下位階層から上位階層へ
   の探索を繰り返すことを特徴とする請求項１記載のルー
   ト探索方法。
3. （３）地図データとして、各階層の各ブロック毎に交差
   点と交差点間の道路に関する連結情報及び上位階層との
   連結交差点情報を有することを特徴とするルート探索方
   法。