(57)【要約】【課題】  右左折にかかる時間を適切に考慮して経路探索する。【解決手段】  ナビゲーション装置は、各分岐点におけるコストを記憶する。分岐点のコストは、過去に収集された交通情報をもとに、統計処理して求められたものであり、収集条件ごとに分類されている。経路探索は、分岐点通過時の状況に対応する収集条件の分岐点のコストを用いて、総コストが最少となる経路を探索する【選択図】図８
2006047246.tif 000002
【特許請求の範囲】
【請求項１】
ナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、
地図上の道路を構成する各リンクのリンクコストと、分岐点におけるコストであるリンク間接続コストとを記憶する記憶装置を有し、
前記リンク間接続コストは、分岐点ごとに、分岐点通過時の状況に対応させて記憶されており、
前記ナビゲーション装置は、
前記リンクコストと、分岐点通過時の状況に対応するリンク間接続コストとを用いて、総コストが最少となる経路を探索する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項２】
請求項２において、
前記分岐点通過時の状況は、日の種類、天気及び時間帯のいずれか1以上であることを特徴とするナビゲーション装置の経路探索方法。
【請求項３】
ナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、
地図上の道路を構成する各リンクのリンクコストと、
過去に収集された交通情報から統計処理により求められ、該交通情報の収集条件毎に分類された、道路の分岐点におけるコストであるリンク間接続コストとを記憶する記憶装置を有し、
前記リンクコストと、分岐点通過時の状況に対応する収集条件のリンク間接続コストとを用いて、総コストが最少となる経路を探索する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項４】
ナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、
地図上の道路を構成する各リンクのリンクコストと、
過去に収集された交通情報から統計処理により求められ、該交通情報の収集条件毎に分類された、道路の分岐点におけるコストであるリンク間接続コストとを記憶する記憶装置を有し、
前記リンクコストと、分岐点通過時の状況に対応する収集条件のリンク間接続コストとを用いて、目的地への到着時刻を算出する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項５】
請求項３において、
前記ナビゲーション装置は、
分岐点通過時の状況に対応する収集条件のリンク間接続コストを用いて、分岐方向に対応する渋滞度を求め、求めた渋滞度を表示する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項６】
請求項５において、
前記ナビゲーション装置は、
分岐方向により渋滞度が異なる場合、分岐方向ごとに渋滞度を表示する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項７】
請求項５において、
前記ナビゲーション装置は、
渋滞度が同じ分岐方向については、いずれか一つの渋滞度を表示する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項８】
請求項５において、
前記ナビゲーション装置は、
分岐方向に対応する交差点進入車線ごとに、渋滞度を表示する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項９】
請求項５において、
前記ナビゲーション装置は、
地図表示の拡大縮尺が所定値以上の場合、分岐方向に対応させて渋滞度を表示することを特徴とするナビゲーション装置の経路探索方法。
【請求項１０】
請求項５において、
前記ナビゲーション装置は、
探索した経路に沿った車線の渋滞度を表示する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項１１】
ナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、
道路の分岐点におけるコストであるリンク間接続コストとを記憶する情報センタから、当該リンク間接続コストを受信し、
分岐点通過時の状況に対応する収集条件のリンク間接続コストを用いて、総コストが最少となる経路を探索する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項１２】
情報センタとナビゲーション装置とを有するナビゲーションシステムの経路探索方法において、
前記情報センタは、道路の分岐点におけるコストであるリンク間接続コストとを記憶し、
分岐方向の間で、リンク間接続コストの差若しくは比が所定値以上である分岐に関するリンク間接続コストを、前記ナビゲーション装置に送信し、
前記ナビゲーション装置は、
前記情報センタから、当該リンク間接続コストを受信し、
分岐点通過時の状況に対応する収集条件のリンク間接続コストを用いて、総コストが最少となる経路を探索する
ことを特徴とするナビゲーションシステムの経路探索方法。
【請求項１３】
ナビゲーション装置の処理方法であって、
前記ナビゲーション装置は、
過去に収集された交通情報から統計処理により求められ、該交通情報の収集条件毎に分類された、道路の分岐点におけるコストであるリンク間接続コストとを記憶する記憶装置を有し、
前記記憶装置に記憶されたリンク間接続コストが実際と異なる場合、実際の旅行により取得した交通情報を、交通情報を収集する情報センタに送信する
ことを特徴とするナビゲーション装置の処理方法。
【請求項１４】
ナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、
地図上の道路を構成する各リンクのリンクコストと、
過去に収集された交通情報から統計処理により求められ、該交通情報の収集条件毎に分類された、道路の分岐点におけるコストであるリンク間接続コストとを記憶する記憶装置を有し、
現在の交通情報を含む現況データを入手し、
前記現況データを、前記記憶装置に記憶されたリンクコストとリンク間接続コストとで補間して、総コストが最少となる経路を探索する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項１５】
請求項１４において、
前記ナビゲーション装置は、
前記現況データにリンク間接続コストが含まれている分岐点については、当該リンク間接続コストを用い、
前記現況データにリンク間接続コストが含まれていない分岐点については、前記記憶装置に記憶されているリンク間接続コストを用いて、総コストが最少となる経路を探索する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項１６】
請求項１４において、
地図上の特定の範囲のリンクについては、前記現況データに含まれるリンク間接続コストを用いて、総コストが最少となる経路を探索する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項１７】
ナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、
地図上の道路を構成する各リンクのリンクデータと、
過去に収集された交通情報から統計処理により求められ、該交通情報の収集条件毎に分類された、各リンクのリンクコストと、
過去に収集された交通情報から統計処理により求められ、該交通情報の収集条件毎に分類された、道路の分岐点におけるコストであるリンク間接続コストとを記憶する記憶装置を有し、
前記リンクデータと、リンク通過時の状況に対応する収集条件のリンクコストと、分岐点通過時の状況に対応する収集条件のリンク間接続コストとを用いて、総コストが最少となる経路を探索する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項１８】
ナビゲーション装置であって、
地図上の道路を構成する各リンクのリンクコストと、分岐点通過時の状況に分類された、分岐点におけるコストであるリンク間接続コストとを記憶する記憶装置と、
前記リンクコストと、分岐点通過時の状況に対応するリンク間接続コストとを用いて、総コストが最少となる経路を探索する手段と
を有することを特徴とするナビゲーション装置。
【請求項１９】
請求項１８において、
前記記憶装置は、右折車線若しくは左折車線があるリンクのみのリンク間接続コストを記憶する
ことを特徴とするナビゲーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置に関し、特に車載用ナビゲーション装置の推奨経路探索処理の技術に関する。
【背景技術】
【０００２】
特許文献１には、右左折時の所要時間を考慮して経路探索を行うナビゲーション装置が記載されている。特許文献１の技術では、一律に定められた右左折時の所要時間を、リンク旅行時間に加算し、総旅行時間が最少となる経路を探索する。
【０００３】
【特許文献１】特開２００２−１６２２４３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、右左折時の所要時間は実際には一律ではない。右左折時の所要時間は、交差点の種類、時間帯等によって異なる。したがって、特許文献１の技術では、右左折時の所要時間を適切に考慮した経路探索ができるとは限らない。
【０００５】
本発明は上記事情に鑑みてなされたものであり、本発明の目的は、より正確に右左折時の所要時間を考慮し、推奨経路を探索することにある。
【課題を解決するための手段】
【０００６】
上記課題を解決すべく本発明のナビゲーション装置の経路探索方法は、ナビゲーション装置の記憶装置に、各分岐点におけるコストを記憶させる。そして、経路探索の際、分岐点ごとのコストを考慮して、コストが最少となる経路を探索する。
【０００７】
例えば、ナビゲーション装置は、地図上の道路を構成する各リンクのリンクコストと、分岐点におけるコストであるリンク間接続コストとを記憶する記憶装置を有する。前記リンク間接続コストは、分岐点ごとに、分岐点通過時の状況に対応させて記憶されている。そして、前記ナビゲーション装置は、前記リンクコストと、分岐点通過時の状況に対応するリンク間接続コストとを用いて、総コストが最少となる経路を探索する。
【０００８】
具体的には、前記ナビゲーション装置は、地図上の道路を構成する各リンクのリンクコストと、過去に収集された交通情報から統計処理により求められ、該交通情報の収集条件毎に分類された、道路の分岐点におけるコストであるリンク間接続コストとを記憶する記憶装置を有する。そして、前記ナビゲーション装置は、前記リンクコストと、分岐点通過時の状況に対応する収集条件のリンク間接続コストを用いて、総コストが最少となる経路を探索する。
【０００９】
また、前記ナビゲーション装置は、分岐点通過時の状況に対応する収集条件のリンク間接続コストを用いて、分岐方向に対応する渋滞度を求め、求めた渋滞度を表示するようにしてもよい。
【発明を実施するための最良の形態】
【００１０】
以下に、本発明の一実施形態について、図面を参照して説明する。
【００１１】
図１は、本発明の一実施形態にかかる車載用ナビゲーション装置１０００の概略構成図である。図示するように、本実施形態の車載用ナビゲーション装置１０００は、演算処理部１と、ディスプレイ２と、データ記憶装置３と、音声入出力装置４と、入力装置５と、車輪速センサ６と、地磁気センサ７と、ジャイロセンサ８と、ＧＰＳ(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)３０と、パルス信号を積分するカウンタ３１と、を有する。
【００３５】
図７は、演算処理部１の機能構成を示す図である。
【００３６】
図示するように、演算処理部１は、ユーザ操作解析部４１と、経路探索部４２と、経路誘導部４４と、現在位置算出部４６と、表示処理部４５とを有する。
【００３７】
現在位置算出部４６は、車輪速センサ６で計測される距離パルスデータＳ５およびジャイロ８で計測される角加速度データＳ７を各々積分した結果得られる距離データおよび角度データを用い、そのデータを時間軸で積分していくことにより、初期位置（Ｘ，Ｙ）から自車走行後の位置である現在地（Ｘ′，Ｙ′）を定期的に演算する。また、演算結果を用いて、マップマッチ処理することにより、形状の相関が最も高い道路（リンク）上に、現在地を合わせ込む。
【００３８】
ユーザ操作解析部４１は、入力装置５に入力されたユーザからの要求を受け、その要求内容を解析して、その要求内容に対応する処理が実行されるように演算処理部１の各部を制御する。例えば、ユーザが推奨経路の探索を要求したときは、目的地を設定するため、地図をディスプレイ２に表示する処理を表示処理部４５に要求する。また、現在地（出発地）から目的地までの経路を演算する処理を経路探索部４２に要求する。
【００３９】
経路探索部４２は、ダイクストラ法等を用いて、指定された２地点（現在地、目的地）間を結ぶ経路のコスト（例えば、旅行時間）が最少となる経路を探索する。
【００４０】
経路誘導部４４は、経路探索部４２で探索された経路を用いて経路誘導を行う。例えば、経路の情報と、現在地の情報とを比較し、交差点等を通過する前に直進すべきか、右左折すべきかを音声出入力装置４を用いて音声でユーザに知らせる。また、経路誘導部４４は、ディスプレイ２に表示された地図上に進行すべき方向を表示して、ユーザに推奨経路を通知する。
【００４１】
表示処理部４５は、ディスプレイ２への表示が要求される領域にある地図データをデータ記憶装置３から受け取り、指定された縮尺、描画方式で、道路、その他の地図構成物や、現在地、目的地、誘導経路のための矢印といったマークを描画するように地図描画コマンドを生成する。また、ユーザ操作解析部４１から出力される命令を受けて、ディスプレイ２への表示が要求される統計交通データをデータ記憶装置３から受け取り、ディスプレイ２に表示中の地図上に、各道路の交通情報を重ねて表示するように地図描画コマンドを生成する。そして、生成したコマンドを、ディスプレイ２に送信する。
【００４２】
［動作の説明］次に、車載用ナビゲーション装置１０００の動作について説明する。図８は、本実施形態の車載用ナビゲーション装置１０００の動作の概略を示すフロー図である。
【００４３】
このフローは、ユーザ操作解析部４１が、音声入出力装置４あるいは入力装置５を介してユーザより推奨経路の探索要求を受け付けることで開始する。
【００４４】
まず、ユーザ操作解析部４１は、出発地を設定する。ユーザ操作解析部４１は、通常、現在位置算出部４６で求めた現在地を出発地に設定する。ユーザ操作解析部４１はまた、ユーザの指示に基づき目的地を設定する。例えばユーザ操作解析部４１は、データ記憶装置３から地図データに登録されている地図構成物を読み込む。ユーザ操作解析部４１は、表示処理部４５を介してディスプレイ２に、これらの地図構成物を表示する。ユーザ操作解析部４１は、入力装置５を介してユーザより、表示中の地図構成物の情報の中から目的地を選択させる。ユーザ操作解析部４１はまた、出発時刻を設定する。現在時刻を出発時刻に設定する場合は、図示していない内蔵タイマなどを用いて推奨経路の探索要求を受け付けた時に取得した現在時刻を出発時刻に設定する（Ｓ１０２）。
【００４５】
次に、経路探索部４２は、現在位置の座標から、出発地および目的地を含む経路探索領域に含まれる各メッシュ領域のメッシュＩＤを特定する。経路探索部４２はまた、データ記憶装置３より、特定したメッシュＩＤを持つ地図データ３１０各々に登録されている各リンクデータ３１２を入手する。経路探索部４２はまた、データ記憶装置３より日付変換テーブルを読み出す。経路探索部４２はまた、日付変換テーブルを用いて、出発日の日の種類を特定する。経路探索部４２はまた、出発日の日付が日付変換テーブルに登録されていない場合、計算ロジックにより日付から日の種類を特定する。この出発日に対応する日の種類を特定する処理は、車載用ナビゲーション装置に組み込まれたソフトウエアで実行するようにしてもよい。こうすれば、日付変換テーブルに登録されている日付の範囲を超えた場合でも、処理を継続実行させることができる（Ｓ１０４）。
【００４６】
次に、経路探索部４２は、Ｓ１０４で入手した各リンクデータ３１２を用いて、後述するＳ１１８でヒープテーブルから抽出された抽出リンクの終了ノードを開始ノードとするリンクを、推奨経路を構成する候補リンクとして選出する。ただし、Ｓ１１８での処理が行われていない場合、つまり、ヒープテーブルにリンクが登録されていない初期段階では、抽出リンクの終了ノードを開始ノードとするリンクを候補リンクとして選出する代わりに、出発地が存在あるいは出発地に近接する少なくとも１つのリンクを、候補リンクとして選出する（Ｓ１０６）。
【００４７】
次に、経路探索部４２は、抽出リンクの終了ノードへの到着予想時刻を算出する。これは、出発時刻に、ヒープテーブルに登録されている抽出リンクまでの旅行時間を加算することで算出できる。このとき、リンク旅行時間のみならず、リンク間の接続旅行時間も加算して、総旅行時間を求める。また、経路探索部４２は、抽出リンクの終了ノードの座標から終了ノードが位置するメッシュ領域のメッシュＩＤを特定する。ただし、Ｓ１１８での処理が行われていない場合、つまり、ヒープテーブルにリンクが登録されていない初期段階では、出発地が位置するメッシュ領域のメッシュＩＤを特定する。そして、経路探索部４２は、ＦＭ多重放送受信装置１２を介して、前記特定したメッシュＩＤと、抽出リンクの終了ノードへの到着予想時刻が属する対象時間帯（注目時間帯と呼ぶ）とを有する天気情報を入手する。なお、車内ＬＡＮ装置１１を介して受信したワイパーの作動状況情報や外気温情報から天気を判断し、この判断結果を天気情報として利用してもよい（Ｓ１０８）。
【００４８】
次に、経路探索部４２は、データ記憶装置３に記憶されているＳ１０４で特定したメッシュＩＤを持つ統計交通データ３２０にアクセスする。そして、この統計交通データ３２０を用いて、候補リンク各々について、注目時間帯の交通情報統計値であって、且つ、Ｓ１０４で特定した日の種類およびＳ１０６で入手した天気情報により特定される天気の種類に対応付けられている交通情報統計値３２２４を入手する。そして交通情報統計値３２２４に含まれるリンク旅行時間３２２５を入手する。
【００４９】
さらに、経路探索部４２は、抽出リンクについて、注目時間帯の交通情報統計値であって、且つ、Ｓ１０４で特定した日の種類およびＳ１０６で入手した天気情報により特定される天気の種類に対応付けられている交通情報統計値３２２４を入手する。そして交通情報統計値３２２４に含まれる接続旅行時間情報３２２６を参照し、各候補リンク（次リンク）への接続旅行時間３２２６３を入手する。
【００５０】
このようにして、経路探索部４２は、候補リンク各々について、リンク旅行時間及び接続旅行時間を求める（Ｓ１１０）。
【００５１】
次に、経路探索部４２は、出発地から候補リンクの終了ノードまでの総コストを算出する。具体的には、ヒープテーブルに登録されている抽出リンクまでの総コストに、Ｓ１１０で求めた候補リンクのコスト（リンク旅行時間）及び接続コスト（接続旅行時間）を加算する。そして、その加算結果を当該候補リンクまでの総コストとする。ただし、ヒープテーブルに抽出リンクが登録されていない初期段階では、Ｓ１１０で算出した候補リンクのコストを当該候補リンクまでの総コストとする。それから、経路探索部４２は、候補リンク各々のリンクデータおよび総コストをヒープテーブルに追加する（Ｓ１１４）。
【００５２】
次に、経路探索部４２は、ヒープテーブルに新たに追加されたリンクの中に、目的地リンクがあるか否かを調べる（Ｓ１１６）。目的地リンクがないと判断した場合（Ｓ１１６でＮｏ）、経路探索部４２は、ヒープテーブルに登録されているリンクの情報を総コストの小さい順にソートし、最初に位置する未抽出のリンクを抽出するなどして、ヒープテーブルから総コストが最小の候補リンク（未抽出リンク）を抽出する（Ｓ１１８）。それから、Ｓ１０６に戻る。
【００５３】
一方、目的地リンクがあると判断した場合（Ｓ１１６でＹｅｓ）、経路探索部４２は、推奨経路決定処理を行う。具体的には、ヒープテーブルから、目的地リンクを発生させたリンク（目的地リンクの開始ノードを終了ノードとするリンク）を検索し、検出したリンクを推奨経路を構成する構成リンクに決定する。次に、構成リンクが、出発地が存在あるいは出発地に近接する出発地リンクであるか否かを調べ、出発地リンクでないならば、この構成リンクを発生させたリンクを検索し、検出したリンクを構成リンクに決定して、それが出発リンクであるか否かをさらに調べる。この処理を、構成リンクが出発リンクであると判断されるまで繰り返すことで、推奨経路を構成する各構成リンクを決定する。
【００５４】
なお、本発明に適用できる経路探索処理は、上記に限られない。本発明をその要旨の範囲で実施可能であれば、他の経路探索方法を採用することもできる。例えば、想定されるメッシュ領域に含まれる、出発地から目的地までのすべての経路についてダイクストラ法等により総当りで調べたのち、その経路の中でコストが最短となる経路を探索する経路探索方法を採用してもよい。
【００５５】
以上、推奨経路を探索する処理について説明した。
【００５６】
経路探索部４２は、推奨経路が探索されると、探索した経路を用いて経路誘導を行うように経路誘導部４４に指示する。これを受けて、経路誘導部４４は、経路誘導を開始する。経路誘導部４４は、ディスプレイ２に推奨経路を表示するなどして、誘導を行う。
【００５７】
図９は、経路誘導中のディスプレイ２の表示画面７０１の一例である。図示するように、経路誘導部４４は、表示画面７０１に、地図７０２を表示する。そして、現在位置７０３とともに、推奨経路７０４を表示する。経路誘導部４４はまた、渋滞の度合い（渋滞度）７０６を表示する。渋滞度７０６は、交通情報統計値３３２４から求めることができる。具体的には、リンク旅行時間３３２５をリンク長３１２４で割った値から移動速度を求め、移動速度の大きさに応じて渋滞度を求める。渋滞度のレベル（例えば、「高」、「中」、「低」）は、移動速度に応じて予め定められている。
【００５８】
経路誘導部４４はまた、交差点などの分岐点７０７の渋滞度７０８を表示する。分岐点の渋滞度７０８は、交通情報統計値３３２４の接続旅行時間情報３２２６から求めることができる。具体的には、接続旅行時間３３２６３に応じて、渋滞度を求める。渋滞度のレベル（例えば、「高」、「中」、「低」）は、接続旅行時間の長さに応じて予め定められている。
【００５９】
また、経路誘導部４４は、渋滞度を表示する際、推奨経路に関係するもののみを表示するようにしてもよい。こうすれば、推奨経路に関係ない情報が表示されず、表示画面が繁雑となるのを防止できる。
【００６０】
また、交差点などの分岐前において、渋滞度が、車線によって異なる場合は、推奨経路上の車線の渋滞度のみを表示してもよい。図９の例では、推奨経路７０４は、交差点７０７において右折している。そこで、表示画面７０１には右車線の渋滞度７０８のみが表示されている。
【００６１】
経路誘導部４４はまた、分岐点の様子を拡大表示してもよい。図１０は、交差点の様子を拡大表示したところを示す図である。図１０の例では、経路誘導部４４は、左折車線７１２、直進車線７１３及び右折車線７１４を有する交差点７１１を拡大表示している。また、経路誘導部４４は、交差点７１１において右折する推奨経路７１５を表示している。また、車線ごとに渋滞度７２１〜７２３を表示している。図９の例では、全ての車線の渋滞度を表示しているが、推奨経路に関係する車線（図１０の例では右折車線７１４）のみの渋滞度を表示するようにしてもよい。
【００６２】
また、経路誘導部４４は、地図表示の拡大縮尺に応じて、車線ごと（分岐方向ごと）の渋滞度を表示するか否か判定してもよい。例えば、経路誘導部４４は、地図表示の拡大縮尺が、分岐方向を表示できるまでになった場合、車線ごとの渋滞度を表示するようにする。
【００６３】
また、経路誘導部４４は、複数の車線において、渋滞度が同じ場合は、一つの渋滞度のみを表示するようにしてもよい。
【００６４】
また、渋滞度は、文字で表示してもよいし、リンクに特定の色を付す等して異なる渋滞度の区間を異なる態様で表示するようにしてもよい。
【００６５】
以上、本発明の一実施形態について説明した。
【００６６】
上記の実施形態によれば、分岐点ごとに右左折にかかる時間を考慮して、推奨経路を探索できる。
【００６７】
また、経路探索において、分岐点での右左折にかかる旅行時間として、一律に定められたものではなく、過去の交通情報から求めた旅行時間を用いる。したがって、出発地から目的地までの旅行時間をより正確に求めることができる。
【００６８】
上記実施形態は、本発明の要旨の範囲内で様々な変形が可能である。
【００６９】
例えば、上記の実施形態では、車載用ナビゲーション装置１０００は、そのデータ記憶装置３に統計交通データ３２０を保持している。本発明は、これに限られない。統計交通データ３２０と同様の交通情報や予測情報を配信するセンタから受信するようにしてもよい。
【００７０】
図１１にかかる場合のナビゲーションシステムの構成の概略を示す。図示するように、ナビゲーションシステムは、車両に搭載された車載用ナビゲーション装置１０００と、無線基地局３０００およびネットワーク４０００を介して接続された交通情報配信センタ２０００と、ＦＭ多重放送局５０００と、交通情報管理センタ６０００と、天気情報管理センタ７０００と、を有する。
【００７１】
交通情報管理センタ６０００は、各地域の最新の交通情報を管理しており、これらの交通情報を、交通情報配信センタ２０００、ＦＭ多重放送局５０００に配信する。
【００７２】
天気情報管理センタ７０００は、各地域の天気情報を管理しており、これらの天気情報を、ＦＭ多重放送局５０００に配信する。
【００７３】
ＦＭ多重放送局５０００は、交通情報管理センタ６０００より配信された各地域の交通情報を放送する。また、ＦＭ多重放送局５０００は、天気情報管理センタ７０００より配信された各地域の天気情報をＦＭ多重放送信号として放送する。なお、天気情報管理センタ７０００からの天気情報は、ＦＭ多重放送局５０００からではなく、後述する交通情報配信センタ２０００から配信されることもあり得る。
【００７４】
交通情報配信センタ２０００は、そのデータベースに、統計交通データを記憶する。統計交通データの構成は、上記、図３で示した統計交通データ３２０の構成と同様とすることができる。
【００７５】
車載用ナビゲーション装置１０００は、図１で示した構成と同様に構成されるが、さらに、交通情報配信センタ２０００と情報の授受を行う通信装置を備える。
【００７６】
以上のような構成において、車載用ナビゲーション装置１０００の経路探索部４２は、通信装置を介して、交通情報配信センタ２０００にアクセスし、交通データをダウンロード（受信）する。このとき、経路探索に使用される交通データ（例えば、出発地から目的地までの経路が含まれるメッシュ領域の統計交通データ）のみを送信するように交通情報配信センタ１０００に要求するようにしてもよい。そして、経路探索部４２は、受信した統計交通データを用いて、出発地から目的地まで推奨経路を探索する。探索処理の流れは、図８で示したフローと同様に行うことができる。
【００７７】
このような実施形態によれば、車載用ナビゲーション装置１０００自身が、統計交通データを保持している必要がない。また、統計交通データが更新された場合でも、交通情報配信センタ２０００にアクセスすることで、容易に最新の交通データを取得することができる。
【００７８】
なお、交通情報配信センタ１０００は、分岐方向ごとの接続旅行時間の差（または比）が所定値以上の分岐に関する接続旅行時間のみ、車載用ナビゲーション装置１０００に送信するようにしてもよい。例えば、直進車線の次リンクへの接続旅行時間を基準として、接続旅行時間の差が所定値以上の車線の接続旅行時間のみを車載用ナビゲーション装置１０００に送信するようにする。こうすれば、情報通信量を軽減できる。
【００７９】
また、上記実施形態において、車載用ナビゲーション装置１０００が搭載された車両が、交通情報を収集するプローブカーとして機能するようにしてもよい。例えば、実際に走行することにより算出された、リンク旅行時間や接続旅行時間を交通情報配信センタ２００に送信する。実際の値と統計交通データに含まれる値とが異なる場合（例えば差または比が所定値以上の場合）に、交通情報配信線２０００に送信するようにしてもよい。例えば、車載用ナビゲーション装置１０００自身が保持する統計交通データまたは、交通情報配信センタ２０００から受信した統計交通データに含まれるリンク旅行時間や接続旅行時間と、実際のリンク旅行時間や接続旅行時間が異なる場合、実際のリンク旅行時間や接続旅行時間を交通情報配信センタ２００に送信する。こうすれば、車載用ナビゲーション装置１０００が搭載された車両は、プローブカーとして機能する。交通情報配信センタ２０００は、効率よく交通情報を収集することができる。
【００８０】
図１２は、かかる実施形態における車載用ナビゲーション装置１０００の処理のフロー図である。このフローは、経路誘導中に行われる。
【００８１】
まず、経路誘導部４４は、現在位置算出部４６の出力から、車両が次のリンクへ移動したか否か判定する（Ｓ２１０）。次のリンクへ移動した場合（Ｓ２１０でＹｅｓ）、経路誘導部４４は、前のリンク（対象リンク）の開始ノードから現在のリンクの開始ノードまでの旅行時間（実際の旅行時間）を走行履歴から算出する（Ｓ２２０）。
【００８２】
次に、経路誘導部４４は、統計交通データ３２０を参照して、対象リンクを走行した日の種類、天気の種類に対応するリンク旅行時間３３２５と接続旅行時間３３２６とを抽出する。そして、抽出したリンク旅行時間３３２５と接続旅行時間３３２６との和を算出する。さらに、算出した和の値と、Ｓ２２０で算出した実際に走行した旅行時間との差を算出する。さらに、算出した差が所定値（例えば５分）以上か否か判定する（Ｓ２３０）。差が所定値未満の場合（Ｓ２３０でＮｏ）、Ｓ２１０に戻って処理を続ける。
【００８３】
一方、差が所定値以上の場合（Ｓ２３０でＹｅｓ）、経路誘導部４４は、実際の旅行時間（対象リンクの開始ノードから次のリンクの開始ノードまでの旅行時間）を交通情報配信センタ２０００に、通信装置を介して送信する（Ｓ２４０）。そして、Ｓ２１０に戻って処理を続ける。なお、実際の旅行時間から、統計交通データのリンク旅行時間３２２５を減じた値を、実際の接続旅行時間（右左折コスト）として、交通情報配信センタ２０００に送信してもよい。
【００８４】
交通情報配信センタ２０００は、車載用ナビゲーション装置１０００から受信した実際の旅行時間を基に、統計処理により、そのリンクのリンク旅行時間、接続旅行時間を算出することになる。
【００８５】
このような実施形態によれば、車載用ナビゲーション装置１０００は、リンク間の接続旅行時間（右左折コスト）を収集するプローブカーとして機能する。
【００８６】
また、統計交通データに格納されている接続旅行時間が実際と異なる場合にのみ、交通情報配信センタ２０００に情報を送信するので、情報通信量を軽減できる。
【００８７】
また、上記実施形態では、統計交通データを用いて経路探索を行っている。これに限らず、現況の交通情報を用いて経路探索を行っても良い。例えば、ビーコンや交通情報配信センタ２０００から受信した現況交通データに、リンク旅行時間やリンク間の接続旅行時間が含まれている場合、それらの情報を用いて経路探索を行う。現況交通データに、リンク旅行時間や接続旅行時間が含まれてない場合は、統計交通データに含まれるリンク旅行時間や接続旅行時間で補間するようにする。具体的には、図８のフローのＳ１１０において、図１３に示す処理を行う。
【００８８】
経路探索部４２は、各候補リンクについて、現況交通データがあるか否か判定する（Ｓ１１０１）。現況交通データがない場合（Ｓ１１０１でＮｏ）、上記実施形態と同様に、統計交通データ３２０の中からリンク旅行時間３３２５を入手する（Ｓ１１０２）。一方、現況交通データがある場合（Ｓ１１０１でＹｅｓ）、現況交通データの候補リンクの旅行時間を入手する（Ｓ１１０３）。
【００８９】
次に、経路探索部４２は、各候補リンクへの接続旅行時間について、現況交通データがあるか否か判定する（Ｓ１１０４）。現況交通データがない場合（Ｓ１１０４でＮｏ）、上記実施形態と同様に、統計交通データ３２０の中から接続旅行時間３３２６を入手する（Ｓ１１０５）。一方、現況交通データがある場合（Ｓ１１０４でＹｅｓ）、現況交通データの接続旅行時間を入手する（Ｓ１１０６）。
【００９０】
そして、経路探索部４２は、全ての候補リンクについてＳ１１０１〜Ｓ１１０６の処理を行うと（Ｓ１１０７）、図７のＳ１１４に移行し処理を続ける。
【００９１】
上記フローによれば、入手した現況交通データを優先的に用いて経路探索を行うことができる。なお、地図上の特定の範囲（例えば、現在位置周辺）については現況交通データを用い、その他の範囲については統計交通データを用いるようにしてもよい。
【００９２】
なお、上記実施形態では、図３に示すように、統計交通データ３２０には、収集した天気の種類ごとに、交通情報統計値３２２４が登録されている。これに限らず、統計交通データ３２０は、天気の収集条件を省略したものとしてもよい。
【００９３】
また、上記実施形態では、統計交通データの中に、リンクごとに、接続旅行時間を格納している。しかし、本発明の要旨を達成できるものであれば、データ構造の形に制限はない。例えば、分岐のノードに対応させて接続旅行時間を格納するようにしてもよい。また、接続旅行時間をリンク旅行時間に含ませてもよい。そして、統計交通データの中に、リンクの車線ごとに、リンク旅行時間を格納するようにしてもよい。また、接続旅行時間があるリンクについては、統計交通データの中に、そのことを示すフラグ情報を含ませてもよい。
【００９４】
また、本発明を車載用ナビゲーション装置に適用した例について説明したが、本発明は車載用以外のナビゲーション装置にも適用することができる。
【図面の簡単な説明】
【００９５】
【図１】図１は、車載用ナビゲーション装置１０００の概略構成図である。
【図２】図２は、データ記憶装置３に記憶されている地図データの構成を示す図である。
【図３】図３は、統計交通データの構成を示す図である。
【図４】図４は、接続旅行時間情報の構成を示す図である。
【図５】図５は、日付から日の種類を特定するための日付変換テーブルの構成を示す図である。
【図６】図６は、演算処理部１のハードウェア構成を示す図である。
【図７】図７は、演算処理部１の機能構成を示す図である。
【図８】図８は、車載用ナビゲーション装置１０００の経路探索処理の概略を示すフロー図である。
【図９】図９は、経路誘導中の推奨経路の表示例を示す図である。
【図１０】図１０は、経路誘導中の交差点拡大図の表示例を示す図である
【図１１】図１１は、統計交通データを交通情報配信センタから受信する実施形態の概略構成図である。
【図１２】図１２は、車両をプローブカーとして機能させる実施形態のフロー図である。
【図１３】図１３は、現況交通データを用いて経路探索する場合の、図８のＳ１１０における処理のフロー図である。
【符号の説明】
【００９６】
１・・・演算処理部、２・・・ディスプレイ、３・・・データ記憶装置、４・・・音声出入力装置、５・・・入力装置、６・・・車輪速センサ、７・・・地磁気センサ、８・・・ジャイロ、９・・・ＧＰＳ受信機、１１・・・車内ＬＡＮ装置、１２・・・ＦＭ多重放送受信装置、１３…ビーコン受信装置、２１・・・ＣＰＵ、２２・・・ＲＡＭ、２３・・・ＲＯＭ、２４・・・ＤＭＡ、２５・・・描画コントローラ、２６・・・ＶＲＡＭ、２７・・・カラーパレット、２８・・・Ａ/Ｄ変換器、２９・・・ＳＣＩ、３０・・・ＰＩＯ、３１・・・カウンタ、４１・・・ユーザ操作解析部、４２・・・経路探索部、４４・・・経路誘導部、４５・・・表示処理部、４６・・・現在位置算出部
【図１】
2006047246.tif 000003
【図２】
2006047246.tif 000004
【図３】
2006047246.tif 000005
【図４】
2006047246.tif 000006
【図５】
2006047246.tif 000007
【図６】
2006047246.tif 000008
【図７】
2006047246.tif 000009
【図８】
2006047246.tif 000010
【図９】
2006047246.tif 000011
【図１０】
2006047246.tif 000012
【図１１】
2006047246.tif 000013
【図１２】
2006047246.tif 000014
【図１３】
2006047246.tif 000015