JPH0429013A - 経路探索装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明（Ｌ　車両の運転者が出発地または現在地点から
目的地に至る経路を知るために用いる経路探索装置に関
するものであも 従来の技術 従来の経路探索装置において、車両の走行すべき経路の
探索を行う装置としては、　例えば特開昭６２−６０１
００号公報に示された車両用経路案内装置がある。この
車両用経路案内装置は道路網上の交差点全てに対して交
差点番号を重複することなく持板　その各々の交差点番
号に対応してＸ。

Ｙ座標情報や道程情報等を記憶しておいて、−度に全て
の交差点に対応するデータを用いて出発交差点から接続
する交差点を目的地に至るまで順番に経路を探索して行
くものであっ九 発明が解決しようとする課題 しかしながぺ　長距離経路の探索等で経路探索に使用す
る道路網が広域になるときには、　読み込む道路網デー
タのサイズが大きくなり使用するメモリ量を増大させて
しまう等の課題があった本発明１表　このような従来の
経路探索装置の課題に鑑へ　長距離経路の探索等で経路
探索に使用する道路網が広域になるときでｋ　使用する
メモリ量を増大させることなく、少ないメモリ量で経路
探索を行うことができる経路探索装置を提供することを
目的とするものであも 課題を解決するための手段 上記目的を達成するため本発明は　出発地及び目的地の
位置を記憶した地点記憶手段と、特定範囲毎に道路網デ
ータを分割して記憶した地図データ記憶手段と、特定範
囲毎の探索結果を記憶する探索結果記憶手段と、出発地
または目的地を開始点として１つ以上の特定範囲で、最
短距離経路または最適経路を探索する探索手段と、探索
結果を出力する出力手段からなる経路探索装置であムま
た地図データ記憶手段は　特定範囲毎に分割された道路
網データと、分割された境界で隣接する特定範囲との道
路接続データとを記憶していることを特徴とする経路探
索装置であム また地図データ記憶手段は、　詳しさの異なる複数の道
路網データをそれぞれの特定範囲毎に分割して記憶し　
探索手段は詳しさの異なる道路網データを用いて特定範
囲毎に探索し　探索結果データを探索結果記憶手段に記
憶させることを特徴とする経路探索装置である。

作用 本発明は前記した構成により、出発地点から目的地点ま
での経路を探索する際に　あらかじめ区切って記憶して
おいた特定範囲の道路網データを読み込んで経路探索を
行う。探索の順序は出発地点か収　若しくは目的地点か
収　またはこれらの両方から行し＼　特定範囲ごとの探
索を繰り返し行ｕ％　　それぞれの探索ごとに探索結果
を探索結果記憶手段に記憶しておき、探索終了すると探
索結果記憶手段より探索結果を読みだして出力す４　あ
らかじめ区切って記憶された特定範囲ごとの道路網デー
タで経路探索を行うので一度に大量の道路網データを読
み込まなくてもよく、大容量のメモリを備えることなく
、少ないメモリ量で経路探索を行うことができ、また探
索時間を短縮することができも 実施例 本発明の第１の実施例について説明すも第１図は本発明
の第１の実施例における経路探索装置のブロック図であ
ａ　１０１は出発地および目的地の位置を記憶する地点
記憶手段　１０２は特定範囲毎に道路網データを分割し
て記憶した地図データ記憶手段、　１０３は特定範囲毎
の地図の道路網上の地点（ノード）に対応する探索結果
データを記憶する例えばＲＡＭ等の探索結果記憶手段　
１０４は探索手段であり、例えばＣＰＵを用いて、前記
出発地または前記目的地を開始点として、　１つ以上の
特定範囲で最短距離経路または最適経路を探索するとき
に　特定範囲毎の道路網データを用いて特定範囲毎に探
索し　特定範囲毎の道路網上のノードに対応する探索結
果データを探索結果記憶手段１０３に記憶させも　１０
５は出力手段で、探索手段１０４の探索結果を出力すも
　具体的には、　例えばデイスプレィなどテアってもよ
いし　また探索結果を音声で出力する出力装置であって
もよ（−また現在位置検出装置を組み合わせ、適当な時
または場所で探索結果を指示する画像または音声による
誘導案内装置であってもよ（℃ 上記のように構成された第１の実施例の経路探索装置に
ついて、以下その動作を説明する。

地点記憶手段１０１は経路を探索する出発地および目的
地の位置を入力して記憶する。地図データ記憶手段１０
２は予め経路探索に必要な道路網データを特定範囲毎　
例えば経度・緯度または道路網データのサイズに基づい
て分割して記憶してあも　探索結果記憶手段１０３は地
図データ記憶手段１０２で分割された特定範囲毎の道路
網データに基づいて、特定範囲毎の道路網上のノードに
対応する探索手段１０４の探索結果デー久　例えば道路
網上の各ノードに対応して出発地から各ノードに到達す
る到達距離および各ノードに到達する経路の１つ前のノ
ードを記憶する。探索手段１０４は地点記憶手段１０１
の記憶している出発地および目的地を人力し　出発地ま
たは目的地を開始点として、最短距離経路または最適経
路を探索すも　これは例えば出発地を開始点として最短
距離の経路を探索する場合には　特定範囲の道路網デー
タの中から出発地が含まれる１特定範囲（１面分）の道
路網データを地図データ記憶手段１０２から読み込へ　
読み込んだ特定範囲の道路網上のノードに対応する探索
結果データが探索結果記憶手段１０３に記憶されてあれ
ばこのデータも併せて読み込ａ　そして出発地から広が
る道路網に従って、読み込んだ特定範囲の道路網データ
１面分の中で、出発地から道路網上の各ノードに対して
探索結果データで記録されている各ノードへの到達距離
よりも最短距離で到達する経路があればそのノードに対
する探索結果データ（出発地からの到達距離および経路
の１つ前のノード）を更新していく。そして１面分の経
路探索を終了した時に目的地に探索した経路が到達して
いなければ更新した探索結果データを探索結果記憶手段
１０３に記憶させ、読み込んだ特定範囲の道路網データ
および探索結果データの代わりに出発地から最短距離で
到達した特定範囲の境界に接する未探索の特定範囲を、
例えば境界の経度・緯度から選出し　この特定範囲の道
路網データおよび道路網上のノードに対応する探索結果
データを地図データ記憶手段１０２および探索結果記憶
手段１０３から読み込んで、探索した特定範囲の境界上
のノードの位置から経路か接続したノードを選出し　探
索した特定範囲の境界上のノードに対応する探索結果デ
ータをこの接続したノードに対応する探索結果データに
移して、接続した特定範囲内で接続した地点から経路探
索を以前と同様に続け、探索した経路が目的地に到達す
るまでこの上記探索する特定範囲を移していく動作を繰
り返す。出力手段１０５は探索手段１０４の探索結果を
出力する。

