JP4409965B2 - ナビゲーション装置と、その経路探索方法 - Google Patents

Description

本発明は、ナビゲーション装置に関し、特に車載用ナビゲーション装置の経路探索の技術に関する。

特許文献１には、有料道路を優先して出発地から目的地までの経路を探索する車載用ナビゲーション装置が記載されている。特許文献１に記載の技術は、総コストが最少となる推奨経路を探索する場合において、有料道路のコストに係数を乗じて他の道路に比べ低めに設定し、有料道路が採用され易いようにしたものである。

特開２００２−１３９３７号公報

しかし、特許文献１の技術では、利用する価値があるとは言ない有料道路を採用した経路が探索される場合があった。

例えば、時間的に遠回りにならなければ、有料道路を迂回する経路の方が、料金が安いので、ユーザの要求に沿った経路といえる。しかし、特許文献１の技術では、このような経路が探索できす、時間の短縮に見合わない料金がかかる有料道路を含む経路が探索される場合があった。

本発明は上記事情に鑑みてなされたものであり、本発明の目的は、有料道路を優先して経路探索する場合において、よりユーザの要求に沿った探索を行うことにある。

上記課題を解決すべく本発明のナビゲーション装置の経路探索方法は、有料道路優先で探索した場合、探索した経路に含まれる有料道路を回避する経路を新たに探索する。そして、もとの経路と回避経路の中から、予め定めた条件を満たす経路を推奨経路として定める。

例えば、ナビゲーション装置は、出発地から目的地までの有料道路を含む第１の経路を探索する有料経路探索ステップと、前記有料経路探索ステップで探索された第１の経路に含まれる有料道路のうち少なくとも１部（区間）を回避する第２の経路を探索する回避経路探索ステップと、前記有料経路探索ステップにより探索された第１の経路と前記回避経路探索ステップにより探索された第２の経路の中から、予め定めた条件を満たす経路を推奨経路として特定する推奨経路特定ステップとを行う。

前記ナビゲーション装置は、旅行時間に関する閾値条件および旅行料金に関する閾値条件のうち少なくとも１つを設定する閾値設定ステップを行うようにしてもよい。また、前記ナビゲーション装置は、地図上の道路を構成する各リンクのリンクデータと、有料道路に関する情報とを記憶する記憶装置を有し、前記リンクデータを用いて、有料道路に属するリンクのコストを他のリンクに比べ低く設定するようにしてもよい。そして、前記有料経路探索ステップにより探索された第１の経路と前記回避経路探索ステップにより探索された第２の経路の中から、前記閾値設定ステップで設定された閾値条件を満たす経路を推奨経路として特定するようにしてもよい。

本発明によれば、有料道路を含めた経路探索において、利用する価値のない有料道路が採用されないようにすることができる。

以下に、本発明の一実施形態について、図面を参照して説明する。

図１は、本発明の一実施形態を適用した車載用ナビゲーション装置１０００の概略構成図である。図示するように、本実施形態の車載用ナビゲーション装置１０００は、演算処理部１と、ディスプレイ２と、地図データ記憶装置３と、音声入出力装置４と、入力装置５と、車輪速センサ６と、地磁気センサ７と、ジャイロセンサ８と、ＧＰＳ(Global Positioning System)受信装置９とを有する。

演算処理部１は、様々な処理を行う中心的ユニットである。例えば各種センサ６〜８やＧＰＳ受信装置９から出力される情報を基にして現在地を検出し、得られた現在地情報に基づいて、表示に必要な地図データを地図データ記憶装置３から読み出す。また、読み出した地図データをグラフィックス展開し、そこに現在地を示すマークを重ねてディスプレイ２へ表示する。また、不図示のビーコン、ＦＭ多重放送局、交通情報配信センタ等から受信した現況交通データ及び地図データ記憶装置３に記憶されている地図データを用いて、ユーザから指示された目的地と現在地（出発地）とを結ぶ最適な経路（推奨経路）を探索し、音声入出力装置４やディスプレイ２を用いてユーザを誘導する。

ディスプレイ２は、演算処理部１で生成されたグラフィックス情報を表示するユニットで、ＣＲＴや液晶ディスプレイなどで構成される。また、演算処理部１とディスプレイ２との間の信号Ｓ１は、ＲＧＢ信号やＮＴＳＣ（National Television System Committee）信号で接続するのが一般的である。

地図データ記憶装置３は、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭやＨＤＤやＩＣカードといった記憶媒体で構成されている。この記憶媒体には、地図データ、有料料金データ等が記憶されている。

図２は、地図データ記憶装置３に記憶されている地図データの構成例を示す図である。図示するように、メッシュ領域毎に地図データ３１０が記憶されている。地図データ３１０は、メッシュ領域の識別コード（メッシュＩＤ）３１１、および、そのメッシュ領域に含まれる道路を構成する各リンクのリンクデータ３１２を有する。リンクデータ３１２は、リンクの識別コード（リンクＩＤ）３１２１、リンクを構成する２つのノード（開始ノード、終了ノード）の座標情報３１２２、リンクを含む道路の種別情報３１２３、リンクの長さを示すリンク長情報３１２４、リンクの旅行時間情報３１２５、２つのノードにそれぞれ接続するリンクのリンクＩＤ（接続リンクＩＤ）３１２６などを有する。なお、ここでは、リンクを構成する２つのノードについて開始ノードと終了ノードとを区別することで、同じ道路の上り方向と下り方向とを、それぞれ別のリンクとして管理するようにしている。また、地図データ３１０には、対応するメッシュ領域に含まれている道路以外の地図構成物の情報（名称、種別、座標情報など）も含まれている。

