ナビゲーション装置
【課題】 同一の道路でも車線により交通状況が異なる場合があることに配慮して経路探索を行う。
【解決手段】 ナビゲーション装置は、車線ごとに分類されたリンクコスト（リンク旅行時間）を用いて、経路探索を行う。例えば、ナビゲーション装置は、地図上の道路を構成するリンクの車線ごとのコストを定めたリンクデータを用いて、目的地までの総コストが最少となる経路を探索する。経路上のリンクのコストとして、そのリンクのいずれかの車線のコストであって次のリンクに移動するために走行することになる車線のコストを用いる。
【解決手段】 ナビゲーション装置は、車線ごとに分類されたリンクコスト（リンク旅行時間）を用いて、経路探索を行う。例えば、ナビゲーション装置は、地図上の道路を構成するリンクの車線ごとのコストを定めたリンクデータを用いて、目的地までの総コストが最少となる経路を探索する。経路上のリンクのコストとして、そのリンクのいずれかの車線のコストであって次のリンクに移動するために走行することになる車線のコストを用いる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置に関し、特に車載用ナビゲーション装置の経路探索技術に関する。
【背景技術】
【０００２】
特許文献１には、道路を構成するリンクごとのコスト（旅行時間）を用いて、目的地までのコストが最少となる経路を探索する車載用ナビゲーション装置が記載されている。
【０００３】
【特許文献１】特開平０８−２８７３９３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところで、道路によっては同一方向に複数の車線が存在する場合がある。例えば、右折車線と直進車線がある場合、右折車線は渋滞でも直進車線は順調であるなど、車線によって旅行時間が大きく異なることがある。特許文献１の技術は、このことに配慮していない。
【０００５】
本発明の目的は、車線により交通状況が異なることに配慮して経路探索を行うことにある。
【課題を解決するための手段】
【０００６】
上記課題を解決すべく本発明のナビゲーション装置は、車線ごとに分類されたリンクコストを用いて、経路探索を行う。
【０００７】
例えば、本発明のナビゲーション装置は、地図上の道路を構成するリンクの車線ごとのコスト（例えば、旅行時間）を含むリンクデータを記憶する手段と、前記リンクデータを用いて、目的地までの総コストが最少となる経路を探索する経路探索手段とを備えている。前記経路探索手段は、経路を構成するリンクのコストとして、そのリンクのいずれかの車線のコストであって次のリンクに移動するために走行する車線（例えば、次ぎのリンクが右折後である場合、右折車線）のコストを用いることができる。
【０００８】
また、前記ナビゲーション装置は、過去に収集された交通情報を基に統計処理され収集条件毎に分類された、地図上の道路を構成するリンクの車線ごとのコストを含むリンクデータを記憶する手段と、前記リンクデータを用いて、目的地までの総コストが最少となる経路を探索する経路探索手段とを備えていてもよい。そして、前記経路探索手段は、経路を構成するリンクのコストとして、そのリンクへの到達時における状況に対応する収集条件に分類されているコストであって、そのリンクの次のリンクに移動するために走行する車線のコストを用いるようにしてもよい。
【０００９】
また、前記ナビゲーション装置であって、地図上の道路を構成するリンクの車線ごとの旅行時間を含むリンクデータを記憶する手段と、目的地までの経路を探索する経路探索手段と、前記リンクデータを用いて、前記目的地までの経路を構成する各リンクの旅行時間を加算することで目的地までの総旅行時間を算出する旅行時間算出手段とを備えていてもよい。そして、前記旅行時間算出手段は、経路を構成する各リンクの旅行時間として、そのリンクのいずれかの車線の旅行時間であって次のリンクに移動するために走行する車線の旅行時間を用いるようにしてもよい。
【発明を実施するための最良の形態】
【００１０】
以下に、本発明の一実施形態について、図面を参照して説明する。
【００１１】
図１は、本発明の一実施形態にかかる車載用ナビゲーション装置１０００の概略構成図である。図示するように、本実施形態の車載用ナビゲーション装置１０００は、演算処理部１と、ディスプレイ２と、データ記憶装置３と、音声入出力装置４と、入力装置５と、車輪速センサ６と、地磁気センサ７と、ジャイロセンサ８と、ＧＰＳ(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)３０と、パルス信号を積分するカウンタ３１と、を有する。
【００３３】
図８は、演算処理部１の機能構成を示す図である。
【００３４】
図示するように、演算処理部１は、ユーザ操作解析部４１と、現在位置算出部４２と、経路探索部４３と、経路誘導部４４と、表示処理部４５とを有する。
【００３５】
ユーザ操作解析部４１は、入力装置５に入力されたユーザからの要求を受け、その要求内容を解析して、その要求内容に対応する処理が実行されるように演算処理部１の各部を制御する。例えば、ユーザが推奨経路の探索を要求したときは、目的地を設定するため、地図をディスプレイ２に表示する処理を表示処理部４５に要求する。また、現在地（出発地）から目的地までの経路を演算する処理を経路探索部４３に要求する。
【００３６】
現在位置算出部４２は、車輪速センサ６で計測される距離パルスデータＳ５およびジャイロ８で計測される角加速度データＳ７を各々積分した結果得られる距離データおよび角度データを用い、そのデータを時間軸で積分していくことにより、初期位置（Ｘ，Ｙ）から自車走行後の位置である現在地（Ｘ′，Ｙ′）を定期的に演算する。また、演算結果を用いて、マップマッチ処理することにより、形状の相関が最も高い道路（リンク）上に、現在位置を合わせ込む。また、定期的にＧＰＳ受信装置９の出力値から求められる現在位置により修正する。
【００３７】
経路探索部４３は、ダイクストラ法等を用いて、指定された２地点（現在地、目的地）間を結ぶ経路のコスト（例えば、旅行時間）が最少となる経路を探索する。
【００３８】
経路誘導部４４は、経路探索部４３で探索された経路を用いて経路誘導を行う。例えば、経路の情報と、現在地の情報とを比較し、交差点等を通過する前に直進すべきか、右左折すべきかを音声出入力装置４を用いて音声でユーザに知らせる。また、経路誘導部４４は、ディスプレイ２に表示された地図上に進行すべき方向を表示して、ユーザに推奨経路を通知する。
【００３９】
表示処理部４５は、ディスプレイ２への表示が要求される領域にある地図データをデータ記憶装置３から受け取り、指定された縮尺、描画方式で、道路、その他の地図構成物や、現在地、目的地、誘導経路のための矢印といったマークを描画するように地図描画コマンドを生成する。また、ユーザ操作解析部４１から出力される命令を受けて、ディスプレイ２への表示が要求される統計交通データをデータ記憶装置３から受け取り、ディスプレイ２に表示中の地図上に、各道路の交通情報を重ねて表示するように地図描画コマンドを生成する。そして、生成したコマンドを、ディスプレイ２に送信する。
【００４０】
［動作の説明］次に、車載用ナビゲーション装置１０００の動作について説明する。図９は、本実施形態の車載用ナビゲーション装置１０００の動作の概略を示すフロー図である。
【００４１】
このフローは、ユーザ操作解析部４１が、音声入出力装置４あるいは入力装置５を介してユーザより推奨経路の探索要求を受け付けることで開始する。
【００４２】
まず、ユーザ操作解析部４１は、出発地を設定する。ユーザ操作解析部４１は、通常、現在位置算出部４２で求めた現在地を出発地に設定する。ユーザ操作解析部４１はまた、ユーザの指示に基づき目的地を設定する。例えばユーザ操作解析部４１は、データ記憶装置３から地図データに登録されている地図構成物を読み込む。ユーザ操作解析部４１は、表示処理部４５を介してディスプレイ２に、これらの地図構成物を表示する。ユーザ操作解析部４１は、入力装置５を介してユーザより、表示中の地図構成物の情報の中から目的地を選択させる。ユーザ操作解析部４１はまた、出発時刻を設定する。現在時刻を出発時刻に設定する場合は、図示していない内蔵タイマなどを用いて推奨経路の探索要求を受け付けた時に取得した現在時刻を出発時刻に設定する（Ｓ１０２）。
【００４３】
次に、経路探索部４３は、現在位置の座標から、出発地および目的地を含む経路探索領域に含まれる各メッシュ領域のメッシュＩＤを特定する。経路探索部４３はまた、データ記憶装置３より、特定したメッシュＩＤを持つ地図データ３１０各々に登録されている各リンクデータ３１２を入手する。経路探索部４３はまた、データ記憶装置３より日付変換テーブルを読み出す。経路探索部４３はまた、日付変換テーブルを用いて、出発日の日の種類を特定する。なお、経路探索部４３は、出発日の日付が日付変換テーブルに登録されていない場合、計算ロジックにより日付から日の種類を特定する。この出発日に対応する日の種類を特定する処理は、車載用ナビゲーション装置１０００に組み込まれたソフトウエアで実行するようにしてもよい。こうすれば、日付変換テーブルに登録されている日付の範囲を超えた場合でも、処理を継続実行させることができる（Ｓ１０４）。
【００４４】
次に、経路探索部４３は、Ｓ１０４で入手した各リンクデータ３１２を用いて、後述するＳ１１８でヒープテーブル４２０から抽出された抽出リンクの終了ノードを開始ノードとするリンクを、推奨経路を構成する候補リンクとして選出する。
【００４５】
図１０にヒープテーブル４２０の構成を示す。ヒープテーブル４２０にはリンクＩＤ４２１ごとに、接続元リンクＩＤ４２２と、そのリンクの開始ノードまでの総旅行時間４２３と、そのリンクの車線ごとの旅行時間４２４と、そのリンクの終了ノードまでの車線ごとの総旅行時間４２５と、抽出済みか否かを示すフラグ４２６とを含むレコード４２７が格納されている。
【００４６】
経路探索部４３は、車線情報３１２５を参照して、候補リンクとして、Ｓ１１８で特定した車線に接続するリンクを選出するようにする。すなわち、Ｓ１１８で右折車線が特定されている場合、右折車線３１２５１の接続リンク３１２５２を選出する。左折車線が特定されている場合、左折車線３１２５１の接続リンク３１２５２を選出する、直進車線が特定されている場合、直進車線３１２５１の接続リンク３１２５２を選出する。
【００４７】
なお、Ｓ１１８での処理が行われていない場合、つまり、ヒープテーブル４２０にリンクが登録されていない初期段階では、抽出リンクの終了ノードを開始ノードとするリンクを候補リンクとして選出する代わりに、出発地が存在あるいは出発地に近接する少なくとも１つのリンクを、候補リンクとして選出する（Ｓ１０６）。
【００４８】
次に、経路探索部４３は、候補リンクの開始ノードへの到着予想時刻を下記式により算出する。
（候補リンクの開始ノードへの到着予想時刻）＝（出発時刻）＋（Ｃ１）＋（Ｃ２）
ここで、
Ｃ１：抽出リンクの開始ノードまでの総旅行時間
Ｃ２：抽出リンクの、候補リンクへ接続する車線の旅行時間
抽出リンクの開始ノードまでの総旅行時間Ｃ１は、ヒープテーブル４２０から、抽出リンクのリンクＩＤと同じリンクＩＤ４２１の開始ノードまでの総旅行時間４２３を検索することで求められる。
【００４９】
抽出リンクの候補リンクへ接続する車線の旅行時間Ｃ２は、次ぎのようにして求められる。まず、経路探索部４３は、出発時刻に、抽出リンクの開始ノードまでの総旅行時間Ｃ１を加算して、抽出リンクの開始ノードへの到達予想時刻を求める。そして、抽出リンクの開始ノードの到達予想時刻における天気を、ＦＭ多重放送受信装置１２を介して取得する。さらに、到達予想時刻と取得した天気におけるそのリンクのリンク旅行時間を統計交通データ３２２から取得する。取得した統計交通データ３２２の中のリンク旅行時間３２２５から、次リンクＩＤ３２２５２が候補リンクＩＤである車線３２２５１の旅行時間３２２５３を検索する。検索した旅行時間３２２５３を、抽出リンクの、候補リンクへ接続する車線の旅行時間Ｃ２とする（Ｓ１０８）。
【００５０】
つぎに、経路探索部４３は、抽出リンクの終了ノードの座標から終了ノードが位置するメッシュ領域のメッシュＩＤを特定する。ただし、Ｓ１１８での処理が行われていない場合、つまり、ヒープテーブル４２０にリンクが登録されていない初期段階では、出発地が位置するメッシュ領域のメッシュＩＤを特定する。そして、経路探索部４３は、ＦＭ多重放送受信装置１２を介して、前記特定したメッシュＩＤと、候補リンクの開始ノードへの到着予想時刻が属する時間帯（注目時間帯と呼ぶ）における天気情報を入手する（Ｓ１０８）。
【００５１】
次に、経路探索部４３は、データ記憶装置３に記憶されているＳ１０４で特定したメッシュＩＤを持つ統計交通データ３２０にアクセスする。そして、この統計交通データ３２０を用いて、候補リンクについて、注目時間帯の交通情報統計値であって、且つ、Ｓ１０４で特定した日の種類およびＳ１０６で入手した天気情報により特定される天気の種類に対応付けられている交通情報統計値３２２４を入手する。そして交通情報統計値３２２４に含まれるリンク旅行時間３２２５を入手する（Ｓ１１０）。
【００５２】
次に、経路探索部４３は、出発地から候補リンクの終了ノードまでの総旅行時間４２５を算出する。具体的には、ヒープテーブル４２０に登録されている候補リンクの開始ノードまでの総旅行時間４２３に、Ｓ１１０で求めた候補リンクの旅行時間を加算する。このとき、複数車線がある場合は、車線ごとに、旅行時間を加算して、総旅行時間４２５を求める。ただし、ヒープテーブル４２０に抽出リンクが登録されていない初期段階では、Ｓ１１０で算出した候補リンクの旅行時間を当該候補リンクまでの総旅行時間４２５とする。それから、経路探索部４３は、図１０に示すように、候補リンクのリンクＩＤ４２１、接続元リンクＩＤ（抽出リンクＩＤ）４２２、開始ノードまでの総旅行時間４２３、車線ごとのリンク旅行時間４２４、終了ノードまでの車線ごとの総旅行時間４２５、抽出リンクとして抽出されたか否かを示すフラグ４２６を格納したレコード４２７をヒープテーブル４２０に追加する（Ｓ１１４）。
【００５３】
次に、経路探索部４３は、ヒープテーブル４２０に新たに追加されたリンクの中に、目的地が存在するリンク（目的地リンク）があるか否かを調べる（Ｓ１１６）。
【００５４】
目的地リンクがないと判断した場合（Ｓ１１６でＮｏ）、経路探索部４３は、ヒープテーブル４２０から総旅行時間４２５が最小の未抽出リンクを抽出する。具体的には、リンクの車線ごと付与されたフラグ４２６を調べ、未抽出フラグが付与されている中で、最も小さい総旅行時間４２５を示しているリンクの車線を特定する。そして、特定した車線の存在するリンクを抽出リンクと設定する。それから、Ｓ１０６に戻る（Ｓ１１８）。
【００５５】
一方、目的地リンクがあると判断した場合（Ｓ１１６でＹｅｓ）、経路探索部４３は、推奨経路決定処理を行う。具体的には、ヒープテーブル４２０から、目的地リンクを発生させたリンク（接続元リンク）を検索し、検出したリンクを推奨経路を構成する構成リンクに決定する。次に、構成リンクが、出発地が存在あるいは出発地に近接する出発地リンクであるか否かを調べ、出発地リンクでないならば、この構成リンクを発生させたリンク（接続元リンク）を検索し、検出したリンクを構成リンクに決定して、それが出発リンクであるか否かをさらに調べる。この処理を、構成リンクが出発リンクであると判断されるまで繰り返すことで、推奨経路を構成する各構成リンクを決定する。
【００５６】
なお、目的地までの総旅行時間は、ヒープテーブル４２０を参照して、目的地リンクの終了ノードまでの総旅行時間４２５を検索することより求めることができる。また、目的地までの到着予想時刻は、出発時刻に総旅行時間４２５を加算することで求められる。
【００５７】
以上、推奨経路を探索する処理について説明した。
【００５８】
なお、本発明に適用できる経路探索方法は、上記に限られない。他の経路探索方法を採用することもできる。例えば、想定されるメッシュ領域に含まれる、出発地から目的地までのすべての経路を調べたのち、その経路の中で総旅行時間が最短となる経路を探索するようにしてもよい。このときも、経路を構成するリンクの旅行時間として、そのリンクの経路上の次ぎのリンクに接続する車線の旅行時間を用いるようにする。すなわち、図１１（Ａ）に示すように、次リンクＡに移動する前に、左折する場合は、左折前のリンクＸの旅行時間として、左折車線の旅行時間を用いる。図１１（Ｂ）に示すように、次リンクに移動する前に、右折する場合は、右折前のリンクＸの旅行時間として、右折車線の旅行時間を用いる。図１１（Ｃ）に示すように、次リンクＣに移動する前に、右左折せずに直進する場合は、次リンクＣの前のリンクＸの旅行時間として、直進車線の旅行時間を用いる。
【００５９】
経路探索部４３は、推奨経路が探索されると、探索した経路を用いて経路誘導を行うように経路誘導部４４に指示する。これを受けて、経路誘導部４４は、経路誘導を開始する。経路誘導部４４は、ディスプレイ２に推奨経路、総旅行時間、到達予想時刻を表示するなどして、誘導を行う。
【００６０】
以上、本発明が適用された一実施形態について説明した。
【００６１】
上記実施形態によれば、車線ごとに交通状況が異なることに配慮して、より精度よく推奨経路を探索することができる。
【００６２】
また、リンクのコストとして、過去に収集された交通情報を統計処理した交通情報を用いる。具体的には、そのリンクを通過する状況（通過日時、天気など）に対応する統計交通情報を用いる。したがって、より実情に即した推奨経路の探索を行うことができる。
【００６３】
本実施形態は、右左折時のコストを単に考慮して経路探索する方法とは異なる。道路によっては、右左折と関係なく、車線数が変化する場合がある。そして、同一の道路でも車線によって交通状況が異なる場合がある。本実施形態は、このような実情にも対応でき、より精度良く推奨経路を探索することができる。
【００６４】
本発明は、上記実施形態に限定されない。上記実施形態は、本発明の技術的思想の範囲内でさまざまな変形が可能である。
【００６５】
上記実施形態では、統計交通情報を用いて経路探索する場合について説明したが、ＦＭ多重放送受信装置１２やビーコン受信装置１３またはネットワークを介して交通情報配信センタから受信した現況交通情報を用いて経路探索を行うようにしてもよい。かかる場合、現況交通情報には、車線ごとの交通情報が含まれている。経路探索部４３は、この交通情報からリンクのコスト（旅行時間や車速など）を求める。経路探索の処理は、上記した統計交通情報を用いて探索する場合に比べて単純である。すなわち、ダイクストラ法等によって、経路探索する際、経路のリンクのコストとして、次ぎのリンクに移動するために走行する車線のコストを用いる（図１１参照）。そして、総コストが最少の経路を、目的地までの最適経路として求める。
【００６６】
また、リンクの車線ごとの交通情報を、ビーコンやＦＭ多重放送を介して受信し、記憶装置に記憶するようにしてもよい。そして、記憶した交通情報を用いて、上記実施形態と同様に経路探索に利用するようにしてもよい。
【図面の簡単な説明】
【００６７】
【図１】図１は、車載用ナビゲーション装置１０００の概略構成図である。
【図２】図２は、データ記憶装置３に記憶されている地図データの構成を示す図である。
【図３】図３は、リンクデータの中の車線情報の構成を示す図である。
【図４】図４は、統計交通データの構成を示す図である。
【図５】図５は、統計交通データの中のリンク旅行時間情報の構成を示す図である。
【図６】図６は、日付から日の種類を特定するための日付変換テーブルの構成を示す図である。
【図７】図７は、演算処理部１のハードウェア構成を示す図である。
【図８】図８は、演算処理部１の機能構成を示す図である。
【図９】図９は、車載用ナビゲーション装置１０００の経路探索処理の概略を示すフロー図である。
【図１０】図１０は、経路探索処理に用いるヒープテーブルの構成を示す図である。
【図１１】図１１は、採用するリンク旅行時間を説明するための図である
【符号の説明】
【００６８】
１…演算処理部、２…ディスプレイ、３…データ記憶装置、４…音声出入力装置、５…入力装置、６…車輪速センサ、７…地磁気センサ、８…ジャイロ、９…ＧＰＳ受信機、１２…ＦＭ多重放送受信装置、１３…ビーコン受信装置、２１…ＣＰＵ、２２…ＲＡＭ、２３…ＲＯＭ、２４…ＤＭＡ、２５…描画コントローラ、２６…ＶＲＡＭ、２７…カラーパレット、２８…Ａ/Ｄ変換器、２９…ＳＣＩ、３０…ＰＩＯ、３１…カウンタ、４１…ユーザ操作解析部、４２…現在位置算出部、４３…経路探索部、４４…経路誘導部、４５…表示処理部
【特許請求の範囲】
【請求項１】
ナビゲーション装置であって、
地図上の道路を構成するリンクの車線ごとのコストを含むリンクデータを記憶する手段と、
前記リンクデータを用いて、目的地までの総コストが最少となる経路を探索する経路探索手段と
を備えることを特徴とするナビゲーション装置。
【請求項２】
請求項１において、
前記経路探索手段は、
経路を構成するリンクのコストとして、そのリンクのいずれかの車線のコストであって次のリンクに移動するために走行する車線のコストを用いる
ことを特徴とするナビゲーション装置。
【請求項３】
請求項２において、
前記リンクデータは、時間帯毎のコストを含み、
前記経路探索手段は、
経路を構成するリンクのコストとして、そのリンクへの予想到達時刻が属する時間帯のコストを用いる
ことを特徴とするナビゲーション装置。
【請求項４】
ナビゲーション装置であって、
過去に収集された交通情報を基に統計処理され収集条件毎に分類された、地図上の道路を構成するリンクの車線ごとのコストを含むリンクデータを記憶する手段と、
前記リンクデータを用いて、目的地までの総コストが最少となる経路を探索する経路探索手段とを備え、
前記経路探索手段は、
経路を構成するリンクのコストとして、そのリンクへの到達時における状況に対応する収集条件に分類されているコストであって、そのリンクの次のリンクに移動するために走行する車線のコストを用いる
ことを特徴とするナビゲーション装置。
【請求項５】
請求項４において、
前記過去に収集された交通情報の前記収集条件は、日の種類、天気及び時間帯のいずれか1以上であることを特徴とするナビゲーション装置。
【請求項６】
ナビゲーション装置であって、
地図上の道路を構成するリンクの車線ごとの旅行時間を含むリンクデータを記憶する手段と、
目的地までの経路を探索する経路探索手段と、
前記リンクデータを用いて、前記目的地までの経路を構成する各リンクの旅行時間を加算することで目的地までの総旅行時間を算出する旅行時間算出手段とを備え、
前記旅行時間算出手段は、
経路を構成する各リンクの旅行時間として、そのリンクのいずれかの車線の旅行時間であって次のリンクに移動するために走行する車線の旅行時間を用いる
ことを特徴とするナビゲーション装置。
【請求項７】
請求項１または２において、
リンクの車線ごとの交通情報を含む現況交通情報を受信する受信手段を備え、
前記記憶手段は、前記受信手段が受信した交通情報から求められるリンクの車線ごとのコストを記憶する
ことを特徴とするナビゲーション装置。
【請求項１】
ナビゲーション装置であって、
地図上の道路を構成するリンクの車線ごとのコストを含むリンクデータを記憶する手段と、
前記リンクデータを用いて、目的地までの総コストが最少となる経路を探索する経路探索手段と
を備えることを特徴とするナビゲーション装置。
【請求項２】
請求項１において、
前記経路探索手段は、
経路を構成するリンクのコストとして、そのリンクのいずれかの車線のコストであって次のリンクに移動するために走行する車線のコストを用いる
ことを特徴とするナビゲーション装置。
【請求項３】
請求項２において、
前記リンクデータは、時間帯毎のコストを含み、
前記経路探索手段は、
経路を構成するリンクのコストとして、そのリンクへの予想到達時刻が属する時間帯のコストを用いる
ことを特徴とするナビゲーション装置。
【請求項４】
ナビゲーション装置であって、
過去に収集された交通情報を基に統計処理され収集条件毎に分類された、地図上の道路を構成するリンクの車線ごとのコストを含むリンクデータを記憶する手段と、
前記リンクデータを用いて、目的地までの総コストが最少となる経路を探索する経路探索手段とを備え、
前記経路探索手段は、
経路を構成するリンクのコストとして、そのリンクへの到達時における状況に対応する収集条件に分類されているコストであって、そのリンクの次のリンクに移動するために走行する車線のコストを用いる
ことを特徴とするナビゲーション装置。
【請求項５】
請求項４において、
前記過去に収集された交通情報の前記収集条件は、日の種類、天気及び時間帯のいずれか1以上であることを特徴とするナビゲーション装置。
【請求項６】
ナビゲーション装置であって、
地図上の道路を構成するリンクの車線ごとの旅行時間を含むリンクデータを記憶する手段と、
目的地までの経路を探索する経路探索手段と、
前記リンクデータを用いて、前記目的地までの経路を構成する各リンクの旅行時間を加算することで目的地までの総旅行時間を算出する旅行時間算出手段とを備え、
前記旅行時間算出手段は、
経路を構成する各リンクの旅行時間として、そのリンクのいずれかの車線の旅行時間であって次のリンクに移動するために走行する車線の旅行時間を用いる
ことを特徴とするナビゲーション装置。
【請求項７】
請求項１または２において、
リンクの車線ごとの交通情報を含む現況交通情報を受信する受信手段を備え、
前記記憶手段は、前記受信手段が受信した交通情報から求められるリンクの車線ごとのコストを記憶する
ことを特徴とするナビゲーション装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００７−７１５８１（Ｐ２００７−７１５８１Ａ）
【公開日】平成１９年３月２２日（２００７．３．２２）
【国際特許分類】
【出願番号】特願２００５−２５６４８５（Ｐ２００５−２５６４８５）
【出願日】平成１７年９月５日（２００５．９．５）
【出願人】（５９１１３２３３５）株式会社ザナヴィ・インフォマティクス (745)
【Ｆターム（参考）】
【公開日】平成１９年３月２２日（２００７．３．２２）
【国際特許分類】
【出願日】平成１７年９月５日（２００５．９．５）
【出願人】（５９１１３２３３５）株式会社ザナヴィ・インフォマティクス (745)
【Ｆターム（参考）】
[ Back to top ]