第１の実施例の動作をソフトウェアで実現する場合の概
略フローチャートを第２図に示す。先ず始めに　処理２
０１で探索する経路の出発地および目的地の位置を入力
して記憶しく地点記憶手段１０１に相当）、処理２０２
で出発地または目的地を開始点として最短距離経路また
は最適経路の探索を行い（地図データ記憶手段１０２、
探索結果記憶手段１０３および探索手段１０４に相当）
、処理２０３で処理２０２で求めた探索結果を出力する
（出力手段１０５に相当）。

次に　探索処理２０２について、最短距離経路の探索の
場合を例にとり第３図のフローチャートを用いて更に詳
しく説明する。処理２０１で記憶された出発地および目
的地の位置を処理３０１で入力し　処理３０２で出発地
を含む特定範囲の道路網データを地図データ記憶手段１
０２から読み込ａ　この読み込んだ特定範囲の道路網デ
ータ１面分を最短距離の経路を求めるために処理３０３
で探索すム　処理３０４は処理３０３で経路探索した特
定範囲の道路網上のノードに対応する探索結果データを
探索結果記憶手段１０３に記憶させ、判断３０５で処理
３０３で探索した経路が目的地に今まで探索した中の最
短の距離で到達したかどうかを判断し　今までの最短距
離で到達していれば処理３０６で経路探索を行う探索範
囲の限度距離をこの最短距離に設定すム　また　判断３
０５で探索した経路が今までの最短距離で到達していな
ければ処理３０６は行わな（′Ｉｏ　　次に処理３０７
において処理３０３で求めた探索結果データを調べて探
索した経路が特定範囲の境界上で接続したノードに対し
て、接続する隣の特定範囲の道路網上のノードに対応す
る探索結果データを作成して記憶させ、この接続する特
定範囲を次に経路探索を行う探索対象範囲にする。処理
３０８は処理３０７で探索対象範囲となっている特定範
囲の内かぺ　出発地から最短距離で到達した特定範囲の
道路網を選出し　この選出した特定範囲に到達した距離
が処理３０６で設定した探索限度距離内かどうかを判断
３０９で判断し　探索限度距離内であれば処理３０３で
経路探索を行った特定範囲の道路網データの代わりに選
出した特定範囲の道路網データ１面分を処理３１０で読
み込へ　選出した特定範囲の道路網上のノードに対応す
る探索結果データを処理３１１で読み込んで処理３０３
へ戻ム　また　判断３０９で選出した特定範囲に到達し
た距離が探索限度距離外であれば　処理２０２を終了す
る。

次に　特定範囲内探索処理３０３について、第４図のフ
ローチャートを用いて更に詳しく説明すも　処理４０１
は処理３０２または処理３１０で読み込んだ特定範囲の
道路網データと、処理３０１で入力した出発地または処
理３０７で記憶し処理３１１で読み込んだ特定範囲の探
索結果データに基づき、出発地または探索した経路が接
続したノードを探索対象ノードとして設定し　この探索
対象ノードが残っているかどうかを判断４０２で判断す
ム　ここで、探索対象アートが残っていれは　探索対象
ノードの内で出発地から最短距離で到達しているノード
を捜し出して処理４０３で経路探索の基準点とし　読み
込んだ特定範囲の道路網データ１面分の中で、この基準
点に道路網を通じて接続するノードを処理４０４で捜す
。そして、探索結果データか収　接続するノードに出発
地から今までの最短距離で到達したかどうかを判断４０
５で判断し　今までの最短距離であれば接続するノード
に対応する探索結果データに基準点と出発地からの到達
距離を処理４０６で記憶させ、接続するノードを探索対
象ノードに処理４０７で加える。また　判断４０５にお
いて今までの最短距離で到達していなければ処理４０６
および処理４０７は行わない。次に基準点に対して全て
の接続するノードを調べたかどうかを判断４０８で判断
し　調べていれば処理４０９で基準点を探索対象ノード
から削除して判断４０２へ戻る。まｆ、　　判断４０８
で基準点に対して全ての接続するノードを調べていなけ
れば処理４０４へ戻る。また　判断４０２において探索
対象ノードが残っていなければ　特定範囲内探索処理３
０３を終了する。

次に第５図および第６図を用いて、探索゛処理２０２お
よび特定範囲内探索処理３０３で扱うデータ形式の一例
及び処理２０３の例を説明す４　道路網上の各ノードに
番号を対応づけ、ノード間の接続とその距離が記憶され
た道路網データが第５図のような道路網である場合、第
６図のように探索結果データを記憶させ、４　６０１は
道路網上のノードを番号として記憶するノード番号記憶
領域６０２はノード番号記憶領域６０１の各ノード番号
に対応する基準点のノード番号を記憶する基準点番号記
憶領域　６０３は出発地からノード番号に到達するまで
の最短距離を記憶した最短距離記憶領域であム　例えば
ノード番号１を出発地のノードとした隊　ノード番号記
憶領域６０１のノード番号が１のところに対応する基準
点番号記憶領域６０２にＯを記入し　最短距離記憶領域
６０３に０　（ｍ）を記憶する。さらに第５図のよう＆
ミノード番号１から接続するノード番号が２と３であっ
たとし　出発地からの到達距離が ノード番号は２、到達距離は３０（ｍ）ノード番号は３
、到達距離は５０（ｍ）であった場合、ノード番号記憶
領域６０１のノード番号が２に対応する基準点番号記憶
領域６０２に基準点番号１を記憶し　最短距離記憶領域
６０３に到達距離の３０（ｍ）を記憶すも　またノード
番号記憶領域６０１のノード番号が３に対応する基準点
番号記憶領域６０２に基準点番号１を記憶し　最短距離
記憶領域６０３に到達距離の５０（ｍ）を記憶すム　そ
して、ノード番号２および３を探索対象ノードにする。