地図データ記憶装置３には、さらに、有料道路の料金を算出するために用いられる料金データ３４０が記憶されている。

料金データ３４０は、図３に示すように、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)３０と、パルス信号を積分するカウンタ３１と、を有する。

図５は、演算処理部１の機能構成を示す図である。

図示するように、演算処理部１は、ユーザ操作解析部４１と、経路探索部４２と、経路データ記憶部４３と、経路誘導部４４と、地図表示処理部４５と、現在位置演算部４６と、マップマッチ処理部４７と、データ読込部４８と、軌跡記憶部４９と、メニュー表示処理部５０と、グラフィックス処理部５１とを有する。

現在位置演算部４６は、車輪速センサ６で計測される距離パルスデータＳ５およびジャイロ８で計測される角加速度データＳ７を各々積分した結果得られる距離データおよび角度データを用い、そのデータを時間軸で積分していくことにより、初期位置（Ｘ，Ｙ）から自車走行後の位置である現在地（Ｘ′，Ｙ′）を定期的に演算し、マップマッチ処理部４７に出力する処理を行う。ここで、自車の回転した角度と進む方位との関係を一致させるため、地磁気センサ７から得られる方位データＳ６と、ジャイロ８から得られる角加速度データＳ７を積分した角度データとを参照して、自車が進行している方向の絶対方位を推定する。なお、車輪速センサ６のデータおよびジャイロ８のデータを各々積分してゆくと、誤差が蓄積するため、ある時間周期でＧＰＳ受信装置９から得られた位置データＳ８をもとに蓄積した誤差をキャンセルするという処理を施して、現在地の情報をマップマッチ処理部４７に出力する。

マップマッチ処理部４７は、データ読込部４８によって読み込まれた現在地周辺の地図データと、後述する軌跡記憶部４９に記憶されている走行軌跡とを互いに照らし合わせ、形状の相関が最も高い道路（リンク）上に、現在位置演算部４６より定期的に出力される現在地を合わせ込むというマップマッチ処理を行う。現在位置演算部４６で得られる現在地の情報にはセンサ誤差が含まれているため、さらに位置精度を高めることを目的に、マップマッチ処理を行う。これにより、現在地は、多くの場合、走行道路と一致するようになる。

軌跡記憶部４９は、マップマッチ処理部４７でマップマッチ処理が施された現在地の情報を、軌跡データとして自車が所定距離走行する度に記憶する。なお、この軌跡データは、これまで走行してきた道路につき、対応する地図上の道路に軌跡マークを描画するために用いられる。

ユーザ操作解析部４１は、入力装置５に入力されたユーザからの要求を受け、その要求内容を解析して、その要求内容に対応する処理が実行されるように演算処理部１の各部を制御する。例えば、ユーザが推奨経路の探索を要求したときは、目的地を設定するため、地図をディスプレイ２に表示する処理を地図表示部４５に要求し、さらに、現在地（出発地）から目的地までの経路を演算する処理を経路探索部４２に要求する。

経路探索部４２は、ダイクストラ法等を用いて、指定された２地点（現在地、目的地）間を結ぶ経路のコスト（例えば、旅行時間）が最少となる経路を探索する。その結果得られた推奨経路を経路データ記憶部４３に蓄える。

経路誘導部４４は、経路データ記憶部４３に蓄えられた経路で経路誘導を行う。例えば、経路の情報と、マップマッチ処理部４７から出力された現在地の情報とを比較し、交差点等を通過する前に直進すべきか、右左折すべきかを音声出入力装置４を用いて音声でユーザに知らせる。

データ読込部４８は、ディスプレイ２への表示が要求される領域や、経路探索のために要求される領域（出発地および目的地を含む領域）にある地図データを、地図データ記憶装置３から読み込み準備するように動作する。

地図表示処理部４５は、ディスプレイ２への表示が要求される領域にある地図データを地図データ記憶装置３から受け取り、グラフィック処理部５１が、指定された縮尺、描画方式で、道路、その他の地図構成物や、現在地、目的地、誘導経路のための矢印といったマークを描画するように地図描画コマンドを生成する。

メニュー表示処理部５０は、ユーザ操作解析部４１から出力される命令を受け、グラフィック処理部５１が、様々な種類のメニューやグラフなどを描画するようにメニュー描画コマンドを生成する。

グラフィックス処理部５１は、地図表示処理部４５およびメニュー表示処理部５０で生成されたコマンドを受け、ディスプレイ２に表示する画像データをＶＲＡＭ２６にイメージ展開する。

上記のように構成される車載用ナビゲーション装置１０００は、有料道路を含めて経路探索する場合、有料道路のコストを他の道路に比べ低めに設定（あるいは、他の道路のコストを有料道路に比べ高めに設定）して、出発地（現在位置）から目的地までの経路探索を行う。探索された経路に有料道路が含まれる場合は、その有料道路を迂回する経路を探索する。そして、迂回する経路と元の有料道路を含む経路とを、旅行時間、有料料金の観点から比較し推奨経路を特定する。

