経路探索装置及び経路探索装置の経路探索に用いられる地図データ
【課題】経路探索処理の処理時間や処理負担を軽減させるとともに、適切な経路探索を行うことを可能とした経路探索装置及び経路探索装置の経路探索に用いられる地図データを提供する。
【解決手段】地図情報ＤＢ３１に記憶される地図データ３２は、後述のように道路網の情報量の差異に基づいて複数レイヤに階層化された構造し、各レイヤは複数の領域（リージョン）に分割されて記憶される。そして、レイヤ３のオーバーラップ領域を削除してレイヤ３のリージョン同士が重複しないようにし、レイヤ２の境界ノードには、レイヤ３の接続先ノードとの接続関係を特定する上位接続データに加えて、境界ノードが接続される接続先ノードを含むレイヤ３のリージョンを対応づけるノード領域対応データ３３についても持たせるように構成する。
【解決手段】地図情報ＤＢ３１に記憶される地図データ３２は、後述のように道路網の情報量の差異に基づいて複数レイヤに階層化された構造し、各レイヤは複数の領域（リージョン）に分割されて記憶される。そして、レイヤ３のオーバーラップ領域を削除してレイヤ３のリージョン同士が重複しないようにし、レイヤ２の境界ノードには、レイヤ３の接続先ノードとの接続関係を特定する上位接続データに加えて、境界ノードが接続される接続先ノードを含むレイヤ３のリージョンを対応づけるノード領域対応データ３３についても持たせるように構成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地から目的地までの経路を探索する経路探索装置及び経路探索装置の経路探索に用いられる地図データに関する。
【背景技術】
【０００２】
近年、車両の走行案内を行い、運転者が所望の目的地に容易に到着できるようにしたナビゲーション装置が車両に搭載されていることが多い。ここで、ナビゲーション装置とは、ＧＰＳ受信機などにより車両の現在位置を検出し、その現在位置に対応する地図データをＤＶＤ−ＲＯＭやＨＤＤなどの記録媒体から取得して液晶モニタに表示することが可能な装置である。そして、車両の現在位置を含む地図データを記録媒体等から読み出し、地図データに基づいて車両の現在位置の周囲における地図画像を描画して表示装置に表示するとともに、車両位置マークを地図画像に重ね合わせて表示し、車両の移動に応じて地図画像をスクロールしたり、地図画像を画面に固定し車両位置マークを移動させることによって、車両が現在どの地点を走行しているのかを一目でわかるようにしている。また、上記ナビゲーション装置では、所望する目的地を設定すると、出発地（例えば自車の現在位置）から設定された目的地までの最適経路を探索する経路探索機能を備えており、更に、探索された経路に従って走行の案内を行う走行案内機能についても備えている。また、近年は携帯電話機、ＰＤＡ（Personal Digital Assistant）、パーソナルコンピュータ等においても上記ナビゲーション装置と同様の機能を有するものがある。
【０００３】
ここで、上記ナビゲーション装置等が記憶する地図データは、道路網の情報量の差異に基づいて複数レイヤに階層化された構造をしている。更に、各レイヤは複数の領域（リージョン）に分割されて記憶されている。例えば、特開２００９−１５６９４０号公報では、地図データをレイヤ１〜３の３層に階層化し、更に各階層において地図データを複数のブロックに分割して記憶することが記載されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００９−１５６９４０号公報（第４頁〜第１１頁、図１）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、上記したように地図データを複数のリージョンに分割する場合においては、リージョンの境界付近を走行する経路を適切に探索する為に、一般的にリージョン同士が重複するオーバーラップ領域を設けている。図１０には、従来において地図データを構成するリージョン２００の一例を示す。図１０に示すようにリージョン２００は、コア領域２０１とコア領域２０１の周囲に形成されたオーバーラップ領域２０２から構成されていた。その結果、図１１に示すようにオーバーラップ領域２０２は、他のリージョン２００のコア領域２０１や他のリージョン２００のオーバーラップ領域２０２と重複することとなり、地図データのデータサイズが必要以上に大きくなっていた。また、探索対象となるリンクやノードの数が増加するので、経路探索処理に係る時間が長時間化し、処理負担も大きくなっていた。
【０００６】
また、地図データを複数のリージョンに分割する場合においては、出発地と目的地の位置関係に基づいて探索対象とするリージョンを予め決定していた。しかしながら、従来のようにオーバーラップ領域を設けることとすると、経路の探索方向（出発地→目的地、又は目的地→出発地）によって異なる経路が探索される場合がある。また、特に２つのＣＰＵにより出発地と目的地の両方から探索を行う場合には、探索時のＣＰＵの状態によって、出発地と目的地が同じでも探索処理を行う度に異なる経路が探索される場合がある。
【０００７】
以下に、図１１を用いて上記問題点についてより詳細に説明する。図１１に示す例では、地点Ｘを出発地とし、地点Ｙを目的地に設定し、リージョンＡとリージョンＢが探索対象に決定された場合の経路の探索例を示す。ここで、図１１に示す例では、地点Ｘと地点Ｙとを結ぶ経路としては、一般道路を通る“下ルート”と、有料道路を通る“上ルート”がある。そして、出発地である地点Ｘ方向から地点Ｙ方向へと探索を行うと、“下ルート”のリージョンＡの境界ノード２０２が接続される先のノード２０３はリージョンＢのコア領域内のノードとなるので、“下ルート”は経路候補の対象となる。また、“上ルート”のリージョンＡの境界ノード２０４が接続される先のノード２０５についてもリージョンＢのコア領域内のノードとなるので、“上ルート”も経路候補の対象となる。従って、出発地である地点Ｘ方向から地点Ｙ方向へと探索を行うと、“上ルート”と“下ルート”の両方が経路候補となり、コスト算出結果に基づいていずれかのルートが案内経路となる。
【０００８】
一方、目的地である地点Ｙ方向から地点Ｘ方向へと探索を行うと、“下ルート”のリージョンＢの境界ノード２１０が接続される先のノード２１１はリージョンＡのコア領域内のノードとなるので、“下ルート”は経路候補の対象となる。しかし、“上ルート”のリージョンＢの境界ノード２１２が接続される先のノード２１３についてはリージョンＡのコア領域内のノードとならない（即ち、探索対象外のリージョンのコア領域内のノードとなる）ので、“上ルート”は経路候補の対象とならない（経路が接続されない）。従って、目的地である地点Ｙ方向から地点Ｘ方向へと探索を行うと、“下ルート”のみが経路候補となり、上記した出発地である地点Ｘ方向から地点Ｙ方向へと探索した場合と異なる案内経路が設定される場合がある。
【０００９】
本発明は前記従来における問題点を解消するためになされたものであり、オーバーラップ領域を削除することにより地図データのデータサイズを減少させ、経路探索処理の処理時間や処理負担を軽減させるとともに、適切な経路探索を行うことを可能とした経路探索装置及び経路探索装置の経路探索に用いられる地図データを提供することを目的とする。
【課題を解決するための手段】
【００１０】
前記目的を達成するため本願の請求項１に係る経路探索装置（１）は、地図データ（３２）を記憶する地図データ記憶媒体（３１）と、前記地図データ記憶媒体に記憶された前記地図データに基づいて、出発地から目的地までの経路を探索する経路探索手段（５１）と、を有する経路探索装置であって、前記地図データ記憶媒体は、前記地図データを複数の領域に区分するとともに、道路網の情報量に基づいて複数のレイヤに階層化して記憶し、前記地図データの領域毎に、該領域と対応する他のレイヤの領域とを関連付けた領域対応情報を記憶し、前記複数のレイヤの内、特定レイヤの前記地図データを各領域が重複する重複エリアが生じないように記憶するとともに、前記特定レイヤ以外のレイヤの前記地図データを各領域が重複する重複エリアが生じるように記憶し、前記特定レイヤ以外のレイヤの前記地図データに含まれるノードの内、前記重複エリアから退出するリンクに接続されたノードである境界ノード（８７、９８）と、該境界ノードが接続されるノードである接続先ノード（８９、９９）を含む前記特定レイヤの領域とを対応付けるノード領域対応情報（３３）を記憶することを特徴とする
【００１１】
また、請求項２に係る経路探索装置（１）は、請求項１に記載の経路探索装置であって、前記特定レイヤは、前記複数のレイヤの内、最も道路網の情報量の少ない最上位レイヤであることを特徴とする。
【００１２】
また、請求項３に係る経路探索装置（１）は、請求項２に記載の経路探索装置であって、前記ノード領域対応情報（３３）は、前記複数のレイヤの内、前記最上位レイヤの次に道路網の情報量が少ない次上位レイヤの前記境界ノード（８７、９８）と、前記接続先ノード（８９、９９）を含む前記最上位レイヤの領域とを対応付けることを特徴とする。
【００１３】
また、請求項４に係る経路探索装置（１）は、請求項１乃至請求項３のいずれかに記載の経路探索装置であって、前記経路探索手段（５１）は、前記出発地側及び前記目的地側から経路の探索を行い、前記出発地側からの探索と前記目的地側からの探索とが重なった場合において、前記出発地側から累積された探索コストと前記目的地側から累積された探索コストとを加算したコスト加算値を算出するコスト算出手段（５２）と、前記コスト算出手段により算出された前記コスト加算値に基づいて、前記出発地から前記目的地までの経路を設定する経路設定手段（５３）と、を備えることを特徴とする。
【００１４】
また、請求項５に係る経路探索装置（１）は、請求項１乃至請求項４のいずれかに記載の経路探索装置であって、前記出発地及び前記目的地に基づいて、前記地図データの内、探索対象とする領域を設定する探索対象領域設定手段（５４）を有し、前記経路探索手段は、前記探索対象領域設定手段によって設定された領域を対象として、前記出発地から前記目的地までの経路を探索することを特徴とする。
【００１５】
更に、請求項６に係る地図データ（３２）は、経路探索装置（１）の経路探索に用いられる地図データであって、複数の領域に区分されるとともに、道路網の情報量に基づいて複数のレイヤに階層化され、前記領域毎に、該領域と対応する他のレイヤの領域とを関連付けた領域対応情報を含み、前記複数のレイヤの内、特定レイヤは各領域が重複する重複エリアが生じることなく、前記特定レイヤ以外のレイヤは前記地図データの各領域が重複する重複エリアが生じ、前記特定レイヤ以外のレイヤに含まれるノードの内、前記重複エリアから退出するリンクに接続されたノードである境界ノード（８７、９８）と、該境界ノードが接続されるノードである接続先ノード（８９、９９）を含む前記特定レイヤの領域とを対応付けるノード領域対応情報（３３）を含むことを特徴とする。
【発明の効果】
【００１６】
前記構成を有する請求項１に係る経路探索装置では、特定レイヤにおいて重複エリアが生じないようにすることにより地図データのデータサイズを減少させ、経路探索処理の処理時間や処理負担を軽減させることが可能となる。また、経路の探索方向や探索時のＣＰＵの状態によって、異なる経路が探索されることを防止できる。また、ノード領域対応情報を記憶させることによって、特定レイヤの重複エリアが生じないようにした場合でも、特定レイヤと特定レイヤ以外のレイヤとの間のノードの接続を適切に行うことが可能となる。
【００１７】
また、請求項２に係る経路探索装置では、特定レイヤを最も道路網の情報量の少ない最上位レイヤとするので、最上位レイヤにおいて重複エリアが生じないように記憶した場合でも、最上位レイヤと下位レイヤとの間のノードの接続を適切に行うことが可能となる。従って、出発地と目的地とが離れた位置にある場合であっても、最上位レイヤを含む複数のレイヤを用いて、経路探索を適切に行うことが可能となる。
【００１８】
また、請求項３に係る経路探索装置では、最上位レイヤと最上位レイヤに連絡するレイヤである次上位レイヤとの間のノードの接続を適切に行うことが可能となる。
【００１９】
また、請求項４に係る経路探索装置では、出発地と目的地の両方から探索を行う場合において、出発地と目的地が同一であっても探索時のＣＰＵの状態によって探索を行う度に異なる経路が探索されることを防止できる。
【００２０】
更に、請求項５に係る経路探索装置では、出発地と目的地に基づいて特定された領域を対象として、出発地から目的地までの経路を探索するので、経路探索の為の演算量を抑えることができる。結果として、ＣＰＵの処理負担が軽減でき、また、経路探索に必要な時間を短縮することができる。
【００２１】
更に、請求項６に係る地図データでは、特定レイヤにおいて重複エリアが生じないようにすることによりデータサイズを減少することができ、該地図データを用いた経路探索処理の処理時間や処理負担を軽減させることが可能となる。また、経路の探索方向や探索時のＣＰＵの状態によって、異なる経路が探索されることを防止できる。また、ノード領域対応情報を含むことによって、特定レイヤの重複エリアが生じないようにした場合でも、特定レイヤと特定レイヤ以外のレイヤとの間のノードの接続を適切に行うことが可能となる。
【図面の簡単な説明】
【００２２】
【図１】本実施形態に係るナビゲーション装置を示したブロック図である。
【図２】ナビゲーションＥＣＵが構成する各種手段を示した図である。
【図３】地図情報ＤＢに記憶される３層に階層化された地図データを示した模式図である。
【図４】レイヤ１〜３の各リージョンの構成を示した図である。
【図５】地図データの構成を示した図である。
【図６】レイヤ１〜３を用いて出発地から目的地までの経路探索を行う場合の経路探索処理を説明した図である。
【図７】レイヤ２とレイヤ３の間のノードの接続関係を比較例と比較して説明した図である。
【図８】レイヤ２とレイヤ３の間のノードの接続関係を比較例と比較して説明した図である。
【図９】本実施形態に係る経路探索処理プログラムのフローチャートである。
【図１０】一般的な地図データを構成する各リージョンについて示した図である。
【図１１】従来の地図データの探索処理について説明した図である。
【発明を実施するための形態】
【００２３】
以下、本発明に係る経路探索装置をナビゲーション装置に具体化した一実施形態に基づき図面を参照しつつ詳細に説明する。先ず、本実施形態に係るナビゲーション装置１の概略構成について図１を用いて説明する。図１は本実施形態に係るナビゲーション装置１を示したブロック図である。
【００２４】
図１に示すように本実施形態に係るナビゲーション装置１は、ナビゲーション装置１が搭載された車両の現在位置を検出する現在位置検出部１１と、各種のデータが記録されたデータ記録部１２と、入力された情報に基づいて、各種の演算処理を行うナビゲーションＥＣＵ１３と、ユーザからの操作を受け付ける操作部１４と、ユーザに対して車両周辺の地図や施設の関する施設情報を表示する液晶ディスプレイ１５と、経路案内に関する音声ガイダンスを出力するスピーカ１６と、記憶媒体であるＤＶＤを読み取るＤＶＤドライブ１７と、プローブセンタやＶＩＣＳ（登録商標：Vehicle Information and Communication System）センタ等の情報センタとの間で通信を行う通信モジュール１８と、から構成されている。
【００２５】
以下に、ナビゲーション装置１を構成する各構成要素について順に説明する。
現在位置検出部１１は、ＧＰＳ２１、車速センサ２２、ステアリングセンサ２３、ジャイロセンサ２４等からなり、現在の車両の位置、方位、車両の走行速度、現在時刻等を検出することが可能となっている。ここで、特に車速センサ２２は、車両の移動距離や車速を検出する為のセンサであり、車両の駆動輪の回転に応じてパルスを発生させ、パルス信号をナビゲーションＥＣＵ１３に出力する。そして、ナビゲーションＥＣＵ１３は発生するパルスを計数することにより駆動輪の回転速度や移動距離を算出する。尚、上記５種類のセンサをナビゲーション装置１が全て備える必要はなく、これらの内の１又は複数種類のセンサのみをナビゲーション装置１が備える構成としても良い。
【００２６】
また、データ記録部１２は、外部記憶装置及び記録媒体としてのハードディスク（図示せず）と、ハードディスクに記録された地図情報ＤＢ３１や所定のプログラム等を読み出すとともにハードディスクに所定のデータを書き込む為のドライバである記録ヘッド（図示せず）とを備えている。尚、データ記録部１２をハードディスクの代わりにメモリーカードやＣＤやＤＶＤ等の光ディスクにより構成しても良い。
【００２７】
ここで、地図情報ＤＢ３１は、経路案内及び地図表示に必要な地図データ３２が記憶された記憶媒体である。また、地図データ３２は、例えば、道路（リンク）に関するリンクデータ、ノード点に関するノードデータ、施設等の地点に関する地点データ、地図を表示するための地図表示データ、各交差点に関する交差点データ、レイヤ間におけるリージョンの親子関係を特定する従属関係データ、経路を探索するための探索データ、地点を検索するための検索データ等から構成されている。また、地図情報ＤＢ３１に記憶される地図データ３２は、後述のように道路網の情報量の差異に基づいて複数レイヤに階層化された構造をしている。更に、各レイヤは複数の領域（リージョン）に分割されて記憶されている。尚、地図データ３２の詳細については後述する。
【００２８】
一方、ナビゲーションＥＣＵ（エレクトロニック・コントロール・ユニット）１３は、ナビゲーション装置１の全体の制御を行う電子制御ユニットであり、演算装置及び制御装置としてのＣＰＵ４１、並びにＣＰＵ４１が各種の演算処理を行うにあたってワーキングメモリとして使用されるとともに、経路が探索されたときの経路データ等が記憶されるＲＡＭ４２、制御用のプログラムのほか、後述の経路探索処理プログラム（図９参照）等が記録されたＲＯＭ４３、ＲＯＭ４３から読み出したプログラムを記憶するフラッシュメモリ４４等の内部記憶装置を備えている。尚、ナビゲーションＥＣＵ１３は、図２に示す処理アルゴリズムとしての各種手段を構成する。例えば、経路探索手段５１は、地図情報ＤＢ３１に記憶された地図データ３２に基づいて、出発地から目的地までの経路を探索する。また、経路探索手段５１は、更に、コスト算出手段５２と経路設定手段５３を備える。コスト算出手段５２は、出発地側及び目的地側から経路の探索を行い、出発地側からの探索と目的地側からの探索とが重なった場合において、出発地側から累積された探索コストと目的地側から累積された探索コストとを加算したコスト加算値を算出し、経路設定手段５３は、コスト算出手段５２により算出されたコスト加算値に基づいて、出発地から目的地までの経路を設定する。また、探索対象領域設定手段５４は、出発地及び目的地に基づいて、地図データの内、探索対象とする領域を設定する。
【００２９】
操作部１４は、走行開始地点としての出発地及び走行終了地点としての目的地を入力する際等に操作され、各種のキー、ボタン等の複数の操作スイッチ（図示せず）から構成される。そして、ナビゲーションＥＣＵ１３は、各スイッチの押下等により出力されるスイッチ信号に基づき、対応する各種の動作を実行すべく制御を行う。尚、操作部１４は液晶ディスプレイ１５の前面に設けたタッチパネルによって構成することもできる。また、マイクと音声認識装置によって構成することもできる。
【００３０】
また、液晶ディスプレイ１５には、道路を含む地図画像、交通情報、操作案内、操作メニュー、キーの案内、出発地から目的地までの走行予定経路、走行予定経路に沿った案内情報、ニュース、天気予報、時刻、メール、テレビ番組等が表示される。
【００３１】
また、スピーカ１６は、ナビゲーションＥＣＵ１３からの指示に基づいて走行予定経路に沿った走行を案内する音声ガイダンスや、交通情報の案内を出力する。
【００３２】
また、ＤＶＤドライブ１７は、ＤＶＤやＣＤ等の記録媒体に記録されたデータを読み取り可能なドライブである。そして、読み取ったデータに基づいて音楽や映像の再生、地図情報ＤＢ３１の更新等が行われる。
【００３３】
また、通信モジュール１８は、交通情報センタ、例えば、ＶＩＣＳセンタやプローブセンタ等から送信された渋滞情報、規制情報、交通事故情報等の各情報から成る交通情報を受信する為の通信装置であり、例えば携帯電話機やＤＣＭが該当する。
【００３４】
次に、地図情報ＤＢ３１に記憶された地図データ３２について説明する。
本実施形態において地図データ３２は、図３に示されるように道路網の情報量に応じて３層のレイヤに階層化されている。図３は地図情報ＤＢ３１に記憶される３層のレイヤに階層化された地図データ３２を示した模式図である。この場合、例えば、レベル１の階層（以下、レイヤ１という）は１０ｋｍ四方のリージョンによって複数に区分された地図データであり、レベル２の階層（以下、レイヤ２という）は２０ｋｍ四方のリージョンによって複数に区分された地図データであり、レベル３の階層（以下、レイヤ３という）は４０ｋｍ四方のリージョンによって複数に区分された地図データである。
そして、下位レベルのレイヤは上位レベルのレイヤより道路網の情報量がより多く含まれており、例えばレイヤ３は高速自動車国道、自動車専用道路、都市高速道路、有料道路に関する情報が格納されている。また、レイヤ２はレイヤ３に含まれる道路網に加えて国道や県道等の主要な一般道路に関する情報が格納されている。また、レイヤ１はレイヤ２に含まれる道路網に加えて細街路等のその他全ての一般道に関する詳細な道路網に関する情報が格納されている。
【００３５】
更に、下位レベルのレイヤでは詳細なデータを有する代わりにカバーする範囲が狭く、上位レベルのレイヤでは粗いデータしか有していない代わりにカバーする範囲が広くなっている。例えば、最下位レベルのレイヤ１では細街路を含む全ての道路の道路データを有するが市町村範囲しかカバーしておらず、最上位レベルのレイヤ３では高速道路や有料道路等の道路の道路データしか有していないが日本全国をカバーする。
【００３６】
尚、各レベルのレイヤにおけるリーションの形状、即ち、各リージョンのカバーする範囲の広さは、適宜決定することができる。また、地図データを構成するレベルの数、即ち、レイヤの階層の数も、必ずしも３層である必要はなく、例えば２層や４層であっても良い。
【００３７】
次に、各レイヤの地図データ３２を構成する各リージョンについて説明する。
図４に示すように、各レイヤの内、最も上位のレイヤ３を除くレイヤを構成する各リージョン６１は、コア領域６２とコア領域６２の周囲に形成されたオーバーラップ領域６３から構成されている。それに対して、最も上位階層のレイヤ３を構成するリージョン６４の地図データ３２Ｃについては、オーバーラップ領域が存在せず、コア領域６５のみから構成されている。即ち、最も上位階層のレイヤ３の地図データは、各リージョンが重複する重複エリアが生じないように記憶され、他のレイヤ１、２の地図データは、各リージョンが重複する重複エリアが生じるように記憶される。
【００３８】
そして、本実施形態に係るナビゲーション装置１では、上記のようにレイヤ３についてオーバーラップ領域を存在しないように構成したことから、従来のように経路の探索方向（出発地→目的地、又は目的地→出発地）によって異なる経路が探索される虞がない。また、特に２つのＣＰＵにより出発地と目的地の両方から探索を行う場合においても、探索時のＣＰＵの状態によって、出発地と目的地が同じでも探索処理を行う度に異なる経路が探索される虞もない（図１１参照）。
【００３９】
以下に、図４を用いて上記従来の問題点の解消についてより詳細に説明する。図４に示す例では、図１１と同様に地点Ｘを出発地とし、地点Ｙを目的地に設定し、リージョンＡとリージョンＢが探索対象に決定された場合の経路の探索例を示す。ここで、図４に示す例では、地点Ｘと地点Ｙとを結ぶ経路としては、一般道路を通る“下ルート”と、有料道路を通る“上ルート”がある。そして、出発地である地点Ｘ方向から地点Ｙ方向へと探索を行うと、“下ルート”のリージョンＡの境界ノード１１０が接続される先のノード１１１はリージョンＢのコア領域内のノードとなるので、“下ルート”は経路候補の対象となる。しかし、“上ルート”のリージョンＡの境界ノード１１０が接続される先のノード１１２についてはリージョンＢのコア領域内のノードとならない（即ち、探索対象外のリージョンのコア領域内のノードとなる）ので、“上ルート”は経路候補の対象とならない（経路が接続されない）。従って、出発地である地点Ｘ方向から地点Ｙ方向へと探索を行うと、“下ルート”のみが経路候補となる。
【００４０】
一方、目的地である地点Ｙ方向から地点Ｘ方向へと探索を行うと、“下ルート”のリージョンＢの境界ノード１１１が接続される先のノード１１０はリージョンＡのコア領域内のノードとなるので、“下ルート”は経路候補の対象となる。しかし、“上ルート”のリージョンＢの境界ノード１１３が接続される先のノード１１４についてはリージョンＡのコア領域内のノードとならない（即ち、探索対象外のリージョンのコア領域内のノードとなる）ので、“上ルート”は経路候補の対象とならない（経路が接続されない）。従って、目的地である地点Ｙ方向から地点Ｘ方向へと探索を行う場合でも、“下ルート”のみが経路候補となり、上記した出発地である地点Ｘ方向から地点Ｙ方向へと探索を行う場合と同じ案内経路が設定されることとなる。
【００４１】
次に、地図データ３２を構成するデータの詳細について説明する。
図５に示すように、地図データ３２は、各レイヤの地図データ３２Ａ〜３２Ｃから構成される。そして、各レイヤの地図データ３２Ａ〜３２Ｃは、上述したように地図表示データ、リンクデータ、ノードデータ、探索データ、従属関係データ、施設データ、交差点データ、検索データ等によってそれぞれ構成されている。図５は本実施形態に係る地図データ３２の構成を示した図である。
【００４２】
ここで、地図表示データとしては、各レイヤの地図データ３２Ａ〜３２Ｃに応じた地図表示を行う為の地図描画情報が記憶される。
【００４３】
また、リンクデータとしては、それぞれのレイヤの地図データ３２Ａ〜３２Ｃにおいて道路を構成する各リンクに関してリンクの属する道路の幅員、勾（こう）配、カント、バンク、路面の状態、道路の車線数、車線数の減少する箇所、幅員の狭くなる箇所、踏切り等を表すデータが、コーナに関して、曲率半径、交差点、Ｔ字路、コーナの入口及び出口等を表すデータが、道路属性に関して、降坂路、登坂路等を表すデータが、道路種別に関して、国道、県道、細街路等の一般道のほか、高速自動車国道、自動車専用道路、都市高速道路、一般有料道路、有料橋等の有料道路を表すデータがそれぞれ記録される。更に、有料道路に関して、有料道路の入口及び出口の取付道（ランプウェイ）、料金所（インターチェンジ）等に関するデータが記録される。
【００４４】
また、ノードデータとしては、それぞれのレイヤの地図データ３２Ａ〜３２Ｃにおいて道路の分岐点（交差点、Ｔ字路等も含む）、各道路に曲率半径等に応じて所定の距離ごとに設定されたノード点の座標（位置）、ノードが交差点に対応するノードであるか等を表すノード属性、ノードに接続するリンクのリンク番号のリストである接続リンク番号リスト、ノードにリンクを介して隣接する他のノードのノード番号のリストである隣接ノード番号リスト、各ノード点の高さ（高度）等に関するデータ等が記録される。
また、ノードデータとしては、階層の異なるレイヤ同士のノード（例えば、レイヤ１のノードとレイヤ２のノード、レイヤ２のノードとレイヤ３のノード）の接続関係を特定する上位接続データについても記憶される。
更に、本実施形態ではノードデータとして、特に“レイヤ２のノードの内の境界ノード”と、“該境界ノードが接続されるノードである接続先ノードを含むレイヤ３のリージョン”とを対応付けるノード領域対応データ３３についても記憶される。尚、ノード領域対応データ３３の詳細については後述する。
【００４５】
また、探索データとしては、それぞれのレイヤの地図データ３２Ａ〜３２Ｃにおいて設定された目的地までの経路を探索及び表示する際に使用されるデータについて記録されており、ノードを通過する際のコスト（以下、ノードコストという）や道路を構成するリンクのコスト（以下、リンクコストという）からなる探索コストを算出する為に使用するコストデータ、リンクを通過するのに必要な旅行時間、経路探索により選択された経路を液晶ディスプレイ１５の地図上に表示するための経路表示データ等から構成されている。
ここで、ノードコストは、交差点に対応するノードに対して基本的に設定されており、例えば、信号の有無や交差点を通過する際の自車の走行経路（即ち直進、右折及び左折の種類）によってその値が決定される。
また、リンクコストは、リンクを構成する道路属性や道路種別、道路幅、車線数、リンク長さに加え、ＶＩＣＳ情報として取得する渋滞度等の交通情報に関するデータを用いて算出される。
【００４６】
また、施設データとしては、各地域のホテル、病院、ガソリンスタンド、駐車場、観光施設、インターチェンジ、レストラン、サービスエリア等の建物に関するデータが建物を特定する施設ＩＤとともに記録される。
【００４７】
また、従属関係データとしては、各レイヤを構成する各リージョンについて、レイヤ間のリージョンの親子関係を特定するデータが記憶される。具体的には、レイヤ３のリージョンと、該リージョン内に含まれるレイヤ２のリージョンとを対応づけたデータと、レイヤ２のリージョンと、該リージョン内に含まれるレイヤ１のリージョンとを対応づけたデータとが記憶される。
【００４８】
そして、ナビゲーション装置１は、出発地と目的地付近の地域では、出発地から目的地までの距離が短距離（例えば、３ｋｍ程度）の経路探索の場合には、現在地周辺の最下層の地図データであるレイヤ１の地図データのみを使用して経路を探索する。
また、現在地から目的地までの距離が中距離（例えば、５０ｋｍ程度）の経路探索の場合には、現在地及び目的地周辺については最下層の地図データであるレイヤ１の地図データのリージョンを使用し、使用されたレイヤ１の地図データのリージョンに隣接するエリアは中間層の地図データであるレイヤ２の地図データのリージョンを使用して経路を探索する。
更に、現在地から目的地までの距離が長距離（例えば、３００ｋｍ程度）の経路探索の場合には、現在地及び目的地周辺の最下層の地図データであるレイヤ１の地図データのリージョンを使用し、使用されたレイヤ１の地図データのリージョンに隣接するエリアは中間層の地図データであるレイヤ２の地図データのリージョンを使用し、使用されたレイヤ２の地図データのリージョンに隣接するエリアは最上層の地図データであるレイヤ３の地図データのリージョンを使用して経路を探索する。また、特にレイヤ３については出発地と目的地の位置座標に基づいて、予め探索対象とするリージョンが設定される。
以上により、経路を探索の為の演算量を抑えることができ、経路探索に必要な時間を短縮することができる。
【００４９】
また、上記中距離や長距離等の複数のレイヤを跨ぐ探索を行う場合には、図６に示すように、下位階層を構成するリージョン内での探索において、そのリージョンの境界ノード７１まで達すると、その境界ノード７１が含まれる上位階層のリージョンのノード（接続先ノード）７２に上げて探索が続けられる。従って、図６に示す例では出発地７３と目的地７４を含むレイヤ１のリージョンと、レイヤ１の境界ノード７１と接続されるレイヤ２の接続先ノード７２を含むリージョンと、探索対象に設定されるレイヤ３のリージョン内で経路の探索が行われる。尚、境界ノード７１は、レイヤ１とレイヤ２については、オーバーラップ領域６３から退出するリンクの外側に接続されたノードとなる。一方、レイヤ３については、コア領域６５から退出するリンクの内側に接続されたノードとなる。
【００５０】
そして、本実施形態では、上述したようにレイヤ３の地図データはオーバーラップ領域が存在せず、コア領域６５のみから構成される。従って、レイヤ２の境界ノード７１からレイヤ３の接続先ノード７２への連絡には、レイヤ２の境界ノード７１にノード領域対応データ３３を持たせる必要がある。
以下に、その理由について説明する。
図７及び図８は、レイヤ３の地図データにオーバーラップ領域を含めた比較例と、レイヤ３の地図データからオーバーラップ領域を削除した実施例についてそれぞれ示した図である。
【００５１】
図７の比較例では、レイヤ２のリージョン８１の親関係にあるレイヤ３のリージョン８２（リージョン８１を含むレイヤ３のリージョン）に、リージョン８１の境界ノード８３と同じノードを含む。従って、レイヤ２の境界ノード８３からレイヤ３の接続先ノード８４への連絡を行う際に、接続先ノード８４を含むレイヤ３のリージョンが親関係にあるリージョン８２となる。ここで、前記したようにレイヤ間のリージョンの親子関係を特定する従属関係データは地図データ３２に含まれているので、レイヤ２の境界ノード８３に“境界ノード８３が接続される接続先ノード８４を含むレイヤ３のリージョン”を対応づけるノード領域対応データ３３を持たせる必要は無い。
【００５２】
一方、図７の実施例では、レイヤ２のリージョン８５の親関係にあるレイヤ３のリージョン８６（リージョン８５を含むレイヤ３のリージョン）には、リージョン８５の境界ノード８７と同じノードを含まず、隣接する他のリージョン８８にリージョン８５の境界ノード８７と同じノードを含む。従って、レイヤ２の境界ノード８７からレイヤ３の接続先ノード８９への連絡を行う際に、接続先ノード８９を含むレイヤ３のリージョンは親関係にないリージョン８８となる。従って、レイヤ２の境界ノード８７には、接続先ノード８９との接続関係を特定する上位接続データに加えて“境界ノード８７が接続される接続先ノード８９を含むレイヤ３のリージョン８８”を対応づけるノード領域対応データ３３を持たせる必要がある。
また、前記したようにレイヤ３のオーバーラップ領域を削除した実施例では、レイヤ３の境界ノードはコア領域から退出するリンクの内側に接続されたノードとなるので、経路探索中にレイヤ２の境界ノードからレイヤ３の接続先ノードへと連絡する際に、探索経路が探索方向（例えば、目的地から出発地方向）と逆方向側に戻り、経路が重複する可能性がある。ノード領域対応データ３３を境界ノード８７に持たせることによって、このような経路の重複についても防止することが可能となる。
【００５３】
一方、図８の比較例では、レイヤ２のリージョン９１の親関係にあるレイヤ３のリージョン９２（リージョン９１を含むレイヤ３のリージョン）に、リージョン９１の境界ノード９３の接続先となる接続先ノード９４は含まないが、接続先ノード９４と接続されるノード９５は必ず含む。従って、レイヤ２の境界ノード９３からレイヤ３の接続先ノード９４への連絡を行う際に、接続先ノード９４に接続されるノード９５を含むレイヤ３のリージョンが親関係にあるリージョン９２となる。ここで、前記したようにレイヤ間のリージョンの親子関係を特定する従属関係データは地図データ３２に含まれ、且つノード９５と接続先ノード９４の接続関係もノードデータとして記憶されているので、レイヤ２の境界ノード９３に“境界ノード９３が接続される接続先ノード９４を含むレイヤ３のリージョン”を対応づけるノード領域対応データ３３を持たせる必要は無い。
【００５４】
一方、図８の実施例では、レイヤ２のリージョン９６の親関係にあるレイヤ３のリージョン９７（リージョン９６を含むレイヤ３のリージョン）には、リージョン９６の境界ノード９８の接続先となる接続先ノード９９は含まず、接続先ノード９９と接続されるノード１００も含まない場合がある。従って、レイヤ２の境界ノード９８からレイヤ３の接続先ノード９９への連絡を行う際に、接続先ノード９９やノード１００を含むレイヤ３のリージョンは親関係にないリージョン１０１となる。従って、レイヤ２の境界ノード９８には、接続先ノード９９との接続関係を特定する上位接続データに加えて“境界ノード９８が接続される接続先ノード９９を含むレイヤ３のリージョン１０１”を対応づけるノード領域対応データ３３を持たせる必要がある。
また、前記したようにレイヤ３のオーバーラップ領域を削除した実施例では、レイヤ３の境界ノードはコア領域から退出するリンクの内側に接続されたノードとなるので、経路探索中にレイヤ２の境界ノードからレイヤ３の接続先ノードへと連絡する際に、探索経路が探索方向（例えば、目的地から出発地方向）と逆方向側に戻り、経路が重複する可能性がある。ノード領域対応データ３３を境界ノード９８に持たせることによって、このような経路の重複についても防止することが可能となる。
【００５５】
そして、ナビゲーションＥＣＵ１３が経路を探索する際には、地図データにおける探索データ中の道路データを調査して、探索に使用されるメッシュに含まれる道路（リンク及びノード）についての探索コスト（ノードコスト及びリンクコスト）を計算して、経路を探索する。一般的には、目的地側から経路の探索が行われ、目的地側から出発地まで累積された探索コストを加算した値、即ち、コスト加算値が算出される。そして、探索条件（有料道優先、一般道優先、距離優先等）を変更し、各条件で最もコスト加算値が小さくなった経路をそれぞれ案内する。そして、ユーザによって選択された経路を誘導経路として設定する。また、２つのＣＰＵにより出発地と目的地の両方から探索を行う探索方法を用いた場合には、出発地側及び目的地側から経路の探索が行われ、出発地側からの探索と目的地側からの探索とが重なった場合において、出発地側から累積された探索コストと目的地側から累積された探索コストとを加算した値、即ち、コスト加算値が算出される。
【００５６】
続いて、前記構成を有するナビゲーション装置１においてＣＰＵ４１が実行する経路探索処理プログラムについて図９に基づき説明する。図９は本実施形態に係る経路探索処理プログラムのフローチャートである。ここで、経路探索処理プログラムはナビゲーション装置１において経路探索を行う為の所定の操作（例えば、目的地の設定操作）を受け付けた際に実行され、出発地から目的地までの経路を探索するプログラムである。尚、以下の図９にフローチャートで示されるプログラムは、ナビゲーション装置１が備えているＲＡＭ４２やＲＯＭ４３に記憶されており、ＣＰＵ４１により実行される。
【００５７】
先ず、経路探索処理プログラムではステップ（以下、Ｓと略記する）１において、ＣＰＵ４１は、受け付けたユーザの操作に基づいて出発地及び目的地を設定する。尚、出発地については車両の現在位置としても良い。
【００５８】
次に、Ｓ２においてＣＰＵ４１は、前記Ｓ１で設定された出発地と目的地に基づいて、探索対象とするレイヤ３のリージョンが設定される。具体的には、予め出発地及び目的地の位置座標と、検索対象とするリージョンとの対応関係を示すテーブルをＲＡＭ４２等に記憶させておき、前記Ｓ１で設定された出発地及び目的地の位置座標とテーブルとに基づいて、検索対象とするリージョンを特定することにより行う。
【００５９】
続いて、Ｓ３においてＣＰＵ４１は、前記Ｓ１で設定された出発地から目的地までの経路の探索処理を行う。尚、レイヤ３については前記Ｓ２で設定されたリージョンのみを対象として経路探索が行われる。そして、複数の探索条件（有料道優先、一般道優先、距離優先等）でそれぞれコスト加算値の算出を行い、各条件で最もコスト加算値が小さくなった経路をそれぞれ案内する。例えば、液晶ディスプレイ１５上に探索条件とともに経路の全体図を表示する。尚、一の探索条件だけを用い、最もコスト加算値が小さくなった一の経路のみを案内する構成としても良い。また、経路探索処理の詳細については既に説明したので省略する。
【００６０】
その後、Ｓ４でＣＰＵ４１は、前記Ｓ３で案内された経路の内、ユーザの操作等に基づいて選択された経路を案内経路に設定する。
【００６１】
そして、Ｓ５においてＣＰＵ４１は、設定された案内経路に従って液晶ディスプレイ１５やスピーカ１６を用いて走行の案内を行う。
【００６２】
以上詳細に説明した通り、本実施形態に係るナビゲーション装置１では、地図情報ＤＢ３１に記憶される地図データ３２は、後述のように道路網の情報量の差異に基づいて複数レイヤに階層化された構造し、各レイヤは複数の領域（リージョン）に分割されて記憶される。そして、レイヤ３のオーバーラップ領域を削除してレイヤ３のリージョン同士が重複しないようにし、レイヤ２の境界ノードには、レイヤ３の接続先ノードとの接続関係を特定する上位接続データに加えて、境界ノードが接続される接続先ノードを含むレイヤ３のリージョンを対応づけるノード領域対応データ３３についても持たせるように構成するので、地図データのデータサイズを減少させ、経路探索処理の処理時間や処理負担を軽減させることが可能となる。また、経路の探索方向や探索時のＣＰＵの状態によって、異なる経路が探索されることを防止できる。また、ノード領域対応データ３３を記憶させることによって、レイヤ３のオーバーラップ領域を削除した場合でも、レイヤ３とレイヤ２との間のノードの接続を適切に行うことが可能となる。
また、オーバーラップ領域を削除するレイヤは、最も道路網の情報量の少ない最上位のレイヤ３とする。従って、レイヤ３においてオーバーラップ領域を削除した場合でも、レイヤ３とレイヤ３に連絡するレイヤ２との間のノードの接続を適切に行うことが可能となる。従って、出発地と目的地とが離れた位置にある場合であっても、レイヤ３を含む複数のレイヤを用いて、経路探索を適切に行うことが可能となる。
また、特に２つのＣＰＵにより出発地と目的地の両方から探索を行う場合には、出発地と目的地が同一であっても探索時のＣＰＵの状態によって探索を行う度に異なる経路が探索されることを防止できる。
出発地と目的地に基づいて特定された領域を対象として、出発地から目的地までの経路を探索するので、経路探索の為の演算量を抑えることができる。結果として、ＣＰＵの処理負担が軽減でき、また、経路探索に必要な時間を短縮することができる。
【００６３】
尚、本発明は前記実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の改良、変形が可能であることは勿論である。
例えば、本実施形態では、オーバーラップ領域を削除するレイヤを最も道路網の情報量の少ない最上位のレイヤ３としているが、レイヤ３以外のレイヤについてオーバーラップ領域を削除しても良い。また、オーバーラップ領域を削除する対象とするレイヤは、複数層でも良い。
【００６４】
また、レイヤの階層の数も、必ずしも３層である必要はなく、例えば２層や４層であっても良い。更に、地域毎にレイヤの階層の数が異なるようにしても良い。更に、各レイヤのリーションの形状（コア領域やオーバーラップ領域の形状）は適宜変更することが可能である、
【００６５】
また、境界ノードは、レイヤ１とレイヤ２については、オーバーラップ領域から退出するリンクの外側に接続されたノードとし、レイヤ３については、コア領域から退出するリンクの内側に接続されたノードとしているが、他のノードを境界ノードとしても良い。例えば、レイヤ１とレイヤ２については、オーバーラップ領域から退出するリンクの外側に接続されたノードに、更に一また複数のリンクを介して接続されたノードを境界ノードとしても良い。
【００６６】
また、本実施形態では本願発明をナビゲーション装置１に適用した例について説明したが、経路探索機能を有する装置であれば、携帯電話機等の携帯端末やパーソナルコンピュータ等に適用することも可能である。
【符号の説明】
【００６７】
１ ナビゲーション装置
１３ ナビゲーションＥＣＵ
３１ 地図情報ＤＢ
３２ 地図データ
３３ ノード領域対応データ
４１ ＣＰＵ
４２ ＲＡＭ
４３ ＲＯＭ
７１、８３、８７、９３、９８ 境界ノード
７２、８４、８９、９４、９９ 接続先ノード
【技術分野】
【０００１】
本発明は、出発地から目的地までの経路を探索する経路探索装置及び経路探索装置の経路探索に用いられる地図データに関する。
【背景技術】
【０００２】
近年、車両の走行案内を行い、運転者が所望の目的地に容易に到着できるようにしたナビゲーション装置が車両に搭載されていることが多い。ここで、ナビゲーション装置とは、ＧＰＳ受信機などにより車両の現在位置を検出し、その現在位置に対応する地図データをＤＶＤ−ＲＯＭやＨＤＤなどの記録媒体から取得して液晶モニタに表示することが可能な装置である。そして、車両の現在位置を含む地図データを記録媒体等から読み出し、地図データに基づいて車両の現在位置の周囲における地図画像を描画して表示装置に表示するとともに、車両位置マークを地図画像に重ね合わせて表示し、車両の移動に応じて地図画像をスクロールしたり、地図画像を画面に固定し車両位置マークを移動させることによって、車両が現在どの地点を走行しているのかを一目でわかるようにしている。また、上記ナビゲーション装置では、所望する目的地を設定すると、出発地（例えば自車の現在位置）から設定された目的地までの最適経路を探索する経路探索機能を備えており、更に、探索された経路に従って走行の案内を行う走行案内機能についても備えている。また、近年は携帯電話機、ＰＤＡ（Personal Digital Assistant）、パーソナルコンピュータ等においても上記ナビゲーション装置と同様の機能を有するものがある。
【０００３】
ここで、上記ナビゲーション装置等が記憶する地図データは、道路網の情報量の差異に基づいて複数レイヤに階層化された構造をしている。更に、各レイヤは複数の領域（リージョン）に分割されて記憶されている。例えば、特開２００９−１５６９４０号公報では、地図データをレイヤ１〜３の３層に階層化し、更に各階層において地図データを複数のブロックに分割して記憶することが記載されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００９−１５６９４０号公報（第４頁〜第１１頁、図１）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、上記したように地図データを複数のリージョンに分割する場合においては、リージョンの境界付近を走行する経路を適切に探索する為に、一般的にリージョン同士が重複するオーバーラップ領域を設けている。図１０には、従来において地図データを構成するリージョン２００の一例を示す。図１０に示すようにリージョン２００は、コア領域２０１とコア領域２０１の周囲に形成されたオーバーラップ領域２０２から構成されていた。その結果、図１１に示すようにオーバーラップ領域２０２は、他のリージョン２００のコア領域２０１や他のリージョン２００のオーバーラップ領域２０２と重複することとなり、地図データのデータサイズが必要以上に大きくなっていた。また、探索対象となるリンクやノードの数が増加するので、経路探索処理に係る時間が長時間化し、処理負担も大きくなっていた。
【０００６】
また、地図データを複数のリージョンに分割する場合においては、出発地と目的地の位置関係に基づいて探索対象とするリージョンを予め決定していた。しかしながら、従来のようにオーバーラップ領域を設けることとすると、経路の探索方向（出発地→目的地、又は目的地→出発地）によって異なる経路が探索される場合がある。また、特に２つのＣＰＵにより出発地と目的地の両方から探索を行う場合には、探索時のＣＰＵの状態によって、出発地と目的地が同じでも探索処理を行う度に異なる経路が探索される場合がある。
【０００７】
以下に、図１１を用いて上記問題点についてより詳細に説明する。図１１に示す例では、地点Ｘを出発地とし、地点Ｙを目的地に設定し、リージョンＡとリージョンＢが探索対象に決定された場合の経路の探索例を示す。ここで、図１１に示す例では、地点Ｘと地点Ｙとを結ぶ経路としては、一般道路を通る“下ルート”と、有料道路を通る“上ルート”がある。そして、出発地である地点Ｘ方向から地点Ｙ方向へと探索を行うと、“下ルート”のリージョンＡの境界ノード２０２が接続される先のノード２０３はリージョンＢのコア領域内のノードとなるので、“下ルート”は経路候補の対象となる。また、“上ルート”のリージョンＡの境界ノード２０４が接続される先のノード２０５についてもリージョンＢのコア領域内のノードとなるので、“上ルート”も経路候補の対象となる。従って、出発地である地点Ｘ方向から地点Ｙ方向へと探索を行うと、“上ルート”と“下ルート”の両方が経路候補となり、コスト算出結果に基づいていずれかのルートが案内経路となる。
【０００８】
一方、目的地である地点Ｙ方向から地点Ｘ方向へと探索を行うと、“下ルート”のリージョンＢの境界ノード２１０が接続される先のノード２１１はリージョンＡのコア領域内のノードとなるので、“下ルート”は経路候補の対象となる。しかし、“上ルート”のリージョンＢの境界ノード２１２が接続される先のノード２１３についてはリージョンＡのコア領域内のノードとならない（即ち、探索対象外のリージョンのコア領域内のノードとなる）ので、“上ルート”は経路候補の対象とならない（経路が接続されない）。従って、目的地である地点Ｙ方向から地点Ｘ方向へと探索を行うと、“下ルート”のみが経路候補となり、上記した出発地である地点Ｘ方向から地点Ｙ方向へと探索した場合と異なる案内経路が設定される場合がある。
【０００９】
本発明は前記従来における問題点を解消するためになされたものであり、オーバーラップ領域を削除することにより地図データのデータサイズを減少させ、経路探索処理の処理時間や処理負担を軽減させるとともに、適切な経路探索を行うことを可能とした経路探索装置及び経路探索装置の経路探索に用いられる地図データを提供することを目的とする。
【課題を解決するための手段】
【００１０】
前記目的を達成するため本願の請求項１に係る経路探索装置（１）は、地図データ（３２）を記憶する地図データ記憶媒体（３１）と、前記地図データ記憶媒体に記憶された前記地図データに基づいて、出発地から目的地までの経路を探索する経路探索手段（５１）と、を有する経路探索装置であって、前記地図データ記憶媒体は、前記地図データを複数の領域に区分するとともに、道路網の情報量に基づいて複数のレイヤに階層化して記憶し、前記地図データの領域毎に、該領域と対応する他のレイヤの領域とを関連付けた領域対応情報を記憶し、前記複数のレイヤの内、特定レイヤの前記地図データを各領域が重複する重複エリアが生じないように記憶するとともに、前記特定レイヤ以外のレイヤの前記地図データを各領域が重複する重複エリアが生じるように記憶し、前記特定レイヤ以外のレイヤの前記地図データに含まれるノードの内、前記重複エリアから退出するリンクに接続されたノードである境界ノード（８７、９８）と、該境界ノードが接続されるノードである接続先ノード（８９、９９）を含む前記特定レイヤの領域とを対応付けるノード領域対応情報（３３）を記憶することを特徴とする
【００１１】
また、請求項２に係る経路探索装置（１）は、請求項１に記載の経路探索装置であって、前記特定レイヤは、前記複数のレイヤの内、最も道路網の情報量の少ない最上位レイヤであることを特徴とする。
【００１２】
また、請求項３に係る経路探索装置（１）は、請求項２に記載の経路探索装置であって、前記ノード領域対応情報（３３）は、前記複数のレイヤの内、前記最上位レイヤの次に道路網の情報量が少ない次上位レイヤの前記境界ノード（８７、９８）と、前記接続先ノード（８９、９９）を含む前記最上位レイヤの領域とを対応付けることを特徴とする。
【００１３】
また、請求項４に係る経路探索装置（１）は、請求項１乃至請求項３のいずれかに記載の経路探索装置であって、前記経路探索手段（５１）は、前記出発地側及び前記目的地側から経路の探索を行い、前記出発地側からの探索と前記目的地側からの探索とが重なった場合において、前記出発地側から累積された探索コストと前記目的地側から累積された探索コストとを加算したコスト加算値を算出するコスト算出手段（５２）と、前記コスト算出手段により算出された前記コスト加算値に基づいて、前記出発地から前記目的地までの経路を設定する経路設定手段（５３）と、を備えることを特徴とする。
【００１４】
また、請求項５に係る経路探索装置（１）は、請求項１乃至請求項４のいずれかに記載の経路探索装置であって、前記出発地及び前記目的地に基づいて、前記地図データの内、探索対象とする領域を設定する探索対象領域設定手段（５４）を有し、前記経路探索手段は、前記探索対象領域設定手段によって設定された領域を対象として、前記出発地から前記目的地までの経路を探索することを特徴とする。
【００１５】
更に、請求項６に係る地図データ（３２）は、経路探索装置（１）の経路探索に用いられる地図データであって、複数の領域に区分されるとともに、道路網の情報量に基づいて複数のレイヤに階層化され、前記領域毎に、該領域と対応する他のレイヤの領域とを関連付けた領域対応情報を含み、前記複数のレイヤの内、特定レイヤは各領域が重複する重複エリアが生じることなく、前記特定レイヤ以外のレイヤは前記地図データの各領域が重複する重複エリアが生じ、前記特定レイヤ以外のレイヤに含まれるノードの内、前記重複エリアから退出するリンクに接続されたノードである境界ノード（８７、９８）と、該境界ノードが接続されるノードである接続先ノード（８９、９９）を含む前記特定レイヤの領域とを対応付けるノード領域対応情報（３３）を含むことを特徴とする。
【発明の効果】
【００１６】
前記構成を有する請求項１に係る経路探索装置では、特定レイヤにおいて重複エリアが生じないようにすることにより地図データのデータサイズを減少させ、経路探索処理の処理時間や処理負担を軽減させることが可能となる。また、経路の探索方向や探索時のＣＰＵの状態によって、異なる経路が探索されることを防止できる。また、ノード領域対応情報を記憶させることによって、特定レイヤの重複エリアが生じないようにした場合でも、特定レイヤと特定レイヤ以外のレイヤとの間のノードの接続を適切に行うことが可能となる。
【００１７】
また、請求項２に係る経路探索装置では、特定レイヤを最も道路網の情報量の少ない最上位レイヤとするので、最上位レイヤにおいて重複エリアが生じないように記憶した場合でも、最上位レイヤと下位レイヤとの間のノードの接続を適切に行うことが可能となる。従って、出発地と目的地とが離れた位置にある場合であっても、最上位レイヤを含む複数のレイヤを用いて、経路探索を適切に行うことが可能となる。
【００１８】
また、請求項３に係る経路探索装置では、最上位レイヤと最上位レイヤに連絡するレイヤである次上位レイヤとの間のノードの接続を適切に行うことが可能となる。
【００１９】
また、請求項４に係る経路探索装置では、出発地と目的地の両方から探索を行う場合において、出発地と目的地が同一であっても探索時のＣＰＵの状態によって探索を行う度に異なる経路が探索されることを防止できる。
【００２０】
更に、請求項５に係る経路探索装置では、出発地と目的地に基づいて特定された領域を対象として、出発地から目的地までの経路を探索するので、経路探索の為の演算量を抑えることができる。結果として、ＣＰＵの処理負担が軽減でき、また、経路探索に必要な時間を短縮することができる。
【００２１】
更に、請求項６に係る地図データでは、特定レイヤにおいて重複エリアが生じないようにすることによりデータサイズを減少することができ、該地図データを用いた経路探索処理の処理時間や処理負担を軽減させることが可能となる。また、経路の探索方向や探索時のＣＰＵの状態によって、異なる経路が探索されることを防止できる。また、ノード領域対応情報を含むことによって、特定レイヤの重複エリアが生じないようにした場合でも、特定レイヤと特定レイヤ以外のレイヤとの間のノードの接続を適切に行うことが可能となる。
【図面の簡単な説明】
【００２２】
【図１】本実施形態に係るナビゲーション装置を示したブロック図である。
【図２】ナビゲーションＥＣＵが構成する各種手段を示した図である。
【図３】地図情報ＤＢに記憶される３層に階層化された地図データを示した模式図である。
【図４】レイヤ１〜３の各リージョンの構成を示した図である。
【図５】地図データの構成を示した図である。
【図６】レイヤ１〜３を用いて出発地から目的地までの経路探索を行う場合の経路探索処理を説明した図である。
【図７】レイヤ２とレイヤ３の間のノードの接続関係を比較例と比較して説明した図である。
【図８】レイヤ２とレイヤ３の間のノードの接続関係を比較例と比較して説明した図である。
【図９】本実施形態に係る経路探索処理プログラムのフローチャートである。
【図１０】一般的な地図データを構成する各リージョンについて示した図である。
【図１１】従来の地図データの探索処理について説明した図である。
【発明を実施するための形態】
【００２３】
以下、本発明に係る経路探索装置をナビゲーション装置に具体化した一実施形態に基づき図面を参照しつつ詳細に説明する。先ず、本実施形態に係るナビゲーション装置１の概略構成について図１を用いて説明する。図１は本実施形態に係るナビゲーション装置１を示したブロック図である。
【００２４】
図１に示すように本実施形態に係るナビゲーション装置１は、ナビゲーション装置１が搭載された車両の現在位置を検出する現在位置検出部１１と、各種のデータが記録されたデータ記録部１２と、入力された情報に基づいて、各種の演算処理を行うナビゲーションＥＣＵ１３と、ユーザからの操作を受け付ける操作部１４と、ユーザに対して車両周辺の地図や施設の関する施設情報を表示する液晶ディスプレイ１５と、経路案内に関する音声ガイダンスを出力するスピーカ１６と、記憶媒体であるＤＶＤを読み取るＤＶＤドライブ１７と、プローブセンタやＶＩＣＳ（登録商標：Vehicle Information and Communication System）センタ等の情報センタとの間で通信を行う通信モジュール１８と、から構成されている。
【００２５】
以下に、ナビゲーション装置１を構成する各構成要素について順に説明する。
現在位置検出部１１は、ＧＰＳ２１、車速センサ２２、ステアリングセンサ２３、ジャイロセンサ２４等からなり、現在の車両の位置、方位、車両の走行速度、現在時刻等を検出することが可能となっている。ここで、特に車速センサ２２は、車両の移動距離や車速を検出する為のセンサであり、車両の駆動輪の回転に応じてパルスを発生させ、パルス信号をナビゲーションＥＣＵ１３に出力する。そして、ナビゲーションＥＣＵ１３は発生するパルスを計数することにより駆動輪の回転速度や移動距離を算出する。尚、上記５種類のセンサをナビゲーション装置１が全て備える必要はなく、これらの内の１又は複数種類のセンサのみをナビゲーション装置１が備える構成としても良い。
【００２６】
また、データ記録部１２は、外部記憶装置及び記録媒体としてのハードディスク（図示せず）と、ハードディスクに記録された地図情報ＤＢ３１や所定のプログラム等を読み出すとともにハードディスクに所定のデータを書き込む為のドライバである記録ヘッド（図示せず）とを備えている。尚、データ記録部１２をハードディスクの代わりにメモリーカードやＣＤやＤＶＤ等の光ディスクにより構成しても良い。
【００２７】
ここで、地図情報ＤＢ３１は、経路案内及び地図表示に必要な地図データ３２が記憶された記憶媒体である。また、地図データ３２は、例えば、道路（リンク）に関するリンクデータ、ノード点に関するノードデータ、施設等の地点に関する地点データ、地図を表示するための地図表示データ、各交差点に関する交差点データ、レイヤ間におけるリージョンの親子関係を特定する従属関係データ、経路を探索するための探索データ、地点を検索するための検索データ等から構成されている。また、地図情報ＤＢ３１に記憶される地図データ３２は、後述のように道路網の情報量の差異に基づいて複数レイヤに階層化された構造をしている。更に、各レイヤは複数の領域（リージョン）に分割されて記憶されている。尚、地図データ３２の詳細については後述する。
【００２８】
一方、ナビゲーションＥＣＵ（エレクトロニック・コントロール・ユニット）１３は、ナビゲーション装置１の全体の制御を行う電子制御ユニットであり、演算装置及び制御装置としてのＣＰＵ４１、並びにＣＰＵ４１が各種の演算処理を行うにあたってワーキングメモリとして使用されるとともに、経路が探索されたときの経路データ等が記憶されるＲＡＭ４２、制御用のプログラムのほか、後述の経路探索処理プログラム（図９参照）等が記録されたＲＯＭ４３、ＲＯＭ４３から読み出したプログラムを記憶するフラッシュメモリ４４等の内部記憶装置を備えている。尚、ナビゲーションＥＣＵ１３は、図２に示す処理アルゴリズムとしての各種手段を構成する。例えば、経路探索手段５１は、地図情報ＤＢ３１に記憶された地図データ３２に基づいて、出発地から目的地までの経路を探索する。また、経路探索手段５１は、更に、コスト算出手段５２と経路設定手段５３を備える。コスト算出手段５２は、出発地側及び目的地側から経路の探索を行い、出発地側からの探索と目的地側からの探索とが重なった場合において、出発地側から累積された探索コストと目的地側から累積された探索コストとを加算したコスト加算値を算出し、経路設定手段５３は、コスト算出手段５２により算出されたコスト加算値に基づいて、出発地から目的地までの経路を設定する。また、探索対象領域設定手段５４は、出発地及び目的地に基づいて、地図データの内、探索対象とする領域を設定する。
【００２９】
操作部１４は、走行開始地点としての出発地及び走行終了地点としての目的地を入力する際等に操作され、各種のキー、ボタン等の複数の操作スイッチ（図示せず）から構成される。そして、ナビゲーションＥＣＵ１３は、各スイッチの押下等により出力されるスイッチ信号に基づき、対応する各種の動作を実行すべく制御を行う。尚、操作部１４は液晶ディスプレイ１５の前面に設けたタッチパネルによって構成することもできる。また、マイクと音声認識装置によって構成することもできる。
【００３０】
また、液晶ディスプレイ１５には、道路を含む地図画像、交通情報、操作案内、操作メニュー、キーの案内、出発地から目的地までの走行予定経路、走行予定経路に沿った案内情報、ニュース、天気予報、時刻、メール、テレビ番組等が表示される。
【００３１】
また、スピーカ１６は、ナビゲーションＥＣＵ１３からの指示に基づいて走行予定経路に沿った走行を案内する音声ガイダンスや、交通情報の案内を出力する。
【００３２】
また、ＤＶＤドライブ１７は、ＤＶＤやＣＤ等の記録媒体に記録されたデータを読み取り可能なドライブである。そして、読み取ったデータに基づいて音楽や映像の再生、地図情報ＤＢ３１の更新等が行われる。
【００３３】
また、通信モジュール１８は、交通情報センタ、例えば、ＶＩＣＳセンタやプローブセンタ等から送信された渋滞情報、規制情報、交通事故情報等の各情報から成る交通情報を受信する為の通信装置であり、例えば携帯電話機やＤＣＭが該当する。
【００３４】
次に、地図情報ＤＢ３１に記憶された地図データ３２について説明する。
本実施形態において地図データ３２は、図３に示されるように道路網の情報量に応じて３層のレイヤに階層化されている。図３は地図情報ＤＢ３１に記憶される３層のレイヤに階層化された地図データ３２を示した模式図である。この場合、例えば、レベル１の階層（以下、レイヤ１という）は１０ｋｍ四方のリージョンによって複数に区分された地図データであり、レベル２の階層（以下、レイヤ２という）は２０ｋｍ四方のリージョンによって複数に区分された地図データであり、レベル３の階層（以下、レイヤ３という）は４０ｋｍ四方のリージョンによって複数に区分された地図データである。
そして、下位レベルのレイヤは上位レベルのレイヤより道路網の情報量がより多く含まれており、例えばレイヤ３は高速自動車国道、自動車専用道路、都市高速道路、有料道路に関する情報が格納されている。また、レイヤ２はレイヤ３に含まれる道路網に加えて国道や県道等の主要な一般道路に関する情報が格納されている。また、レイヤ１はレイヤ２に含まれる道路網に加えて細街路等のその他全ての一般道に関する詳細な道路網に関する情報が格納されている。
【００３５】
更に、下位レベルのレイヤでは詳細なデータを有する代わりにカバーする範囲が狭く、上位レベルのレイヤでは粗いデータしか有していない代わりにカバーする範囲が広くなっている。例えば、最下位レベルのレイヤ１では細街路を含む全ての道路の道路データを有するが市町村範囲しかカバーしておらず、最上位レベルのレイヤ３では高速道路や有料道路等の道路の道路データしか有していないが日本全国をカバーする。
【００３６】
尚、各レベルのレイヤにおけるリーションの形状、即ち、各リージョンのカバーする範囲の広さは、適宜決定することができる。また、地図データを構成するレベルの数、即ち、レイヤの階層の数も、必ずしも３層である必要はなく、例えば２層や４層であっても良い。
【００３７】
次に、各レイヤの地図データ３２を構成する各リージョンについて説明する。
図４に示すように、各レイヤの内、最も上位のレイヤ３を除くレイヤを構成する各リージョン６１は、コア領域６２とコア領域６２の周囲に形成されたオーバーラップ領域６３から構成されている。それに対して、最も上位階層のレイヤ３を構成するリージョン６４の地図データ３２Ｃについては、オーバーラップ領域が存在せず、コア領域６５のみから構成されている。即ち、最も上位階層のレイヤ３の地図データは、各リージョンが重複する重複エリアが生じないように記憶され、他のレイヤ１、２の地図データは、各リージョンが重複する重複エリアが生じるように記憶される。
【００３８】
そして、本実施形態に係るナビゲーション装置１では、上記のようにレイヤ３についてオーバーラップ領域を存在しないように構成したことから、従来のように経路の探索方向（出発地→目的地、又は目的地→出発地）によって異なる経路が探索される虞がない。また、特に２つのＣＰＵにより出発地と目的地の両方から探索を行う場合においても、探索時のＣＰＵの状態によって、出発地と目的地が同じでも探索処理を行う度に異なる経路が探索される虞もない（図１１参照）。
【００３９】
以下に、図４を用いて上記従来の問題点の解消についてより詳細に説明する。図４に示す例では、図１１と同様に地点Ｘを出発地とし、地点Ｙを目的地に設定し、リージョンＡとリージョンＢが探索対象に決定された場合の経路の探索例を示す。ここで、図４に示す例では、地点Ｘと地点Ｙとを結ぶ経路としては、一般道路を通る“下ルート”と、有料道路を通る“上ルート”がある。そして、出発地である地点Ｘ方向から地点Ｙ方向へと探索を行うと、“下ルート”のリージョンＡの境界ノード１１０が接続される先のノード１１１はリージョンＢのコア領域内のノードとなるので、“下ルート”は経路候補の対象となる。しかし、“上ルート”のリージョンＡの境界ノード１１０が接続される先のノード１１２についてはリージョンＢのコア領域内のノードとならない（即ち、探索対象外のリージョンのコア領域内のノードとなる）ので、“上ルート”は経路候補の対象とならない（経路が接続されない）。従って、出発地である地点Ｘ方向から地点Ｙ方向へと探索を行うと、“下ルート”のみが経路候補となる。
【００４０】
一方、目的地である地点Ｙ方向から地点Ｘ方向へと探索を行うと、“下ルート”のリージョンＢの境界ノード１１１が接続される先のノード１１０はリージョンＡのコア領域内のノードとなるので、“下ルート”は経路候補の対象となる。しかし、“上ルート”のリージョンＢの境界ノード１１３が接続される先のノード１１４についてはリージョンＡのコア領域内のノードとならない（即ち、探索対象外のリージョンのコア領域内のノードとなる）ので、“上ルート”は経路候補の対象とならない（経路が接続されない）。従って、目的地である地点Ｙ方向から地点Ｘ方向へと探索を行う場合でも、“下ルート”のみが経路候補となり、上記した出発地である地点Ｘ方向から地点Ｙ方向へと探索を行う場合と同じ案内経路が設定されることとなる。
【００４１】
次に、地図データ３２を構成するデータの詳細について説明する。
図５に示すように、地図データ３２は、各レイヤの地図データ３２Ａ〜３２Ｃから構成される。そして、各レイヤの地図データ３２Ａ〜３２Ｃは、上述したように地図表示データ、リンクデータ、ノードデータ、探索データ、従属関係データ、施設データ、交差点データ、検索データ等によってそれぞれ構成されている。図５は本実施形態に係る地図データ３２の構成を示した図である。
【００４２】
ここで、地図表示データとしては、各レイヤの地図データ３２Ａ〜３２Ｃに応じた地図表示を行う為の地図描画情報が記憶される。
【００４３】
また、リンクデータとしては、それぞれのレイヤの地図データ３２Ａ〜３２Ｃにおいて道路を構成する各リンクに関してリンクの属する道路の幅員、勾（こう）配、カント、バンク、路面の状態、道路の車線数、車線数の減少する箇所、幅員の狭くなる箇所、踏切り等を表すデータが、コーナに関して、曲率半径、交差点、Ｔ字路、コーナの入口及び出口等を表すデータが、道路属性に関して、降坂路、登坂路等を表すデータが、道路種別に関して、国道、県道、細街路等の一般道のほか、高速自動車国道、自動車専用道路、都市高速道路、一般有料道路、有料橋等の有料道路を表すデータがそれぞれ記録される。更に、有料道路に関して、有料道路の入口及び出口の取付道（ランプウェイ）、料金所（インターチェンジ）等に関するデータが記録される。
【００４４】
また、ノードデータとしては、それぞれのレイヤの地図データ３２Ａ〜３２Ｃにおいて道路の分岐点（交差点、Ｔ字路等も含む）、各道路に曲率半径等に応じて所定の距離ごとに設定されたノード点の座標（位置）、ノードが交差点に対応するノードであるか等を表すノード属性、ノードに接続するリンクのリンク番号のリストである接続リンク番号リスト、ノードにリンクを介して隣接する他のノードのノード番号のリストである隣接ノード番号リスト、各ノード点の高さ（高度）等に関するデータ等が記録される。
また、ノードデータとしては、階層の異なるレイヤ同士のノード（例えば、レイヤ１のノードとレイヤ２のノード、レイヤ２のノードとレイヤ３のノード）の接続関係を特定する上位接続データについても記憶される。
更に、本実施形態ではノードデータとして、特に“レイヤ２のノードの内の境界ノード”と、“該境界ノードが接続されるノードである接続先ノードを含むレイヤ３のリージョン”とを対応付けるノード領域対応データ３３についても記憶される。尚、ノード領域対応データ３３の詳細については後述する。
【００４５】
また、探索データとしては、それぞれのレイヤの地図データ３２Ａ〜３２Ｃにおいて設定された目的地までの経路を探索及び表示する際に使用されるデータについて記録されており、ノードを通過する際のコスト（以下、ノードコストという）や道路を構成するリンクのコスト（以下、リンクコストという）からなる探索コストを算出する為に使用するコストデータ、リンクを通過するのに必要な旅行時間、経路探索により選択された経路を液晶ディスプレイ１５の地図上に表示するための経路表示データ等から構成されている。
ここで、ノードコストは、交差点に対応するノードに対して基本的に設定されており、例えば、信号の有無や交差点を通過する際の自車の走行経路（即ち直進、右折及び左折の種類）によってその値が決定される。
また、リンクコストは、リンクを構成する道路属性や道路種別、道路幅、車線数、リンク長さに加え、ＶＩＣＳ情報として取得する渋滞度等の交通情報に関するデータを用いて算出される。
【００４６】
また、施設データとしては、各地域のホテル、病院、ガソリンスタンド、駐車場、観光施設、インターチェンジ、レストラン、サービスエリア等の建物に関するデータが建物を特定する施設ＩＤとともに記録される。
【００４７】
また、従属関係データとしては、各レイヤを構成する各リージョンについて、レイヤ間のリージョンの親子関係を特定するデータが記憶される。具体的には、レイヤ３のリージョンと、該リージョン内に含まれるレイヤ２のリージョンとを対応づけたデータと、レイヤ２のリージョンと、該リージョン内に含まれるレイヤ１のリージョンとを対応づけたデータとが記憶される。
【００４８】
そして、ナビゲーション装置１は、出発地と目的地付近の地域では、出発地から目的地までの距離が短距離（例えば、３ｋｍ程度）の経路探索の場合には、現在地周辺の最下層の地図データであるレイヤ１の地図データのみを使用して経路を探索する。
また、現在地から目的地までの距離が中距離（例えば、５０ｋｍ程度）の経路探索の場合には、現在地及び目的地周辺については最下層の地図データであるレイヤ１の地図データのリージョンを使用し、使用されたレイヤ１の地図データのリージョンに隣接するエリアは中間層の地図データであるレイヤ２の地図データのリージョンを使用して経路を探索する。
更に、現在地から目的地までの距離が長距離（例えば、３００ｋｍ程度）の経路探索の場合には、現在地及び目的地周辺の最下層の地図データであるレイヤ１の地図データのリージョンを使用し、使用されたレイヤ１の地図データのリージョンに隣接するエリアは中間層の地図データであるレイヤ２の地図データのリージョンを使用し、使用されたレイヤ２の地図データのリージョンに隣接するエリアは最上層の地図データであるレイヤ３の地図データのリージョンを使用して経路を探索する。また、特にレイヤ３については出発地と目的地の位置座標に基づいて、予め探索対象とするリージョンが設定される。
以上により、経路を探索の為の演算量を抑えることができ、経路探索に必要な時間を短縮することができる。
【００４９】
また、上記中距離や長距離等の複数のレイヤを跨ぐ探索を行う場合には、図６に示すように、下位階層を構成するリージョン内での探索において、そのリージョンの境界ノード７１まで達すると、その境界ノード７１が含まれる上位階層のリージョンのノード（接続先ノード）７２に上げて探索が続けられる。従って、図６に示す例では出発地７３と目的地７４を含むレイヤ１のリージョンと、レイヤ１の境界ノード７１と接続されるレイヤ２の接続先ノード７２を含むリージョンと、探索対象に設定されるレイヤ３のリージョン内で経路の探索が行われる。尚、境界ノード７１は、レイヤ１とレイヤ２については、オーバーラップ領域６３から退出するリンクの外側に接続されたノードとなる。一方、レイヤ３については、コア領域６５から退出するリンクの内側に接続されたノードとなる。
【００５０】
そして、本実施形態では、上述したようにレイヤ３の地図データはオーバーラップ領域が存在せず、コア領域６５のみから構成される。従って、レイヤ２の境界ノード７１からレイヤ３の接続先ノード７２への連絡には、レイヤ２の境界ノード７１にノード領域対応データ３３を持たせる必要がある。
以下に、その理由について説明する。
図７及び図８は、レイヤ３の地図データにオーバーラップ領域を含めた比較例と、レイヤ３の地図データからオーバーラップ領域を削除した実施例についてそれぞれ示した図である。
【００５１】
図７の比較例では、レイヤ２のリージョン８１の親関係にあるレイヤ３のリージョン８２（リージョン８１を含むレイヤ３のリージョン）に、リージョン８１の境界ノード８３と同じノードを含む。従って、レイヤ２の境界ノード８３からレイヤ３の接続先ノード８４への連絡を行う際に、接続先ノード８４を含むレイヤ３のリージョンが親関係にあるリージョン８２となる。ここで、前記したようにレイヤ間のリージョンの親子関係を特定する従属関係データは地図データ３２に含まれているので、レイヤ２の境界ノード８３に“境界ノード８３が接続される接続先ノード８４を含むレイヤ３のリージョン”を対応づけるノード領域対応データ３３を持たせる必要は無い。
【００５２】
一方、図７の実施例では、レイヤ２のリージョン８５の親関係にあるレイヤ３のリージョン８６（リージョン８５を含むレイヤ３のリージョン）には、リージョン８５の境界ノード８７と同じノードを含まず、隣接する他のリージョン８８にリージョン８５の境界ノード８７と同じノードを含む。従って、レイヤ２の境界ノード８７からレイヤ３の接続先ノード８９への連絡を行う際に、接続先ノード８９を含むレイヤ３のリージョンは親関係にないリージョン８８となる。従って、レイヤ２の境界ノード８７には、接続先ノード８９との接続関係を特定する上位接続データに加えて“境界ノード８７が接続される接続先ノード８９を含むレイヤ３のリージョン８８”を対応づけるノード領域対応データ３３を持たせる必要がある。
また、前記したようにレイヤ３のオーバーラップ領域を削除した実施例では、レイヤ３の境界ノードはコア領域から退出するリンクの内側に接続されたノードとなるので、経路探索中にレイヤ２の境界ノードからレイヤ３の接続先ノードへと連絡する際に、探索経路が探索方向（例えば、目的地から出発地方向）と逆方向側に戻り、経路が重複する可能性がある。ノード領域対応データ３３を境界ノード８７に持たせることによって、このような経路の重複についても防止することが可能となる。
【００５３】
一方、図８の比較例では、レイヤ２のリージョン９１の親関係にあるレイヤ３のリージョン９２（リージョン９１を含むレイヤ３のリージョン）に、リージョン９１の境界ノード９３の接続先となる接続先ノード９４は含まないが、接続先ノード９４と接続されるノード９５は必ず含む。従って、レイヤ２の境界ノード９３からレイヤ３の接続先ノード９４への連絡を行う際に、接続先ノード９４に接続されるノード９５を含むレイヤ３のリージョンが親関係にあるリージョン９２となる。ここで、前記したようにレイヤ間のリージョンの親子関係を特定する従属関係データは地図データ３２に含まれ、且つノード９５と接続先ノード９４の接続関係もノードデータとして記憶されているので、レイヤ２の境界ノード９３に“境界ノード９３が接続される接続先ノード９４を含むレイヤ３のリージョン”を対応づけるノード領域対応データ３３を持たせる必要は無い。
【００５４】
一方、図８の実施例では、レイヤ２のリージョン９６の親関係にあるレイヤ３のリージョン９７（リージョン９６を含むレイヤ３のリージョン）には、リージョン９６の境界ノード９８の接続先となる接続先ノード９９は含まず、接続先ノード９９と接続されるノード１００も含まない場合がある。従って、レイヤ２の境界ノード９８からレイヤ３の接続先ノード９９への連絡を行う際に、接続先ノード９９やノード１００を含むレイヤ３のリージョンは親関係にないリージョン１０１となる。従って、レイヤ２の境界ノード９８には、接続先ノード９９との接続関係を特定する上位接続データに加えて“境界ノード９８が接続される接続先ノード９９を含むレイヤ３のリージョン１０１”を対応づけるノード領域対応データ３３を持たせる必要がある。
また、前記したようにレイヤ３のオーバーラップ領域を削除した実施例では、レイヤ３の境界ノードはコア領域から退出するリンクの内側に接続されたノードとなるので、経路探索中にレイヤ２の境界ノードからレイヤ３の接続先ノードへと連絡する際に、探索経路が探索方向（例えば、目的地から出発地方向）と逆方向側に戻り、経路が重複する可能性がある。ノード領域対応データ３３を境界ノード９８に持たせることによって、このような経路の重複についても防止することが可能となる。
【００５５】
そして、ナビゲーションＥＣＵ１３が経路を探索する際には、地図データにおける探索データ中の道路データを調査して、探索に使用されるメッシュに含まれる道路（リンク及びノード）についての探索コスト（ノードコスト及びリンクコスト）を計算して、経路を探索する。一般的には、目的地側から経路の探索が行われ、目的地側から出発地まで累積された探索コストを加算した値、即ち、コスト加算値が算出される。そして、探索条件（有料道優先、一般道優先、距離優先等）を変更し、各条件で最もコスト加算値が小さくなった経路をそれぞれ案内する。そして、ユーザによって選択された経路を誘導経路として設定する。また、２つのＣＰＵにより出発地と目的地の両方から探索を行う探索方法を用いた場合には、出発地側及び目的地側から経路の探索が行われ、出発地側からの探索と目的地側からの探索とが重なった場合において、出発地側から累積された探索コストと目的地側から累積された探索コストとを加算した値、即ち、コスト加算値が算出される。
【００５６】
続いて、前記構成を有するナビゲーション装置１においてＣＰＵ４１が実行する経路探索処理プログラムについて図９に基づき説明する。図９は本実施形態に係る経路探索処理プログラムのフローチャートである。ここで、経路探索処理プログラムはナビゲーション装置１において経路探索を行う為の所定の操作（例えば、目的地の設定操作）を受け付けた際に実行され、出発地から目的地までの経路を探索するプログラムである。尚、以下の図９にフローチャートで示されるプログラムは、ナビゲーション装置１が備えているＲＡＭ４２やＲＯＭ４３に記憶されており、ＣＰＵ４１により実行される。
【００５７】
先ず、経路探索処理プログラムではステップ（以下、Ｓと略記する）１において、ＣＰＵ４１は、受け付けたユーザの操作に基づいて出発地及び目的地を設定する。尚、出発地については車両の現在位置としても良い。
【００５８】
次に、Ｓ２においてＣＰＵ４１は、前記Ｓ１で設定された出発地と目的地に基づいて、探索対象とするレイヤ３のリージョンが設定される。具体的には、予め出発地及び目的地の位置座標と、検索対象とするリージョンとの対応関係を示すテーブルをＲＡＭ４２等に記憶させておき、前記Ｓ１で設定された出発地及び目的地の位置座標とテーブルとに基づいて、検索対象とするリージョンを特定することにより行う。
【００５９】
続いて、Ｓ３においてＣＰＵ４１は、前記Ｓ１で設定された出発地から目的地までの経路の探索処理を行う。尚、レイヤ３については前記Ｓ２で設定されたリージョンのみを対象として経路探索が行われる。そして、複数の探索条件（有料道優先、一般道優先、距離優先等）でそれぞれコスト加算値の算出を行い、各条件で最もコスト加算値が小さくなった経路をそれぞれ案内する。例えば、液晶ディスプレイ１５上に探索条件とともに経路の全体図を表示する。尚、一の探索条件だけを用い、最もコスト加算値が小さくなった一の経路のみを案内する構成としても良い。また、経路探索処理の詳細については既に説明したので省略する。
【００６０】
その後、Ｓ４でＣＰＵ４１は、前記Ｓ３で案内された経路の内、ユーザの操作等に基づいて選択された経路を案内経路に設定する。
【００６１】
そして、Ｓ５においてＣＰＵ４１は、設定された案内経路に従って液晶ディスプレイ１５やスピーカ１６を用いて走行の案内を行う。
【００６２】
以上詳細に説明した通り、本実施形態に係るナビゲーション装置１では、地図情報ＤＢ３１に記憶される地図データ３２は、後述のように道路網の情報量の差異に基づいて複数レイヤに階層化された構造し、各レイヤは複数の領域（リージョン）に分割されて記憶される。そして、レイヤ３のオーバーラップ領域を削除してレイヤ３のリージョン同士が重複しないようにし、レイヤ２の境界ノードには、レイヤ３の接続先ノードとの接続関係を特定する上位接続データに加えて、境界ノードが接続される接続先ノードを含むレイヤ３のリージョンを対応づけるノード領域対応データ３３についても持たせるように構成するので、地図データのデータサイズを減少させ、経路探索処理の処理時間や処理負担を軽減させることが可能となる。また、経路の探索方向や探索時のＣＰＵの状態によって、異なる経路が探索されることを防止できる。また、ノード領域対応データ３３を記憶させることによって、レイヤ３のオーバーラップ領域を削除した場合でも、レイヤ３とレイヤ２との間のノードの接続を適切に行うことが可能となる。
また、オーバーラップ領域を削除するレイヤは、最も道路網の情報量の少ない最上位のレイヤ３とする。従って、レイヤ３においてオーバーラップ領域を削除した場合でも、レイヤ３とレイヤ３に連絡するレイヤ２との間のノードの接続を適切に行うことが可能となる。従って、出発地と目的地とが離れた位置にある場合であっても、レイヤ３を含む複数のレイヤを用いて、経路探索を適切に行うことが可能となる。
また、特に２つのＣＰＵにより出発地と目的地の両方から探索を行う場合には、出発地と目的地が同一であっても探索時のＣＰＵの状態によって探索を行う度に異なる経路が探索されることを防止できる。
出発地と目的地に基づいて特定された領域を対象として、出発地から目的地までの経路を探索するので、経路探索の為の演算量を抑えることができる。結果として、ＣＰＵの処理負担が軽減でき、また、経路探索に必要な時間を短縮することができる。
【００６３】
尚、本発明は前記実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の改良、変形が可能であることは勿論である。
例えば、本実施形態では、オーバーラップ領域を削除するレイヤを最も道路網の情報量の少ない最上位のレイヤ３としているが、レイヤ３以外のレイヤについてオーバーラップ領域を削除しても良い。また、オーバーラップ領域を削除する対象とするレイヤは、複数層でも良い。
【００６４】
また、レイヤの階層の数も、必ずしも３層である必要はなく、例えば２層や４層であっても良い。更に、地域毎にレイヤの階層の数が異なるようにしても良い。更に、各レイヤのリーションの形状（コア領域やオーバーラップ領域の形状）は適宜変更することが可能である、
【００６５】
また、境界ノードは、レイヤ１とレイヤ２については、オーバーラップ領域から退出するリンクの外側に接続されたノードとし、レイヤ３については、コア領域から退出するリンクの内側に接続されたノードとしているが、他のノードを境界ノードとしても良い。例えば、レイヤ１とレイヤ２については、オーバーラップ領域から退出するリンクの外側に接続されたノードに、更に一また複数のリンクを介して接続されたノードを境界ノードとしても良い。
【００６６】
また、本実施形態では本願発明をナビゲーション装置１に適用した例について説明したが、経路探索機能を有する装置であれば、携帯電話機等の携帯端末やパーソナルコンピュータ等に適用することも可能である。
【符号の説明】
【００６７】
１ ナビゲーション装置
１３ ナビゲーションＥＣＵ
３１ 地図情報ＤＢ
３２ 地図データ
３３ ノード領域対応データ
４１ ＣＰＵ
４２ ＲＡＭ
４３ ＲＯＭ
７１、８３、８７、９３、９８ 境界ノード
７２、８４、８９、９４、９９ 接続先ノード
【特許請求の範囲】
【請求項１】
地図データを記憶する地図データ記憶媒体と、
前記地図データ記憶媒体に記憶された前記地図データに基づいて、出発地から目的地までの経路を探索する経路探索手段と、を有する経路探索装置であって、
前記地図データ記憶媒体は、
前記地図データを複数の領域に区分するとともに、道路網の情報量に基づいて複数のレイヤに階層化して記憶し、
前記地図データの領域毎に、該領域と対応する他のレイヤの領域とを関連付けた領域対応情報を記憶し、
前記複数のレイヤの内、特定レイヤの前記地図データを各領域が重複する重複エリアが生じないように記憶するとともに、前記特定レイヤ以外のレイヤの前記地図データを各領域が重複する重複エリアが生じるように記憶し、
前記特定レイヤ以外のレイヤの前記地図データに含まれるノードの内、前記重複エリアから退出するリンクに接続されたノードである境界ノードと、該境界ノードが接続されるノードである接続先ノードを含む前記特定レイヤの領域とを対応付けるノード領域対応情報を記憶することを特徴とする経路探索装置。
【請求項２】
前記特定レイヤは、前記複数のレイヤの内、最も道路網の情報量の少ない最上位レイヤであることを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記ノード領域対応情報は、前記複数のレイヤの内、前記最上位レイヤの次に道路網の情報量が少ない次上位レイヤの前記境界ノードと、前記接続先ノードを含む前記最上位レイヤの領域とを対応付けることを特徴とする請求項２に記載の経路探索装置。
【請求項４】
前記経路探索手段は、
前記出発地側及び前記目的地側から経路の探索を行い、前記出発地側からの探索と前記目的地側からの探索とが重なった場合において、前記出発地側から累積された探索コストと前記目的地側から累積された探索コストとを加算したコスト加算値を算出するコスト算出手段と、
前記コスト算出手段により算出された前記コスト加算値に基づいて、前記出発地から前記目的地までの経路を設定する経路設定手段と、
を備えることを特徴とする請求項１乃至請求項３のいずれかに記載の経路探索装置。
【請求項５】
前記出発地及び前記目的地に基づいて、前記地図データの内、探索対象とする領域を設定する探索対象領域設定手段を有し、
前記経路探索手段は、前記探索対象領域設定手段によって設定された領域を対象として、前記出発地から前記目的地までの経路を探索することを特徴とする請求項１乃至請求項４のいずれかに記載の経路探索装置。
【請求項６】
経路探索装置の経路探索に用いられる地図データであって、
複数の領域に区分されるとともに、道路網の情報量に基づいて複数のレイヤに階層化され、
前記領域毎に、該領域と対応する他のレイヤの領域とを関連付けた領域対応情報を含み、
前記複数のレイヤの内、特定レイヤは各領域が重複する重複エリアを生じることなく、前記特定レイヤ以外のレイヤは前記地図データの各領域が重複する重複エリアを生じ、
前記特定レイヤ以外のレイヤに含まれるノードの内、前記重複エリアから退出するリンクに接続されたノードである境界ノードと、該境界ノードが接続されるノードである接続先ノードを含む前記特定レイヤの領域とを対応付けるノード領域対応情報を含むことを特徴とする地図データ。
【請求項１】
地図データを記憶する地図データ記憶媒体と、
前記地図データ記憶媒体に記憶された前記地図データに基づいて、出発地から目的地までの経路を探索する経路探索手段と、を有する経路探索装置であって、
前記地図データ記憶媒体は、
前記地図データを複数の領域に区分するとともに、道路網の情報量に基づいて複数のレイヤに階層化して記憶し、
前記地図データの領域毎に、該領域と対応する他のレイヤの領域とを関連付けた領域対応情報を記憶し、
前記複数のレイヤの内、特定レイヤの前記地図データを各領域が重複する重複エリアが生じないように記憶するとともに、前記特定レイヤ以外のレイヤの前記地図データを各領域が重複する重複エリアが生じるように記憶し、
前記特定レイヤ以外のレイヤの前記地図データに含まれるノードの内、前記重複エリアから退出するリンクに接続されたノードである境界ノードと、該境界ノードが接続されるノードである接続先ノードを含む前記特定レイヤの領域とを対応付けるノード領域対応情報を記憶することを特徴とする経路探索装置。
【請求項２】
前記特定レイヤは、前記複数のレイヤの内、最も道路網の情報量の少ない最上位レイヤであることを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記ノード領域対応情報は、前記複数のレイヤの内、前記最上位レイヤの次に道路網の情報量が少ない次上位レイヤの前記境界ノードと、前記接続先ノードを含む前記最上位レイヤの領域とを対応付けることを特徴とする請求項２に記載の経路探索装置。
【請求項４】
前記経路探索手段は、
前記出発地側及び前記目的地側から経路の探索を行い、前記出発地側からの探索と前記目的地側からの探索とが重なった場合において、前記出発地側から累積された探索コストと前記目的地側から累積された探索コストとを加算したコスト加算値を算出するコスト算出手段と、
前記コスト算出手段により算出された前記コスト加算値に基づいて、前記出発地から前記目的地までの経路を設定する経路設定手段と、
を備えることを特徴とする請求項１乃至請求項３のいずれかに記載の経路探索装置。
【請求項５】
前記出発地及び前記目的地に基づいて、前記地図データの内、探索対象とする領域を設定する探索対象領域設定手段を有し、
前記経路探索手段は、前記探索対象領域設定手段によって設定された領域を対象として、前記出発地から前記目的地までの経路を探索することを特徴とする請求項１乃至請求項４のいずれかに記載の経路探索装置。
【請求項６】
経路探索装置の経路探索に用いられる地図データであって、
複数の領域に区分されるとともに、道路網の情報量に基づいて複数のレイヤに階層化され、
前記領域毎に、該領域と対応する他のレイヤの領域とを関連付けた領域対応情報を含み、
前記複数のレイヤの内、特定レイヤは各領域が重複する重複エリアを生じることなく、前記特定レイヤ以外のレイヤは前記地図データの各領域が重複する重複エリアを生じ、
前記特定レイヤ以外のレイヤに含まれるノードの内、前記重複エリアから退出するリンクに接続されたノードである境界ノードと、該境界ノードが接続されるノードである接続先ノードを含む前記特定レイヤの領域とを対応付けるノード領域対応情報を含むことを特徴とする地図データ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１２−１１７８６８（Ｐ２０１２−１１７８６８Ａ）
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願番号】特願２０１０−２６６３３５（Ｐ２０１０−２６６３３５）
【出願日】平成２２年１１月３０日（２０１０．１１．３０）
【出願人】（０００１００７６８）アイシン・エィ・ダブリュ株式会社 (3,717)
【Ｆターム（参考）】
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願日】平成２２年１１月３０日（２０１０．１１．３０）
【出願人】（０００１００７６８）アイシン・エィ・ダブリュ株式会社 (3,717)
【Ｆターム（参考）】
[ Back to top ]