ここでノード番号ｌに接続するノードを調べ終ったとき
、探索の次の基準点として探索対象ノードの中で出発地
（ノード番号１）から最短距離で到達するノードを選出
すも　いま探索対象ノードはノード番号２および３で、
ノード番号記憶領域６０１のノード番号２および３に対
応する最短距離記憶領域６０３の値は３０（ｍ）および
５０（ｍ）であるた嵌　次の基準点には最短到達距離３
０（ｍ）であるノード番号２を選出すも　こうして基準
点であるノード番号２につながるノードをノード間の接
続情報から調べて探索結果データを作成していく。また
探索処理２０２を終了した後、処理２０３では目的地の
ノード番号をノード番号記憶領域６０１の中から捜し出
し　このノード番号に対応する基準点番号を基準点記憶
領域６０２から読み出す。そして読み出した基準点番号
をノード番号記憶領域６０１の中から捜し出し　このノ
ード番号の基準点番号を再び基準点記憶領域６０２から
読み出すことを出発地のノード番号にたどり着くまで繰
り返して、読み出したノード番号を順に記憶させておく
ことにより、最短距離経路をノードの列として求めるこ
とができも　またこのノードの列か収例えば最短距離経
路をデイスプレィ上に表示する場合には、　各々のノー
ドの地図上の位置を調べてこれらをノードの列の順番に
線等で結んで表示する事により、最短距離経路を出力す
る事ができも次へ　処理３０７および処理３０８の動作
の例を第７図を用いて説明する。　７０１は出発地の位
Ｗｔ、　７０２は特定範囲毎に分割された地図の境界線
　７０３は境界線７０２で区切られた出発地７０１を含
む特定範囲の地は　７０４は特定範囲の地図７０３に記
録された道路緻　７０５は道路網７０４を探索したとき
に接続する特定範囲の地文７０６は道路網７０３と接続
する特定範囲の地図７０５との接続ノードであム　例え
ば　探索処理２０２で最初に特定範囲内探索処理３０３
を行つたときは、　処理３０３は特定範囲の地図７０３
を出発地７０１から道路網７０３に従って経路探索を行
し＼　特定範囲の地図７０４の地図の道路網上の各ノー
ドに対応する探索結果データを作成する。

次に処理３０７は道路網７０３によって接続する特定範
囲の地図７０５を捜して接続ノード７０６を捜し出し　
探索結果データから該当する接続ノード７０６の探索結
果データを選出して、今回の特定範囲内探索処理３０３
で接続ノード７０６の探索結果データか書き換えられて
いる接続する特定範囲の地図７０５各々に対して接続す
る特定範囲の地図７０５の道路網上のノードに対応する
探索結果データを作成し記憶させ、接続する特定範囲の
地図７０５を次の探索対象範囲にする。処理３０８は処
理３０７で探索対象範囲となった接続する特定範囲の地
図７０５の接続ノード７０６の内で出発地７０１から最
短の距離で到達するノードを選出し　選出したノートを
含む接続する特定範囲の地図７０５の内の１つを選出し
　選出した特定範囲の地図を次の探索対象範囲から削除
すムまた地図データ記憶手段１０２く　特定範囲毎に分
割された道路網データと、分割された境界で隣接する特
定範囲との道路接続データとを合わせて記憶している地
図データ記憶手段を用いれは探索した特定範囲の境界上
のノードの経路・緯度等の位置から経路が接続したノー
ドを選出する処理を行わずＧＱ　　この道路接続データ
を用いて経路が接続したノードを選出することができ４
以上のように第１の実施例によれ（二　道路網データを
特定範囲の道路網データ毎に読み込んで経路探索を行う
ために　−度に大量の道路網データを読み込んで経路探
索に使用するメモリ量を増大させることなく、少ないメ
モリ量で経路探索を行うことができる。

次に本発明の第２の実施例について説明すも本発明は長
距離経路の探索等で経路探索に使用する道路網が広域に
なるときで叡　使用するメモリ量を増大させることなく
、少ないメモリ量で経路の探索を行うことができ、かつ
探索時間を第１の実施例よりも短縮することができる経
路探索装置を提供することを目的とするものであム本発
明の第２の実施例における経路探索装置のブロック図は
第１図と同様であるたべ　この図を用いて説明すも　地
点記憶手段１０１、地図データ記憶手段１０２、探索結
果記憶手段１０３、出力手段１０５は第１の実施例と同
様な構成てあム第１の実施例の構成と異なるのは、　探
索手段１０４で複数の特定範囲の道路網データを用いて
出発地または目的地を開始点として最短距離経路または
最適経路を探索するときｌへ２つ以上の特定範囲の道路
網データを１つの特定範囲の道路網データと同じデータ
構成に変換し　この変換した道路網データ毎に探索し　
変換した２つ以上の特定範囲毎の道路網上のノードに対
応する探索結果データを探索結果記憶手段１０３に記憶
させる点である。

次にこのように構成された第２の実施例の経路探索装置
について、以下その動作を説明すも探索手段１０４は予
め地図データ記憶手段１０２に記憶されている特定範囲
毎の道路網データを２つ以上の特定範囲毎の組に対応相
しておく。そして地点記憶手段１０１の記憶している出
発地および目的地を入力し　この出発地または目的地を
開始点として最短距離経路または最適経路を探索する。

これは例えば出発地を開始点として最短距離の経路を探
索する場合に（友　特定範囲毎の道路網データの中から
出発地を含む特定範囲の道路網データが属する２つ以上
の特定範囲からなる道路網データの組を地図データ記憶
手段１０２から読み込へ　１つの特定範囲の道路網デー
タと同じデータ構成に変換する。このとき変換した道路
網上のノードに対応する探索結果データが探索結果記憶
手段１０３に記憶されていればこのデータも併せて読み
込む。ここで出発地から広がる道路網に従って、変換し
た道路網データ内で出発地から道路網上の各ノードに対
して探索結果データよりも最短距離で到達する経路があ
れば　そのノードに対応する探索結果データを更新する
。そして変換した道路網データ内の経路探索を終了した
時に目的地に探索した経路が到達していなければ　探索
結果データを探索結果記憶手段１０３に記憶させて、変
換した道路網データの代わりに探索した道路が変換した
特定範囲外との境界上での接続する隣の特定範囲を含む
対応相た組の道路網データを地図データ記憶手段１０２
から読み込んで同様に道路網データを変換し　この変換
した道路網上のノードに対応する探索結果データを探索
結果記憶手段１０３から読み込へ　出発地からの最短距
離経路の探索を道路が接続するノードから同様に続けも
　また探索した経路か目的地に到達していれば出発地か
ら目的地までの最短到達距離を探索する限度距離として
、探索している経路が全てこの限度距離を越えれば探索
を終了すも　探索結果記憶手段１０３は探索手段１０４
で変換した２つ以上の特定範囲毎の道路網上のノードに
対応する探索結果データを記憶する。