［動作の説明］ 次に、上記のように構成される車載用ナビゲーション装置１０００の動作を説明する。図６は、上記のように構成される車載用ナビゲーション装置１０００の経路探索処理の流れの概略を示すフロー図である。

このフローは、経路探索部４２が、ユーザからの経路探索要求を受け付けることにより開始される。

まず、経路探索部４２は、出発地・目的地の設定を行う（Ｓ１０１）。具体的には、経路探索部４２は、入力装置２を介して、ユーザから出発地、目的地の入力を受け付ける。入力は、文字入力により行うようにしてもよいし、ディスプレイ２に、地図を表示して、地図上で特定するようにしてもよい。

次に、経路探索部４２は、探索条件の設定を行う（Ｓ１０２）。このとき、経路探索部４２は、メニュー表示処理部５０を介して、ディスプレイ２に、図７に示すように、探索条件設定画面２１０を表示する。

本実施形態では、有料道路を優先して経路探索を行うモードと、有料道路を特に優先することなく経路探索を行うモード等がある。そこで、探索条件設定画面２１０には、これらのモードを選択する選択肢２１２、２１４が表示されている。そして、ユーザが、この選択肢２１２、２１４を入力装置５を介して選択することができるようになっている。

経路探索部４２は、ユーザにより選択された選択肢を、探索条件に設定する。

有料道路を優先することなく経路探索を行うように設定された場合（Ｓ１０２でＮｏ）、経路探索部４２は、有料道路を優先することなく経路探索を行う（Ｓ１２０）。具体的には、経路探索部４２は、リンクデータ３１２のリンク旅行時間３１２５と料金データ３４０を参照して、旅行時間３１２５と有料料金３４５をコストとして、出発地から目的地までのコストが最少となる経路をダイクストラ法等により求める。そして、求めた経路を候補経路として、その所要時間をＴ１とする。また、候補経路が有料道路を含む場合は、有料料金データ３４０を参照して有料料金の総額を算出し、算出した総額をＰ１とする。

そして、経路探索部４２は、候補経路を推奨経路とし、所要時間Ｔ１、所要料金Ｐ１とともに、経路データ記憶部４３に記憶する（Ｓ１３０）。

一方、有料道路を優先して経路探索を行うように設定された場合（Ｓ１０２でＮｏ）、経路探索部４２は、有料道路を通りやすくして経路探索を行う（Ｓ１０４）。具体的には、経路探索部４２は、リンクデータ３１２のリンク旅行時間３１２５と料金データ３４０を参照して、旅行時間３１２５と料金３４５をコストとして、出発地から目的地までのコストが最少となる経路をダイクストラ法等により求める。このとき、有料道路に属すリンクのコストについてはその他の道路に属すリンクのコストより低め設定する。例えば、旅行時間３１２５と料金３４５からなるコストに、コスト係数（１以下、例えば０．５）を乗じて、リンクコストとする。こうすることで、推奨経路に有料道路が含まれやすくなる。

経路探索部４２は、求めた経路を候補経路として、その所要時間をＴ１とする。また、候補経路が有料道路を含む場合は、有料料金データ３４０を参照して有料料金の総額を算出し、算出した総額をＰ１とする。

次に、経路探索部４２は、Ｓ１０４で求めた候補経路が有料道路を含むか否か判定する（Ｓ１０６）。候補経路が有料道路を含まない場合（Ｓ１０６でＮｏ）、経路探索部４２は、Ｓ１３０に処理を移行する。そして、経路探索部４２は、候補経路を推奨経路として経路データ記憶部４３に記憶する（Ｓ１３０）
一方、候補経路が有料道路を含む場合（Ｓ１０６でＹｅｓ）、経路探索部４２は、候補経路の見直し処理（Ｓ１０８〜Ｓ１１６）を行う。ここでは、経路探索部４２は、有料道路の回避経路を求め、候補経路に含まれる有料道路それぞれについて推奨経路に含ませるべきか否かの見直しを行う。

まず、回避経路の探索（Ｓ１０８）について説明する。

図８は、回避経路の探索処理（Ｓ１０８）の流れを示すフロー図である。

まず、経路探索部４２は、候補経路に含まれる有料道路区間（同種の有料道路に属する有料道路は１区間とする）であって、まだ見直しがされていない有料道路区間を抽出する（Ｓ１０８１）。ここで、見直しがされてない有料道路区間とは、図６のＳ１０８〜Ｓ１１６の見直し処理がなされていない有料道路区間をいう。

次に、経路探索部４２は、Ｓ１０８１で抽出した有料道路区間の中から、目的地に最も近い方にある有料道路区間を選択し、回避すべき有料道路区間に設定する（Ｓ１０８２）。Ｓ１０８の処理を初めて行う場合、見直しされた有料道路区間はない。したがって、この場合、経路探索部４２は、目的地に一番近い方にある有料道路区間が回避すべき有料道路区間となる。

