(57)【特許請求の範囲】
【請求項１】
ナビゲーション情報を取得する情報取得処理手段と、目的地を設定する目的地設定処理手段と、出発地から目的地までの経路を探索する経路探索処理手段と、探索された経路を分割し、分割された経路を再び探索する経路再探索処理手段と、該経路再探索処理手段による探索結果に基づいて再探索経路を決定する再探索経路決定処理手段とを有するとともに、前記探索された経路は、各分割された経路間の分割点をずらして、繰り返し分割されることを特徴とするナビゲーションシステム。
【請求項２】
前記ナビゲーション情報の探索データは、下位の道路から上位の道路までの詳細度に応じて階層化された複数のレイヤとして記録され、前記経路再探索処理手段は、複数のレイヤの探索データを使用して経路を再び探索する請求項１に記載のナビゲーションシステム。
【請求項３】
前記探索された経路は、所定のメモリ容量で探索が可能なナビゲーション情報の範囲に基づいて分割される請求項１に記載のナビゲーションシステム。
【請求項４】
コンピュータを、ナビゲーション情報を取得する情報取得処理手段、目的地を設定する目的地設定処理手段、出発地から目的地までの経路を探索する経路探索処理手段、探索された経路を分割し、分割された経路を再び探索する経路再探索処理手段、及び該経路再探索処理手段による探索結果に基づいて再探索経路を決定する再探索経路決定処理手段として機能させるとともに、前記探索された経路は、各分割された経路間の分割点をずらして、繰り返し分割されることを特徴とする経路探索方法のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ナビゲーションシステム及び経路探索方法のプログラムに関するものである。
【０００２】
【従来の技術】
従来、ナビゲーション装置においては、例えば、ＧＰＳ（グローバルポジショニングシステム）によって車両の現在の位置、すなわち、現在地が検出されるとともに、ジャイロセンサによって検出された車両の回転角速度、すなわち、旋回角に基づいて、車両の方位、すなわち、自車方位が検出され、データ記録部から地図データが読み出され、表示部のディスプレイに地図画面が形成され、該地図画面に、地図、現在地及び自車方位が表示されるようになっている。したがって、操作者である運転者は、前記地図画面に表示された地図、現在地及び自車方位に従って車両を走行させることができる。
【０００３】
また、運転者が目的地及び出発地を設定することができるようになっていて、目的地が設定されると、現在地から目的地までの経路が探索され、目的地及び出発地が設定されると、出発地から目的地までの経路が探索される。そして、前記ディスプレイに探索経路表示画面が形成され、該探索経路表示画面に、探索された経路、すなわち、探索経路が表示される。したがって、運転者は、探索経路に従って車両を走行させることができる。
【０００４】
ところで、前記経路を探索するために、前記データ記録部に探索データファイルが記録され、該探索データファイルから経路を決定するためにデータ、すなわち、探索データが読み出されるようになっている。該探索データは、下位から上位にかけて複数のレイヤ、例えば、レイヤ１〜３から成る階層構造を有し、レイヤ１においては、高速道路、有料道路等の高速・有料道、国道、主要地方道、県道等の一般道のほかに、細街路、導入路等のすべての道路が記録され、レイヤ２においては、前記レイヤ１の道路のうちの、前記高速・有料道、国道、主要地方道等のように、幅員が大きい道路、車線数が多い道路、制限速度が高い道路、車両の流れがよい道路等が記録される。そして、レイヤ３においては、前記高速・有料道、国道等のように、レイヤ２の道路のうちの、更に幅員が大きい道路、車線数が多い道路、制限速度が高い道路、車両の流れがよい道路等が記録される。なお、各レイヤ１〜３はデータファイルによって形成される。
【０００５】
ところで、一般に、運転者は、数百〔ｋｍ〕程度の長い距離を走行する場合、高速道路を使用することが多く、数十〔ｋｍ〕程度の中程度の距離を走行する場合、国道、主要地方道、県道等を使用することが多い。したがって、走行する距離によって、各レイヤ１〜３の構成、例えば、階層の数、各レイヤ１〜３を構成する道路、各レイヤ１〜３の探索データの領域等が決定されるようになっている。
【０００６】
そして、距離が短い経路を探索する場合、レイヤ１の探索データだけが使用され、距離が長い経路を探索する場合、各レイヤ１〜３の探索データが使用される。これは、距離が長い経路を探索する場合に、レイヤ１だけを使用すると、データ記録部に記録される探索データの量が極めて多くなり、経路を探索するための処理、すなわち、経路探索処理を行うのに必要なメモリ容量を確保することができず、経路を探索することができなくなったり、経路探索処理の処理速度が低くなったりするからである。
【０００７】
また、出発地及び目的地に近いほど、下位のレイヤの探索データが使用され、出発地及び目的地から離れるほど、上位のレイヤの探索データが使用される。そして、出発地及び目的地の付近においては、レイヤ１の探索データが使用され、すべての道路の探索データが探索の対象になる。
【０００８】
【発明が解決しようとする課題】
しかしながら、前記従来のナビゲーション装置においては、出発地と目的地との中間地点では、上位のレイヤ２、３の探索データが使用されるので、レイヤ１だけに存在する県道、細街路、導入路等の道路の探索データは、探索の対象にはならない。
【０００９】
したがって、前記中間地点に、経路探索処理によって得られた探索経路から分岐し、かつ、経路探索処理において経路を決定する際に用いられる探索コスト（一般に、道路の長さ、又は通過するのに必要な時間に関連する値）の低い近道等の道路（以下「分岐道路」という。）が存在していても、分岐道路が県道、細街路、導入路等である限り、探索されることはないので、最適な経路を探索することができない。
【００１０】
図２は従来の経路探索処理の動作を説明する図である。
【００１１】
図において、Ｐｓは出発地、Ｐｅは目的地であり、出発地Ｐｓ及び目的地Ｐｅの周囲にレイヤ１が形成され、該レイヤ１の上位のレイヤとして、レイヤ２が形成される。また、Ｒｎ１、Ｒｎ２は国道、Ｒｐ１は県道、Ｆ１は探索経路である。前記国道Ｒｎ１、Ｒｎ２の探索データはレイヤ１、２に存在し、県道Ｒｐ１の探索データはレイヤ１に存在する。
【００１２】
そして、出発地Ｐｓと目的地Ｐｅとの中間地点においては、レイヤ２が使用されるので、県道Ｒｐ１の探索データは探索の対象にはならない。したがって、前記県道Ｒｐ１は、分岐道路であるにもかかわらず、探索経路Ｆ１に含まれないので、最適な経路を探索することができない。
【００１３】
本発明は、前記従来のナビゲーション装置の問題点を解決して、必要に応じて分岐道路の探索データを探索の対象にすることができ、最適な経路を探索することができるナビゲーションシステム及び経路探索方法のプログラムを提供することを目的とする。
【００１４】
【課題を解決するための手段】
そのために、本発明のナビゲーションシステムにおいては、ナビゲーション情報を取得する情報取得処理手段と、目的地を設定する目的地設定処理手段と、出発地から目的地までの経路を探索する経路探索処理手段と、探索された経路を分割し、分割された経路を再び探索する経路再探索処理手段と、該経路再探索処理手段による探索結果に基づいて再探索経路を決定する再探索経路決定処理手段とを有する。
そして、前記探索された経路は、各分割された経路間の分割点をずらして、繰り返し分割される。
【００１６】
本発明の他のナビゲーションシステムにおいては、さらに、前記ナビゲーション情報の探索データは、下位の道路から上位の道路までの詳細度に応じて階層化された複数のレイヤとして記録される。そして、前記経路再探索処理手段は、複数のレイヤの探索データを使用して経路を再び探索する。
【００１７】
本発明の更に他のナビゲーションシステムにおいては、さらに、前記探索された経路は、所定のメモリ容量で探索が可能なナビゲーション情報の範囲に基づいて分割される。
【００２３】
本発明の経路探索方法のプログラムにおいては、コンピュータを、ナビゲーション情報を取得する情報取得処理手段、目的地を設定する目的地設定処理手段、出発地から目的地までの経路を探索する経路探索処理手段、探索された経路を分割し、分割された経路を再び探索する経路再探索処理手段、及び該経路再探索処理手段による探索結果に基づいて再探索経路を決定する再探索経路決定処理手段として機能させる。
そして、前記探索された経路は、各分割された経路間の分割点をずらして、繰り返し分割される。
【００２４】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照しながら詳細に説明する。
【００２５】
図１は本発明の第１の実施の形態におけるナビゲーションシステムの機能ブロック図である。
【００２６】
図において、９２はナビゲーション情報を取得する情報取得処理手段、９３は目的地を設定する目的地設定処理手段、９６は出発地から目的地までの経路を探索する経路探索処理手段、９５は、探索された経路を分割し、分割された経路を再び探索する経路再探索処理手段、９７は該経路再探索処理手段９５による探索結果に基づいて再探索経路を決定する再探索経路決定処理手段である。
【００２７】
図３は本発明の第１の実施の形態におけるナビゲーションシステムの要部を示すブロック図である。
【００２８】
図において、１４はナビゲーション装置であり、該ナビゲーション装置１４は、現在地等を検出する現在地検出処理部１５、地図データ、道路データ、探索データ等のナビゲーション情報が記録された情報記録部及び記録媒体としてのデータ記録部１６、コンピュータとして配設され、各種の処理手段として機能し、入力された情報に基づいて、ナビゲーション処理等の各種の演算処理を行うナビゲーション処理部１７、操作装置及び第１の入力装置としての入力部３４、表示装置及び第１の出力装置としての表示部３５、第２の入力装置としての音声入力部３６、第２の出力装置としての音声出力部３７、並びに第３の入力装置及び第３の出力装置としての通信部３８を有し、前記ナビゲーション処理部１７に車速センサ４１が接続される。
【００２９】
そして、前記現在地検出処理部１５は、現在地検出部としてのＧＰＳ２１、地磁気センサ２２、距離センサ２３、ステアリングセンサ２４、ビーコンセンサ２５、方位検出部としてのジャイロセンサ２６、図示されない高度計等から成る。
【００３０】
前記ＧＰＳ２１は、人工衛星によって発生させられた電波を受信することによって地球上における現在地を検出し、前記地磁気センサ２２は、地磁気を測定することによって自車方位を検出し、前記距離センサ２３は、道路上の所定の位置間の距離等を検出する。距離センサ２３としては、例えば、図示されない車輪の回転速度を測定し、該回転速度に基づいて距離を検出するもの、加速度を測定し、該加速度を２回積分して距離を検出するもの等を使用することができる。
【００３１】
また、前記ステアリングセンサ２４は、舵（だ）角を検出し、ステアリングセンサ２４としては、例えば、図示されないステアリングホイールの回転部に取り付けられた光学的な回転センサ、回転抵抗センサ、車輪に取り付けられた角度センサ等が使用される。
【００３２】
そして、前記ビーコンセンサ２５は、道路に沿って配設された電波ビーコン、光ビーコン等からの位置情報を受信して現在地を検出する。前記ジャイロセンサ２６は、旋回角を検出し、ジャイロセンサ２６としては、例えば、ガスレートジャイロ、振動ジャイロ等が使用される。そして、前記ジャイロセンサ２６によって検出された旋回角を積分することにより、自車方位を検出することができる。
【００３３】
なお、前記ＧＰＳ２１及びビーコンセンサ２５はそれぞれ単独で現在地を検出することができる。そして、距離センサ２３によって検出された距離と、地磁気センサ２２によって検出された自車方位、又はジャイロセンサ２６によって検出された旋回角とを組み合わせることにより現在地を検出することもできる。また、距離センサ２３によって検出された距離と、ステアリングセンサ２４によって検出された舵角とを組み合わせることにより現在地を検出することもできる。
【００３４】
前記データ記録部１６は、地図データファイル、交差点データファイル、ノードデータファイル、道路データファイル、写真データファイル、探索データファイル及び地点情報データファイル等のデータファイルから成るデータベースを備え、前記地図データファイルには、前記表示部３５の図示されないディスプレイに形成された地図画面に地図を表示するための地図データが、前記交差点データファイルには各交差点に関する交差点データが、ノードデータファイルにはノード点に関するノードデータが、道路データファイルには道路に関する道路データが、探索データファイルには経路を探索するための探索データが、前記地点情報データファイルには、各地域のホテル、ガソリンスタンド、駐車場、観光地案内等の施設に関する地点情報データがナビゲーション情報として記録される。そして、前記交差点データ、ノードデータ、道路データ及び探索データによって道路状況を表す道路状況データが構成される。なお、前記ノードデータは、実際の道路の分岐点（交差点、Ｔ字路等も含む）、ノード点、各ノード点間を連結するノード点間リンク等を示すデータから成る。
【００３５】
そして、前記道路データによって、道路自体について、幅員、勾（こう）配、カント、バンク、路面の状態、道路の車線数、車線数の減少する箇所、幅員の小さくなる箇所等が、コーナについて、曲率半径、交差点、Ｔ字路、コーナの入口等が、道路属性について、降坂路、登坂路等が、道路種別について、高速道路、都市高速道路、有料道路等の高速・有料道のほか、国道、県道等の一般道がそれぞれ表される。さらに、道路データによって、踏切、高速道路の入口及び出口の取付道（ランプウェイ）、高速・有料道の料金所等が表される。
【００３６】
そして、前記各データファイルには、前記表示部３５のディスプレイに設定された探索経路表示画面に、探索経路に沿って案内図を出力し、表示したり、交差点又は経路における特徴的な写真、コマ図等を表示したり、次の交差点までの距離、次の交差点における進行方向等を表示したり、他の案内情報を表示したりするための各種のデータが記録される。なお、前記データ記録部１６には、所定の情報を音声出力部３７によって出力するための各種のデータも記録される。
【００３７】
また、前記ナビゲーション処理部１７は、ナビゲーション装置１４の全体の制御を行う演算装置としてのＣＰＵ３１、該ＣＰＵ３１が各種の演算処理を行うに当たってワーキングメモリとして使用されるＲＡＭ３２、及び制御用のプログラムのほか、目的地までの経路の探索、経路案内、特定区間の決定等を行うための各種のプログラムが記録された記録媒体としてのＲＯＭ３３から成るとともに、前記ナビゲーション処理部１７に、前記入力部３４、表示部３５、音声入力部３６、音声出力部３７及び通信部３８が接続される。なお、前記ＣＰＵ３１にはＭＰＵも含まれる。
【００３８】
なお、前記データ記録部１６及びＲＯＭ３３は、図示されない磁気コア、半導体メモリ等によって構成される。また、前記データ記録部１６及びＲＯＭ３３として、磁気テープ、磁気ディスク、フレキシブルディスク、磁気ドラム、ＣＤ、ＭＤ、ＤＶＤ、光ディスク、ＭＯ、ＩＣカード、光カード等の各種の記録媒体を使用することもできる。
【００３９】
本実施の形態においては、前記ＲＯＭ３３に各種のプログラムが記録され、前記データ記録部１６に各種のデータが記録されるようになっているが、プログラム、データ等を同じ外部の記録媒体に記録することもできる。この場合、例えば、前記ナビゲーション処理部１７に図示されないフラッシュメモリを配設し、前記外部の記録媒体から前記プログラム、データ等を読み出してフラッシュメモリに書き込むこともできる。したがって、外部の記録媒体を交換することによって前記プログラム、データ等を更新することができる。また、図示されない自動変速機制御装置の制御用のプログラム等も前記外部の記録媒体に記録することができる。このように、各種の記録媒体に記録されたプログラムを起動し、データに基づいて各種の処理を行うことができる。
【００４０】
さらに、前記通信部３８は、例えば、渋滞情報、規制情報、駐車場情報等の各情報から成る交通情報のほか、交通事故情報、ＧＰＳ２１の検出誤差を検出するＤ−ＧＰＳ情報等の基地局から送信された各種のデータを受信したり、道路に沿って配設された電波ビーコン装置、光ビーコン装置等から電波ビーコン、光ビーコン等を介して位置情報を受信したりする。
【００４１】
また、前記入力部３４は、走行開始時の現在地を修正したり、出発地及び目的地を入力したりするためのものであり、前記ディスプレイに設定された画面に画像で表示された各種のキー、操作メニュー等の操作スイッチから成る。したがって、該操作スイッチをタッチすることによって入力を行うことができる。なお、入力部３４として、表示部３５と別に配設されたキーボード、マウス、バーコードリーダ、ライトペン、遠隔操作用のリモートコントロール装置等を使用することもできる。
【００４２】
そして、前記ディスプレイに形成された各種の画面には、操作案内、操作メニュー、操作キーの案内、現在地から目的地までの経路、該経路に沿った案内情報等が表示される。前記表示部３５としては、ＣＲＴディスプレイ、液晶ディスプレイ、プラズマディスプレイ等のディスプレイを使用したり、車両のフロントガラスにホログラムを投影するホログラム装置等を使用したりすることができる。
【００４３】
また、音声入力部３６は、図示されないマイクロホン等によって構成され、音声によって必要な情報を入力することができる。さらに、音声出力部３７は、図示されない音声合成装置及びスピーカを備え、音情報、例えば、音声合成装置によって合成された音声から成る案内情報、変速情報等をスピーカから出力する。なお、音声合成装置によって合成された音声のほかに、各種の音、あらかじめテープ、メモリ等に録音された各種の案内情報等をスピーカから出力することもできる。
【００４４】
次に、前記構成のナビゲーション装置１４の動作について説明する。
【００４５】
図４は本発明の第１の実施の形態におけるナビゲーション装置の動作を示すフローチャート、図５は本発明の第１の実施の形態における探索データの階層構造を示す図、図６は本発明の第１の実施の形態におけるレイヤ構成を示す図、図７は本発明の第１の実施の形態における経路を分割する動作を説明する第１の図、図８は本発明の第１の実施の形態における経路を分割する動作を説明する第２の図、図９は本発明の第１の実施の形態における経路を分割する動作を説明する第３の図、図１０は本発明の第１の実施の形態における情報登録処理のサブルーチンを示す図である。
【００４６】
まず、操作者である運転者によって入力部３４（図３）が操作され、ナビゲーション装置１４が起動されると、ＣＰＵ３１の図示されないナビ初期化処理手段は、ナビ初期化処理を行う。続いて、ＣＰＵ３１は、ＧＰＳ２１によって検出された現在地、及びジャイロセンサ２６によって検出された自車方位を読み込むとともに、ＣＰＵ３１の情報取得処理手段９２（図１）は、情報取得処理を行い、データ記録部１６から地図データファイル、道路データファイル、探索データファイル等を参照し、地図データ、道路データ、探索データ等のナビゲーション情報を読み出して情報を取得する。なお、本実施の形態において、前記情報取得処理手段９２は、データ記録部１６からナビゲーション情報を読み出して取得するようになっているが、通信部３８によってナビゲーション情報を受信して取得することもできる。
【００４７】
次に、前記ＣＰＵ３１の図示されない地図表示処理手段は、地図表示処理を行い、前記ディスプレイに地図画面を形成し、該地図画面に、前記地図データに従って現在地の周辺の地図を表示するとともに、前記現在地及び自車方位を表示する。
【００４８】
そして、前記ナビゲーション装置１４が経路探索装置として使用される場合、運転者が入力部３４を操作して出発地及び目的地を入力すると、ＣＰＵ３１の目的地設定処理手段９３は、目的地設定処理を行い、目的地を設定する。また、ＣＰＵ３１の経路探索処理手段９６は、経路探索処理を行う。そして、経路探索処理手段９６は、前記探索データを読み出し、該探索データに基づいて、出発地から目的地までの経路を探索する。
【００４９】
続いて、前記経路探索処理手段９６の図示されない探索経路表示処理手段は、探索経路表示処理を行い、前記ディスプレイに探索経路表示画面を形成し、該探索経路表示画面に探索経路を表示する。したがって、運転者は、探索経路に従って車両を走行させることができる。なお、本実施の形態においては、入力部３４を操作することによって出発地を設定するようになっているが、現在地検出処理部１５によって検出された現在地を利用して出発地を設定することもできる。
【００５０】
ところで、探索データは、図５に示されるように、下位から上位にかけて複数のレイヤ、例えば、レイヤ１〜３から成る階層構造を有し、図６に示されるようなレイヤ構成を有する。すなわち、各レイヤ１〜３は、下位の道路から上位の道路までの詳細度に応じて階層化される。なお、図５において矢印は経路探索処理の探索方向を示す。本実施の形態においては、出発地Ｐｓから目的地Ｐｅまで前記探索方向に沿って経路が探索されるようになっているが、出発地Ｐｓから目的地Ｐｅに向けて、かつ、目的地Ｐｅから出発地Ｐｓに向けて経路を探索することもできる。
【００５１】
レイヤ１においては、高速道路、有料道路等の高速・有料道、国道、主要地方道、県道等の一般道のほかに、細街路、導入路等のすべての道路が記録され、レイヤ２においては、前記レイヤ１の道路のうちの、前記高速・有料道、国道、主要地方道等のように、幅員が大きい道路、車線数が多い道路、制限速度が高い道路、車両の流れがよい道路等が記録される。そして、レイヤ３においては、前記高速・有料道、国道等のように、レイヤ２の道路のうちの、更に幅員が大きい道路、車線数が多い道路、制限速度が高い道路、車両の流れがよい道路等が記録される。なお、各レイヤ１〜３はデータファイルによって形成される。
【００５２】
ところで、一般に、運転者は、数百〔ｋｍ〕程度の長い距離を走行する場合、高速道路を使用することが多く、数十〔ｋｍ〕程度の中程度の距離を走行する場合、国道、主要地方道、県道等を使用することが多い。したがって、走行する距離によって、各レイヤ１〜３の構成、例えば、階層の数、各レイヤ１〜３を構成する道路、各レイヤ１〜３の範囲等が決定されるようになっている。
【００５３】
そして、出発地Ｐｓから目的地Ｐｅまでの距離が短い経路を探索する場合、レイヤ１の探索データだけが使用され、出発地Ｐｓから目的地Ｐｅまでの距離が長い経路を探索する場合、各レイヤ１〜３の探索データが使用される。これは、長い距離の経路を探索する場合に、レイヤ１の探索データだけを使用すると、経路探索処理を行うのに必要なメモリ容量を十分に確保することができず、経路探索処理を行うことができなくなったり、経路探索処理の処理速度が低くなったりするからである。
【００５４】
また、出発地Ｐｓ及び目的地Ｐｅに近いほど、下位のレイヤの探索データが使用され、出発地Ｐｓ及び目的地Ｐｅから離れるほど、上位のレイヤの探索データが使用される。そして、出発地Ｐｓ及び目的地Ｐｅの付近においては、レイヤ１の探索データが使用され、すべての道路の探索データが探索の対象になる。したがって、経路探索処理において、適正なレイヤの探索データを使用し、所定の探索手法に従って経路を探索することができる。
【００５５】
ところが、出発地Ｐｓと目的地Ｐｅとの中間地点では、上位のレイヤ２、３が使用されるので、レイヤ１だけに存在する県道、細街路、導入路等の道路の探索データが探索の対象にならず、その場合、前記中間地点において分岐道路が存在していても、分岐道路は、県道、細街路、導入路等の道路である限り、探索経路に含まれない。したがって、最適な経路を探索することができなくなってしまう。
【００５６】
そこで、本実施の形態においては、前記経路探索処理が行われた後の所定のタイミングで、ＣＰＵ３１の経路再探索処理手段９５は、経路探索処理によって得られた出発地Ｐｓから目的地Ｐｅまでの探索経路を複数の分割経路ＡＲｉ（ｉ＝１、２、…）に分割し、分割経路ＡＲｉにおける二つの地点間（区間）、本実施の形態においては、分割経路ＡＲｉの始点と終点との間について、探索データに従って再び経路を探索し、探索結果に基づいて最適な経路を決定することができるようにしている。なお、分割経路ＡＲｉにおける二つの地点間を再探索するときの探索データは、レイヤ１の探索データだけでもよいが、出発地Ｐｓから目的地Ｐｅまでの経路を探索する場合と同様に、分割経路ＡＲｉの始点と終点との距離に基づいて所定のレイヤの探索データとしてもよい。
【００５７】
図７において、Ｆ１は経路探索処理によって得られた出発地Ｐｓから目的地Ｐｅまでの探索経路であり、該探索経路Ｆ１は、国道Ｒｎだけを含み、国道Ｒｎに対する近道となる県道Ｒｐを含まない。また、図において、×は分割点を示す。
【００５８】
そして、前記経路再探索処理手段９５の図示されない経路分割処理手段は、経路分割処理を行い、探索経路Ｆ１を分割して分割経路ＡＲ１〜ＡＲ４を形成する。
【００５９】
この場合、経路再探索処理において分岐道路が確実に探索経路Ｆ１に含まれるようにするためには、前記分割経路ＡＲ１〜ＡＲ４を広くすることが望ましい。そこで、探索経路Ｆ１を分割するに当たり、分割経路ＡＲ１〜ＡＲ４は、ＲＡＭ３２において、バックグラウンドで経路再探索処理を行うのに必要なメモリ容量等のリソースの許す範囲内で可能な限り大きく形成される。
【００６０】
そのために、前記経路分割処理手段は、ＲＡＭ３２において、例えば、２〔Ｍｂｙｔｅ〕のメモリ容量をバックグラウンドで経路再探索処理を行うために割り当てることが可能であるとすると、出発地Ｐｓを含み、２〔Ｍｂｙｔｅ〕のメモリ容量で探索が可能な探索データの範囲を分割経路ＡＲ１として形成し、分割経路ＡＲ１内の各道路のうちの最も目的地Ｐｅ側の道路の終点、すなわち、最終ポイントを分割点とする。次に、該分割点を含み、同様に、２〔Ｍｂｙｔｅ〕のメモリ容量で探索が可能な探索データの範囲を分割経路ＡＲ２として形成し、分割経路ＡＲ２の最終ポイントを分割点とする。そして、この動作を繰り返すことによって、分割経路ＡＲ３、ＡＲ４を形成することができる。
【００６１】
続いて、前記経路再探索処理手段９５の図示されない分割探索処理手段は、分割探索処理を行い、各分割経路ＡＲ１〜ＡＲ４についてレイヤ１の探索データに従って再び経路を探索する。
【００６２】
ところで、図７に示されるように、前記探索経路Ｆ１を分割経路ＡＲ１〜ＡＲ４に分割したときに、前記県道Ｒｐが複数の分割経路、本実施の形態においては、分割経路ＡＲ１〜ＡＲ４に及ぶ場合は、各分割経路ＡＲ１〜ＡＲ４について再び経路を探索しても、県道Ｒｐは探索の対象にはならない。
【００６３】
そこで、前記経路分割処理手段は、レイヤ１の探索データに従って、図８に示されるように、出発地Ｐｓから目的地Ｐｅまでの探索経路Ｆ１を分割し、所定の数の分割経路、本実施の形態においては、前記各分割経路ＡＲ１〜ＡＲ４より長い一つの分割経路ＡＲ１１を形成する。続いて、前記分割探索処理手段は、分割経路ＡＲ１１についてレイヤ１の探索データに従って再び経路を探索する。このようにして、分岐道路である県道Ｒｐを再探索経路として探索することができ、新たな探索経路Ｆ２を得ることができる。
【００６４】
この場合、前記分割経路ＡＲ１１は、各分割経路ＡＲ１〜ＡＲ４より長いので、前記県道Ｒｐは分割経路ＡＲ１１内に収まり、複数の分割経路には及ばない。したがって、県道Ｒｐは探索経路Ｆ２に含まれるので、最適な経路を探索することができる。
【００６５】
続いて、ＣＰＵ３１の再探索経路決定処理手段９７は、再探索経路決定処理を行い、経路再探索処理手段９５による探索結果に基づいて県道Ｒｐを再探索経路として決定する。そのために、再探索経路決定処理手段９７の図示されない経路比較処理手段は、経路比較処理を行い、県道Ｒｐと、経路探索処理によって得られた探索経路Ｆ１上の県道Ｒｐに対応する経路とを、探索コスト等に従って比較し、県道Ｒｐが、県道Ｒｐに対応する経路より探索コストが低いかどうか、すなわち、県道Ｒｐに対応する経路と比較して良好であるかどうかを判断する。
【００６６】
なお、経路比較処理手段は、分割探索処理手段によって得られた二つの地点間の再探索経路、例えば、県道Ｒｐと、探索経路Ｆ１上の二つの地点間の経路、例えば、県道Ｒｐに対応する経路とが同じであるかどうかを判断し、同じでない場合は再探索経路が良好であると判断することができる。さらに、再探索経路決定処理手段９７は、探索経路Ｆ１上の二つの地点間の経路を前記再探索経路に自動的に置き換えることもできる。このように、前記再探索経路決定処理手段９７は、経路比較処理手段による比較結果に基づいて再探索経路を決定する。
【００６７】
そして、前記ＣＰＵ３１の図示されない情報登録処理手段は、県道Ｒｐが、良好である場合、情報登録処理を行い、前記県道Ｒｐを登録する。
【００６８】
そのために、前記情報登録処理手段は、県道Ｒｐが既に登録されているかどうかを判断し、県道Ｒｐが既に登録されている場合、分割探索処理において県道Ｒｐが探索経路Ｆ２に含まれる頻度、県道Ｒｐが登録されることによる改善効果等のデータを更新し、県道Ｒｐが登録されていない場合、県道Ｒｐの道路データをレイヤ２の探索データとしてデータ記録部１６に記録する。
【００６９】
このように、再探索経路が探索され、探索経路Ｆ１上の所定の経路より探索コストの低い分岐道路の探索データを算出することができるので、該探索データを経路探索処理の対象にすることができる。したがって、最適な経路を探索することができる。
【００７０】
この場合、探索データファイルの所定のメモリ領域が県道Ｒｐを登録するために使用され、県道Ｒｐの道路データが分岐道路の探索データとして記録されるほかに、県道Ｒｐの前後の道路、すなわち、前記国道Ｒｎ上の県道Ｒｐが分岐する前の道路の道路データが離脱前道路の探索データとして、前記県道Ｒｐが合流した後の道路の道路データが復帰後道路の探索データとして併せて記録される。
【００７１】
本実施の形態においては、県道Ｒｐ、離脱前道路及び復帰後道路の各道路データが記録されるようになっているが、県道Ｒｐの道路データだけを記録したり、県道Ｒｐが含まれる分割経路の道路データだけを記録したりすることもできる。
【００７２】
このように、前記情報登録処理において、前記探索データファイルに、県道Ｒｐ、離脱前道路及び復帰後道路の各道路データが探索データとして記録されるので、その後、別の機会に、運転者が新たに目的地Ｐｅを設定すると、経路探索処理手段９６は、レイヤ２に、前記県道Ｒｐ、離脱前道路及び復帰後道路の探索データが含まれた探索データファイルを参照して経路を決定する。
【００７３】
すなわち、経路探索処理手段９６は、探索経路Ｆ１上の所定の道路と前記離脱前道路又は復帰後道路とが一致するかどうかを、探索データに付された道路番号等に基づいて判断し、前記所定の道路と前記離脱前道路又は復帰後道路とが一致する場合、探索経路Ｆ１における国道Ｒｎ上の県道Ｒｐに対応する経路を県道Ｒｐに置き換え、探索経路Ｆ２を形成する。
【００７４】
このように、出発地Ｐｓと目的地Ｐｅとの中間地点において、最も下位のレイヤ１だけに存在する分岐道路の道路データを他のレイヤに探索データとして記録し、該探索データをその後の経路探索処理において探索の対象とすることができるので、分岐道路を探索経路に含ませることができる。したがって、最適な経路を探索することができる。
【００７５】
また、分岐道路が登録された後は、登録された分岐道路に対応する分割経路については、経路再探索処理を行う必要がなくなるので、経路再探索処理の処理時間を短くすることができる。
【００７６】
ところで、前記経路再探索処理においては、各レイヤ１〜３について、また、各分割経路ＡＲｉについて分割探索処理を繰り返す必要があるので、経路探索処理が終了した後、直ちに経路再探索処理を開始すると、経路再探索処理が終了するまでに、数十秒又は数分かかってしまう。したがって、最適な経路をリアルタイムで探索することができない。
【００７７】
そこで、本実施の形態においては、運転者が経路探索処理によって得られた探索経路Ｆ１に従って車両を走行させている間に、ＣＰＵ３１の空き時間を利用して、バックグラウンドで経路再探索処理を行うようにしている。したがって、その後、別の機会に、運転者が新たに目的地Ｐｅを設定したときに、情報登録処理が行われた後の探索データに基づいて経路が探索される。なお、バックグラウンドで経路再探索処理が行われた後、直ちに、情報登録処理が行われた後の探索データに基づいて経路を探索し、探索経路Ｆ２に従って車両を走行させることもできる。
【００７８】
ところで、前記経路再探索処理手段９５は、最も下位のレイヤ１から最も上位のレイヤ３までのすべてのレイヤについて経路分割処理及び分割探索処理を行うようになっている。
【００７９】
したがって、例えば、最も上位のレイヤ３について経路分割処理及び分割探索処理を行うと、図９に示されるように、出発地Ｐｓから目的地Ｐｅまで国道Ｒｎを利用する場合より、国道Ｒｎを迂回して高速道路Ｒｈを利用する方が好ましい場合に、高速道路Ｒｈを含む分割経路Ｆ３を最適な経路として探索することができる。
【００８０】
本実施の形態においては、経路探索処理において探索された探索経路Ｆ１を分割して分割経路ＡＲｉを形成するようになっているが、探索経路Ｆ１を分割することなく、最も下位のレイヤ１の範囲を経路再探索処理の対象にして、レイヤ１の範囲を越えるたびに経路再探索処理を行うこともできる。
【００８１】
また、目的地Ｐｅが設定され、経路探索処理が行われた後に、探索経路Ｆ１に離脱前道路及び復帰後道路が含まれる場合において、探索経路Ｆ１における国道Ｒｎ上の県道Ｒｐに対応する経路を県道Ｒｐに置き換え、国道Ｒｎ上の残りの部分について経路を分割し、経路再探索処理を行うこともできる。
【００８２】
次に、図４のフローチャートについて説明する。
ステップＳ１  出発地Ｐｓ及び目的地Ｐｅを入力する。
ステップＳ２  経路探索処理を行う。
ステップＳ３  レイヤ数によるループを開始する。
ステップＳ４  探索経路を分割する。
ステップＳ５  分割経路数によるループを開始する。
ステップＳ６  分割探索処理を行う。
ステップＳ７  県道Ｒｐが良好であるかどうかを判断する。県道Ｒｐが良好である場合はステップＳ８に、良好でない場合はステップＳ９に進む。
ステップＳ８  情報登録処理を行う。
ステップＳ９  分割経路数によるループを終了する。
ステップＳ１０  レイヤ数によるループを終了し、処理を終了する。
【００８３】
次に、図１０のフローチャートについて説明する。
ステップＳ８−１  県道Ｒｐが既に登録されているかどうかを判断する。県道Ｒｐが既に登録されている場合はステップＳ８−３に、登録されていない場合はステップＳ８−２に進む。
ステップＳ８−２  県道Ｒｐを登録する。
ステップＳ８−３  頻度、改善効果等のデータを更新し、リターンする。
【００８４】
次に、探索経路Ｆ１を他の方法で分割するようにした本発明の第２の実施の形態について説明する。
【００８５】
図１１は本発明の第２の実施の形態における経路分割処理手段の動作を示すフローチャートである。
【００８６】
この場合、前記経路分割処理手段は、まず、出発地Ｐｓ（図７）を始点に、目的地Ｐｅを終点に設定し、始点から終点までの探索データに従って探索を行うのに必要なメモリ容量が閾（しきい）値である２〔Ｍｂｙｔｅ〕より大きいかどうかを判断する。メモリ容量が２〔Ｍｂｙｔｅ〕より大きい場合、前記経路分割処理手段は、始点から終点までの経路を二つに分割し、始点と終点との中間点を終点にし、メモリ容量が２〔Ｍｂｙｔｅ〕以下である場合、前記経路分割処理手段は、前記終点を分割点として設定する。続いて、前記経路分割処理手段は、終点と目的地Ｐｅとが一致するかどうかを判断し、終点と目的地Ｐｅとが一致しない場合には、前記終点を始点に、目的地Ｐｅを終点にしてメモリ容量が２〔Ｍｂｙｔｅ〕より大きいかどうかを再び判断する。
【００８７】
このような動作を繰り返すことによって、探索経路Ｆ１に分割経路ＡＲｉを形成することができる。
【００８８】
次に、フローチャートについて説明する。
ステップＳ１１  出発点Ｐｓを始点に、目的地Ｐｅを終点に設定する。
ステップＳ１２  メモリ容量が閾値より大きいかどうかを判断する。メモリ容量が閾値より大きい場合はステップＳ１３に、メモリ容量が閾値以下である場合はステップＳ１４に進む。
ステップＳ１３  始点と終点との中間点を終点に設定し、ステップＳ１２に戻る。
ステップＳ１４  終点を分割点として設定する。
ステップＳ１５  終点と目的地Ｐｅとが一致するかどうかを判断する。終点と目的地Ｐｅとが一致する場合は処理を終了し、一致しない場合はステップＳ１６に進む。
ステップＳ１６  終点を始点に、目的地Ｐｅを終点に設定し、ステップＳ１２に戻る。
【００８９】
ところで、前記第１の実施の形態においては、分割経路ＡＲｉをメモリ容量の許す範囲内で広くするようになっているが、分割経路ＡＲｉを広くしても、分岐道路が一つの分割経路内に収まらず、二つ以上の分割経路に及ぶ場合には、分岐道路を探索経路Ｆ２に含まれるようにすることができない。
【００９０】
そこで、分岐道路が一つの分割経路内に収まらず、二つ以上の分割経路に及ぶ場合でも、分岐道路を探索経路Ｆ２に含まれるようにすることができるようにした本発明の第３の実施の形態について説明する。
【００９１】
図１２は本発明の第３の実施の形態における経路分割処理手段の動作を示すフローチャート、図１３は本発明の第３の実施の形態における経路を分割する動作を説明する第１の図、図１４は本発明の第３の実施の形態における経路を分割する動作を説明する第２の図である。
【００９２】
この場合、経路分割処理手段（図１）は、まず、図１３に示されるように、第１、第２の実施の形態において説明された経路の分割方法に従って探索経路Ｆ３を分割し、分割経路ＡＲ２１、ＡＲ２２を形成する。続いて、前記経路分割処理手段は、既に形成された分割経路ＡＲ２１、ＡＲ２２を取得し、取得された各分割経路ＡＲ２１、ＡＲ２２の中間点を算出し、設定する。次に、前記経路分割処理手段は、出発地Ｐｓを始点に設定し、出発地Ｐｓから近い順に各中間点を読み出し、各中間点を終点に設定するとともに、始点から終点までの探索データに従って探索を行うのに必要なメモリ容量が閾値である２〔Ｍｂｙｔｅ〕より大きいかどうかを判断する。メモリ容量が２〔Ｍｂｙｔｅ〕より大きい場合、前記経路分割処理手段は、始点から、終点より一つ前の中間点までの経路を新しい分割経路として設定する。
【００９３】
例えば、レイヤ２の探索データに従って経路を探索する場合において、図１３に示されるように、１回目の経路分割処理において形成された分割経路ＡＲ２１、ＡＲ２２の探索データに従って経路を探索すると、国道Ｒｎに対する近道となる県道Ｒｐは、二つの分割経路ＡＲ２１、ＡＲ２２に及ぶので、探索経路Ｆ３に含まれない。
【００９４】
これに対して、図１４に示されるように、２回目の経路分割処理において形成された分割経路ＡＲ３１〜ＡＲ３３の探索データに従って経路を探索すると、県道Ｒｐは、一つの分割経路ＡＲ３２内に収まり、複数の分割経路には及ばない。したがって、県道Ｒｐは探索経路Ｆ４に含まれる。
【００９５】
このように、２回目の経路分割処理において分割点をずらして再び分割経路ＡＲｉを形成し、該分割経路ＡＲｉの探索データに従って経路を探索することによって、分割点の周辺の分割経路の質を向上させることができる。したがって、分割探索処理を行うことによって、分岐道路が確実に探索経路に含まれるようにすることができる。
【００９６】
なお、前記中間点は、１回目の経路分割処理において形成された分割経路ＡＲ２１、ＡＲ２２の中央に位置させる必要はなく、分割経路ＡＲ２１、ＡＲ２２上の任意の点に位置させることができる。また、３回目の経路分割処理を行い、１回目及び２回目の経路分割処理において設定された各分割点を避けるように中間点を設定し、更に分割経路を形成することができる。したがって、前記分割探索処理を行うことによって、分岐道路が一層確実に探索経路に含まれるようにすることができる。同様に、経路分割処理を４回以上繰り返し、更に分割経路を形成することもできる。なお、Ｐｅは目的地である。
【００９７】
本実施の形態においては、探索経路Ｆ１の全体を分割して複数の分割経路ＡＲｉを形成するようにしているが、車両の走行に伴って、少なくとも二つの分割点を設定し、各分割点間を分割経路とすることもできる。例えば、車両が所定の距離を走行するごとに、又は所定の時間を走行するごとに車両の走行方向において二つの分割点を設定することができる。
【００９８】
また、分割経路Ｆ１上において、道路属性が変化するごとに分割点を設定することができる。さらに、有料道路優先の探索条件が設定されている場合に、高速・有料道の部分については、分割経路ＡＲｉを形成せず、高速・有料道以外の一般道の部分についてだけ分割経路ＡＲｉを形成することもできる。
【００９９】
次に、フローチャートについて説明する。
ステップＳ２１  既に形成された分割経路ＡＲ２１、ＡＲ２２を取得する。
ステップＳ２２  各分割経路ＡＲ２１、ＡＲ２２の中間点を算出する。
ステップＳ２３  出発地Ｐｓを始点に設定する。
ステップＳ２４  中間点数によるループを開始する。
ステップＳ２５  出発地Ｐｓから近い順に中間点を読み出す。
ステップＳ２６  中間点を終点に設定する。
ステップＳ２７  メモリ容量が閾値より大きいかどうかを判断する。メモリ容量が閾値より大きい場合はステップＳ２８に、メモリ容量が閾値以下である場合はステップＳ３０に進む。
ステップＳ２８  一つ前の中間点までの経路を新しい分割経路として設定する。
ステップＳ２９  一つ前の中間点を始点に設定する。
ステップＳ３０  中間点数によるループを終了し、処理を終了する。
【０１００】
次に、探索データファイルのデータ構造について説明する。なお、探索データファイルにおいて、各分割経路＃０〜＃ｎは、登録された分岐道路を表す。
【０１０１】
図１５は本発明の第４の実施の形態における探索データファイルの例を示す図である。
【０１０２】
図に示されるように、探索データファイルには、探索データファイルのバージョン情報を表すデータバージョン＃０、登録された分岐道路の数を表す分割経路数、分割経路＃０〜＃ｎ等のデータが記録され、各分割経路＃０〜＃ｎのデータとして、各分割経路＃０〜＃ｎが属するレイヤ、各分岐道路に対応させて記録された離脱前道路の道路番号を表す離脱前道路番号、各分岐道路に対応させて記録された復帰後道路の道路番号を表す復帰後道路番号、各分割経路＃０〜＃ｎの探索コスト、探索条件、各分割経路＃０〜＃ｎの道路数、道路＃０〜＃ｎ、上位のレイヤの道路数を表す上位レイヤ道路数、上位のレイヤに属する道路を表す上位レイヤ道路＃０〜＃ｎ等のデータが記録される。
【０１０３】
また、各道路＃０〜＃ｎのデータとして、道路番号、道路形状、道路属性（種別、距離、幅員等の属性）等のデータが記録され、上位レイヤ道路＃０〜＃ｎのデータとして、道路番号、道路形状、道路属性（種別、距離、幅員等の属性）、下位道路の上位道路に対する位置情報等のデータが記録される。
【０１０４】
ところで、情報登録処理において探索データを記録する場合、該探索データのデータ形式を、データ記録部１６（図３）に既に記録されている探索データファイルの探索データのデータ形式に合わせる必要がある。そこで、前述されたように、探索データファイルには、データ形式を認識するためのデータバージョン＃０のデータが記録される。なお、データバージョン＃０のバージョンの探索データファイルには、データバージョン＃０以下の探索データを記録することができる。
【０１０５】
また、一般に、探索経路は道路の列（以下「道路列」という。）から成るので、道路＃０〜＃ｎの列と探索データファイルの探索データとの対応関係を特定するために、各道路＃０〜＃ｎのデータとして道路番号のデータが記録される。
【０１０６】
そして、各分割経路＃０〜＃ｎのデータとして離脱前道路番号及び復帰後道路番号のデータが記録されるので、経路探索処理手段９６は、経路探索処理において得られた探索経路の道路列の各道路に付された道路番号と、前記離脱前道路番号及び復帰後道路番号とを比較し、前記道路番号と前記離脱前道路番号及び復帰後道路番号とが一致する場合に、強制的に離脱前道路と復帰後道路との間の分岐道路に対応する経路を分岐道路の道路列に置き換えることによって、最適な経路を探索することができる。
【０１０７】
また、分岐道路が分岐道路に対応する経路より良好であるかどうかを判断するために、単に探索コストを比較するのではなく、探索条件が一致しているかどうかも併せて判断するのが好ましい。そこで、前記各分割経路＃０〜＃ｎのデータとして探索コスト及び探索条件のデータが記録される。
【０１０８】
そして、分岐道路に対応する経路を分岐道路に置き換えるのに伴って、探索経路表示画面に表示される探索経路が変化する。このとき、探索経路表示処理手段が、地図データから道路形状のデータを読み出して探索経路を表示すると、処理時間が長くなってしまう。そこで、前記各道路＃０〜＃ｎのデータとして道路形状のデータが記録される。したがって、前記探索経路表示処理手段は、道路形状のデータに基づいて探索経路を短い時間で表示することができる。
【０１０９】
さらに、分岐道路が下位のレイヤの探索データに従って探索される場合、上位のレイヤの道路と下位のレイヤの道路との切れ目が異なることがある。その場合、道路番号だけで分岐道路に対応する経路を分岐道路に置き換えると、出発地Ｐｓから目的地Ｐｅまでの距離の情報を整合させることができなくなってしまう。そこで、前記各分割経路＃０〜＃ｎのデータとして、各分岐道路に対応する上位のレイヤに属する道路を表す上位レイヤ道路＃０〜＃ｎのデータが記録される。したがって、経路探索処理の応答性を高くすることができる。
【０１１０】
ところで、図に示されるように、登録された各分岐道路の探索データを、分割経路＃０〜＃ｎの単位で並列に記録すると、経路探索処理において、すべての分岐道路の探索データにアクセスする必要が生じ、経路探索処理の応答性が低くなってしまう。
【０１１１】
そこで、各レイヤ＃０〜＃ｎ、各道路属性＃０〜＃ｎ及び各メッシュ＃０〜＃ｎのデータ要素のうちの一つのデータ要素について階層化し、各データ要素ごとに探索データを記録することによって、経路探索処理の応答性を高くすることができるようにした探索データファイルについて説明する。
【０１１２】
図１６は本発明の第４の実施の形態における探索データファイルの第１の変形例を示す図、図１７は本発明の第４の実施の形態における探索データファイルの第２の変形例を示す図、図１８は本発明の第４の実施の形態における探索データファイルの第３の変形例を示す図である。
【０１１３】
図１６においては、探索データファイルに、データバージョン＃０、分割経路数、分割経路＃０〜＃ｎ等のデータが記録され、各分割経路＃０〜＃ｎのデータとして、各分割経路＃０〜＃ｎのレイヤ数、各分割経路＃０〜＃ｎが属するレイヤ＃０〜＃ｎ等のデータが記録される。また、各レイヤ＃０〜＃ｎのデータには、レイヤ、離脱前道路番号、復帰後道路番号、探索コスト、探索条件、各分割経路＃０〜＃ｎの道路数、道路＃０〜＃ｎ、上位レイヤ道路数、上位レイヤ道路＃０〜＃ｎ等のデータが記録される。
【０１１４】
そして、各道路＃０〜＃ｎのデータとして、道路番号、道路形状、道路属性（種別、距離、幅員等の属性）等のデータが記録され、上位レイヤ道路＃０〜＃ｎのデータとして、道路番号、道路形状、道路属性（種別、距離、幅員等の属性）、下位道路の上位道路に対する位置情報等のデータが記録される。
【０１１５】
この場合、データ要素として各レイヤ＃０〜＃ｎが階層化される。必要なレイヤについてだけ、探索データに従って経路を探索することができるので、経路探索処理の応答性を高くすることができる。例えば、最初の経路探索処理においてレイヤ１の探索データに従って経路が探索された場合には、レイヤ２又は３の探索データに従って経路を探索する必要はない。これは、下位のレイヤの探索データは上位のレイヤの探索データより道路の種別が多く、基本的には良好な経路が探索されているからである。
【０１１６】
また、図１７においては、探索データファイルに、データバージョン＃０、分割経路数、分割経路＃０〜＃ｎ等のデータが記録され、各分割経路＃０〜＃ｎのデータとして、各分割経路＃０〜＃ｎの道路属性数、道路属性＃０〜＃ｎ等のデータが記録される。また、各道路属性＃０〜＃ｎのデータには、レイヤ、離脱前道路番号、復帰後道路番号、探索コスト、探索条件、各分割経路＃０〜＃ｎの道路数、道路＃０〜＃ｎ、上位レイヤ道路数、上位レイヤ道路＃０〜＃ｎ等のデータが記録される。
【０１１７】
そして、各道路＃０〜＃ｎのデータとして、道路番号、道路形状、道路属性（種別、距離、幅員等の属性）等のデータが記録され、上位レイヤ道路＃０〜＃ｎのデータとして、道路番号、道路形状、道路属性（種別、距離、幅員等の属性）、下位道路の上位道路に対する位置情報等のデータが記録される。
【０１１８】
この場合、データ要素として各道路属性＃０〜＃ｎが階層化される。離脱前道路及び復帰後道路の道路属性に従って経路を探索することができるので、経路探索処理の応答性を高くすることができる。例えば、道路属性が道路種別である場合は、離脱前道路及び復帰後道路の道路種別によって、高速・有料道、国道、主要地方道、県道、細街路、導入路等の階層構造で探索データが記録される。したがって、例えば、最初の経路探索処理において得られた探索経路が高速・有料道である場合には、高速・有料道以上のレベルの道路の探索データだけを探索の対象にすることができる。なお、最初の経路探索処理において得られた探索経路がレベルの低い道路である場合に、それ以下の格の道路の探索データだけを探索の対象にすることもできる。
【０１１９】
また、図１８においては、探索データファイルに、データバージョン＃０、分割経路数、分割経路＃０〜＃ｎ等のデータが記録され、各分割経路＃０〜＃ｎのデータとして、各分割経路＃０〜＃ｎのメッシュ数、メッシュ＃０〜＃ｎ等のデータが記録される。また、各メッシュ＃０〜＃ｎのデータには、レイヤ、離脱前道路番号、復帰後道路番号、探索コスト、探索条件、各分割経路＃０〜＃ｎの道路数、道路＃０〜＃ｎ、上位レイヤ道路数、上位レイヤ道路＃０〜＃ｎ等のデータが記録される。
【０１２０】
そして、各道路＃０〜＃ｎのデータとして、道路番号、道路形状、道路属性（種別、距離、幅員等の属性）等のデータが記録され、上位レイヤ道路＃０〜＃ｎのデータとして、道路番号、道路形状、道路属性（種別、距離、幅員等の属性）、下位道路の上位道路に対する位置情報等のデータが記録される。
【０１２１】
この場合、データ要素として各メッシュ＃０〜＃ｎが階層化される。離脱前道路と分岐道路との分岐点を表す離脱ポイント、及び分岐道路と復帰後道路との分岐点を表す復帰ポイントの各座標を利用し、各座標が属するメッシュに従って経路を探索することができるので、経路探索処理の応答性を高くすることができる。なお、メッシュは、日本全国を均等に区切られた領域を表す。
【０１２２】
この場合、経路探索処理において得られた探索経路上の離脱ポイントと復帰ポイントとの中間点を算出し、前記メッシュに対応する位置に分割経路＃０〜＃ｎの各データを記録する。探索経路と交差するメッシュ（探索経路の周辺のメッシュ）の探索データだけを探索の対象にすることができる。
【０１２３】
ところで、前記データ記録部１６（図３）に使用されるＤＶＤ等のディスクを、新しいバージョンのデータベースのものと交換したり、異なるデータ供給会社によって製造されたディスクと交換したりすると、交換する前のディスクのデータベースにおいて道路に付された道路番号と、交換した後のディスクのデータベースにおいて道路に付された道路番号とが一致しない限り、各種のデータを読み出すことができない。
【０１２４】
また、経路再探索処理によって登録された分岐道路の探索データも、ディスクの変更に伴って読み出すことができなくなってしまう。
【０１２５】
そこで、既存のデータベースを、異なるバージョンのデータベース、異なるデータ供給会社によって製造されたデータベース等に交換したときに、探索データを読み出すことができるようにした本発明の第５の実施の形態について説明する。
【０１２６】
図１９は本発明の第５の実施の形態における探索データファイルを示す図である。
【０１２７】
図に示されるように、データベースを構成する探索データファイルに、近道数、近道＃０〜＃ｎ等のデータが記録され、各近道＃０〜＃ｎのデータとして、データバージョン＃０、分割経路数、分割経路＃０〜＃ｎ等のデータが記録され、各分割経路＃０〜＃ｎのデータとして、各分割経路＃０〜＃ｎが属するレイヤ、離脱前道路番号、復帰後道路番号、探索コスト、探索条件、道路数、道路＃０〜＃ｎ、上位レイヤ道路数、上位レイヤ道路＃０〜＃ｎ等のデータが記録される。
【０１２８】
そして、前記離脱前道路番号、復帰後道路番号及び各道路＃０〜＃ｎのデータとして、それぞれ道路番号、道路形状、道路属性（種別、距離、幅員等の属性）等のデータが記録され、上位レイヤ道路＃０〜＃ｎのデータとして、道路番号、道路形状、道路属性（種別、距離、幅員等の属性）、下位道路の上位道路に対する位置情報等のデータが記録される。
【０１２９】
この場合、前記離脱前道路番号及び復帰後道路番号を特定するためのデータとして道路番号、道路形状、道路属性（種別、距離、幅員等の属性）等のデータが記録されるので、経路再探索処理手段９５は、交換された後の探索データファイルの探索データの中から、道路形状、道路属性（種別、距離、幅員等の属性）等に基づいて、新たに離脱前道路番号及び復帰後道路番号を検出することができる。そして、前記経路再探索処理手段９５は、交換された後の探索データファイルの離脱前道路を出発地Ｐｓとし、復帰後道路を目的地Ｐｅとして設定し、再び各レイヤ１〜３について探索データに従って経路を探索する。また、前記情報登録処理手段は、経路再探索処理において得られた探索経路に基づいて分岐道路を登録する。
【０１３０】
このようにして、交換される前のデータベースにおいて記録された、前記離脱前道路番号及び復帰後道路番号の道路形状、道路属性（種別、距離、幅員等の属性）等によって、交換された後のデータベースにおいて分岐道路を登録することができる。
【０１３１】
したがって、既存のデータベースを、異なるバージョンのデータベース、異なるデータ供給会社によって製造されたデータベース等に交換したときに、探索データを読み出すことができる。
【０１３２】
次に、情報基地と車載端末との間でデータベースを送受信することができるようにしたナビゲーションシステムについて説明する。
【０１３３】
図２０は本発明の第５の実施の形態におけるナビゲーションシステムを示す第１のブロック図、図２１は本発明の第５の実施の形態におけるナビゲーションシステムを示す第２のブロック図、図２２は本発明の第５の実施の形態における参照用データのデータ構成を示す図である。
【０１３４】
図２０において、５０はナビゲーションシステム、６１は前記ナビゲーション装置１４（図３）によって構成される車載端末、５１は情報基地、５２は該情報基地５１と車載端末６１とを接続する情報ネットワーク、５３は前記情報基地５１に配設されたサーバであり、情報基地５１と車載端末６１との間で、各種のプログラム、データ等の送受信を行うことができる。そのために、前記車載端末６１の通信部３８は送受信装置を備える。また、前記サーバ５３は、演算装置としてのＣＰＵ５４、ＲＡＭ５５、ＲＯＭ５６、図示されない通信インタフェース等を備え、コンピュータを構成する。また、前記サーバ５３及び車載端末６１のナビゲーション処理部１７によってコンピュータを構成することもでき、更にコンピュータに他の演算装置を含ませることもできる。
【０１３５】
そして、前記情報基地５１が情報センタである場合、情報センタに前記サーバ５３としてナビゲーション用サーバが配設され、前記情報センタと車載端末６１とが情報ネットワーク５２としての通信回線網を介して接続され、情報基地５１がプロバイダである場合、該プロバイダにサーバ５３としてインターネット用サーバが配設され、前記プロバイダと車載端末６１とがサーバ５３としてのインターネット網を介して接続され、情報基地５１が基地局である場合、該基地局に基地局用サーバが配設され、前記基地局と車載端末６１とがサーバ５３としてのＦＭ多重放送網、電話回線網等を介して接続される。
【０１３６】
前記サーバ５３は、地図データファイル、道路データファイル、交差点データファイル、ノードデータファイル、探索データファイル、案内データファイル、施設データファイル等から成るデータベースをナビゲーション情報として記録する情報記録部としての記録装置５７を備え、該記録装置５７に各種のデータが記録される。
【０１３７】
前記車載端末６１において、通信部３８によって各種のプログラム、データ等が受信されると、前記ナビゲーション処理部１７のＣＰＵ３１は、例えば、ＲＡＭ３２、フラッシュメモリ、ハードディスク等にダウンロードし、前記プログラムを起動し、前記データに基づいて各種の処理を行う。すなわち、前記ＣＰＵ３１は、前記データベースをＲＡＭ３２、フラッシュメモリ、ハードディスク等の記録媒体にダウンロードし、前記データベースの各データに基づいて各種の処理を行う。なお、プログラムとデータとを互いに異なる記録媒体に記録したり、同じ記録媒体に記録したりすることもできる。
【０１３８】
また、家庭用のパソコンを使用して、前記情報基地５１から送信されたプログラム、データ等を、パソコンに対して着脱自在なメモリカード、フレキシブルディスク等の外部の記録媒体にダウンロードし、前記プログラムを起動し、データに基づいて各種の処理を行うこともできる。
【０１３９】
ところで、サーバ５３は、各種のデータを管理することができるので、ＣＰＵ３１は、サーバ５３に対して探索データに関する問合せを行うことによって、交換された後のデータベースにおいて分岐道路を登録し、該分岐道路の探索データを読み出すことができる。そのために、前記情報基地５１と複数の車載端末６１とが接続されるとともに、情報基地５１のサーバ５３において、各データベースごとの離脱前道路番号及び復帰後道路番号の対応表が、図２２に示されるような参照用データとしてＲＯＭ５６に記録される。
【０１４０】
なお、前記参照用データには、各データベースＡ〜Ｃごとに、離脱前道路番号及び復帰後道路番号から成る道路＃Ａ１〜＃Ａｎ、＃Ｂ１〜＃Ｂｎ、＃Ｃ１〜＃Ｃｎのデータが記録される。
【０１４１】
したがって、前記ＣＰＵ３１の分割探索処理手段（図１）は、交換される前のデータベースの離脱前道路番号及び復帰後道路番号をサーバ５３に送ることによって、交換された後のデータベースの離脱前道路番号及び復帰後道路番号をサーバ５３から受け、交換された後のデータベースの離脱前道路を出発地Ｐｓとし、復帰後道路を目的地Ｐｅとして設定し、再び各レイヤ１〜３について探索データに従って経路を探索する。また、前記ＣＰＵ３１の図示されない情報登録処理手段は、経路再探索処理において得られた探索経路に基づいて分岐道路を登録する。
【０１４２】
なお、各実施の形態においては、ＣＰＵ３１に分割探索処理手段及び情報登録処理手段を配設するようになっているが、サーバ５３のＣＰＵ５４に図示されない分割探索処理手段及び情報登録処理手段を配設し、車載端末６１から受けた離脱前道路番号及び復帰後道路番号に基づいて、経路を探索し、経路再探索処理において得られた探索経路に基づいて分岐道路を登録することもできる。
【０１４３】
また、情報基地５１と接続された各車載端末６１との間において共通のデータベースを保有することもできる。そのために、共通のデータベースがサーバ５３によって管理され、例えば、サーバ５３の図示されない情報管理処理手段は、情報管理処理を行い、各車載端末６１からデータベースを受けると、既に保持しているデータベースと車載端末６１から受けたデータベースとを比較し、共通の探索データ以外の探索データを記録装置５７に記録する。
【０１４４】
したがって、各車載端末６１においては、他の車載端末６１から供給された分岐道路の探索データを利用することができる。
【０１４５】
また、各ＣＰＵ３１の目的地設定処理手段９３は、目的地設定処理を行い、目的地Ｐｅを設定し、目的地Ｐｅのデータをサーバ５３に送ることができる。そして、ＣＰＵ５４に図示されない経路探索処理手段、経路分割処理手段及び分割探索処理手段が配設され、経路探索処理を行い、経路探索処理によって得られた探索経路を分割し、分割経路に基づいて再び経路を探索し、分岐道路を登録することができる。
【０１４６】
なお、本発明は前記実施の形態に限定されるものではなく、本発明の趣旨に基づいて種々変形させることが可能であり、それらを本発明の範囲から排除するものではない。
【０１４７】
【発明の効果】
以上詳細に説明したように、本発明によれば、各分割された経路についてナビゲーション情報に従って経路が再び探索されるので、再探索による探索経路を経路探索処理の対象にすることができる。したがって、最適な経路を探索することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態におけるナビゲーションシステムの機能ブロック図である。
【図２】従来の経路探索処理の動作を説明する図である。
【図３】本発明の第１の実施の形態におけるナビゲーションシステムの要部を示すブロック図である。
【図４】本発明の第１の実施の形態におけるナビゲーション装置の動作を示すフローチャートである。
【図５】本発明の第１の実施の形態における探索データの階層構造を示す図である。
【図６】本発明の第１の実施の形態におけるレイヤの構成を示す図である。
【図７】本発明の第１の実施の形態における経路を分割する動作を説明する第１の図である。
【図８】本発明の第１の実施の形態における経路を分割する動作を説明する第２の図である。
【図９】本発明の第１の実施の形態における経路を分割する動作を説明する第３の図である。
【図１０】本発明の第１の実施の形態における情報登録処理のサブルーチンを示す図である。
【図１１】本発明の第２の実施の形態における経路分割処理手段の動作を示すフローチャートである。
【図１２】本発明の第３の実施の形態における経路分割処理手段の動作を示すフローチャートである。
【図１３】本発明の第３の実施の形態における経路を分割する動作を説明する第１の図である。
【図１４】本発明の第３の実施の形態における経路を分割する動作を説明する第２の図である。
【図１５】本発明の第４の実施の形態における探索データファイルの例を示す図である。
【図１６】本発明の第４の実施の形態における探索データファイルの第１の変形例を示す図である。
【図１７】本発明の第４の実施の形態における探索データファイルの第２の変形例を示す図である。
【図１８】本発明の第４の実施の形態における探索データファイルの第３の変形例を示す図である。
【図１９】本発明の第５の実施の形態における探索データファイルを示す図である。
【図２０】本発明の第５の実施の形態におけるナビゲーションシステムを示す第１のブロック図である。
【図２１】本発明の第５の実施の形態におけるナビゲーションシステムを示す第２のブロック図である。
【図２２】本発明の第５の実施の形態における参照用データのデータ構成を示す図である。
【符号の説明】
１６    データ記録部
１７    ナビゲーション処理部
３１    ＣＰＵ
５０    ナビゲーションシステム
５３    サーバ
５７    記録装置
９２    情報取得処理手段
９３    目的地設定処理手段
９５    経路再探索処理手段
９６    経路探索処理手段
９７    再探索経路決定処理手段
【図１】
0003753045.tif 000002
【図２】
0003753045.tif 000003
【図３】
0003753045.tif 000004
【図４】
0003753045.tif 000005
【図５】
0003753045.tif 000006
【図６】
0003753045.tif 000007
【図７】
0003753045.tif 000008
【図８】
0003753045.tif 000009
【図９】
0003753045.tif 000010
【図１０】
0003753045.tif 000011
【図１１】
0003753045.tif 000012
【図１２】
0003753045.tif 000013
【図１３】
0003753045.tif 000014
【図１４】
0003753045.tif 000015
【図１５】
0003753045.tif 000016
【図１６】
0003753045.tif 000017
【図１７】
0003753045.tif 000018
【図１８】
0003753045.tif 000019
【図１９】
0003753045.tif 000020
【図２０】
0003753045.tif 000021
【図２１】
0003753045.tif 000022
【図２２】
0003753045.tif 000023