第２の実施例の動作をソフトウェアで実現する場合の説
明を以下に行う。

概略フローチャートは第２図と同様なものであり、処理
２０１、処理２０３は第１の実施例と同様の動作を行う
。第１の実施例と異なるのは、　処理２０２で出発地ま
たは目的地を開始点として最短距離経路または最適経路
を探索するとき置　２つ以上の特定範囲の道路網データ
を１つの特定範囲の道路網データと同じデータ構成に変
換して経路探索を行う点である（地図データ記憶手段１
０２、探索結果記憶手段１０３および探索手段１０４に
相当）。

次に探索処理２０２について、第８図のフローチャート
を用いて更に詳しく説明すも　処理８０１は予め分割し
て記憶された特定範囲毎の道路網データを隣接し合う２
つ以上の特定範囲毎に組にする様に対応相を行う。そし
て、処理３０１で出発地および目的地の位置を人力し　
処理８０２で出発地を含む処理８０１で対応相た２つ以
上の特定範囲の道路網データの組を地図データ記憶手段
１０２から一度に読み込へ　処理８０３でこの道路網デ
ータを１つの特定範囲の道路網データと同じデータ構造
に変換すも　この変換したデータを新しく構成した１つ
の特定範囲の道路網データと同様に対応して、処理３０
３から判断３０９までは第１の実施例の第３図と同様に
動作を行う。そして判断３０９で、処理３０８で選出し
た特定範囲が処理３０６で設定した探索限度距離内であ
れは　処理８０４でこの選出した特定範囲を含む２つ以
上の特定範囲の組の道路網データを経路探索を行った道
路網データの代わりに読み込へ　読み込んだ道路網デー
タを１つの特定範囲の道路網データと同じデータ構造に
処理８０５で変換し　この変換した道路網上のノードに
対応する探索結果データを処理３１１で読み込んで処理
３０３へ戻る。

次に　第２の実施例における探索処理２０２の動作の例
を第９図を用いて説明す４　９０＋は予め特定範囲毎に
分割された地図の境界線　９０２は処理８０１で対応相
た組となる２つ以上の特定範囲の地図であり、例えば４
範囲毎の地図の境界線であム　９０３は出発地の位＠　
　９０４は地図上の道路諷　９０５は境界線９０１で分
割された出発地９０３を含む特定範囲の地１１ｆｌ　　
９０６は境界線９０２で対応相られた地図９０５と組を
成す４範囲の地図　９０７は出発地９０３から経路探索
を行ったときに出発地から最短距離で接続する特定範囲
の地ｌ　９０８は接続する特定範囲の地図９０７と組を
成す４範囲の地図であも　出発地９０３から経路探索を
行うとき、出発地９０３を含む地図９０５を読み込むと
同時に地図９０５と組を成す４範囲の地図９０６を全て
読み込む。そして組を成す４範囲の地図９０６内を１つ
の特定範囲の道路網データと同じデータ構成に変換して
から一度に探索した後、その探索結果データをまとめて
記憶する。次に例えば探索した４範囲の地図９０６のへ
　探索した経路が出発地９０３から最短距離で特定範囲
の地図９０７に接続していれば　特定範囲の地図９０７
と組を成す４範囲の地図９０８を全て読み込へ　探索し
た４範囲の地図９０５から接続するノードの探索結果デ
ータに基づいて読み込んだ４範囲の地図９０８内を１つ
の特定範囲の道路網データと同じデータ構成に変換して
から経路探索すム　この様にして目的地に到達するまで
経路探索の範囲を広げて行くことにより、出発地９０３
から目的地までの最短距離経路を求めることができる。

以上のように　本実施例によれば２つ以上の特定範囲の
道路網データを一度に探索することにより、　１つの特
定範囲の道路網データを探索したときに　−度探索が終
了した隣の特定範囲の探索結果データを書き換えてしま
うために　探索が終了した特定範囲の地図を再び探索し
直す回数を減らすことができるたべ　−度に大量の道路
網データを読み込む必要がなく、少ないメモリ量で経路
探索を行うことができ、かつ探索時間を第１の実施例よ
りも短縮することができも 次に本発明の第３の実施例について説明する。

本発明は長距離経路の探索等で経路探索に使用する道路
網が広域にわたるときで耘　使用するメモリ量を増大さ
せることなく、少ないメモリ量で経路探索を行うことが
でき、かつ探索時間を第１の実施例よりも短縮すること
ができる経路探索装置を提供することを目的とするもの
である。

本発明の第３の実施例における経路探索装置のブロック
図は第１図と同様であるたム　この図を用いて説明すも
　地点記憶手段１０１、探索結果記憶手段１０３、出力
手段１０５は第１の実施例と同様な構成であ４　第１の
実施例の構成と異なるのは　地図データ記憶手段１０２
で同じ地図上の地域において複数の詳しさの異なる道路
網データをそれぞれの特定範囲に分割し　この詳しさの
異なる道路網データ間で道路網上の共通する地点が同一
である事を示すデータを合わせて記憶する戊　および探
索手段１０４で、例えばＣＰＵを用いて、出発地または
目的地を開始点として、　１つの詳しさの道路網データ
を予め定めた範囲の道路網データ例えば特定枚数の特定
範囲の道路網データを各々の特定範囲毎に経路探索して
道路網上のノードに対応する探索結果データを探索結果
データ記憶手段１０３に記憶させ、複数の詳しさの異な
る道路網間を道路網上の共通する部分を用いて探索する
道路網データを切り替えながら最短距離経路または最適
経路を求める点である。

次にこのように構成された第３の実施例の経路探索装置
について、以下その動作を説明する。

