ナビゲーション装置
【課題】自車が走行する際の通過予定時刻に交通障害が発生する地点を含むエリアを周囲のエリアより下位レベルの地図データに基づいて経路の探索を行うことによって、交通障害を回避した適切な経路を設定することを可能としたナビゲーション装置を提供する。
【解決手段】自車が走行する際の通過予定時刻において交通障害の一つである渋滞が発生する渋滞区間をタイムスライス計算を用いて検出し（Ｓ４）、その渋滞区間を含むエリアを、第２経路探索処理で周囲のエリアより道路網の情報量の多い下位レベルの地図データに基づいて探索する（Ｓ１１）ように構成する。
【解決手段】自車が走行する際の通過予定時刻において交通障害の一つである渋滞が発生する渋滞区間をタイムスライス計算を用いて検出し（Ｓ４）、その渋滞区間を含むエリアを、第２経路探索処理で周囲のエリアより道路網の情報量の多い下位レベルの地図データに基づいて探索する（Ｓ１１）ように構成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数レベルに階層化して記憶された地図データに基づいて目的地までの誘導経路の探索を行うナビゲーション装置に関し、特に、自車が走行する際の通過予定時刻に交通障害が発生する地点を含むエリアを周囲のエリアより下位レベルの地図データに基づいて経路の探索を行うことによって、交通障害を回避した適切な経路を設定することを可能としたナビゲーション装置に関するものである。
【背景技術】
【０００２】
近年、車両の走行案内を行い、運転者が所望の目的地に容易に到着できるようにしたナビゲーション装置が車両に搭載されていることが多い。ここで、ナビゲーション装置とは、ＧＰＳ受信機などにより自車の現在位置を検出し、その現在位置に対応する地図データをＤＶＤ−ＲＯＭやＨＤＤなどの記録媒体またはネットワークを通じて取得して液晶モニタに表示することが可能な装置である。更に、かかるナビゲーション装置には、所望する目的地を入力すると、自車位置から目的地までの最適経路を探索する経路探索機能を備えており、ディスプレイ画面に誘導経路を表示するとともに、交差点に接近した場合等には音声による案内をすることによって、運転者を所望の目的地まで確実に案内するようになっている。
【０００３】
また、従来のナビゲーション装置では、上記経路の探索を行う際に、例えば、高速道路、有料道路、国道、主要地方道、県道、細街路等の道路種別や、右左折禁止、一方通行等の交通規制の有無や、リンクの長さ、即ちリンク長の大小、道路の幅員の大小、車線数の多寡等によって、それぞれ、リンク又はリンク間（ノード）に各種のコストが設定される。そして、自車位置から目的地までの最適経路を探索する際においては、地図データに記憶されたリンクに沿って出発地側及び目的地側から経路の探索が行われ、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積されたコストと目的地側から累積されたコストとを加算した値、即ちコスト加算値が算出されるようになっている。その結果、算出されたコスト加算値が最小になる経路が誘導経路として設定される。
【０００４】
また、上記経路の探索に使用する地図データは、道路網の情報量の差異に基づいて複数レベルに階層化された階層構造をしている。図１０は従来のナビゲーション装置のもつ階層構造の地図データを示した模式図である。
図１０に示す地図データは、例えばレベル１、レベル２、レベル３の３層に階層化された階層構造をしている。そして、レベル３は高速自動車国道、自動車専用道路、都市高速道路、有料道路を含む地図データ、レベル２はそれに加えて国道や県道の一般道路を含む地図データ、レベル１は更に加えて細街路等のその他一般道を含む詳細地図データであり、レベルが上がるにつれて道路網の情報量の少ないより粗い地図データとなっている。
そして、経路探索を実施するにあたっては、経路の探索に係る演算量を抑える為に、出発地と目的地付近の地域では、下位レベルの階層の地図データを使用して詳細に計算するのに対して、経路の中間地域では、上位レベルの階層の地図データを使用して概略的に計算し、両方の結果を統合して案内経路として出力する方法が採用されている。
更に、特開２００２−２４３４７６号公報には、経路の中間地域においても下位レベルの階層の詳細な地図データを用いた探索を行うことにより、渋滞などの交通障害がある場合に下位レベルの階層の地図データに基づく迂回経路を含んだ案内経路を使用者に対して提示することのできる経路探索案内装置について記載されている。
【特許文献１】特開２００２−２４３４７６号公報（第９頁、図２１〜図２２）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、前記した特許文献１に記載されたナビゲーション装置では、交通情報センタからの交通情報に基づいて中間地点において局地的な渋滞等の交通障害が発見された場合に、下位レベルの階層の地図データにある道路を選択した迂回経路を探索することとしているが、出発地から目的地までの経路が長い場合には、交通障害が発生していることが検出された地点まで自車が走行する間に、発生していた交通障害が解消されていることがあった。更に、経路探索時には交通障害が発生していなかった地点で、自車が走行する間に新たに交通障害が発生することがあった。従って、利用者にとって最適な経路を設定することができない場合も多かった。
一方で、交通障害が解消されたり新たに発生したことを検出する度に、経路探索を再度やり直すようにすることも可能であるが、そのような探索方法では経路探索に係るナビゲーション装置の処理負担が非常に大きくなっていた。また、誘導経路が時間の経過とともに複数回変更されると、利用者を困惑させてしまう虞もあった。
【０００６】
本発明は前記従来における問題点を解消するためになされたものであり、経路の探索を行う際に交通障害を回避した適切な経路を予め設定することを可能としたナビゲーション装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
前記目的を達成するため本願の請求項１に係るナビゲーション装置（１）は、地図データ（２３〜２５）を道路網の情報量に基づいて複数レベルに階層化して記憶する地図データ記憶手段（２２）と、目的地を設定する目的地設定手段（１３）と、前記目的地設定手段によって設定された目的地までの間の経路を前記地図データに基づいて探索する経路探索手段（１３）と、を有するナビゲーション装置において、自車が走行する際の通過予定時刻において交通障害が発生する交通障害地点（６６）を検出する交通障害検出手段（１３）を備え、前記経路探索手段は、前記交通障害検出手段によって検出された交通障害地点を含むエリアを周囲のエリアより道路網の情報量の多い下位レベルの地図データに基づいて探索することを特徴とする。
ここで、「交通障害」とは、渋滞、速度規制、通行止め等の車両の走行にとって障害となる事象をいう。
【０００８】
また、請求項２に係るナビゲーション装置（１）は、請求項１に記載のナビゲーション装置であって、前記交通障害が所定距離未満の渋滞であるか否かを判定する渋滞判定手段（１３）を有し、前記経路探索手段（１３）は前記渋滞判定手段によって所定距離未満の渋滞であると判定された場合に、前記交通障害検出手段（１３）によって検出された交通障害地点（６６）を含むエリアを周囲のエリアより下位レベルの地図データに基づいて探索することを特徴とする。
【０００９】
また、請求項３に係るナビゲーション装置（１）は、地図データ（２３〜２５）を道路網の情報量に基づいて複数レベルに階層化して記憶する地図データ記憶手段（２２）と、目的地を設定する目的地設定手段（１３）と、前記目的地設定手段によって設定された目的地までの間の経路を前記地図データに基づいて探索する第１経路探索手段（１３）と、を有するナビゲーション装置において、自車が走行する際の通過予定時刻において交通障害が発生する交通障害地点を検出する交通障害検出手段（１３）と、前記交通障害検出手段によって検出された交通障害地点（６６）を含むエリアを前記第１経路探索手段の探索時より道路網の情報量の多い下位レベルの地図データに基づいて再度探索する第２経路探索手段（１３）と、を有することを特徴とする。
【００１０】
また、請求項４に係るナビゲーション装置（１）は、請求項３に記載のナビゲーション装置であって、前記交通障害検出手段（１３）は、前記第１経路探索手段（１３）によって探索された経路を自車が走行する際の通過予定時刻において交通障害が発生する地点を前記交通障害地点（６６）として検出することを特徴とする。
【００１１】
また、請求項５に係るナビゲーション装置（１）は、請求項３又は請求項４に記載のナビゲーション装置であって、前記第２経路探索手段（１３）は、前記交通障害地点（６６）より前記第１経路探索手段（１３）によって探索された経路に沿って所定分岐数自車位置側に位置する第１分岐点（６７、６９）から所定分岐数目的地側に位置する第２分岐点（６８、７０）までの経路を含むエリアを前記第１経路探索手段の探索時より下位レベルの地図データに基づいて再度探索することを特徴とする。
ここで、「分岐点」とは３本以上のリンクが接続されているノードが該当し、インターチェンジや交差点等が該当する。
【００１２】
また、請求項６に係るナビゲーション装置（１）は、請求項３乃至請求項５のいずれかに記載のナビゲーション装置であって、前記交通障害地点（６６）を含む道路の道路種類を検出する道路種類検出手段（１３）を有し、前記第２経路探索手段（１３）は、前記道路種類検出手段によって検出された道路種類に基づいて前記第１分岐点（６７、６９）及び前記第２分岐点（６８、７０）の前記交通障害地点までの分岐点の数を変更することを特徴とする。
【００１３】
更に、請求項７に係るナビゲーション装置（１）は、請求項３乃至請求項６のいずれかに記載のナビゲーション装置であって、前記交通障害が所定距離未満の渋滞であるか否かを判定する渋滞判定手段（１３）を有し、前記第２経路探索手段（１３）は前記渋滞判定手段（１３）によって所定距離未満の渋滞であると判定された場合に、前記交通障害検出手段（１３）によって検出された交通障害地点を含むエリアを前記第１経路探索手段（１３）の探索時より道路網の情報量の多い下位レベルの地図データに基づいて再度探索することを特徴とする。
【発明の効果】
【００１４】
前記構成を有する請求項１に係るナビゲーション装置では、自車が走行する際の通過予定時刻において交通障害が発生する交通障害地点を含むエリアを、周囲のエリアより道路網の情報量の多い下位レベルの地図データに基づいて探索するので、交通障害を回避した適切な経路を予め設定することが可能となる。
また、自車の通過予定時刻に発生する交通障害を考慮した経路の探索を行うことができるので、利用者にとって最適な経路を予め設定することが可能となる。従って、利用者の利便性が向上し、快適な走行環境を提供することが可能となる。
【００１５】
また、請求項２に係るナビゲーション装置では、交通障害が所定距離未満の渋滞であると判定された場合に、交通障害地点を含むエリアを周囲のエリアより下位レベルの地図データに基づいて探索するので、下位レベルの地図データで探索する範囲が非常に広くなることによって経路の探索に係る演算量が多くなる状況が発生することを予め防止できる。従って、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
【００１６】
また、請求項３に係るナビゲーション装置では、一旦探索された経路を自車が走行する際の通過予定時刻において交通障害が発生する交通障害地点を含むエリアを、最初の探索時より道路網の情報量の多い下位レベルの地図データに基づいて探索するので、交通障害を回避した適切な経路を予め設定することが可能となる。
また、自車の通過予定時刻に発生する交通障害を考慮した経路の探索を行うことができるので、利用者にとって最適な経路を予め設定することが可能となる。従って、利用者の利便性が向上し、快適な走行環境を提供することが可能となる。
【００１７】
また、請求項４に係るナビゲーション装置では、一旦探索された経路を自車が走行する際の通過予定時刻において交通障害が発生する地点を交通障害地点として検出するので、経路上の自車の通過予定時刻をより正確に算出することが可能となる。従って、自車の通過予定時刻に発生する交通障害を考慮した経路の探索を行うことができる。
【００１８】
また、請求項５に係るナビゲーション装置では、交通障害地点より経路に沿って所定分岐数自車位置側に位置する第１分岐点から所定分岐数目的地側に位置する第２分岐点までの経路を含むエリアを最初の探索時より下位レベルの地図データに基づいて再度探索するので、交通障害の発生した地点を適切に含むエリアのみを下位レベルの地図データに変更して探索することが可能となる。従って、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
【００１９】
また、請求項６に係るナビゲーション装置では、道路種類に基づいて第１分岐点及び第２分岐点の交通障害地点までの分岐点の数を変更するので、交通障害の発生した地点を適切に含むエリアのみを道路の種類に応じた範囲で特定可能となり、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
【００２０】
更に、請求項７に係るナビゲーション装置では、交通障害が所定距離未満の渋滞であると判定された場合に、交通障害地点を含むエリアを最初の探索時より下位レベルの地図データに基づいて探索するので、下位レベルの地図データで探索する範囲が非常に広くなることによって経路の探索に係る演算量が多くなる状況が発生することを予め防止できる。従って、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
【発明を実施するための最良の形態】
【００２１】
以下、本発明に係るナビゲーション装置について具体化した一実施形態に基づき図面を参照しつつ詳細に説明する。先ず、本実施形態に係るナビゲーション装置１の概略構成について図１を用いて説明する。図１は本実施形態に係るナビゲーション装置１を示したブロック図である。
【００２２】
図１に示すように本実施形態に係るナビゲーション装置１は、自車の現在位置を検出する現在地検出処理部１１と、各種のデータが記録されたデータ記録部（地図データ記憶手段）１２と、入力された情報に基づいて、各種の演算処理を行うナビゲーション制御部（目的地設定手段、経路探索手段、交通障害検出手段、第１経路探索手段、第２経路探索手段、道路種類検出手段、渋滞判定手段）１３と、操作者からの操作を受け付ける操作部１４と、操作者に対して地図等の情報を表示する液晶ディスプレイ１５と、経路案内に関する音声ガイダンスを出力するスピーカ１６と、交通情報センタ等の情報センタとの間で通信を行う通信装置１７と、から構成されている。また、ナビゲーション制御部１３には自車の走行速度を検出する車速センサ２１が接続される。
【００２３】
以下に、ナビゲーション装置１を構成する各構成要素について説明すると、現在地検出処理部１１は、ＧＰＳ３１、地磁気センサ３２、距離センサ３３、ステアリングセンサ３４、方位検出部としてのジャイロセンサ３５、高度計（図示せず）等からなり、現在の自車の位置、方位、目標物（例えば、交差点）までの距離等を検出することが可能となっている。
【００２４】
具体的には、ＧＰＳ３１は、人工衛星によって発生させられた電波を受信することにより、地球上における自車の現在地及び現在時刻を検出し、地磁気センサ３２は、地磁気を測定することによって自車方位を検出し、距離センサ３３は、道路上の所定の位置間の距離等を検出する。ここで、距離センサ３３としては、例えば、自車の車輪（図示せず）の回転速度を測定し、測定した回転速度に基づいて距離を検出するセンサ、加速度を測定し、測定した加速度を２回積分して距離を検出するセンサ等を使用することができる。
【００２５】
また、ステアリングセンサ３４は自車の舵（だ）角を検出する。ここで、ステアリングセンサ３４としては、例えば、ステアリングホイール（図示せず）の回転部に取り付けられた光学的な回転センサ、回転抵抗センサ、車輪に取り付けられた角度センサ等が使用される。
【００２６】
そして、ジャイロセンサ３５は自車の旋回角を検出する。ここで、ジャイロセンサ３５としては、例えば、ガスレートジャイロ、振動ジャイロ等が使用される。また、ジャイロセンサ３５によって検出された旋回角を積分することにより、自車方位を検出することができる。
【００２７】
また、データ記録部１２は、外部記憶装置及び記録媒体としてのハードディスク（図示せず）と、ハードディスクに記録された地図情報ＤＢ２２、渋滞度設定テーブル２６、所定のプログラム等を読み出すとともにハードディスクに所定のデータを書き込む為のドライバである記録ヘッド（図示せず）とを備えている。尚、本実施形態においては、データ記録部１２の外部記憶装置及び記憶媒体としてハードディスクが使用されるが、ハードディスクのほかに、フレキシブルディスク等の磁気ディスクを外部記憶装置として使用することができる。また、メモリーカード、磁気テープ、磁気ドラム、ＣＤ、ＭＤ、ＤＶＤ、光ディスク、ＭＯ、ＩＣカード、光カード等を外部記憶装置として使用することもできる。尚、地図情報ＤＢ２２及び渋滞度設定テーブル２６の詳細については後述する。
【００２８】
更に、ナビゲーション制御部１３は、ナビゲーション装置１の全体の制御を行う演算装置及び制御装置としてのＣＰＵ４１、並びにＣＰＵ４１が各種の演算処理を行うに当たってワーキングメモリとして使用されるとともに、経路が探索されたときの経路データ等が記憶されるＲＡＭ４２、制御用のプログラムのほか、自車の現在位置から入力された目的地までの経路を経路上に発生する交通障害を考慮して探索し、誘導経路に設定する経路設定処理プログラム（図５参照）が記録されたＲＯＭ４３、ＲＯＭ４３から読み出したプログラムを記録するフラッシュメモリ４４等の内部記憶装置を備えている。尚、前記ＲＡＭ４２、ＲＯＭ４３、フラッシュメモリ４４等としては半導体メモリ、磁気コア等が使用される。そして、演算装置及び制御装置としては、ＣＰＵ４１に代えてＭＰＵ等を使用することも可能である。
【００２９】
また、本実施形態においては、前記ＲＯＭ４３に各種のプログラムが記録され、前記データ記録部１２に各種のデータが記録されるようになっているが、プログラム、データ等を同じ外部記憶装置、メモリーカード等からプログラム、データ等を読み出して前記フラッシュメモリ４４に書き込むこともできる。更に、メモリーカード等を交換することによって前記プログラム、データ等を更新することができる。
【００３０】
更に、前記ナビゲーション制御部１３には、操作部１４、液晶ディスプレイ１５、スピーカ１６、通信装置１７の各周辺装置（アクチュエータ）が電気的に接続されている。
【００３１】
操作部１４は、走行開始時の現在地を修正し、案内開始地点としての出発地及び案内終了地点としての目的地を入力する際等に操作され、各種のキー、ボタン等の複数の操作スイッチ（図示せず）から構成される。そして、ナビゲーション制御部１３は、各スイッチの押下等により出力されるスイッチ信号に基づき、対応する各種の動作を実行すべく制御を行う。尚、操作部１４としては、キーボード、マウス、バーコードリーダ、遠隔操作用のリモートコントロール装置、ジョイスティック、ライトペン、スタイラスペン等を使用することもできる。更に、液晶ディスプレイ１５の前面に設けたタッチパネルによって構成することもできる。
【００３２】
また、液晶ディスプレイ１５には、操作案内、操作メニュー、キーの案内、現在地から目的地までの誘導経路、誘導経路に沿った案内情報、交通情報、ニュース、天気予報、時刻、メール、テレビ番組等が表示される。尚、液晶ディスプレイ１５の代わりに、ＣＲＴディスプレイ、プラズマディスプレイ等を使用したり、車両のフロントガラスにホログラムを投影するホログラム装置等を使用することも可能である。
【００３３】
また、スピーカ１６は、ナビゲーション制御部１３からの指示に基づいて誘導経路に沿った走行を案内する音声ガイダンスを出力する。ここで、案内される音声ガイダンスとしては、例えば、「２００ｍ先の交差点を右折してください。」や「この先の国道○○号線が渋滞しています。」等がある。なお、スピーカ１６より出力される音声としては、合成された音声のほかに、各種効果音、予めテープやメモリ等に録音された各種の案内情報を出力することもできる。
【００３４】
そして、通信装置１７は、交通情報センタ、例えば、ＶＩＣＳ（登録商標：Ｖｅｈｉｃｌｅ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）センタ等から送信された渋滞情報、規制情報、駐車場情報、交通事故情報等の各情報から成る交通情報を、道路に沿って配設された電波ビーコン装置、光ビーコン装置等を介して電波ビーコン、光ビーコン等として受信するビーコンレシーバである。また、通信装置１７としては、ＬＡＮ、ＷＡＮ、イントラネット、携帯電話回線網、電話回線網、公衆通信回線網、専用通信回線網、インターネット等の通信回線網等の通信系において通信を可能とするネットワーク機器であっても良い。更に、通信装置１７は前記情報センタからの情報の他に、ニュース、天気予報等の情報から成るＦＭ多重情報を、ＦＭ放送局を介してＦＭ多重放送として受信するＦＭ受信機を備える。尚、前記ビーコンレシーバ及びＦＭ受信機は、ユニット化されてＶＩＣＳレシーバとして配設されるようになっているが、別々に配設することもできる。
【００３５】
次に、データ記録部１２に格納された地図情報ＤＢ２２について説明する。ここで、地図情報ＤＢ２２には、経路案内及び地図表示に必要な地図データが記録されており、地図データは、例えば地図を表示するための地図表示データ、各交差点に関する交差点データ、道路（リンク）に関するリンクデータ、ノード点に関するノードデータ、経路を探索するための探索データ、施設に関する施設データ、地点を検索するための検索データ等から構成されている。
【００３６】
また、本実施形態において地図データは、図２に示されるように道路網の情報量に応じて３層に階層化されている。図２は地図情報ＤＢに記憶される３層に階層化された地図データを示した模式図である。この場合、例えば、レベル１の階層は１０ｋｍ四方のメッシュによって複数に区分された地図データであり、レベル２の階層は２０ｋｍ四方のメッシュによって複数に区分された地図データであり、レベル３の階層は４０ｋｍ四方のメッシュによって複数に区分された地図データである。
そして、下位レベルの階層の地図データは上位レベルの階層の地図データより道路網の情報量がより多く含まれており、例えばレベル３の地図データは高速自動車国道、自動車専用道路、都市高速道路、有料道路に関する情報が格納されている。また、レベル２の地図データはレベル３に含まれる道路網に加えて国道や県道等の主要な一般道路に関する情報が格納されている。また、レベル１の地図データはレベル２に含まれる道路網に加えて細街路等のその他全ての一般道に関する詳細な道路網に関する情報が格納されている。
【００３７】
更に、下位レベルの階層における地図データのメッシュでは詳細なデータを有する代わりにカバーする範囲が狭く、上位レベルの階層における地図データのメッシュでは粗いデータしか有していない代わりにカバーする範囲が広くなっている。例えば、最下位レベル（レベル１）の階層におけるメッシュでは細街路を含む全ての道路の道路データを有するが市町村範囲しかカバーしておらず、最上位レベル（レベル３）の階層におけるメッシュでは高速道路や有料道路等の道路の道路データしか有していないが日本全国をカバーする。
【００３８】
尚、各レベルの階層、即ち最上層であるレベル３の階層、中間層であるレベル２の階層及び最下層であるレベル１の階層におけるメッシュの大きさ、即ち、メッシュのカバーする範囲の広さは、適宜決定することができる。また、地図データを構成するレベルの数、即ち、階層の数も、必ずしも３層である必要はなく、例えば５層や１０層であっても良い。
【００３９】
そして、各レベル階層の地図データ２３〜２５は、図３に示すように前記した地図表示データ、交差点データ、リンクデータ、ノードデータ、探索データ、施設データ、検索データ等によってそれぞれ構成されている。図３は本実施形態に係るナビゲーション装置１の地図情報ＤＢ２２の記憶領域を示した図である。
【００４０】
ここで、特に地図データを構成する地図表示データとしては、各レベル階層の地図データ２３〜２５に応じた地図表示を行う為の地図描画情報が記憶される。
【００４１】
また、リンクデータとしては、それぞれのレベル階層の地図データ２３〜２５において道路を構成する各リンクに関してリンクの属する道路の幅員、勾（こう）配、カント、バンク、路面の状態、道路の車線数、車線数の減少する箇所、幅員の狭くなる箇所、踏切り等を表すデータが、コーナに関して、曲率半径、交差点、Ｔ字路、コーナの入口及び出口等を表すデータが、道路属性に関して、降坂路、登坂路等を表すデータが、道路種別に関して、国道、県道、細街路等の一般道のほか、高速自動車国道、自動車専用道路、都市高速道路、一般有料道路、有料橋等の有料道路を表すデータがそれぞれ記録される。更に、有料道路に関して、有料道路の入口及び出口の取付道（ランプウェイ）、料金所（インターチェンジ）等に関するデータが記録される。
【００４２】
また、ノードデータとしては、それぞれのレベル階層の地図データ２３〜２５において道路の分岐点（交差点、Ｔ字路等も含む）、各道路に曲率半径等に応じて所定の距離ごとに設定されたノード点の座標（位置）、ノードが交差点に対応するノードであるか等を表すノード属性、ノードに接続するリンクのリンク番号のリストである接続リンク番号リスト、ノードにリンクを介して隣接するノードのノード番号のリストである隣接ノード番号リスト、各ノード点の高さ（高度）等に関するデータ等が記録される。
【００４３】
また、探索データとしては、それぞれのレベル階層の地図データ２３〜２５において設定された目的地までの経路を探索及び表示する際に使用されるデータについて記録されており、ノードを通過する際のコスト（以下、ノードコストという）や道路を構成するリンクのコスト（以下、リンクコストという）からなる探索コストを算出する為に使用するコストデータ、リンクを通過するのに必要な旅行時間、経路探索により選択された経路を液晶ディスプレイ１５の地図上に表示するための経路表示データ等から構成されている。
ここで、ノードコストは交差点に対応するノードに対して基本的に設定されており、本実施形態に係るナビゲーション装置１では、信号の有無や交差点を通過する際の自車の走行経路（即ち直進、右折及び左折の種類）によってその値が決定される。
また、リンクコストは、リンクを構成する道路属性や道路種別、道路幅、車線数、リンク長さに加え、後述する渋滞度設定テーブル２６（図４参照）によって検出される渋滞度等の交通情報に関するデータを用いて算出される。
【００４４】
また、施設データとしては、各地域のホテル、病院、ガソリンスタンド、駐車場、観光施設、インターチェンジ、レストラン、サービスエリア等の建物に関するデータが建物を特定する施設ＩＤとともに記録される。なお、前記地図情報ＤＢ２２には、所定の情報をナビゲーション装置１のスピーカ１６によって出力するための音声出力データも記録される。
【００４５】
そして、ナビゲーション制御部１３は、現在地（出発地）から目的地までの距離が短距離（例えば、３ｋｍ程度）の経路探索の場合には、現在地周辺の最下層の地図データであるレベル１の地図データのメッシュのみを使用して経路を探索する。
また、現在地から目的地までの距離が中距離（例えば、５０ｋｍ程度）の経路探索の場合には、現在地及び目的地周辺については最下層の地図データであるレベル１の地図データのメッシュを使用し、前記レベル１の地図データのメッシュに隣接するエリアは中間層の地図データであるレベル２の地図データのメッシュを使用して経路を探索する。
更に、現在地から目的地までの距離が長距離（例えば、３００ｋｍ程度）の経路探索の場合には、現在地及び目的地周辺の最下層の地図データであるレベル１の地図データのメッシュを使用し、前記レベル１の地図データのメッシュに隣接するエリアは中間層の地図データであるレベル２の地図データのメッシュを使用し、前記レベル２の地図データのメッシュに隣接するエリアは最上層の地図データであるレベル３の地図データのメッシュを使用して経路を探索する。それによって、経路を探索の為の演算量を抑えることができ、経路探索に必要な時間を短縮することができる。
【００４６】
そして、ナビゲーション制御部１３が経路を探索する際には、地図データにおける探索データ中の道路データを調査して、探索に使用されるメッシュに含まれる道路（リンク及びノード）についての探索コスト（ノードコスト及びリンクコスト）を計算して、経路を探索する。具体的には、出発地側及び目的地側から経路の探索が行われ、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積された探索コストと目的地側から累積された探索コストとを加算した値、即ち、コスト加算値が算出される。その結果、コストが小さい順に経路を複数本（例えば５本）選択し、最もコスト加算値が小さくなった経路、又は利用者によって選択された経路を誘導経路として設定する。
【００４７】
また、これら地図情報ＤＢ２２の内容は、ＤＶＤや外部に接続したメモリーカード等の記録媒体から情報を転送すること、又は特定の情報センタ等から通信装置１７を介して情報をダウンロードすること等によって更新される。
【００４８】
次に、データ記録部１２に格納された渋滞度設定テーブル２６について図４を用いて説明する。図４は本実施形態に係る渋滞度設定テーブル２６の一例について示した図である。ここで、渋滞度設定テーブル２６は自車の走行に影響を与える交通障害の内、特に渋滞の発生する区間と時刻とを特定したテーブルである。
【００４９】
図４に示すように、本実施形態に係る渋滞度設定テーブル２６は、リンクを特定するリンク番号と、曜日及び時間帯と、リンク番号によって特定されるリンクの各曜日及び各時間帯での渋滞の程度を特定する渋滞度とから構成されている。
ここで、渋滞度は「１」、「２」、「３」の３種類の数値のいずれかによって設定され、「１」が設定されたリンクではその時間帯に渋滞が発生しないことを意味する。一方、「２」が設定されたリンクではその時間帯に渋滞が発生し、リンクを走行するのに通常の２倍程度の時間が必要となることを意味する。また、「３」が設定されたリンクではその時間帯に渋滞が発生し、リンクを走行するのに通常の３倍程度の時間が必要となることを意味する。
例えば、図４に示す渋滞度設定テーブル２６では、リンク番号ＸＺ１のリンクについて、月曜日の８：１５〜８：３０の間は渋滞度が「２」に設定され、８：３０〜８：４５の間は渋滞度が「３」に設定され、８：４５〜９：００の間は渋滞度が「２」に設定されていることを示している。
【００５０】
そして、ナビゲーション制御部１３は、渋滞度設定テーブル２６によって前記地図情報ＤＢ２２に記憶された各レベル階層の地図データに含まれるリンク毎に、各曜日及び各時間帯における渋滞度を検出することが可能となる。その結果、後述するように自車が通過する予定時刻で渋滞の発生するリンク（即ち、渋滞度が「１」以外のリンク）が検出された場合には、そのリンクを通過するのに必要な旅行時間やリンクコストについて渋滞度を乗じた値に調整する。そして、調整された旅行時間やリンクコストに基づいて後述するようにタイムスライスによる経路探索が行われる（図５のＳ４、Ｓ１１）。
尚、渋滞度設定テーブル２６はナビゲーション装置１の出荷時に予めデータ記録部１２に対して記憶されているが、通信装置１７を介して交通情報センタから受信した情報に基づいて渋滞度設定テーブル２６の内容の更新を行うようにしても良い。また、自車の走行履歴に基づいて渋滞度設定テーブル２６の内容を更新するようにしても良い。
【００５１】
続いて、前記構成を有するナビゲーション装置１においてＣＰＵ４１が実行する経路設定処理プログラムについて図５に基づき説明する。図５は本実施形態に係る経路案内処理プログラムのフローチャートである。ここで、経路案内処理プログラムは車両のイグニションがＯＮされた際に実行され、自車の現在位置から入力された目的地までの経路を経路上に発生する交通障害を考慮して探索し、誘導経路に設定するプログラムである。尚、以下の図５にフローチャートで示されるプログラムは、ナビゲーション装置１が備えているＲＡＭ４２やＲＯＭ４３に記憶されており、ＣＰＵ４１により実行される。
【００５２】
先ず、経路設定処理プログラムではステップ（以下、Ｓと略記する）１において、ＣＰＵ４１は、利用者の操作部１４の操作に基づいて目的地を設定する。次にＳ２では、現在地検出処理部１１の検出結果に基づいて自車の現在位置を検出する。尚、上記Ｓ１の処理が目的地設定手段の処理に相当する。
【００５３】
その後に、渋滞、通行止め、速度規制などの交通障害を考慮せずに、自車の現在位置である出発地から前記Ｓ１で設定された目的地までの経路の探索処理（以下、第１経路探索処理という）を行う（Ｓ３）。
【００５４】
以下に、前記Ｓ３の第１経路探索処理における経路の探索手順について図６を用いて説明する。図６は前記Ｓ３で本実施形態に係るナビゲーション装置１が実行する第１経路探索処理によって探索された経路を地図上に示した模式図である。尚、図６では特に出発地から目的地までの距離が長距離（例えば、３００ｋｍ程度）であって、中間地点を最上層のレベル３の地図データを用いて探索する場合を例に挙げて説明する。
【００５５】
先ず、第１経路探索処理において、ナビゲーション制御部１３が経路を探索する際には、地図データにおける探索データ中の道路データを調査して、探索に使用されるメッシュに含まれる道路（リンク及びノード）についての探索コスト（ノードコスト及びリンクコスト）を計算する。その後、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積された探索コストと目的地側から累積された探索コストとを加算した値、即ち、コスト加算値が算出される。
そして、上記の探索コスト及びコスト加算値の算出の際には、図６に示すように、出発地及び目的地周辺では最下層の地図データであるレベル１の地図データのメッシュ５１、６５がそれぞれ使用される。また、前記レベル１の地図データのメッシュ５１、６５に隣接するエリアは中間層の地図データであるレベル２の地図データのメッシュ５２、５３、６２〜６４が使用される。そして、前記レベル２の地図データのメッシュ５２、５３、６２〜６４に隣接するエリア、並びにその中間地点のエリアは最上位の地図データであるレベル３の地図データのメッシュ５４〜６１が使用される。尚、探索する経路が異なるレベルの地図データのメッシュに移行する際には、異なるレベルの地図データで共通して含まれるノードを介して移行する。
そして、探索の結果、コスト加算値が所定の条件を満たした経路（例えば、コスト加算値が小さいほうから順に２つの経路）として、経路Ａと経路Ｂがそれぞれ図６に示すように経路の候補として選択される。尚、上記Ｓ３の処理が第１経路探索手段の処理に相当する。
【００５６】
続いて、Ｓ４では前記Ｓ３の第１経路探索処理で探索された経路上の交通障害（本実施形態では渋滞のみ）を考慮してタイムスライス計算し、交通障害地点である渋滞の発生する区間と、その渋滞度を検出する。
以下に、タイムスライス計算の具体的方法について説明すると、先ずＣＰＵ４１はＧＰＳ３１により現在時刻を検出し、更に前記Ｓ３の第１経路探索処理で探索された経路（図６では経路Ａと経路Ｂ）を構成する各リンクの旅行時間に基づいて、自車が経路を構成する各リンクを走行する通過予定時刻を算出する。その後、算出された通過予定時刻と渋滞度設定テーブル２６（図４参照）とに基づいて、経路を構成する各リンクの通過予定時刻で渋滞が発生するか否か（具体的には、渋滞度が「１」以外のリンクがあるか否か）を判定する。その結果、通過予定時刻に渋滞が発生すると判定された場合には、発生すると判定されたリンクの旅行時間を渋滞度に基づいて調整し（具体的には、渋滞度を乗じた旅行時間とする）、更に、調整した旅行時間に基づいて再び経路を構成する各リンクを走行する通過予定時刻を算出する。
その後、同様に再度算出された通過予定時刻と渋滞度設定テーブル２６（図４参照）とに基づいて、経路を構成するリンクの通過予定時刻で新たに渋滞が発生するリンクがあるか否かを判定し、渋滞が発生すると判定された場合には、発生すると判定されたリンクの旅行時間を渋滞度に基づいて調整する。以上の操作を新たに渋滞が発生するリンクが検出されなくなるまで行う。そして、最終的に渋滞が発生すると予測された全てのリンクについて渋滞度設定テーブル２６を用いてそれぞれ渋滞度を検出する。尚、上記Ｓ４の処理が交通障害検出手段の処理に相当する。
【００５７】
次に、Ｓ５では前記Ｓ４の検出結果に基づいて前記第１経路探索処理で探索された経路上に渋滞するリンクがあるか否か、即ち、自車が経路を構成する各リンクを走行する通過予定時刻において渋滞度設定テーブル２６で渋滞度が「１」以外に設定されたリンクがあるか否かが判定される。
【００５８】
その結果、経路上に渋滞するリンクがあると判定された場合（Ｓ５：ＹＥＳ）には、Ｓ６へと移行する。
一方、経路上に渋滞するリンクがないと判定された場合（Ｓ５：ＮＯ）には、渋滞を考慮する必要がないので前記Ｓ３の第１経路探索処理で探索された経路（図６では経路Ａ及び経路Ｂ）の内、コスト加算が最も小さい経路をそのまま選択する（Ｓ１２）。その後、選択された経路を誘導経路に設定し（Ｓ１３）、当該経路案内処理プログラムを終了する。そして、設定された誘導経路に従って液晶ディスプレイ１５に誘導経路を表示するとともに、液晶ディスプレイ１５の表示とスピーカ１６から出力する音声により、利用者に対して経路の案内を行う。尚、第１経路探索処理で探索された経路の選択では、利用者の操作部１４の操作に基づいて選択された経路を誘導経路に設定することとしても良い。
【００５９】
次に、Ｓ６では前記第１経路探索処理で探索された経路上において渋滞すると判定されたリンクの長さ（即ち渋滞区間）が所定距離（本実施形態では３０ｋｍ）未満であるか否かが判定される。尚、Ｓ６の処理が渋滞判定手段の処理に相当する。
【００６０】
そして、渋滞区間が所定距離未満であると判定された場合（Ｓ６：ＹＥＳ）には、Ｓ７へと移行する。それに対して、渋滞区間が所定距離以上であると判定された場合（Ｓ６：ＮＯ）には、その渋滞区間を含むエリアの地図データのレベルを下げて再度探索するとすると、ＣＰＵ４１の演算量が非常に多くなってしまうので、前記Ｓ３の第１経路探索処理で探索された経路（図６では経路Ａ及び経路Ｂ）の内、前記Ｓ４で検出された渋滞度に基づいて調整したコスト加算（具体的には、渋滞度が「１」以外のリンクのリンクコストについて渋滞度を乗じたリンクコストとする）が最も小さい経路を選択する（Ｓ１２）。その後、選択された経路を誘導経路に設定し（Ｓ１３）、当該経路案内処理プログラムを終了する。尚、第１経路探索処理で探索された経路の選択では、利用者の操作部１４の操作に基づいて選択された経路を誘導経路に設定することとしても良い。
【００６１】
続いて、Ｓ７では前記第１経路探索処理で探索された経路上において渋滞すると判定されたリンクが高速道路（高速自動車国道、自動車専用道路、都市高速道路など）であるか否かを地図情報ＤＢ２２のリンクデータに基づいて判定する。尚、Ｓ７の処理が道路種類検出手段の処理に相当する。
【００６２】
その結果、渋滞区間が高速道路であると判定された場合（Ｓ７：ＹＥＳ）には、経路に沿って渋滞区間から１分岐数分自車位置（出発地）側に位置する第１分起点と、経路に沿って渋滞区間から１分岐数分目的地側に位置する第２分起点とを検出し、更に検出された第１分岐点と第２分岐点の区間を含む最下位レベル（レベル１）の階層の地図データのメッシュを地図情報ＤＢ２２から抽出する（Ｓ８）。ここで、分岐点とは３本以上のリンクが接続されているノードが該当し、インターチェンジや交差点等が該当する。
【００６３】
一方、渋滞区間が高速道路以外の一般道路であると判定された場合（Ｓ７：ＮＯ）には、経路に沿って渋滞区間から２分岐数分自車位置（出発地）側に位置する第３分起点と、経路に沿って渋滞区間から２分岐数分目的地側に位置する第４分起点とを検出し、更に検出された第３分岐点と第４分岐点の区間を含む最下位レベル（レベル１）の階層の地図データのメッシュを地図情報ＤＢ２２から抽出する（Ｓ９）。
【００６４】
ここで、前記Ｓ８及びＳ９の処理について、図６に示すように第１経路探索処理で探索された経路Ａの通過予定時刻に渋滞区間６６が発生することが検出された場合を具体例に挙げて説明する。ここで、図７は図６に示す経路上の地図の内、メッシュ５８の特に渋滞区間６６付近を拡大して示した模式図である。
ここで、特に渋滞区間６６が高速道路であった場合には、図７に示すように渋滞区間６６の１分岐数分自車位置（出発地）側に位置する第１分起点６７と、経路に沿って渋滞区間から１分岐数分目的地側に位置する第２分起点６８とがそれぞれ検出され、その区間を含む最下位レベル（レベル１）の階層の地図データのメッシュ８１〜８４が抽出される。
また、渋滞区間６６が高速道路以外の道路であった場合には、図７に示すように渋滞区間６６の２分岐数分自車位置（出発地）側に位置する第３分起点６９と、経路に沿って渋滞区間から２分岐数分目的地側に位置する第４分起点７０とがそれぞれ検出され、その区間を含む最下位レベル（レベル１）の階層の地図データのメッシュ８１〜８４が抽出される。
【００６５】
次に、Ｓ１０では前記Ｓ８又はＳ９で抽出されたメッシュに含まれる地図データ（地図表示データ、交差点データ、リンクデータ、ノードデータ、探索データ、施設データ、検索データ等）を地図情報ＤＢ２２から取得する。
【００６６】
続いて、Ｓ１１では前記Ｓ４で抽出された各リンクの渋滞度を考慮するとともに前記Ｓ１０で取得した地図データを用い、再び自車の現在位置である出発地から前記Ｓ１で設定された目的地までの経路の探索処理（以下、第２経路探索処理という）を行う。
【００６７】
以下に、前記Ｓ１１の第２経路探索処理における経路の探索手順について図８を用いて説明する。図８は前記第１経路探索処理によって図６に示す経路Ａ及び経路Ｂが探索され、且つ渋滞区間６６が検出された後に、前記Ｓ１１で本実施形態に係るナビゲーション装置１が実行する第２経路探索処理によって探索された経路を地図上に示した模式図である。
【００６８】
先ず、第２経路探索処理において、ナビゲーション制御部１３が経路を探索する際には、地図データにおける探索データ中の道路データを調査して、探索に使用されるメッシュに含まれる道路（リンク及びノード）についての探索コスト（ノードコスト及びリンクコスト）を前記Ｓ４で検出された渋滞度を考慮しつつ計算する。また、第２経路探索処理では渋滞が発生する区間として前記Ｓ４で検出されたリンクのリンクコストに、同じく検出された渋滞度を乗じることによって、交通障害を考慮したコスト計算を行う。
その後、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積された探索コストと目的地側から累積された探索コストとを加算した値、即ち、コスト加算値が算出される。
そして、上記の探索コスト及びコスト加算値の算出の際には、図８に示すように、現在地及び目的地周辺、並びに渋滞区間６６の前後の分岐点６７〜７０を含むエリアでは最下層の地図データであるレベル１の地図データのメッシュ５１、６５、８１〜８４がそれぞれ使用される。また、前記レベル１の地図データのメッシュ５１、６５に隣接するエリアは中間層の地図データであるレベル２の地図データのメッシュ５２、５３、６２〜６４が使用される。そして、前記レベル２の地図データのメッシュ５２、５３、６２〜６４に隣接するエリア、並びにその中間地点のエリアは最上位の地図データであるレベル３の地図データのメッシュ５４〜６１が使用される。尚、探索する経路が異なるレベルの地図データのメッシュに移行する際には、異なるレベルの地図データで共通して含まれるノードを介して移行する。
そして、探索の結果、コスト加算値が所定の条件を満たした経路（例えば、コスト加算値が小さいほうから順に２つの経路）として、第１経路探索処理で探索された経路Ｂと、メッシュ８１〜８４のリンクを利用して渋滞区間６６を迂回した経路Ｃが図８に示すように新たに経路の候補として選択される。尚、図８では渋滞区間６６の渋滞度を考慮したことにより、経路Ａより経路Ｂ及び経路Ｃの方がコスト加算値が小さくなった場合を示しているが、渋滞度を考慮しても経路Ａのコスト加算値が経路Ｂ又は経路Ｃより小さい場合には渋滞区間を有する経路Ａが経路の候補として選択されることとなる。尚、上記Ｓ１１の処理が経路探索手段及び第２経路探索手段の処理に相当する。
【００６９】
その後、Ｓ１２では、前記Ｓ１１の第２経路探索処理で探索された経路（図８では経路Ｂ及び経路Ｃ）の内、コスト加算値が最も小さい経路を選択する。その後、選択された経路を誘導経路に設定し（Ｓ１３）、当該経路案内処理プログラムを終了する。尚、第１経路探索処理で探索された経路の選択では、利用者の操作部１４の操作に基づいて選択された経路を誘導経路に設定することとしても良い。そして、設定された誘導経路に従って液晶ディスプレイ１５に誘導経路を表示するとともに、液晶ディスプレイ１５の表示とスピーカ１６から出力する音声により、利用者に対して経路の案内を行う。尚、第２経路探索処理で探索された経路の選択では、利用者の操作部１４の操作に基づいて選択された経路を誘導経路に設定することとしても良い。
【００７０】
以上詳細に説明した通り、本実施形態に係るナビゲーション装置１では、自車が走行する際の通過予定時刻において交通障害の一つである渋滞が発生する渋滞区間をタイムスライス計算を用いて検出し（Ｓ４）、その渋滞区間を含むエリアを、第２経路探索処理で周囲のエリアより道路網の情報量の多い下位レベルの地図データに基づいて探索する（Ｓ１１）ので、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
また、第２経路探索処理では、渋滞区間を含むエリアを交通障害を考慮せずに行った第１経路探索処理より道路網の情報量の多い下位レベルの地図データに基づいて探索する（Ｓ１１）ので、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
また、第１経路探索処理で探索された経路を自車が走行する際の通過予定時刻において交通障害が発生する地点をタイムスライス計算により交通障害地点として検出する（Ｓ４）ので、経路上の自車の通過予定時刻をより正確に算出することが可能となる。
また、渋滞区間より経路に沿って所定分岐数自車位置側に位置する第１分岐点又は第３分岐点から所定分岐数目的地側に位置する第２分岐点又は第４分岐点までの経路を含むエリアを最初の探索時より下位レベルの地図データに基づいて再度探索するので、渋滞区間の発生した地点を適切に含むエリアのみを下位レベルの地図データに変更して探索することが可能となる。従って、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
また、高速道路で渋滞が発生した場合における第１分岐点及び第２分岐点の渋滞区間までの分岐数と、高速道路以外の一般道路で渋滞が発生した場合における第３分岐点及び第４分岐点の渋滞区間までの分岐数とをそれぞれ変更することによって、交通障害の発生した地点を適切に含むエリアのみを道路の種類に応じた範囲で特定可能となる。
また、渋滞区間の長さが所定距離未満の渋滞であると判定された場合（Ｓ６：ＹＥＳ）のみに、渋滞区間を含むエリアを周囲のエリアより下位レベルの地図データに基づいて探索するので、下位レベルの地図データで探索する範囲が非常に広くなることによって経路の探索に係る演算量が多くなる状況が発生することを予め防止できる。
また、自車の通過予定時刻に発生する渋滞を考慮した経路の探索を行うことができるので、利用者にとって最適な経路を予め設定することが可能となり、一旦設定された経路が走行中に変更される虞も無い。従って、利用者の利便性が向上し、快適な走行環境を提供することが可能となる。
【００７１】
尚、本発明は前記実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の改良、変形が可能であることは勿論である。
例えば、本実施形態では地図データに含まれる各リンクの渋滞度を設定した渋滞度設定テーブル２６をナビゲーション装置１に記憶することとしているが、渋滞度設定テーブルを車両内でなく外部の施設である交通情報センタ内に記憶させ、車両が交通情報センタと通信を行うことによってリンクの渋滞度に関する情報を取得することとしても良い。
【００７２】
ここで、図９は前記他の実施形態における通信システム１０１を示した概略構成図である。図９に示すように、通信システム１０１は、ナビゲーション装置１と、交通情報センタ１０２とネットワーク１０４とから構成される。そして、交通情報センタ１０２とナビゲーション装置１は、ネットワーク１０４を介して各種の情報の送受信が可能となるように構成されている。
【００７３】
また、交通情報センタ１０２は、サーバ１１１と、サーバ１１１に接続された情報記録部としての交通情報ＤＢ１１５と、センタ側通信装置１１６とを備える。また、サーバ１１１は、サーバ１１１の全体の制御を行う演算装置及び制御装置としてのＣＰＵ１１２、並びにＣＰＵ１１２が各種の演算処理を行うに当たってワーキングメモリとして使用されるＲＡＭ１１３、ナビゲーション装置１からの通信に基づいて交通情報ＤＢ１１５に格納された渋滞度設定テーブル１１７から第１経路探索処理の経路探索に関連するエリア（図６ではメッシュ５１〜６５）に含まれる各リンクの渋滞度に係る情報を抽出し、ナビゲーション装置１に対して送信するための各種の制御プログラムが記録されたＲＯＭ１１４等の内部記憶装置を備えている。また、ＣＰＵ１１２に代えてＭＰＵ等を使用することができる。
【００７４】
そして、ＣＰＵ１１２はナビゲーション装置１に対して第１経路探索処理の経路探索に関連するエリア（図６ではメッシュ５１〜６５）に含まれる各リンクの渋滞度に係る情報を送信し、一方で、ナビゲーション装置１は交通情報センタ１０２から送信された各リンクの渋滞度に関する情報に基づいて、自車が走行する際の通過予定時刻において渋滞の発生するリンクと渋滞度とをそれぞれタイムスライス計算により検出する（Ｓ４）。
それによって、自車の通過予定時刻において渋滞の発生するリンクと、その渋滞度をそれぞれナビゲーション制御部１３が検出することが可能となる。
【００７５】
また、本実施形態では渋滞区間の前後の分岐点を含むエリアのみを、最下層のレベル１の地図データに変更して探索することとしているが、分岐点を含むエリアに隣接するエリアについても周囲より下位のレベル（例えばレベル２）の地図データに変更して探索を行うこととしても良い。
【図面の簡単な説明】
【００７６】
【図１】本実施形態に係るナビゲーション装置を示したブロック図である。
【図２】地図情報ＤＢに記憶される３層に階層化された地図データを示した模式図である。
【図３】本実施形態に係るナビゲーション装置の地図情報ＤＢの記憶領域を示した図である。
【図４】本実施形態に係る渋滞度設定テーブルの一例について示した図である。
【図５】本実施形態に係る経路案内処理プログラムのフローチャートである。
【図６】ステップ３で本実施形態に係るナビゲーション装置が実行する第１経路探索処理によって探索された経路を地図上に示した模式図である。
【図７】図６に示す経路上の地図の内、特に渋滞区間付近を拡大して示した模式図である。
【図８】第１経路探索処理によって図６に示す経路が探索され、且つ渋滞区間が検出された後に、ステップ１１で本実施形態に係るナビゲーション装置が実行する第２経路探索処理によって探索された経路を地図上に示した模式図である。
【図９】他の実施形態における通信システムを示した概略構成図である。
【図１０】従来のナビゲーション装置のもつ階層構造の地図データを示した模式図である。
【符号の説明】
【００７７】
１ ナビゲーション装置
１１ 現在地検出処理部
１２ データ記録部
１３ ナビゲーション制御部
２２ 地図情報ＤＢ
２６ 渋滞度設定テーブル
４１ ＣＰＵ
４２ ＲＡＭ
４３ ＲＯＭ
６６ 渋滞区間
６７ 第１分起点
６８ 第２分起点
６９ 第３分起点
７０ 第４分起点
【技術分野】
【０００１】
本発明は、複数レベルに階層化して記憶された地図データに基づいて目的地までの誘導経路の探索を行うナビゲーション装置に関し、特に、自車が走行する際の通過予定時刻に交通障害が発生する地点を含むエリアを周囲のエリアより下位レベルの地図データに基づいて経路の探索を行うことによって、交通障害を回避した適切な経路を設定することを可能としたナビゲーション装置に関するものである。
【背景技術】
【０００２】
近年、車両の走行案内を行い、運転者が所望の目的地に容易に到着できるようにしたナビゲーション装置が車両に搭載されていることが多い。ここで、ナビゲーション装置とは、ＧＰＳ受信機などにより自車の現在位置を検出し、その現在位置に対応する地図データをＤＶＤ−ＲＯＭやＨＤＤなどの記録媒体またはネットワークを通じて取得して液晶モニタに表示することが可能な装置である。更に、かかるナビゲーション装置には、所望する目的地を入力すると、自車位置から目的地までの最適経路を探索する経路探索機能を備えており、ディスプレイ画面に誘導経路を表示するとともに、交差点に接近した場合等には音声による案内をすることによって、運転者を所望の目的地まで確実に案内するようになっている。
【０００３】
また、従来のナビゲーション装置では、上記経路の探索を行う際に、例えば、高速道路、有料道路、国道、主要地方道、県道、細街路等の道路種別や、右左折禁止、一方通行等の交通規制の有無や、リンクの長さ、即ちリンク長の大小、道路の幅員の大小、車線数の多寡等によって、それぞれ、リンク又はリンク間（ノード）に各種のコストが設定される。そして、自車位置から目的地までの最適経路を探索する際においては、地図データに記憶されたリンクに沿って出発地側及び目的地側から経路の探索が行われ、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積されたコストと目的地側から累積されたコストとを加算した値、即ちコスト加算値が算出されるようになっている。その結果、算出されたコスト加算値が最小になる経路が誘導経路として設定される。
【０００４】
また、上記経路の探索に使用する地図データは、道路網の情報量の差異に基づいて複数レベルに階層化された階層構造をしている。図１０は従来のナビゲーション装置のもつ階層構造の地図データを示した模式図である。
図１０に示す地図データは、例えばレベル１、レベル２、レベル３の３層に階層化された階層構造をしている。そして、レベル３は高速自動車国道、自動車専用道路、都市高速道路、有料道路を含む地図データ、レベル２はそれに加えて国道や県道の一般道路を含む地図データ、レベル１は更に加えて細街路等のその他一般道を含む詳細地図データであり、レベルが上がるにつれて道路網の情報量の少ないより粗い地図データとなっている。
そして、経路探索を実施するにあたっては、経路の探索に係る演算量を抑える為に、出発地と目的地付近の地域では、下位レベルの階層の地図データを使用して詳細に計算するのに対して、経路の中間地域では、上位レベルの階層の地図データを使用して概略的に計算し、両方の結果を統合して案内経路として出力する方法が採用されている。
更に、特開２００２−２４３４７６号公報には、経路の中間地域においても下位レベルの階層の詳細な地図データを用いた探索を行うことにより、渋滞などの交通障害がある場合に下位レベルの階層の地図データに基づく迂回経路を含んだ案内経路を使用者に対して提示することのできる経路探索案内装置について記載されている。
【特許文献１】特開２００２−２４３４７６号公報（第９頁、図２１〜図２２）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、前記した特許文献１に記載されたナビゲーション装置では、交通情報センタからの交通情報に基づいて中間地点において局地的な渋滞等の交通障害が発見された場合に、下位レベルの階層の地図データにある道路を選択した迂回経路を探索することとしているが、出発地から目的地までの経路が長い場合には、交通障害が発生していることが検出された地点まで自車が走行する間に、発生していた交通障害が解消されていることがあった。更に、経路探索時には交通障害が発生していなかった地点で、自車が走行する間に新たに交通障害が発生することがあった。従って、利用者にとって最適な経路を設定することができない場合も多かった。
一方で、交通障害が解消されたり新たに発生したことを検出する度に、経路探索を再度やり直すようにすることも可能であるが、そのような探索方法では経路探索に係るナビゲーション装置の処理負担が非常に大きくなっていた。また、誘導経路が時間の経過とともに複数回変更されると、利用者を困惑させてしまう虞もあった。
【０００６】
本発明は前記従来における問題点を解消するためになされたものであり、経路の探索を行う際に交通障害を回避した適切な経路を予め設定することを可能としたナビゲーション装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
前記目的を達成するため本願の請求項１に係るナビゲーション装置（１）は、地図データ（２３〜２５）を道路網の情報量に基づいて複数レベルに階層化して記憶する地図データ記憶手段（２２）と、目的地を設定する目的地設定手段（１３）と、前記目的地設定手段によって設定された目的地までの間の経路を前記地図データに基づいて探索する経路探索手段（１３）と、を有するナビゲーション装置において、自車が走行する際の通過予定時刻において交通障害が発生する交通障害地点（６６）を検出する交通障害検出手段（１３）を備え、前記経路探索手段は、前記交通障害検出手段によって検出された交通障害地点を含むエリアを周囲のエリアより道路網の情報量の多い下位レベルの地図データに基づいて探索することを特徴とする。
ここで、「交通障害」とは、渋滞、速度規制、通行止め等の車両の走行にとって障害となる事象をいう。
【０００８】
また、請求項２に係るナビゲーション装置（１）は、請求項１に記載のナビゲーション装置であって、前記交通障害が所定距離未満の渋滞であるか否かを判定する渋滞判定手段（１３）を有し、前記経路探索手段（１３）は前記渋滞判定手段によって所定距離未満の渋滞であると判定された場合に、前記交通障害検出手段（１３）によって検出された交通障害地点（６６）を含むエリアを周囲のエリアより下位レベルの地図データに基づいて探索することを特徴とする。
【０００９】
また、請求項３に係るナビゲーション装置（１）は、地図データ（２３〜２５）を道路網の情報量に基づいて複数レベルに階層化して記憶する地図データ記憶手段（２２）と、目的地を設定する目的地設定手段（１３）と、前記目的地設定手段によって設定された目的地までの間の経路を前記地図データに基づいて探索する第１経路探索手段（１３）と、を有するナビゲーション装置において、自車が走行する際の通過予定時刻において交通障害が発生する交通障害地点を検出する交通障害検出手段（１３）と、前記交通障害検出手段によって検出された交通障害地点（６６）を含むエリアを前記第１経路探索手段の探索時より道路網の情報量の多い下位レベルの地図データに基づいて再度探索する第２経路探索手段（１３）と、を有することを特徴とする。
【００１０】
また、請求項４に係るナビゲーション装置（１）は、請求項３に記載のナビゲーション装置であって、前記交通障害検出手段（１３）は、前記第１経路探索手段（１３）によって探索された経路を自車が走行する際の通過予定時刻において交通障害が発生する地点を前記交通障害地点（６６）として検出することを特徴とする。
【００１１】
また、請求項５に係るナビゲーション装置（１）は、請求項３又は請求項４に記載のナビゲーション装置であって、前記第２経路探索手段（１３）は、前記交通障害地点（６６）より前記第１経路探索手段（１３）によって探索された経路に沿って所定分岐数自車位置側に位置する第１分岐点（６７、６９）から所定分岐数目的地側に位置する第２分岐点（６８、７０）までの経路を含むエリアを前記第１経路探索手段の探索時より下位レベルの地図データに基づいて再度探索することを特徴とする。
ここで、「分岐点」とは３本以上のリンクが接続されているノードが該当し、インターチェンジや交差点等が該当する。
【００１２】
また、請求項６に係るナビゲーション装置（１）は、請求項３乃至請求項５のいずれかに記載のナビゲーション装置であって、前記交通障害地点（６６）を含む道路の道路種類を検出する道路種類検出手段（１３）を有し、前記第２経路探索手段（１３）は、前記道路種類検出手段によって検出された道路種類に基づいて前記第１分岐点（６７、６９）及び前記第２分岐点（６８、７０）の前記交通障害地点までの分岐点の数を変更することを特徴とする。
【００１３】
更に、請求項７に係るナビゲーション装置（１）は、請求項３乃至請求項６のいずれかに記載のナビゲーション装置であって、前記交通障害が所定距離未満の渋滞であるか否かを判定する渋滞判定手段（１３）を有し、前記第２経路探索手段（１３）は前記渋滞判定手段（１３）によって所定距離未満の渋滞であると判定された場合に、前記交通障害検出手段（１３）によって検出された交通障害地点を含むエリアを前記第１経路探索手段（１３）の探索時より道路網の情報量の多い下位レベルの地図データに基づいて再度探索することを特徴とする。
【発明の効果】
【００１４】
前記構成を有する請求項１に係るナビゲーション装置では、自車が走行する際の通過予定時刻において交通障害が発生する交通障害地点を含むエリアを、周囲のエリアより道路網の情報量の多い下位レベルの地図データに基づいて探索するので、交通障害を回避した適切な経路を予め設定することが可能となる。
また、自車の通過予定時刻に発生する交通障害を考慮した経路の探索を行うことができるので、利用者にとって最適な経路を予め設定することが可能となる。従って、利用者の利便性が向上し、快適な走行環境を提供することが可能となる。
【００１５】
また、請求項２に係るナビゲーション装置では、交通障害が所定距離未満の渋滞であると判定された場合に、交通障害地点を含むエリアを周囲のエリアより下位レベルの地図データに基づいて探索するので、下位レベルの地図データで探索する範囲が非常に広くなることによって経路の探索に係る演算量が多くなる状況が発生することを予め防止できる。従って、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
【００１６】
また、請求項３に係るナビゲーション装置では、一旦探索された経路を自車が走行する際の通過予定時刻において交通障害が発生する交通障害地点を含むエリアを、最初の探索時より道路網の情報量の多い下位レベルの地図データに基づいて探索するので、交通障害を回避した適切な経路を予め設定することが可能となる。
また、自車の通過予定時刻に発生する交通障害を考慮した経路の探索を行うことができるので、利用者にとって最適な経路を予め設定することが可能となる。従って、利用者の利便性が向上し、快適な走行環境を提供することが可能となる。
【００１７】
また、請求項４に係るナビゲーション装置では、一旦探索された経路を自車が走行する際の通過予定時刻において交通障害が発生する地点を交通障害地点として検出するので、経路上の自車の通過予定時刻をより正確に算出することが可能となる。従って、自車の通過予定時刻に発生する交通障害を考慮した経路の探索を行うことができる。
【００１８】
また、請求項５に係るナビゲーション装置では、交通障害地点より経路に沿って所定分岐数自車位置側に位置する第１分岐点から所定分岐数目的地側に位置する第２分岐点までの経路を含むエリアを最初の探索時より下位レベルの地図データに基づいて再度探索するので、交通障害の発生した地点を適切に含むエリアのみを下位レベルの地図データに変更して探索することが可能となる。従って、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
【００１９】
また、請求項６に係るナビゲーション装置では、道路種類に基づいて第１分岐点及び第２分岐点の交通障害地点までの分岐点の数を変更するので、交通障害の発生した地点を適切に含むエリアのみを道路の種類に応じた範囲で特定可能となり、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
【００２０】
更に、請求項７に係るナビゲーション装置では、交通障害が所定距離未満の渋滞であると判定された場合に、交通障害地点を含むエリアを最初の探索時より下位レベルの地図データに基づいて探索するので、下位レベルの地図データで探索する範囲が非常に広くなることによって経路の探索に係る演算量が多くなる状況が発生することを予め防止できる。従って、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
【発明を実施するための最良の形態】
【００２１】
以下、本発明に係るナビゲーション装置について具体化した一実施形態に基づき図面を参照しつつ詳細に説明する。先ず、本実施形態に係るナビゲーション装置１の概略構成について図１を用いて説明する。図１は本実施形態に係るナビゲーション装置１を示したブロック図である。
【００２２】
図１に示すように本実施形態に係るナビゲーション装置１は、自車の現在位置を検出する現在地検出処理部１１と、各種のデータが記録されたデータ記録部（地図データ記憶手段）１２と、入力された情報に基づいて、各種の演算処理を行うナビゲーション制御部（目的地設定手段、経路探索手段、交通障害検出手段、第１経路探索手段、第２経路探索手段、道路種類検出手段、渋滞判定手段）１３と、操作者からの操作を受け付ける操作部１４と、操作者に対して地図等の情報を表示する液晶ディスプレイ１５と、経路案内に関する音声ガイダンスを出力するスピーカ１６と、交通情報センタ等の情報センタとの間で通信を行う通信装置１７と、から構成されている。また、ナビゲーション制御部１３には自車の走行速度を検出する車速センサ２１が接続される。
【００２３】
以下に、ナビゲーション装置１を構成する各構成要素について説明すると、現在地検出処理部１１は、ＧＰＳ３１、地磁気センサ３２、距離センサ３３、ステアリングセンサ３４、方位検出部としてのジャイロセンサ３５、高度計（図示せず）等からなり、現在の自車の位置、方位、目標物（例えば、交差点）までの距離等を検出することが可能となっている。
【００２４】
具体的には、ＧＰＳ３１は、人工衛星によって発生させられた電波を受信することにより、地球上における自車の現在地及び現在時刻を検出し、地磁気センサ３２は、地磁気を測定することによって自車方位を検出し、距離センサ３３は、道路上の所定の位置間の距離等を検出する。ここで、距離センサ３３としては、例えば、自車の車輪（図示せず）の回転速度を測定し、測定した回転速度に基づいて距離を検出するセンサ、加速度を測定し、測定した加速度を２回積分して距離を検出するセンサ等を使用することができる。
【００２５】
また、ステアリングセンサ３４は自車の舵（だ）角を検出する。ここで、ステアリングセンサ３４としては、例えば、ステアリングホイール（図示せず）の回転部に取り付けられた光学的な回転センサ、回転抵抗センサ、車輪に取り付けられた角度センサ等が使用される。
【００２６】
そして、ジャイロセンサ３５は自車の旋回角を検出する。ここで、ジャイロセンサ３５としては、例えば、ガスレートジャイロ、振動ジャイロ等が使用される。また、ジャイロセンサ３５によって検出された旋回角を積分することにより、自車方位を検出することができる。
【００２７】
また、データ記録部１２は、外部記憶装置及び記録媒体としてのハードディスク（図示せず）と、ハードディスクに記録された地図情報ＤＢ２２、渋滞度設定テーブル２６、所定のプログラム等を読み出すとともにハードディスクに所定のデータを書き込む為のドライバである記録ヘッド（図示せず）とを備えている。尚、本実施形態においては、データ記録部１２の外部記憶装置及び記憶媒体としてハードディスクが使用されるが、ハードディスクのほかに、フレキシブルディスク等の磁気ディスクを外部記憶装置として使用することができる。また、メモリーカード、磁気テープ、磁気ドラム、ＣＤ、ＭＤ、ＤＶＤ、光ディスク、ＭＯ、ＩＣカード、光カード等を外部記憶装置として使用することもできる。尚、地図情報ＤＢ２２及び渋滞度設定テーブル２６の詳細については後述する。
【００２８】
更に、ナビゲーション制御部１３は、ナビゲーション装置１の全体の制御を行う演算装置及び制御装置としてのＣＰＵ４１、並びにＣＰＵ４１が各種の演算処理を行うに当たってワーキングメモリとして使用されるとともに、経路が探索されたときの経路データ等が記憶されるＲＡＭ４２、制御用のプログラムのほか、自車の現在位置から入力された目的地までの経路を経路上に発生する交通障害を考慮して探索し、誘導経路に設定する経路設定処理プログラム（図５参照）が記録されたＲＯＭ４３、ＲＯＭ４３から読み出したプログラムを記録するフラッシュメモリ４４等の内部記憶装置を備えている。尚、前記ＲＡＭ４２、ＲＯＭ４３、フラッシュメモリ４４等としては半導体メモリ、磁気コア等が使用される。そして、演算装置及び制御装置としては、ＣＰＵ４１に代えてＭＰＵ等を使用することも可能である。
【００２９】
また、本実施形態においては、前記ＲＯＭ４３に各種のプログラムが記録され、前記データ記録部１２に各種のデータが記録されるようになっているが、プログラム、データ等を同じ外部記憶装置、メモリーカード等からプログラム、データ等を読み出して前記フラッシュメモリ４４に書き込むこともできる。更に、メモリーカード等を交換することによって前記プログラム、データ等を更新することができる。
【００３０】
更に、前記ナビゲーション制御部１３には、操作部１４、液晶ディスプレイ１５、スピーカ１６、通信装置１７の各周辺装置（アクチュエータ）が電気的に接続されている。
【００３１】
操作部１４は、走行開始時の現在地を修正し、案内開始地点としての出発地及び案内終了地点としての目的地を入力する際等に操作され、各種のキー、ボタン等の複数の操作スイッチ（図示せず）から構成される。そして、ナビゲーション制御部１３は、各スイッチの押下等により出力されるスイッチ信号に基づき、対応する各種の動作を実行すべく制御を行う。尚、操作部１４としては、キーボード、マウス、バーコードリーダ、遠隔操作用のリモートコントロール装置、ジョイスティック、ライトペン、スタイラスペン等を使用することもできる。更に、液晶ディスプレイ１５の前面に設けたタッチパネルによって構成することもできる。
【００３２】
また、液晶ディスプレイ１５には、操作案内、操作メニュー、キーの案内、現在地から目的地までの誘導経路、誘導経路に沿った案内情報、交通情報、ニュース、天気予報、時刻、メール、テレビ番組等が表示される。尚、液晶ディスプレイ１５の代わりに、ＣＲＴディスプレイ、プラズマディスプレイ等を使用したり、車両のフロントガラスにホログラムを投影するホログラム装置等を使用することも可能である。
【００３３】
また、スピーカ１６は、ナビゲーション制御部１３からの指示に基づいて誘導経路に沿った走行を案内する音声ガイダンスを出力する。ここで、案内される音声ガイダンスとしては、例えば、「２００ｍ先の交差点を右折してください。」や「この先の国道○○号線が渋滞しています。」等がある。なお、スピーカ１６より出力される音声としては、合成された音声のほかに、各種効果音、予めテープやメモリ等に録音された各種の案内情報を出力することもできる。
【００３４】
そして、通信装置１７は、交通情報センタ、例えば、ＶＩＣＳ（登録商標：Ｖｅｈｉｃｌｅ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）センタ等から送信された渋滞情報、規制情報、駐車場情報、交通事故情報等の各情報から成る交通情報を、道路に沿って配設された電波ビーコン装置、光ビーコン装置等を介して電波ビーコン、光ビーコン等として受信するビーコンレシーバである。また、通信装置１７としては、ＬＡＮ、ＷＡＮ、イントラネット、携帯電話回線網、電話回線網、公衆通信回線網、専用通信回線網、インターネット等の通信回線網等の通信系において通信を可能とするネットワーク機器であっても良い。更に、通信装置１７は前記情報センタからの情報の他に、ニュース、天気予報等の情報から成るＦＭ多重情報を、ＦＭ放送局を介してＦＭ多重放送として受信するＦＭ受信機を備える。尚、前記ビーコンレシーバ及びＦＭ受信機は、ユニット化されてＶＩＣＳレシーバとして配設されるようになっているが、別々に配設することもできる。
【００３５】
次に、データ記録部１２に格納された地図情報ＤＢ２２について説明する。ここで、地図情報ＤＢ２２には、経路案内及び地図表示に必要な地図データが記録されており、地図データは、例えば地図を表示するための地図表示データ、各交差点に関する交差点データ、道路（リンク）に関するリンクデータ、ノード点に関するノードデータ、経路を探索するための探索データ、施設に関する施設データ、地点を検索するための検索データ等から構成されている。
【００３６】
また、本実施形態において地図データは、図２に示されるように道路網の情報量に応じて３層に階層化されている。図２は地図情報ＤＢに記憶される３層に階層化された地図データを示した模式図である。この場合、例えば、レベル１の階層は１０ｋｍ四方のメッシュによって複数に区分された地図データであり、レベル２の階層は２０ｋｍ四方のメッシュによって複数に区分された地図データであり、レベル３の階層は４０ｋｍ四方のメッシュによって複数に区分された地図データである。
そして、下位レベルの階層の地図データは上位レベルの階層の地図データより道路網の情報量がより多く含まれており、例えばレベル３の地図データは高速自動車国道、自動車専用道路、都市高速道路、有料道路に関する情報が格納されている。また、レベル２の地図データはレベル３に含まれる道路網に加えて国道や県道等の主要な一般道路に関する情報が格納されている。また、レベル１の地図データはレベル２に含まれる道路網に加えて細街路等のその他全ての一般道に関する詳細な道路網に関する情報が格納されている。
【００３７】
更に、下位レベルの階層における地図データのメッシュでは詳細なデータを有する代わりにカバーする範囲が狭く、上位レベルの階層における地図データのメッシュでは粗いデータしか有していない代わりにカバーする範囲が広くなっている。例えば、最下位レベル（レベル１）の階層におけるメッシュでは細街路を含む全ての道路の道路データを有するが市町村範囲しかカバーしておらず、最上位レベル（レベル３）の階層におけるメッシュでは高速道路や有料道路等の道路の道路データしか有していないが日本全国をカバーする。
【００３８】
尚、各レベルの階層、即ち最上層であるレベル３の階層、中間層であるレベル２の階層及び最下層であるレベル１の階層におけるメッシュの大きさ、即ち、メッシュのカバーする範囲の広さは、適宜決定することができる。また、地図データを構成するレベルの数、即ち、階層の数も、必ずしも３層である必要はなく、例えば５層や１０層であっても良い。
【００３９】
そして、各レベル階層の地図データ２３〜２５は、図３に示すように前記した地図表示データ、交差点データ、リンクデータ、ノードデータ、探索データ、施設データ、検索データ等によってそれぞれ構成されている。図３は本実施形態に係るナビゲーション装置１の地図情報ＤＢ２２の記憶領域を示した図である。
【００４０】
ここで、特に地図データを構成する地図表示データとしては、各レベル階層の地図データ２３〜２５に応じた地図表示を行う為の地図描画情報が記憶される。
【００４１】
また、リンクデータとしては、それぞれのレベル階層の地図データ２３〜２５において道路を構成する各リンクに関してリンクの属する道路の幅員、勾（こう）配、カント、バンク、路面の状態、道路の車線数、車線数の減少する箇所、幅員の狭くなる箇所、踏切り等を表すデータが、コーナに関して、曲率半径、交差点、Ｔ字路、コーナの入口及び出口等を表すデータが、道路属性に関して、降坂路、登坂路等を表すデータが、道路種別に関して、国道、県道、細街路等の一般道のほか、高速自動車国道、自動車専用道路、都市高速道路、一般有料道路、有料橋等の有料道路を表すデータがそれぞれ記録される。更に、有料道路に関して、有料道路の入口及び出口の取付道（ランプウェイ）、料金所（インターチェンジ）等に関するデータが記録される。
【００４２】
また、ノードデータとしては、それぞれのレベル階層の地図データ２３〜２５において道路の分岐点（交差点、Ｔ字路等も含む）、各道路に曲率半径等に応じて所定の距離ごとに設定されたノード点の座標（位置）、ノードが交差点に対応するノードであるか等を表すノード属性、ノードに接続するリンクのリンク番号のリストである接続リンク番号リスト、ノードにリンクを介して隣接するノードのノード番号のリストである隣接ノード番号リスト、各ノード点の高さ（高度）等に関するデータ等が記録される。
【００４３】
また、探索データとしては、それぞれのレベル階層の地図データ２３〜２５において設定された目的地までの経路を探索及び表示する際に使用されるデータについて記録されており、ノードを通過する際のコスト（以下、ノードコストという）や道路を構成するリンクのコスト（以下、リンクコストという）からなる探索コストを算出する為に使用するコストデータ、リンクを通過するのに必要な旅行時間、経路探索により選択された経路を液晶ディスプレイ１５の地図上に表示するための経路表示データ等から構成されている。
ここで、ノードコストは交差点に対応するノードに対して基本的に設定されており、本実施形態に係るナビゲーション装置１では、信号の有無や交差点を通過する際の自車の走行経路（即ち直進、右折及び左折の種類）によってその値が決定される。
また、リンクコストは、リンクを構成する道路属性や道路種別、道路幅、車線数、リンク長さに加え、後述する渋滞度設定テーブル２６（図４参照）によって検出される渋滞度等の交通情報に関するデータを用いて算出される。
【００４４】
また、施設データとしては、各地域のホテル、病院、ガソリンスタンド、駐車場、観光施設、インターチェンジ、レストラン、サービスエリア等の建物に関するデータが建物を特定する施設ＩＤとともに記録される。なお、前記地図情報ＤＢ２２には、所定の情報をナビゲーション装置１のスピーカ１６によって出力するための音声出力データも記録される。
【００４５】
そして、ナビゲーション制御部１３は、現在地（出発地）から目的地までの距離が短距離（例えば、３ｋｍ程度）の経路探索の場合には、現在地周辺の最下層の地図データであるレベル１の地図データのメッシュのみを使用して経路を探索する。
また、現在地から目的地までの距離が中距離（例えば、５０ｋｍ程度）の経路探索の場合には、現在地及び目的地周辺については最下層の地図データであるレベル１の地図データのメッシュを使用し、前記レベル１の地図データのメッシュに隣接するエリアは中間層の地図データであるレベル２の地図データのメッシュを使用して経路を探索する。
更に、現在地から目的地までの距離が長距離（例えば、３００ｋｍ程度）の経路探索の場合には、現在地及び目的地周辺の最下層の地図データであるレベル１の地図データのメッシュを使用し、前記レベル１の地図データのメッシュに隣接するエリアは中間層の地図データであるレベル２の地図データのメッシュを使用し、前記レベル２の地図データのメッシュに隣接するエリアは最上層の地図データであるレベル３の地図データのメッシュを使用して経路を探索する。それによって、経路を探索の為の演算量を抑えることができ、経路探索に必要な時間を短縮することができる。
【００４６】
そして、ナビゲーション制御部１３が経路を探索する際には、地図データにおける探索データ中の道路データを調査して、探索に使用されるメッシュに含まれる道路（リンク及びノード）についての探索コスト（ノードコスト及びリンクコスト）を計算して、経路を探索する。具体的には、出発地側及び目的地側から経路の探索が行われ、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積された探索コストと目的地側から累積された探索コストとを加算した値、即ち、コスト加算値が算出される。その結果、コストが小さい順に経路を複数本（例えば５本）選択し、最もコスト加算値が小さくなった経路、又は利用者によって選択された経路を誘導経路として設定する。
【００４７】
また、これら地図情報ＤＢ２２の内容は、ＤＶＤや外部に接続したメモリーカード等の記録媒体から情報を転送すること、又は特定の情報センタ等から通信装置１７を介して情報をダウンロードすること等によって更新される。
【００４８】
次に、データ記録部１２に格納された渋滞度設定テーブル２６について図４を用いて説明する。図４は本実施形態に係る渋滞度設定テーブル２６の一例について示した図である。ここで、渋滞度設定テーブル２６は自車の走行に影響を与える交通障害の内、特に渋滞の発生する区間と時刻とを特定したテーブルである。
【００４９】
図４に示すように、本実施形態に係る渋滞度設定テーブル２６は、リンクを特定するリンク番号と、曜日及び時間帯と、リンク番号によって特定されるリンクの各曜日及び各時間帯での渋滞の程度を特定する渋滞度とから構成されている。
ここで、渋滞度は「１」、「２」、「３」の３種類の数値のいずれかによって設定され、「１」が設定されたリンクではその時間帯に渋滞が発生しないことを意味する。一方、「２」が設定されたリンクではその時間帯に渋滞が発生し、リンクを走行するのに通常の２倍程度の時間が必要となることを意味する。また、「３」が設定されたリンクではその時間帯に渋滞が発生し、リンクを走行するのに通常の３倍程度の時間が必要となることを意味する。
例えば、図４に示す渋滞度設定テーブル２６では、リンク番号ＸＺ１のリンクについて、月曜日の８：１５〜８：３０の間は渋滞度が「２」に設定され、８：３０〜８：４５の間は渋滞度が「３」に設定され、８：４５〜９：００の間は渋滞度が「２」に設定されていることを示している。
【００５０】
そして、ナビゲーション制御部１３は、渋滞度設定テーブル２６によって前記地図情報ＤＢ２２に記憶された各レベル階層の地図データに含まれるリンク毎に、各曜日及び各時間帯における渋滞度を検出することが可能となる。その結果、後述するように自車が通過する予定時刻で渋滞の発生するリンク（即ち、渋滞度が「１」以外のリンク）が検出された場合には、そのリンクを通過するのに必要な旅行時間やリンクコストについて渋滞度を乗じた値に調整する。そして、調整された旅行時間やリンクコストに基づいて後述するようにタイムスライスによる経路探索が行われる（図５のＳ４、Ｓ１１）。
尚、渋滞度設定テーブル２６はナビゲーション装置１の出荷時に予めデータ記録部１２に対して記憶されているが、通信装置１７を介して交通情報センタから受信した情報に基づいて渋滞度設定テーブル２６の内容の更新を行うようにしても良い。また、自車の走行履歴に基づいて渋滞度設定テーブル２６の内容を更新するようにしても良い。
【００５１】
続いて、前記構成を有するナビゲーション装置１においてＣＰＵ４１が実行する経路設定処理プログラムについて図５に基づき説明する。図５は本実施形態に係る経路案内処理プログラムのフローチャートである。ここで、経路案内処理プログラムは車両のイグニションがＯＮされた際に実行され、自車の現在位置から入力された目的地までの経路を経路上に発生する交通障害を考慮して探索し、誘導経路に設定するプログラムである。尚、以下の図５にフローチャートで示されるプログラムは、ナビゲーション装置１が備えているＲＡＭ４２やＲＯＭ４３に記憶されており、ＣＰＵ４１により実行される。
【００５２】
先ず、経路設定処理プログラムではステップ（以下、Ｓと略記する）１において、ＣＰＵ４１は、利用者の操作部１４の操作に基づいて目的地を設定する。次にＳ２では、現在地検出処理部１１の検出結果に基づいて自車の現在位置を検出する。尚、上記Ｓ１の処理が目的地設定手段の処理に相当する。
【００５３】
その後に、渋滞、通行止め、速度規制などの交通障害を考慮せずに、自車の現在位置である出発地から前記Ｓ１で設定された目的地までの経路の探索処理（以下、第１経路探索処理という）を行う（Ｓ３）。
【００５４】
以下に、前記Ｓ３の第１経路探索処理における経路の探索手順について図６を用いて説明する。図６は前記Ｓ３で本実施形態に係るナビゲーション装置１が実行する第１経路探索処理によって探索された経路を地図上に示した模式図である。尚、図６では特に出発地から目的地までの距離が長距離（例えば、３００ｋｍ程度）であって、中間地点を最上層のレベル３の地図データを用いて探索する場合を例に挙げて説明する。
【００５５】
先ず、第１経路探索処理において、ナビゲーション制御部１３が経路を探索する際には、地図データにおける探索データ中の道路データを調査して、探索に使用されるメッシュに含まれる道路（リンク及びノード）についての探索コスト（ノードコスト及びリンクコスト）を計算する。その後、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積された探索コストと目的地側から累積された探索コストとを加算した値、即ち、コスト加算値が算出される。
そして、上記の探索コスト及びコスト加算値の算出の際には、図６に示すように、出発地及び目的地周辺では最下層の地図データであるレベル１の地図データのメッシュ５１、６５がそれぞれ使用される。また、前記レベル１の地図データのメッシュ５１、６５に隣接するエリアは中間層の地図データであるレベル２の地図データのメッシュ５２、５３、６２〜６４が使用される。そして、前記レベル２の地図データのメッシュ５２、５３、６２〜６４に隣接するエリア、並びにその中間地点のエリアは最上位の地図データであるレベル３の地図データのメッシュ５４〜６１が使用される。尚、探索する経路が異なるレベルの地図データのメッシュに移行する際には、異なるレベルの地図データで共通して含まれるノードを介して移行する。
そして、探索の結果、コスト加算値が所定の条件を満たした経路（例えば、コスト加算値が小さいほうから順に２つの経路）として、経路Ａと経路Ｂがそれぞれ図６に示すように経路の候補として選択される。尚、上記Ｓ３の処理が第１経路探索手段の処理に相当する。
【００５６】
続いて、Ｓ４では前記Ｓ３の第１経路探索処理で探索された経路上の交通障害（本実施形態では渋滞のみ）を考慮してタイムスライス計算し、交通障害地点である渋滞の発生する区間と、その渋滞度を検出する。
以下に、タイムスライス計算の具体的方法について説明すると、先ずＣＰＵ４１はＧＰＳ３１により現在時刻を検出し、更に前記Ｓ３の第１経路探索処理で探索された経路（図６では経路Ａと経路Ｂ）を構成する各リンクの旅行時間に基づいて、自車が経路を構成する各リンクを走行する通過予定時刻を算出する。その後、算出された通過予定時刻と渋滞度設定テーブル２６（図４参照）とに基づいて、経路を構成する各リンクの通過予定時刻で渋滞が発生するか否か（具体的には、渋滞度が「１」以外のリンクがあるか否か）を判定する。その結果、通過予定時刻に渋滞が発生すると判定された場合には、発生すると判定されたリンクの旅行時間を渋滞度に基づいて調整し（具体的には、渋滞度を乗じた旅行時間とする）、更に、調整した旅行時間に基づいて再び経路を構成する各リンクを走行する通過予定時刻を算出する。
その後、同様に再度算出された通過予定時刻と渋滞度設定テーブル２６（図４参照）とに基づいて、経路を構成するリンクの通過予定時刻で新たに渋滞が発生するリンクがあるか否かを判定し、渋滞が発生すると判定された場合には、発生すると判定されたリンクの旅行時間を渋滞度に基づいて調整する。以上の操作を新たに渋滞が発生するリンクが検出されなくなるまで行う。そして、最終的に渋滞が発生すると予測された全てのリンクについて渋滞度設定テーブル２６を用いてそれぞれ渋滞度を検出する。尚、上記Ｓ４の処理が交通障害検出手段の処理に相当する。
【００５７】
次に、Ｓ５では前記Ｓ４の検出結果に基づいて前記第１経路探索処理で探索された経路上に渋滞するリンクがあるか否か、即ち、自車が経路を構成する各リンクを走行する通過予定時刻において渋滞度設定テーブル２６で渋滞度が「１」以外に設定されたリンクがあるか否かが判定される。
【００５８】
その結果、経路上に渋滞するリンクがあると判定された場合（Ｓ５：ＹＥＳ）には、Ｓ６へと移行する。
一方、経路上に渋滞するリンクがないと判定された場合（Ｓ５：ＮＯ）には、渋滞を考慮する必要がないので前記Ｓ３の第１経路探索処理で探索された経路（図６では経路Ａ及び経路Ｂ）の内、コスト加算が最も小さい経路をそのまま選択する（Ｓ１２）。その後、選択された経路を誘導経路に設定し（Ｓ１３）、当該経路案内処理プログラムを終了する。そして、設定された誘導経路に従って液晶ディスプレイ１５に誘導経路を表示するとともに、液晶ディスプレイ１５の表示とスピーカ１６から出力する音声により、利用者に対して経路の案内を行う。尚、第１経路探索処理で探索された経路の選択では、利用者の操作部１４の操作に基づいて選択された経路を誘導経路に設定することとしても良い。
【００５９】
次に、Ｓ６では前記第１経路探索処理で探索された経路上において渋滞すると判定されたリンクの長さ（即ち渋滞区間）が所定距離（本実施形態では３０ｋｍ）未満であるか否かが判定される。尚、Ｓ６の処理が渋滞判定手段の処理に相当する。
【００６０】
そして、渋滞区間が所定距離未満であると判定された場合（Ｓ６：ＹＥＳ）には、Ｓ７へと移行する。それに対して、渋滞区間が所定距離以上であると判定された場合（Ｓ６：ＮＯ）には、その渋滞区間を含むエリアの地図データのレベルを下げて再度探索するとすると、ＣＰＵ４１の演算量が非常に多くなってしまうので、前記Ｓ３の第１経路探索処理で探索された経路（図６では経路Ａ及び経路Ｂ）の内、前記Ｓ４で検出された渋滞度に基づいて調整したコスト加算（具体的には、渋滞度が「１」以外のリンクのリンクコストについて渋滞度を乗じたリンクコストとする）が最も小さい経路を選択する（Ｓ１２）。その後、選択された経路を誘導経路に設定し（Ｓ１３）、当該経路案内処理プログラムを終了する。尚、第１経路探索処理で探索された経路の選択では、利用者の操作部１４の操作に基づいて選択された経路を誘導経路に設定することとしても良い。
【００６１】
続いて、Ｓ７では前記第１経路探索処理で探索された経路上において渋滞すると判定されたリンクが高速道路（高速自動車国道、自動車専用道路、都市高速道路など）であるか否かを地図情報ＤＢ２２のリンクデータに基づいて判定する。尚、Ｓ７の処理が道路種類検出手段の処理に相当する。
【００６２】
その結果、渋滞区間が高速道路であると判定された場合（Ｓ７：ＹＥＳ）には、経路に沿って渋滞区間から１分岐数分自車位置（出発地）側に位置する第１分起点と、経路に沿って渋滞区間から１分岐数分目的地側に位置する第２分起点とを検出し、更に検出された第１分岐点と第２分岐点の区間を含む最下位レベル（レベル１）の階層の地図データのメッシュを地図情報ＤＢ２２から抽出する（Ｓ８）。ここで、分岐点とは３本以上のリンクが接続されているノードが該当し、インターチェンジや交差点等が該当する。
【００６３】
一方、渋滞区間が高速道路以外の一般道路であると判定された場合（Ｓ７：ＮＯ）には、経路に沿って渋滞区間から２分岐数分自車位置（出発地）側に位置する第３分起点と、経路に沿って渋滞区間から２分岐数分目的地側に位置する第４分起点とを検出し、更に検出された第３分岐点と第４分岐点の区間を含む最下位レベル（レベル１）の階層の地図データのメッシュを地図情報ＤＢ２２から抽出する（Ｓ９）。
【００６４】
ここで、前記Ｓ８及びＳ９の処理について、図６に示すように第１経路探索処理で探索された経路Ａの通過予定時刻に渋滞区間６６が発生することが検出された場合を具体例に挙げて説明する。ここで、図７は図６に示す経路上の地図の内、メッシュ５８の特に渋滞区間６６付近を拡大して示した模式図である。
ここで、特に渋滞区間６６が高速道路であった場合には、図７に示すように渋滞区間６６の１分岐数分自車位置（出発地）側に位置する第１分起点６７と、経路に沿って渋滞区間から１分岐数分目的地側に位置する第２分起点６８とがそれぞれ検出され、その区間を含む最下位レベル（レベル１）の階層の地図データのメッシュ８１〜８４が抽出される。
また、渋滞区間６６が高速道路以外の道路であった場合には、図７に示すように渋滞区間６６の２分岐数分自車位置（出発地）側に位置する第３分起点６９と、経路に沿って渋滞区間から２分岐数分目的地側に位置する第４分起点７０とがそれぞれ検出され、その区間を含む最下位レベル（レベル１）の階層の地図データのメッシュ８１〜８４が抽出される。
【００６５】
次に、Ｓ１０では前記Ｓ８又はＳ９で抽出されたメッシュに含まれる地図データ（地図表示データ、交差点データ、リンクデータ、ノードデータ、探索データ、施設データ、検索データ等）を地図情報ＤＢ２２から取得する。
【００６６】
続いて、Ｓ１１では前記Ｓ４で抽出された各リンクの渋滞度を考慮するとともに前記Ｓ１０で取得した地図データを用い、再び自車の現在位置である出発地から前記Ｓ１で設定された目的地までの経路の探索処理（以下、第２経路探索処理という）を行う。
【００６７】
以下に、前記Ｓ１１の第２経路探索処理における経路の探索手順について図８を用いて説明する。図８は前記第１経路探索処理によって図６に示す経路Ａ及び経路Ｂが探索され、且つ渋滞区間６６が検出された後に、前記Ｓ１１で本実施形態に係るナビゲーション装置１が実行する第２経路探索処理によって探索された経路を地図上に示した模式図である。
【００６８】
先ず、第２経路探索処理において、ナビゲーション制御部１３が経路を探索する際には、地図データにおける探索データ中の道路データを調査して、探索に使用されるメッシュに含まれる道路（リンク及びノード）についての探索コスト（ノードコスト及びリンクコスト）を前記Ｓ４で検出された渋滞度を考慮しつつ計算する。また、第２経路探索処理では渋滞が発生する区間として前記Ｓ４で検出されたリンクのリンクコストに、同じく検出された渋滞度を乗じることによって、交通障害を考慮したコスト計算を行う。
その後、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積された探索コストと目的地側から累積された探索コストとを加算した値、即ち、コスト加算値が算出される。
そして、上記の探索コスト及びコスト加算値の算出の際には、図８に示すように、現在地及び目的地周辺、並びに渋滞区間６６の前後の分岐点６７〜７０を含むエリアでは最下層の地図データであるレベル１の地図データのメッシュ５１、６５、８１〜８４がそれぞれ使用される。また、前記レベル１の地図データのメッシュ５１、６５に隣接するエリアは中間層の地図データであるレベル２の地図データのメッシュ５２、５３、６２〜６４が使用される。そして、前記レベル２の地図データのメッシュ５２、５３、６２〜６４に隣接するエリア、並びにその中間地点のエリアは最上位の地図データであるレベル３の地図データのメッシュ５４〜６１が使用される。尚、探索する経路が異なるレベルの地図データのメッシュに移行する際には、異なるレベルの地図データで共通して含まれるノードを介して移行する。
そして、探索の結果、コスト加算値が所定の条件を満たした経路（例えば、コスト加算値が小さいほうから順に２つの経路）として、第１経路探索処理で探索された経路Ｂと、メッシュ８１〜８４のリンクを利用して渋滞区間６６を迂回した経路Ｃが図８に示すように新たに経路の候補として選択される。尚、図８では渋滞区間６６の渋滞度を考慮したことにより、経路Ａより経路Ｂ及び経路Ｃの方がコスト加算値が小さくなった場合を示しているが、渋滞度を考慮しても経路Ａのコスト加算値が経路Ｂ又は経路Ｃより小さい場合には渋滞区間を有する経路Ａが経路の候補として選択されることとなる。尚、上記Ｓ１１の処理が経路探索手段及び第２経路探索手段の処理に相当する。
【００６９】
その後、Ｓ１２では、前記Ｓ１１の第２経路探索処理で探索された経路（図８では経路Ｂ及び経路Ｃ）の内、コスト加算値が最も小さい経路を選択する。その後、選択された経路を誘導経路に設定し（Ｓ１３）、当該経路案内処理プログラムを終了する。尚、第１経路探索処理で探索された経路の選択では、利用者の操作部１４の操作に基づいて選択された経路を誘導経路に設定することとしても良い。そして、設定された誘導経路に従って液晶ディスプレイ１５に誘導経路を表示するとともに、液晶ディスプレイ１５の表示とスピーカ１６から出力する音声により、利用者に対して経路の案内を行う。尚、第２経路探索処理で探索された経路の選択では、利用者の操作部１４の操作に基づいて選択された経路を誘導経路に設定することとしても良い。
【００７０】
以上詳細に説明した通り、本実施形態に係るナビゲーション装置１では、自車が走行する際の通過予定時刻において交通障害の一つである渋滞が発生する渋滞区間をタイムスライス計算を用いて検出し（Ｓ４）、その渋滞区間を含むエリアを、第２経路探索処理で周囲のエリアより道路網の情報量の多い下位レベルの地図データに基づいて探索する（Ｓ１１）ので、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
また、第２経路探索処理では、渋滞区間を含むエリアを交通障害を考慮せずに行った第１経路探索処理より道路網の情報量の多い下位レベルの地図データに基づいて探索する（Ｓ１１）ので、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
また、第１経路探索処理で探索された経路を自車が走行する際の通過予定時刻において交通障害が発生する地点をタイムスライス計算により交通障害地点として検出する（Ｓ４）ので、経路上の自車の通過予定時刻をより正確に算出することが可能となる。
また、渋滞区間より経路に沿って所定分岐数自車位置側に位置する第１分岐点又は第３分岐点から所定分岐数目的地側に位置する第２分岐点又は第４分岐点までの経路を含むエリアを最初の探索時より下位レベルの地図データに基づいて再度探索するので、渋滞区間の発生した地点を適切に含むエリアのみを下位レベルの地図データに変更して探索することが可能となる。従って、経路の探索に係る演算量を抑えつつ交通障害を回避した適切な経路を予め設定することが可能となる。
また、高速道路で渋滞が発生した場合における第１分岐点及び第２分岐点の渋滞区間までの分岐数と、高速道路以外の一般道路で渋滞が発生した場合における第３分岐点及び第４分岐点の渋滞区間までの分岐数とをそれぞれ変更することによって、交通障害の発生した地点を適切に含むエリアのみを道路の種類に応じた範囲で特定可能となる。
また、渋滞区間の長さが所定距離未満の渋滞であると判定された場合（Ｓ６：ＹＥＳ）のみに、渋滞区間を含むエリアを周囲のエリアより下位レベルの地図データに基づいて探索するので、下位レベルの地図データで探索する範囲が非常に広くなることによって経路の探索に係る演算量が多くなる状況が発生することを予め防止できる。
また、自車の通過予定時刻に発生する渋滞を考慮した経路の探索を行うことができるので、利用者にとって最適な経路を予め設定することが可能となり、一旦設定された経路が走行中に変更される虞も無い。従って、利用者の利便性が向上し、快適な走行環境を提供することが可能となる。
【００７１】
尚、本発明は前記実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の改良、変形が可能であることは勿論である。
例えば、本実施形態では地図データに含まれる各リンクの渋滞度を設定した渋滞度設定テーブル２６をナビゲーション装置１に記憶することとしているが、渋滞度設定テーブルを車両内でなく外部の施設である交通情報センタ内に記憶させ、車両が交通情報センタと通信を行うことによってリンクの渋滞度に関する情報を取得することとしても良い。
【００７２】
ここで、図９は前記他の実施形態における通信システム１０１を示した概略構成図である。図９に示すように、通信システム１０１は、ナビゲーション装置１と、交通情報センタ１０２とネットワーク１０４とから構成される。そして、交通情報センタ１０２とナビゲーション装置１は、ネットワーク１０４を介して各種の情報の送受信が可能となるように構成されている。
【００７３】
また、交通情報センタ１０２は、サーバ１１１と、サーバ１１１に接続された情報記録部としての交通情報ＤＢ１１５と、センタ側通信装置１１６とを備える。また、サーバ１１１は、サーバ１１１の全体の制御を行う演算装置及び制御装置としてのＣＰＵ１１２、並びにＣＰＵ１１２が各種の演算処理を行うに当たってワーキングメモリとして使用されるＲＡＭ１１３、ナビゲーション装置１からの通信に基づいて交通情報ＤＢ１１５に格納された渋滞度設定テーブル１１７から第１経路探索処理の経路探索に関連するエリア（図６ではメッシュ５１〜６５）に含まれる各リンクの渋滞度に係る情報を抽出し、ナビゲーション装置１に対して送信するための各種の制御プログラムが記録されたＲＯＭ１１４等の内部記憶装置を備えている。また、ＣＰＵ１１２に代えてＭＰＵ等を使用することができる。
【００７４】
そして、ＣＰＵ１１２はナビゲーション装置１に対して第１経路探索処理の経路探索に関連するエリア（図６ではメッシュ５１〜６５）に含まれる各リンクの渋滞度に係る情報を送信し、一方で、ナビゲーション装置１は交通情報センタ１０２から送信された各リンクの渋滞度に関する情報に基づいて、自車が走行する際の通過予定時刻において渋滞の発生するリンクと渋滞度とをそれぞれタイムスライス計算により検出する（Ｓ４）。
それによって、自車の通過予定時刻において渋滞の発生するリンクと、その渋滞度をそれぞれナビゲーション制御部１３が検出することが可能となる。
【００７５】
また、本実施形態では渋滞区間の前後の分岐点を含むエリアのみを、最下層のレベル１の地図データに変更して探索することとしているが、分岐点を含むエリアに隣接するエリアについても周囲より下位のレベル（例えばレベル２）の地図データに変更して探索を行うこととしても良い。
【図面の簡単な説明】
【００７６】
【図１】本実施形態に係るナビゲーション装置を示したブロック図である。
【図２】地図情報ＤＢに記憶される３層に階層化された地図データを示した模式図である。
【図３】本実施形態に係るナビゲーション装置の地図情報ＤＢの記憶領域を示した図である。
【図４】本実施形態に係る渋滞度設定テーブルの一例について示した図である。
【図５】本実施形態に係る経路案内処理プログラムのフローチャートである。
【図６】ステップ３で本実施形態に係るナビゲーション装置が実行する第１経路探索処理によって探索された経路を地図上に示した模式図である。
【図７】図６に示す経路上の地図の内、特に渋滞区間付近を拡大して示した模式図である。
【図８】第１経路探索処理によって図６に示す経路が探索され、且つ渋滞区間が検出された後に、ステップ１１で本実施形態に係るナビゲーション装置が実行する第２経路探索処理によって探索された経路を地図上に示した模式図である。
【図９】他の実施形態における通信システムを示した概略構成図である。
【図１０】従来のナビゲーション装置のもつ階層構造の地図データを示した模式図である。
【符号の説明】
【００７７】
１ ナビゲーション装置
１１ 現在地検出処理部
１２ データ記録部
１３ ナビゲーション制御部
２２ 地図情報ＤＢ
２６ 渋滞度設定テーブル
４１ ＣＰＵ
４２ ＲＡＭ
４３ ＲＯＭ
６６ 渋滞区間
６７ 第１分起点
６８ 第２分起点
６９ 第３分起点
７０ 第４分起点
【特許請求の範囲】
【請求項１】
地図データを道路網の情報量に基づいて複数レベルに階層化して記憶する地図データ記憶手段と、
目的地を設定する目的地設定手段と、
前記目的地設定手段によって設定された目的地までの間の経路を前記地図データに基づいて探索する経路探索手段と、を有するナビゲーション装置において、
自車が走行する際の通過予定時刻において交通障害が発生する交通障害地点を検出する交通障害検出手段を備え、
前記経路探索手段は、前記交通障害検出手段によって検出された交通障害地点を含むエリアを周囲のエリアより道路網の情報量の多い下位レベルの地図データに基づいて探索することを特徴とするナビゲーション装置。
【請求項２】
前記交通障害が所定距離未満の渋滞であるか否かを判定する渋滞判定手段を有し、
前記経路探索手段は前記渋滞判定手段によって所定距離未満の渋滞であると判定された場合に、前記交通障害検出手段によって検出された交通障害地点を含むエリアを周囲のエリアより下位レベルの地図データに基づいて探索することを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
地図データを道路網の情報量に基づいて複数レベルに階層化して記憶する地図データ記憶手段と、
目的地を設定する目的地設定手段と、
前記目的地設定手段によって設定された目的地までの間の経路を前記地図データに基づいて探索する第１経路探索手段と、を有するナビゲーション装置において、
自車が走行する際の通過予定時刻において交通障害が発生する交通障害地点を検出する交通障害検出手段と、
前記交通障害検出手段によって検出された交通障害地点を含むエリアを前記第１経路探索手段の探索時より道路網の情報量の多い下位レベルの地図データに基づいて再度探索する第２経路探索手段と、を有することを特徴とするナビゲーション装置。
【請求項４】
前記交通障害検出手段は、前記第１経路探索手段によって探索された経路を自車が走行する際の通過予定時刻において交通障害が発生する地点を前記交通障害地点として検出することを特徴とする請求項３に記載のナビゲーション装置。
【請求項５】
前記第２経路探索手段は、前記交通障害地点より前記第１経路探索手段によって探索された経路に沿って所定分岐数自車位置側に位置する第１分岐点から所定分岐数目的地側に位置する第２分岐点までの経路を含むエリアを前記第１経路探索手段の探索時より下位レベルの地図データに基づいて再度探索することを特徴とする請求項３又は請求項４に記載のナビゲーション装置。
【請求項６】
前記交通障害地点を含む道路の道路種類を検出する道路種類検出手段を有し、
前記第２経路探索手段は、前記道路種類検出手段によって検出された道路種類に基づいて前記第１分岐点及び前記第２分岐点の前記交通障害地点までの分岐点の数を変更することを特徴とする請求項３乃至請求項５のいずれかに記載のナビゲーション装置。
【請求項７】
前記交通障害が所定距離未満の渋滞であるか否かを判定する渋滞判定手段を有し、
前記第２経路探索手段は前記渋滞判定手段によって所定距離未満の渋滞であると判定された場合に、前記交通障害検出手段によって検出された交通障害地点を含むエリアを前記第１経路探索手段の探索時より道路網の情報量の多い下位レベルの地図データに基づいて再度探索することを特徴とする請求項３乃至請求項６のいずれかに記載のナビゲーション装置。
【請求項１】
地図データを道路網の情報量に基づいて複数レベルに階層化して記憶する地図データ記憶手段と、
目的地を設定する目的地設定手段と、
前記目的地設定手段によって設定された目的地までの間の経路を前記地図データに基づいて探索する経路探索手段と、を有するナビゲーション装置において、
自車が走行する際の通過予定時刻において交通障害が発生する交通障害地点を検出する交通障害検出手段を備え、
前記経路探索手段は、前記交通障害検出手段によって検出された交通障害地点を含むエリアを周囲のエリアより道路網の情報量の多い下位レベルの地図データに基づいて探索することを特徴とするナビゲーション装置。
【請求項２】
前記交通障害が所定距離未満の渋滞であるか否かを判定する渋滞判定手段を有し、
前記経路探索手段は前記渋滞判定手段によって所定距離未満の渋滞であると判定された場合に、前記交通障害検出手段によって検出された交通障害地点を含むエリアを周囲のエリアより下位レベルの地図データに基づいて探索することを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
地図データを道路網の情報量に基づいて複数レベルに階層化して記憶する地図データ記憶手段と、
目的地を設定する目的地設定手段と、
前記目的地設定手段によって設定された目的地までの間の経路を前記地図データに基づいて探索する第１経路探索手段と、を有するナビゲーション装置において、
自車が走行する際の通過予定時刻において交通障害が発生する交通障害地点を検出する交通障害検出手段と、
前記交通障害検出手段によって検出された交通障害地点を含むエリアを前記第１経路探索手段の探索時より道路網の情報量の多い下位レベルの地図データに基づいて再度探索する第２経路探索手段と、を有することを特徴とするナビゲーション装置。
【請求項４】
前記交通障害検出手段は、前記第１経路探索手段によって探索された経路を自車が走行する際の通過予定時刻において交通障害が発生する地点を前記交通障害地点として検出することを特徴とする請求項３に記載のナビゲーション装置。
【請求項５】
前記第２経路探索手段は、前記交通障害地点より前記第１経路探索手段によって探索された経路に沿って所定分岐数自車位置側に位置する第１分岐点から所定分岐数目的地側に位置する第２分岐点までの経路を含むエリアを前記第１経路探索手段の探索時より下位レベルの地図データに基づいて再度探索することを特徴とする請求項３又は請求項４に記載のナビゲーション装置。
【請求項６】
前記交通障害地点を含む道路の道路種類を検出する道路種類検出手段を有し、
前記第２経路探索手段は、前記道路種類検出手段によって検出された道路種類に基づいて前記第１分岐点及び前記第２分岐点の前記交通障害地点までの分岐点の数を変更することを特徴とする請求項３乃至請求項５のいずれかに記載のナビゲーション装置。
【請求項７】
前記交通障害が所定距離未満の渋滞であるか否かを判定する渋滞判定手段を有し、
前記第２経路探索手段は前記渋滞判定手段によって所定距離未満の渋滞であると判定された場合に、前記交通障害検出手段によって検出された交通障害地点を含むエリアを前記第１経路探索手段の探索時より道路網の情報量の多い下位レベルの地図データに基づいて再度探索することを特徴とする請求項３乃至請求項６のいずれかに記載のナビゲーション装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２００７−１５５４６２（Ｐ２００７−１５５４６２Ａ）
【公開日】平成１９年６月２１日（２００７．６．２１）
【国際特許分類】
【出願番号】特願２００５−３４９９８５（Ｐ２００５−３４９９８５）
【出願日】平成１７年１２月２日（２００５．１２．２）
【出願人】（０００１００７６８）アイシン・エィ・ダブリュ株式会社 (3,717)
【Ｆターム（参考）】
【公開日】平成１９年６月２１日（２００７．６．２１）
【国際特許分類】
【出願日】平成１７年１２月２日（２００５．１２．２）
【出願人】（０００１００７６８）アイシン・エィ・ダブリュ株式会社 (3,717)
【Ｆターム（参考）】
[ Back to top ]