続いて、経路探索部４２は、候補経路上に、回避すべき有料道路区間の前に有料道路区間があるか否か判定する（Ｓ１０８３）。ある場合（Ｓ１０８３でＹｅｓ）、経路探索部４２は、候補経路上の、回避すべき有料道路区間の一つ前の有料道路区間の出口を地点Ｘと設定する。

地点Ｘは、実際の有料道路区間の出口に限らず、実情に応じて、出口周辺の地点を適宜予め定めておいてもよい。例えば、有料道路区間の出口側料金所を出て、一般道に入る合流地点であってもよいし、合流地点付近において渋滞が考えられる場合は、渋滞が緩和される地点であってもよい
一方、回避すべき有料道路区間の前に有料道路区間がない場合（Ｓ１０８３でＮｏ）、出発地を地点Ｘと設定する（Ｓ１０８５）。

次に、経路探索部４２は、候補経路上に、回避すべき有料道路区間の次に有料道路区間があるか否か判定する（Ｓ１０８６）。ある場合（Ｓ１０８６でＹｅｓ）、経路探索部４２は、候補経路上の、回避すべき有料道路区間の次の有料道路区間の入口を地点Ｙと設定する（Ｓ１０８７）。

地点Ｙは、実際の有料道路区間の入口に限らず、実情に応じて、入口周辺の地点を適宜予め定めておいてもよい。例えば、有料道路の入口側料金所に通じる道路への合流地点であってもよいし、合流地点付近において渋滞が考えられる場合は、合流地点をより手前の渋滞していない地点であってもよい。

一方、回避すべき有料道路区間の次に有料道路区間がない場合（Ｓ１０８６でＮｏ）、目的地を地点Ｙと設定する（Ｓ１０８８）。

地点Ｘと地点Ｙが設定されると、経路探索部４２は、地点Ｘから地点Ｙまでの経路であって、かつ回避すべき有料道路区間を含まない経路を探索する（Ｓ１０８９）。具体的には、経路探索部４２は、地点Ｘから地点Ｙまでを、その有料道路区間を含めないで、旅行時間をリンクコストとして、コストが最少となる経路をダイクストラ法等により探索する。

次に、経路探索部４２は、候補経路のうち、地点Ｘから地点Ｙまでを、Ｓ１０８９で探索した地点Ｘから地点Ｙまでの経路に入れ替える。そして得られた経路を回避経路とし、処理を終了する（Ｓ１０９０）。

図６に戻って説明する。

経路探索部４２は、求めた回避経路の総所要時間をＴ２、有料料金の総額をＰ２とする。有料料金の総額Ｐ２は、有料料金データ３４０を参照して、回避経路に含まれる有料道路の料金の総額を算出することで求めることができる。

次に、経路探索部４２は、所要時間、有料料金について閾値判定処理（Ｓ１１０、Ｓ１１２）を行う。

まず、経路探索部４２は、Ｔ２−Ｔ１が予め定めた時間閾値（例えば、１時間）より小さいか否かを判定する（Ｓ１１０）。Ｔ２−Ｔ１が時間閾値より小さい場合（Ｓ１１０でＹｅｓ）、経路探索部４２は、回避経路を候補経路とする。また、Ｔ１にＴ２の値を入れ、Ｐ１にＰ２の値を入れる（Ｓ１１４）。

一方、Ｔ２−Ｔ１が時間閾値以上の場合（Ｓ１１０でＮｏ）、経路探索部４２は、Ｐ１−Ｐ２が予め定めた料金閾値（例えば、１０００円）以上か否かを判定する（Ｓ１１２）。Ｐ１−Ｐ２が料金閾値以上の場合（Ｓ１１２でＹｅｓ）、経路探索部４２は、回避経路を候補経路とする。また、Ｔ１にＴ２の値を入れ、Ｐ１にＰ２の値を入れる（Ｓ１１４）。

一方、Ｐ１−Ｐ２が料金閾値より小さい場合（Ｓ１１２でＮｏ）、経路探索部４２は、そのまま処理をＳ１１６に移行する。

次に、経路探索部４２は、候補経路に見直しされていない有料道路が含まれているか否か判定する（Ｓ１１６）。見直しされていない有料道路が含まれている場合（Ｓ１１６でＹｅｓ）、経路探索部４２は、Ｓ１０８に処理を移行し、再び回避経路を探索する。

一方、見直しされていない有料道路区間が含まれていない場合（Ｓ１１６でＮｏ）、経路探索部４２は、Ｓ１３０に処理を移行する。

そして、経路探索部４２は、候補経路を推奨経路に設定し、経路データ記憶部４３に記憶する（Ｓ１３０）。

なお、Ｓ１０８９で、回避すべき有料道路区間を回避した地点Ｘ−Ｙ間の経路を探索した場合、別の新たな有料道路が含まれる経路が探索される場合がある。この場合でも図６、図８のフローを適用し、候補経路と回避経路の比較を行うことで、最終的に推奨経路を求めることができる。

以上、図６、図８を用いて経路探索処理について説明した。

次に、上記経路探索処理について、図９、図１０を用いて、具体的なモデルを示して説明する。

図９は、図６のＳ１０４において、有料道路区間Ａ，Ｂ及びＣを含む候補経路（ａ）が探索された場合について、説明するための図である。