地図データ記憶手段１０２は予め同一地域での複数の詳
しさの異なる道路網データを各々の特定範囲孤　例えば
経度・緯度または道路網データのサイズに基づいて分割
し　かつ詳しくない地図は詳しい地図に対して同一以上
に広い範囲を特定範囲とするように分割して記憶すも　
探索手段１０４は地点記憶手段１０１の記憶している出
発地および目的地を入力し　この出発地または目的地を
開始点として最短距離経路または最適経路を探索すム　
これは例えば出発地を開始点として最短距離経路の探索
を行う場合には、　例えば最も詳しい特定範囲の道路網
データの中から出発地が含まれる特定範囲の道路網デー
タを１面分地図データ記憶手段１０２から読み込む。そ
して出発地から広がる道路網に従って、この道路網デー
タ１面分で出発地から道路網上の各ノードへの最短距離
経路探索を行しＸ、１面分の経路探索が終了した時に目
的地に探索した経路が到達していなければ　探索結果デ
ータを探索結果記憶手段１０３に記憶させて、同じ詳し
さの道路網データで探索した道路が特定範囲の境界線上
で接続する隣の特定範囲の道路網データを探索する。こ
こで予め定めた特定枚数を探索し終えた時に目的地の位
置に経路探索した範囲が到達していなけれ（二　経路を
探索した道路網データの代わりに経路探索した詳しさよ
りも詳しくない道路網の道路網データで探索した特定範
囲の地域を包括する特定範囲の道路網データを読み込仏
　そして道路網上の共通する部分、例えばノードの経度
・緯度の位置に基づいて詳しい道路網上のノードと詳し
くない道路網上のノードを比較して位置が同一であるノ
ード、を選出して共通するノードとし　この共通するノ
ードの探索結果データを読み詰んだ詳しくない道路網上
の共通するノードに対応させて、詳しくない道路網上の
ノードに対応する探索結果データを作成す４　この新し
く作成した探索結果データに基づいて、読み込んだ詳し
くない道路網で再び予め定めた特定枚数の特定範囲の道
路網データ内を経路探索し目的地の位置を含む特定範囲
内を経路探索していなければ　探索した詳しくない道路
網データよりも更に詳しくない道路網データを用いて経
路探索を行う。また目的地の位置を含む特定範囲内を経
路探索していれは　探索した地図よりも詳しい道路網で
目的地の位置を含む特定範囲および接続する隣の特定範
囲を予め定めた特定枚数を捜し出しこの特定枚数につい
て道路網上の共通するノードを用いて探索結果データを
作成し　特定枚数内で探索を行１．％　　目的地に経路
か到達するまで上記の動作を繰り返す。

第３の実施例の動作をソフトウェアで実現する場合の説
明を以下に行う。

概略フローチャートは第２図と同様なものであり、処理
２０１、処理２０３は第１の実施例と同様の動作を行う
。第１の実施例と異なるのは　処理２０２で出発地また
は目的地を開始点として、１つの詳しさの地図において
予め定めた特定枚数の特定範囲の道路網データを経路探
索し　詳しさの異なる道路網間で道路網上で共通するノ
ードを用いて経路探索する道路網データの詳しさを切り
換えて、　２つ以上の詳しさの異なる道路網データを探
索して最短距離経路または最適経路を求める点である（
地図データ記憶手段１０２、探索結果記憶手段１０３お
よび探索手段１０４に相当）。

次に　探索処理２０２について、第１０図のフローチャ
ートを用いて更に詳しく説明すも　処理３０１から処理
３０４までは第１の実施例の第３図と同様の動作を行う
。そして、予め定めた特定枚数の特定範囲の道路網デー
タを探索し終っていないかどうかを判断１００１で判断
し　まだ特定枚数を探索していなければ　処理３０７、
処理３０８および処理３１０、処理３１１を第１の実施
例の第３図と同様に行し＼　処理３０３へ戻る。また　
判断１００１で特定枚数を探索し終っているときは　探
索した経路が目的地に到達しているかどうかを判断１０
０２で判断し　目的地に到達しているときは探索処理２
０２を終了すム　また目的地に到達していないときは、
　探索範囲が目的地の位置を含んでいるかどうかを判断
１００３で判断し　含んでいなければ探索した道路網よ
りも更に詳しくない道路網の道路網データに対応して、
探索した特定枚数の特定範囲内のノードの中から道路網
上で共通するノードを選出して、詳しくない特定範囲の
道路網上のノードに対応する探索結果データを作成して
探索結果記憶手段２０３に記憶し　処理１００５で特定
範囲の道路網の探索対象候補を全て詳しくない道路網デ
ータの特定範囲にして経路探索を詳しい道路網データか
ら詳しくない道路網データへ切り替えて、処理３０８へ
移る。また判断１００３で探索範囲が目的地の位置を含
んでいれば　処理１００６で探索した特定枚数の特定範
囲の探索結果データか収　探索した道路網よりも更に詳
しい道路網で記憶されている道路網データで目的地の位
置付近の予め定めた特定枚数の特定範囲で道路網上で共
通するノードを選出して、詳しい特定範囲の道路網上の
ノードに対応する探索結果データを作成して探索結果記
憶手段２０３に記憶し　処理１００７で特定範囲の道路
網の探索対象候補を全て詳しい道路網データの特定範囲
にして経路探索を詳しくない道路網データから詳しい道
路網データへ切り替えて、処理３０８へ移も 次に第３の実施例の動作の概要を第１１図を用いて説明
する。　１１０１は特定範囲で分割されたもっとも詳し
い道路網データの地図　１１０２は地図１１０は、りも
詳しくない道路網データの地＠　　１１０３は地図１１
０２よりも更に詳しくない道路網データの地ｅｆｌ　　
１１０４は出発地の位置＋１０５は目的地の位１ｉ！ｒ
、　　１１０６は出発地１１０４側で地図１１０１と地
図１１０２間の道路網上で共通するノード、　１１０７
は共通するノード１１０６を用いて地図１１０１から地
図１１０２へ探索する道路網データの詳しさを切り替え
るときの探索結果データを移す方向を示す矢印１１０８
は出発地１１０４側で地図１１０２と地図１１０３間の
道路網上で共通するノード、　１１０９は共通するノー
ド１１０８を用いて地図１１０２から地図１１０３へ探
索する道路網デニタの詳しさを切り替えるときの探索結
果データを移す方向を示す矢Ｅｌｌ　１１１０は目的地
１１０５側で地図１１０３と地図１１０２間の道路網上
で共通するノード、　１１１１は共通するノード１１１
０を用いて地図１１０３から地図１１０２へ探索する道
路網データの詳しさを切り替えるときの探索結果データ
を移す方向を示す矢Ｅｌｌ　　１１１２は目的地１１０
５側で地図１１０２と地図１１０１間の道路網上で共通
するノードｔ　　１１１３は共通するノード１１１２を
用いて地図１１０２から地図１１０１へ探索する道路網
データの詳しさを切り替えるときの探索結果データを移
す方向を示した矢印１１１４は探索により求めた経路の
一例である。

