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