(57)【要約】【課題】具体的な経由地を指定しなくても経路探索をできるようにする。【解決手段】ナビゲーション装置に地図上の道路を構成する各リンクのコストを含むリンクデータを有する地図データを記憶する記憶部３を設けておく。そして、ナビゲーション装置に、目的地、および目的地までの間に経由する経由方面の設定を受け付けさせ、出発地および経由方面を含む領域と、目的地および経由方面を含む領域とを合わせた経由領域を特定させ、記憶装置３に記憶されているリンクデータを取得させ、前記特定した経由領域に属する各リンクのコストを該経由領域に属さない各リンクのコストに比べて減少させた上で、或いは該経由領域以外に属する各リンクのコストを該経由領域に属する各リンクのコストに比べて増加させた上で、出発地から目的地までの経路を算出させる。【選択図】図１
2005098814.tif 000002
【特許請求の範囲】
【請求項１】
地図上の道路を構成する各リンクのリンクデータを記憶する記憶部を有する、ナビゲーション装置における出発地から目的地までの経路探索方法であって、
前記リンクデータには、各リンクのコストが含まれていて、
目的地の設定を受け付けるステップと、
前記目的地までの間に経由する経由方面の設定を受け付けるステップと、
前記出発地および前記経由方面を含む領域と、前記目的地および該経由方面を含む領域とを合わせた経由領域を特定するステップと、
前記記憶部に記憶されている前記リンクデータを取得し、前記特定した経由領域に属する各リンクのコストを該経由領域に属さない各リンクのコストに比べて減少させた上で、或いは該経由領域に属さない各リンクのコストを該経由領域に属する各リンクのコストに比べて増加させた上で、該リンクデータのコストを用いて前記経路を算出するステップと、を実行すること
を特徴とする経路探索方法。
【請求項２】
請求項１に記載の経路探索方法であって、
前記経由領域を特定するステップの前に、前記出発地、前記目的地、および前記経由方面を含む探索領域を特定するステップを行い、
前記特定した探索領域の中から前記経由領域を特定するステップと、
前記特定した探索領域に属する各リンクのリンクデータの中から、前記経路を算出するステップと、を実行すること
を特徴とする経路探索方法。
【請求項３】
請求項１又は２に記載の経路探索方法であって、
前記経由領域とは、前記出発地および前記経由方面に予め対応付けられた経由位置の２点を焦点とする楕円と、前記目的地および該経由位置の２点を焦点とする楕円とを合わせた領域であること
を特徴とする経路探索方法。
【請求項４】
請求項１または２に記載の経路探索方法であって、
前記経由領域とは、前記出発地および前記経由方面に予め対応付けられた経由位置とを結んだ直線から引いた垂線が所定の距離に入る領域と、該目的地と該経由位置とを結んだ直線から引いた垂線が所定の距離に入る領域とを合わせた領域であること
を特徴とする経路探索方法。
【請求項５】
請求項１に記載の経路探索方法であって、
前記経由領域を特定するステップの前に、前記出発地から前記目的地までの第１の直線距離および前記出発地から前記経由方面に予め対応付けられた経由位置までの第２の直線距離を算出し、前記第２の直線距離が前記第１の直線距離に比べて所定の距離より長い場合、前記経由領域を特定するステップを行わないで、前記出発地および前記目的地の２点を含む探索領域を特定し、該特定した探索領域に属する各リンクのコストを用いて、前記出発地から目的地までの経路を算出するステップを実行すること
を特徴とする経路探索方法。
【請求項６】
請求項１から５のいずれか一項に記載の経路探索方法であって、
前記コストは、各リンクの旅行時間、移動距離、および旅行料金の少なくとも１つを含むこと
を特徴とする経路探索方法。
【請求項７】
目的地の設定を受付け、出発地から該受付けた目的地までの経路を探索するナビゲーション装置であって、
地図上の道路を構成する各リンクのコストを含むリンクデータを記憶する記憶手段と、
目的地までの間に経由する経由方面の設定を受付けることができる設定手段と、
前記記憶手段が記憶する前記リンクデータを用いて、前記出発地から前記目的地までの経路であって、該受付けた経由方面を通過する経路を探索する経路探索手段と、を有し、
前記経路探索手段は、
前記出発地および前記経由方面を含む領域と、前記目的地および該経由方面を含む領域とを合わせた経由領域を特定し、
前記記憶部に記憶されている前記リンクデータを用いて、前記特定した経由領域に属する各リンクのコストを該経由領域に属さない各リンクのコストに比べて減少させた上で、或いは該経由領域に属さない各リンクのコストを該経由領域に属する各リンクのコストよりも増加させた上で、前記経路を算出すること
を特徴とするナビゲーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的地までの経路を探索する経路探索技術に関し、特にナビゲーション装置の経路探索技術に関する。
【背景技術】
【０００２】
従来のナビゲーション装置には、ユーザから目的地、および経由地の指定を受付け、出発地（現在位置）から経由地を通過し目的地まで至る経路を探索するものがある（例えば、特許文献１）。この特許文献１のナビゲーション装置によれば、ユーザは、予め通過したい場所（例えばレストランや眺めがいい道路等）を指定しておけば、所望する場所を経由して目的地まで向うことができる。
【０００３】
また、従来のナビゲーション装置には、ユーザから目的地の指定を受け付けた場合に、出発地から目的地に至るまでの経路を探索した上で、さらに探索した経路上の経由地を所定の規則にしたがって算出して表示するものがある（例えば、特許文献２）。
【０００４】
【特許文献１】特開平１１−３０４５０５号公報
【０００５】
【特許文献２】特開平１１−８３５２８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記特許文献１のナビゲーション装置は、ユーザが経由したい経由地を具体的に指定しない限り、ユーザが立ち寄りたい経由地域を通過する経路探索を行うことができないという問題を有している。具体的には、上記特許文献１に記載のナビゲーション装置では、ある方面（エリア）を通過して目的地に向かいたい場合、その方面（エリア）の中からユーザが具体的な経由地を指定しなければ、その方面を経由する経路探索を行うことができない。
【０００７】
特許文献２のナビゲーション装置は、探索した経路上の経由地を所定の規則にしたがって算出することはできるが、ユーザから所望する経由地を受け付けて経路探索をするものではない。そのため、特許文献２のナビゲーション装置は、目的地に向かう間に立ち寄りたい経由地がある場合、目的地の代わりに具体的に経由地を設定する必要がある。すなわち、特許文献２のナビゲーション装置も、特許文献１と同様に、ユーザが経由したい経由地を具体的に指定しない限り、ユーザが立ち寄りたい経由方面（エリア）を通過する経路探索を行うことができない。
【０００８】
また、上記特許文献１、２のナビゲーション装置は、ユーザが経由地を指定した場合、必ずその経由地を通過する経路が探索される。そして、その探索された経路は、所望する方面（エリア）を経由する経路の中で最適なコスト（例えば旅行時間が最小）のものとは限らない。
【０００９】
本発明は上記事情に鑑みてなされたものであり、ナビゲーション装置において、
具体的な経由地を指定しなくても経路探索をできるようにすることにある。
【課題を解決するための手段】
【００１０】
上記課題を解決するため、本発明の一態様の経路探索方法は、ナビゲーション装置に地図上の道路を構成する各リンクのコストを含むリンクデータを記憶する記憶部を設けておく。そして、ナビゲーション装置に、目的地の設定を受け付けるステップと、出発地から前記目的地までの間に経由する経由方面の設定を受け付けるステップと、前記出発地および前記経由方面を含む領域と、前記目的地および該経由方面を含む領域とを合わせた経由領域を特定するステップと、前記記憶部に記憶されている前記リンクデータを取得し、前記特定した経由領域に属する各リンクのコストを該経由領域に属さない各リンクのコストに比べて減少させた上で、或いは該経由領域に属さない各リンクのコストを該経由領域に属する各リンクのコストに比べて増加させた上で、該リンクデータのコストを用いて前記経路を算出するステップと、を行わせる。
【００１１】
このように、本一態様では、ユーザから経由方面（エリア）の設定を受付けることができるようにして、前記出発地および前記経由方面を含む領域と、前記目的地および該経由方面を含む領域とを合わせた経由領域を特定し、前記特定した経由領域に属する各リンクのコストを該経由領域に属さない各リンクのコストに比べて減少させた上で、或いは該経由領域に属さない各リンクのコストを該経由領域に属する各リンクのコストに比べて増加させた上で、出発地から目的地までの経路を算出するようにしている。そのため、本一態様では、出発地から目的地までの経路探索を行う場合、前記経由領域から経路が選出される可能性が高くなる。すなわち、本一態様によれば、ユーザがある方面を経由して目的地まで行きたい場合、具体的な経由地を指定しなくても、ユーザの所望する方面（エリア）を経由した経路探索を行うことができる。
【００１２】
また、上記経由領域を特定するステップの前に、前記出発地から前記目的地までの第１の直線距離および前記出発地から前記経由方面に予め対応付けられた経由位置までの第２の直線距離を算出し、前記第２の直線距離が前記第１の直線距離に比べて所定の距離より長い場合、前記経由領域を特定するステップを行わないで、前記出発地および前記目的地の２点を含む探索領域を特定し、該特定した探索領域に属する各リンクのコストを用いて、前記出発地から目的地までの経路を算出するステップを実行することとしてもよい。
【００１３】
このように構成することにより、ユーザが設定した経由方面が、出発地および目的地の２地点の関係（２地点から算出される経路）から見て離れ過ぎている場合に、その経由方面を通過する経路を探索する処理を除外することができる。すなわち、本一態様によれば、出発地および目的地の２地点から見て著しく逸脱する経由方面が設定されても、その経由方面を通過する経路が探索する処理を行わないため、該出発地および目的地の２地点から見て不自然な経由方面を通過する経路が算出されることを防ぐことができる。また、この場合、経由方面を考慮した経路探索を行わないため、出発地から目的地までの経路を迅速に探索することができる。例えば、本一態様によれば、新潟を出発して大阪に向う経路探索の際に、九州方面を経由方面として設定した場合等に、九州方面を経由する経路が探索されることはない。
【発明の効果】
【００１４】
このように本発明によれば、ナビゲーション装置において、具体的な経由地を指定しなくても経路探索を行うことができる。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施の形態について図面を用いて説明する。
【００１６】
最初に本実施形態が適用された車載用ナビゲーション装置の概略構成について図１を用いて説明する。
【００１７】
図１は、本発明の実施形態が適用された車載用ナビゲーション装置（以下において単に「ナビゲーション装置」という）の概略構成図である。
【００１８】
図示するように、ナビゲーション装置は、演算処理部１と、ディスプレイ２と、地図データ記憶装置３と、音声入出力装置４と、入力装置５と、車輪速センサ６と、地磁気センサ７と、ジャイロ８と、ＧＰＳ（Global Positioning System）受信装置９と、を有する。
【００１９】
演算処理部１は、ナビゲーション装置がユーザに提供する各種情報を処理するための中心的ユニットである。例えば、各種センサ６〜８やＧＰＳ受信装置９から出力される情報を基にして現在位置を検出し、検出した現在位置に基づいて、表示に必要な地図データを地図データ記憶装置３から読み出す。その後、演算処理部１は、読み出した地図データをグラフィックス展開し、そこに現在位置を示すマークを重ねてディスプレイ２に表示したり、出発地（例えば現在位置）とユーザから指示された目的地とを結ぶ最適な経路を探索し、音声入出力装置４やディスプレイ２を用いてユーザを誘導する。また、演算処理部１は、後述するように、ユーザから目的地に加え、目的地に向う途中で経由したい経由方面の設定を受け付けることができるように構成されている。そして、演算処理部１は、ユーザから目的地に向う際の経由したい方面（例えば関東方面）を受け付けた場合、その経由方面を通過する経路を探索できるように構成されている。
【００２０】
ディスプレイ２は、演算処理部１で生成された画像データを表示するユニットで、ＣＲＴや液晶ディスプレイ等により構成される。また、演算処理部１とディスプレイ２との間の信号Ｓ１は、ＲＧＢ信号やＮＴＳＣ（National TV Standards Committee）信号で接続するのが一般的である。
【００２１】
地図データ記憶装置３は、日本列島の全体図から全国各市町村の詳細図まで多段階の縮尺図に対応した地図データを記憶するユニットであり、例えば、ＣＤ−ＲＯＭドライブとＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭドライブとＤＶＤ−ＲＯＭ、またはＨＤＤ等により構成される。
【００２２】
ここで地図データの構成を説明する。図２は、地図データ記憶装置３に記憶されている地図データのデータ構造を模擬的に示す図である。図示するように、地図データ記憶装置３には、地図を複数に分割することで得られるメッシュ領域毎に地図データ３１０が記憶されている。地図データ３１０は、メッシュ領域を識別するためのメッシュＩＤ３１１、および、そのメッシュ領域に含まれる道路を構成する各リンクのリンクデータ３１２を有する。
【００２３】
リンクデータ３１２は、リンクを識別するためのリンクＩＤ３１２１、リンクを構成する２つのノード（開始ノード、終了ノード）の座標情報３１２２、リンクを含む道路の種別情報３１２３、リンクの長さを示すリンク長情報３１２４、リンクの旅行時間（或いは移動時間）情報３１２５、および、２つのノード（開始ノード、終了ノード）にそれぞれ接続するリンクのリンクＩＤ（接続リンクＩＤ）３１２６などを有する。また、地図データ３１０には、対応するメッシュ領域に含まれている道路以外の地図構成物の情報（名称、種別、座標情報など）も含まれている。
【００２４】
図１に戻り、説明を続ける。音声入出力装置４は、演算処理部１で生成したユーザへのメッセージを音声信号に変換して出力すると共に、ユーザが発した声を認識し、デジタルデータに変換して演算処理部１にその内容を転送する。
【００２５】
入力装置５は、ナビゲーション装置の各種機能選択、目的地設定等のユーザからの指示を受け付けるユニットで、スクロールキー、縮尺変更キーなどのハードスイッチ、ジョイステック、ディスプレイ上に貼られたタッチパネルなどで構成される。
【００２６】
センサ６〜８およびＧＰＳ受信装置９は、ナビゲーション装置が現在位置を検出するために使用するものである。車輪速センサ６は、車輪の円周と計測される車輪の回転数から距離を測定し、さらに対となる車輪の回転数から移動体が曲がった角度を計測する。地磁気センサ７は、地球が保持している磁気を検知し、移動体が向かっている方角を検出する。ジャイロ８は、光ファイバジャイロや振動ジャイロで構成され、移動体が回転した角度を検出する。ＧＰＳ受信装置９は、ＧＰＳ衛星からの信号を受信し移動体とＧＳＰ衛星間の距離および距離の変化率を３個以上の衛星に対して測定することで移動体の現在位置、進行方向および進行方位を測定する。
【００２７】
続いて、上述したナビゲーション装置の演算処理部１が有する機能について図３を用いて説明する。図３は、演算処理部１の機能構成を説明するための図である。
【００２８】
図示するように、演算処理部１は、設定部１０と、現在位置検出部１１と、データ読込部１２と、マップマッチ処理部１３と、経路探索部１４と、経路誘導部１５と、地図表示処理部１６と、メニュー表示処理部１７と、グラフィックス処理部１８と、を有する。
【００２９】
設定部１０は、入力装置５および音声入出力装置４に入力されたユーザからの要求を受け付けて、その要求された内容に対応する処理が実行されるように演算処理部１を制御する。例えば、ユーザが推奨経路の探索を要求した場合には、出発地（または現在位置）、目的地、およびユーザが目的地までの間に経由したい方面（以下において「経由方面」という）を設定する設定画面をディスプレイ２に表示させる処理をメニュー表示処理部１７に要求する。また、設定部１０は、出発地、目的地、および経由方面の設定を受付けた場合、設定された方面を経由する、出発地（または現在位置）から目的地までの経路を探索する処理を経路探索部１４に要求する。
【００３０】
現在位置検出部１１は、車輪速センサ６で計測される距離パルスデータＳ５およびジャイロセンサ８で計測される角速度データＳ7を各々積分した結果得られる距離データおよび角度データを用いて、そのデータを時間軸で積分していくことにより、初期値（Ｘ,Ｙ）から自車走行後の位置である現在位置（Ｘ´,Ｙ´）を定期的に演算し、マップマッチ処理部１３に出力する。ここで、自車の回転した角度と進む方向との関係を一致させるため、地磁気センサ７から得られた方位データＳ６と、ジャイロ８から得られ角速度データＳ７を積分した角度データを参照して、自車が進行している方向の絶対方位を推定する。車輪速センサ６のデータＳ５およびジャイロ８のデータＳ７を各々積分していくと、誤差が蓄積するため、ある時間でＧＰＳ受信装置９から得られた位置データＳ８をもとに蓄積した誤差をキャンセルする処理を施し、現在位置のデータをマップマッチ処理部１３に出力する。
【００３１】
データ読込部１２は、ディスプレイ２に表示が要求される領域や、経路探索のために要求される領域（出発地および目的地を含む）にある地図データを、地図データ記憶装置３から読み込む。
【００３２】
マップマッチ処理部１３は、データ読込部１２が読み込んだ現在地周辺の地図データと、現在位置検出部１１が定期的に検出する現時位置を合わせ込むマップマッチ処理を行う。
【００３３】
経路探索部１４は、ダイクストラ法等を用いて、指定された２地点（出発地、目的地）を結ぶ最適なコストで目的地に到達する経路を、地図データ３１０（図２参照）を用いて探索する。経路探索部１４は、上記探索の結果得られた経路を推奨経路として、ディスプレイ２に表示させるために地図表示処理部１６に出力する。また、経路探索部１４は、設定部１０が、目的地に加えて、さらに経由方面の設定を受け付けた場合、その経由方面を通過し、かつコストを考慮した経路を算出するように構成されている。なお、経路探索部１４が行う経路探索処理については、後段で詳細に説明する。
【００３４】
なお、本実施形態は、上述した最適なコストについて具体的に限定するものではない。例えば、最適なコストを判断するデータに、図２に示すリンクデータ３１２が有するリンクの旅行時間情報３１２５を用いるようにする。そして、この場合には、経路を構成する各リンクの旅行時間の総和が最小となる経路を最適なコストの経路とする。また、最適なコストを判断するデータに、リンクデータ３１２が有する「リンク長情報（リンクの距離情報）３１２４」を用いるようにする。そして、この場合には、リンク長の総和が最小となる経路を最適なコストの経路とする。また、例えば、最適なコストを判断するデータに、リンクデータ３１２が有する、道路種別情報３１２３等の旅行費用を用いるようにする。この場合には、経路を構成する各リンクの旅行費用の総和が最小となる経路を最適なコストの経路とする。さらに、コストを判断するデータとして、リンク長情報３１２４、旅行時間情報３１２５、旅行時間等のデータを組合せて判断するようにしてもよい。また、例えば、コストを判断するためのデータをユーザが任意に設定できるようにしてもよい（コストを判断するためのデータ種（旅行時間、リンク長等）を、ユーザが選択し、または、優先順位を付けて設定できるようにする）。
【００３５】
経路誘導部１５は、経路探索部１４が探索した推奨経路と、マップマッチ処理部１３により地図データ上に合わせ込まれた現在位置の情報とを比較し、交差点を通過する前に直進すべきか、右左折すべきかを音声入出力装置４を用いて音声でユーザに知らせたり、ディスプレイ２に表示された地図上に進行すべき方向を表示してユーザに推奨経路を通知する。
【００３６】
地図表示処理部１６は、ディスプレイ２に表示が要求される領域にある地図データ３１０を地図データ記憶装置３からデータ読込部１２を介して受け取る。また、地図表示処理部１６は、経路探索部１４から探索した経路を受け取り、マップマッチ処理部１３から現在位置の情報を受け取る。そして、地図表示処理部１６は、道路、その他の地図構成物、現在位置、目的地、および経路誘導のための矢印といったマーク等をディスプレイ２の画面に描画させるための地図描画コマンドを生成し、グラフィックス処理部１８に出力する。
【００３７】
メニュー表示処理部１７は、設定部１０から出力される命令を受け、グラフィックス処理部１８が、様々な種類のメニューやグラフなどをディスプレイ２の画面に描画するようにメニュー描画コマンドを生成する。
【００３８】
グラフィックス処理部１８は、地図表示処理部１６およびメニュー表示処理部１７で生成されたコマンド（地図描画コマンド、メニュー描画コマンド）に基づいて、ディスプレイ２の画面上に画像データを表示させる。
【００３９】
続いて、演算処理部１のハードウェア構成を説明する。図４は、演算処理部１のハードウェア構成を示す図である。
【００４０】
図示するように、演算処理部１は、ＣＰＵ（中央演算処理装置）２１と、ＣＰＵ２１が実行するプログラムやデータを一時的に記憶するＲＡＭ（Random Access Memory）２２と、上記各部（設定部１０、現在位置検出部１１、データ読込部１２、マップマッチ処理部１３、経路探索部１４、経路誘導部１５、地図表示処理部１６、メニュー表示処理部１７、グラフィックス処理部１８）が有する機能を実行するためのプログラムが予め記憶されているＲＯＭ（Read Only Memory）２３と、メモリ間およびメモリと各デバイスとの間のデータを転送するＤＭＡ（Direct Memory Access）２４と、グラフィック描画を実行し且つ表示制御を行う描画コントローラ２５と、グラフィックスイメージデータを蓄えるＶＲＡＭ（Video  Random  Access  Memory）２６と、イメージデータをＲＧＢ信号に変換するカラーパレット２７と、アナログ信号をデジタル信号に変換するＡ/Ｄ変換器２８と、シリアル信号をバスに同期したパラレル信号に変換するＳＣI(Serial Communication Interface)２９と、パラレル信号をバスに同期させてバス上に載せるＰＩＯ（Parallel Input/Output）３０と、パルス信号を積分するカウンタ３１と、を有する。そして、上記各部（設定部１０、現在位置検出部１１、データ読込部１２、マップマッチ処理部１３、経路探索部１４、経路誘導部１５、地図表示処理部１６、メニュー表示処理部１７、グラフィックス処理部１８）の機能は、ＣＰＵ２１が、ＲＯＭ２３に記憶されている上記各部が有する機能を実行するためのプログラを、ＲＡＭ２２にロードし、実行することにより実現される。
【００４１】
続いて、本実施形態のナビゲーション装置が行う経路探索の処理について図５〜図７を用いて詳細に説明する。図５は、本実施形態のナビゲーション装置の経路探索処理のフローを説明するための図である。図６は、本実施形態のナビゲーション装置の出発地および目的地と、経由方面の関係を説明するための図である。図７は、本実施形態のナビゲーション装置の経由方面を設定するための設定画面の遷移の一例を示す図である。
【００４２】
図５に示すように、最初に、ナビゲーション装置の設定部１０は、ユーザから出発地および目的地の設定を、入力装置５を介して受け付ける処理を行い、Ｓ１０１に進む（Ｓ１００）。なお、本実施形態では、出発地および目的地の設定を受け付ける具体的手順については特に限定しないが、例えば、設定部１０は、メニュー表示処理部１７およびグラフィックス処理部１８を制御して、ディスプレイ２に出発地および目的地を設定するための設定画面を表示し、入力装置５を介し、ユーザが入力するデータに基づいて目的地および出発地のデータ（緯度、経度）を受付けるようにしてもよい。また、設定部１０は、現在位置検出部１１が検出した現在位置を取得し、その取得した現在位置を出発地として設定するようにしてもよい。
【００４３】
Ｓ１００において、出発地および目的地を設定した設定部１０は、ユーザに対して、目的地に向う際に経由したい方面（経由したいエリア）があるか否かの確認を行う（Ｓ１０１）。そして、設定部１０は、ユーザから経由方面の設定を行う旨の指示を、入力装置５を介して受付けた場合、Ｓ１０２に進み、ユーザから経由方面の設定を行わない旨の指示を受付けた場合、Ｓ１０９の処理に進む。
【００４４】
ここで、Ｓ１０１における経由方面の確認の手順について特に限定しないが、例えば、設定部１０は、メニュー表示処理部１７およびグラフィックス処理部１８を制御して、図７に示す設定画面４０ａをディスプレイ２に表示し、経由したい方面（経由したいエリア）があるか否かの確認を、入力装置５を介して行うようにしてもよい。このユーザへの経由方面があるか否かの確認は、出発地および目的地の２点から経路探索を行った後、再度、受付けるようにしてもよい。例えば、出発地および目的地の２点で求めた経路探索の結果をユーザに表示した後、設定部１０は、さらに図７に示す設定画面４０ｂをディスプレイ２に表示して、ユーザから経由したい方面（エリア）が在るか否かについて受付けるようにしてもよい。このように構成しておけば、経路探索の結果がユーザの所望する経路でない場合や、ユーザが別の経路をみてみたい場合等のユーザの要求に対応することができる。
【００４５】
Ｓ１０２では、設定部１０は、ユーザから入力装置５を介して経由方面の設定を受付ける処理を行う。なお、設定部１０が行う経由方面を受付ける具体的な手順については、特に限定しないが、例えば、メニュー表示処理部１７およびグラフィックス処理部１８を制御して、ディスプレイ２に地図データを表示して、表示した地図データから経由方面の設定を受付けるようにしてもよい。また、「関東地方」、「東京方面」、「関西地方」のように地方名の入力により、経由方面の設定を受付けるようにしてもよい。また、予め地図データに登録されている登録地（著名な施設や観光地名）の入力により経由方面の設定を受付けるようにしてもよい。また、設定部１０が、「電話番号（又は郵便番号）」に対応する位置を予め保持しておいて、電話番号の入力により、経由方面の設定を受付けるようにしてもよい。また、設定部１０は、住所の入力を受付けることで経由方面の設定を受付けるようにしてもよい。
【００４６】
例えば、設定部１０は、メニュー表示処理部１７およびグラフィックス処理部１８を制御して、図７に示す、設定画面４１〜４７を表示する。設定画面４１は、経由方面を指定するためのメニュー画面を例示したものである。図示するように、設定画面４１は、３態様（「地図から指定」、「地方名称から指定」、および「登録地から指定」）の経由方面を指定するための指定ボタンを有している。そして、画面上でのカーソルによる指定（或いは、タッチパネル方式により、設定画面４１上の所定の位置の押下）等により、対応する設定画面に遷移するように構成されている。
【００４７】
具体的には、設定画面４１において、「地図から指定」の指定ボタンが選択された場合には、設定画面４２に遷移し、「地方名称から指定」の指定ボタンが選択された場合には、設定画面４３に遷移する（「登録地から指定」の指定ボタンが選択された場合についての説明は省略する）。
【００４８】
設定画面４２は、地図上に出発地（矢印が指す位置）および目的地（旗のアイコンが指す位置）が表示されている（出発地および目的地はＳ１００で既に設定されている）。そして、設定画面４２は、「アイコン（図示する例では十字のアイコンを表示）」を移動させることにで、経由したい方面を地図上で指定できるように構成されている。設定画面４３は、「関東地方」や「関西地方」等の地方名が表示されていている。そして、設定画面４３は、画面上でのカーソルによる指定（或いは、タッチパネル方式により、設定画面４３上の所定の位置の押下）等により、経由したい方面を画面上から指定できるように構成されている。なお、設定画面４３に示す、地方名はあくまで例示に過ぎない。例えば、「東京方面」、「箱根方面」、「世田谷方面」のような都道府県名や市区町村名等を地方名として表示するようにしてもよい。
【００４９】
そして、設定画面４２、４３上での選択により、経由方面の指定を受付けた場合、設定画面４５を表示し、ユーザから指定内容の確認を受付けるようにする。そして、設定画面４５において、「ルートに追加」又は「位置を修正」の指定ボタンの選択を受付けた場合、設定画面４７を表示し、指定された経由方面の追加や修正を受付けるようにする。
【００５０】
また、設定画面４１において、「解除」が選択された場合には、方向指定の解除の確認画面として構成されている、設定画面４４に遷移する。そして、設定画面４４で、解除する旨が選択された場合（「はい」が選択された場合）、経由方面の指定は解除され、その後は、出発地および目的地の２点により、経路探索が行われるようになる。一方、設定画面４４で、解除しない旨が選択された場合（「いいえ」が選択された場合）、設定画面４０ａ（又は４０ｂ）に戻る。
【００５１】
図５に戻り説明を続ける。Ｓ１０２で、設定部１０は、経由方面を指定する設定を受付けた場合、受付けた経由方面を経由位置（地図データ上の位置（緯度、経度））に変換する処理を行う。具体的には、設定部１０は、図７の設定画面４２のように設定画面上に表示した地図上のカーソルにより経由方面が指定された場合、そのまま、カーソルが示す地図データ３１０上の位置を経由位置とする。設定部１０は、登録地（例えば署名な施設）から経由方面を指定する設定を受付けた場合、地図データ３１０上での登録地の位置を経由位置とする。また、設定部１０は、図７の設定画面４３のように地方名称により経由方面を指定された場合は、以下のように経由位置を特定する。
【００５２】
設定部１０は、経由方面（例えば、「関東方面」、「東京方面」等）を、その経由方面を示す経由位置に対応付けた経由方面ＴＢ（図示しない）を有している。そして、設定部１０は、図７の設定画面４３のように地方名称により経由方面を指定された場合（例えば、「関東方面」）、受付けた経由方面を、図示しない経由方面ＴＢの「地方名称」に対応付けられている地図データ３１０上の経路位置データ（緯度、経度）に変換する。そして、設定部１０は、出発地および目的地と、受付けた経由方面に対応する経路位置データを経路探索部１４に送信し、Ｓ１０３に進む。
【００５３】
Ｓ１０３では、経路探索部１４が、経路探索を行うための第１エリアの特定を行う。具体的には、経路探索部１４は、Ｓ１００で設定した出発地および目的地と、Ｓ１０２で設定された経由方面に対応する経由位置を内包する第１のエリアの特定を地図データ記憶装置３が記憶する地図データ３１０を利用して行う（地図データ３１０はデータ読込部１２を介して取得する）。例えば、図６に示すように、新潟を出発地３２として、大阪を目的地３３に設定している場合に、Ｓ１０２で「東京方面」が経由方面として設定されたとする（例えば、ユーザが、関越道〜東名高速等を経由合し大阪に向いたい場合等）。その場合、経路探索部１４は、出発地３２（新潟）、目的地３３（大阪）、および経由方面（「東京方面」）に対応する経由位置３４を内包する第１のエリア３５を特定する。
【００５４】
Ｓ１０３で第１のエリアを特定した後、経路探索部１４は、上記特定した第１のエリアの中から、出発地および上記受付けた経由方面に対応する経由位置を内包する第２のエリアを特定する（Ｓ１０４）。なお、本実施形態では、この第２のエリアを特定する具体的な手順については、特に限定しない。例えば、上記出発地および前記経由位置の２点を焦点とする楕円を第２のエリアとしてもよい。また、例えば、上記出発地と上記経由位置とを直線で結んで、前記出発地と前記経由位置とを結んだ直線から引いた垂線が所定の距離に入る領域を第２のエリアとしてもよい。なお、図６の例では、経路探索部１４は、第１のエリア３５の中から、出発地３２（新潟）および経由方面（「東京方面」）に対応する経由位置３４の２点を焦点とした楕円を第２のエリア３６として特定している。
【００５５】
その後、経路探索部１４は、Ｓ１０４と同様の手順により、上記特定した第１のエリアの中から、目的地および上記受付けた経由方面に対応する経由位置を内包する第３のエリアを特定する（Ｓ１０５）。図６の例では、経路探索部１４は、第１のエリア３５の中から、目的地３３（大阪）および経由方面（「東京方面」）に対応する経由位置３４の２点を焦点とした楕円を第３のエリア３７として特定している。
【００５６】
続いて、経路探索部１４は、Ｓ１０３で特定した第１エリアに含まれるメッシュ領域の各リンクデータを読込む処理を行い（一部でも第１エリアに含まれるメッシュ領域のリンクデータは読込む）、Ｓ１０７に進む（Ｓ１０６）。具体的には、経路探索部１４は、第１エリアに含まれるメッシュＩＤ３１１（図２参照）を特定し、特定したメッシュＩＤを持つ各リンクデータ３１２を、データ読込部１２を介して地図データ記憶装置３が記憶する地図データ３１０から読込む処理を行う。
【００５７】
Ｓ１０７では、経路探索部１４は、Ｓ１０６で読込んだ第１エリアに含まれるメッシュ領域内のメッシュＩＤを持つ各リンクデータ３１２の中から、Ｓ１０４およびＳ１０５で特定した第２および第３のエリアに含まれるメッシュ領域内のメッシュＩＤ３１１（図２参照）を持つリンクデータ３１２を抽出する。そして、経路探索部１４は、抽出した第２および第３のエリアに含まれるメッシュ領域内の各リンクデータ３１２のコストを下げる演算処理を行う。この演算処理については、具体的に限定しないが、例えば、図２に示す、リンクの旅行時間（或いは移動時間）情報３１２５に所定の係数を乗じてリンクの旅行時間の値を下げるようにしてもよい（例えば、所定の係数を「０．１」として、リンクの旅行時間情報３１２５に係数の「０．１」を乗算する）。また、例えば、経路探索部１４は、リンクの旅行時間情報３１２５から所定の値を減算することにより、コストを下げるようにしてもよい。
【００５８】
Ｓ１０７の処理を行った上で、経路探索部１４は、ダイクストラ法等により、上記第１エリア内の各リンクデータ３１２を用いて目的地から出発地に至る、経路コストが最適となる経路の探索を行い、推奨経路を算出する（Ｓ１０８）。
【００５９】
このように、本実施形態では、経由方面が設定された場合、経路探索を行う対象の第１のエリアの中から、ユーザが所望する経由方面（経由方面に対応する経由位置を含む）を含む、第２および第３エリア内のリンクデータ３１２のコストを下げるようにしている。その結果、経路探索部１４が、ダイクストラ法等により、読込んだ第１エリアに含まれるメッシュ領域内のリンクデータ３１２の中から、目的地から出発地に至る経路の探索を行えば、コストが下げられている第２および第３エリアに属するリンクが推奨経路を構成するリンクとして選択されるようになる。ずなわち、本実施形態によれば、ユーザが所望する方面（エリア）を通過し、かつコストを考慮した推奨経路を算出するおことができる。例えば、図６に示す例では、第２のエリア３６および第３のエリア３７内のリンクが推奨経路として算出されるようになる。
【００６０】
続いて、Ｓ１０９〜Ｓ１１０で行う処理、すなわちＳ１０１において、設定部１０が、ユーザから経由方面の設定を行わない旨の指示を受付けた場合の処理について説明する。Ｓ１０９〜Ｓ１１０は、出発地および目的地の２点が設定された場合の最適なコストを探索するための従来技術の処理が行われる。具体的には、Ｓ１０９では、経路探索部１４は、出発地および目的地を内包する第１のエリアの特定をして（Ｓ１０９）、該第１エリアに含まれるメッシュＩＤ３１１（図２参照）を特定し、特定したメッシュＩＤを持つ各リンクデータ３１２を、データ読込部１２を介して地図データ記憶装置３が記憶する地図データ３１０から読込む処理を行なう（Ｓ１１０）。その後、経路探索部１４は、上述したＳ１０８の処理に進む。なお、Ｓ１１０の後に行うＳ１０８は、上述のように、第２および第３エリア等は考慮されていないため、目的地および出発地の２点を結ぶ経路が探索されることとなる。
【００６１】
このように、本実施形態では、例えば、目的地に向う途中に経由したいエリアがある場合に、ユーザは、上記エリア内の具体的位置（施設や道路名）を調べないで、経由方面を設定するだけでその方面を経由する経路探索を行うことができる。
【００６２】
なお、本発明は以上で説明した実施形態に限定されるものではなく、本発明の要旨の範囲内において種々の変形が可能である。例えば、上記実施形態では、ユーザが経由方面を設定した場合、出発地および目的地と、経由方面に対応する経由位置を含む第１のエリアを設定するようにしているが、特にこれに限定するものではない。経路探索部１４は、第１のエリアを特定する際、受付けた経由方面の位置を考慮するようにしてもよい。例えば、経路探索部１４は、出発地から目的地までの第１の直線距離および該出発地からの前記経由位置までの第２の直線距離を算出し、該第２の直線距離が該第１の直線距離に比べて所定の距離より
長い場合、前記経由位置を除いて、前記出発地および前記目的地に２点から第１の領域を特定するようにしてもよい（前記出発地および前記目的地が含まれる領域を特定する）。そして、この場合には、経路探索部１４は、ユーザが入力した経由方面について考慮に入れないで、出発地および目的地の２地点から最適なコストの経路を算出する。
【００６３】
このように構成することにより、例えば、設定した出発地および目的地の関係から見て著しく逸脱する経由方面が設定されても、その経由方面を通過する経路が探索されることを防ぐことができる。例えば、上述した図６に示す例において、新潟を出発して大阪に向う経路探索の際に、九州方面を経由方面として設定した場合、九州方面を経由する経路が推奨経路として算出されることを防ぐことができる。また、上記のように第１のエリアから上記逸脱した経由方面に対応する経由位置を除いているため、経路探索の演算処理の負担を軽減させることができる。
【００６４】
また、上記実施形態の図５のＳ１０７において、経路探索部１４は、第２および第３のエリアに含まれるメッシュ領域内の各リンクデータ３１２の各リンクのコストを下げる演算処理を行うこととしているが、特にこれに限定するものではない。例えば、Ｓ１０７において、経路探索部１４は、第１のエリアに含まれるメッシュ領域内のメッシュＩＤを持つ各リンクデータ３１２であって、かつ第２および第３エリアに含まれないメッシュ領域内の各リンクデータ３１２の値を増加させるようにしてもよい（例えば、リンクの旅行時間情報３１２５に「１０」を係数として乗算する）。この場合も、上記同様に、経路探索部１４が、ダイクストラ法等により、目的地から出発地に至る経路コストが最適となる経路の探索を行えば、コストが上げられていない第２および第３エリアのリンクが推奨経路を構成するリンクとして選択されるようになる。
【００６５】
また、本実施形態では、車載用ナビゲーション装置の演算処理部１において、経路探索を行う場合を説明しているが特にこれに限定するものではない。例えば、車載用ナビゲーション装置が有する経路探索機能を外部の情報センタで行うようにしてもよい。この場合、車載用ナビゲーション装置に、外部の情報センタと通信可能な通信手段を設けておく。また、車載用ナビゲーション装置と通信可能な情報センタに上記経路探索部１４と同様の機能を有する探索部と地図データ３１２が記憶されている記憶部を設けておく。そして、情報センタは、車載用ナビゲーション装置から送信された出発地（現在位置）、目的地、および経由方面を示すデータを受信した場合、上述した図５のステップ１０３〜Ｓ１０８の処理を行い、推奨経路を探索し、その推奨経路を示すデータを車載用ナビゲーション装置に送信するようにする（この場合にナビゲーション装置のディスプレイ２に表示させる地図データを共に送信するようにしてもよい）。車載用ナビゲーション装置は、情報センタから送信された推奨経路を示すデータを受信して、その推奨経路データを利用して経路誘導を行う。
【図面の簡単な説明】
【００６６】
【図１】本発明の実施形態が適用された車載用ナビゲーション装置の概略構成図である。
【図２】本実施形態の地図データ記憶装置３に記憶されている地図データのデータ構造を模擬的に示す図である。
【図３】本実施形態の演算処理部１の機能構成を説明するための図である。
【図４】本実施形態の演算処理部１のハードウェア構成を示す図である。
【図５】本実施形態のナビゲーション装置の経路探索処理のフローを説明するための図である。
【図６】本実施形態のナビゲーション装置の出発地および目的地と、経由方面の関係を説明するための図である。
【図７】本実施形態のナビゲーション装置の経由方面を設定するための設定画面の遷移の一例を示す図である。
【符号の説明】
【００６７】
１…演算処理部、２…ディスプレイ、３…地図データ記憶装置、４…音声入出力装置、５…入力装置、６…車輪速センサ、７…地磁気センサ、８…ジャイロ、９…ＧＰＳ受信装置、１０…設定部、１１…現在位置検出部、１２…データ読込部、１３…マップマッチ処理部、１４…経路探索部、１５…経路誘導部、１６…地図表示処理部、１７…メニュー表示処理部、１８…グラフィックス処理部、２１…ＣＰＵ、２２…ＲＡＭ、２３…ＲＯＭ、２４…ＤＭＡ、２５…描画コントローラ、２６…ＶＲＡＭ、２７…カラーパレット、２８…Ａ/Ｄ変換器、２９…ＳＣI、３０…ＰＩＯ、３１…カウンタ、３２…出発地、３３…目的地、３４…経由位置、３５…第１のエリア、３６…第２のエリア、３７…第３のエリア、３１０…地図データ、３１１…メッシュＩＤ、３１２…リンクデータ、３１２１…リンクＩＤ、３１２２…ノード（開始ノード、終了ノード）の座標情報、３１２３…道路の種別情報、３１２４…リンク長情報、３１２５…リンク長情報、３１２６…２つのノード（開始ノード、終了ノード）にそれぞれ接続するリンクのリンクＩＤ
【図１】
2005098814.tif 000003
【図２】
2005098814.tif 000004
【図３】
2005098814.tif 000005
【図４】
2005098814.tif 000006
【図５】
2005098814.tif 000007
【図６】
2005098814.tif 000008
【図７】
2005098814.tif 000009