各地図において出発地１１０４及び目的地１１０５付近
では、　例えば４枚の特定範囲の道路網データを探索し
てから探索移行を行うと定めたとき、地図１１０１にお
いて出発地１１０４を含む４特定範囲の道路網データを
探索し　地図１１０２に共通するノード１１０６に対応
する探索結果データを１１０７の方向へ移して探索する
道路網データの詳しさを切り替えも　次に地図１１０２
で４特定範囲の道路網データを探索し　地図１１０３に
共通するノード１１０８に対応する探索結果データを１
１０９の方向に移して探索する道路網データの詳しさを
切り替えも　ここで、地図１１０３で４特定範囲の道路
網データを探索したとき目的地１１０５の位置が経路を
探索した範囲に含まれたた八　地図１１０２の目的地付
近の４特定範囲との共通するノード１１１０に対応する
探索結果データを１１１１の方向に移して地図１１０２
に探索する道路網を切り替えも　地図１１０２で４特定
範囲の道路網データを探索して目的地１１０５に探索し
た経路が到達していないときは、　地図１１０１との共
通するノード１１１２に対応する探索結果データを１１
１３の方向に移して探索する道路網データの詳しさを切
り替えて、地図１１０１で４特定範囲の道路網データを
探索して目的地１１０５に探索した経路が接続すること
により、出発地１１０４から目的地１１０５への最短距
離経路１１１４を求めることができも以上のようｔＱ　
　本実施例によれば複数の詳しさの異なる道路網データ
を記憶し　詳しさの異なる特定範囲の道路網データを用
いて探索範囲の拡大を行うために　出発地および目的地
付近以外の細かい道路を探索せず、探索時間を第１の実
施例よりも短縮することができ、かつ−度に大量の道路
網データを読み込んで経路探索に使用するメモリ量を増
大させることなく、少ないメモリ量で経路探索を行うこ
とができる。

次に本発明の第４の実施例について説明すも本発明は長
距離経路の探索等で経路探索に使用する道路網が広域に
わたるときで耘　使用するメモリ量を増大させることな
く、少ないメモリ量で経路探索を行うことができ、かつ
探索時間を第１の実施例よりも短縮することができ、な
おかつ探索に使用する特定範囲の道路網データを第３の
実施例よりも少なくする経路探索装置を提供することを
目的とするものであも 本発明の第４の実施例における経路探索装置のブロック
図は第１図と同様であるた八　この図を用いて説明する
。地点記憶手段１０１、地図データ記憶手段１０２、探
索結果記憶手段１０３、出力手段１０５は第３の実施例
と同様な構成である。

第３の実施例の構成と異なるの（ｉ　探索手段１０４で
、例えばＣＰＵを用いて、　１つの詳しさの道路網デー
タを用いて出発地の位置および目的地の位置の両方から
予め定めた乾固　例えば特定枚数の特定範囲の道路網デ
ータを特定範囲毎に経路探索して特定範囲毎に道路網上
のノードに対応する探索結果データを探索結果データ記
憶手段１０３に記憶させ、複数の詳しさの異なる道路網
間を道路網上の共通する部分、例えばノードの経度・緯
度を用いて、探索する道路網データを切り替えながら出
発地から目的地までの最短距離経路または最適経路を求
める点であも 次にこのように構成された第４の実施例の経路探索装置
について、以下その動作を説明する。

探索手段１０４は地点記憶手段１０１の記憶している出
発地および目的地を入力し　この出発地の位置および目
的地の位置の両方を開始点として最短距離経路または最
適経路を探索すム　これは例えば最短距離経路の探索を
行う場合には、　もっとも詳しい道路網の中か叙　先ず
出発地が含まれる特定範囲の道路網データ１面分を地図
データ記憶手段１０２から読み込へ　出発地から広がる
道路網に従って読み込んだ特定範囲内で出発地から道路
網上の各ノードへの最短距離経路探索を行しく探索結果
データを探索結果記憶手段１０３に記憶させも　そして
同じ詳しさの道路網データで予め定めた特定枚数まで特
定範囲を同様に探索する。

次に同し詳しさの道路網の中で、目的地が含まれる特定
範囲の道路網データを出発地と同様に予め定めた特定枚
数の特定範囲まで探索すも　そして出発地および目的地
の両方から探索した経路が接続していなければ　経路を
探索した詳しさの道路網の代わりにこの詳しさの道路網
データよりも詳しくない道路網データでの出発地側およ
び目的地側の特定範囲について、探索結果データから道
路網上の共通する部分、例えば道路網上で共通するノー
ドに対応する探索結果データを選出して、詳しくない道
路網上のノードに対応する探索結果データを作成し　出
発地側および目的地側の両方で詳しくない道路網の特定
範囲の道路網データと作成した探索結果データを用いて
、上記と同様に経路探索を行う。また出発地からの経路
と目的地からの探索した経路が接続すれば　出発地から
接続したノードへの経路と目的地から接続したノードへ
の経路をつなげて、出発地から目的地への最短距離経路
または最適経路として構成すも第４の実施例の動作をソ
フトウェアで実現する場合の説明を以下に行う。