図示するように、経路（ａ）のモデルは、出発地、目的地間に有料道路区間Ａ，Ｂ及びＣ（図中、点線）を含んでいる。有料道路区間の入口、出口は、例えば、有料道路区間Ａの入口をＡｉｎ、出口をＡｏｕｔという具合に表している。

この候補経路（ａ）について、見直し処理（Ｓ１０８〜S１１６）を行う場合について説明する。

まず、経路探索部４２は、経路（ａ）から見直し処理がなされていない有料道路を抽出する（Ｓ１０８１）。経路（ａ）では、有料道路区間Ａ、Ｂ及びＣが抽出される。

次に、経路探索部４２は、Ｓ１０８１で抽出した有料道路区間の中から、目的地に一番近い方にある有料道路区間を選択し、回避すべき有料道路区間に設定する（Ｓ１０８２）。経路（ａ）では、有料道路区間Ｃが選択される。

続いて、経路探索部４２は、候補経路上に、有料道路区間Ｃの前に有料道路区間があるか否か判定する（Ｓ１０８３）。経路（ａ）では、有料道路区間Ｃの前に有料道路Ｂがあるので（Ｓ１０８３でＹｅｓ）、経路探索部４２は、有料道路区間Ｂの出口Ｂｏｕｔを地点Ｘと設定する。

次に、経路探索部４２は、候補経路上に、有料道路区間Ｃの次に有料道路区間があるか否か判定する（Ｓ１０８４）。経路（ａ）では、有料道路区間Ｃの次に有料道路区間はないので（Ｓ１０８４でＮｏ）、目的地を地点Ｙと設定する（Ｓ１０８８）。

地点Ｘと地点Ｙが設定されると、経路探索部４２は、地点Ｘ（Ｂｏｕｔ）から地点Ｙ（目的地）までの経路を探索する（Ｓ１０８９）。経路（ａ）については、経路（ｂ）に示すＸ１が探索される。

次に、経路探索部４２は、候補経路（ａ）のうち、地点Ｘ（Ｂｏｕｔ）から地点Ｙ（目的地）までを、探索した経路Ｘ１に入れ替える。そして得られた経路（ｂ）を回避経路とし、回避経路探索処理を処理を終了する（Ｓ１０９０）。

Ｓ１０９０の処理が終了すると、経路探索部４２は、候補経路（ａ）と回避経路（ｂ）について、図６に示す閾値判定処理Ｓ１１０、Ｓ１１２を行う。

閾値判定処理Ｓ１１０、Ｓ１１２のいずれかがＹｅｓの場合、経路探索部４２は、回避経路（ｂ）を候補経路と設定する（Ｓ１１４）。そして、経路探索部４２は、まだ見直しされていない有料道路があるか判定する（Ｓ１１６）。候補経路（ｂ）において、有料道路区間ＡおよびＢは、まだ見直しされていないので（Ｓ１１６でＹｅｓ）、経路探索部４２は、Ｓ１０８に処理を移行し、再び回避経路探索処理（Ｓ１０８）を行う。そして、今度は、回避経路（ｃ）が探索されることになる。そして、候補経路（ｂ）とともに閾値判定処理Ｓ１１０、Ｓ１１２が行われることになる。

一方、候補経路（ａ）と回避経路（ｂ）とでの閾値判定処理Ｓ１１０、Ｓ１１２のいずれもがＮｏの場合、経路探索部４２は、候補経路は経路（ａ）のままにして、Ｓ１０８の処理に移行する。そして、今度は、新たな回避経路ｄが探索されることになる。そして、候補経路（ａ）と回避経路（ｄ）とでの、閾値判定処理Ｓ１１０、Ｓ１１２を行うことになる。

以上のような処理を繰り返すと、閾値判定の結果により、図９で示すような経路（ｂ）〜（ｇ）が回避経路として探索されうる。

図１０に、閾値判定処理により、最終的に候補経路が求まるまでの流れを示す。図示するように、例えば、候補経路（ａ）と回避経路（ｂ）とでの閾値判定で（Ｓ３０１）、経路（ａ）が候補経路にとどまった場合、候補経路（ａ）は、回避経路（ｄ）とで閾値判定がなされる（Ｓ３０２）。Ｓ３０２で経路（ｄ）が新たな候補経路となった場合、今度は、候補経路（ｄ）と回避経路（ｆ）とで閾値判定がなされる（Ｓ３０５）。Ｓ３０５で回避経路（ｆ）が新たな候補経路になった場合、経路（ｆ）が推奨経路として特定されることになる。

同様にして、閾値判定処理の結果によって、経路（ａ）〜（ｄ）のいずれかが推奨経路として特定される（Ｓ３０１〜Ｓ３０６）。

以上、経路探索処理について説明した。

推奨経路が探索されると、経路探索部４２は、推奨経路を、図１１に示すように、メニュー表示処理部５０を介してディスプイ２に表示する。

画面８１０上には、地図８２０上に、出発地８２４から目的地８２５までの推奨経路８２９が表示されている。推奨経路８２９は、インターチャンジ８２８aと８２８ｂの間、８２８ｃと８２８ｄの間を、それぞれ高速道路（有料道路）８２６および８２０を経由している。

また、画面上８１０には有料料金８３１および所要旅行時間８３２も表示されている。

