(57)【要約】  【課題】タイムゾーンが異なる地域を跨いで経路探索する場合でも、時間規制を考慮した推奨経路を探索する技術を提供することにある。  【解決手段】  ナビゲーション装置は、地図上の道路を構成する各リンクの時間規制情報を含むリンクデータと前記各リンクの属すタイムゾーンを判別するためのタイムゾーン情報とを含む地図データを記憶する記憶装置を有している。そして、出発地と目的地を設定し、地図データを用いて出発地・目的地間の推奨経路を探索する。経路探索は、時間規制情報とタイムゾーン情報とに基づいて、そのリンクの到着予想時刻において時間規制されているリンクを除外して行う。また、各リンクは、異なるタイムゾーンに跨って存在しないようする。異なるタイムゾーンに跨って存在するリンクを、タイムゾーン境界線で分割した複数のリンクとして扱う。【選択図】図７
2005121425.tif 000002
【特許請求の範囲】
【請求項１】
ナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、
地図上の道路を構成する各リンクの時間規制情報を含むリンクデータと前記各リンクの属すタイムゾーンを判別するためのタイムゾーン情報とを記憶する記憶装置を有し、
出発地と目的地を設定するステップと、
前記リンクデータと前記タイムゾーン情報とを用いて、前記出発地・目的地間の推奨経路を探索する経路探索ステップとを行う
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項２】
請求項１に記載のナビゲーション装置の経路探索方法であって、
前記経路探索ステップは、
前記時間規制情報と前記タイムゾーン情報とに基づいて、そのリンクの到着予想時刻において時間規制されているリンクを除外して、前記出発地・目的地間の推奨経路を探索する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項３】
ナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、
地図上の道路を構成する各リンクの時間規制情報を含むリンクデータと前記各リンクの属すタイムゾーンを判別するためのタイムゾーン情報とを記憶する記憶装置を有し、
出発地と目的地を設定するステップと、
前記リンクデータと前記タイムゾーン情報とを用いて、前記出発地・目的地間の推奨経路を探索する経路探索ステップとを行い、
前記リンクデータに含まれる各リンクは、異なるタイムゾーンに跨って存在しないように定められている
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項４】
ナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、
地図上の道路を構成する各リンクの時間規制情報を含むリンクデータと前記各リンクの属すタイムゾーンを判別するためのタイムゾーン情報とを記憶する記憶装置を有し、
出発地と目的地を設定するステップと、
前記リンクデータと前記タイムゾーン情報とを用いて、前記出発地・目的地間の推奨経路を探索する経路探索ステップとを行い、
前記経路探索ステップは、前記地図データに含まれるリンクうち、異なるタイムゾーンに跨って存在するリンクを、タイムゾーン境界線で分割した複数のリンクとして扱う
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項５】
ナビゲーション装置であって、
地図上の道路を構成する各リンクの時間規制情報を含むリンクデータと前記各リンクの属すタイムゾーンを判別するためのタイムゾーン情報とを記憶する記憶装置と、
出発地と目的地を設定する手段と、
前記リンクデータと前記タイムゾーン情報とを用いて、前記出発地・目的地間の推奨経路を探索する経路探索手段とを有する
ことを特徴とするナビゲーション装置。
【請求項６】
ナビゲーション装置であって、
地図上の道路を構成する各リンクの時間規制情報を含むリンクデータと前記各リンクの属すタイムゾーンを判別するためのタイムゾーン情報とを記憶する記憶装置と、
出発地と目的地を設定する手段と、
前記リンクデータと前記タイムゾーン情報とを用いて、前記出発地・目的地間の推奨経路を探索する経路探索手段とを有し、
前記リンクデータに含まれる各リンクは、異なるタイムゾーンに跨って存在しないように定められている
ことを特徴とするナビゲーション装置。
【請求項７】
ナビゲーション装置であって、
地図上の道路を構成する各リンクの時間規制情報を含むリンクデータと前記各リンクの属すタイムゾーンを判別するためのタイムゾーン情報とを記憶する記憶装置と、
出発地と目的地を設定する手段と、
前記リンクデータと前記タイムゾーン情報とを用いて、前記出発地・目的地間の推奨経路を探索する経路探索手段とを行い、
前記経路探索手段は、前記リンクデータに含まれるリンクうち、異なるタイムゾーンに跨って存在するリンクを、タイムゾーン境界線で分割した複数のリンクとして扱う機能を有する
ことを特徴とするナビゲーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置に関し、特に車載用ナビゲーション装置の経路探索技術に関する。
【背景技術】
【０００２】
特許文献１には、地図データに基づいて出発地から目的地までの推奨経路、特に、道路の時間規制を考慮して推奨経路を探索する車載用ナビゲーション装置が記載されている。
【０００３】
この車載用ナビゲーション装置においては、まず、時間規制のある道路について、その道路までの予想到着時刻を算出する。そして、その予想到着時刻において、その道路が通行可能か否かを調べ、通行可能であればその道路を経路探索の対象として採用する。一方、通行不可能であれば、経路探索の対象から除外している。このような処理を経路探索処理の中で行い、時間規制を考慮した推奨経路を探索している。
【０００４】
【特許文献１】特開平１１−１３２７７６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、特許文献１の技術は、異なるタイムゾーンが存在する場合を考慮していない。これでは、出発地から目的地までの経路が、異なるタイムゾーンに跨っている場合、時間規制を考慮した適切な経路探索は行えない。
【０００６】
本発明は上記事情に鑑みてなされたものであり、本発明の目的は、タイムゾーンが異なる地域を跨いで経路探索する場合でも、時間規制を考慮した推奨経路を探索する技術を提供することにある。
【課題を解決するための手段】
【０００７】
上記課題を解決すべく、本発明のナビゲーション装置の経路探索方法は、時間規制情報を含むリンクデータとタイムゾーン情報とを用いて出発地・目的地間の推奨経路を探索する。
【０００８】
また、本発明のナビゲーション装置の経路探索方法は、例えば、以下のように構成される。ナビゲーション装置は、地図上の道路を構成する各リンクの時間規制情報を含むリンクデータと前記各リンクの属すタイムゾーンを判別するためのタイムゾーン情報とを記憶する記憶装置を有している。そして、前記ナビゲーション装置は、出発地と目的地を設定するステップと、前記リンクデータと前記タイムゾーン情報とを用いて、前記出発地・目的地間の推奨経路を探索する経路探索ステップとを行う。前記経路探索ステップは、前記時間規制情報と前記タイムゾーン情報とに基づいて、そのリンクの到着予想時刻において時間規制されるリンクを除外して、前記出発地・目的地間の推奨経路を探索するようにしてもよい。
【０００９】
また、前記リンクデータに含まれる各リンクは、異なるタイムゾーンに跨って存在しないように定めるようにしてもよい。
【００１０】
また、前記経路探索ステップは、前記地図データに含まれるリンクうち、異なるタイムゾーンに跨って存在するリンクを、タイムゾーン境界線で分割した複数のリンクとして扱うようにしてもよい。
【発明の効果】
【００１１】
本発明によれば、タイムゾーンが異なる地域を跨いで経路探索する場合でも、時間規制を考慮した推奨経路を探索できる。
【発明を実施するための最良の形態】
【００１２】
以下に、本発明の一実施形態について、図面を参照して説明する。
【００１３】
図１は、本発明の一実施形態が適用された車載用ナビゲーション装置の概略構成図である。
【００１４】
図示するように、本実施形態の車載用ナビゲーション装置は、演算処理部１と、ディスプレイ２と、地図データ記憶装置３と、音声入出力装置４と、入力装置５と、車輪速センサ６と、地磁気センサ７と、ジャイロセンサ８と、ＧＰＳ(Ground Positioning System)受信装置９と、車内ＬＡＮ装置１１と、を有する。
【００１５】
演算処理部１は、様々な処理を行う中心的ユニットである。例えば、各種センサ６〜８やＧＰＳ受信装置９から出力される情報を基にして現在地を検出し、得られた現在地情報に基づいて、表示に必要な地図データを地図データ記憶装置３から読み出す。また、読み出した地図データ３１０をグラフィックス展開し、そこに現在地を示すマークを重ねてディスプレイ２へ表示したり、地図データ記憶装置３に記憶されている地図データ３１０を用いて、ユーザから指示された目的地と出発地（例えば現在地）とを結ぶ最適な経路（推奨経路）を探索し、音声入出力装置４やディスプレイ２を用いてユーザを誘導したりする。
【００１６】
ディスプレイ２は、演算処理部１で生成されたグラフィックス情報を表示するユニットで、ＣＲＴや液晶ディスプレイなどで構成される。また、演算処理部１とディスプレイ２との間の信号Ｓ１は、ＲＧＢ信号やＮＴＳＣ（National Television System Committee）信号で接続するのが一般的である。
【００１７】
地図データ記憶装置３は、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭやＨＤＤやＩＣカードといった記憶媒体で構成されている。この記憶媒体には、地図データが記憶されている。
【００１８】
図２は、地図データ記憶装置３に記憶されている地図データの構成例を示す図である。図示するように、地図を複数に分割することで得られるメッシュ領域毎に地図データ３１０が記憶されている。地図データ３１０は、メッシュ領域の識別コード（メッシュＩＤ）３１１、および、そのメッシュ領域に含まれる道路を構成する各リンクのリンクデータ３１２を有する。リンクデータ３１２は、リンクの識別コード（リンクＩＤ）３１２１、リンクを構成する２つのノード（開始ノード、終了ノード）の座標情報３１２２、リンクを含む道路の種別情報３１２３、リンクの長さを示すリンク長情報３１２４、リンクの旅行時間（あるいは移動速度）情報３１２５、時間規制情報３１２７、２つのノードにそれぞれ接続するリンクのリンクＩＤ（接続リンクＩＤ）３１２６などを有する。
【００１９】
時間規制情報３１２７は、そのリンクの通行が規制（禁止）されている時間帯情報を含む。また、日にちにより時間規制の時間帯が異なる場合は、その情報も含む。なお、時間規制情報３１２７に含まれる時刻は、そのリンクの属するタイムゾーンにおける時刻である。
【００２０】
なお、ここでは、リンクを構成する２つのノードについて開始ノードと終了ノードとを区別することで、同じ道路の上り方向と下り方向とを、それぞれ別のリンクとして管理するようにしている。また、地図データ３１０には、対応するメッシュ領域に含まれている道路以外の地図構成物の情報（名称、種別、座標情報など）も含まれている。
【００２１】
また、リンクデータ３１２には、タイムゾーン情報３２０が含まれている。タイムゾーン情報３２０は、各リンクが属するタイムゾーンの情報である。この情報は、図３に示すように、リンクＩＤ３２２ごとにそのリンクが属するタイムゾーン３２３が対応付けられて記憶されている。また、夏時間・冬時間等のように、同一地域でも期間によってタイムゾーンが異なる地域に属すリンクについては、そのタイムゾーンとなる期間の情報３２４も記憶されている。
【００２２】
また、地図データ３１０には、タイムゾーン間の時差情報３３０が含まれている。この情報は、図４に示すように、タイムゾーン３３１ごとにタイムゾーン３３２との時間差３３３が対応付けられて記憶されている。図４においては、タイムゾーン３３１の時刻は、タイムゾーン３３２の時刻に時間差３３３を足した時刻と等しいことを示す。
【００２３】
図１に戻って説明を続ける。音声入出力装置４は、演算処理部１で生成したユーザへのメッセージを音声信号に変換し出力すると共に、ユーザが発した声を認識し演算処理部１にその内容を転送する処理を行う。
【００２４】
入力装置５は、ユーザからの指示を受け付けるユニットで、スクロールキー、縮尺変更キーなどのハードスイッチ、ジョイスティック、ディスプレイ上に貼られたタッチパネルなどで構成される。
【００２５】
センサ６〜８およびＧＰＳ受信装置９は、車載用ナビゲーション装置で現在地（自車位置）を検出するために使用するものである。車輪速センサ６は、車輪の円周と計測される車輪の回転数の積から距離を測定し、さらに対となる車輪の回転数の差から移動体が曲がった角度を計測する。地磁気センサ７は、地球が保持している磁場を検知し、移動体が向いている方角を検出する。ジャイロ８は、光ファイバジャイロや振動ジャイロ等で構成され、移動体が回転した角度を検出するものである。ＧＰＳ受信装置９は、ＧＰＳ衛星からの信号を受信し移動体とＧＰＳ衛星間の距離と距離の変化率を３個以上の衛星に対して測定することで移動体の現在地、進行方向および進行方位を測定する。
【００２６】
図５は、演算処理部１のハードウェア構成を示す図である。
【００２７】
図示するように、演算処理部１は、各デバイス間をバス３２で接続した構成としてある。演算処理部１は、数値演算及び各デバイスを制御するといった様々な処理を実行するＣＰＵ(Central Processing Unit)２１と、地図データ記憶装置３から読み出した地図データや演算データを格納するＲＡＭ(Random Access Memory)２２と、プログラムやデータを格納するＲＯＭ(Read Only Memory)２３と、メモリ間およびメモリと各デバイスとの間のデータ転送を実行するＤＭＡ（Direct Memory Access）２４と、グラフィックス描画を実行し且つ表示制御を行う描画コントローラ２５と、グラフィックスイメージデータを蓄えるＶＲＡＭ(Video Random Access Memory)２６と、イメージデータをＲＧＢ信号に変換するカラーパレット２７と、アナログ信号をデジタル信号に変換するＡ/Ｄ変換器２８と、シリアル信号をバスに同期したパラレル信号に変換するＳＣＩ(Serial Communication Interface)２９と、パラレル信号をバスに同期させてバス上にのせるＰＩＯ(Parallel Input/Output)３０と、パルス信号を積分するカウンタ３１と、を有する。
【００２８】
図６は、演算処理部１の機能構成を示す図である。
【００２９】
図示するように、演算処理部１は、ユーザ操作解析部４１と、経路探索部４２と、経路記憶部４３と、経路誘導部４４と、地図表示処理部４５と、現在位置演算部４６と、マップマッチ処理部４７と、データ読込部４８と、軌跡記憶部４９と、メニュー表示処理部５０と、グラフィックス処理部５１とを有する。
【００３０】
現在位置演算部４６は、車輪速センサ６で計測される距離パルスデータＳ５およびジャイロ８で計測される角加速度データＳ７を各々積分した結果得られる距離データおよび角度データを用い、そのデータを時間軸で積分していくことにより、初期位置（Ｘ，Ｙ）から自車走行後の位置である現在地（Ｘ′，Ｙ′）を定期的に演算し、マップマッチ処理部４７に出力する処理を行う。ここで、自車の回転した角度と進む方位との関係を一致させるため、地磁気センサ７から得られる方位データＳ６と、ジャイロ８から得られる角加速度データＳ７を積分した角度データとを参照して、自車が進行している方向の絶対方位を推定する。なお、車輪速センサ６のデータおよびジャイロ８のデータを各々積分してゆくと、誤差が蓄積するため、ある時間周期でＧＰＳ受信装置９から得られた位置データＳ８をもとに蓄積した誤差をキャンセルするという処理を施して、現在地の情報をマップマッチ処理部４７に出力する。
【００３１】
マップマッチ処理部４７は、データ読込部４８によって読み込まれた現在地周辺の地図データと、後述する軌跡記憶部４９に記憶されている走行軌跡とを互いに照らし合わせ、形状の相関が最も高い道路（リンク）上に、現在位置演算部４６より出力された現在地を合わせ込むというマップマッチ処理を行う。現在位置演算部４６で得られる現在地の情報にはセンサ誤差が含まれているため、さらに位置精度を高めることを目的に、マップマッチ処理を行う。これにより、現在地は、多くの場合、走行道路と一致するようになる。
【００３２】
軌跡記憶部４９は、マップマッチ処理部４７でマップマッチ処理が施された現在地の情報を、軌跡データとして自車が所定距離走行する度に記憶する。なお、この軌跡データは、これまで走行してきた道路につき、対応する地図上の道路に軌跡マークを描画するために用いられる。
【００３３】
ユーザ操作解析部４１は、入力装置５に入力されたユーザからの要求を受け、その要求内容を解析して、その要求内容に対応する処理が実行されるように演算処理部１の各部を制御する。例えば、ユーザが推奨経路の探索を要求したときは、出発地および目的地を設定するため、地図をディスプレイ２に表示する処理を地図表示部４５に要求し、さらに、出発地から目的地までの経路を演算する処理を経路探索部４２に要求する。
【００３４】
経路探索部４２は、ダイクストラ法等を用いて、指定された２地点（出発地、目的地）間を結ぶ経路のうち少ないコスト（例えば、旅行時間や旅行距離など）で目的地へ到達可能な経路を、地図データから検索し、その結果得られた経路を推奨経路として経路記憶部４３に蓄える。
【００３５】
経路誘導部４４は、経路記憶部４３に蓄えられた推奨経路の情報と、マップマッチ処理部４７から出力された現在地の情報とを比較し、交差点等を通過する前に直進すべきか、右左折すべきかを音声出入力装置４を用いて音声でユーザに知らせたり、ディスプレイ２に表示された地図上に進行すべき方向を表示して、ユーザに推奨経路を通知したりする。
【００３６】
また、経路誘導部４４は、現在時刻と地図データ記憶装置３に記憶されている地図データとを用いて、マップマッチ処理部４７から出力された現在地から目的地までの予想旅行時間を計算する。そして、計算した予想旅行時間を現在時刻に加算することで、目的地への予想到着時刻を算出し、ユーザに通知する。
【００３７】
データ読込部４８は、ディスプレイ２への表示が要求される領域や、経路探索のために要求される領域（出発地および目的地を含む領域）にある地図データを、地図データ記憶装置３から読み込み準備するように動作する。
【００３８】
地図表示処理部４５は、ディスプレイ２への表示が要求される領域にある地図データをデータ読込部４８から受け取り、グラフィック処理部５１が、指定された縮尺、描画方式で、道路、その他の地図構成物や、現在地、目的地、誘導経路のための矢印といったマークを描画するように、地図描画コマンドを生成する。
【００３９】
メニュー表示処理部５０は、ユーザ操作解析部４１から出力される命令を受け、グラフィック処理部５１が、様々な種類のメニューやグラフなどを描画するようにメニュー描画コマンドを生成する。
【００４０】
グラフィックス処理部５１は、地図表示処理部４５およびメニュー表示処理部５０で生成されたコマンドを受け、ディスプレイ２に表示する画像データをＶＲＡＭ２６にイメージ展開する。
【００４１】
以上のように構成される車載用ナビゲーション装置１０００は、地図データをもとにして、時間規制されているリンクを除外して、出発地・目的地間の経路探索を行う。また、異なるタイムゾーンに属す地域に跨って経路探索を行う場合は、時差を考慮して、時間規制のあるリンクへの予想到着時刻を算出し、その予想到着時刻において時間規制がされているかを判定する。そして、時間規制されている場合は、そのリンクを除外して経路探索を行う。
【００４２】
［動作の説明］次に、上記構成の車載用ナビゲーション装置の動作について説明する。
【００４３】
図７は、本実施形態が適用された車載用ナビゲーション装置の推奨経路探索動作を説明するためのフロー図である。このフローは、ユーザ操作解析部４１が、音声入出力装置４あるいは入力装置５を介してユーザより推奨経路の探索要求を受け付けることで開始される。
【００４４】
まず、ユーザ操作解析部４１は、出発地（現在地）、目的地および出発時刻を経路探索部４３に設定する（Ｓ１０１）。
【００４５】
ここで、設定する出発地および目的地は、ユーザ操作解析部４１が、メニュー表示処理部５０およびグラフィックス処理部５１を介してディスプレイ２に、データ読込部４８を介して地図データ記憶装置３から読み込んだ地図データに登録されている地図構成物の情報を表示させ、音声入出力装置４あるいは入力装置５を介してユーザより、この表示中の地図構成物の情報の中から選択させるようにしてもよい。あるいは、ユーザによって予めＲＡＭ２２などの記憶装置に登録されている地点（登録地）の情報を表示させ、音声入出力装置４あるいは入力装置５を介してユーザより、この表示中の登録地の情報の中から選択させるようにしてもよい。さらには、ユーザ操作解析部４１が、地図表示処理部４５およびグラフィックス処理部５１を介してディスプレイ２に、データ読込部４８を介して地図データ記憶装置３から読み込んだ地図データより特定される地図を表示させ、音声入出力装置４あるいは入力装置５を介してユーザより、地図上にて地点の指定を受け付けることで、選択されるようにしてもよい。
【００４６】
なお、現在地を出発地に設定する場合は、ユーザによる出発地の指定を省略してもよい。また、現在時刻を出発時刻に設定する場合も、ユーザによる出発時刻の指定を省略してもよい。
【００４７】
以上のようにして出発地、目的地および出発時刻が経路探索部４２に設定されたならば、ユーザ操作解析部４１は、経路探索部４２に経路探索指示を出力する。
【００４８】
これを受けて、経路探索部４２は、出発地から目的地までの推奨経路を探索する（Ｓ１０２）。具体的には、まず、経路探索部４２は、データ読込部４８を介して地図データ記憶装置３より、座標情報（経度、緯度等）に基づいて計算により、出発地・目的地を含むメッシュ領域のメッシュＩＤを特定する。次に、データ読込部４８を介して地図データ記憶装置３より、特定したメッシュＩＤを持つ地図データ３１各々に登録されている各リンクデータ３１２を入手する。
【００４９】
次に、経路探索部４２は、Ｓ１０２で入手した各リンクデータ３１２を用いて、後述するＳ１１８でヒープテーブルから抽出された抽出リンクの終了ノードを開始ノードとするリンクを、推奨経路を構成する候補リンクとして選出する（Ｓ１０４）。ただし、Ｓ１１８での処理が行われていない場合、つまり、ヒープテーブルにリンクが登録されていない初期段階では、抽出リンクの終了ノードを開始ノードとするリンクを候補リンクとして選出する代わりに、出発地が存在あるいは出発地に近接する少なくとも１つのリンクを、候補リンクとして選出する。
【００５０】
次に、経路探索部４２は、候補リンクの中から、時間規制中のリンクを除外する（Ｓ１０６）。図８は、候補リンクの中から、時間規制中のリンクを除外する処理の流れを示すフロー図である。
【００５１】
まず、経路探索部４２は、候補リンクの開始ノードへの到着予想時刻を求める（Ｓ２０１）。具体的には、まず、抽出リンクの終了ノードへの到着予想時刻を求める。抽出リンクの終了ノードへの到着予想時刻は、出発時刻に、ヒープテーブルに登録されている抽出リンクの総旅行時間を加算することで算出できる。そして、求めた到着予想時刻を候補リンクの開始ノードへの到着予想時刻とする。
【００５２】
次に、経路探索部４２は、タイムゾーン情報３２０を参照して候補リンクが抽出リンク（候補リンクの前のリンク）と同じタイムゾーンに属すか否かを判定する（Ｓ２０２）。同じタイムゾーンに属す場合（Ｓ２０２でＹｅｓ）、Ｓ２０４に処理を移行する。なお、夏時間・冬時間のように同じ地域でも期間によって異なるタイムゾーンが定められている地域に属すリンクについては、現在の日にちとタイムゾーン情報３２０（例えば、図３の３２４のように期間情報を含むタイムゾーン情報）から、候補リンクが抽出リンク（候補リンクの前のリンク）と同じタイムゾーンに属すか否かを判定する
一方、候補リンクが抽出リンク（候補リンクの前のリンク）と異なるタイムゾーンに属す場合（Ｓ２０２でＮｏ）、経路探索部４２は、時差情報３３０を参照して、Ｓ２０１で求めた到着予想時刻を候補リンクの属するタイムゾーンの時刻に換算する（Ｓ２０３）。具体的には、図４に示す時差情報３３０を参照し、候補リンクが属すタイムゾーン３３１と抽出リンクが属すタイムゾーン３３２に対応する時差３３３を抽出し、Ｓ２０１で求めた到着予想時刻に抽出した時差３３３を加算し、候補リンクの属するタイムゾーンの時刻を求める。そして、処理をＳ２０４に移行する。
【００５３】
候補リンクへの到着予想時刻が求まると、経路探索部４２は、リンクデータ３１２の時間規制情報３１２７を参照して、Ｓ２０１で求めた到着予想時刻において候補リンクの通行が可能か否か調べる（Ｓ２０４）。時間規制がされておらず通行が可能な場合、経路探索部４２は、その候補リンクを除外しない（Ｓ２０６）。一方、時間規制がされており通行ができない場合、経路探索部４２は、その候補リンクを除外する（Ｓ２０８）。
【００５４】
以上のＳ２０２〜２０８の処理を候補リンクの全てについて行った後（Ｓ２２０）、Ｓ１１２の処理に移行する。
【００５５】
ここで、上記の時間規制中のリンクを候補リンクから除外する処理について、図９を用いて具体的に説明する。
【００５６】
図９において、出発地Ｅと目的地Ｋとの間には、ノードＦ，Ｇ，Ｈ，Ｉ，Ｊが存在する。実線のＥＦＧＨＪＫ、ＩＫのリンクは時間規制のない通常のリンクを表す。出発地Ｅから目的地Ｋ間の経路は、ノードＨでリンクＨＩとリンクＨＪに分岐している。ＨＩは、１１：００〜１３：００の間において時間規制があり通行禁止である。また、ＥＦＧＨ間のリンクはタイムゾーンＡに属し、ＨＫ間のリンクはタイムゾーンＢに属す。タイムゾーンＡとタイムゾーンＢとの時差は１時間で、例えば、タイムゾーンＡで１０：００のとき、タイムゾーンＢでは１１：００である。
【００５７】
このような例において、ノードＨからさらに目的地までの経路を探索する場合について考える。候補リンクはＨＩとＨＪである。また、ノードＨへの到着予想時間は、タイムゾーンＡにおいて１０：００であるとする。経路探索部４２は、まず、候補リンクであるＨＩのリンクが、候補リンクの前のリンクＧＨと同じタイムゾーンに属すか否かを判定する（Ｓ２０２）。同じタイムゾーンには属さないので（Ｓ２０２でＮｏ）、候補リンクの開始ノードＨへの到着予想時刻を、タイムゾーンＢでの時刻に換算する（Ｓ２０３）。ノードＨへの到着予想時間は１０：００であり、これをタイムゾーンＢでの時刻に換算すると１１：００になる。次に、経路探索部４２は、候補リンクＨＩについて、１１：００において通行可能か否か判定する（Ｓ２０４）。ＨＩ間は１１：００〜１３：００までの間、時間規制により通行できないので、ＨＩ間のリンクは候補リンクから除外する（Ｓ２０８）。残りの候補リンクＨＪについても同様に処理する。すなわち、ＨＪ間は時間規制がないので、候補リンクから除外しない。
【００５８】
このように、候補リンクの中から時間規制中のリンクを除外する処理を行うと、経路探索部４２は、処理をＳ１１２に移行する。
【００５９】
Ｓ１１２では、まず、経路探索部４２は、候補リンク各々について、Ｓ１０２で入手したリンクデータ３１２を用いて当該候補リンクのコスト（旅行時間）を求める。そして、出発地から候補リンクの終了ノードまでの総コストを算出する。具体的には、ヒープテーブルに登録されている抽出リンクの総コストに、候補リンクのコストを加算し、その加算結果を当該候補リンクの総コストとする。ただし、ヒープテーブルに抽出リンクが登録されていない初期段階では、候補リンクのコストを当該候補リンクの総コストとする。それから、経路探索部４２は、候補リンク各々のリンクデータおよび総コストをヒープテーブルに追加する。
【００６０】
次に、経路探索部４２は、直前に行ったＳ１１２にてヒープテーブルに新たに追加されたリンクの中に、目的地リンク（目的地に近接するリンク）があるか否かを調べる（Ｓ１１４）。目的地リンクがないと判断した場合（Ｓ１１４でＮｏ）、経路探索部４２は、ヒープテーブルに登録されているリンクの情報を総コストの小さい順にソートし、最初に位置するリンクを抽出するなどして、ヒープテーブルから総コストが最小の候補リンクを抽出する（Ｓ１１８）。それから、Ｓ１０４に戻る。
【００６１】
一方、目的地リンクがあると判断した場合（Ｓ１１４でＹｅｓ）、経路探索部４２は、推奨経路決定処理を行う（Ｓ１２０）。具体的には、ヒープテーブルから、目的地リンクを発生させたリンク（目的地リンクの開始ノードを終了ノードとするリンク）を検索し、検出したリンクを推奨経路を構成する構成リンクに決定する。次に、構成リンクが、出発地が存在あるいは出発地に近接する出発地リンクであるか否かを調べ、出発地リンクでないならば、この構成リンクを発生させたリンクを検索し、検出したリンクを構成リンクに決定して、それが出発リンクであるか否かをさらに調べる。この処理を、構成リンクが出発リンクであると判断されるまで繰り返すことで、推奨経路を構成する各構成リンクを決定する。それから、経路探索部４２は、推奨経路を構成する各構成リンクについて、リンクデータ３１２を経路記憶部４３の推奨経路テーブルに記憶する（Ｓ１２０）。
【００６２】
以上のように、推奨経路が決定し経路記憶部４３に記憶されると、ディスプレイ２は、経路探索部４２の指示を受けて推奨経路を画面に表示する。
【００６３】
図１０に画面表示例を示す。図示するように、画面には、地図４２０上に、出発地４０２、目的地４０３までの推奨経路４１０が表示されている。また、推奨経路４１０が異なるタイムゾーンに跨って存在することが分かるように表示されている。すなわち、タイムゾーン境界線４０６が表示され、タイムゾーンの情報４０４，４０５が表示されている。また、時間規制を考慮して経路探索を行ったことを知らせるメッセージ４０７が表示されている。
【００６４】
以上、本発明の一実施形態について説明した。
【００６５】
上記、経路探索処理によれば、異なるタイムゾーンに属す地域を跨いで経路探索する場合でも、時間規制を考慮した推奨経路が探索できる。
【００６６】
また、例えば、図９に示す例において、タイムゾーンを考慮しないで経路探索すると、ノードＨへの到着予想時刻は１０：００なので、ＨＩ間も通行可能と判定され、経路探索の対象に含まれてしまう。そして、実際に通行できないリンクを含む推奨経路を探索してしまうことになる。これに対して、本実施形態によれば、異なるタイムゾーンに属す地域を跨いで経路探索する場合でも、時間規制を適切に考慮して推奨経路が探索できる。
【００６７】
尚、本発明は上記の実施形態に限定されるものではなく、その要旨の範囲内で様々な変形が可能である。
【００６８】
例えば、リンクデータ３１２に含まれるリンクが異なるタイムゾーンに跨って存在する場合、タイムゾーンの変わる部分にノードを設定し、そのリンクをそのノード部分で分割して複数のリンクとして扱うようにしてもよい。
【００６９】
かかる構成は、地図データ記憶装置３に、図１１で示すように、各リンクについて、タイムゾーンの変わる部分で分割した複数のリンクとして取り扱うための情報を記憶することで達成できる。具体的には、図１１に示すように、分割前のリンクと分割後のリンクの対応を表す情報が記憶する。すなわち、分割前のリンクＩＤ３４１ごとに、分割後新たに設定されたリンクＩＤ３４２２と、そのリンクのリンクデータ３４２を記憶するようにする。そして、経路探索処理においては、異なるタイムゾーンに跨って存在するリンクについては、図１１で示す情報を参照して、タイムゾーンごとに異なるリンクであるとして、それぞれタイムゾーンの時刻を適用する。このようにすれば、リンクについてどのタイムゾーンの時刻を適用すればよいかが明確になるので、時間規制を考慮した経路探索をより確実に行うことができる。
【００７０】
また、上記実施形態では、リンクごとにそのリンクの属するタイムゾーンを記憶している。本実施形態は、これに限られない。リンクが属するタイムゾーンが分かる情報であれば、どのような形の情報を記憶し利用するようにしもよい。
【００７１】
例えば、特定のタイムゾーンに属する地域についての座標情報と、リンクデータ３の座標情報とから、そのリンクがどのタイムゾーンに属すかを判断するようにしてもよい。具体的には、図１２に示すように、特定のタイムゾーンの地域範囲をかたどったポリゴン５０２、５０４を座標情報により設定し、どのポリゴン内に存在するかで、そのリンクの属すタイムゾーンを判断するようにしてもよい。図中では、リンク５０６は、ポリゴン５０４内に存在するので、タイムゾーンＩに属するリンクと判断される。
【００７２】
また、上記の実施形態では、本発明を車載用ナビゲーション装置に適用した例について説明したが、本発明は車載用以外のナビゲーション装置にも適用することができる。
【図面の簡単な説明】
【００７３】
【図１】図１は、本発明の一実施形態が適用された車載用ナビゲーション装置の概略構成図である。
【図２】図２は、地図データ記憶装置３に記憶されている地図データの構成例を示す図である。
【図３】図３は、地図データに含まれるタイムゾーン情報の構成例を示す図である。
【図４】図４は、地図データに含まれる時差情報の構成例を示す図である。
【図５】図５は、演算処理部１のハードウェア構成を示す図である。
【図６】図６は、演算処理部１の機能構成を示す図である。
【図７】図７は、本実施形態が適用された車載用ナビゲーション装置の推奨経路探索動作を説明するためのフロー図である。
【図８】図８は、図７のＳ１０６（候補リンクから時間規制中リンクを除外する処理）を説明するためのフロー図である。
【図９】図９は、候補リンクから時間規制中リンクを除外する処理を説明するための図である。
【図１０】図１０は、推奨経路のディスプレイ２への表示例を示す図である。
【図１１】図１１は、タイムゾーン境界線を跨いで存在するリンクを分割した場合のリンクデータの構成の構成例を示す図である。
【図１２】図１２は、ポリゴンを用いてリンクが属するタイムゾーンを特定する構成を説明するための図である。
【符号の説明】
【００７４】
１・・・演算処理部、２・・・ディスプレイ、３・・・地図・統計交通データ記憶装置、４・・・音声出入力装置、５・・・入力装置、６・・・車輪速センサ、７・・・地磁気センサ、８・・・ジャイロ、９・・・ＧＰＳ受信機、１０・・・天気情報受信装置、１１・・・車内ＬＡＮ装置、２１・・・ＣＰＵ、２２・・・ＲＡＭ、２３・・・ＲＯＭ、２４・・・ＤＭＡ、２５・・・描画コントローラ、２６・・・ＶＲＡＭ、２７・・・カラーパレット、２８・・・Ａ/Ｄ変換器、２９・・・ＳＣＩ、３０・・・ＰＩＯ、３１・・・カウンタ、４１・・・ユーザ操作解析部、４２・・・経路探索部、４３・・・経路記憶部、４４・・・経路誘導部、４５・・・地図表示処理部、４６・・・現在位置演算部、４７・・・マップマッチ処理部、４８・・・データ読込部、４９・・・軌跡記憶部、５０・・・メニュー表示処理部、５１・・・グラフィックス処理部
【図１】
2005121425.tif 000003
【図２】
2005121425.tif 000004
【図３】
2005121425.tif 000005
【図４】
2005121425.tif 000006
【図５】
2005121425.tif 000007
【図６】
2005121425.tif 000008
【図７】
2005121425.tif 000009
【図８】
2005121425.tif 000010
【図９】
2005121425.tif 000011
【図１０】
2005121425.tif 000012
【図１１】
2005121425.tif 000013
【図１２】
2005121425.tif 000014