概略フローチャートは第２図と同様であり、処理２０１
、処理２０３は第１および第３の実施例と同様の動作を
行う。第１および第３の実施例と異なるの（戴　処理２
０２で１つの詳しさの地図において、出発地の位置およ
び目的地の位置の両方を開始点として予め定めた特定枚
数の特定範囲の道路網データを経路探索し　詳しさの異
なる道路網間を道路網上の共通する部分、例えば道路網
上で共通するノードを用いて探索する道路網データの詳
しさを切り替えて、　２つ以上の詳しさの異なる道路網
データを探索して最短距離経路または最適経路を求める
点であも 次に　探索処理２０２について、第１２図のフローチャ
ートを用いて更に詳しく説明すも　処理２０１で記憶さ
れた出発地および目的地の位置を地点記憶手段１０１か
ら処理３０１で入力し　処理１２０１で１つの詳しさの
道路網データにおいて出発地を含む特定範囲の道路網デ
ータを経路探索を行う探索対象にして、処理１２０２で
探索対象となった出発地側で予め定めた特定枚数の特定
範囲の道路網データを経路探索すム　また　出発地側で
探索した同じ詳しさの道路網データにおいて処理１２０
３で目的地を含む特定範囲の道路網データを経路探索を
行う探索対象にして、処理１２０２で探索対象となった
目的地側で予め定めた特定枚数の特定範囲の道路網デー
タを経路探索すム　ここで探索した出発地側の経路と目
的地側の経路が接続していないかどうかを判断１２０４
で判断し　接続していれば処理２０２を終了すムまた接
続していなければ出発地側の探索結果データを探索した
詳しさの道路網よりも詳しくない道路網に対して道路網
上で共通するノードを選出して、詳しくない道路網上の
ノードに対応する探索結果データを処理１２０５で作成
して探索する道路網の詳しさを切り替えて、出発地側の
探索結果データを作成した特定範囲を処理１２０６で探
索対象にして、処理１２０２で探索対象となった出発地
側で予め定めた特定枚数の特定範囲内の道路網データを
経路探索すａ　また　目的地側でも出発地側で探索を切
り替えた同じ詳しさの道路網データに対して道路網上で
共通するノードを選出し詳しくない道路網上のノードに
対応する探索結果データを処理１２０７で作成して探索
する道路網の詳しさを切り替えて、目的地側の特定範囲
を処理１２０８で探索対象にして、処理１２０２で探索
対象となった目的地側で予め定めた特定枚数の特定範囲
内の道路網データを探索して、判断１２０４に戻も 次に　特定枚数探索処理１２０２について、第１３図の
フローチャートを用いて更に詳しく説明すも　処理１３
０１は処理１２０１、処理１２０３、処理１２０６およ
び処理１２０８で探索対象となった特定範囲の道路網デ
ータの中で出発地側では出発地からの最短到達距離の特
定範囲を捜し出し　目的地側では目的地からの最短到達
距離の特定範囲を捜し出して、その特定範囲の道路網デ
ータを読み込む。処理１３０２は処理１３０１で読み込
んだ特定範囲の道路網上のノードに対応する探索結果デ
ータを読み込む。ここで読み込んだ特定範囲の道路網デ
ータ１面分を処理３０３で経路探索し　探索した特定範
囲内の探索結果データを処理３０４で記憶する。次に予
め定めた特定枚数の特定範囲を探索し終っていないかど
うかを判断１３０３で判断し　探索し終っていれば処理
１２０２を終了する。探索し終っていなければ・処理３
０７で探索した特定範囲の道路網に特定範囲の境界上で
接続する隣の特定範囲の探索結果データを探索した探索
結果データから作成して記憶し最短距離で到達した特定
範囲を処理１３０４で選出して、選出した特定範囲の道
路網データを処理３１０で読み込へ　選出した特定範囲
の道路網上のノードに対応する探索結果データを処理３
１１で読み込んで処理３０３へ戻も 次に第４の実施例の動作の概要を第１４図を用いて説明
す＆　　１４０１は特定範囲で分割されたもっとも詳し
い道路網データの地ａ　１４０２は地図１４０は、りも
詳しくない道路網データの地Ｅｌ　　１４０３は地図１
４０２よりも更に詳しくない道路網データの地ａ　　１
４０４は出発地の位１１４０５は目的地の位ＷｊＬ　１
４０６は出発地１４０４側で地図１４０１と地図１４０
２間の道路網上で共通するノード、　１４０７は共通す
るノード１４０６を用いて地図１４０１から地図１４０
２へ探索する道路網データの詳しさを切り替えるときの
探索結果データを移す方向を示す矢咀１４０８は目的地
１４０５側で地図１４０１と地図１４０２間の道路網上
で共通するノード、　１４０９は共通するノード１４０
８を用いて地図１４０１から地図１４０２へ探索する道
路網データの詳しさを切り替えるときの探索結果データ
を移す方向を示す矢Ｅｌｌ　　１４１０は出発地１４０
４側で地図１４０２と地図１４０３間の道路網上で共通
するノード、　１４１１は共通するノード１４１０を用
いて地図１４０２から地図１４０３へ探索する道路網デ
ータの詳しさを切り替えるときの探索結果データを移す
方向を示す矢Ｅｌｌ　　１４１２は目的地１４０５側で
地図１４０２と地図１４０３間の道路網上で共通するノ
ードミ　１４１３は共通するノード１４１２を用いて地
図１４０２から地図１４０３へ探索する道路網データの
詳しさを切り替えるときの探索結果データを移す方向を
示した矢Ｅｌ１１４１４は出発地１４０４側の探索範囲
と目的地１４０５側の探索範囲が接続した境界線　１４
１５は探索により求めた経路の１例であム　各地図にお
いて出発地１４０４及び目的地１４０５付近では４枚の
特定範囲の道路網データを探索してから探索移行を行う
と定めたとき、地図１４０１において出発地１４０４を
含む４特定範囲の道路網データを探索し　また目的地１
４０５を含む４特定範囲の道路網データを探索すム　こ
こで地図１４０２へ探索する道路網データの詳しさを切
り替えるために　出発地１４０４側では共通するノード
１４０６に対応する探索結果データを１４０７の方向へ
移して４特定範囲の道路網データを探索し　目的地１４
０５側では共通するノード１４０８に対応する探索結果
データを１４０９の方向へ移して４特定範囲の道路網デ
ータを探索すも　次に地図１４０３へ探索する道路網デ
ータの詳しさを切り替えるために　出発地１４０４側で
は共通するノード１４１０に対応する探索結果データを
１４１１の方向に移して４特定範囲の道路網データを探
索し　目的地Ｉ４０５側では共通するノード１４１２に
対応する探索結果データを１４１３の方向に移して４特
定範囲の道路網データを探索すム　ここで、地図１４０
３で出発地１４０４側および目的地１４０５側の両方の
探索範囲が接続する境界線１４１４で経路１４１５が接
続したた八　探索を終了して経路１４１５を出発地１４
０４から目的地１４０５への経路に再構成して最短距離
経路または最適経路を求めることができム以上のよう置
　本実施例によれば　詳しさの異なる特定範囲の道路網
間を探索移行するときに出発地および目的地の両方を開
始点として経路を探索した範囲のみを用いて探索結果デ
ータを移して探索する道路網データの詳しさを切り替え
るた敢第１の実施例よりも探索時間を短縮することがで
き、出発地又は目的地に道路網が接続していないノード
で探索結果データを移す事がないたム　探索に使用する
道路網データを第３の実施例よりも少なくすることがで
き、かつ−度に大量の道路網データを読み込むための大
容量のメモリを備えることなく、少ないメモリ量で経路
探索を行うことができも な耘　第１、第２、第３および第４の実施例において、
道路網上のノード間の平均旅行時間を基にして距離によ
る探索ではなく最短旅行時間経路として最適経路を求め
てもよしも　また経路探索を行うときの出発地の位置は
現在位置に設定して探索を行ってもよ（ち　また経路を
探索する具体的な方法は上記した方法以外でもよ鶏　ま
た第１の実施例においてメモリの許す限り特定範囲の道
路網データおよび特定範囲の地図の道路網上のノードに
対応する探索結果データを保持して、データを読み込ん
だり記憶したりする時間を削減してもよ（ち　また第３
の実施例において、地図データ記憶手段に複数の詳しさ
の異なる道路網データ間の道路網上で共通するノードが
同一であることを示すデータを予め合わせて記憶させた
地図データ記憶手段を用いて、道路網上の共通するノー
ドに対応して探索結果データを移すときに利用すること
により、共通するノードを選出する時間を短縮するよう
にしてもよ１、％　　また複数の詳しさの異なる道路網
データ間の道路の共通する部分が同一であることを示す
データを予め合わせて記憶させた地図データ記憶手段を
用いて、道路網上の共通する道路に対応して探索結果デ
ータを移すときに利用することにより、道路の共通する
部分を選出する時間を短縮するようにしてもよｕ％　　
また第３および第４の実施例において、予め定めた枚数
の特定範囲を探索してから探索する道路網データの詳し
さを切り替えるときく　予め定めた探索距離の範囲を探
索してから探索する道路網データの詳しさを切り替えて
もよＬも 発明の詳細 な説明したように　本発明によれ（瓜　特定範囲毎の道
路網データを読み込んで経路探索を行うので、−度に大
量の道路網データを読み込まなくてもよく、大容量のメ
モリを備えることなく、少ないメモリ量で経路探索を行
しＸ、探索処理を高速に行うことができる。

