(57)【要約】【課題】  旅行費用が安い経路を探索する技術を提供することにある。【解決手段】  例えば、ナビゲーション装置は、車種ごとに、車速に応じた燃費情報を記憶している。そして、リンクデータと燃費情報とを用いて、燃料消費量が最少の経路を探索する。また、燃費検出センサにより収集した過去の燃費情報を用いて経路探索する。また、燃料単価から燃料費用が最少の経路を探索する。さらに、有料道路情報を用いて、費用が最少の経路を探索する。【選択図】図１０
2005172582.tif 000002
【特許請求の範囲】
【請求項１】
ナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、
地図上の道路を構成するリンクデータと、前記ナビゲーション装置が搭載される移動体の移動速度に応じた燃費を含む燃費情報とを記憶する記憶装置を有し、
前記リンクデータと前記燃費情報とを用いて、出発地から目的地までの燃料消費量が最少の経路を探索する経路探索ステップを行う
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項２】
ナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、
地図上の道路を構成するリンクデータを記憶する記憶装置と、
前記ナビゲーション装置が搭載される移動体の燃費を検出する燃費検出センサとを有し、
前記燃費検出センサにより過去に収集した情報から移動速度に応じた燃費を含む燃費情報を作成するステップと、
前記リンクデータと前記燃費情報とを用いて、出発地から目的地までの燃料消費量が最少の経路を探索する経路探索ステップとを行う
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項３】
請求項１または２に記載のナビゲーション装置の経路探索方法であって、
前記記憶装置は、さらに燃料単価を記憶し、
前記経路探索ステップは、前記リンクデータと前記燃費情報と前記燃料単価と用いて、出発地から目的地までの燃料費用が最少の経路を探索する
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項４】
請求項３に記載のナビゲーション装置の経路探索方法であって、
前記記憶装置は、さらに、有料道路の料金情報を含む有料道路情報記憶し、
前記経路探索ステップは、前記リンクデータと前記燃費情報と前記燃料単価と前記有料道路情報とを用いて、出発地から目的地までの費用が最少の経路を探索することを特徴とするナビゲーション装置の経路探索方法。
【請求項５】
請求項３または４に記載のナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、さらに、
前記燃料単価の入力を受け付ける燃料単価受付ステップと、
前記燃料単価受付ステップで受け付けた燃費単価を前記記憶装置に記憶させるステップとを行うことを特徴とするナビゲーション装置の経路探索方法。
【請求項６】
請求項１〜５のいずれか一項に記載のナビゲーション装置の経路探索方法であって、
前記記憶装置は、移動体の種類ごとの燃費情報を記憶し、
前記経路探索ステップは、前記燃費情報を用いる際、前記ナビゲーション装置が搭載された移動体の種類に対応した燃費情報を用いる
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項７】
請求項６に記載のナビゲーション装置の経路探索方法であって、
前記移動体の種類は、移動体の燃料排気量により区別される種類である
ことを特徴とするナビゲーション装置の経路探索方法。
【請求項８】
請求項１〜７のいずれか一項に記載のナビゲーション装置の経路探索方法であって、
前記ナビゲーション装置は、さらに、
前記燃費情報の入力を受け付ける燃費情報受付ステップと、
前記燃費情報受付ステップで受け付けた燃費情報を前記記憶装置に記憶させるステップとを行うことを特徴とするナビゲーション装置の経路探索方法。
【請求項９】
ナビゲーション装置であって、
地図上の道路を構成するリンクデータと、前記ナビゲーション装置が搭載される移動体の移動速度に応じた燃費を含む燃費情報とを記憶する記憶装置と、
前記リンクデータと前記燃費情報とを用いて、出発地から目的地までの燃料消費量が最少の経路を探索する経路探索手段とを有する
ことを特徴とするナビゲーション装置。
【請求項１０】
ナビゲーション装置であって、
地図上の道路を構成するリンクデータを記憶する記憶装置と、
前記ナビゲーション装置が搭載される移動体の燃費を検出する燃費検出センサと、
前記燃費検出センサにより過去に収集した情報から移動速度に応じた燃費を含む燃費情報を作成する手段と、
前記リンクデータと前記燃費情報とを用いて、出発地から目的地までの燃料消費量が最少の経路を探索する経路探索手段とを有する
ことを特徴とするナビゲーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置に関し、特に車載用ナビゲーション装置の経路探索処理の技術に関する。
【背景技術】
【０００２】
特許文献１には、出発地から目的地まで経路探索した後、移動距離と車両の燃費（燃料消費率）から移動距離全体のガソリン費を求める車載用ナビゲーション装置が記載されている。
【０００３】
【特許文献１】特開２００１−１７４２７７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、特許文献１の技術では、車速によって燃費が異なる実情を考慮していない。これでは、経路全体の正確なガソリン費用を求めることはできない。したがって、ガソリン費用が安い経路を正確に探索することはできない。
【０００５】
本発明は上記事情に鑑みてなされたものであり、本発明の目的は、実情に即した燃料費用を考慮し、費用の安い経路探索を行うことにある。
【課題を解決するための手段】
【０００６】
上記課題を解決すべく本発明のナビゲーション装置の経路探索方法は、移動体の移動速度に応じた燃費（燃料消費率）を用いて、燃料消費量が最少となる経路を探索する。そして、燃料単価を用いて、費用が最少の経路を探索する。本発明のナビゲーション装置の経路探索方法は、例えば、以下のように構成される。
【０００７】
ナビゲーション装置の経路探索方法であって、前記ナビゲーション装置は、地図上の道路を構成するリンクデータと、前記ナビゲーション装置が搭載される移動体の移動速度に応じた燃費を含む燃費情報とを記憶する記憶装置を有している。そして、前記ナビゲーション装置は、前記リンクデータと前記燃費情報とを用いて、出発地から目的地までの燃料消費量が最少の経路を探索する経路探索ステップを行う。
【０００８】
また、前記ナビゲーション装置は、前記ナビゲーション装置が搭載される移動体の燃費を検出する燃費検出センサとを有している。そして、前記ナビゲーション装置は、前記燃費検出センサにより過去に収集した情報から移動速度に応じた燃費を含む燃費情報を作成するステップと、前記リンクデータと前記燃費情報とを用いて、出発地から目的地までの燃料消費量が最少の経路を探索する経路探索ステップとを行う。
【０００９】
また、前記記憶装置は、さらに燃料単価を記憶していてもよい。そして、前記経路探索ステップは、前記リンクデータと前記燃費情報と前記燃料単価と用いて、出発地から目的地までの燃料費用が最少の経路を探索するようにしてもよい。
【００１０】
また、前記記憶装置は、さらに、有料道路の料金情報を含む有料道路情報記憶していてもよい。そして、前記経路探索ステップは、前記リンクデータと前記燃費情報と前記燃料単価と前記有料道路情報とを用いて、出発地から目的地までの費用が最少の経路を探索するようにしてもよい。
【発明の効果】
【００１１】
本発明によれば、燃料消費量の少ない経路を探索することができる。また、費用の安い経路を探索することができる。
【発明を実施するための最良の形態】
【００１２】
以下に、本発明の一実施形態について、図面を参照して説明する。
【００１３】
図１は、本発明の一実施形態を適用した車載用ナビゲーション装置１０００の概略構成図である。図示するように、本実施形態の車載用ナビゲーション装置１０００は、演算処理部１と、ディスプレイ２と、データ記憶装置３と、音声入出力装置４と、入力装置５と、車輪速センサ６と、地磁気センサ７と、ジャイロセンサ８と、ＧＰＳ(Global Positioning System)受信装置９とを有する。
【００１４】
演算処理部１は、様々な処理を行う中心的ユニットである。例えば各種センサ６〜８やＧＰＳ受信装置９から出力される情報を基にして現在地を検出し、得られた現在地情報に基づいて、表示に必要な地図データをデータ記憶装置３から読み出す。また、読み出した地図データをグラフィックス展開し、そこに現在地を示すマークを重ねてディスプレイ２へ表示する。また、交通情報配信センタ２０００から受信した現況交通データ及びデータ記憶装置３に記憶されている地図データを用いて、ユーザから指示された目的地と現在地（出発地）とを結ぶ最適な経路（推奨経路）を探索し、音声入出力装置４やディスプレイ２を用いてユーザを誘導する。
【００１５】
ディスプレイ２は、演算処理部１で生成されたグラフィックス情報を表示するユニットで、ＣＲＴや液晶ディスプレイなどで構成される。また、演算処理部１とディスプレイ２との間の信号Ｓ１は、ＲＧＢ信号やＮＴＳＣ（National Television System Committee）信号で接続するのが一般的である。
【００１６】
データ記憶装置３は、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭやＨＤＤやＩＣカードといった記憶媒体で構成されている。この記憶媒体には、地図データ、有料道路に関する情報、車種データ、燃費データ等が記憶されている。
【００１７】
図２は、データ記憶装置３に記憶されている地図データの構成例を示す図である。図示するように、メッシュ領域毎に地図データ３１０が記憶されている。地図データ３１０は、メッシュ領域の識別コード（メッシュＩＤ）３１１、および、そのメッシュ領域に含まれる道路を構成する各リンクのリンクデータ３１２を有する。リンクデータ３１２は、リンクの識別コード（リンクＩＤ）３１２１、リンクを構成する２つのノード（開始ノード、終了ノード）の座標情報３１２２、リンクを含む道路の種別情報３１２３、リンクの長さを示すリンク長情報３１２４、リンクの旅行時間情報３１２５、２つのノードにそれぞれ接続するリンクのリンクＩＤ（接続リンＩＤ）３１２６などを有する。なお、ここでは、リンクを構成する２つのノードについて開始ノードと終了ノードとを区別することで、同じ道路の上り方向と下り方向とを、それぞれ別のリンクとして管理するようにしている。また、地図データ３１０には、対応するメッシュ領域に含まれている道路以外の地図構成物の情報（名称、種別、座標情報など）も含まれている。
【００１８】
データ記憶装置３には、さらに、有料道路の料金を算出するために用いられる情報が記憶されている。この情報は、料金所ノードデータ３２０と、料金データ３４０とを含む。
【００１９】
料金所ノードデータ３２０は、図３に示すように、料金所が置かれているノードの識別コード（料金所ノードID）３２１ごとに、有料道路の入口（IN）か出口（OUT）かの識別情報３２３とを含む。すなわち、その料金所ノードがIN（入口）側料金所ノードかOUT（出口）側料金所ノードかも分かるようになっている。
【００２０】
料金データ３４０は、有料道路の料金に関する情報を含んでいる。図４に示すように、IN側料金所ノードID（ＩＮ／ＯＵＴ識別情報３２３がＩＮ）３４１とOUT側料金所ノードID（ＩＮ／ＯＵＴ識別情報３２３がＯＵＴ）３４２との組み合わせごとに、料金情報３４３、３４５を含んでいる。
【００２１】
ところで、有料道路の料金は、単純に走行距離に比例するとは限らない。また、有料道路の入口（IN）と出口（OUT）が同じでも、通行経路によって料金が異なる場合もある。したがって、有料道路の料金は、走行経路ごとに定められているのが一般的である。走行経路は、有料道路の入口・出口と、有料道路上のいずれの経由地を経由してきたかで特定される。そこで、本実施形態では、経由地から経路を特定し、料金を算出することとしている。
【００２２】
すなわち、料金データ３４０には、図４に示すように、経由地３４３ごとの料金３４５が含まれている。また、１つの経由地が特定されれば、１つの経路が特定されるとは限らない。複数の経由地によって１つの経路が特定される場合もある。そこで、かかる場合は、複数の経由地の経由地ノードID３４３により経路を特定し料金を求めるようになっている。
【００２３】
図５は、データ記憶装置３に記憶されている車種データ３５０の構成例を示す図である。図示するように、車種データ３５０には、車両の製造会社名３５２ごとに車種（型式）３５３が含まれている。
【００２４】
図６は、データ記憶装置３に記憶されている燃費データ３６０の構成例を示す図である。図示するように、燃費データ３６０には、車種（型式）３６２ごとに、車速（ｋｍ／ｈ）３６３と燃費（ｋｍ／Ｌ）３６４との組み合わせが含まれている。
【００２５】
図１に戻って説明を続ける。音声入出力装置４は、演算処理部１で生成したユーザへのメッセージを音声信号に変換し出力すると共に、ユーザが発した声を認識し演算処理部１にその内容を転送する処理を行う。
【００２６】
入力装置５は、ユーザからの指示を受け付けるユニットで、スクロールキー、縮尺変更キーなどのハードスイッチ、ジョイスティック、ディスプレイ上に貼られたタッチパネルなどで構成される。
【００２７】
センサ６〜８およびＧＰＳ受信装置９は、車載用ナビゲーション装置で現在地（自車位置）を検出するために使用するものである。車輪速センサ６は、車輪の円周と計測される車輪の回転数の積から距離を測定し、さらに対となる車輪の回転数の差から移動体が曲がった角度を計測する。地磁気センサ７は、地球が保持している磁場を検知し、移動体が向いている方角を検出する。ジャイロ８は、光ファイバジャイロや振動ジャイロ等で構成され、移動体が回転した角度を検出するものである。ＧＰＳ受信装置９は、ＧＰＳ衛星からの信号を受信し移動体とＧＰＳ衛星間の距離と距離の変化率を３個以上の衛星に対して測定することで移動体の現在地、進行速度および進行方位を測定する。
【００２８】
図７は、演算処理部１のハードウェア構成例を示す図である。
【００２９】
図示するように、演算処理部１は、各デバイス間をバス３２で接続した構成としてある。演算処理部１は、数値演算及び各デバイスを制御するといった様々な処理を実行するＣＰＵ(Central Processing Unit)２１と、データ記憶装置３から読み出した地図データや演算データなどを格納するＲＡＭ(Random Access Memory)２２と、プログラムやデータを格納するＲＯＭ(Read Only Memory)２３と、メモリ間およびメモリと各デバイスとの間のデータ転送を実行するＤＭＡ（Direct Memory Access）２４と、グラフィックス描画を実行し且つ表示制御を行う描画コントローラ２５と、グラフィックスイメージデータを蓄えるＶＲＡＭ(Video Random Access Memory)２６と、イメージデータをＲＧＢ信号に変換するカラーパレット２７と、アナログ信号をデジタル信号に変換するＡ/Ｄ変換器２８と、シリアル信号をバスに同期したパラレル信号に変換するＳＣＩ(Serial Communication Interface)２９と、パラレル信号をバスに同期させてバス上にのせるＰＩＯ(Parallel Input/Output)３０と、パルス信号を積分するカウンタ３１と、を有する。
【００３０】
図８は、演算処理部１の機能構成を示す図である。
【００３１】
図示するように、演算処理部１は、ユーザ操作解析部４１と、経路探索部４２と、経路データ記憶部４３と、経路誘導部４４と、地図表示処理部４５と、現在位置演算部４６と、マップマッチ処理部４７と、データ読込部４８と、軌跡記憶部４９と、メニュー表示処理部５０と、グラフィックス処理部５１と、燃料情報記憶部５５とを有する。
【００３２】
現在位置演算部４６は、車輪速センサ６で計測される距離パルスデータＳ５およびジャイロ８で計測される角加速度データＳ７を各々積分した結果得られる距離データおよび角度データを用い、そのデータを時間軸で積分していくことにより、初期位置（Ｘ，Ｙ）から自車走行後の位置である現在地（Ｘ′，Ｙ′）を定期的に演算し、マップマッチ処理部４７に出力する処理を行う。ここで、自車の回転した角度と進む方位との関係を一致させるため、地磁気センサ７から得られる方位データＳ６と、ジャイロ８から得られる角加速度データＳ７を積分した角度データとを参照して、自車が進行している方向の絶対方位を推定する。なお、車輪速センサ６のデータおよびジャイロ８のデータを各々積分してゆくと、誤差が蓄積するため、ある時間周期でＧＰＳ受信装置９から得られた位置データＳ８をもとに蓄積した誤差をキャンセルするという処理を施して、現在地の情報をマップマッチ処理部４７に出力する。
【００３３】
マップマッチ処理部４７は、データ読込部４８によって読み込まれた現在地周辺の地図データと、後述する軌跡記憶部４９に記憶されている走行軌跡とを互いに照らし合わせ、形状の相関が最も高い道路（リンク）上に、現在位置演算部４６より定期的に出力される現在地を合わせ込むというマップマッチ処理を行う。現在位置演算部４６で得られる現在地の情報にはセンサ誤差が含まれているため、さらに位置精度を高めることを目的に、マップマッチ処理を行う。これにより、現在地は、多くの場合、走行道路と一致するようになる。
【００３４】
軌跡記憶部４９は、マップマッチ処理部４７でマップマッチ処理が施された現在地の情報を、軌跡データとして自車が所定距離走行する度に記憶する。なお、この軌跡データは、これまで走行してきた道路につき、対応する地図上の道路に軌跡マークを描画するために用いられる。
【００３５】
ユーザ操作解析部４１は、入力装置５に入力されたユーザからの要求を受け、その要求内容を解析して、その要求内容に対応する処理が実行されるように演算処理部１の各部を制御する。例えば、ユーザが推奨経路の探索を要求したときは、目的地を設定するため、地図をディスプレイ２に表示する処理を地図表示部４５に要求し、さらに、現在地（出発地）から目的地までの経路を演算する処理を経路探索部４２に要求する。
【００３６】
経路探索部４２は、ダイクストラ法等を用いて、指定された２地点（現在地、目的地）間を結ぶ経路のコスト（例えば、燃料費用）が最少となる経路を探索する。その結果得られた推奨経路を経路データ記憶部４３に蓄える。
【００３７】
経路誘導部４４は、経路データ記憶部４３に蓄えられた経路で経路誘導を行う。例えば、経路の情報と、マップマッチ処理部４７から出力された現在地の情報とを比較し、交差点等を通過する前に直進すべきか、右左折すべきかを音声出入力装置４を用いて音声でユーザに知らせる。
【００３８】
データ読込部４８は、ディスプレイ２への表示が要求される領域や、経路探索のために要求される領域（出発地および目的地を含む領域）にある地図データを、データ記憶装置３から読み込み準備するように動作する。
【００３９】
地図表示処理部４５は、ディスプレイ２への表示が要求される領域にある地図データをデータ記憶装置３から受け取り、グラフィック処理部５１が、指定された縮尺、描画方式で、道路、その他の地図構成物や、現在地、目的地、誘導経路のための矢印といったマークを描画するように地図描画コマンドを生成する。
【００４０】
メニュー表示処理部５０は、ユーザ操作解析部４１から出力される命令を受け、グラフィック処理部５１が、様々な種類のメニューやグラフなどを描画するようにメニュー描画コマンドを生成する。
【００４１】
グラフィックス処理部５１は、地図表示処理部４５およびメニュー表示処理部５０で生成されたコマンドを受け、ディスプレイ２に表示する画像データをＶＲＡＭ２６にイメージ展開する。
【００４２】
燃料情報記憶部５５は、燃料単価等の燃料に関する情報を記憶する
［動作の説明］  図９は、上記のように構成される車載用ナビゲーション装置１０００の動作の流れを示すフロー図である。
【００４３】
このフローは、経路探索部４２が、ユーザからの経路探索要求を受け付けることにより開始される。そして、車種を設定し（Ｓ１０１）、燃料単価を設定し（Ｓ１０２）、出発地と目的地を設定し（Ｓ１０４）、経路探索のモードを設定し（Ｓ１０５）、出発地から目的地までのコストが最少となる経路をダイクストラ法により探索し（Ｓ１０６）、探索した経路をディスプレイ２に表示し（Ｓ１０８）、探索した経路用いて経路誘導を行う（Ｓ１０９）。なお、車種設定処理（Ｓ１０１）、燃料単価設定処理（Ｓ１０２）が既に行われている場合は、これらの処理は省略できる。
【００４４】
以下に、車種設定処理（Ｓ１０１）、燃料単価設定処理（Ｓ１０２）、および経路探索処理（Ｓ１０６）処理について詳しく説明する。
【００４５】
まず、車種設定処理（Ｓ１０１）について説明する。この処理は、ユーザ操作解析部４１により行われる。ユーザ操作解析部４１は、車載用ナビゲーション装置１０００が搭載されている車両の車種（型式）を設定する（Ｓ１０１）。具体的には、ユーザ操作解析部４１は、図１０に示すように、車種設定画面４４０を、メニュー表示処理部５０を介してディスプレイ２に表示する。画面４４０には、製造会社名４５２、車種（型式）４６２が列挙されている。列挙された製造会社名４５２、車種（型式）４６２は、ボタン４５４Ａ，４５４Ｂ，４６４Ａ，４６４Ｂによりスクロールできるようになっており、ユーザが容易に車種を入力できるようになっている。なお、車種（型式）４６２の表示は、製造会社４５２に応じて変化する。すなわち、ユーザ操作解析部４１は、車種データ３２０を参照し、選択されている製造会社４５２に対応した車種（型式）４６２が表示されるようにする。
【００４６】
入力装置５を介してＯＫボタン４７０が押されると、ユーザ操作解析部４１は、そのとき選択されている車種(型式)４６２を、車載用ナビゲーション装置１０００が搭載されている車両の車種（型式）として設定する。
【００４７】
次に、燃料単価設定処理（Ｓ１０２）について説明する。燃料単価の設定は、ユーザ操作解析部４１により行われる。具体的には、ユーザ操作解析部４１は、図１０に示すように、料金単価設定画面４１０を、メニュー表示処理部５１を介してディスプレイ２に表示する。画面上４１０には、燃料単価４１２、燃料単価を増加・減少させるボタン４１４Ａ、４１４Ｂ、確定ボタン４３０が表示されている。ユーザは、入力装置５を介して、カーソル操作により、ボタン４１４Ａ、４１４Ｂを押すことにより、燃料単価を増減させ設定する。ＯＫボタン４３０が押されると、ユーザ操作解析部４１は、そのときに選択されている燃料単価の値４１２を、燃料情報記憶部５５に登録する。
【００４８】
次に、探索モード設定処理（Ｓ１０５）について説明する。
【００４９】
本実施形態では、経路探索モードとして、出発地から目的地までの旅行時間が最短の経路を探索するモード、旅行距離が最短の経路を探索するモード、旅行費用が最安の経路を探索するモード等がある。それぞれのモードは、さらに、有料道路を含めて探索するモード、有料道路を含めないで探索するモードに設定できるようになっている。このような経路探索モード設定処理（Ｓ１０５）では、ユーザ操作解析部４１は、図１１に示すように、ディスプレイ２に、探索モード設定画面２１０をメニュー表示処理部５０を介して表示する。画面２１０には、それぞれのモードを選択肢２１２〜２１８が表示され、ユーザが容易に探索モードを選択できるようになっている。ユーザ操作解析部４１は、ユーザにより入力装置５を介して選択された内容で探索モードを設定する。
【００５０】
次に、経路探索処理Ｓ１０６について説明する。
【００５１】
上記の通り、本実施形態では、経路探索モードとして、出発地から目的地までの旅行時間が最短の経路を探索するモード、旅行距離が最短の経路を探索するモード、旅行費用が最安の経路を探索するモード等がある。以下では、Ｓ１０５で、旅行費用が最安の経路を探索するモードに設定された場合について説明する。
【００５２】
まず、Ｓ１０５で、探索モードとして、有料道路を含めないで経路探索するように設定された場合について説明する。
【００５３】
経路探索部４２は、リンクごとにコストを設定し、出発地から目的地までの総コストが最少となる経路をダイクストラ法等により探索する。
【００５４】
リンクのコストの算出について説明する。図１２は、コスト算出処理の流れを示す図である。経路探索部４２は、この処理を経路探索の過程において対象となっているリンクの全てについて行う。
【００５５】
まず、経路探索部４２は、リンクデータ３１２のリンク長情報３１２４、旅行時間情報３１２５を参照して、リンク長を旅行時間で割ることで、リンク移動速度を求める（Ｓ１０６１）。
【００５６】
次に、経路探索部４２は、Ｓ１０１で設定された車種（型式）と、Ｓ１０６１で求めた移動速度から、燃費データ３５０を参照して、燃費３５４を特定する（Ｓ１０６２）。
【００５７】
次に、経路探索部４２は、対象リンクのコストを、次の数式１により求める（Ｓ１０６４）。
コスト＝（リンク長／燃費）×燃料単価  …数式１
経路探索部４２は、このようにして求めたリンクコストを用いて、出発地から目的地までのコストが最少となる経路を探索する。そして探索した経路を推奨経路として経路データ記憶部４３に記憶する。
【００５８】
次に、Ｓ１０５で探索モードとして、旅行費用が最安の経路を探索し、かつ有料道路を含めて探索するように設定された場合について説明する。
【００５９】
図１３は、有料道路を含めて経路探索をする処理の流れを示すフロー図である。
【００６０】
まず、経路探索部４２は、出発地付近のＩＮ側料金所ノードの探索を行う（Ｓ１０７１）。
【００６１】
具体的には、経路探索部４２は、上述した図１２で示したような方法により、燃料料金をコストとして、ダイクストラ法等により、出発地からのコストが少ない順に複数のＩＮ側料金ノードを探索する。そして、経路探索部４２は、探索したＩＮ側料金所ノードについて、図１４（Ａ）に示すように、そのノードＩＤ４３１１と、出発地・ＩＮ側料金所ノード間の経路構成リンクのリンクデータ４３１２と、出発地・ＩＮ側料金所ノード間の燃料料金４３１３とを、経路データ記憶部４３のＩＮ側料金所ノード候補テーブル４３１に登録する。出発地までのコストの少ない順に、予め定めた数（例えば１０個）のＩＮ側料金所ノードを探索すると、経路探索部４２は、ＩＮ側料金所ノード探索処理を終了する。なお、地図上の各ノードがＩＮ側料金所ノードであるか否かは、料金所ノードデータ３２０を参照して判断される。
【００６２】
ＩＮ側料金所ノードの探索（Ｓ１０７１）を終了すると、経路探索部４２は、次に、目的地付近のＯＵＴ側料金所ノードの探索処理を行う（Ｓ１０７２）。ここでの処理は、上記した出発地付近のＩＮ側料金所ノード探索処理とほぼ同じである。
【００６３】
ただし、実際の旅行では、ＯＵＴ側料金所ノードから目的地に向かって旅行することになるが、ここでのＯＵＴ側料金所ノード探索処理においては、処理の簡便化のため、目的地を開始点としてＯＵＴ側料金所ノードを探索する。
【００６４】
すなわち、燃料料金をコストとして、ダイクストラ法等により、目的地からのコストが少ない順に複数のＯＵＴ側料金ノードを探索する。そして、経路探索部４２は、探索したＯＵＴ側料金所ノードについて、図１４（Ｂ）に示すように、そのノードＩＤ４３２１と、目的地・ＩＮ側料金所ノードまでの経路構成リンクのリンクデータ４３２２と、燃料料金４３２３とを、経路データ記憶部４３のＯＵＴ側料金所ノード候補テーブル４３２に登録する。目的地からのコストが少ない順に、予め定めた数（例えば１０個）のＩＮ側料金所ノードが探索されると、経路探索部４２は、ＯＵＴ側料金所ノード探索処理を終了する。なお、地図上の各ノードがＯＵＴ側料金所ノードであるか否かは、料金所ノードデータ３２０を参照して判断される。
【００６５】
次に、経路探索部４２は、ＩＮ側料金所ノード候補テーブル４３１に登録されたＩＮ側料金所ノードＩＤ４３１１と、ＯＵＴ側料金所ノード候補テーブル４３２に登録されたＯＵＴ側料金所ノードＩＤ４３２１とを総当りさせ、ペアを作成する（Ｓ１０７３）。例えば、ＩＮ側料金所ノードＩＤ４３１１がｍ個、ＯＵＴ側料金所ノードＩＤ４３２１がｎ個登録されている場合、総当りさせると、（ｍ×ｎ）個のペアが作成されることになる。ペアを作成すると、経路探索部４２は、作成したＩＮ側料金所ノードＩＤ４３３１とＯＵＴ側料金所ノードＩＤ４３３２とのペアを、図１５に示すように、経路データ記憶部４３のペア候補テーブル４３３に登録する。
【００６６】
次に、経路探索部４２は、料金データ３４０を参照して、作成したペアのＩＮ側料金所ノード・ＯＵＴ側料金所ノード間の有料道路の料金を求める。このとき、ＩＮ側料金所ノード・ＯＵＴ側料金所ノード間に複数の経路があり、それぞれ料金が異なる場合は、最安の経路の料金をそのペアの料金とする。そして、求めたＩＮ・ＯＵＴ料金所間の有料道路料金と燃料料金の合計４３３３を、図１５に示すように、ペアを対応させてペア候補テーブル４３３に登録する。
【００６７】
次に、経路探索部４２は、ペア候補テーブル４３３に登録された各ペアの有料道路を採用した場合の、出発地・目的地間の総コストを求める（Ｓ１０７６）。
【００６８】
コストは、ＩＮ側料金所ノード候補テーブル４３１、ＯＵＴ側料金所ノード候補テーブル４３２、ペア候補テーブル４３３を参照して、以下の数式２を用いて求める。
【００６９】
コスト＝（出発地・ＩＮ側料金所ノード間の燃料料金４３１２）＋（ＯＵＴ側料金所ノード・目的地間の燃料料金４３２３）＋（ＩＮ側料金所ノード・ＯＵＴ側料金所ノード間の有料道路料金と燃料料金の合計４３２３）…数式２
ペア候補テーブル４３３に登録されている全てのペアについて、そのペアの有料道路を採用した場合の経路の出発地・目的地間の総コストを求めると（Ｓ１０７７）、経路探索部４２は、コストが最少となる経路を特定する（Ｓ１０７８）。そして、特定した経路を推奨経路として、経路データ記憶部４３に記憶する。
【００７０】
なお、ＩＮ側料金所ノード・ＯＵＴ側料金所ノード間に複数の経路がある場合は、料金が最安となる経路を、ＩＮ側料金所ノード・ＯＵＴ側料金所ノード間の経路として採用する。
【００７１】
なお、上記有料道路を含めて経路探索する処理では、有料道路を含まない経路探索（出発地若しくは目的地から有料道路までの経路探索）と、有料道路を含む経路探索（料金所間の経路探索）の２レベルの経路探索を組み合わせて出発地・目的地間の経路探索をしている。本実施形態は、これに限らず、２レベル以上のレベルの経路探索を組み合わせて経路探索を行うこともできる。例えば、出発地若しくは目的地から主要幹線道路までの経路探索、幹線道路から高速道路までの経路探索、高速道路上での入口・出口間の経路探索の３つのレベルでの経路探索を組み合わせて経路探索を行うこともできる。この場合でも、経路探索の処理を、出発地若しくは目的地から最上位のレベルの有料道路上までの経路探索と、最上位の有料道路上の経路探索に大きく分けることで、上記実施形態が適用できる。
【００７２】
また、有料道路の中でも、特定の有料道路のみ、最上位のレベルの経路探索に用いるようにしてもよい。例えば、高速道路でない有料道路や、他の有料道路と連結していない有料道路、橋の区間だけが有料等の主要でない有料道路については、上位のレベルに含ませないで、下位のレベルに含ませて経路探索を行うようにしてもよい。
【００７３】
以上、有料道路を含めた場合と含めない場合における、料金が安い経路の探索処理について説明した。
【００７４】
図１６に、探索した経路のディスプレイ２への表示例を示す。画面上８１０には、地図上８２０に、出発地８２４から目的地８２５までの推奨経路８２６が表示されている。推奨経路８２６は、インターチャンジ８２８、８２９間において高速道路８２７を経由している。そして、経路全体での燃料料金８３１、高速道路料金８３２、それらの合計８３０が表示されている。なお、旅行時間８３４、燃料単価８３５を表示してもよい。旅行時間８３４は、経路を構成する各リンクの旅行時間をリンクデータ３１２から求め、経路全体で合計することにより求まる。また、表示画面には、燃料消費量を表示するようにしてもよい。
【００７５】
以上、本発明が適用された一実施形態について説明した。
【００７６】
上記実施形態によれば、燃料費用（燃料消費量）を考慮した経路探索ができる。
【００７７】
また、燃料費用の安い経路を探索することができる。
【００７８】
また、燃料費用と有料道路の料金をともに考慮し、全体の料金の安い経路を探索することができる。
【００７９】
また、車種に応じた燃費を考慮して、費用の安い経路探索を行うことができる。
【００８０】
また、車速により燃費が異なることを考慮して燃料消費量を考慮した経路探索ができる。
【００８１】
尚、本発明は上記の実施形態に限定されるものではなく、その要旨の範囲内で様々な変形が可能である。
【００８２】
例えば、上記では、有料道路を含めて経路探索する場合について説明したが、有料道路を含めないで経路探索するようにしてもよい。
【００８３】
また、上記では、データ記憶装置３に、車種（型式）ごとに燃費データを記憶していたが、車両の排気量、燃料の種類（例えば、軽油、レギュラーガソリン、ハイオク燃料等）に応じて、燃費を記憶しておくようにすることもできる。こうすれば、排気量、燃料の種類に応じて燃費が変化する実情を考慮した、燃料消費量の少ない経路の探索ができるようになる。
【００８４】
また、燃費データをユーザが入力できるようにしてもよい。この場合、本実施形態は、以下のように構成することができる。
【００８５】
まず、ユーザ操作解析部４１は、ユーザからの燃費データ入力要求に応じて、メニュー表示処理部５１を介して、図１７に示すような燃費入力画面５００をディスプレイ２に表示する。画面５００には、車速ごとの燃費の入力を容易にするための表示がされている。例えば、車速５１２の値は、ボタン５１４Ａ、５１４Ｂにより増加・減少させることができる。また、燃費５２２の値は、ボタン５２４Ａ、５２４Ｂにより増加・減少させることができる。ユーザは、まず、車速の範囲を５１２に設定し、その車速の範囲での燃費を５２２に入力することになる。ＯＫボタン５３０が押されると、ユーザ操作解析部４１は、そのとき設定されている車速の燃費を燃料情報記憶部５５に登録する。また、ユーザ操作解析部４１は、登録済の燃費データ５５０を、ユーザに分かりやすいように、画面５００に表示する。
【００８６】
また、車載用ナビゲーション装置１０００が搭載された車両の過去の燃費から、燃費情報を作成し、経路探索で使用するようにしてもよい。この場合、本実施形態は以下のように構成することができる。
【００８７】
車載用ナビゲーション装置１０００は、図１で示した構成の他に、不図示の燃費センサを備えている。
【００８８】
燃費センサは、走行距離と消費燃料量から燃費を求め、そのときの車速に対応させて燃費データを蓄積する。そして、燃費センサは、蓄積した燃費データを車速の範囲ごとに平均化し、車速と燃費との関係を求める。図１８は、燃費センサにより求められた車速と燃費との関係６００を表す図である。燃費センサは、定期的に、求めた車速と燃費との関係６００を、燃費データとして、燃料情報記憶部５５に登録する。
【００８９】
そして、経路探索部４２は、経路探索においてリンクのコストを算出する際、燃費情報記憶部５５に記憶された燃費データを用いる。具体的な処理は、図１０で示したコスト算出処理と同様である。
【００９０】
このようにすれば、外部から燃費データが入手できない場合でも、過去の燃費データを基に、燃料消費量の少ない経路の探索を行うことができる。
【００９１】
なお、本発明を車載用ナビゲーション装置に適用した例について説明したが、本発明は車載用以外のナビゲーション装置にも適用することができる。
【図面の簡単な説明】
【００９２】
【図１】図１は、車載用ナビゲーション装置１０００の概略構成図である。
【図２】図２は、データ記憶装置３に記憶されている地図データの構成例を示す図である。
【図３】図３は、データ記憶装置３に記憶されている料金所データの構成例を示す図である。
【図４】図４は、データ記憶装置３に記憶されている料金データの構成例を示す図である。
【図５】図５は、データ記憶装置３に記憶されている車種データの構成例を示す図である。
【図６】図６は、データ記憶装置３に記憶されている燃費データの構成例を示す図である。
【図７】図７は、演算処理部１のハードウェア構成を示す図である。
【図８】図８は、演算処理部１の機能構成を示す図である。
【図９】図９は、車載用ナビゲーション装置１０００の動作の概略を示すフロー図である。
【図１０】図１０は、車種設定画面、燃料単価設定画面の表示画面の一例を示す図である。
【図１１】図１１は、探索モード設定画面の表示例を示す図である
【図１２】図１２は、経路探索処理（有料道路を含まない）におけるリンクコスト算出処理の概略を示すフロー図である。
【図１３】図１３は、経路探索処理（有料道路を含む）の概略を示すフロー図である。
【図１４】図１４は、経路データ記憶部４３に記憶されているＩＮ側料金所ノード候補テーブル（Ａ）、ＯＵＴ側料金所ノード候補テーブル（Ｂ）の構成例を示す図である。
【図１５】図１５は、経路データ記憶部４３に記憶されているＩＮ側料金所ノードとＯＵＴ側料金所ノードのペア候補テーブルの構成例を示す図である。
【図１６】図１６は、推奨経路の表示例を示す図である。
【図１７】図１７は、燃費設定画面の表示画面の一例を示す図である。
【図１８】図１８は、燃費センサから求めた車速と燃費との関係の例を示す図である。
【符号の説明】
【００９３】
１・・・演算処理部、２・・・ディスプレイ、３・・・データ記憶装置、４・・・音声出入力装置、５・・・入力装置、６・・・車輪速センサ、７・・・地磁気センサ、８・・・ジャイロ、９・・・ＧＰＳ受信機、１１・・・車内ＬＡＮ装置、１２・・・ＦＭ多重放送受信装置、１３・・・ビーコン受信装置、２１・・・ＣＰＵ、２２・・・ＲＡＭ、２３・・・ＲＯＭ、２４・・・ＤＭＡ、２５・・・描画コントローラ、２６・・・ＶＲＡＭ、２７・・・カラーパレット、２８・・・Ａ/Ｄ変換器、２９・・・ＳＣＩ、３０・・・ＰＩＯ、３１・・・カウンタ、４１・・・ユーザ操作解析部、４２・・・経路探索部、４３・・・経路データ記憶部、４４・・・経路誘導部、４５・・・地図表示処理部、４６・・・現在位置演算部、４７・・・マップマッチ処理部、４８・・・データ読込部、４９・・・軌跡記憶部、５０・・・メニュー表示処理部、５１・・・グラフィックス処理部、５５・・・燃料情報記
【図１】
2005172582.tif 000003
【図２】
2005172582.tif 000004
【図３】
2005172582.tif 000005
【図４】
2005172582.tif 000006
【図５】
2005172582.tif 000007
【図６】
2005172582.tif 000008
【図７】
2005172582.tif 000009
【図８】
2005172582.tif 000010
【図９】
2005172582.tif 000011
【図１０】
2005172582.tif 000012
【図１１】
2005172582.tif 000013
【図１２】
2005172582.tif 000014
【図１３】
2005172582.tif 000015
【図１４】
2005172582.tif 000016
【図１５】
2005172582.tif 000017
【図１６】
2005172582.tif 000018
【図１７】
2005172582.tif 000019
【図１８】
2005172582.tif 000020