なお、ビーコンやFM多重放送局、交通情報配信センタから受信した渋滞情報８３５を表示するようにしてもよい。

以上、本発明が適用された一実施形態について説明した。

本実施形態によれば、よりユーザの要求に沿った経路を探索できる。

また、有料道路のコストについて画一的に他の道路に比べ低めに設定するようにして経路探索する場合でも、有料道路を迂回する経路と比較することで、よりユーザの要求に沿った経路を探索することができる。すなわち、利用価値のない有料道路や旅行時間時間の短縮に見合わない料金の有料道路が採用されない経路探索ができる。

また、有料道路を用いる経路と有料道路を回避する経路について、旅行時間、や旅行料金の面から比較するので、旅行時間時間の短縮に見合わない料金の有料道路を除外した推奨経路を容易に探索することができる。

また、有料道路を用いる経路と有料道路を回避する経路について比較する場合、閾値を設定して比較する。したがって、比較処理が容易である。

本発明は上記の実施形態に限定されるものではなく、その要旨の範囲内で様々な変形が可能である。

例えば、図６、図８で示した処理のステップは、本願発明の要旨の範囲内で順番を変更することができる。

例えば、上記実施形態では閾値判定処理において、時間閾値を判定した後、料金閾値を判定してるが、この順番は逆であってもよい。

また、図８のフローにおいて、地点Ｘを設定してから地点Ｙを設定しているが、この順番を逆にしてもよい。

また、図８に示すＳ１０８２では、目的地に最も近い有料道路を選択するようにしているが、出発地から最も近い有料道路を選択するようにしてもよい。

また、時間閾値、旅行時間閾値のほかに閾値を設けて、閾値判定処理を行うようにしてもよい。例えば、旅行距離閾値を設けて、候補経路と回避経路の旅行距離の差が予め定めた旅行距離閾値を越える場合は、候補経路をそのまま採用し、超えない場合は、回避経路を新たな候補経路と設定するようのしてもよい。

また、時間閾値、料金閾値等の閾値を変更できるようにすることもできる。

例えば、ユーザ操作解析部４１が、ディスプレイ２に、メニュー表示処理部５０を介して、図１２に示すような閾値設定画面を表示する。

閾値設定画面５００には、時間閾値５１２、料金閾値５２２の入力を受け付ける表示がなされている。すなわち、ユーザが、閾値の増減ボタン５１４Ａ，５１４Ｂ、５２４Ａ、５２４Ｂを押すことで、容易に閾値を設定できるようになっている。また、閾値をどのように定めればよいかの判断を助けるメッセージ５３２、５３４が表示されている。ユーザ操作解析部４１は、ユーザにより入力装置５を介して入力された値を、それぞれの閾値として設定する。

このようにすれば、ユーザの好みに応じて、閾値が設定できるようになる。そして、節約したい時間、節約したい料金の度合いを考慮したリーズナブルな経路が探索できる。

また、本実施形態は、以下のような変形例も可能である。

上記実施形態では、回避経路を一つずつ求めて、求めた回避経路と候補経路を閾値判定処理により比較している。これに限らず、予め、全ての回避経路を求めておき、その後で、最初に求めた候補経路と閾値判定処理を行うようにしてもよい。

図１３は、かかる場合の推奨経路を求める処理の流れを示す図である。図示するように、上記実施形態と同様に、経路探索部４２は、候補経路が有料道路を含むか否か判定する（Ｓ２０６）。含む場合（Ｓ２０６で、Ｙｅｓ）、経路探索部４２は、全ての回避経路を求める（Ｓ２０８）。回避経路を求める処理は、上述した、図８に示す処理と同様に行うことができる。候補経路がｎ個の有料道路を含む場合、（ｎの２乗−２）本の回避経路が探索されることになる。そして、全ての回避経路が求まると、経路探索部４２は、回避経路ごとに、候補経路との間で閾値判定処理を行う。閾値判定処理Ｓ２１０、Ｓ２１２のいずれかでＹｅｓの場合、経路探索部４２は、その回避経路を推奨経路として経路データ記憶部４３に記憶する（Ｓ２１４）。全ての回避経路について、閾値判定処理を行うと（Ｓ２１５）、経路探索部４２は、経路データ記憶部４３に、すでに推奨経路が登録されているか判定する（Ｓ２１６）。すでに、回避経路が推奨経路として、登録されている場合は、そのまま処理を終了する。一方、推奨経路が登録されていない場合、経路探索部４２は、候補経路を推奨経路として、経路データ記憶部４３に記憶し、処理を終了する。

このような経路探索処理によれば、閾値の設定の仕方によって、推奨経路が複数求まる場合がある。かかる場合は、さらに新たな閾値を設けて、この閾値を用いて閾値判定処理により、一つの推奨経路が求まるようにしてもよい。また、旅行距離が最も短い経路を選択して、一つの推奨経路に絞り込むようにしてもよい。また、複数の推奨経路をディスプレイに表示して、ユーザに選択させるようにしてもよい。

さらに、本実施形態は、以下のような変形が可能である。

上記実施形態では、経路探索で用いるコストとして、リンクデータ３１２の旅行時間３１２２を用いている。しかし、これに限らず、リンクの旅行時間を含む現況の交通情報が入手された場合、この旅行時間をコストとして用いて経路探索するようにしてもよい。

