(57)【特許請求の範囲】
【請求項１】
地図データに含まれているリンク情報を用いて、出発地から目的地までの推奨経路を探索するナビゲーション装置であって、
前記地図データ上の道路を構成する各リンクについて、過去に収集されたデータを統計処理することにより求めた統計交通情報を記憶する手段と、
外部から各道路の渋滞状況を示す現状交通情報を取得する手段と、
前記地図データに含まれているリンク情報、前記現状交通情報、および前記統計交通情報を利用して目的地までの推奨経路を探索する経路探索手段と、を備え、
前記統計交通情報には、リンク毎に、前記統計処理により求めた該リンクのコストと、車速の変化に基づいて求められた変化予測情報が対応付けられていて、
前記経路探索手段は、
前記推奨経路の候補となるリンクを抽出した際、該抽出したリンクに対応する前記変化予測情報を参照し、該参照した変化予測情報が該リンクの渋滞状況が変化する傾向にあることを示すデータの場合、該抽出したリンクのコスト算出に前記統計交通情報のコストを利用し、該リンクの渋滞状況が変化する傾向にないことを示すデータの場合、該抽出したリンクのコスト算出に前記現状交通情報のコストを利用すること
を特徴とするナビゲーション装置。
【請求項２】
請求項１に記載のナビゲーション装置であって、
前記統計交通情報の各リンクは、所定の時間帯毎に、前記コストおよび前記変化予測情報が対応付けられていて、
出発時刻の設定を受け付ける手段を有し、
前記候補となるリンクを抽出した場合、出発地から該抽出したリンクに至るまでのコストを算出し、前記受け付けた出発時刻に該コストを加算した到着予測時刻を求め、該到着予測時刻が属する前記時間帯の変化予測情報を参照し、該リンクのコスト算出に、前記統計交通情報のコストを利用するのか、或いは、前記現状交通情報のコストを利用するのかの判定を行うこと
を特徴とするナビゲーション装置。
【請求項３】
請求項１〜２のいずれか一項に記載のナビゲーション装置であって、
前記経路探索手段は、
前記変化予測情報を参照する前に、前記地図データを用いて該リンクが前記出発地から所定距離の範囲内に位置するか否かを判定し、前記出発地から所定距離の範囲内に位置しない場合、該抽出したリンクのコスト算出に前記統計交通情報を利用し、該所定距離の範囲内に位置する場合に前記変化予測情報を参照し、該リンクのコスト算出に前記統計交通情報のコストを利用するのか、或いは、前記現状交通情報のコストを利用するのかの判定を行うこと
を特徴とするナビゲーション装置。
【請求項４】
請求項２に記載のナビゲーション装置であって、
前記統計交通情報は、
前記統計処理により求めたリンクのコストが所定値以上変化する前記時間帯に、該変化する傾向にあることを示す変化予測情報が対応付けられていて、前記統計処理により求めたリンクのコストが所定値以上変化しない前記時間帯に該変化する傾向にないことを示す変化予測情報が対応付けられていること
を特徴とするナビゲーション装置。
【請求項５】
地図データに含まれているリンク情報を用いて、出発地から目的地までの推奨経路を探索するナビゲーション装置であって、
前記地図データ上の道路を構成する各リンクについて、過去に収集されたデータを統計処理することにより求めた統計交通情報を記憶する手段と、
外部から各道路のコストを含む渋滞状況を示す現状交通情報を取得する手段と、
前記地図データに含まれているリンク情報、前記現状交通情報、および前記統計交通情報を利用して目的地までの推奨経路を探索する経路探索手段と、を備え、
前記統計交通情報に含まれるリンクには前記統計処理により求めた該リンクのコストが対応付けられていると共に、該リンクが属するメッシュ毎に、車速の変化に基づいて求められた変化予測情報が対応付けられていて、
前記経路探索手段は、
前記地図データを用いて、前記出発地から前記目的地に至るまでのメッシュを特定し、該特定したメッシュ毎に前記統計交通情報の対応する変化予測情報を参照し、該渋滞状況が変化する傾向にあることを示す変化予測情報に対応付けられているメッシュに対し、該メッシュの中のリンクのコスト算出に前記統計交通情報のコストを利用し、該渋滞状況が変化する傾向にないことを示す変化予測情報に対応付けられているメッシュに対し、該メッシュの中のリンクのコスト算出に前記現状交通情報のコストを利用すること
を特徴とするナビゲーション装置。
【請求項６】
地図データに含まれているリンク情報を用いて、出発地から目的地までの推奨経路を探索するナビゲーション装置が行う経路探索方法であって、
前記地図データ上の道路を構成する各リンクについて、過去に収集されたデータを統計処理することにより求めた統計交通情報を記憶する手段を備え、
前記統計交通情報には、リンク毎に、前記統計処理により求めた該リンクのコストと、車速の変化に基づいて求められた変化予測情報が対応付けられていて、
前記ナビゲーション装置は、
外部から各道路のコストを含む渋滞状況を示す現状交通情報を取得するステップと、
前記地図データに含まれているリンク情報、前記現状交通情報、および前記統計交通情報を利用して目的地までの推奨経路を探索するステップと、を有し、
前記経路を探索するステップは、
前記推奨経路の候補となるリンクを抽出した際、該抽出したリンクに対応する前記変化予測情報を参照し、該参照した変化予測情報が該リンクの渋滞状況が変化する傾向にあることを示すデータの場合、該抽出したリンクのコスト算出に前記統計交通情報のコストを利用し、該リンクの渋滞状況が変化する傾向にない旨を示すデータの場合、該抽出したリンクのコスト算出に前記現状交通情報のコストを利用すること
を特徴とする経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置に関し、特に車載用ナビゲーション装置の経路探索技術に関する。
【背景技術】
【０００２】
従来のナビゲーション装置には、目的地までの経路を探索する際、地図上の道路を構成するリンクデータに加え、外部からの交通情報を利用して目的地までの推奨経路を探索するものがある（例えば特許文献１）。特許文献１のナビゲーション装置は、受信した交通情報を反映させ、渋滞を避けた推奨経路を探索するようにしている。
【０００３】
【特許文献１】特開平１０−１３２５９１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記特許文献１は、以下の問題を有している。具体的には、道路の渋滞状況は、時間により変化する。そのため、特許文献１のように、経路探索を行う前の段階で受信した交通情報を利用して経路探索を行っても、その後、渋滞状況が変化した場合、探索した推奨経路が最適な経路ではないこともある。そのため、例えば、不必要な迂回路を推奨経路として利用者に提示してしまうこともある。また、わずかな時間で大きく渋滞が変化する道路もあり、受信した交通情報をそのまま利用して経路探索を行っても、最適な推奨経路を探索できないこともある。
【０００５】
本発明は、上記事情に鑑みてなされたものであり、本発明の目的は、ナビゲーション装置において最適な推奨経路を探索することにある。
【課題を解決するための手段】
【０００６】
上記課題を解決するため、本発明の一態様は、地図データに含まれているリンク情報を用いて、出発地から目的地までの推奨経路を探索するナビゲーション装置に適用される。
【０００７】
そして、前記ナビゲーション装置は、前記地図データ上の道路を構成する各リンクについて、過去に収集されたデータを統計処理することにより求めた統計交通情報を記憶する手段と、外部から各道路のコストを含む渋滞状況を示す現状交通情報を取得する手段と、前記地図データに含まれているリンク情報、前記現状交通情報、および前記統計交通情報を利用して目的地までの推奨経路を探索する経路探索手段と、を備え、前記統計交通情報には、リンク毎に、前記統計処理により求めた該リンクのコストと、該リンクの渋滞状況が変化する傾向にあるか否かを示す予測情報が対応付けられていて、前記経路探索手段は、前記推奨経路の候補となるリンクを抽出した際、該抽出したリンクに対応する前記予測情報を参照し、該参照した予測情報が該リンクの渋滞状況が変化する傾向にあることを示すデータの場合、該抽出したリンクのコスト算出に前記統計交通情報のコストを利用し、該リンクの渋滞状況が変化する傾向にない旨を示すデータの場合、該抽出したリンクのコスト算出に前記現状交通情報のコストを利用する。
【発明の効果】
【０００８】
このように本発明によれば、経路探索の際、渋滞状況が変化する傾向にない道路に対して現状交通情報を使いコスト計算を行い、渋滞状況が変化する傾向にある道路に対して統計交通情報を使いコスト計算を行うようにしている。
【０００９】
そのため、本発明によれば、ナビゲーション装置において、実際の道路の渋滞状況が反映された経路が探索される可能性を高めることができる。
【発明を実施するための最良の形態】
【００１０】
以下、本発明の実施の形態について図面を用いて説明する。
【００１１】
《第１実施形態》
先ず、本発明の第１実施形態を説明する。
【００１２】
最初に第１実施形態が適用された車載用ナビゲーション装置の概略構成について図１を用いて説明する。
【００１３】
図１は、本発明の第１実施形態の車載用ナビゲーション装置（以下、単に「ナビゲーション装置」という）の概略構成図である。
【００１４】
図示するように、ナビゲーション装置は、演算処理部１と、ディスプレイ２と、地図データ等が記憶された記憶装置３と、音声入出力装置４と、入力装置５と、車輪速センサ６と、地磁気センサ７と、ジャイロ８と、ＧＰＳ（Global Positioning System）受信装置９と、道路の渋滞状況等を示す交通情報（以下では、「リアルタイム交通情報」ということもある）を取得するためのＦＭ多重放送受信装置１０とを有する。
【００１５】
なお、本実施形態では、交通情報を取得するための手段としてＦＭ多重放送受信装置１０を用いているがこれは例示に過ぎない。外部から交通情報を取得できるものであればよい。例えば、ナビゲーション装置に、路上の設置されたビーコンが送信する交通情報を受信するビーコン受信装置を設け、ビーコン受信装置により交通情報を取得するようにしてもよい。また、ナビゲーション装置に、衛星放送で配信される交通情報を受信する受信端末を設け、その受信端末により交通情報を取得するようにしてもよい。
【００１６】
演算処理部１は、ナビゲーション装置が利用者に提供する各種情報を処理するための中心的ユニットである。例えば、各種センサ６〜８やＧＰＳ受信装置９から出力される情報を基にして現在位置を検出する。演算処理部１は、検出した現在位置の周辺の地図データを記憶装置３から読み出して、その読み出した地図データをグラフィックス展開し、そこに現在位置を示すマークを重ねてディスプレイ２に表示する。また、演算処理部１は、現在位置と利用者から指示された目的地とを結ぶ推奨経路を探索し、音声入出力装置４やディスプレイ２を用いて利用者を誘導する。
【００１７】
ディスプレイ２は、演算処理部１で生成された画像データを表示するユニットで、ＣＲＴや液晶ディスプレイ等により構成される。また、演算処理部１とディスプレイ２との間の信号Ｓ１は、ＲＧＢ信号やＮＴＳＣ（National TV Standards Committee）信号で接続するのが一般的である。
【００１８】
記憶装置３は、地図データ３１０（図２参照）や、統計交通情報を記憶するユニットである。なお、記憶装置３には、例えば、ＤＶＤ装置やハードディスク装置を用いることができる。
【００１９】
ここで地図データの構成を説明する。
【００２０】
図２は、記憶装置３に記憶されている地図データのデータ構造を模擬的に示す図である。
【００２１】
図示するように、地図データ３１０は、地図を複数に分割することで得られるメッシュ領域毎に分類されている。地図データ３１０は、メッシュ領域を識別するためのメッシュＩＤ３１１、および、そのメッシュ領域に含まれる道路を構成する各リンクのリンクデータ３１２を有する。
【００２２】
リンクデータ３１２は、リンクを識別するためのリンクＩＤ３１２１、リンクを構成する２つのノード（開始ノード、終了ノード）の座標情報３１２２、リンクが属する道路が「有料道路」であるか「一般道路」であるかを示す道路種別３１２３、リンクの長さを示すリンク長情報３１２４、リンクの旅行時間（或いは移動時間）情報３１２５、および２つのノード（開始ノード、終了ノード）にそれぞれ接続するリンクのリンクＩＤ（接続リンクＩＤ）３１２６などを有する。なお、リンクデータ３１２は、１つのリンクに対して、順方向のデータと、逆方向のデータとが設けられている。
【００２３】
また、記憶装置３には、後述する統計交通情報や座標情報からその座標情報により特定される地点を含むメッシュのメッシュＩＤを特定するためのテーブル（「メッシュ変換テーブル」と呼ぶ）が記憶されている。
【００２４】
図１に戻り、説明を続ける。音声入出力装置４は、演算処理部１で生成した利用者へのメッセージを音声信号に変換して出力すると共に、利用者が発した声を認識し、認識した内容を演算処理部１に転送する。
【００２５】
入力装置５は、ナビゲーション装置の各種機能選択、目的地設定等の利用者からの指示を受け付けるユニットで、スクロールキー、縮尺変更キーなどのハードスイッチ、ジョイステック、ディスプレイ２上に貼られたタッチパネルなどで構成される。
【００２６】
センサ６〜８およびＧＰＳ受信装置９は、ナビゲーション装置が現在位置を検出するために使用するものである。車輪速センサ６は、車輪の円周と計測される車輪の回転数から距離を測定し、さらに対となる車輪の回転数から移動体が曲がった角度を計測する。地磁気センサ７は、地球が保持している磁気を検知し、移動体が向かっている方角を検出する。ジャイロ８は、光ファイバジャイロや振動ジャイロで構成され、車両（移動体）が回転した角度を検出する。ＧＰＳ受信装置９は、ＧＰＳ衛星からの信号を受信し移動体とＧＳＰ衛星間の距離および距離の変化率を３個以上の衛星に対して測定することで移動体の現在位置、進行方向および進行方位を測定する。
【００２７】
ＦＭ多重放送装置１０は、ＦＭ多重放送局（図示しない）が送信する交通情報（リアルタイム交通情報）を受信する。リアルタイム交通情報には、道路の渋滞情報、規制情報、駐車場情報、サービスエリア情報、パーキングエリア情報等が含まれる。渋滞情報には、道路（国道１号線等）毎の速度情報（車両の通過速度を示す情報）が含まれるものとする。
【００２８】
続いて、上述したナビゲーション装置の演算処理部１が有する特徴的な機能について図３を用いて説明する。
【００２９】
図３は、本実施形態の演算処理部１の機能ブロック図である。
【００３０】
図示するように、演算処理部１は、ＵＩ（User Interface）制御部１００、現在位置算出部１１０、交通情報設定部１２０、統計交通情報設定部１３０、経路探索部１４０、および地図表示処理部１５０を有する。
【００３１】
ＵＩ制御部１００は、入力装置５或いは音声入出力装置４に入力された利用者からの要求を受け付け、その要求された内容に対応する処理が実行されるように演算処理部１を制御する。また、ＵＩ制御部１００は、各種操作を誘導するための画像データを生成して、ディスプレイ２に表示する。また、ＵＩ制御部１００は、後述する地図表示処理部１５０が生成した地図の画像データをディスプレイに表示する。
【００３２】
現在位置算出部１１０は、車輪速センサ６で計測される距離パルスデータＳ５およびジャイロセンサ８で計測される角速度データＳ７を各々積分した結果得られる距離データおよび角度データを用いて、そのデータを時間軸で積分していくことにより、初期値（Ｘ,Ｙ）から自車走行後の位置である現在位置（Ｘ´,Ｙ´）を定期的に演算する。そして、現在位置算出部１１０は、上記の算出した現在位置を地図表示処理部１６に出力する。
【００３３】
ここで、現在位置算出部１１０は、自車の回転した角度と進む方向との関係を一致させるため、地磁気センサ７から得られた方位データＳ６と、ジャイロ８から得られ角速度データＳ７を積分した角度データを参照して、自車が進行している方向の絶対方位を推定する。現在位置算出部１１０は、車輪速センサ６のデータＳ５およびジャイロ８のデータＳ７を各々積分していくと、誤差が蓄積するため、ある時間でＧＰＳ受信装置９から得られた位置データＳ８をもとに蓄積した誤差をキャンセルする処理を施し、現在位置のデータを求める。
【００３４】
交通情報設定部１２０は、ＦＭ多重放送受信装置１０を制御し、定期的にリアルタイム交通情報を取得する。交通情報設定部１２０は、取得したリアルタイム交通情報を用いて、リンク毎にコストを対応付けた「現状交通情報」を生成し、ＲＡＭ２２（図４参照）の所定領域に格納する。交通情報設定部１２０は、交通情報を取得するたびに、「現状交通情報」を生成し、ＲＡＭ２２に記憶されている「現状交通情報」を新たに生成したものに更新していく。なお、交通情報設定部１２０が行う処理は、後述する図５で詳細に説明する。
【００３５】
統計交通情報設定部１３０は、地図データ上の道路を構成する各リンクについて、過去に収集されたデータを統計処理することにより求められた各リンクの統計値を含む統計交通情報を記憶装置３から読み出し、統計データ（図８参照）を作成する。記憶装置３に予め記憶されている統計交通情報は、メッシュ毎に、そのメッシュに属する各リンクの所定時間毎の統計値（平均旅行時間、平均速度）が対応付けられている。
【００３６】
なお、統計交通情報設定部１３０が行う統計データ（図８参照）を作成する処理は、ナビゲーション装置の初期設定の際に一度行っておけばよい。統計交通情報設定部１３０が行う処理は、後述する図６〜８で詳細に説明する。
【００３７】
経路探索部１４０は、ダイクストラ法等を用いて、指定された２地点（現在位置（或いは利用者が指定した出発地）、目的地）を結ぶ最適なコストで目的地に到達する推奨経路を探索する。本実施形態の経路探索部１４０は、地図データ３１０（図２）、「統計交通情報」から求めた統計データ（図８）、および交通情報設定部１２０が生成した現状交通情報を用いて、目的地までの推奨経路を探索する。なお、経路探索部１４０が行う処理は、後段で詳細に説明する。
【００３８】
地図表示処理部１５０は、ディスプレイ２に表示が要求される領域にある地図データ３１０を記憶装置３から読み出す。また、地図表示処理部１５０は、経路探索部１４０から探索した推奨経路を受け取ると共に、
現在位置算出部１１０から現在位置の情報を受け取る。そして、地図表示処理部１５０は、道路、その他の地図構成物、現在位置、目的地、および経路誘導のための矢印といったマーク等をディスプレイ２の画面に表示する画像データを生成し、ＵＩ制御部１００に出力する。ＵＩ制御部１００は、地図表示処理部１５０が生成した画像データをディスプレイ２に表示する。
【００３９】
続いて、本実施形態の演算処理部１のハードウェア構成を説明する。
【００４０】
図４は、演算処理部１のハードウェア構成図である。
【００４１】
図示するように、演算処理部１は、ＣＰＵ（中央演算処理装置）２１と、ＣＰＵ２１が実行するプログラムや各種データを一時的に記憶するＲＡＭ（Random Access Memory）２２と、上記各部（ＵＩ制御部１００、現在位置算出部１１０、交通情報設定部１２０、統計交通情報設定部１３０、経路探索部１４０、および地図表示処理部１５０）が有する機能を実行するためのプログラムが予め記憶されているＲＯＭ（Read Only Memory）２３と、メモリ間およびメモリと各デバイスとの間のデータを転送するＤＭＡ（Direct Memory Access）２４と、グラフィック描画を実行し且つ表示制御を行う描画コントローラ２５と、グラフィックスイメージデータを蓄えるＶＲＡＭ（Video  Random  Access  Memory）２６と、イメージデータをＲＧＢ信号に変換するカラーパレット２７と、アナログ信号をデジタル信号に変換するＡ/Ｄ変換器２８と、シリアル信号をバスに同期したパラレル信号に変換するＳＣI(Serial Communication Interface)２９と、パラレル信号をバスに同期させてバス上に載せるＰＩＯ（Parallel Input/Output）３０と、パルス信号を積分するカウンタ３１と、を有する。そして、上記各部（ＵＩ制御部１００、現在位置算出部１１０、交通情報設定部１２０、統計交通情報設定部１３０、経路探索部１４０、および地図表示処理部１５０）の機能は、ＣＰＵ２１が、ＲＯＭ２３に記憶されている上記各部の機能を実行するためのプログラを実行することにより実現される。
【００４２】
続いて、演算処理部１が行う処理について具体的に説明する。
【００４３】
先ず、演算処理部１の交通情報設定部１２０が行う処理について、図５を用いて説明する。
【００４４】
図５は、本実施形態のナビゲーション装置が行う交通情報設定処理のフローチャートである。なお、以下の処理は、所定の時間間隔で定期的に実行される。また、以下の処理は、交通情報設定部１２０が、ＵＩ制御部１００を介して、利用者からの要求（リアルタイム交通情報の取得要求）を受け付けた場合にも実行される。
【００４５】
ここで、交通情報設定部１２０は、リアルタイム交通情報の渋滞情報に含まれる道路毎に、地図データ３１０上のリンク（リンクＩＤ３１２１）を対応付けたリンク変換テーブル（図示しない）を保持しているものとする。
【００４６】
先ず、交通情報設定部１２０は、ＦＭ多重放送受信装置１０に、ＦＭ多重放送局（図示しない）が送信しているリアルタイム交通情報を受信させる（Ｓ２０）。そして、交通情報設定部１２０は、ＦＭ多重放送受信装置１０から、受信したリアルタイム交通情報を取得する。リアルタイム交通情報に含まれる渋滞情報には、上述したように、道路毎に、その道路の速度情報（車両の通過速度を示す情報）が含まれるものとする。
【００４７】
つぎに、交通情報設定部１２０は、Ｓ２０で受信したリアルタイム交通情報から、リンクＩＤ３１２１毎に旅行時間（コスト）を対応付けたデータを求めて、ＲＡＭ２２（図４）の所定領域に格納する（Ｓ３０）。
【００４８】
具体的には、交通情報設定部１２０は、「リンク変換テーブル」を利用して、リアルタイム交通情報の中の渋滞情報をリンクＩＤ毎の速度情報に変換する。さらに、交通情報設定部１２０は、地図データ３１０のリンク長情報３１２４（図２参照）および変換した渋滞情報を用いて、「リンクＩＤ毎に旅行時間（コスト）」を対応付けた「現状交通情報」を生成する。交通情報設定部１２０は、生成した「現状交通情報」をＲＡＭ２２（図４）の所定領域に格納する。交通情報設定部１２０は、ＲＡＭ２２にすでに「現状交通情報」が記憶されている場合、その記憶されている「現状交通情報」を、新たに生成した「現状交通情報」に更新する。
【００４９】
続いて、演算処理部１の統計交通情報設定部１３０が行う処理について図６〜８を参照しながら説明する。
【００５０】
図６および７は、本実施形態の統計交通情報設定部１３０が行う、各リンクの時間帯毎の変化予測情報を求める処理を説明するための図である。図８は、本実施形態の統計データのデータ構成を模擬的に示す図である。
【００５１】
記憶装置３には、予め、地図データ３１０上の道路を構成する各リンクについて、過去に収集されたデータを統計処理することにより求められた各リンクの統計値を含む統計交通情報が記憶されている。統計交通情報は、例えば、各リンクについて、日情報（平日、休日等の情報）別、天気情報（晴れ、雨、雪等の情報）別、時間別にコスト（旅行時間、および平均速度）が対応付けられている。
【００５２】
なお、以下では、説明を簡単にするために、統計交通情報が、各リンクの時間別のコスト（平均旅行時間、および平均速度）である場合を例にする。そして、統計交通情報設定部１３０は、各リンクの所定時間帯毎に変化予測情報を作成する。
【００５３】
変化予測情報とは、統計交通情報を用いて、各リンクの所定時間帯毎に、渋滞状況が変化しているのか、或いは安定しているのかを推定したデータである。統計交通情報設定部１３０は、統計交通情報の中の各リンクに、統計交通情報に含まれる統計値、および変化予測情報を対応付けた統計データを作成して記憶装置３に記憶する。
【００５４】
例えば、図６に示すように、あるメッシュ領域１０００にリンク１〜３が含まれていたとする。この場合、統計交通情報設定部１３０は、統計交通情報に含まれる統計値を用いて、各リンクの所定時間帯毎に、当該リンクの渋滞状況が変化しているか否かを判定する。以下では、リンク１〜３の「８：００〜８：３０」の時間帯において、渋滞状況が変化しているか否かを判定する場合を例にする。
【００５５】
まず、統計交通情報設定部１３０は、記憶している統計交通情報の中から、各リンク１〜３について、順方向および逆方向のそれぞれ、「８：００」の平均速度と、「８：３０」の平均速度とを抽出する。
【００５６】
つぎに、統計交通情報設定部１３０は、各リンク１〜３の方向（順方向、逆方向）毎に、「８：００」の平均速度と、「８：３０」の平均速度との差分を求める。統計交通情報設定部１３０は、差分が所定値より大きければ、その時間帯（ここでは「８：００〜８：３０」）において、リンクの渋滞状況は変化すると推定する。一方、統計交通情報設定部１３０は、差分が所定値より大きくなければ、その時間帯（ここでは「８：００〜８：３０」）において、リンクの渋滞状況は安定していると推定する。
【００５７】
そして、例えば、図７に示すような、推定結果５００が得られる。なお、図示する例では、所定値が「１５ｋｍ/ｈ」とする。
【００５８】
図示するように、リンク１の順方向では、「８：００」の平均速度と、「８：３０」の平均速度との差分（「２０ｋｍ/ｈ」）が所定値（「１５ｋｍ/ｈ」）より大きい。そのため、統計交通情報設定部１３０は、リンク１の順方向は、「８：００〜８：３０」において渋滞状況が変化する傾向にあると推定する（図示する破線５１０で囲むデータ参照）。一方、リンク３の逆方向は、「８：００」の平均速度と、「８：３０」の平均速度との差分（「０ｋｍ/ｈ」）が所定値（「１５ｋｍ/ｈ」）より小さい。そのため、統計交通情報設定部１３０は、リンク３の逆方向は、「８：００〜８：３０」において渋滞状況が変化しない（安定している）傾向にあると推定する（図示する破線５２０で囲むデータ参照）。
【００５９】
なお、本実施形態は、平均速度の差分により、リンクの渋滞状況が変化するか否かを推定しているが、これは例示に過ぎない。例えば、２つの平均速度の差分ではなく、２つの平均速度の変化率により判定するようにしてもよい。例えば、所定値（ｎ％）以上変化していれば、渋滞状況が変化していると推定し、所定値（ｎ％）未満の変化であれば、渋滞状況が安定していると推定する。
【００６０】
また、上記では、所定の時間帯において、開始時刻および終了時刻における平均速度の差分を求めているが、これは例示に過ぎない。時間帯の中の任意の２つの時点のリンクの平均速度の差分を求めるようにしてもよい。或いは、所定の時間帯における平均速度の最大値と最小値の差分により渋滞状況が変化しているか否かを判定するようにしてもよい。また、その他の統計処理で算出した値（例えば、時間帯における複数の時点の平均速度のばらつき）により、渋滞状況が変化する傾向にあるか否かを判定してもよい。
【００６１】
また、本実施形態は、推定結果を示す「変化予測情報」に「１ビット」のデータを用いるものとする。具体的には、渋滞状況が変化すること推定した「変化予測情報」を「１（変化）」で示す。また、渋滞状況が変化しないと推定した「変化予測情報」を「０（安定）」で示す。
【００６２】
そして、統計交通情報設定部１３０は、記憶している統計交通情報の中の全てのリンクの「変化予測情報」を求め、図８に示す統計データ８０１を作成する。なお、統計データ８０１は、予め記憶している統計交通情報に、「変化予測情報」を付加したものである。
【００６３】
図示する統計データ８０１は、メッシュ領域毎に分類されている。統計データ８０１は、メッシュ領域のメッシュＩＤ８０２、および、そのメッシュ領域に含まれる道路を構成する各リンクの交通情報統計値（過去に収集された交通情報の統計値）を管理するための管理データ８１５を有する。メッシュＩＤ８０２は、地図データ３１０のメッシュＩＤ３１１と同じものを用いている。管理データ８１５は、階層構造を有する複数のテーブル８１０、８３０で構成されている。
【００６４】
テーブル８１０は、メッシュＩＤ８０２により登録されるメッシュ領域に含まれる道路を構成する各リンクのリンクＩＤ（なお、１つのリンクには、方向毎（順方向および逆方向）にリンクＩＤが設けれている）に登録するためのテーブルである。リンクＩＤは、地図データ３１０のリンクＩＤ３１２１と同じものを用いている。
【００６５】
テーブル８３０は、テーブル８１０に登録されているリンクＩＤ毎に設けられていて、時間帯毎の交通情報の統計値と、上述の「変化予測情報」とが登録されている。具体的には、テーブル８３０は、時間帯を登録するためのエントリ８３１と、エントリ８３１に登録された時間帯の交通情報の統計値を登録するためのエントリ８３２と、エントリ８３１に登録された時間帯におけるリンクの「変化予測情報」を登録するためのエントリ８３２と、を備える。
【００６６】
時間帯毎の交通情報の統計値は、これらの基となる複数の交通情報により特定されるリンク旅行時間、および平均速度（平均移動速度）を含んでいる。「変化予測情報」は、統計交通情報設定部１３０が作成したデータである。そして、本実施形態のナビゲーション装置は、経路探索を行う際、この「変化予測情報」を参照して、エントリ８３１に登録された交通情報の統計値を利用するか、それとも、リアルタイム交通情報から作成した現状交通情報を利用するかを判定する。
【００６７】
具体的には、本実施形態では、「変化予測情報」が「１（変化）」のリンクは、渋滞状況が変化する道路であるとの推定し、リアルタイム交通情報から求めたリンクのコストを利用しないで、統計交通情報に含まれるコストを利用する。一方、本実施形態では、「変化予測情報」が「０（安定）」のリンクは、渋滞状況が変化しない道路と推定し、リアルタイム交通情報から求めたリンクのコストを利用する。すなわち、統計交通情報に含まれるコストを利用しないで、リアルタイム交通情報から求めたリンクのコストを利用する。
【００６８】
続いて、演算処理部１の経路探索部１４０が行う経路探索処理について、図９を用いて説明する。なお、以下では、推奨経路の探索にダイクストラ法を利用する場合を例にする。
【００６９】
図９は、本実施形態のナビゲーション装置が行う経路探索処理のフローチャートである。以下の処理は、経路探索部１４０が、ＵＩ制御部１００を介して利用者からの出発地および目的地を指定した経路探索要求を受け付けた場合に開始される。なお、以下では、車両の現在位置を出発地とする場合を例にするが、特にこれに限定しない。経路探索部１４０は、ＵＩ制御部１００を介して利用者からの出発地の入力を受付けるようにしてもよい。また、ナビゲーション装置の演算処理部１のメモリ（ＲＡＭ２２）の所定領域には、リアルタイム交通情報を用いて作成した現状交通情報が格納されているものとする。
【００７０】
先ず、経路探索部１４０は、ＵＩ制御部１００を介して、利用者からの経路探索要求を受け付けると、現在位置算出部１１０から現在位置を取得する。また、経路探索部１４０は、ＵＩ制御部１００を介して、利用者からの出発時刻の設定を受け付ける。なお、出発時刻が現在時刻の場合、ナビゲーション装置内のタイマ（図示しない）から取得した現在時刻を出発時刻としてもよい（Ｓ１００）。
【００７１】
つぎに、経路探索部１４０は、推奨経路の探索に必要な地図３１０（図２参照）を記憶装置３から読み出し（Ｓ１０１）、Ｓ１０２の処理に進む。具体的には、経路探索部１４０は、記憶装置３から「メッシュ変換テーブル（図示しない）」を読出し、現在位置および目的地を示す座標情報からその座標情報により特定される地点を含むメッシュ領域のメッシュＩＤを特定する。次に、経路探索部１４０は、記憶装置３より、特定したメッシュＩＤを持つ地図データ３１０を取得する。
【００７２】
Ｓ１０２では、Ｓ１０１で読み込んだ地図データ３１０に含まれるリンクデータ３１２を用いて、後述するＳ１１０でヒープテーブルから抽出されたリンク（抽出リンクという）の終了ノードを開始ノードとするリンクを、推奨経路を構成するリンクの候補のリンク（候補リンクという）として選出する。なお、Ｓ１１０での処理が行われていない場合、つまり、ヒープテーブルにリンクが登録されていない初期段階では、現在位置（出発地）に開始ノードが近接する少なくとも１つのリンクを、候補リンクとして選出する。また、抽出リンクの終了ノードを開始ノードとするリンクが複数ある場合には、複数の候補リンクが選択される。
【００７３】
ここで、ヒープテーブルとは、推奨経路を構成する候補となるリンクのリンクデータを、出発地から当該候補のリンクの終了ノードまでの総コスト（旅行時間等）と共に登録するためのテーブルであり、ＲＡＭ２２の所定領域に記憶されるものである。
【００７４】
続いて、経路探索部１４０は、地図データ３１０を用いて、Ｓ１０２で選択した候補リンクが出発地から所定距離の範囲内に位置するか否かを判定する（Ｓ１０３）。判定の結果、Ｓ１０２で選択した候補リンクが出発地から所定距離の範囲内に位置しなければ、Ｓ１０７の処理に進む。一方、判定の結果、Ｓ１０２で選択した候補リンクが出発地から所定距離の範囲内に位置すれば、Ｓ１０４に進む。
【００７５】
Ｓ１０４では、経路探索部１４０は、記憶装置３から統計データ（図８）を読み出し、候補リンクと同じリンクＩＤに対応付けられている変化予測情報を抽出する。すなわち、候補リンクと同じリンクであり、且つ同じ進行方向に対応付けられている変化予測情報を抽出する。つぎに、経路探索部１４０は、候補リンクへの到着予測時刻を算出する。具体的には、経路探索部１４０は、ヒープテーブルにアクセスし、ヒープテーブルに登録されている抽出リンク（候補リンクの接続元となっているリンク）の総コストを読み出す。経路探索部１４０は、Ｓ１００で取得した現在時刻に読み出した総コストを加算し、その加算した値を到着予測時刻とする。そして、経路探索部１１０は、算出した到着予測時刻が属する時間帯の変化予測情報を参照する。
【００７６】
なお、初期段階では、ヒープテーブルに抽出リンクが登録されていない。その場合、経路探索部１４０は、Ｓ１００で取得した現在時刻が属する時間帯の変化予測情報を参照する。
【００７７】
ここで、図８を例にして、Ｓ１０４の処理を説明する。例えば、候補リンクがリンク１の逆方向であり、算出した候補リンクまで到着予測時刻が「８：３５」であったとする。この場合、経路探索部１４０は、「８：３０〜９：００」の時間帯に対応付けられている変化予測情報（図示する例では、「０（安定）」を参照する。
【００７８】
図９に戻り、説明を続ける。つぎに、経路探索部１４０は、参照した変化予測情報が「安定（０）」を示す情報か否かを判定する（Ｓ１０５）。経路探索部１４０は、変化予測情報が「安定（０）」を示す情報である場合にＳ１０６の処理に進み、「安定（０）」を示す情報ではない場合にＳ１０７の処理に進む。すなわち、本実施形態では、参照した変化予測情報が「安定（０）」を示す情報の場合、候補リンクのその時間帯における道路の渋滞状況が安定している傾向にあると推定し、Ｓ１０６の処理に進む。一方、参照した変化予測情報が「１（変化）」を示す情報の場合、候補リンクのその時間帯における道路の渋滞状況が変化する傾向にあると推定し、Ｓ１０７の処理に進む。
【００７９】
Ｓ１０６では、経路探索部１４０は、ＲＡＭ２２の所定領域に記憶されている「現状交通情報」を用いてコスト計算を行う。本ステップは、候補リンクのその時間帯における道路の渋滞状況が安定していると推定された場合に行われる処理である。そのため、リアルタイム交通情報で受信した渋滞状況が変化していないと推定し、リアルタイム交通情報から作成した「現状交通情報」を利用する。
【００８０】
具体的には、Ｓ１０６では、経路探索部１４０は、メモリ（ＲＡＭ２２）に記憶されている「現状交通情報」にアクセスし、「現状交通情報」の中から、候補リンクと同じリンクＩＤに対応付けられているコスト（旅行時間）を読み出す。経路探索部１４０は、Ｓ１０４でヒープテーブルから読み出した抽出リンク（候補リンクの接続元のリンク）の総コストに、上記の読み出した候補リンクのコスト（旅行時間）を加算する。経路探索部１４０は、この加算して得られた値を出発地から候補リンクの終了ノードまでの総コストとする。
【００８１】
なお、経路探索部１４０は、ヒープテーブルに抽出リンクが登録されていない初期段階では、候補リンクのコスト（現状交通情報から読み出したコスト）を当該候補リンクまでの総コストとする。
【００８２】
つぎに、Ｓ１０３で候補リンクが出発地から所定距離の範囲内に位置しないと判定された場合、および、Ｓ１０５で変化予測情報が「安定」を示す情報ではないと判定した場合に進むＳ１０７について説明する。
【００８３】
Ｓ１０７では、経路探索部１４０は、「統計交通情報」を用いてコスト計算を行う。本ステップは、候補リンクが出発地から所定距離の範囲内に位置しないと判定された場合と、候補リンクのその時間帯における道路の渋滞状況が安定していないと推定された場合に行われる処理である。
【００８４】
候補リンクが出発地から所定距離の範囲内に位置しないと判定された場合、リアルタイム交通情報を受信したときから、ある程度の時間が経過してしいると考えられる。すなわち、受信したリアルタイム交通情報は、候補リンクを実際に車両が通過する際の渋滞状況を反映しないものとなっている可能性が高いと考えられる。そのため、本ステップでは、リアルタイム交通情報から作成した「現状交通情報」を利用しないで、統計交通情報の統計値を利用するようにしている。
【００８５】
また、候補リンクが出発地から所定距離の範囲内に位置しても、候補リンクのその時間帯における道路の渋滞状況が安定していないと推定された場合、リアルタイム交通情報で示された道路状況（渋滞状況）が変化する可能性が高いと考えられる。そのため、本ステップでは、リアルタイム交通情報から作成した「現状交通情報」を利用しないで、統計交通情報の統計値を利用するようにしている。
【００８６】
具体的には、Ｓ１０７では、経路探索部１４０は、Ｓ１０４で読み出した「統計データ（図８）」の中から、候補リンクと同じリンクＩＤに対応付けられている統計値を抽出する。すなわち、候補リンクと同じリンクであり、且つ同じ進行方向に対応付けられているデータ（図８のテーブル８３０）を抽出する。経路探索部１４０は、抽出したデータの中からＳ１０４で算出した到着予測時刻が属する時間帯の統計値を特定する。さらに、経路探索部１４０は、Ｓ１０４でヒープテーブルから読み出した抽出リンクの総コストに、上記の特定した統計値の中のコスト（旅行時間）を加算する。
【００８７】
なお、Ｓ１０７においても、Ｓ１０６と同様、ヒープテーブルに抽出リンクが登録されていない初期段階では、候補リンクのコスト（上記の特定した統計値の中のコスト（旅行時間））を当該候補リンクまでの総コストとする。
【００８８】
つぎに、経路探索部１４０は、候補リンクのリンクデータと、候補リンクの総コストと、をヒープテーブルに追加する（Ｓ１０８）。なお、Ｓ１０２で候補リンクが複数在る場合には、それぞれの候補リンクについて、Ｓ１０３〜Ｓ１０８の処理を行う。
【００８９】
次に、経路探索部１４０は、直前に行ったＳ１０８にてヒープテーブルに新たに追加されたリンクの中に、目的地が存在あるいは目的地に近接するリンク（目的地リンクと呼ぶ）があるか否かを調べる（Ｓ１０９）。経路探索部１４０は、目的地リンクがないと判断したならば、Ｓ１１０の処理に進み、目的地リンクがあると判断した場合には、Ｓ１１１の処理に進む。
【００９０】
Ｓ１１０では、経路探索部１４０は、ヒープテーブルに登録されている未抽出のリンクの情報を総コストの小さい順にソートし、最初に位置するリンクを抽出するなどして、ヒープテーブルから総コストが最小の未抽出のリンクを抽出する。それから、Ｓ１０２に戻る。
【００９１】
続いて、Ｓ１０９において目的地リンクがあると判断した場合に進むＳ１１１の処理について説明する。Ｓ１１１では、経路探索部１４０は、推奨経路決定処理を行う。具体的には、ヒープテーブルから、目的地リンクを発生させたリンク（目的地リンクの開始ノードを終了ノードとするリンク）を検索し、検出したリンクを推奨経路を構成する構成リンクに決定する。次に、構成リンクが、出発地が存在あるいは出発地に近接する出発地リンクであるか否かを調べ、出発地リンクでないならば、この構成リンクを発生させたリンクを検索し、検出したリンクを構成リンクに決定して、それが出発リンクであるか否かをさらに調べる。この処理を、構成リンクが出発リンクであると判断されるまで繰り返すことで、推奨経路を構成する各構成リンクを決定する。
【００９２】
このように、本実施形態では、リアルタイム交通情報の渋滞状況（道路状況）が変化する可能性が高いと考えられるリンクに対して統計交通情報を用いてコスト計算し、リアルタイム交通情報で示された渋滞状況（道路状況）が変化する可能性が低いと考えられるリンクに対してリアルタイム交通情報から求めた現状交通情報を用いてコスト計算をするようにしている。
【００９３】
そのため、本実施形態によれば、現実の道路の渋滞状況を反映させた推奨経路が探索される可能性を高めることができる。
【００９４】
なお、第１実施形態では、統計交通情報設定部１３０が、予め記憶している統計交通情報を利用して、図８に示す統計データを求めるようにしているが特にこれに限定するものではない。例えば、ナビゲーション装置のメーカ側において、図８に示すデータを作成し、記憶装置３に格納しておくようにしてもよい。この場合には、演算処理部１に統計交通情報設定部１３０の機能を設ける必要がなくなる。
【００９５】
《第２実施形態》
つぎに、本発明の第２実施形態について説明する。本発明の第２実施形態は、第１実施形態のものと、統計交通情報設定部１３０が行う処理の一部と、経路探索部１４０が行う処理の一部とが異なる以外は、同じである。なお、第２実施形態の説明は、第１実施形態のものと同じ符号を用いることとする。
【００９６】
第２実施形態のナビゲーション装置は、経路探索する際、リンク毎ではなく、メッシュ毎に、リアルタイム交通情報から求めたコストと、統計交通情報のコストとを使い分けるようにしたものである。すなわち、第２実施形態は、メッシュ毎に、道路の渋滞状況が安定しているか否かを推定する。そして、道路の渋滞状況が安定していると推定されたメッシュに属するリンクは、リアルタイム交通情報から求めたコストを利用して経路探索を行う。また、道路の渋滞状況が安定していないと推定されたメッシュに属するリンクは、統計交通情報のコストを利用して経路探索を行う。このようにすることで、第１実施形態と比べて、経路探索の処理時間を短縮することができる。以下、第１実施形態と異なる部分を中心に説明する。
【００９７】
第２実施形態の概略構成は、図１に示すものと同じであり、記憶装置３には、第１実施形態と同様、図２に例示する地図データが記憶されている。また、記憶装置３には、地図データ上の道路を構成する各リンクについて、過去に収集されたデータを統計処理することにより求められた各リンクの統計値が含まれる統計交通情報が記憶されている。なお、第２実施形態では、記憶装置３に記憶されている統計交通情報には、図１４に示すデータ８５０が含まれているものとする。なお、図１４に示すデータ８５０は、図８に示す統計データから、「変化予測情報」を除いたものであるため、ここでの説明は省略する。
【００９８】
また、演算処理部１の機能構成は、図３に示すものと、統計交通情報設定部１３０および経路探索部１４０の機能の一部が異なる以外は同じである。また、演算処理部１のハードウェア構成は、図４に示すものと同じである。以下、第１実施形態と異なる、統計交通情報設定部１３０および経路探索部１４０について説明する。
【００９９】
先ず、第２実施形態の統計交通情報設定部１３０について、図１０〜１２を用いて説明する。
【０１００】
図１０は、本発明の第２実施形態の統計交通情報設定処理のフローチャートである。図１１は、第２実施形態において、各リンクを所定方向にグループ分けする処理を説明するための図である。図１２は、メッシュ毎の変化予測情報を求める処理を説明するための図である。
【０１０１】
そして、以下で説明する処理により、統計交通情報設定部１３０は、記憶装置３に記憶されている地図データおよび統計交通情報を用いて、各メッシュの時間帯毎の変化予測情報を求める。統計交通情報設定部１３０は、各メッシュの時間帯毎に、求めた変化予測情報を対応付けた判定テーブル（図１３参照）を作成し、その判定テーブルを記憶装置３に記憶する。
【０１０２】
先ず、統計交通情報設定部１３０は、変化予測を行う対象のメッシュを選択する（Ｓ２００）。具体的には、統計交通情報設定部１３０は、変化予測情報を求めていない１のメッシュを選択する。ここでは、図６に示すメッシュ１０００を選択したものとする。
【０１０３】
つぎに、統計交通情報設定部１３０は、選択したメッシュの地図データ３１０および統計交通情報を記憶装置３から読み出し（Ｓ２０１）、Ｓ２０２の処理に進む。
【０１０４】
Ｓ２０２では、統計交通情報設定部１３０は、読み出した地図データ３１０を用いて、選択したメッシュに属するリンクを所定方向にグループ分けする。以下では、図１１に例示する方向（方向１〜８）にグループ分けする場合を例にする。すなわち、メッシュ１０００の中の「リンク１（順方向）」、「リンク１（逆方向）」、「リンク２（順方向）」、「リンク２（逆方向）」、「リンク３（順方向）」、および「リンク３（逆方向）」は、それぞれ、方向１〜８のいずれかに分類されることとなる。ここでは、「方向１」に「リンク１（順方向）」および「リンク２（順方向）」が分類され、「方向３」に「リンク３（順方向）」が分類されて、「方向４」に「リンク１（逆方向）」および「リンク２（逆方向）」が分類されて、「方向６」に「リンク２（逆方向）」が分類されたものとする（図１２参照）。
【０１０５】
つぎに、統計交通情報設定部１３０は、予め設定されている時間帯の中から、変化予測情報を求めていない時間帯を選択する（Ｓ２０３）。なお、予め設定されている複数の時間帯とは、１日を所定時間（例えば「３０分」）毎に区切ったものをいう。ここでは、統計交通情報設定部１３０は、「８：００〜８：３０」の時間帯を選択したものとする。
【０１０６】
つぎに、統計交通情報設定部１３０は、リンクが分類された方向毎に、Ｓ２０３で選択した時間帯の開始時刻と終了時刻におけるリンクの平均速度の平均値を算出し（Ｓ２０４）、Ｓ２０５に進む。なお、開始時刻および終了時刻は例示に過ぎない。時間帯の中の任意の２つの時点のリンクの平均速度の平均値を算出するようにしてもよい。
【０１０７】
具体的には、統計交通情報設定部１３０は、Ｓ２０１で読み出した統計交通情報を用いて、Ｓ２０２でリンクが分類された方向毎の上記時間帯の開始時刻と終了時刻の平均速度の平均値を算出する。ここでは、「方向１」、「方向３」、「方向４」および「方向６」の各々について、「８：００」の平均速度の平均値と、「８：３０」の平均速度の平均値とが算出される。
【０１０８】
ここで、図１２に示す「方向１」を例に説明する。「方向１」には、「リンク１（順方向）」および「リンク２（順方向）」が分類されている。この場合、統計交通情報設定部１３０は、Ｓ２０１で読み出した統計交通情報の中から、「リンク１（順方向）」の「８：００」の平均速度と、「リンク２（順方向）」の「８：００」の平均速度とから「方向１」の「８：００」における平均速度の平均値を求める。同様に、統計交通情報設定部１３０は、Ｓ２０１で読み出した統計交通情報の中から、「リンク１（順方向）」の「８：３０」の平均速度と、「リンク２（順方向）」の「８：３０」の平均速度とから「方向１」の「８：３０」における平均速度の平均値を求める。
【０１０９】
Ｓ２０５では、統計交通情報設定部１３０は、リンクが分類された方向毎に、Ｓ２０４で求めた開始時刻の平均速度の平均値と、終了時刻の平均速度の平均値との差分を求める。そして、統計交通情報設定部１３０は、求めた差分が所定値（例えば、１５ｋｍ/ｈ）より大きければ、そのメッシュのその方向のリンクが、渋滞状況が変化する傾向にあるものと推定し、その方向に「変化」を示すデータを対応付ける。なお、変化を示すデータは、第１実施形態と同様、「１」とする。一方、統計交通情報設定部１３０は、求めた差分が所定値より大きくなければ、そのメッシュのその方向のリンクが、渋滞状況が変化しない傾向（安定する傾向）にあるものと推定し、その方向に「安定」を示すデータを対応付ける。なお、安定を示すデータは、第１実施形態と同様、「０」とする。
【０１１０】
例えば、所定値が「１５ｋｍ」に設定されている場合、図１２に示す「方向１（図１２の破線１２００で囲むデータ参照）」は、差分が「２０ｋｍ」であるため、変化予測情報として変化を示すデータ（変化（１））が対応付けられる。また、「方向３（図１２の破線１２０１で囲むデータ参照）」は、差分が「０ｋｍ」であるため、変化予測情報として安定を示すデータ（安定（０））が対応付けられる。
【０１１１】
なお、第２実施形態においても、第１実施形態と同様、平均速度の差分により、リンクの渋滞状況が変化するか否かを推定しているが、これは例示に過ぎない。例えば、２つの平均速度の差分ではなく、２つの平均速度の変化率により判定するようにしてもよい。
【０１１２】
つぎに、統計交通情報設定部１３０は、Ｓ２０５で方向毎に対応付けた変化予測情報を用いて、当該メッシュのＳ２０３で選択した時間帯の変化予測情報を求める（Ｓ２０６）。例えば、統計交通情報設定部１３０は、Ｓ２０５で求めた方向毎の変化予測情報（「変化」および「安定」のいずれかを示す情報）について、その方向に分類されたリンク本数の重み付けをした上でカウントし、「変化」および「安定」のうち、カウントした値が大きい方をメッシュの変化予測情報とする。
【０１１３】
図１２の例では、「方向１」および「方向４」の変化予測情報が「変化（１）」であり、各々、２本のリンクが分類されている。すなわち、変化予測情報が「変化（１）」の方向には、４本のリンクが分類されている。そのため、変化予測情報の「変化」を「４」とカウントする。一方、「方向３」および「方向６」の変化予測情報が「安定（０）」であり、各々、１本のリンクが分類されている。すなわち、変化予測情報が「安定（０）」の方向には、２本のリンクが分類されている。そのため、変化予測情報の「安定」を「２」とカウントする。その結果、カウントされた値が「変化」の方が大きいため、統計交通情報設定部１３０は、メッシュ全体の変化予測情報を「変化（１）」と判定する。
【０１１４】
図１０に戻り、説明を続ける。つぎに、統計交通情報設定部１３０は、全ての時間帯について、変化予測情報を求めたか否かを判定する（Ｓ２０７）。全ての時間帯の変化予測情報を求めたらＳ２０８に進み、まだ、求めていない時間帯があればＳ２０３に戻る。
【０１１５】
Ｓ２０８では、統計交通情報設定部１３０は、全てのメッシュに対して、変化予測情報を求めたか否かを判定する。全てのメッシュの変化予測情報を求めたらＳ２０９に進み、まだ、求めていないメッシュがあればＳ２００に戻り、Ｓ２００〜Ｓ２０８の処理を行う。
【０１１６】
Ｓ２０９では、Ｓ２００〜Ｓ２０８の処理により求めた、各メッシュの時間帯毎に、変化予測情報を対応付けた判定テーブルを作成し、その判定テーブルを記憶装置３に格納して処理を終了する。
【０１１７】
ここで、統計交通情報設定部１３０が作成する判定テーブルを図１３に示す。
【０１１８】
図１３は、第２実施形態の判定テーブルのデータ構成を模擬的に示した図である。
【０１１９】
図示するように、判定テーブルは、メッシュＩＤが登録されたテーブル１３００と、テーブル１３００に登録されたメッシュＩＤ毎に、時間帯毎の変化予測情報を対応付けたテーブル１３１０とを備える。
【０１２０】
なお、上述した統計交通情報設定部１３０が行う図１０の処理は、ナビゲーション装置の初期設定の際（或いは、販売店等でナビゲーション装置を車両に設定する際）に一度行っておけばよい。また、図１０の処理をナビゲーションで行わずに、メーカ側がナビゲーション装置の製造の際に判定テーブルを作成し、記憶装置３に記憶させておいてもよい。この場合には、統計交通情報設定部１３０の構成を省略することができる。
【０１２１】
続いて、第２実施形態の経路探索部１４０について図１５を用いて説明する。
【０１２２】
図１５は、第２実施形態のナビゲーション装置が行う経路探索処理のフローチャートである。なお、以下の処理は、利用者からの出発地および目的地を指定された経路探索要求を受け付けた際に開示される処理である。また、ナビゲーション装置の演算処理部１のメモリ（ＲＡＭ２２）の所定領域には、リアルタイム交通情報から作成した現状交通情報が格納されているものとする。
【０１２３】
先ず、経路探索部１４０は、出発地を含むメッシュを特定すると共に、出発時刻の設定を受け付ける。なお、出発時刻が現在時刻の場合、ナビゲーション装置内のタイマ（図示しない）から取得した現在時刻を出発時刻としてもよい。また、出発地点が車両の現在位置の場合、現在位置算出部１１０が算出した現在位置を出発地とする。経路探索部１４０は、記憶装置３から「メッシュ変換テーブル（図示しない）」を読出し、現在位置および目的地を示す座標情報からその座標情報により特定される地点を含むメッシュ領域のメッシュＩＤを特定する。次に、経路探索部１４０は、記憶装置３より、特定したメッシュＩＤを持つ地図データ３１０を取得する（Ｓ３００）。また、本ステップにおいて、記憶装置３から判定テーブル（図１３）を読み出しておく。
【０１２４】
つぎに、経路探索部１４０は、特定したメッシュが出発地から所定距離の範囲内にあるか否かを判定する（Ｓ３０１）。判定の結果、所定距離の範囲でなければＳ３０５に進み、所定距離の範囲内にあればＳ３０２の処理に進む。
【０１２５】
Ｓ３０２では、経路探索部１４０は、Ｓ３００で読み出した判定テーブル（図１３）の変化予測情報を参照する。具体的には、経路探索部１４０は、特定したメッシュへの到着予測時刻を求める。そして、経路探索部１４０は、判定テーブルの中で、特定したメッシュに対応付けられているテーブル１３１０を読み出す。経路探索部１４０は、読み出したテーブル１３１０の中で、求めた到着予測時刻に対応する時間帯の変化予測情報を参照する。
【０１２６】
ここで、特定したメッシュが出発地を含むメッシュの場合、到着予測時刻は、出発時刻とする。特定したメッシュが出発地を含むメッシュ以外の場合、到着予測時刻は、出発地から当該特定したメッシュのリンクの接続元のリンク（特定したメッシュに隣接するメッシュのリンク）までの経路の総コスト（旅行時間）に、出発時刻を加算するなどして求める。
【０１２７】
つぎに、経路探索部１４０は、Ｓ３０２で参照した変化予測情報が「安定」であるか否かを判定する（Ｓ３０３）。そして、経路探索部１４０は、「安定」の場合には、Ｓ３０４に進み、「安定」ではない場合にＳ３０５に進む。
【０１２８】
Ｓ３０４では、経路探索部１４０は、特定したメッシュ内において、既存の技術のダイクストラ法の手順にしたがい、記憶している現状交通情報のコスト（旅行時間）を用いて経路探索を行う。そして、特定したメッシュ内の経路探索が終了すると、Ｓ３０６に進む。
【０１２９】
このように、Ｓ３０４において現状交通情報を利用するのは、以下の理由による。すなわち、本ステップは、特定したメッシュのその時間帯における道路の渋滞状況が安定していると推定された場合に行われる処理である。そのため、リアルタイム交通情報で受信した道路状況が変化していないと推定し、リアルタイム交通情報から作成した「現状交通情報」を利用するようにしている。
【０１３０】
一方、Ｓ３０１で、特定したメッシュが出発地から所定距離の範囲内に位置しないと判定された場合、および、Ｓ３０３で特定したメッシュの変化予測情報が「安定」ではないと判定された場合に進むＳ３０５について説明する。
【０１３１】
Ｓ３０５では、経路探索部１４０は、特定したメッシュ内において、ダイクストラ法の手順にしたがい、統計交通情報に含まれるデータ８５０（図１４参照）のコスト（旅行時間）を用いて経路探索を行う。具体的には、経路探索部１４０は、記憶装置３から特定したメッシュの統計交通情報を読み出す。そして、経路探索部１４０は、特定したメッシュ内について、読み出した統計交通情報のコストを利用して経路探索を行う。なお、本ステップにおいて、コスト計算をする際、メッシュ内の各リンクへの到着予測時刻を求め、到着予測時刻が属する時間帯の統計値を利用してコスト計算を行う。
【０１３２】
このように、Ｓ３０５において統計交通情報を利用するのは、以下の理由による。特定したメッシュが出発地から所定距離の範囲内に位置しないと判定された場合、リアルタイム交通情報を受信したときから、ある程度の時間が経過していると考えられる。すなわち、受信したリアルタイム交通情報は、特定したメッシュを車両が通過する際の渋滞状況を反映しないものとなっている可能性が高いと考えられる。そのため、本ステップでは、リアルタイム交通情報から作成した「現状交通情報」を利用しないで、統計交通情報の統計値を利用するようにしている。
【０１３３】
また、メッシュが出発地から所定距離の範囲内に位置しても、当該メッシュのその時間帯における道路の渋滞状況が安定していないと推定された場合、リアルタイム交通情報で示された渋滞状況が変化する可能性が高いと考えられる。そのため、本ステップでは、リアルタイム交通情報から作成した「現状交通情報」を利用しないで、統計交通情報の統計値を利用するようにしている。
【０１３４】
Ｓ３０６では、経路探索部１４０は、Ｓ３０５またはＳ３０６で探索された経路が目的地に到着したか否かを判定する。目的地に到達していなければ、Ｓ３０７に進み、目的地に到達していれば、Ｓ３０８に進む。
【０１３５】
Ｓ３０７では、経路探索部１４０は、次ぎのメッシュを特定する。具体的には、経路探索部１４０は、地図データ３１０を用いて、Ｓ３０５またはＳ３０６で探索された経路に接続されるリンクが属するメッシュを特定して、Ｓ３０１の処理に戻る。
【０１３６】
Ｓ３０８では、上述した図９のＳ１１１と同様の手順により目的地から出発地までの推奨経路を決定して処理を終了する。
【０１３７】
なお、Ｓ３０５およびＳ３０６において、ダイクストラ法を利用する場合を説明したがこれは例示に過ぎない。
【０１３８】
このように、第２実施形態においても、第１実施形態と同様の効果を得ることができる。さらに、第２実施形態では、リンク毎に、現状交通情報および統計交通情報のどちらを利用するかを判定する必要がないため、第１実施形態と比較して、処理を短縮することができる。
【０１３９】
なお、第２実施形態では、特定したメッシュまでの到達時刻を求め、その到達時刻を考慮した上で、現状交通情報および統計交通情報のどちらを利用するかを判定しているが、以下のようにしてもよい。
【０１４０】
具体的には、経路探索部１４０は、目的地から出発地に至るまでの経路探索に必要な範囲のメッシュを選ぶ。つぎに、選んだ全てのメッシュの中から、出発地から所定距離の範囲内にあるメッシュを抽出する。そして、抽出した各メッシュに対して、判定テーブル（図１３）を用いて、出発時刻に対応する時間帯の変化予測情報を参照し、メッシュ毎に変化予測情報を対応付けたデータ（参照結果）を作成する。経路探索部１４０は、出発地から所定距離の範囲内のメッシュについて、作成した参照結果にしたがい、現状交通情報および統計交通情報のどちらを選んでコスト計算を行う。なお、出発地から所定距離の範囲内にないメッシュの経路探索には、統計交通情報を利用する。
【０１４１】
このように構成すれば、特定したメッシュまでの到達時刻を求める処理を省略できるため、第２実施形態よりもさらに経路探索処理を短縮することができる。
【０１４２】
《第３実施形態》
つぎに、本発明の第３実施形態を説明する。
【０１４３】
第３実施形態は、第１実施形態および第２実施形態の交通情報設定部１２０の機能の一部と、経路探索部１４０の機能の一部を変更したものである。具体的には、第３実施形態は、交通情報設定部１２０がリアルタイム交通情報を受信した際、リアルタイム交通情報が配信されないエリアがあるか否かを判定する。そして、配信されていないエリアのメッシュＩＤを特定し、そのメッシュＩＤを経路探索部１４０に通知する。なお、交通情報設定部１２０は、第１および第２実施形態と同様、リアルタイム交通情報から現状交通情報を作成して、メモリ（ＲＡＭ２２の所定領域）に格納しておく。そして、経路探索部１４０は、推奨経路を探索する際に、通知されたメッシュのリンクに対しては、メモリの現状交通情報にアクセスしないで、地図データ３１０のコスト（或いは、統計交通情報のコスト）を利用して経路探索を行う。
【０１４４】
以下、第３実施形態の交通情報設定部１２０および経路探索部１４０の処理について説明していく。なお、第３実施形態についても、第１実施形態と同じ符号を用いて説明する。
【０１４５】
最初に、交通情報設定部１２０の処理について図１６を用いて説明する。
【０１４６】
図１６は、本発明の第３実施形態の交通情報の設定処理のフローチャートである。なお、以下の処理は、第１実施形態と同様、所定の時間間隔で定期的に実行される。また、以下の処理は、交通情報設定部１２０が、ＵＩ制御部１００を介して、利用者からの要求（リアルタイム交通情報の取得要求）を受け付けた場合にも実行される。
【０１４７】
また、交通情報設定部１２０は、第１実施形態と同様、交通情報の渋滞情報に含まれる道路毎に、地図データ３１０上のリンクを対応付けたリンク変換テーブルを保持しているものとする。
【０１４８】
先ず、交通情報設定部１２０は、上述した図５のＳ２０と同様に手順により、ＦＭ多重放送受信装置１０から、受信したリアルタイム交通情報を取得する（Ｓ４００）。なお、リアルタイム交通情報は、所定のエリア（例えば、州、市などの行政区画）毎に分類されていて、どのエリアのデータかが識別可能に構成されているものとする。
【０１４９】
つぎに、交通情報設定部１２０は、取得したリアルタイム交通情報の中にデータが無いエリア（例えば、州、市などの行政区画）があるか否かを判定する（Ｓ４０１）。交通情報設定部１２０は、判定の結果、データが無いエリアがある場合にＳ４０３に進み、データが無いエリアが無ければＳ４０４に進む。
【０１５０】
Ｓ４０３では、交通情報設定部１２０は、データが無いエリアのメッシュを特定し、特定したメッシュのリストを作成して、その作成したリストを経路探索部１４０に送信する（Ｓ４０３）。なお、経路探索部１４０は、交通情報設定部１２０からの上記リストを保持しておく。
【０１５１】
Ｓ４０４では、交通情報設定部１２０は、図５のＳ３０と同様の処理を行い、取得したリアルタイム交通情報から、リンク毎にコストを対応付けた現状交通情報を作成し、メモリ（ＲＡＭ２２）の所定領域に格納する。
【０１５２】
続いて、第３実施形態の経路探索部１４０の処理について説明する。第３実施形態の経路探索部１４０は、メモリに記憶している現状交通情報にアクセスする処理が第１実施形態および第２実施形態と異なる以外は同じである。以下、現状交通情報へアクセスする際の処理を説明する。
【０１５３】
図１７は、本発明の第３実施形態のナビゲーション装置が行う、現状交通情報へアクセスする際の処理のフローチャートである。なお、以下の処理は、経路探索でのコスト計算において、リアルタイム交通情報から作成した現状交通情報を利用する場合に開始される。なお、経路探索部１４０は、リアルタイム交通情報がないエリアのメッシュのリスト（以下、「メッシュリスト」という）を保持しているものとする。すなわち、以下の処理を実行する前に、図１６のＳ４０３が行われているものとする。また、メモリ(ＲＡＭ２２)の所定エリアには交通情報設定部１２０が作成した現状交通情報が格納されているものとする。
【０１５４】
まず、経路探索部１４０は、コスト計算の対象のリンクが属するメッシュがリアルタイム交通情報のないエリアか否かの判定を行う（Ｓ５００）。具体的には、経路探索部１４０は、保持しているメッシュリストを参照して、コスト計算の対象のリンクが属するメッシュがリアルタイム交通情報のないエリアか否かを判定する。すなわち、経路探索部１４０は、対象のリンクが属するメッシュがメッシュリストにあれば、対象のリンクが属するメッシュがリアルタイム交通情報のないエリアと判定する。また、経路探索部１４０は、対象のリンクが属するメッシュがメッシュリストになければ、対象のリンクが属するメッシュがリアルタイム交通情報のあるエリアと判定する。
【０１５５】
そして、経路探索部１４０は、対象のリンクが属するメッシュがリアルタイム交通情報のないエリアと判定した場合にＳ５０３に進む。一方、経路探索部１４０は、対象のリンクが属するメッシュがリアルタイム交通情報のあるエリアと判定した場合にＳ５０２に進む（Ｓ５０１）。
【０１５６】
Ｓ５０２では、経路探索部１４０は、メモリの現状交通情報にアクセスして、対応するデータを読み出してコスト計算をする。
【０１５７】
Ｓ５０３では、経路探索部１４０は、メモリの現状交通情報にアクセスすることなく、地図データの中のコストを利用してコスト計算を行う（或いは、統計交通情報の中のコストを利用してコスト計算を行う）。
【０１５８】
このように、第３実施形態では、リアルタイム交通情報の中に、あるエリアのデータだけが無いような場合、そのエリアのデータに対するアクセスを行わないようにしている。そのため、第３実施形態では、不要なメモリへのアクセス処理を省略でき、経路探索処理の処理時間を短縮することができる。
【０１５９】
なお、本発明は以上で説明した実施形態に限定されるものではなく、本発明の要旨の範囲内において種々の変形が可能である。
【０１６０】
例えば、経路探索部１４０は、出発地から所定距離の範囲内にあるリンク毎に、変化予測情報を参照し、変化予測情報が「変化」のリンクを抽出するまで、上記の第１実施形態と同様の処理を行い、変化予測情報が「変化」のリンクを抽出した後は、統計交通情報のコストを利用して経路探索を行うようにしてもよい。すなわち、経路探索部１４０は、変化予測情報が「変化」のリンクを抽出するまで、リアルタイム交通情報から求めたコストを用いるか、統計交通情報のコストを用いるかを判定し、判定結果にしたがいコスト計算を行う。そして、経路探索部１４０は、変化予測情報が「変化」のリンクを抽出した後は、統計交通情報のコストを利用して経路探索を行う。
【０１６１】
また、経路探索部１４０は、出発地から所定距離の範囲内にあるメッシュ毎に、変化予測情報を参照し、変化予測情報が「変化」のメッシュを抽出するまで、上記の第２実施形態と同様の処理を行い、変化予測情報が「変化」のメッシュを抽出した後は、統計交通情報のコストを利用して経路探索を行うようにしてもよい。
【０１６２】
上記実施形態では、出発地から所定距離の範囲内にあるリンク（あるいはメッシュ）について、統計交通情報およびリアルタイム交通情報のいずれかを利用するかを判定するようにしているが、以下のように代えてもよい。すなわち、出発時刻から所定時間が経過するまでは、統計交通情報およびリアルタイム交通情報のいずれかを利用するかを判定し、所定時間が経過した後に通過するリンク（あるいはメッシュ）のコストは、統計交通情報を用いるようにしてもよい。
【０１６３】
また、上記実施形態は、推奨経路を探索する際のコスト計算について説明したが、同様の処理を、推奨経路の所要時間の計算（所要時間の計算では、料金の重み付け等のその他の要素の計算も行なわれる）に利用するようにしてもよい。
【図面の簡単な説明】
【０１６４】
【図１】本発明の実施形態が適用された車載用ナビゲーション装置の概略構成図である。
【図２】本発明の実施形態の記憶装置３に記憶されている地図データのデータ構造を模擬的に示す図である。
【図３】本発明の実施形態の演算処理部１の機能ブロック図である。
【図４】本発明の実施形態の演算処理部１のハードウェア構成図である。
【図５】本発明の第１実施形態のナビゲーション装置が行う交通情報設定処理のフローチャートである。
【図６】本発明の第１実施形態の統計交通情報設定部１３０が行う、各リンクの時間帯毎の変化予測情報を求める処理を説明するための図である。
【図７】本発明の第１実施形態の統計交通情報設定部１３０が行う、各リンクの時間帯毎の変化予測情報を求める処理を説明するための図である。
【図８】本発明の第１実施形態の統計データのデータ構成を模擬的に示す図である。
【図９】本発明の第１実施形態のナビゲーション装置が行う経路探索処理のフローチャートである。
【図１０】本発明の第２実施形態の統計交通情報設定処理のフローチャートである。
【図１１】本発明の第２実施形態の各リンクを所定方向にグループ分けする処理を説明するための図である。
【図１２】本発明の第２実施形態のメッシュ毎の変化予測情報を求める処理を説明するための図である。
【図１３】本発明の第２実施形態の判定テーブルのデータ構成を模擬的に示した図である。
【図１４】本発明の第２実施形態の統計交通情報のデータ構成を模擬的に示した図である。
【図１５】本発明の第２実施形態のナビゲーション装置が行う経路探索処理のフローチャートである。
【図１６】本発明の第３実施形態の交通情報の設定処理のフローチャートである。
【図１７】本発明の第３実施形態のナビゲーション装置が行う、現状交通情報へアクセスする際の処理のフローチャートである。
【符号の説明】
【０１６５】
１…演算処理部、２…ディスプレイ、３…記憶装置、４…音声入出力装置、５…入力装置、６…車輪速センサ、７…地磁気センサ、８…ジャイロ、９…ＧＰＳ受信装置、１０…ＦＭ多重放送受信装置、１５…経路誘導部、１６…地図表示処理部、１７…グラフィックス処理部、２１…ＣＰＵ、２２…ＲＡＭ、２３…ＲＯＭ、２４…ＤＭＡ、２５…描画コントローラ、２６…ＶＲＡＭ、２７…カラーパレット、２８…Ａ/Ｄ変換器、２９…ＳＣＩ、３０…ＰＩＯ、３１…カウンタ、１００…ＵＩ制御部、１１０…現在位置算出部、１２０…交通情報設定部、１３０…統計交通情報設定部、１４０…経路探索部、１５０…地図表示処理部
【図１】
0004696013.tif 000002
【図２】
0004696013.tif 000003
【図３】
0004696013.tif 000004
【図４】
0004696013.tif 000005
【図５】
0004696013.tif 000006
【図６】
0004696013.tif 000007
【図７】
0004696013.tif 000008
【図８】
0004696013.tif 000009
【図９】
0004696013.tif 000010
【図１０】
0004696013.tif 000011
【図１１】
0004696013.tif 000012
【図１２】
0004696013.tif 000013
【図１３】
0004696013.tif 000014
【図１４】
0004696013.tif 000015
【図１５】
0004696013.tif 000016
【図１６】
0004696013.tif 000017
【図１７】
0004696013.tif 000018