【図面の簡単な説明】

菓１図は本発明における第１の実施例の経路探索装置の
ブロックは　第２図は第１の実施例の動作を示す概略フ
ローチャート、第３図は第１の実施例の探索処理の一例
を示すフローチャート、第４図は第１の実施例の特定範
囲内探索処理の一例を示すフローチャート、第５図は探
索に使用する道路網の一例を示す説明図　第６図は同装
置における探索時のデータの構成図　第７図は同装置に
おける動作の説明図　第８図は本発明における第２の実
施例の経路探索装置の探索処理の一例を示すフローチャ
ート、第９図は同装置における動作の説明＠　第１０図
は本発明における第３の実施例の経路探索装置の探索処
理の一例を示すフローチャート、第１１図は同装置にお
ける動作の概要を示す説明図　第１２図は本発明におけ
る第４の実施例の経路探索装置の探索処理の一例を示す
フローチャート、第１３図は第４の実施例の特定枚数探
索処理の一例を示すフローチャート、第１４図は同装置
における動作の概要を示す説明図であム １０１・・・地点記憶手段、　１０２・・・地図データ
記憶手段、　＋０３・・・探索結果記憶半没１０４・・
・探索手段、　１０５・・・出力手北代理人の氏名　弁
理士　粟野重孝　はか１名第 図 第 図 第 図 ■ 第 図 第 図 第１３図

Claims (8)

【特許請求の範囲】
1. （１）出発地及び目的地の位置を記憶した地点記憶手段
   と、道路網データを複数の特定範囲に分割して記憶し、
   それぞれの分割された特定範囲道路網データの接続関係
   データをあわせて記憶する地図データ記憶手段と、出発
   地または目的地を開始点とし、最短距離経路または最適
   経路を１つあるいは複数の特定範囲内において探索する
   探索手段と、前記探索手段で探索した結果を記憶する探
   索結果記憶手段と、探索した結果を前記探索結果記憶手
   段から読みだして出力する出力手段とを備えたことを特
   徴とする経路探索装置。
2. （２）探索手段は、少なくとも１つの特定範囲で最短距
   離経路または最適経路を探索するときに特定範囲毎の道
   路網データを用いて特定範囲毎に探索し、この探索結果
   データを探索結果記憶手段に記憶することを特徴とする
   請求項１記載の経路探索装置。
3. （３）接続関係データは、分割された境界で隣接する特
   定範囲との道路接続データであることを特徴とする請求
   項１または２記載の経路探索装置。
4. （４）探索手段は、２つ以上の特定範囲の道路網データ
   毎に１つの特定範囲の道路網データと同じデータ構成に
   変換し、この変換した道路網データ毎に探索し、この探
   索結果データを探索結果記憶手段に記憶することを特徴
   とする請求項１、２または３記載の経路探索装置。
5. （５）地図データ記憶手段は、詳しさの異なる複数の道
   路網データをそれぞれの特定範囲毎に分割して記憶し、
   探索手段は詳しさの異なる道路網データを用いて特定範
   囲毎に探索し、探索結果データを探索結果記憶手段に記
   憶させることを特徴とする請求項１、２、３または４記
   載の経路探索装置。
6. （６）地図データ記憶手段は、詳しさの異なる複数の道
   路網データをそれぞれの特定範囲毎に分割して記憶する
   とともに、詳しさの異なる道路網データ間で道路網上の
   共通する地点が同一であることを示すデータを合わせて
   記憶し、探索手段はこのデータを用いて詳しさの異なる
   道路網データ間で探索を切り換えて探索し、その結果を
   探索結果記憶手段に記憶させることを特徴とする請求項
   ５記載の経路探索装置。
7. （７）地図データ記憶手段は、詳しさの異なる複数の道
   路網データをそれぞれの特定範囲毎に分割して記憶する
   とともに、詳しさの異なる道路網データ間で道路の共通
   する部分が同一であることを示すデータを合わせて記憶
   し、探索手段はこのデータを用いて前記詳しさの異なる
   道路網データ間で探索を切り換えて探索し、探索結果デ
   ータを探索結果記憶手段に記憶させることを特徴とする
   請求項５記載の経路探索装置。
8. （８）探索手段は特定範囲毎の道路網データを出発地の
   位置および目的地の位置の両方から特定範囲毎に探索し
   かつ詳しさの異なる道路網データを２つ以上用いて最短
   距離経路または最適経路を探索し、探索結果を探索結果
   記憶手段に記憶することを特徴とする請求項５記載の経
   路探索装置。