例えば、車載用ナビゲーション装置１０００は、さらに、ビーコン、FM多重放送局、交通情報配信センタ等から交通情報を受信する受信装置を有し、受信した交通情報の中に、現況のリンク旅行時間が含まれている場合は、その旅行時間を経路探索に利用する。受信する交通情報としては、例えば、VICS情報等が挙げられる。このようにすれば、車載用ナビゲーション装置１０００は、現況の交通事情を考慮した推奨経路の探索を行うことができる。

なお、本発明を車載用ナビゲーション装置に適用した例について説明したが、本発明は車載用以外のナビゲーション装置にも適用することができる。

図１は、車載用ナビゲーション装置１０００の概略構成図である。 図２は、地図データ記憶装置３に記憶されている地図データの構成例を示す図である。 図３は、地図データ記憶装置３に記憶されている料金データの構成例を示す図である。 図４は、演算処理部１のハードウェア構成を示す図である。 図５は、演算処理部１の機能構成を示す図である。 図６は、車載用ナビゲーション装置１０００の経路探索処理の概略を示すフロー図である。 図７は、探索条件設定画面の表示例を示す図である。 図８は、図６のＳ１０８の回避経路探索処理の流れのを示すフロー図である。 図９は、回避経路探索処理を具体的に説明するための候補経路および回避経路のモデルを示す図である 図１０は、図９で示す経路モデルにおける候補経路が特定するまでの流れを具体的に説明するためのフロー図である。 図１１は、推奨経路の表示例を示す図である。 図１２は、時間閾値、旅行閾値の変更を受け付ける表示画面の一例である。 図１３は、図６で示した経路探索処理の変形例の概略を示すフロー図である。

符号の説明

１・・・演算処理部、２・・・ディスプレイ、３・・・データ記憶装置、４・・・音声出入力装置、５・・・入力装置、６・・・車輪速センサ、７・・・地磁気センサ、８・・・ジャイロ、９・・・ＧＰＳ受信機、１１・・・車内ＬＡＮ装置、２１・・・ＣＰＵ、２２・・・ＲＡＭ、２３・・・ＲＯＭ、２４・・・ＤＭＡ、２５・・・描画コントローラ、２６・・・ＶＲＡＭ、２７・・・カラーパレット、２８・・・Ａ/Ｄ変換器、２９・・・ＳＣＩ、３０・・・ＰＩＯ、３１・・・カウンタ、４１・・・ユーザ操作解析部、４２・・・経路探索部、４３…経路データ記憶部、４４・・・経路誘導部、４５・・・地図表示処理部、４６・・・現在位置演算部、４７・・・マップマッチ処理部、４８・・・データ読込部、４９・・・軌跡記憶部、５０・・・メニュー表示処理部、５１・・・グラフィックス処理部

Claims (11)

1. ナビゲーション装置であって、
   地図上の道路を構成する各リンクのリンクデータと、有料道路区間に関する情報とを記憶する記憶装置と、
   旅行時間に関する閾値条件と旅行料金に関する閾値条件のうち少なくとも１つを設定する閾値設定手段と、
   前記リンクデータを用いて、有料道路区間に属するリンクのコストを他のリンクに比べ低く設定し、出発地から目的地までのコストが最少となる第１の経路を探索する有料経路探索手段と、
   前記有料経路探索手段により探索された第１の経路が有料道路区間を含む場合、当該第１の経路に含まれる有料道路区間のうち少なくとも１つを回避する第２の経路を探索する回避経路探索手段と、
   前記有料経路探索手段により探索された第１の経路と前記回避経路探索手段により探索された第２の経路の中から、前記閾値設定手段で設定された閾値条件を満たす経路を推奨経路として特定する推奨経路特定手段と
   を有することを特徴とするナビゲーション装置。
2. 請求項１に記載のナビゲーション装置であって、
   前記回避経路探索手段は、前記第１の経路に含まれる有料道路区間のうち少なくとも１つを回避する第２の経路が複数ある場合、
   前記第１の経路と複数の第２の経路の中から、前記閾値設定手段で設定された閾値条件を満たす経路を推奨経路として特定する
   ことを特徴とするナビゲーション装置。
3. 請求項１又は２に記載のナビゲーション装置であって、
   前記旅行時間に関する閾値又は前記旅行料金に関する閾値は、旅行時間の差又は旅行料金の差に関する閾値である
   ことを特徴とするナビゲーション装置。
