(57)【要約】【課題】ナビゲーション装置において、ルート探索時間をより短くし、ユーザの探索待ち時間を低減する。【解決手段】ナビゲーション装置は、入力操作部、ナビゲーション情報を記憶する情報記憶部、及びルートを探索する制御部を備える。ユーザが入力操作部で出発地と目的地を入力し（Ｓ１）、所定時間Ｔｓを設定すると（Ｓ２）、ＣＰＵ１１は、ルート探索を開始し（Ｓ３）、探索時間ＴがＴｓを越えると（Ｓ４でＹＥＳ）、現予測地点から継続探索した場合の継続探索予測時間Ｔａを求め（Ｓ５）、同時に現レイヤを上位レイヤに戻して再探索した場合の再探索予測時間Ｔｂを求める（Ｓ６）。ＣＰＵ１１はＴｂがＴａを越えないときは（Ｓ７でＹＥＳ）、ルートの再探索処理を行い（Ｓ８）、Ｓ７でＮＯのときは現予測地点からのルート探索を継続する（Ｓ９）。これにより、より短い時間によるルート探索を可能にし、ユーザの探索待ち時間を低減することができる。【選択図】図２
2008292416.tif 000002
【特許請求の範囲】
【請求項１】
車輌に搭載され、目的地を入力するための入力手段と、現在地から前記入力された目的地までの候補ルートを探索するルート探索手段と、前記ルート探索手段によるルート探索に必要なナビゲーション情報を記憶する情報記憶手段と、を備えたナビゲーション装置において、
前記ルート探索手段が前記ナビゲーション情報に基いて現在地から前記目的地までの候補ルートを探索するのに必要な探索時間を予測する探索時間予測手段と、
前記ルート探索手段による前記候補ルートの探索時間と比較するための所定時間を設定する所定時間設定手段と、
前記ルート探索手段による前記候補ルートの探索時間が、前記所定時間設定手段で設定された所定時間を越えた場合に、前記候補ルートを絞ってルートを再探索する再ルート探索手段と、
前記再ルート探索手段で目的地までの候補ルートを再探索するために必要な再探索時間を予測する再探索時間予測手段と、
装置全体を制御する制御手段と、を備え、
前記制御手段は、
前記ルート探索手段による前記候補ルートの探索時間が前記所定時間設定手段で設定された所定時間を越えた場合に、前記ルート探索手段でそのまま継続して目的地までの候補ルートを探索した場合の継続探索予測時間を前記探索時間予測手段より予測し、この継続探索予測時間と、前記再探索時間予測手段で予測した再探索予測時間とを比較して、前記継続探索予測時間の方が短いときは、前記ルート探索手段による候補ルートの探索を継続し、前記再探索予測時間の方が短いときは、前記再ルート探索手段による候補ルートの再探索処理を実行することを特徴とするナビゲーション装置。
【請求項２】
前記ナビゲーション情報の探索データは、下位の道路から上位の道路までの詳細度に応じて階層化された複数のレイヤとして記録され、前記ルート探索手段及び前記再ルート探索手段は、複数のレイヤの探索データを使用して候補ルートを探索又は再探索することを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
前記再ルート探索手段は、出発地及び目的地付近以外においては、現在のレイヤより下位レイヤの探索を止め、現在のレイヤより上位レイヤに戻って再探索することを特徴とする請求項２に記載のナビゲーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザによって指定された所定の地点間のルートを探索して、探索されたルートをユーザに提示するナビゲーション装置に関する。
【背景技術】
【０００２】
従来、ナビゲーション装置は、ナビゲーション情報として、ルート探索するための探索データファイルを情報記憶部に記憶し、この探索データファイルからルートを決定するための地図データ等の探索データを読み出し、現在地から目的地までのルートを探索して、探索したルートをディスプレイに表示することによってルート案内する。
【０００３】
従来のナビゲーション装置において、探索データファイルにおける探索データが、下位から上位にかけて複数のレイヤから構成される階層構造のものが知られている、この種の装置における探索データは、例えば、レイヤ１〜３から成る階層構造を有し、レイヤ１においては、高速道路、有料道路等の高速・有料道、国道、主要地方道、県道等の一般道のほかに、細街路（一般道路より道幅の狭い道路）、導入路等のすべての道路が記録される。また、レイヤ２においては、レイヤ１の道路のうち、高速道路、有料道路等の高速・有料道、国道、主要地方道等のように、道幅が大きい道路、車線数が多い道路、制限速度が高い道路、車両の流れが良い道路等が記録される。さらに、レイヤ３においては、レイヤ２の道路のうち、更に道幅が大きい道路、車線数が多い道路、制限速度が高い道路、車両の流れが良い道路等が記録される。なお、各レイヤ１〜３はデータファイルによって形成される。
【０００４】
また、一般に、運転者は、数１００ｋｍの長い距離を走行する場合は、高速道路を使用することが多く、数１０ｋｍの中程度の距離を走行する場合は、国道、主要地方道、県道等を使用することが多い。従って、走行する距離によって、各レイヤ１〜３の構成、例えば、階層の数、各レイヤ１〜３を構成する道路、各レイヤ１〜３の探索データの領域等が決定されるようになっている。
【０００５】
また、距離が短いルートを探索する場合、レイヤ１の探索データが主に使用され、距離が長いルートを探索する場合、各レイヤ１〜３の探索データが使用される。これは、距離が長いルートを探索する場合に、レイヤ１だけを使用すると、ルートを探索するための処理、すなわち、ルート探索処理を行うために必要なメモリ容量を確保することが困難となり、ルートを探索することができなくなったり、ルート探索処理の処理速度が低くなったりするからである。
【０００６】
また、出発地及び目的地に近いほど、下位のレイヤの探索データが使用され、出発地及び目的地から離れるほど、上位のレイヤの探索データが使用される。そして、出発地及び目的地の付近においては、レイヤ１の探索データが使用され、すべての道路の探索データが探索の対象になる。
【０００７】
しかし、道路地図が詳しくなってくると、各レイヤの地図データも増加するので、目的地の探索に時間を要していた。このため、ユーザは、ルート探索における待ち時間が長くなることにより、苛立ったり、又は不安を感じて、再度、探索をやり直すなどして余計に時間を費やすことがあった。特に、探索すべき地点間の距離が長い場合などでは、探索ルートが多くなるのでルート探索に時間を要することが多く、ルート探索時間を短縮することが望まれていた。
【０００８】
ところで、特許文献１に示されるように、ルート探索前にルート探索に要する時間を予測する探索時間予測手段を設け、ルート探索のために多くの処理時間を必要とするような場合には、ユーザにルート探索のための処理時間を通知するなど、ユーザを苛立たせたり、不安を感じさせないような対処を可能としたルート探索装置が知られている。しかし、この装置は、ルート探索時に処理時間を通知することはできるが、ルート探索時間を短くすることができなかった。
【０００９】
また、特許文献２に示されるように、ルート探索前にルート探索に要する探索時間を予測し、予測された探索時間に応じて表示装置の表示画面を変更制御するナビゲーション装置が知られている。しかし、この装置は、ルート探索時間が長い場合に、探索が終わる前に車両を早めに発進させるようにするものであり、ルート探索時間を短くすることができなかった。
【００１０】
また、特許文献３に示されるように、目的地までの探索されたルートを分割し、分割されたルートを再び探索して、この再探索処理による探索結果に基づいて探索ルートを決定するナビゲーションシステムが知られている。しかしながら、このシステムでは、分割されたルートを再探索処理し、必要に応じて分岐道路を探索データの対象にしてルート探索するので、ルート探索における探索ルート数が増加して、ルート探索時間が長くなる場合があった。
【特許文献１】特開２００４‐１３８５０９号公報
【特許文献２】特開２００４‐１３８５０７号公報
【特許文献３】特開２００３‐１３０６６８号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、上記の問題を解決するためになされたものであり、ルート探索を行って目的地までのルート案内を行うナビゲーション装置において、より短い処理時間でルート探索を行うことができ、ユーザのルート探索の待ち時間を低減できるナビゲーション装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するため請求項１の発明は、車輌に搭載され、目的地を入力するための入力手段と、現在地から前記入力された目的地までの候補ルートを探索するルート探索手段と、前記ルート探索手段によるルート探索に必要なナビゲーション情報を記憶する情報記憶手段と、を備えたナビゲーション装置において、前記ルート探索手段が前記ナビゲーション情報に基いて現在地から前記目的地までの候補ルートを探索するのに必要な探索時間を予測する探索時間予測手段と、前記ルート探索手段による前記候補ルートの探索時間と比較するための所定時間を設定する所定時間設定手段と、前記ルート探索手段による前記候補ルートの探索時間が、前記所定時間設定手段で設定された所定時間を越えた場合に、前記候補ルートを絞ってルートを再探索する再ルート探索手段と、前記再ルート探索手段で目的地までの候補ルートを再探索するために必要な再探索時間を予測する再探索時間予測手段と、装置全体を制御する制御手段と、を備え、前記制御手段は、前記ルート探索手段による前記候補ルートの探索時間が前記所定時間設定手段で設定された所定時間を越えた場合に、前記ルート探索手段でそのまま継続して目的地までの候補ルートを探索した場合の継続探索予測時間を前記探索時間予測手段より予測し、この継続探索予測時間と、前記再探索時間予測手段で予測した再探索予測時間とを比較して、前記継続探索予測時間の方が短いときは、前記ルート探索手段による候補ルートの探索を継続し、前記再探索予測時間の方が短いときは、前記再ルート探索手段による候補ルートの再探索処理を実行するものである。
【００１３】
請求項２の発明は、請求項１のナビゲーション装置において、前記ナビゲーション情報の探索データは、下位の道路から上位の道路までの詳細度に応じて階層化された複数のレイヤとして記録され、前記ルート探索手段及び前記再ルート探索手段は、複数のレイヤの探索データを使用して候補ルートを探索又は再探索するものである。
【００１４】
請求項３の発明は、請求項２のナビゲーション装置において、前記再ルート探索手段は、出発地及び目的地付近以外においては、現在のレイヤより下位レイヤの探索を止め、現在のレイヤより上位レイヤに戻って再探索するものである。
【発明の効果】
【００１５】
請求項１の発明によれば、継続探索予測時間の方が短いときは、ルート探索手段による候補ルートの探索を継続し、再探索予測時間の方が短いときは、再ルート探索手段による候補ルートの再探索処理を実行するので、より短い探索時間でルート探索を行うことができる。これにより、迅速なルート探索を行うことができるので、ユーザのルート探索時の待ち時間を短くすることができ、利便性が高まる。
【００１６】
請求項２の発明によれば、下位の道路（例えば、一般道路より狭い道幅の道路）から上位の道路（例えば、高速道路や国道）までの各種道路を含む複数のレイヤを用いて、ルート探索を行えるので、上記請求項１の効果を的確に得ることができる。
【００１７】
請求項３の発明によれば、再ルート探索手段は、出発地及び目的地付近以外においては、現在のレイヤより下位レイヤの探索を止め、現在のレイヤより上位レイヤに戻って再探索するので、特に上位レイヤの利用が増加する遠方の目的地へのルート探索において、より速くルートを探索することができる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明の実施の形態を図面を参照して説明する。図１は本発明のナビゲーション装置１のブロック構成を示す。本実施形態のナビゲーション装置１は、入力操作部（入力手段）２、位置検出部３、情報記憶部（情報記憶手段）４、表示部５、音声案内部６、交通情報受信部７、及び装置全体を制御する制御部（制御手段）１０を備え、データベースに登録されている目的地の候補の中からユーザにより選択された目的地までのルートを案内するものである。
【００１９】
入力操作部２は、出発地、目的地などルート案内に関する情報の入力に用いられる。また、入力操作部２は、それぞれタッチ操作、キー操作で、ルート探索条件を入力したり、ルート案内をリクエストしたりできる操作パネル２１と、装置をリモコン操作するためのリモコン２２と、後述のルート探索部１１ａによる候補ルートの探索時間と比較するための所定時間を設定する所定時間設定部（所定時間設定手段）２３とを有する。操作パネル２１は、後述の表示部５の表示画面上にタッチパネルを設けて構成される。この入力操作部２の操作により、ユーザは、目的地の候補の探索、ディスプレイ画面の設定変更等の各種の指示や設定を行うことができる。なお、所定時間設定部２３は、リモコン２２の中に選択キーのようにして設けてもよい。
【００２０】
位置検出部３は、衛星航法システム（ＧＰＳ）を利用して車両の緯度経度等の現在位置情報をＧＰＳアンテナから入手するＧＰＳ受信機３１、車両の進行方位を、地磁気を利用することにより絶対方位で検出する地磁気センサ３２、車両の進行方位を相対方位で検出するジャイロセンサ３３、車輪の回転数等から車両の走行距離を検出する距離センサ３４を備えている。この位置検出部３は、上記ＧＰＳ受信機３１をはじめ各センサからの位置情報、方位情報、距離情報等を用いて車両の現在位置を検出する。
【００２１】
情報記憶部４は、ナビゲーション用のプログラム及びデータなどルート探索に必要な情報であるルート探索情報を記憶した外部記憶装置で、例えばＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等からなっている。情報記憶部４には、ルート探索などの処理を行うためのプログラム、ルート案内に必要な表示出力制御のプログラム及びデータ、音声案内に必要な音声出力制御を行うためのプログラム及びそれに必要なデータが格納されている。情報記憶部４に記憶されるルート探索情報のデータは、地図データ、道路データ、有料道路／フェリー利用料金データ、案内データ、マップマッチングデータ、目的地データ、登録地点データ（住所、電話番号等）、ジャンル別データ、カレンダーデータ等のファイルから構成される。なお、ＣＤ−ＲＯＭにデータのみを格納し、プログラムを制御部１０に格納することも可能である。
【００２２】
上記ルート探索情報のデータには、さらに、ルート探索するために読み出される探索データを格納する探索データファイルが含まれる。また、探索データは、下位から上位にかけての複数のレイヤ（ここでは、レイヤ１〜５）から成る階層構造を有する。レイヤ１においては、高速道路、有料道路等の高速・有料道、国道、主要地方道、県道等の一般道のほかに、細街路（一般道路より道幅の狭い道路）、導入路等のすべての道路が記憶され、レイヤ２においては、レイヤ１の道路の中で、高速道路、有料道路等の高速・有料道、国道、主要地方道、県道等の一般道の道路が記憶されている。レイヤ３においては、レイヤ２の道路の中で、高速道路、有料道路等の高速・有料道、国道、主要地方道のように、道幅が大きい道路、車線数が多い道路、車両の流れが良い道路等が記憶されている。レイヤ４においては、レイヤ３の道路の中で、高速道路、有料道路等の高速・有料道、国道等のような、さらに道幅が大きい道路、車線数が多い道路等が記憶されている。そして、レイヤ５においては、レイヤ４の道路のうち、より制限速度が高い道路、車両の流れが良い道路が記憶されている。なお、各レイヤ１〜５はデータファイルによって形成される。
【００２３】
表示部５は、簡易型の液晶表示器等により構成されており、ユーザに必要な案内情報を表示画面に表示する。ここでは、制御部１０が処理する地図データや案内データに基づき、目的地に関する情報、目的地名、時刻、距離及び目的地へのルート、及びルート探索時間等を表示する。また、表示部５は、表示画面に設けたタッチパネル等を使用して操作パネル２１として使用することができ、ユーザが画面に触れる、或いは画面をなぞることにより、地点入力、道路入力等を行えるように構成されている。
【００２４】
音声案内部６は、ルート案内、ルート探索時間案内等を音声により行うものであり、後述の制御部１０で形成された案内音声信号を出力する音声出力部６１と、音声出力部６１からの出力音声を拡声するスピーカ６２を備えている。この音声案内部６の音声案内により、運転者は、表示部５を見ずにルート情報や、ルート探索時間等を知ることができる。
【００２５】
交通情報受信部７は、車両外部の現在の道路交通情報を逐次受信するＶＩＣＳ・ＦＭ多重受信機７１を備える。ＶＩＣＳ（Ｖｅｈｉｃｌｅ  Ｉｎｆｏｒｍａｔｉｏｎ  ＆  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｙｓｔｅｍ）は、道路交通情報をリアルタイムで提供するもので、ＦＭ多重（文字放送）、電波ビーコン、光ビーコンにより情報を送信する。このＶＩＣＳからの交通渋滞情報や交通事故情報などの最新の道路交通情報は、制御部１０に伝達され、制御部１０は、この道路交通情報を加味して、目的地へのルート探索及びルート探索時間の計算等を行うことができる。
【００２６】
制御部１０は、ＣＰＵ１１、フラッシュメモリ１２、ＲＯＭ１３、ＲＡＭ１４を有する。ＣＰＵ１１は、ルート探索部（ルート探索手段）１１ａ、探索時間予測部（探索時間予測手段）１１ｂ、再ルート探索部（再ルート探索手段）１１ｃ、再探索時間予測部（再探索時間予測手段）１１ｄを有し、情報記憶部４のルート探索用の探索データ情報に基くルート探索処理、ルート案内情報の出力、出力案内情報の表示制御の他、種々の演算処理を実行する。
【００２７】
上記ＣＰＵ１１において、ルート探索部１１ａは、ユーザが入力操作部２で目的地を入力すると、現在地から目的地までの候補ルートを探索する。探索時間予測部（探索時間予測手段）１１ｂは、ルート探索部１１ａがナビゲーション情報に基いて現在地から目的地までの候補ルートを探索するのに必要な探索時間を予測する。再ルート探索部（再ルート探索手段）１１ｃは、ルート探索部１１ａによる候補ルートの探索時間が、所定時間設定部２３で設定された所定時間を越えた場合に、候補ルートを絞ってルートを再探索する。再探索時間予測部（再探索時間予測手段）１１ｄは、再ルート探索部１１ｃで目的地までの候補ルートを再探索するために必要な再探索時間を予測する。
【００２８】
フラッシュメモリ１２は、情報記憶部４のＣＤ−ＲＯＭからプログラムを読み込んで格納する。ＲＯＭ１３は、フラッシュメモリ１２のプログラムチェック、及びフラッシュメモリ１２に記憶されたプログラムやデータに基いて情報記憶部４に格納されたプログラムやデータの更新処理を行うためのプログラムを格納し、ＲＡＭ１４は、探索された目的地の地点座標、道路名等の探索されたルート案内情報や演算処理中のデータを一時的に格納する。また、制御部１０は、ＣＰＵ１１からの音声出力制御信号に基づいて情報記憶部４から読み出した音声をアナログ信号に変換して音声案内信号として音声出力部６１に出力する音声プロセッサ、位置検出部３の各センサからのセンサ信号を取り込むためのセンサ入力インタフェース、及び移動時間等の時間計測のための時計などを備えている。なお、本実施形態で使用するプログラムは全て情報記憶部４に格納されてもよいし、または、それらプログラムの一部または全てが制御部１０のＲＯＭ１３に格納されていてもよい。
【００２９】
本実施形態のナビゲーション装置のシステム全体の流れを説明すると、予め所定時間設定部２３で、ルート探索部１１ａによる候補ルートの探索時間と比較するための所定時間を設定し、データベースに記憶しておく。ユーザが入力操作部２で出発地と目的地を入力すると、ルート探索部１１ａは、出発地のレイヤからスタートして、各レイヤを用いたルート探索を開始する。ＣＰＵ１１は、ルート探索部１１ａによる候補ルートの探索時間が所定時間設定部２３で予め設定された所定時間を越えた場合に、ルート探索部１１ａでそのまま継続して目的地までの候補ルートを探索した場合の継続探索予測時間を探索時間予測部１１ｂにより予測すると共に、候補ルートを再探索した場合の再探索予測時間を再探索時間予測部１１ｄにより予測する。さらに、探索時間予測部１１ｂで予測した継続探索予測時間と、再探索時間予測部１１ｄで予測した再探索予測時間とを比較する。そして、継続探索予測時間の方が短いときは、ルート探索部１１ａによる候補ルートの探索を継続し、再探索予測時間の方が短いときは、再ルート探索部１１ｃによる候補ルートの再探索処理を実行する。これにより、ＣＰＵ１１は、ルート探索時間が所定時間を経過すれば、自動的により短い探索時間で行えるルート探索に切り替えることができるので、ルート探索時間を短くすることができる。
【００３０】
次に、本実施形態のナビゲーション装置１の動作手順について、図２のフローチャートを参照して説明する。ユーザが、入力操作部２で出発地と目的地を入力し（Ｓ１）、続いて所定時間設定部２３において、所定時間Ｔｓを設定すると（Ｓ２）、ルート探索部１１ａは、レイヤを用いたルート探索を開始する（Ｓ３）。そして、ＣＰＵ１１は、ルート探索部１１ａによるルート探索時間Ｔが所定時間Ｔｓを越えると（Ｓ４でＹＥＳ）、探索時間予測部１１ｂで現在のレイヤにおける現在の予測地点から継続して目的地を探索した場合の継続探索予測時間Ｔａを求め（Ｓ５）、同時に、再探索時間予測部１１ｄで現在のレイヤをそれ以前の上位レイヤに戻して、ルート探索を再計算処理した場合の再探索予測時間Ｔｂを求める（Ｓ６）。ここで、ＣＰＵ１１は、再探索予測時間Ｔｂが継続探索予測時間Ｔａより短いときは（Ｓ７でＹＥＳ）、再ルート探索部１１ｃでルートの再探索処理を行い（Ｓ８）、再探索処理で探索されたルートを表示部５で案内する（Ｓ１１）。また、Ｓ７でＮＯのときは、現在の予測地点からのルート探索処理を継続し（Ｓ９）、継続探索処理で探索されたルートを同様に表示部５で案内する（Ｓ１１）。また、Ｓ４でＮＯの場合に、ルート探索処理が終了している場合は（Ｓ１０でＹＥＳ）、探索されたルートを表示部５で案内し（Ｓ１１）、Ｓ１０でＮＯの場合は、Ｓ４に戻ってＳ４以降のステップを繰り返す。
【００３１】
図３（ａ）、（ｂ）を参照して、上記動作手順に沿ったルート探索例を説明する。これらの図において、左端の上下方向には、低いレイヤのレイヤ１から高いレイヤのレイヤ５までのレイヤブロックを番号順で示す。また、横方向には、各レイヤのルートにおける複数の分岐点を表し、これら分岐点を分岐ブロックＢ１〜Ｂｎとして示す。すなわち、探索ルートは、各レイヤ内、又はレイヤ間の分岐ブロックを結ぶ形で探索される。ここで、各分岐ブロックにおける探索ポイントをＰ１、Ｐ２、・・・Ｐｎで示し、Ｐ１は出発点、Ｐｎは目的地を示す。
【００３２】
図３（ａ）は、当初のルート探索の例を示し、当初探索された初期ルート（太線で表示）の途中までのパスを示す。この初期ルートのパス（経路）では、先ず、レイヤ４の分岐ブロックＢ１の出発地Ｐ１において、選択可能だったパス（点線で表示）ＰＴ１〜ＰＴ４からパスＰＴ２が選ばれレイヤ４の分岐ブロックＢ２のＰ２に結ばれる。続いて、Ｐ２で選択可能だったパスＰＴ５〜ＰＴ８からパスＰＴ７が選ばれ、このパスＰＴ７がレイヤ３の分岐ブロックＢ３のＰ３に結合される。また、Ｐ３で選択可能だったパスＰＴ９〜ＰＴ２からパスＰＴ１２が選択され、このパスＰＴ１２が、レイヤ２の分岐ブロックＢ４のＰ４に結ばれる。さらに、Ｐ４で選択可能だったパスＰＴ１３〜ＰＴ１６からパスＰＴ１５が選択され、このパスＰＴ１５がレイヤ２の分岐ブロックＢ６のＰ５に結合され、これにより、Ｐ１からＰ５までのパスが探索される。この探索の途中において、ルート探索部１１ａによるルート探索時間Ｔが所定時間Ｔｓになったとすると、ＣＰＵ１１は、このまま探索を続けるか、再探索するかを判断する。
【００３３】
図３（ｂ）は、上記図３（ａ）における初期ルート探索で、Ｐ５まで探索した時点で、ルート探索時間Ｔが所定時間Ｔｓを越えたとき、再探索予測時間Ｔｂが継続探索予測時間Ｔａより短い場合において、再ルート探索部１１ｃでルートの再探索処理を行って探索した再探索ルート（二重線で示す）の例を示す。この再探索ルートでは、先ず、レイヤ２における探索ポイントのＰ５から、Ｐ４に戻り（点線の矢印で示す）、さらにレイヤ４の分岐ブロックＢ２のＰ２まで戻して、レイヤ４のＰ２からレイヤが低下しない範囲（出発地、目的地近傍は除く）で（レイヤ４とレイヤ５の範囲で）ルートを再探索する。
【００３４】
このルートの再探索では、先ず、レイヤを低下させないことを考慮して、Ｐ２からパスＰＴ５とパスＰＴ６が選択可能であるが、同じレイヤ４のパスＰＴ６が選択され、レイヤ４の分岐ブロックＢ３のＰ６に結合される。Ｐ６からのパスは、パスＰＴ２０〜パスＰＴ２２から選択可能であるが、下位レイヤのパスＰＴ２２を無視し（一点鎖線で示す）、上位のレイヤに位置するレイヤ５の分岐ブロックＢ４のＰ７に繋がるパスＰＴ２１を選択している。そして、Ｐ７からは、同じレイヤ内の分岐ブロックＢｎ−２のＰ８まで直進し、目的地Ｐｎに近付くと、より詳細な地図が必要なので、Ｐ８でパスＰＴ２４を選択して、目的地と同じレイヤ３の分岐ブロックＢｎ−１のＰ９を選び、最終の分岐ブロックＢｎの目的地Ｐｎを探索する。これにより、再探索ルートは、出発地Ｐ１と目的地Ｐｎの近傍を除いて、出発地及び目的地のレイヤより高いレイヤの道路を通るので、道路分岐が少なく、パスを絞れるため、より短いルート探索時間で目的地へのルートを探索することが可能である。なお、上記図３（ｂ）では、レイヤ２のＰ５からレイヤ４のＰ２まで戻って、再ルート探索を行ったが、レイヤ３のＰ３まで戻って再ルート探索することも可能である。
【００３５】
このように、本実施形態のナビゲーション装置１によれば、ルート探索時間Ｔが、ユーザが設定した所定時間Ｔｓを経過した時点で、探索時間予測部１１ｂで予測した継続探索予測時間Ｔａと、再探索時間予測部１１ｄで予測した再探索予測時間Ｔｂとを比較して、継続探索予測時間Ｔａの方が短いときは、ルート探索部１１ａによる候補ルートの探索を継続し、再探索予測時間Ｔｂの方が短いときは、再ルート探索部１１ｃによる候補ルートの再探索処理を実行するので、より短い探索予測時間でルート探索を行うことができる。これにより、ルート探索時間を短縮して、ユーザの探索待ち時間を短くすることができ、利便性が高まる。
【００３６】
また、ナビゲーション情報の探索データは、下位の道路から上位の道路までの詳細度に応じて階層化された道路の複数のレイヤに含まれているので、ルート探索部１１ａ及び再ルート探索部１１ｃは、これら複数のレイヤの探索データを使用して候補ルートを探索又は再探索することにより、ルートの探索予測時間をより詳細に求めることができ、探索予測時間の精度が良くなる。
【００３７】
また、再ルート探索部１１ｃは、出発地Ｐ１及び目的地Ｐｎ付近以外においては、現在のレイヤより下位レイヤの探索を止め、現在のレイヤより上位レイヤに戻って再探索するので、特に遠方の目的地へのルートを探索する場合に、高速道路等の分岐の少ない道路を含む上位レイヤの使用が増加し、ルート探索時間をより短くすることができる。
【００３８】
また、探索時間予測部１１ｂによる継続探索時間の予測は、予測現時点と到着地点までの距離に、ルート探索部１１ａで探索されるルートのデータレイヤの差（係数で表す）を加味して、探索予測時間の目安を算出することにより得ることもできる。
【００３９】
なお、本発明は上記実施形態の構成に限定されるものではなく、発明の趣旨を変更しない範囲で適宜に種々の変形が可能である。例えば、本実施形態では、所定時間を１つだけ設定したが、所定時間を細かく複数設定することにより、再ルート探索を複数回行えるようにして、探索時間を速めることも可能である。また、長距離ドライブにおける案内を対象に、レイヤの高いルートを用いたルート案内に特化することにより、容量の大きい下位のレイヤを省いてデータ容量を低減することにより、探索処理を速くできると共に、メモリ容量を削減できるので、低コスト化することが可能となる。
【図面の簡単な説明】
【００４０】
【図１】本発明の第１の実施形態に係るナビゲーション装置のブロック構成図。
【図２】同上装置の動作手順を説明するためのフローチャート。
【図３】（ａ）は同上装置の動作手順に基くルート探索の流れを説明する図、（ｂ）は（ａ）で再ルート探索した場合のルート探索の流れを説明する図。
【符号の説明】
【００４１】
１  ナビゲーション装置
２  入力操作部（入力手段、所定時間設定手段）
４  情報記憶部
１０  制御部（制御手段）
１１  ＣＰＵ（制御手段）
１１ａ  ルート探索部（ルート探索手段）
１１ｂ  探索時間予測部（探索時間予測手段）
１１ｃ  再ルート探索部（再ルート探索手段））
１１ｄ  再探索時間予測部（再探索時間予測手段）
２３  所定時間設定部（所定時間設定手段）
【図１】
2008292416.tif 000003
【図２】
2008292416.tif 000004
【図３】
2008292416.tif 000005