ナビゲーション装置の経路探索方法
【課題】 予測交通情報がないリンクについても考慮して経路探索する。
【解決手段】
ナビゲーション装置は、記憶装置に、過去の交通情報から統計処理して生成された統計交通情報を保持する。交通情報配信サーバから、予測交通情報をダウンロードする。予測交通情報があるリンクについては、そのリンクのコストとして予測交通情報の旅行時間を用い、予測交通情報がないリンクについては、そのリンクのコストとして統計交通情報に含まれているリンク旅行時間を用いて、総コストが最少の経路を探索する。
【解決手段】
ナビゲーション装置は、記憶装置に、過去の交通情報から統計処理して生成された統計交通情報を保持する。交通情報配信サーバから、予測交通情報をダウンロードする。予測交通情報があるリンクについては、そのリンクのコストとして予測交通情報の旅行時間を用い、予測交通情報がないリンクについては、そのリンクのコストとして統計交通情報に含まれているリンク旅行時間を用いて、総コストが最少の経路を探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置に関し、特に車載用ナビゲーション装置の経路探索方法に関する。
【背景技術】
【０００２】
特許文献１には、予測交通情報を用いて経路探索を行う車載用ナビゲーション装置が記載されている。
【０００３】
【特許文献１】特開２００４−２３３２３０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、全てのリンクについて予測交通情報が入手できるとは限らない。特許文献１の技術では、予測交通情報が入手できなかったリンクがある場合について考慮しておらず、このようなリンクを含めて経路探索を行うことができない。
【０００５】
本発明の目的は、予測交通情報に旅行時間等が含まれていないリンクがある場合でも、そのリンクを除外することなく経路探索を行う技術を提供することにある。
【課題を解決するための手段】
【０００６】
上記課題を解決すべく本発明のナビゲーション装置は、現在時刻以降における交通情報を含む予測交通情報と、過去の交通情報を統計処理して求めた統計交通情報とを用いて、経路を探索する。
【０００７】
具体的には、前記ナビゲーション装置は、前記予測交通情報にリンク旅行時間が含まれているリンクについては、当該リンクのコストとして当該旅行時間を用い、前記予測交通情報に旅行時間が含まれていないリンクについては、当該リンクのコストとして前記統計交通情報に含まれている当該リンクの旅行時間を用いて、総コストが最少の経路を探索する。
【発明を実施するための最良の形態】
【０００８】
以下に、本発明の一実施形態について、図面を参照して説明する。
【０００９】
図１は、本発明の一実施形態にかかるナビゲーションシステムの概略構成図である。図示するように、本実施形態のナビゲーションシステムは、車載用ナビゲーション装置１００と、交通情報配信サーバ２００とを有する。車載用ナビゲーション装置１００と交通情報配信サーバ２００とは、無線基地局（不図示）とネットワーク４００を介して接続される。また、交通情報配信サーバ２００からの交通情報は、ＦＭ多重放送局２０１、ビーコン２０２によっても車載用ナビゲーション装置１００に送信される。
【００１０】
交通情報配信サーバ２００は、車載用ナビゲーション装置１００に交通情報を配信するサーバ装置である。交通情報配信サーバ２００は、自身の記憶装置に、予測交通情報２１０を保持する。
【００１１】
予測交通情報２１０は、現在以降の未来の交通情報である。予測交通情報２１０は、例えば、過去の交通情報と現在の交通情報から生成することができる。
【００１２】
図２は、予測交通情報２１０の構成例である。予測交通情報２１０は、地図上の領域を区分けしたメッシュ領域の識別コード（メッシュＩＤ）２１１及びリンクの識別コード（リンクＩＤ）２１２ごとに、時間帯２１３ごとのリンク旅行時間２１４を含んでいる。
【００１３】
このような予測交通情報は、過去に収集された交通情報に基づいて生成することができる。図３に、予測交通情報の生成方法の例を示す。
【００１４】
図３において、符号４１は、過去に収集された交通情報から求められた、あるリンクの旅行時間Ｔｄの経時変化を示す。符号４２は、現在の交通情報から求められた、そのリンクの旅行時間Ｔｄ’の経時変化を示す。現在時刻をｔとする。
【００１５】
まず、現在の交通情報から求められたリンク旅行時間Ｔｄ’４２と過去のリンク旅行時間Ｔｄ４１との差分４３を、所定時刻間隔ごとに求める。そして、求めた差分の平均４４を求める。時刻（ｔ＋ｎ）における予測旅行時間Ｔｄ’（ｔ＋ｎ）は、
Ｔｄ（ｔ＋ｎ）＋（差分の平均） により求めることができる。
【００１６】
なお、予測交通情報は、上記の方法で生成されたものに限られない。過去の日の時系列データと当日の時系列データを比較して類似している日のデータを利用して生成されたものであってもよい。
【００１７】
図４は、車載用ナビゲーション装置１００の概略構成図である。図示するように、車載用ナビゲーション装置１００は、演算処理部１と、ディスプレイ２と、記憶装置３と、音声入出力装置４と、入力装置５と、車輪速センサ６と、地磁気センサ７と、ジャイロセンサ８と、ＧＰＳ(Global 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)３０と、パルス信号を積分するカウンタ３１と、を有する。
【００４６】
［動作の説明］次に、車載用ナビゲーション装置１００の動作について説明する。図９は、本実施形態の車載用ナビゲーション装置１００の動作の概略を示すフロー図である。
【００４７】
このフローは、ユーザ操作解析部４１が、音声入出力装置４あるいは入力装置５を介してユーザより経路探索要求を受け付けることにより開始される。
【００４８】
まず、ユーザ操作解析部４１は、出発地および目的地を設定する。ユーザ操作解析部４１は、通常、現在位置算出部４６で求めた現在地を出発地に設定する。ユーザ操作解析部４１はまた、ユーザの指示に基づき目的地を設定する。例えばユーザ操作解析部４１は、記憶装置３から地図データに登録されている地図構成物を読み込む。ユーザ操作解析部４１は、表示処理部４５を介してディスプレイ２に、これらの地図構成物を表示する。ユーザ操作解析部４１は、入力装置５を介してユーザより、表示中の地図構成物の情報の中から目的地を選択させる。ユーザ操作解析部４１はまた、出発時刻を設定する。現在時刻を出発時刻に設定する場合は、図示していない内蔵タイマなどを用いて推奨経路の探索要求を受け付けた時に取得した現在時刻を出発時刻に設定する（Ｓ１０２）。
【００４９】
次に、経路探索部４２は、ダウンロードする予測交通情報の範囲を特定する。経路探索部４２は、この範囲を、メッシュにより特定する。例えば、経路探索部４２は、記憶装置３より、座標情報からその座標情報により特定される地点を含むメッシュ領域のメッシュＩＤを特定するための第１変換テーブルを読み出す。そして、この第１変換テーブルを用いて、設定された出発地から目的地までの直線を含む領域（もしくは、直線から所定の距離内の領域）に含まれる各メッシュ領域のメッシュＩＤを特定する。なお、統計交通情報を用いて、後述する経路探索処理により、経路を探索し、経路上のメッシュ領域のメッシュＩＤをダウンロードする予測交通情報の範囲として特定するようにしてもよい。
【００５０】
さらに、通信処理部４７は、特定したメッシュＩＤごとに、通過予想時刻を特定する。通信処理部４７は、例えば、現在位置からのメッシュ（例えばメッシュの中心点）までの距離や探索条件に基づいて、そのメッシュの通過予想時刻を求める。具体的には、そのメッシュまでの距離を、予め定めた平均速度で除することにより、そのメッシュまでの旅行時間の概算を求める。そして、出発時刻に、その旅行時間の概算を足して、通過予想時刻を求める（Ｓ１０４）。
【００５１】
次に、通信処理部４７は、Ｓ１０４で経路探索部４２により特定されたメッシュのメッシュＩＤ及び通過予想時刻を、ネットワーク通信装置１４を介して交通情報配信サーバ２００に送信する。そして、そのメッシュＩＤで特定されるメッシュ内のリンクであって、通過予想時刻に対応する予測交通情報を車載用ナビゲーション装置１００に送信するように要求する（Ｓ１０６）。
【００５２】
これを受けて、交通情報配信サーバ２００は、自身の記憶装置に記憶されている予測交通情報の中から、車載用ナビゲーション装置１００から送信されたメッシュＩＤの予測交通情報を抽出し、車載用ナビゲーション装置１００に送信する。
【００５３】
車載用ナビゲーション装置１００の通信処理部４７は、交通情報配信サーバ２００から予測交通情報を受信し、受信情報記憶部４８に記憶させる。
【００５４】
次に、経路探索部４２は、後述する処理により、予測交通情報と統計交通情報を用いて、経路探索を行う（Ｓ１１０）。そして、探索した経路を表示処理部４５を介してディスプレイ２に表示する（Ｓ１１２）。
【００５５】
つぎに、経路探索処理（Ｓ１１０）について具体的に説明する。図１０は、経路探索処理のフロー図である。
【００５６】
経路探索部４２は、現在位置の座標から、第１変換テーブルを用いて、出発地および目的地を含む経路探索領域に含まれる各メッシュ領域のメッシュＩＤを特定する（Ｓ１１０２）。
【００５７】
また、経路探索部４２は、記憶装置３より、特定したメッシュＩＤを持つ地図データ３１０各々に登録されている各リンクデータ３１２を入手する（Ｓ１１０４）。
【００５８】
つぎに、経路探索部４２は、Ｓ１１０４で記憶装置３から読み込んだリンクデータ３１２を用いて、後述するＳ１１１８でヒープテーブルから抽出されたリンク（抽出リンクと呼ぶ）の終了ノードを開始ノードとするリンクを、推奨経路を構成するリンクの候補（候補リンクと呼ぶ）として選出する。
【００５９】
ただし、Ｓ１１１８での処理が行われていない場合、つまり、ヒープテーブルにリンクが登録されていない初期段階では、抽出リンクの終了ノードを開始ノードとするリンクを候補リンクとして選出する代わりに、出発地が存在あるいは出発地に近接する少なくとも１つのリンクを、候補リンクとして選出する（Ｓ１１０６）。
【００６０】
ここで、ヒープテーブルとは、候補リンクのリンクデータを、出発地から当該候補リンクの終了ノードまでの総コストと共に登録するためのテーブルであり、メモリ等の記憶装置に記憶される。図１２はヒープテーブルの一例を示す図である。図示するように、ヒープテーブルには、候補リンク毎にレコード４３００が登録される。レコード４３００は、候補リンクのリンクＩＤを登録するフィールド４３０１と、候補リンクのコスト（旅行時間）を登録するフィールド４３０２と、終了ノードが候補リンクの開始ノードと接続する接続元リンクのリンクＩＤを登録するためのフィールド４３０３と、出発地から候補リンクまでの総コスト（総旅行時間）を登録するためのフィールド４３０４と、後述するＳ１１１８で抽出リンクとして設定済みか否かを示す抽出フラグを登録するためのフィールド４３０６と、を有する。
【００６１】
次に、経路探索部４２は、抽出リンクの終了ノードへの到着予想時刻を算出する。これは、ヒープテーブルから、抽出リンクに現在設定されている候補リンクのレコード４３００を特定し、出発時刻にこのレコード４３００のフィールド４３０４に登録されている総旅行時間を加算することで算出できる（Ｓ１１０８）。
【００６２】
それから、経路探索部４２は、記憶装置３に記憶されている予測交通情報または統計交通情報の中から、候補リンクごとに、当該候補リンクを含むレコードを特定する。そして、特定したレコードから、到着予想時刻が属する時間帯（注目時間帯）のリンク旅行時間を特定する（Ｓ１１１０）。
【００６３】
図１１は、かかるリンク旅行時間を特定する処理（Ｓ１１１０）の具体的なフロー図である。
【００６４】
経路探索部４２は、受信情報記憶部４８に記憶されている予測交通情報に、候補リンクを含むレコードがあるか否か判定し、ある場合、そのレコードから、到着予想時刻が属する時間帯（注目時間帯）のリンク旅行時間を抽出を試みる。抽出できた場合（Ｓ１１１０１でＹｅｓ）、抽出したリンク旅行時間を候補リンクのリンク旅行時間とする。
【００６５】
一方、予測交通情報の中に、候補リンクを含むレコードがない場合、若しくは、レコードがあっても候補リンクの注目時間帯のリンク旅行時間が含まれておらず、リンク旅行時間を抽出できなかった場合（Ｓ１１１０１でＮｏ）、経路探索部４２は、統計交通情報の中から、候補リンクの注目時間帯のリンク旅行時間を抽出する。そして、抽出したリンク旅行時間を候補リンクのリンク旅行時間とする。ただし、経路探索部４２は、次のようにして、統計交通情報から候補リンクの旅行時間を抽出する。
【００６６】
まず、経路探索部４２は、記憶装置３より、年月日から統計交通情報３２０のテーブル３２２１で管理されている日の種類を特定するための第２変換テーブルを読み出す。そして、第２変換テーブルを用いて、今日（出発日）の日の種類を特定する。次に、経路探索部４２は、今日の日の種類における、候補リンクの注目時間帯の旅行時間を抽出する。そして、抽出したリンク旅行時間を候補リンクのリンク旅行時間とする。
【００６７】
図１０に戻り、Ｓ１１１４から説明する。次に、経路探索部４２は、候補リンク各々について、出発地から当該候補リンクまでの総旅行時間（総コスト）を算出する。具体的には、ヒープテーブルに登録されている抽出リンクの総旅行時間に、Ｓ１１１０で入手した候補リンクの注目時間帯の旅行時間を加算し、その加算結果を当該候補リンクの総旅行時間とする。それから、経路探索部４２は、ヒープテーブルに、各候補リンクのレコード４３００を追加する。そして、追加した各レコード４３００のフィールド４３０１〜４３０４に、対応する候補リンクのリンクＩＤ、当該候補リンクの旅行時間（コスト）、抽出リンク（接続元リンク）のリンクＩＤ、出発地から当該候補リンクまでの総旅行時間（総コスト）を登録する。また、フィールド４３０６には未だ抽出リンクに設定されていないことを示す「未」を登録する（Ｓ１１１４）。
【００６８】
次に、経路探索部４２は、直前に行ったＳ１１１４にてヒープテーブルに新たに追加された候補リンクの中に、目的地が存在あるいは目的地に近接するリンク（目的地リンクと呼ぶ）があるか否かを調べる（Ｓ１１１６）。
【００６９】
Ｓ１１１６において目的地リンクがないと判断したならば、経路探索部４２は、ヒープテーブルに登録されている各候補リンクのレコード４３００を総旅行時間の小さい順にソートし、フィールド４３０６の抽出フラグが「未」の候補リンク（未抽出リンクと呼ぶ）の中で、最も上位に位置する未抽出リンクを抽出するなどして、ヒープテーブルから総旅行時間が最小の未抽出リンクを抽出する。そして、現在の抽出リンクをこの未抽出リンクに変更し、この未抽出リンクのレコード４３００のフィールド４３０６に登録されている抽出フラグを「未」から「済」に変更する（Ｓ１１１８）。それから、Ｓ１１０６に戻る。
【００７０】
一方、Ｓ１１１６において目的地リンクがあると判断したならば、経路探索部４２は、推奨経路決定処理を行う。具体的には、ヒープテーブルから、目的地リンクの接続元リンク（目的地リンクのレコード４３００のフィールド４３０３にリンクＩＤが登録されている候補リンク）を検索し、検索したリンクを推奨経路を構成するリンク（構成リンクと呼ぶ）に決定する。次に、構成リンクの接続元リンクがあるか否かを調べ、接続元リンクがあるならば、この接続元リンクを構成リンクに決定して、その接続元リンクがあるか否かをさらに調べる。この処理を、構成リンクの接続元リンクがなくなるまで、つまり、構成リンクが、出発地が存在あるいは出発地に近接するリンク（出発地リンクと呼ぶ）となるまで繰り返すことで、推奨経路を構成する各構成リンクを決定する。それから、経路探索部４２は、推奨経路の情報として、推奨経路を構成する各構成リンクのリンクデータ３１２およびＳ１１１０で入手した旅行時間を、出発時刻の情報と共に、経路記憶部４３に記憶する（Ｓ１１２０）。
【００７１】
以上の処理により、推奨経路を構成する各構成リンクのコストは、次のようになる。すなわち、推奨経路を構成する１番目のリンクの旅行時間として、出発時刻を含む時間帯に対応する予測交通情報または統計交通情報より求まる旅行時間が用いられる。また、推奨経路を構成するｎ番目（ｎ≧２）のリンクの旅行時間として、当該ｎ番目のリンクと接続するｎ-１番目のリンクの終了ノードへの予想到着時刻を含む時間帯に対応する予測交通情報または統計交通情報より求まる旅行時間が用いられる。
【００７２】
以上、経路探索処理のフローについて説明した。このフローによれば、予測交通情報があるリンクについては、そのコストとして予測交通情報に含まれる旅行時間を用いる。一方、予測交通情報がないリンクについては、そのコストとして、統計交通情報を用いる。したがって、予測交通情報を入手できなかったリンクについても、除外することなく経路探索を行うことができる。
【００７３】
また、予測交通情報は、通常、リアルタイムに生成されるので、統計交通情報に比べ精度が高い。上記経路探索処理のフローによれば、予測交通情報を優先的に使用して経路探索するので、より実情に即した推奨経路を探索することができる。
【００７４】
本発明は、上記実施形態に限定されず、さまざまな変形が可能である。
【００７５】
例えば、車載用ナビゲーション装置は、交通情報配信サーバ２００から、統計交通情報を補正するための補正情報を入手する。そして、予測交通情報がないリンクについては、補正情報により補正した統計交通情報を用いてコストを定め、経路探索を行うようにしてもよい。
【００７６】
具体的には、交通情報配信サーバ２００は、自身の記憶装置に、車載用ナビゲーション装置が保持する統計交通情報に含まれるリンク旅行時間を補正するための情報（補正情報）を記憶している。補正情報は、現在の交通情報と過去の交通情報を比較してリアルタイムに生成されたものである。
【００７７】
補正情報としては、例えば、統計交通情報の旅行時間に対して一律に増加させる値（例えば＋１０分）、一律に減少させる値（例えば−１０分）、一律に乗じる値（例えば、×１．２）などである。
【００７８】
そして、予測交通情報をダウンロードする際、交通情報配信サーバ２００は、この補正情報もダウンロードする。
【００７９】
車載用ナビゲーション装置は、図１１で示したフローのように、予測交通情報に旅行時間が含まれているリンクについては、そのリンクのコストとして、その旅行時間を用いる。
【００８０】
一方、予測交通情報に旅行時間が含まれていないリンクについては、統計交通情報の中から注目時間帯の旅行時間を得る。そして、さらに、その旅行時間を補正情報を用いて補正し、補正して得た値をそのリンクの旅行時間とする。
【００８１】
具体的には、補正情報が、統計交通情報の旅行時間に対して一律に増加させる値（例えば＋１０分）である場合、統計交通情報の旅行時間をその値で増加させる。一律に減少させる値（例えば−１０分）である場合、統計交通情報の旅行時間をその値で減少させる。一律に乗じる値（例えば、×１．２）である場合、統計交通情報の旅行時間にその値を乗じる。
【００８２】
このようにすれば、予測交通情報がないリンクについては、統計交通情報の旅行時間をさらに補正した旅行時間が用いられる。したがって、より実情に即した経路探索を行うことができる。
【００８３】
また、補正情報を交通情報配信サーバ２００から受信せずに、車載用ナビゲーション装置１００が自ら生成してもよい。すなわち、受信した予測交通情報を用いて統計交通情報の旅行時間を補正するようにしてもよい。
【００８４】
例えば、同一のリンクの同一の時間帯の旅行時間について、ダウンロードした予測交通情報と統計交通情報との差、あるいはＦＭ多重放送受信装置１２若しくはビーコン受信装置１３で受信した現況交通情報と統計交通情報との差を求める。いくつかのリンクについて旅行時間の差を求め、この差を平均する。そして、予測交通情報がないリンクについては、そのリンクの統計交通情報の旅行時間に、求めた差の平均を足して補正する。そして、補正した値を、そのリンクの旅行時間として、経路探索を行う。
【００８５】
このようにすれば、補正情報を交通情報配信サーバ２００から入手しなくても、統計交通情報を補正することができる。
【００８６】
なお、上記では、予測交通情報および統計交通情報がリンク旅行時間を含む場合について説明したが、リンク移動速度を含んでもよい。そして、リンクのコストとしてリンク移動速度を用いてもよい。
【００８７】
なお、本発明を車載用ナビゲーション装置に適用した例について説明したが、本発明は車載用以外のナビゲーション装置にも適用することができる。
【図面の簡単な説明】
【００８８】
【図１】図１は、本発明が適用された実施形態であるナビゲーションシステムの概略構成図である。
【図２】図２は、予測交通情報の構成を示す図である。
【図３】図３は、予測交通情報を生成する方法を説明するための図である。
【図４】図４は、車載用ナビゲーション装置１００の概略構成図である。
【図５】図５は、記憶装置３に記憶されている地図データの構成を示す図である。
【図６】図６は、記憶装置３に記憶されている統計交通情報の構成を示す図である。
【図７】図７は、演算処理部１の機能構成を示す図である。
【図８】図８は、演算処理部１のハードウェア構成を示す図である。
【図９】図９は、車載用ナビゲーション装置１００の処理の概略を示すフロー図である。
【図１０】図１０は、図９のＳ１１０の処理のフロー図である。
【図１１】図１１は、図１０のＳ１１１０の処理のフロー図である。
【図１２】図１２は、経路探索に用いられるヒープテーブルの構成を示す図である。
【符号の説明】
【００８９】
１００…車載用ナビゲーション装置、２００…交通情報配信サーバ、４００…ネットワーク、
１…演算処理部、２…ディスプレイ、３…記憶装置、４…音声出入力装置、５…入力装置、６…車輪速センサ、７…地磁気センサ、８…ジャイロ、９…ＧＰＳ受信機、１１…車内ＬＡＮ装置、１２…ＦＭ多重放送受信装置、１３…ビーコン受信装置、１４…ネットワーク通信装置、２１…ＣＰＵ、２２…ＲＡＭ、２３…ＲＯＭ、２４…ＤＭＡ、２５…描画コントローラ、２６…ＶＲＡＭ、２７…カラーパレット、２８…Ａ/Ｄ変換器、２９…ＳＣＩ、３０…ＰＩＯ、３１…カウンタ、４１…ユーザ操作解析部、４２…経路探索部、４３…経路記憶部、４４…経路誘導部、４５…表示処理部、４６…現在位置算出部、４７…通信処理部、４８…受信情報記憶部
【技術分野】
【０００１】
本発明は、ナビゲーション装置に関し、特に車載用ナビゲーション装置の経路探索方法に関する。
【背景技術】
【０００２】
特許文献１には、予測交通情報を用いて経路探索を行う車載用ナビゲーション装置が記載されている。
【０００３】
【特許文献１】特開２００４−２３３２３０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、全てのリンクについて予測交通情報が入手できるとは限らない。特許文献１の技術では、予測交通情報が入手できなかったリンクがある場合について考慮しておらず、このようなリンクを含めて経路探索を行うことができない。
【０００５】
本発明の目的は、予測交通情報に旅行時間等が含まれていないリンクがある場合でも、そのリンクを除外することなく経路探索を行う技術を提供することにある。
【課題を解決するための手段】
【０００６】
上記課題を解決すべく本発明のナビゲーション装置は、現在時刻以降における交通情報を含む予測交通情報と、過去の交通情報を統計処理して求めた統計交通情報とを用いて、経路を探索する。
【０００７】
具体的には、前記ナビゲーション装置は、前記予測交通情報にリンク旅行時間が含まれているリンクについては、当該リンクのコストとして当該旅行時間を用い、前記予測交通情報に旅行時間が含まれていないリンクについては、当該リンクのコストとして前記統計交通情報に含まれている当該リンクの旅行時間を用いて、総コストが最少の経路を探索する。
【発明を実施するための最良の形態】
【０００８】
以下に、本発明の一実施形態について、図面を参照して説明する。
【０００９】
図１は、本発明の一実施形態にかかるナビゲーションシステムの概略構成図である。図示するように、本実施形態のナビゲーションシステムは、車載用ナビゲーション装置１００と、交通情報配信サーバ２００とを有する。車載用ナビゲーション装置１００と交通情報配信サーバ２００とは、無線基地局（不図示）とネットワーク４００を介して接続される。また、交通情報配信サーバ２００からの交通情報は、ＦＭ多重放送局２０１、ビーコン２０２によっても車載用ナビゲーション装置１００に送信される。
【００１０】
交通情報配信サーバ２００は、車載用ナビゲーション装置１００に交通情報を配信するサーバ装置である。交通情報配信サーバ２００は、自身の記憶装置に、予測交通情報２１０を保持する。
【００１１】
予測交通情報２１０は、現在以降の未来の交通情報である。予測交通情報２１０は、例えば、過去の交通情報と現在の交通情報から生成することができる。
【００１２】
図２は、予測交通情報２１０の構成例である。予測交通情報２１０は、地図上の領域を区分けしたメッシュ領域の識別コード（メッシュＩＤ）２１１及びリンクの識別コード（リンクＩＤ）２１２ごとに、時間帯２１３ごとのリンク旅行時間２１４を含んでいる。
【００１３】
このような予測交通情報は、過去に収集された交通情報に基づいて生成することができる。図３に、予測交通情報の生成方法の例を示す。
【００１４】
図３において、符号４１は、過去に収集された交通情報から求められた、あるリンクの旅行時間Ｔｄの経時変化を示す。符号４２は、現在の交通情報から求められた、そのリンクの旅行時間Ｔｄ’の経時変化を示す。現在時刻をｔとする。
【００１５】
まず、現在の交通情報から求められたリンク旅行時間Ｔｄ’４２と過去のリンク旅行時間Ｔｄ４１との差分４３を、所定時刻間隔ごとに求める。そして、求めた差分の平均４４を求める。時刻（ｔ＋ｎ）における予測旅行時間Ｔｄ’（ｔ＋ｎ）は、
Ｔｄ（ｔ＋ｎ）＋（差分の平均） により求めることができる。
【００１６】
なお、予測交通情報は、上記の方法で生成されたものに限られない。過去の日の時系列データと当日の時系列データを比較して類似している日のデータを利用して生成されたものであってもよい。
【００１７】
図４は、車載用ナビゲーション装置１００の概略構成図である。図示するように、車載用ナビゲーション装置１００は、演算処理部１と、ディスプレイ２と、記憶装置３と、音声入出力装置４と、入力装置５と、車輪速センサ６と、地磁気センサ７と、ジャイロセンサ８と、ＧＰＳ(Global 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)３０と、パルス信号を積分するカウンタ３１と、を有する。
【００４６】
［動作の説明］次に、車載用ナビゲーション装置１００の動作について説明する。図９は、本実施形態の車載用ナビゲーション装置１００の動作の概略を示すフロー図である。
【００４７】
このフローは、ユーザ操作解析部４１が、音声入出力装置４あるいは入力装置５を介してユーザより経路探索要求を受け付けることにより開始される。
【００４８】
まず、ユーザ操作解析部４１は、出発地および目的地を設定する。ユーザ操作解析部４１は、通常、現在位置算出部４６で求めた現在地を出発地に設定する。ユーザ操作解析部４１はまた、ユーザの指示に基づき目的地を設定する。例えばユーザ操作解析部４１は、記憶装置３から地図データに登録されている地図構成物を読み込む。ユーザ操作解析部４１は、表示処理部４５を介してディスプレイ２に、これらの地図構成物を表示する。ユーザ操作解析部４１は、入力装置５を介してユーザより、表示中の地図構成物の情報の中から目的地を選択させる。ユーザ操作解析部４１はまた、出発時刻を設定する。現在時刻を出発時刻に設定する場合は、図示していない内蔵タイマなどを用いて推奨経路の探索要求を受け付けた時に取得した現在時刻を出発時刻に設定する（Ｓ１０２）。
【００４９】
次に、経路探索部４２は、ダウンロードする予測交通情報の範囲を特定する。経路探索部４２は、この範囲を、メッシュにより特定する。例えば、経路探索部４２は、記憶装置３より、座標情報からその座標情報により特定される地点を含むメッシュ領域のメッシュＩＤを特定するための第１変換テーブルを読み出す。そして、この第１変換テーブルを用いて、設定された出発地から目的地までの直線を含む領域（もしくは、直線から所定の距離内の領域）に含まれる各メッシュ領域のメッシュＩＤを特定する。なお、統計交通情報を用いて、後述する経路探索処理により、経路を探索し、経路上のメッシュ領域のメッシュＩＤをダウンロードする予測交通情報の範囲として特定するようにしてもよい。
【００５０】
さらに、通信処理部４７は、特定したメッシュＩＤごとに、通過予想時刻を特定する。通信処理部４７は、例えば、現在位置からのメッシュ（例えばメッシュの中心点）までの距離や探索条件に基づいて、そのメッシュの通過予想時刻を求める。具体的には、そのメッシュまでの距離を、予め定めた平均速度で除することにより、そのメッシュまでの旅行時間の概算を求める。そして、出発時刻に、その旅行時間の概算を足して、通過予想時刻を求める（Ｓ１０４）。
【００５１】
次に、通信処理部４７は、Ｓ１０４で経路探索部４２により特定されたメッシュのメッシュＩＤ及び通過予想時刻を、ネットワーク通信装置１４を介して交通情報配信サーバ２００に送信する。そして、そのメッシュＩＤで特定されるメッシュ内のリンクであって、通過予想時刻に対応する予測交通情報を車載用ナビゲーション装置１００に送信するように要求する（Ｓ１０６）。
【００５２】
これを受けて、交通情報配信サーバ２００は、自身の記憶装置に記憶されている予測交通情報の中から、車載用ナビゲーション装置１００から送信されたメッシュＩＤの予測交通情報を抽出し、車載用ナビゲーション装置１００に送信する。
【００５３】
車載用ナビゲーション装置１００の通信処理部４７は、交通情報配信サーバ２００から予測交通情報を受信し、受信情報記憶部４８に記憶させる。
【００５４】
次に、経路探索部４２は、後述する処理により、予測交通情報と統計交通情報を用いて、経路探索を行う（Ｓ１１０）。そして、探索した経路を表示処理部４５を介してディスプレイ２に表示する（Ｓ１１２）。
【００５５】
つぎに、経路探索処理（Ｓ１１０）について具体的に説明する。図１０は、経路探索処理のフロー図である。
【００５６】
経路探索部４２は、現在位置の座標から、第１変換テーブルを用いて、出発地および目的地を含む経路探索領域に含まれる各メッシュ領域のメッシュＩＤを特定する（Ｓ１１０２）。
【００５７】
また、経路探索部４２は、記憶装置３より、特定したメッシュＩＤを持つ地図データ３１０各々に登録されている各リンクデータ３１２を入手する（Ｓ１１０４）。
【００５８】
つぎに、経路探索部４２は、Ｓ１１０４で記憶装置３から読み込んだリンクデータ３１２を用いて、後述するＳ１１１８でヒープテーブルから抽出されたリンク（抽出リンクと呼ぶ）の終了ノードを開始ノードとするリンクを、推奨経路を構成するリンクの候補（候補リンクと呼ぶ）として選出する。
【００５９】
ただし、Ｓ１１１８での処理が行われていない場合、つまり、ヒープテーブルにリンクが登録されていない初期段階では、抽出リンクの終了ノードを開始ノードとするリンクを候補リンクとして選出する代わりに、出発地が存在あるいは出発地に近接する少なくとも１つのリンクを、候補リンクとして選出する（Ｓ１１０６）。
【００６０】
ここで、ヒープテーブルとは、候補リンクのリンクデータを、出発地から当該候補リンクの終了ノードまでの総コストと共に登録するためのテーブルであり、メモリ等の記憶装置に記憶される。図１２はヒープテーブルの一例を示す図である。図示するように、ヒープテーブルには、候補リンク毎にレコード４３００が登録される。レコード４３００は、候補リンクのリンクＩＤを登録するフィールド４３０１と、候補リンクのコスト（旅行時間）を登録するフィールド４３０２と、終了ノードが候補リンクの開始ノードと接続する接続元リンクのリンクＩＤを登録するためのフィールド４３０３と、出発地から候補リンクまでの総コスト（総旅行時間）を登録するためのフィールド４３０４と、後述するＳ１１１８で抽出リンクとして設定済みか否かを示す抽出フラグを登録するためのフィールド４３０６と、を有する。
【００６１】
次に、経路探索部４２は、抽出リンクの終了ノードへの到着予想時刻を算出する。これは、ヒープテーブルから、抽出リンクに現在設定されている候補リンクのレコード４３００を特定し、出発時刻にこのレコード４３００のフィールド４３０４に登録されている総旅行時間を加算することで算出できる（Ｓ１１０８）。
【００６２】
それから、経路探索部４２は、記憶装置３に記憶されている予測交通情報または統計交通情報の中から、候補リンクごとに、当該候補リンクを含むレコードを特定する。そして、特定したレコードから、到着予想時刻が属する時間帯（注目時間帯）のリンク旅行時間を特定する（Ｓ１１１０）。
【００６３】
図１１は、かかるリンク旅行時間を特定する処理（Ｓ１１１０）の具体的なフロー図である。
【００６４】
経路探索部４２は、受信情報記憶部４８に記憶されている予測交通情報に、候補リンクを含むレコードがあるか否か判定し、ある場合、そのレコードから、到着予想時刻が属する時間帯（注目時間帯）のリンク旅行時間を抽出を試みる。抽出できた場合（Ｓ１１１０１でＹｅｓ）、抽出したリンク旅行時間を候補リンクのリンク旅行時間とする。
【００６５】
一方、予測交通情報の中に、候補リンクを含むレコードがない場合、若しくは、レコードがあっても候補リンクの注目時間帯のリンク旅行時間が含まれておらず、リンク旅行時間を抽出できなかった場合（Ｓ１１１０１でＮｏ）、経路探索部４２は、統計交通情報の中から、候補リンクの注目時間帯のリンク旅行時間を抽出する。そして、抽出したリンク旅行時間を候補リンクのリンク旅行時間とする。ただし、経路探索部４２は、次のようにして、統計交通情報から候補リンクの旅行時間を抽出する。
【００６６】
まず、経路探索部４２は、記憶装置３より、年月日から統計交通情報３２０のテーブル３２２１で管理されている日の種類を特定するための第２変換テーブルを読み出す。そして、第２変換テーブルを用いて、今日（出発日）の日の種類を特定する。次に、経路探索部４２は、今日の日の種類における、候補リンクの注目時間帯の旅行時間を抽出する。そして、抽出したリンク旅行時間を候補リンクのリンク旅行時間とする。
【００６７】
図１０に戻り、Ｓ１１１４から説明する。次に、経路探索部４２は、候補リンク各々について、出発地から当該候補リンクまでの総旅行時間（総コスト）を算出する。具体的には、ヒープテーブルに登録されている抽出リンクの総旅行時間に、Ｓ１１１０で入手した候補リンクの注目時間帯の旅行時間を加算し、その加算結果を当該候補リンクの総旅行時間とする。それから、経路探索部４２は、ヒープテーブルに、各候補リンクのレコード４３００を追加する。そして、追加した各レコード４３００のフィールド４３０１〜４３０４に、対応する候補リンクのリンクＩＤ、当該候補リンクの旅行時間（コスト）、抽出リンク（接続元リンク）のリンクＩＤ、出発地から当該候補リンクまでの総旅行時間（総コスト）を登録する。また、フィールド４３０６には未だ抽出リンクに設定されていないことを示す「未」を登録する（Ｓ１１１４）。
【００６８】
次に、経路探索部４２は、直前に行ったＳ１１１４にてヒープテーブルに新たに追加された候補リンクの中に、目的地が存在あるいは目的地に近接するリンク（目的地リンクと呼ぶ）があるか否かを調べる（Ｓ１１１６）。
【００６９】
Ｓ１１１６において目的地リンクがないと判断したならば、経路探索部４２は、ヒープテーブルに登録されている各候補リンクのレコード４３００を総旅行時間の小さい順にソートし、フィールド４３０６の抽出フラグが「未」の候補リンク（未抽出リンクと呼ぶ）の中で、最も上位に位置する未抽出リンクを抽出するなどして、ヒープテーブルから総旅行時間が最小の未抽出リンクを抽出する。そして、現在の抽出リンクをこの未抽出リンクに変更し、この未抽出リンクのレコード４３００のフィールド４３０６に登録されている抽出フラグを「未」から「済」に変更する（Ｓ１１１８）。それから、Ｓ１１０６に戻る。
【００７０】
一方、Ｓ１１１６において目的地リンクがあると判断したならば、経路探索部４２は、推奨経路決定処理を行う。具体的には、ヒープテーブルから、目的地リンクの接続元リンク（目的地リンクのレコード４３００のフィールド４３０３にリンクＩＤが登録されている候補リンク）を検索し、検索したリンクを推奨経路を構成するリンク（構成リンクと呼ぶ）に決定する。次に、構成リンクの接続元リンクがあるか否かを調べ、接続元リンクがあるならば、この接続元リンクを構成リンクに決定して、その接続元リンクがあるか否かをさらに調べる。この処理を、構成リンクの接続元リンクがなくなるまで、つまり、構成リンクが、出発地が存在あるいは出発地に近接するリンク（出発地リンクと呼ぶ）となるまで繰り返すことで、推奨経路を構成する各構成リンクを決定する。それから、経路探索部４２は、推奨経路の情報として、推奨経路を構成する各構成リンクのリンクデータ３１２およびＳ１１１０で入手した旅行時間を、出発時刻の情報と共に、経路記憶部４３に記憶する（Ｓ１１２０）。
【００７１】
以上の処理により、推奨経路を構成する各構成リンクのコストは、次のようになる。すなわち、推奨経路を構成する１番目のリンクの旅行時間として、出発時刻を含む時間帯に対応する予測交通情報または統計交通情報より求まる旅行時間が用いられる。また、推奨経路を構成するｎ番目（ｎ≧２）のリンクの旅行時間として、当該ｎ番目のリンクと接続するｎ-１番目のリンクの終了ノードへの予想到着時刻を含む時間帯に対応する予測交通情報または統計交通情報より求まる旅行時間が用いられる。
【００７２】
以上、経路探索処理のフローについて説明した。このフローによれば、予測交通情報があるリンクについては、そのコストとして予測交通情報に含まれる旅行時間を用いる。一方、予測交通情報がないリンクについては、そのコストとして、統計交通情報を用いる。したがって、予測交通情報を入手できなかったリンクについても、除外することなく経路探索を行うことができる。
【００７３】
また、予測交通情報は、通常、リアルタイムに生成されるので、統計交通情報に比べ精度が高い。上記経路探索処理のフローによれば、予測交通情報を優先的に使用して経路探索するので、より実情に即した推奨経路を探索することができる。
【００７４】
本発明は、上記実施形態に限定されず、さまざまな変形が可能である。
【００７５】
例えば、車載用ナビゲーション装置は、交通情報配信サーバ２００から、統計交通情報を補正するための補正情報を入手する。そして、予測交通情報がないリンクについては、補正情報により補正した統計交通情報を用いてコストを定め、経路探索を行うようにしてもよい。
【００７６】
具体的には、交通情報配信サーバ２００は、自身の記憶装置に、車載用ナビゲーション装置が保持する統計交通情報に含まれるリンク旅行時間を補正するための情報（補正情報）を記憶している。補正情報は、現在の交通情報と過去の交通情報を比較してリアルタイムに生成されたものである。
【００７７】
補正情報としては、例えば、統計交通情報の旅行時間に対して一律に増加させる値（例えば＋１０分）、一律に減少させる値（例えば−１０分）、一律に乗じる値（例えば、×１．２）などである。
【００７８】
そして、予測交通情報をダウンロードする際、交通情報配信サーバ２００は、この補正情報もダウンロードする。
【００７９】
車載用ナビゲーション装置は、図１１で示したフローのように、予測交通情報に旅行時間が含まれているリンクについては、そのリンクのコストとして、その旅行時間を用いる。
【００８０】
一方、予測交通情報に旅行時間が含まれていないリンクについては、統計交通情報の中から注目時間帯の旅行時間を得る。そして、さらに、その旅行時間を補正情報を用いて補正し、補正して得た値をそのリンクの旅行時間とする。
【００８１】
具体的には、補正情報が、統計交通情報の旅行時間に対して一律に増加させる値（例えば＋１０分）である場合、統計交通情報の旅行時間をその値で増加させる。一律に減少させる値（例えば−１０分）である場合、統計交通情報の旅行時間をその値で減少させる。一律に乗じる値（例えば、×１．２）である場合、統計交通情報の旅行時間にその値を乗じる。
【００８２】
このようにすれば、予測交通情報がないリンクについては、統計交通情報の旅行時間をさらに補正した旅行時間が用いられる。したがって、より実情に即した経路探索を行うことができる。
【００８３】
また、補正情報を交通情報配信サーバ２００から受信せずに、車載用ナビゲーション装置１００が自ら生成してもよい。すなわち、受信した予測交通情報を用いて統計交通情報の旅行時間を補正するようにしてもよい。
【００８４】
例えば、同一のリンクの同一の時間帯の旅行時間について、ダウンロードした予測交通情報と統計交通情報との差、あるいはＦＭ多重放送受信装置１２若しくはビーコン受信装置１３で受信した現況交通情報と統計交通情報との差を求める。いくつかのリンクについて旅行時間の差を求め、この差を平均する。そして、予測交通情報がないリンクについては、そのリンクの統計交通情報の旅行時間に、求めた差の平均を足して補正する。そして、補正した値を、そのリンクの旅行時間として、経路探索を行う。
【００８５】
このようにすれば、補正情報を交通情報配信サーバ２００から入手しなくても、統計交通情報を補正することができる。
【００８６】
なお、上記では、予測交通情報および統計交通情報がリンク旅行時間を含む場合について説明したが、リンク移動速度を含んでもよい。そして、リンクのコストとしてリンク移動速度を用いてもよい。
【００８７】
なお、本発明を車載用ナビゲーション装置に適用した例について説明したが、本発明は車載用以外のナビゲーション装置にも適用することができる。
【図面の簡単な説明】
【００８８】
【図１】図１は、本発明が適用された実施形態であるナビゲーションシステムの概略構成図である。
【図２】図２は、予測交通情報の構成を示す図である。
【図３】図３は、予測交通情報を生成する方法を説明するための図である。
【図４】図４は、車載用ナビゲーション装置１００の概略構成図である。
【図５】図５は、記憶装置３に記憶されている地図データの構成を示す図である。
【図６】図６は、記憶装置３に記憶されている統計交通情報の構成を示す図である。
【図７】図７は、演算処理部１の機能構成を示す図である。
【図８】図８は、演算処理部１のハードウェア構成を示す図である。
【図９】図９は、車載用ナビゲーション装置１００の処理の概略を示すフロー図である。
【図１０】図１０は、図９のＳ１１０の処理のフロー図である。
【図１１】図１１は、図１０のＳ１１１０の処理のフロー図である。
【図１２】図１２は、経路探索に用いられるヒープテーブルの構成を示す図である。
【符号の説明】
【００８９】
１００…車載用ナビゲーション装置、２００…交通情報配信サーバ、４００…ネットワーク、
１…演算処理部、２…ディスプレイ、３…記憶装置、４…音声出入力装置、５…入力装置、６…車輪速センサ、７…地磁気センサ、８…ジャイロ、９…ＧＰＳ受信機、１１…車内ＬＡＮ装置、１２…ＦＭ多重放送受信装置、１３…ビーコン受信装置、１４…ネットワーク通信装置、２１…ＣＰＵ、２２…ＲＡＭ、２３…ＲＯＭ、２４…ＤＭＡ、２５…描画コントローラ、２６…ＶＲＡＭ、２７…カラーパレット、２８…Ａ/Ｄ変換器、２９…ＳＣＩ、３０…ＰＩＯ、３１…カウンタ、４１…ユーザ操作解析部、４２…経路探索部、４３…経路記憶部、４４…経路誘導部、４５…表示処理部、４６…現在位置算出部、４７…通信処理部、４８…受信情報記憶部
【特許請求の範囲】
【請求項１】
ナビゲーション装置の経路探索方法であって、
現在時刻以降における交通情報を含む予測交通情報と、
過去の交通情報を統計処理して求めた統計交通情報とを用いて、経路を探索することを特徴とする経路探索方法。
【請求項２】
請求項１において、
前記予測交通情報に旅行時間が含まれているリンクについては、当該リンクのコストとして当該旅行時間を用い、
前記予測交通情報に旅行時間が含まれていないリンクについては、当該リンクのコストとして前記統計交通情報に含まれている当該リンクの旅行時間を用いて、総コストが最少の経路を探索する
ことを特徴とする経路探索方法。
【請求項３】
請求項１において、
統計交通情報を補正するための補正情報を入手し、
前記予測交通情報に旅行時間が含まれているリンクについては、当該リンクのコストとして当該旅行時間を用い、
前記予測交通情報に旅行時間が含まれていないリンクについては、当該リンクのコストとして前記統計交通情報に含まれている当該リンクの旅行時間を前記補正情報により補正した値を用いて、
総コストが最少の経路を探索する
ことを特徴とする経路探索方法。
【請求項４】
請求項１において、
前記予測交通情報と前記統計交通情報とを用いて、当該統計交通情報を補正するための補正情報を生成し、
前記予測交通情報に旅行時間が含まれているリンクについては、当該リンクのコストとして当該旅行時間を用い、
前記予測交通情報に旅行時間が含まれていないリンクについては、当該リンクのコストとして前記統計交通情報に含まれている当該リンクの旅行時間を前記補正情報により補正した値を用いて、
総コストが最少の経路を探索する
ことを特徴とする経路探索方法。
【請求項５】
請求項１〜４のいずれか一項において、
前記予測交通情報を、交通情報を配信するサーバからダウンロードする
ことを特徴とする経路探索方法。
【請求項６】
ナビゲーション装置であって、
過去の交通情報を統計処理して求めた統計交通情報を記憶する手段と、
現在時刻以降における交通情報を含む予測交通情報を、交通情報を配信するサーバからダウンロードする手段と、
前記予測交通情報と前記統計交通情報とを用いて、経路を探索する手段を有することを特徴とするナビゲーション装置。
【請求項１】
ナビゲーション装置の経路探索方法であって、
現在時刻以降における交通情報を含む予測交通情報と、
過去の交通情報を統計処理して求めた統計交通情報とを用いて、経路を探索することを特徴とする経路探索方法。
【請求項２】
請求項１において、
前記予測交通情報に旅行時間が含まれているリンクについては、当該リンクのコストとして当該旅行時間を用い、
前記予測交通情報に旅行時間が含まれていないリンクについては、当該リンクのコストとして前記統計交通情報に含まれている当該リンクの旅行時間を用いて、総コストが最少の経路を探索する
ことを特徴とする経路探索方法。
【請求項３】
請求項１において、
統計交通情報を補正するための補正情報を入手し、
前記予測交通情報に旅行時間が含まれているリンクについては、当該リンクのコストとして当該旅行時間を用い、
前記予測交通情報に旅行時間が含まれていないリンクについては、当該リンクのコストとして前記統計交通情報に含まれている当該リンクの旅行時間を前記補正情報により補正した値を用いて、
総コストが最少の経路を探索する
ことを特徴とする経路探索方法。
【請求項４】
請求項１において、
前記予測交通情報と前記統計交通情報とを用いて、当該統計交通情報を補正するための補正情報を生成し、
前記予測交通情報に旅行時間が含まれているリンクについては、当該リンクのコストとして当該旅行時間を用い、
前記予測交通情報に旅行時間が含まれていないリンクについては、当該リンクのコストとして前記統計交通情報に含まれている当該リンクの旅行時間を前記補正情報により補正した値を用いて、
総コストが最少の経路を探索する
ことを特徴とする経路探索方法。
【請求項５】
請求項１〜４のいずれか一項において、
前記予測交通情報を、交通情報を配信するサーバからダウンロードする
ことを特徴とする経路探索方法。
【請求項６】
ナビゲーション装置であって、
過去の交通情報を統計処理して求めた統計交通情報を記憶する手段と、
現在時刻以降における交通情報を含む予測交通情報を、交通情報を配信するサーバからダウンロードする手段と、
前記予測交通情報と前記統計交通情報とを用いて、経路を探索する手段を有することを特徴とするナビゲーション装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２００６−２０８２７４（Ｐ２００６−２０８２７４Ａ）
【公開日】平成１８年８月１０日（２００６．８．１０）
【国際特許分類】
【出願番号】特願２００５−２２７５５（Ｐ２００５−２２７５５）
【出願日】平成１７年１月３１日（２００５．１．３１）
【出願人】（５９１１３２３３５）株式会社ザナヴィ・インフォマティクス (745)
【Ｆターム（参考）】
【公開日】平成１８年８月１０日（２００６．８．１０）
【国際特許分類】
【出願日】平成１７年１月３１日（２００５．１．３１）
【出願人】（５９１１３２３３５）株式会社ザナヴィ・インフォマティクス (745)
【Ｆターム（参考）】
[ Back to top ]