4. 請求項１〜３のいずれか一項に記載のナビゲーション装置であって、
   前記回避経路探索手段により探索される第２の経路は、
   前記第１の経路上の回避すべき有料道路区間の前後に有料道路区間がある場合は、
   前記第１の経路中の出発地から前記回避すべき有料道路区間の一つ前の有料道路区間の出口までの経路と、
   前記回避すべき有料道路区間の一つ前の有料道路区間の出口から前記回避すべき有料道路区間の次の有料道路区間の入口までの経路であって前記回避すべき有料道路区間を回避した経路と、
   前記第１の経路中の前記回避すべき有料道路区間の次の有料道路区間の入口から目的地までの経路とからなり、
   前記第１の経路上の前記回避すべき有料道路区間の前に有料道路区間があるが、後にはない場合は、
   前記第１の経路中の出発地から前記回避すべき有料道路区間の一つ前の有料道路区間の出口までの経路と、
   回避すべき有料道路区間の一つ前の有料道路区間の出口から目的地までの経路であって前記回避すべき有料道路区間を回避した経路とからなり、
   前記第１の経路上の前記回避すべき有料道路区間の前に有料道路区間はないが、後にはある場合は、
   出発地からから前記回避すべき有料道路区間の次の有料道路区間の入口までの経路であって前記回避すべき有料道路区間を回避した経路と、
   前記第１の経路中の前記回避すべき有料道路区間の次の有料道路区間の入口から目的地までの経路とからなる
   ことを特徴とするナビゲーション装置。
5. 請求項１〜４のいずれか一項に記載のナビゲーション装置であって、
   さらに、
   前記閾値条件の入力を受け付ける閾値受付手段を有し、
   前記閾値設定手段は、前記閾値受付手段で受け付けた閾値条件を設定する
   ことを特徴とするナビゲーション装置。
6. 請求項１〜５のいずれか一項に記載のナビゲーション装置であって、
   さらに、
   前記リンクの現況の旅行時間を入手する交通情報入手手段を有し、
   前記経路探索手段は、前記交通情報入手手段で入手した現況のリンクの旅行時間をリンクのコストとして用いて経路探索を行う
   ことを特徴とするナビゲーション装置。
7. ナビゲーション装置の経路探索方法であって、
   前記ナビゲーション装置は、
   地図上の道路を構成する各リンクのリンクデータと、有料道路に関する情報とを記憶する記憶装置を有し、
   旅行時間に関する閾値条件と旅行料金に関する閾値条件のうち少なくとも１つを設定する閾値設定ステップと、
   前記リンクデータを用いて、有料道路に属するリンクのコストを他のリンクに比べ低く設定し、出発地から目的地までのコストが最少となる第１の経路を探索する有料経路探索ステップと、
   前記有料経路探索ステップにより探索された第１の経路が有料道路区間を含む場合、当該第１の経路に含まれる有料道路区間のうち少なくとも１つを回避する第２の経路を探索する回避経路探索ステップと、
   前記有料経路探索ステップにより探索された第１の経路と前記回避経路探索ステップにより探索された第２の経路の中から、前記閾値設定ステップで設定された閾値条件を満たす経路を推奨経路として特定する推奨経路特定ステップと
   を行うことを特徴とするナビゲーション装置の経路探索方法。
8. 請求項７に記載のナビゲーション装置の経路探索方法であって、
   前記回避経路探索ステップは、前記第１の経路に含まれる有料道路区間のうち少なくとも１つを回避する第２の経路が複数ある場合、
   前記第１の経路と複数の第２の経路の中から、前記閾値設定ステップで設定された閾値条件を満たす経路を推奨経路として特定する
   ことを特徴とするナビゲーション装置の経路探索方法。
9. 請求項７又は８に記載のナビゲーション装置の経路探索方法であって、
   前記旅行時間に関する閾値又は前記旅行料金に関する閾値は、旅行時間の差又は旅行料金の差に関する閾値である
   ことを特徴とするナビゲーション装置の経路探索方法。
10. 請求項７〜９のいずれか一項に記載のナビゲーション装置の経路探索方法であって、
    前記回避経路探索ステップにより探索される第２の経路は、
    前記第１の経路上の回避すべき有料道路区間の前後に有料道路区間がある場合は、
    前記第１の経路中の出発地から前記回避すべき有料道路区間の一つ前の有料道路区間の出口までの経路と、
    前記回避すべき有料道路区間の一つ前の有料道路区間の出口から前記回避すべき有料道路区間の次の有料道路区間の入口までの経路であって前記回避すべき有料道路区間を回避した経路と、
    前記第１の経路中の前記回避すべき有料道路区間の次の有料道路区間の入口から目的地までの経路とからなり、
    前記第１の経路上の前記回避すべき有料道路区間の前に有料道路区間があるが、後にはない場合は、
    前記第１の経路中の出発地から前記回避すべき有料道路区間の一つ前の有料道路区間の出口までの経路と、
    回避すべき有料道路区間の一つ前の有料道路区間の出口から目的地までの経路であって前記回避すべき有料道路区間を回避した経路とからなり、
    前記第１の経路上の前記回避すべき有料道路区間の前に有料道路区間はないが、後にはある場合は、
    出発地からから前記回避すべき有料道路区間の次の有料道路区間の入口までの経路であって前記回避すべき有料道路区間を回避した経路と、
    前記第１の経路中の前記回避すべき有料道路区間の次の有料道路区間の入口から目的地までの経路とからなる
    ことを特徴とするナビゲーション装置の経路探索方法。
11. 請求項７〜１０のいずれか一項に記載のナビゲーション装置の経路探索方法であって、
    前記ナビゲーション装置は、さらに、
    前記閾値条件の入力を受け付ける閾値受付ステップを行い、
    前記閾値設定ステップは、前記閾値受付ステップで受け付けた閾値条件を設定する
    ことを特徴とするナビゲーション装置の経路探索方法。

Images