案内経路探索装置および案内経路探索方法
【課題】 現在地の後方の至近距離に目的地がある場合に、適切な経路が選択されること。
【解決手段】 案内経路探索装置の判断手段４１は、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、現在地の後方の所定距離以下であるか否かを判断する。コスト計算手段４３は、判断手段４１により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地での進行方向前方のリンクおよび／またはノードのコスト情報の値を低くして進行方向前方のリンクおよび／またはノードを優先させる道なり優先制御を禁止し、コスト情報記憶手段１５に記憶されるリンクおよび／またはノードのコスト情報を用いて、探索された経路のコストを計算する。選択手段４４は、コスト計算手段４３により計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路４８として選択する。
【解決手段】 案内経路探索装置の判断手段４１は、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、現在地の後方の所定距離以下であるか否かを判断する。コスト計算手段４３は、判断手段４１により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地での進行方向前方のリンクおよび／またはノードのコスト情報の値を低くして進行方向前方のリンクおよび／またはノードを優先させる道なり優先制御を禁止し、コスト情報記憶手段１５に記憶されるリンクおよび／またはノードのコスト情報を用いて、探索された経路のコストを計算する。選択手段４４は、コスト計算手段４３により計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路４８として選択する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、案内経路探索装置および案内経路探索方法に関する。
【背景技術】
【０００２】
特許文献１は、車両用誘導装置を開示する。この車両用誘導装置は、経路探索時に車両が存在するリンクに対して、該経路探索時の該車両の進行方向と逆方向になるリンクが経路として選択されることを制限する。具体的には、Ｕターン側のリンクのコストに所定値を加算したり、係数を掛けたりする。
【０００３】
また、特許文献１は、リンクコストの変更値を適当な値に設定することにより、市街地等において、車両の進行方向側の次の交差点ノードまでの距離が非常に大きい場合、または進行方向が行き止まりになっているような場合には、Ｕターンをするリンクを含む経路のコストが相対的に低くなり、このＵターンをするリンクを含む経路が探索結果として得られるようにすることができるとしている。
【０００４】
【特許文献１】特開平８−１５９７９３号公報（特許請求の範囲、発明の詳細な説明、段落００３１、段落００３２など）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来の案内経路探索装置は、特許文献１に記載される従来の車両用誘導装置において経路探索時にはＵターン側のリンクのコストに所定値を加算したり、係数を掛けたりしているように、Ｕターン規制、道なり優先（自車の向き、すなわち進行方向前方のリンクなどのコストを下げる）などの条件の下で、探索された各候補経路のコストを計算し、そのコストが低いものを案内経路として選択している。
【０００６】
その結果、道なり優先の場合には、目的地が設定されると、自車の進行方向を判断し、その進行方向前方へ道なりに進んでから目的地へ向かう経路が選択され易くなる。別の言い方をすれば、現在地においてＵターンする経路が探索されずに済む。
【０００７】
しかしながら、このように道なり優先の条件が設定されている場合、たとえば現在地の後方の至近距離に目的地が設定され、明らかにＵターンなどをして目的地へ向うのが最も早い場合であっても、道なりに直進した後、その道を外れて目的地に向かう経路が、案内経路として選択されてしまう。
【０００８】
本発明は、現在地の後方の至近距離に目的地がある場合に、適切な経路が選択される案内経路探索装置および案内経路探索方法を得ることを目的とする。
【課題を解決するための手段】
【０００９】
本発明に係る案内経路探索装置は、経路探索の際に、現在地での進行方向前方のリンクおよび／またはノードのコスト情報の値を低くして進行方向前方のリンクおよび／またはノードを優先させる道なり優先制御を実行する案内経路探索装置において、起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、現在地の後方の所定距離以下であるか否かを判断する判断手段と、経路探索の起点から終点までの経路として選択されるリンクおよび／またはノードのコスト情報を記憶するコスト情報記憶手段と、判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、道なり優先制御を禁止し、コスト情報記憶手段に記憶されるリンクおよび／またはノードのコスト情報を用いて、探索された経路のコストを計算するコスト計算手段と、コスト計算手段により計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択する選択手段と、を有するものである。
【００１０】
本発明に係る他の案内経路探索装置は、経路探索の起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、現在地の後方の所定距離以下であるか否かを判断する判断手段と、経路探索の起点から終点までの経路として選択されるリンクおよび／またはノードのコスト情報を記憶するコスト情報記憶手段と、判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、コスト情報記憶手段に記憶される各リンクおよび／またはノードのコスト情報を用いて、進行方向前方へ進む経路より進行方向後方へ進む経路の方が選択され易くなるようにコスト情報を調整して、探索された経路のコストを計算するコスト計算手段と、コスト計算手段により計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択する選択手段と、を有するものである。
【００１１】
本発明に係る他の案内経路探索装置は、上述した発明の構成に加えて、コスト計算手段が、現在地から進行方向後方となるリンクおよび／またはノードのコスト情報として、コスト情報記憶手段に記憶されるそのリンクおよび／またはノードのコスト情報より小さな値を有するコスト情報を使用して、探索された経路のコストを計算し、選択手段が、コストが最も低い経路を案内経路として選択するものである。
【００１２】
本発明に係る他の案内経路探索装置は、上述した各発明の構成に加えて、コスト情報記憶手段に記憶されるリンクまたはノードのコスト情報から、現在地から進行方向後方となるリンクまたはノードのコスト情報を得る際に、コスト情報の値を小さくするＵターン優先係数を記憶する優先係数記憶手段を有し、コスト計算手段が、判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地から進行方向後方となるリンクおよび／またはノードについて、コスト情報記憶手段に記憶されるそのリンクおよび／またはノードのコスト情報にＵターン優先係数を適用したコスト情報を使用して、探索された経路のコストを計算し、選択手段が、コストが最も低い経路を案内経路として選択するものである。
【００１３】
本発明に係る他の案内経路探索装置は、上述した各発明の構成に加えて、コスト計算手段が、現在地から進行方向前方となるリンクおよび／またはノードのコスト情報として、コスト情報記憶手段に記憶されるそのリンクおよび／またはノードのコスト情報より大きな値を有するコスト情報を使用して、探索された経路のコストを計算し、選択手段が、コストが最も低い経路を案内経路として選択するものである。
【００１４】
本発明に係る他の案内経路探索装置は、上述した各発明の構成に加えて、コスト情報記憶手段に記憶されるリンクまたはノードのコスト情報から、現在地から進行方向前方となるリンクまたはノードのコスト情報を得る際に、コスト情報の値を大きくする道なり劣後係数を記憶する劣後係数記憶手段を有し、コスト計算手段が、判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地から進行方向前方となるリンクまたはノードについて、コスト情報記憶手段に記憶されるそのリンクまたはノードのコスト情報に道なり劣後係数を適用したコスト情報を使用して、探索された経路のコストを計算し、選択手段が、コストが最も低い経路を案内経路として選択するものである。
【００１５】
本発明に係る案内経路探索方法は、起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、現在地の後方の所定距離以下であるか否かを判断するステップと、経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地での進行方向前方のリンクおよび／またはノードのコスト情報の値を低くして進行方向前方のリンクおよび／またはノードを優先させる道なり優先制御を禁止し、コスト情報記憶手段に記憶されるリンクおよび／またはノードのコスト情報を用いて、探索された経路のコストを計算するステップと、計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択するステップと、を有するものである。
【００１６】
本発明に係る他の案内経路探索方法は、経路探索の起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、現在地の後方の所定距離以下であるか否かを判断するステップと、経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、コスト情報記憶手段に記憶されるリンクおよび／またはノードのコスト情報を用いて、進行方向前方へ進む経路より進行方向後方へ進む経路の方が選択され易くなるようにコスト情報を調整して、探索された経路のコストを計算するステップと、計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択するステップと、を有するものである。
【発明の効果】
【００１７】
本発明では、現在地の後方の至近距離に目的地がある場合に、適切な経路が選択される。
【発明を実施するための最良の形態】
【００１８】
以下、本発明の実施の形態に係る案内経路探索装置および案内経路探索方法を、図面に基づいて説明する。案内経路探索装置は、カーナビゲーションシステムの一部として説明する。案内経路探索方法は、カーナビゲーションシステムの動作の一部として説明する。
【００１９】
実施の形態１．
図１は、本発明の実施の形態１に係るカーナビゲーションシステムを示す構成図である。カーナビゲーションシステムは、現在地から、目的地あるいは経由地への車両の案内経路を探索し、その案内経路で車両が移動するように経路を案内するものである。
【００２０】
カーナビゲーションシステムは、メインコンピュータ１を有する。メインコンピュータ１は、プログラムを実行するＣＰＵ２（中央処理装置）と、ＣＰＵ２が実行しているプログラムやデータを記憶するＲＡＭ３（ランダムアクセスメモリ）と、周辺機器が接続される入出力ポート４と、これらを接続するシステムバス５と、を有する。
【００２１】
入出力ポート４には、液晶デバイス１１と、タッチパネル１２と、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）受信機１３と、ＶＩＣＳ（Ｖｅｈｉｃｌｅ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）受信機１４と、コスト情報記憶手段、優先係数記憶手段および劣後係数記憶手段としての記憶デバイス１５と、が接続される。
【００２２】
液晶デバイス１１は、液晶ディスプレイパネルなどといった表示部を有する。液晶デバイス１１は、表示データに基づき、表示部に画像を表示する。
【００２３】
タッチパネル１２は、透明なスクリーンを有する。透明なスクリーンは、液晶デバイス１１の表示部に重ねて配設される。タッチパネル１２は、透明なスクリーン内の指が触れた位置を検知し、検出した位置の位置情報を出力する。
【００２４】
ＧＰＳ受信機１３は、ＧＰＳ衛星からのＧＰＳ電波を受信する。ＧＰＳ電波は、ＧＰＳ衛星の位置情報と時間情報とを有する。ＧＰＳ受信機１３は、たとえば３つ以上のＧＰＳ衛星からのＧＰＳ電波を受信すると、それら複数のＧＰＳ衛星に対するＧＰＳ受信機１３の相対位置を演算し、その相対位置に基づいてＧＰＳ受信機１３の地球上の位置情報を生成する。地球上の位置情報は、たとえば世界測地系での緯度経度の値として表現される。ＧＰＳ受信機１３は、生成したＧＰＳ受信機１３の位置情報を出力する。
【００２５】
ＶＩＣＳ受信機１４は、電波ビーコン、光ビーコンあるいはＦＭ多重放送により送信される交通情報を受信する。交通情報には、道路の混雑度を示す渋滞情報や、道路の通行止め時間帯などを示す交通規制情報が含まれる。ＶＩＣＳ受信機１４は、受信した交通情報を出力する。
【００２６】
記憶デバイス１５は、たとえばハードディスクドライブなどにより構成される。図２は、図１中の記憶デバイス１５が記憶する内容を示す説明図である。記憶デバイス１５は、ナビゲーションプログラムと、ナビゲーションデータとを記憶する。ナビゲーションプログラムは、案内経路生成プログラム２１と、経路案内プログラム２２と、を有する。ナビゲーションデータは、地点データ群２４と、リンクデータ群２５と、ノードデータ群２６２６と、コスト計算条件リスト２７と、地図データ２８と、を有する。
【００２７】
なお、記憶デバイス１５に記憶されるナビゲーションプログラムとナビゲーションデータとは、たとえばＤＶＤ（デジタル・バーサタイル・ディスク）−ＲＯＭ（リード・オンリィ・メモリ）などのコンピュータ読み取り可能な記録媒体や伝送媒体を介して、記憶デバイス１５に保存されるようにしてもよい。また、ナビゲーションプログラムとナビゲーションデータとは、コンピュータ読み取り可能な記録媒体に記憶されていてもよい。この場合、記憶デバイス１５は、この記録媒体のデータを読み取るドライブなどにより構成される。
【００２８】
地点データ群２４は、複数のレコードを有する。地点データ群２４の各レコードは、１つの地点のデータを有する。各レコードは、その地点にある建物、店舗、施設などの名称、その地点の位置情報などを有する。地点データ群２４の複数の地点は、目的地３５、経由地あるいは出発地などとして選択可能な地点である。
【００２９】
リンクデータ群２５およびノードデータ群２６は、カーナビゲーションシステムが、車両の経路探索や経路案内において使用するデータである。車両は、道路を移動する。道路には、交差点などの道路の分岐点がある。ナビゲーションシステムでは、この道路の分岐点などをノードとして取り扱う。２つの分岐点の間の道路などをリンクとして取り扱う。リンクの両端は、ノードに接続される。ノードには、１つ以上のリンクが接続される。
【００３０】
図３は、ある地域の道路と、リンクおよびノードとの関係を説明する図である。図３（Ａ）は、ある地域の道路を示す図である。図３（Ｂ）は、その地域に対応付けられるノードおよびリンクを示す図である。図３（Ｂ）において、各ノードは、四角形で示され、リンクは、矢印で示される。
【００３１】
図３（Ａ）に示す地域には、第一の国道３１と、第一の地方道３２とが、図の横方向に沿って並行に通っている。また、第二の国道３３と、第二の地方道３４とが、図の縦に通っている。第二の国道３３は、第一の国道３１と、第一の地方道３２と交差する。第二の地方道３４は、第一の地方道３２と交差し、第一の国道３１につきあたる。
【００３２】
このような地域の道路は、図３（Ｂ）に示すように、複数のリンクおよび複数のノードとしてデータ化される。ノードは、第二の国道３３と第一の国道３１との交差点３６、第二の国道３３と第一の地方道３２との交差点３７、第二の地方道３４と第一の国道３１との交差点（第二の地方道３４のつきあたり）３８、および、第二の地方道３４と第一の地方道３２との交差点３９に対応付けて設けられる。この地域のノードは、合計４つになる。
【００３３】
また、このような地域の道路と対応づけて、リンクは、交差点と交差点との間の区間毎に設けられる。具体的には、図の横方向に沿う第一の国道３１は、２つのノードを有する。したがって、この片側二車線（計４車線）の道路は、６本のリンクで構成される。同様に、第一の地方道３２は、６本のリンクで構成される。第二の国道３３は、６本のリンクで構成される。第二の地方道３４は、４本のリンクで構成される。この地域のリンクは、合計２２本となる。
【００３４】
リンクデータ群２５は、複数のレコードを有する。リンクデータ群２５の各レコードは、１つのリンクのデータを有する。各レコードは、そのリンクに関する交通規制情報や、そのリンクの距離、そのリンクを通過するコスト情報、そのリンクに固有の識別番号、そのリンクが接続されるノードの識別番号などを有する。リンクに関する交通規制情報には、たとえば、一方通行路、時間帯通行禁止、右折禁止、Ｕターン禁止、道幅（幅員）などの情報がある。なお、各レコードには、１つのリンクではなく、１つの道路のすべてのリンクが対応付けられていてもよい。
【００３５】
ノードデータ群２６は、複数のレコードを有する。ノードデータ群２６の各レコードは、１つのノードのデータを有する。各レコードは、そのノードの位置情報、そのノードに関する交通規制情報、そのノードを通過するコスト情報、そのノードに固有の識別番号、そのノードに接続されるリンクの識別番号などを有する。ノードに関する交通規制情報としては、たとえば、信号機の有無、右折禁止、Ｕターン禁止などの情報がある。
【００３６】
ノードを通過するコスト情報およびリンクを通過するコスト情報は、それらの通過し易さあるいは通過し難さに応じた値を有する。これらのコスト情報は、通過し難いほど大きな値を有する。
【００３７】
なお、実際に演算に使用するコスト情報そのものは、記憶デバイス１５においてたとえば道路種別などと対応付けて記憶され、これらノードデータ群２６およびリンクデータ群２５の各レコードは、この種別の指定情報を有するデータ構造になっていてもよい。また、コスト情報の値は、通過し易さのみに応じた値ではなく、たとえば、道路の有料無料に応じた値、道路の走りやすさに応じた値、道路の景観の良否に応じた値、道路の交通量に応じた値、あるいはそれらを組み合わせた値などになっていてもよい。
【００３８】
図２に戻り、記憶デバイス１５に記憶されるコスト計算条件リスト２７は、経路のコストを計算するときの計算条件を有する。具体的にはたとえば、コスト計算条件リスト２７は、渋滞係数、道なり優先係数などの各種の係数を記憶する。
【００３９】
渋滞係数は、渋滞しているリンクおよびノードのコスト情報に乗算される係数である。道なり優先係数は、１より大きい値を有する。これにより、渋滞しているリンクおよびノードの通過コストを上げることができる。
【００４０】
道なり優先とは、たとえば車両の進行方向や走行車線が予め判っている場合、その進行方向の道路あるいは車線が、その他の道路に比べて、案内経路として相対的に選択され易くすることである。道なり優先係数は、その道なりのリンクのコスト情報に乗算される係数である。道なり優先係数は、１より小さい値を有する。これにより、車両の進行方向の道路の通過コストを下げることができる。
【００４１】
地図データ２８は、液晶ディスプレイに地図を表示するために使用するデータである。このような地図データ２８としては、たとえば、二次元あるいは三次元のベクトル地図データ２８がある。ベクトル地図データ２８は、地図の背景画像となる背景データと、その背景画像の上に描画されるベクトルデータと、を有する。背景画像は、たとえば公園、河川、池などを色分けした画像データである。ベクトルデータは、たとえば道路毎の描画データである。なお、地図データ２８は、この他にも、ランドマーク用の三次元のポリゴンデータや、各地点に対応付けられたアイコンデータなどを備えていてもよい。
【００４２】
案内経路生成プログラム２１は、ＣＰＵ２に実行されることで、メインコンピュータ１に、案内経路を生成するための各種の機能を実現する。図４は、図１中のＣＰＵ２が案内経路生成プログラム２１を実行することで、カーナビゲーションシステムに実現される機能を示すブロック図である。図１中のＣＰＵ２が案内経路生成プログラム２１を実行することで、判断手段としてのコスト計算条件設定部４１と、候補経路生成部４２と、コスト計算手段としてのコスト計算部４３と、選択手段としての案内経路選択部４４と、が実現される。
【００４３】
コスト計算条件設定部４１は、コスト計算条件リスト２７に基づいて、探索時の車両の状況などに応じたコスト計算条件４６を生成し、記憶デバイス１５に記憶させる。コスト計算条件４６は、たとえば、道なり優先にて探索する状況下では、道なり優先係数を有する。
【００４４】
候補経路生成部４２は、リンクデータ群２５およびノードデータ群２６を使用して、探索の起点から終点までの経路を探索し、記憶デバイス１５に記憶させる。探索した経路は、探索の起点と終点とを１または複数のリンクおよびノードで繋いだものとなる。候補経路生成部４２は、その探索した経路のデータを、候補経路として記憶デバイス１５に記憶させる。複数の候補経路により、記憶デバイス１５には、候補経路リスト４７が記憶される。なお、車両の現在地あるいは出発地などが、経路探索の起点として利用される。目的地３５あるいは経由地などが、経路探索の終点として利用される。
【００４５】
コスト計算部４３は、候補経路生成部４２により探索された候補経路のコストを計算する。
【００４６】
案内経路選択部４４は、コストが最も低い候補経路を案内経路４８として選択し、記憶デバイス１５に記憶させる。
【００４７】
経路案内プログラム２２は、ＣＰＵ２に実行されることで、メインコンピュータ１に、経路を案内するための各種の機能を実現する。図５は、図１中のＣＰＵ２が経路案内プログラム２２を実行することで、カーナビゲーションシステムに実現される機能を示すブロック図である。図１中のＣＰＵ２が経路案内プログラム２２を実行することで、経路案内手段としての経路案内部５６が実現される。
【００４８】
経路案内部５６は、記憶デバイス１５に記憶されている案内経路４８および地図データ２８を読み込み、これらを用いて、液晶デバイス１１に案内経路４８および現在地の周辺地図などを表示させる。なお、経路案内部５６は、必要に応じて図示外のスピーカから音声案内を出力させるようにしてもよい。
【００４９】
次に、以上の構成を有する実施の形態１に係るカーナビゲーションシステムの動作を説明する。まず、図４を参照しながら、案内経路４８の探索処理について説明する。
【００５０】
また、以下の説明では、案内経路４８の生成処理の具体例として、図３（Ａ）において自車位置マーク４０にて示すように、車両は、第二の国道３３と第二の地方道３４との間において、第一の国道３１を走行しているものとする。この自車位置マーク４０がある場所が現在地となる。
【００５１】
また、目的地３５が、この第一の国道３１において、車両の走行方向後方で且つ２ｋｍ以内の距離に設定された場合を例として説明する。目的地３５は、たとえば地点データを液晶デバイス１１に表示し、その表示においてタッチパネル１２が出力する操作位置情報に基づいて選択した地点を、目的地３５として設定すればよい。
【００５２】
自車位置マーク４０（現在地）の位置情報４９および目的地３５の位置情報５０は、記憶デバイス１５に記憶される。
【００５３】
また、記憶デバイス１５には、自車位置マーク４０（現在地）の位置情報４９および目的地３５の位置情報５０のほかにも、ＶＩＣＳ受信機１４が受信した交通情報に含まれる渋滞情報あるいは交通規制情報（渋滞・交通規制情報５１）が記憶されているものとする。
【００５４】
なお、経路探索における自車の現在地の位置情報４９としては、たとえばＧＰＳ受信機１３が生成したＧＰＳ受信機１３の位置情報が使用できる。自車の現在地としては、他にもたとえば、ＧＰＳ受信機１３の位置情報に基づいて特定されるリンク上の位置であってもよい。この場合、自車の現在地は、たとえば、ＧＰＳ受信機１３の位置情報からそのリンクへ垂線を下ろしたときのその垂線とリンクとが交差する地点が、自車の現在地となる。このように自車が存在しているリンクが特定されている場合、図３（Ｂ）に示すように、自車位置マーク４０は、このマッチングしているリンク上の当該地点に表示されることになる。
【００５５】
図６は、図４に示すカーナビゲーションシステムの経路探索時の動作を示すフローチャートである。
【００５６】
タッチパネル１２などから、目的地３５の選択などに伴って探索開始指示があると、コスト計算条件設定部４１は、コスト計算条件４６の設定処理を開始する。コスト計算条件設定部４１は、まず、探索の起点として、記憶デバイス１５に記憶されている現在地を選択するとともに、探索の終点として記憶デバイス１５に記憶されている目的地３５あるいは経由地を選択する。
【００５７】
探索の起点および終点を選択すると、コスト計算条件設定部４１は、経路探索条件の設定を開始する。コスト計算条件設定部４１は、コスト計算条件リスト２７に記憶されている渋滞係数などを、コスト計算条件４６として記憶デバイス１５に記憶させる。
【００５８】
コスト計算条件設定部４１は、また、探索の起点から終点までの直線距離を演算する。コスト計算条件設定部４１は、探索の起点から終点までの直線距離が２ｋｍ以下か否かを判断する（ステップＳＴ１）。
【００５９】
探索の起点から終点までの直線距離が２ｋｍより長い場合、コスト計算条件設定部４１は、コスト計算条件リスト２７から道なり優先係数を読み込み、読み込んだ道なり優先係数をコスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２）。
【００６０】
探索の起点から終点までの直線距離が２ｋｍ以下である場合、コスト計算条件設定部４１は、自車の進行方向を基準として、探索の起点から目的地３５を見た方向の角度（以下、目的地方角とよぶ。）を計算する。自車の進行方向としては、停車時の進行方向であっても、その時のＧＰＳ受信機１３からの位置情報に基づいて特定される方向であっても、自車がマッチングしているリンクの方向であってもよい。そして、コスト計算条件設定部４１は、目的地方角が９０度から２７０度の範囲内か否かを判断する（ステップＳＴ３）。
【００６１】
目的地方角が９０度より小さいか、もしくは、２７０度より大きい場合、コスト計算条件設定部４１は、コスト計算条件リスト２７から道なり優先係数を読み込み、読み込んだ道なり優先係数をコスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２）。
【００６２】
以上のコスト計算条件４６の設定処理により、記憶デバイス１５には、道なり優先係数などの各種の係数がコスト計算条件４６として記憶される。自車の現在位置から目的地３５までの距離が２ｋｍ以下であって、且つ、目的地方角が９０度以上且つ２７０度以下である場合には、道なり優先係数は、コスト計算条件４６として設定されない。探索の起点と終点との位置関係がこれ以外の位置関係の場合には、道なり優先係数は、コスト計算条件４６として設定される。
【００６３】
たとえば、図３（Ａ）では、半円のハッチングが施された部分が、自車の現在位置から２ｋｍ以下の距離であって、且つ、目的地方角が９０度以上且つ２７０度以下となる区域となる。図３（Ａ）の目的地３５は、この半円のハッチングが施された部分内にある。この場合、コスト計算条件設定部４１は、道なり優先係数を、コスト計算条件４６として設定しない。
【００６４】
コスト計算条件４６の設定処理が終了すると、コスト計算条件設定部４１は、候補経路生成部４２に候補経路の生成を指示する。
【００６５】
なお、コスト計算条件設定部４１は、コスト計算条件４６の設定処理の開始前に、候補経路生成部４２に候補経路の生成を指示するようにしてもよい。コスト計算条件設定部４１は、たとえばＶＩＣＳ受信機１４からの渋滞情報受信に伴う探索開始指示などがあった場合などには、コスト計算条件４６の設定処理をすることなく、候補経路生成部４２に候補経路の生成を指示するようにしてもよい。コスト計算条件設定部４１は、ＧＰＳ受信機１３からの位置情報の変化が少ないことなどを検出し、コスト計算条件４６の設定処理をすることなく、自発的に候補経路生成部４２に候補経路の生成を指示するようにしてもよい。
【００６６】
候補経路生成部４２は、リンクデータ群２５およびノードデータ群２６を使用して、候補経路を生成する（ステップＳＴ４）。具体的には、候補経路生成部４２は、ノードの位置情報やリンクのノードに対する接続情報を用いてリンクをノードに繋ぎ、探索の起点から終点までのリンクの鎖を生成する。候補経路生成部４２は、この探索の起点から終点までのリンクの鎖を、候補経路として生成する。
【００６７】
探索の起点（現在地）４０と終点（目的地３５）とが図３（Ａ）に示すような位置関係にある場合、候補経路生成部４２は、たとえば、自車がマップマッチングしているリンクＬ１を最初のリンクとして、図３（Ｂ）に示すように、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路を生成する。この候補経路は、自車の進行方向へ真直に進んでから、終点に向かう経路である。この候補経路は、その途中においてＵターンすることはない。
【００６８】
また、候補経路生成部４２は、たとえば、自車がマップマッチングしているリンクと同一道路上の反対車線のリンクＬ６を最初のリンクとして、図３（Ｂ）に示すように、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路を生成する。この候補経路は、自車の現在地においてＵターンしてから、終点に向かう経路である。
【００６９】
この候補経路の生成処理において、候補経路生成部４２は、リンクデータ群２５、ノードデータ群２６、渋滞・交通規制情報５１などの情報を参照し、走行可能な経路を探索する。たとえば、仮に図３（Ａ）の第一の国道３１においてＵターン禁止や交差点以外での右折禁止などの交通規制情報がある場合、候補経路生成部４２は、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路は生成しない。他にもたとえば、仮に第二の地方道３４において交差点３８での右折禁止時間帯があり、その時間帯に該当するときには、候補経路生成部４２は、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路を生成しない。
【００７０】
候補経路生成部４２は、生成した候補経路を記憶デバイス１５に記憶させる。これにより、記憶デバイス１５には、候補経路リスト４７が記憶される。
【００７１】
記憶デバイス１５に候補経路が記憶されると、コスト計算部４３は、各候補経路のコストを計算する（ステップＳＴ５）。
【００７２】
コスト計算部４３は、まず、候補経路に含まれる各リンクおよび各ノードについて、１つ１つの個別の通過コストを計算する。
【００７３】
このとき、コスト計算条件４６にたとえば道なり優先係数が設定されている場合、コスト計算部４３は、その条件に該当するリンクあるいはノードのリンクデータ群２５あるいはノードデータ群２６におけるコスト情報に、その係数を乗算し、その演算結果を当該リンクあるいはノードの個別の通過コストとする。これにより、道なりに該当する道路の通過コストは低くなる。
【００７４】
また、渋滞・交通規制情報５１において渋滞が発生している道路のリンクについては、コスト計算部４３は、そのリンクについて渋滞係数を乗算する。渋滞係数は、１以上の係数である。これにより、渋滞している経路の通過コストは高くなる。
【００７５】
コスト計算条件４６に係数が設定されていないリンクおよびノードについては、コスト計算部４３は、そのリンクあるいはノードのリンクデータ群２５あるいはノードデータ群２６におけるコスト情報をそのまま、そのリンクあるいはノードの個別の通過コストとする。
【００７６】
候補経路に含まれるすべてのリンクおよびすべてのノードの個別の通過コストを計算したら、コスト計算部４３は、そのすべての個別の通過コストを加算し、その演算結果をその候補経路のコストとする。なお、コスト計算部４３は、リンクあるいはノード毎の個別の通過コストを乗算したり、所定の演算式にて計算したりすることで、候補経路のコストを計算するようにしてもよい。
【００７７】
具体的にはたとえば、先の「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路の場合、コスト計算部４３は、リンクＬ１、ノードＮ１、リンクＬ２、ノードＮ２、リンクＬ３、ノードＮ３、リンクＬ４、ノードＮ４およびリンクＬ５のそれぞれの個別の通過コストを計算し、それらを加算した値を、候補経路のコストとして計算する。
【００７８】
また、図３（Ａ）の場合、半円のハッチング内に目的地３５がある。そのため、コスト計算条件４６として、道なり優先係数が設定されていない。したがって、コスト計算部４３は、リンクＬ１およびノードＮ１の個別の通過コストとして、リンクデータ群２５およびノードデータ群２６に記憶されるそれぞれのコスト情報をそのまま、そのリンクあるいはノードの個別の通過コストとして使用して、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストを計算する。
【００７９】
他にもたとえば、コスト計算部４３は、リンクＬ６、ノードＮ４およびリンクＬ５のそれぞれの個別の通過コストを計算し、それを加算して「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストとして計算する。
【００８０】
記憶デバイス１５に記憶される各候補経路のコストが計算されると、案内経路選択部４４は、その記憶デバイス１５に記憶される複数の候補経路（候補経路リスト４７）の中から、コストが最も低い候補経路を選択する（ステップＳＴ６）。
【００８１】
図３（Ａ）の場合、半円のハッチング内に目的地３５がある。そのため、コスト計算条件４６として、道なり優先係数が設定されずに、各候補経路のコストが計算される。したがって、案内経路選択部４４は、リンクデータ群２５およびノードデータ群２６のコスト情報に基づいて生成した「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストと、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストと、を比較する。
【００８２】
「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストは、コスト計算条件４６において道なり優先係数などが設定されていない限り、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストより低い。したがって、案内経路選択部４４は、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路を、案内経路４８として選択する。
【００８３】
案内経路選択部４４は、選択した１つの候補経路を、案内経路４８として記憶デバイス１５に記憶させる。
【００８４】
以上の案内経路４８の探索処理により、記憶デバイス１５には、探索の起点から終点までの案内経路４８が記憶される。図３（Ａ）の場合には、案内経路４８として「起点→Ｌ６→Ｎ４→Ｌ５→終点」という経路が記憶デバイス１５に記憶される。この「起点→Ｌ６→Ｎ４→Ｌ５→終点」という経路は、自車の現在地においてＵターンしてから、終点に向かう経路である。
【００８５】
なお、仮に図３の目的地３５が半円の外側に位置している場合、コスト計算条件４６として道なり優先係数が設定されることで、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストが「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストより高くなる場合、記憶デバイス１５には、案内経路４８として「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という経路が記憶される。この経路は、自車の現在地から進行方向に直進してから、Ｕターンすることなく、終点に向かう経路である。
【００８６】
次に、図５を参照しながら、案内経路４８を用いた経路案内について説明する。
【００８７】
経路案内部５６は、ＧＰＳ受信機１３からの位置情報を読み込む。経路案内部５６は、ＧＰＳ受信機１３からの位置情報を自車の位置情報として、自車の周辺の案内経路４８および地図データ２８を記憶デバイス１５から読み込む。経路案内部５６は、読み込んだ案内経路４８および地図データ２８から表示データを生成する。経路案内部５６は、自車位置マーク４０を含む表示データを生成する。経路案内部５６は、生成した表示データを液晶デバイス１１へ出力する。液晶デバイス１１は、表示データに基づき、表示部に地図および案内経路４８を表示する。
【００８８】
図７は、液晶デバイス１１に表示される地図および案内経路の一例を示す表示画面である。表示画面には、自車位置マーク４０と、案内する経路と、地図と、目的地３５とが表示される。さらに、液晶デバイス１１には、自車位置マーク４０のある現在地からＵターンして目的地３５へ向かう案内経路６１が表示される。
【００８９】
経路案内部５６は、周期的に、ＧＰＳ受信機１３からの位置情報を読み込む。経路案内部５６は、ＧＰＳ受信機１３からの位置情報により特定される自車の位置が、液晶デバイス１１に表示させている自車位置マーク４０の位置から移動したか否かを判断する。
【００９０】
自車の位置が移動したと判断したら、経路案内部５６は、その新たな自車の位置を基準として、自車の周辺の案内経路４８および地図データ２８を記憶デバイス１５から読み込み、表示データを生成する。液晶デバイス１１は、経路案内部５６により生成された表示データを表示する。
【００９１】
なお、仮に、先の「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という経路が案内経路である場合、図７の点線で示す経路６２が案内経路として表示される。
【００９２】
また、経路案内部５６は、ＧＰＳ受信機１３からの位置情報を読み込んだら、自車位置の移動を判断することなく、新たな表示データを生成するようにしてもよい。経路案内部５６は、図示外のジャイロセンサからの移動量および移動方向に関する情報に基づいて、自車の現在地を判断するようにしてもよい。
【００９３】
このように、経路案内において、カーナビゲーションシステムは、ＧＰＳ受信機１３からの位置情報を自車の位置情報として用い、その自車の位置の周辺の地図および案内経路４８を、液晶デバイス１１に表示し続ける。したがって、車両の運転手が、液晶デバイス１１に表示される案内経路４８にそって自車位置マーク４０が移動するように車両を運転することで、車両は、現在地などから目的地３５あるいは経由地に移動する。
【００９４】
以上のように、この実施の形態１に係るカーナビゲーションシステムは、探索の起点となる現在地から終点までの直線距離が２ｋｍ以下の距離であって、且つ、起点から終点を見る目的地方角が９０度以上且つ２７０度以下である場合には、探索の終点が現在地の後方の至近距離に設定されたと判断している。これにより、カーナビゲーションシステムは、実際に探索の起点となる現在地から終点までの候補経路を探索する前に、簡単な演算処理により、探索の終点が現在地の後方の至近距離に設定されたか否かを判断することができる。
【００９５】
また、この実施の形態１に係るカーナビゲーションシステムは、探索の終点が現在地の後方の所定距離以下に設定された場合には、リンクデータ群２５およびノードデータ群２６に記憶されるリンクおよびノードのコスト情報をそのまま加算して、各候補経路のコストを計算する。つまり、コスト計算部４３は、各候補経路のコストを、道なり優先の条件下で計算しない。
【００９６】
したがって、カーナビゲーションシステムは、探索の終点が現在地の後方の所定距離以下に設定されたと判断した場合には、車両をＵターンさせる経路を案内経路４８として生成することが可能である。
【００９７】
その結果、カーナビゲーションシステムは、上述した条件に該当するようにＵターンした方が明らかに早く目的地３５に到達することができるような場合においては、道なり優先のコスト計算条件４６の下で探索した場合の案内経路４８に比べて目的地３５に早く到達することができる、そのＵターンをする経路を案内することができる。
【００９８】
また、この実施の形態１に係るカーナビゲーションシステムは、探索の終点が現在地の後方の所定距離以下に設定されたか否かを判断して、道なり優先係数をコスト計算に使用するか否かを制御している。コスト計算部４３は、設定された条件下で、各候補経路のコストを計算する。したがって、たとえば探索の終点が現在地の後方の至近距離に設定されたと判断した場合であっても、道なりに進んで目的地に向う経路が選択され得る。
【００９９】
なお、この実施の形態１では、経路探索の起点として現在地を使用している。探索の起点としては、現在地のほかにも、経由地などが出発地として選択されうる。カーナビゲーションシステムは、経由地などから目的地３５や他の経由地への経路を探索することもある。したがって、コスト計算条件設定部４１は、探索の起点から終点までの直線距離の判断に先立って、たとえば探索の起点が現在地であるか否かを判断し、探索の起点が現在地である場合において、探索の起点から終点までの直線距離の判断およびそれ以降の処理を実施するようにしてもよい。これにより、現在地からの経路探索と、経由地からの経路探索などとを区別して、たとえば現在地とは異なる場所である経由地から目的地３５までの直線距離が２ｋｍ以下であるような探索をする場合において、道なり優先を解除した探索条件下での経路探索をしてしまうことを予防することができる。
【０１００】
実施の形態２．
図８は、本発明の実施の形態２に係るカーナビゲーションシステムにおいて、案内経路の探索時に実現される機能を示すブロック図である。
【０１０１】
記憶デバイス１５に記憶されるコスト計算条件リスト７１は、渋滞係数、道なり優先係数、Ｕターン優先係数などの各種の係数を記憶する。
【０１０２】
Ｕターン優先とは、たとえば車両の進行方向や走行車線が予め判っている場合、その進行方向とは逆向きに進む道路あるいは車線が、その他の道路に比べて、案内経路４８として相対的に選択され易くすることである。Ｕターン優先係数は、その進行方向とは逆方向となるリンクのコスト情報に乗算される係数である。Ｕターン優先係数は、１より小さい値を有する。これにより、車両の進行方向とは逆方向への道路の通過コストを下げることができる。
【０１０３】
コスト計算条件設定部７２は、コスト計算条件リスト７１に基づいて、探索時の車両の状況などに応じたコスト計算条件４６を生成し、記憶デバイス１５に記憶させる。コスト計算条件４６は、たとえば、Ｕターン優先にて探索する状況下では、Ｕターン優先係数を有する。コスト計算条件設定部７２は、判断手段として機能する。
【０１０４】
コスト計算部７３は、候補経路リスト４７として記憶デバイス１５に記憶される各候補経路のコストを計算する。コスト計算部７３は、コスト計算手段として機能する。
【０１０５】
図８に示すこれ以外の構成要素は、実施の形態１に係る同名の構成要素と同じ機能を有するものであり、実施の形態１と同名の構成と同一の符号を付してその説明を省略する。また、実施の形態２に係るカーナビゲーションシステムにおいて、経路の案内時に実現される機能は、実施の形態１と同様であり、その説明を省略する。
【０１０６】
なお、このコスト計算条件設定部７２およびコスト計算部７３は、記憶デバイス１５に記憶される案内経路生成プログラムがＣＰＵ２に実行されることで、候補経路生成部４２および案内経路選択部４４とともに、実現される。
【０１０７】
次に、以上の構成を有する実施の形態２に係るカーナビゲーションシステムの動作を説明する。
【０１０８】
図９は、図８に示すカーナビゲーションシステムの経路探索時の動作を示すフローチャートである。
【０１０９】
タッチパネル１２などからの探索開始指示に基づいて探索の起点となる現在地および終点となる目的地３５を選択した後、コスト計算条件設定部７２は、コスト計算条件４６の設定を開始する。コスト計算条件設定部７２は、コスト計算条件リスト７１に記憶されている渋滞係数などを、コスト計算条件４６として記憶デバイス１５に記憶させる。
【０１１０】
コスト計算条件設定部７２は、探索の起点から終点までの直線距離が２ｋｍ以下か否かを判断し（ステップＳＴ１）、探索の起点から終点までの直線距離が２ｋｍより長い場合、コスト計算条件リスト７１に記憶されている道なり優先係数を、コスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２）。
【０１１１】
探索の起点から終点までの直線距離が２ｋｍ以下である場合、コスト計算条件設定部７２は、目的地方角が９０度から２７０度の範囲内か否かを判断し（ステップＳＴ３）、目的地方角が９０度より小さいか、もしくは、２７０度より大きい場合、道なり優先係数をコスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２）。
【０１１２】
目的地方角が９０度から２７０度の範囲内である場合、コスト計算条件設定部７２は、コスト計算条件リスト７１に記憶されているＵターン優先係数を、コスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ１１）。
【０１１３】
以上のコスト計算条件４６の設定処理により、図３（Ａ）のハッチングが施された部分内に目的地３５がある場合、コスト計算条件設定部７２は、コスト計算条件４６として、道なり優先係数を設定せずに、渋滞係数、Ｕターン優先係数を設定する。目的地３５がそれ以外の場所にある場合には、コスト計算条件設定部７２は、コスト計算条件４６として、渋滞係数、道なり優先係数を設定する。
【０１１４】
コスト計算条件４６の設定処理が終了すると、コスト計算条件設定部７２は、候補経路生成部４２に候補経路の生成を指示する。候補経路生成部４２は、リンクデータ群２５およびノードデータ群２６を使用して、候補経路を生成する（ステップＳＴ４）。記憶デバイス１５に候補経路が記憶されると、コスト計算部７３は、各候補経路のコストを計算する（ステップＳＴ５）。記憶デバイス１５に記憶される各候補経路のコストが計算されると、案内経路選択部４４は、その記憶デバイス１５に記憶される複数の候補経路（候補経路リスト４７）の中から、コストが最も低い候補経路を選択する（ステップＳＴ６）。案内経路選択部４４は、選択した１つの候補経路を、案内経路４８として記憶デバイス１５に記憶させる。
【０１１５】
ところで、コスト計算条件４６としてＵターン優先係数が設定されている場合、コスト計算部７３は、探索の起点および終点が図３（Ａ）の状態である場合において「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストを演算する際に、以下のように個別の通過コストを計算する。すなわち、コスト計算部７３は、リンクＬ６についてリンクデータ群に記憶されているコスト情報に、Ｕターン優先係数を乗算し、その演算結果をリンクＬ６の個別の通過コストとする。コスト計算部７３は、ノードＮ４についてノードデータ群に記憶されているコスト情報に、Ｕターン優先係数を乗算し、その演算結果をノードＮ４の個別の通過コストとする。コスト計算部７３は、リンクＬ５についてリンクデータ群に記憶されているコスト情報に、Ｕターン優先係数を乗算し、その演算結果をリンクＬ５の個別の通過コストとする。
【０１１６】
したがって、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストは、リンクデータ群２５およびノードデータ群２６に記憶されているコスト情報をそのままそれぞれの個別の通過コストとする場合にくらべて、小さくなる。そして、案内経路選択部４４は、この小さくなった「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストと、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストとを比較する。
【０１１７】
その結果、たとえばリンクデータ群２５およびノードデータ群２６に記憶されているコスト情報をそのまま個別の通過コストとして演算した場合には、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストが、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストより高くなる場合であったとしても、その「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストを下げて、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路が案内経路として選択され易くすることができる。
【０１１８】
以上のように、この実施の形態２に係るカーナビゲーションシステムは、探索の起点となる現在地から終点までの直線距離が２ｋｍ以下の距離であって、且つ、起点から終点を見る目的地方角が９０度以上且つ２７０度以下である場合には、探索の終点が現在地の後方の至近距離に設定されたと判断し、Ｕターン優先の条件下で各候補経路のコストを計算する。
【０１１９】
したがって、カーナビゲーションシステムは、探索の終点が現在地の後方の所定距離以下に設定されたと判断した場合には、車両をＵターンさせる経路のコストが他の経路のコストに比べて相対的に低くなり、その車両をＵターンさせる経路が案内経路４８として生成され易くなる。
【０１２０】
その結果、カーナビゲーションシステムは、上述した条件に該当するようにＵターンした方が明らかに早く目的地３５に到達することができるような場合においては、道なり優先のコスト計算条件４６の下で探索した場合の案内経路４８に比べて目的地３５に早く到達することができる、そのＵターンをする経路を案内することができる。
【０１２１】
実施の形態３．
図１０は、本発明の実施の形態３に係るカーナビゲーションシステムにおいて、案内経路の探索時に実現される機能を示すブロック図である。
【０１２２】
記憶デバイス１５に記憶されるコスト計算条件リスト８１は、渋滞係数、道なり優先係数、道なり劣後係数、などの各種の係数を記憶する。
【０１２３】
道なり劣後とは、たとえば車両の進行方向や走行車線が予め判っている場合、その進行方向へ進む道路あるいは車線が、その他の道路に比べて、案内経路４８として相対的に選択され難くすることである。道なり劣後係数は、その進行方向となるリンクのコスト情報に乗算される係数である。道なり劣後係数は、１より大きい値を有する。これにより、車両の進行方向への道路の通過コストを上げることができる。
【０１２４】
コスト計算条件設定部８２は、コスト計算条件リスト８１に基づいて、探索時の車両の状況などに応じたコスト計算条件４６を生成し、記憶デバイス１５に記憶させる。コスト計算条件４６は、たとえば、道なり劣後にて探索する状況下では、道なり劣後係数を有する。コスト計算条件設定部８２は、判断手段として機能する。
【０１２５】
コスト計算部８３は、候補経路リスト４７として記憶デバイス１５に記憶される各候補経路のコストを計算する。コスト計算部８３は、コスト計算手段として機能する。
【０１２６】
図８に示すこれ以外の構成要素は、実施の形態１に係る同名の構成要素と同じ機能を有するものであり、実施の形態１と同名の構成と同一の符号を付してその説明を省略する。また、実施の形態３に係るカーナビゲーションシステムにおいて、経路の案内時に実現される機能は、実施の形態１と同様であり、その説明を省略する。
【０１２７】
なお、このコスト計算条件設定部８２およびコスト計算部８３は、記憶デバイス１５に記憶される案内経路生成プログラムがＣＰＵ２に実行されることで、候補経路生成部４２および案内経路選択部４４とともに、実現される。
【０１２８】
次に、以上の構成を有する実施の形態３に係るカーナビゲーションシステムの動作を説明する。
【０１２９】
図１１は、図１０に示すカーナビゲーションシステムの経路探索時の動作を示すフローチャートである。
【０１３０】
タッチパネル１２などからの探索開始指示に基づいて探索の起点となる現在地および終点となる目的地３５を選択した後、コスト計算条件設定部８２は、コスト計算条件４６の設定を開始する。コスト計算条件設定部８２は、コスト計算条件リスト８１に記憶されている渋滞係数などを、コスト計算条件４６として記憶デバイス１５に記憶させる。
【０１３１】
コスト計算条件設定部８２は、探索の起点から終点までの直線距離が２ｋｍ以下か否かを判断し（ステップＳＴ１）、探索の起点から終点までの直線距離が２ｋｍより長い場合、コスト計算条件リスト８１に記憶されている道なり優先係数を、コスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２）。
【０１３２】
探索の起点から終点までの直線距離が２ｋｍ以下である場合、コスト計算条件設定部８２は、目的地方角が９０度から２７０度の範囲内か否かを判断し（ステップＳＴ３）、目的地方角が９０度より小さいか、もしくは、２７０度より大きい場合、道なり優先係数をコスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２）。
【０１３３】
目的地方角が９０度から２７０度の範囲内である場合、コスト計算条件設定部８２は、コスト計算条件リスト８１に記憶されている道なり劣後係数を、コスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２１）。
【０１３４】
以上のコスト計算条件４６の設定処理により、図３（Ａ）のハッチングが施された部分内に目的地３５がある場合、コスト計算条件設定部８２は、コスト計算条件４６として、道なり優先係数を設定せずに、渋滞係数、道なり劣後係数を設定する。目的地３５がそれ以外の場所にある場合には、コスト計算条件設定部８２は、コスト計算条件４６として、渋滞係数、道なり優先係数を設定する。
【０１３５】
コスト計算条件４６の設定処理が終了すると、コスト計算条件設定部８２は、候補経路生成部４２に候補経路の生成を指示する。候補経路生成部４２は、リンクデータ群２５およびノードデータ群２６を使用して、候補経路を生成する（ステップＳＴ４）。記憶デバイス１５に候補経路が記憶されると、コスト計算部８３は、各候補経路のコストを計算する（ステップＳＴ５）。記憶デバイス１５に記憶される各候補経路のコストが計算されると、案内経路選択部４４は、その記憶デバイス１５に記憶される複数の候補経路（候補経路リスト４７）の中から、コストが最も低い候補経路を選択する（ステップＳＴ６）。案内経路選択部４４は、選択した１つの候補経路を、案内経路４８として記憶デバイス１５に記憶させる。
【０１３６】
ところで、コスト計算条件４６として道なり劣後係数が設定されている場合、コスト計算部８３は、探索の起点および終点が図３（Ａ）の状態である場合において「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストを演算する際に、以下のように個別の通過コストを計算する。すなわち、コスト計算部８３は、各リンク（たとえばリンクＬ１）についてリンクデータ群に記憶されているコスト情報に、道なり劣後係数を乗算し、その演算結果をそのリンク（たとえばリンクＬ１）の個別の通過コストとする。コスト計算部８３は、各ノード（たとえばＮ１）についてノードデータ群に記憶されているコスト情報に、道なり劣後係数を乗算し、その演算結果をそのノード（たとえばＮ１）の個別の通過コストとする。
【０１３７】
したがって、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストは、リンクデータ群２５およびノードデータ群２６に記憶されているコスト情報をそのままそれぞれの個別の通過コストとする場合にくらべて、大きくなる。そして、案内経路選択部４４は、この大きくなった「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストと、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストと、を比較する。
【０１３８】
その結果、たとえばリンクデータ群２５およびノードデータ群２６に記憶されているコスト情報をそのまま個別の通過コストとして演算した場合には、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストが、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストより高くなる場合であったとしても、その「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストを上げて、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路が案内経路として選択され易くすることができる。
【０１３９】
以上のように、この実施の形態３に係るカーナビゲーションシステムは、探索の起点となる現在地から終点までの直線距離が２ｋｍ以下の距離であって、且つ、起点から終点を見る目的地方角が９０度以上且つ２７０度以下である場合には、探索の終点が現在地の後方の至近距離に設定されたと判断し、道なり劣後の条件下で各候補経路のコストを計算する。
【０１４０】
したがって、カーナビゲーションシステムは、探索の終点が現在地の後方の所定距離以下に設定されたと判断した場合には、道なりに進む経路のコストが他の経路のコストに比べて相対的に高くなり、車両をＵターンさせる経路は、その道なりに進む経路のコストに比べて相対的に低くなり、その車両をＵターンさせる経路が案内経路４８として生成され易くなる。
【０１４１】
その結果、カーナビゲーションシステムは、上述した条件に該当するようにＵターンした方が明らかに早く目的地３５に到達することができるような場合においては、道なり優先のコスト計算条件４６の下で探索した場合の案内経路４８に比べて目的地３５に早く到達することができる、そのＵターンをする経路を案内することができる。
【０１４２】
なお、この実施の形態３では、カーナビゲーションシステムは、探索の終点が現在地の後方の所定距離以下に設定されたと判断した場合には、道なりに進む経路のコストを、他の経路のコストに比べて相対的に高くしている。この他にもたとえば、探索の終点が現在地の後方の所定距離以下に設定されたと判断した場合には、カーナビゲーションシステムは、この実施の形態３のように道なりに進む経路のコストを、他の経路のコストに比べて相対的に高くするとともに、実施の形態２のように車両をＵターンさせる経路のコストを他の経路のコストに比べて相対的に低くするようにしてもよい。
【０１４３】
以上の各実施の形態は、本発明の好適な実施の形態の例であるが、本発明はこれに限定されるものではなく、発明の要旨を逸脱しない範囲において、種々の変形、変更が可能である。
【０１４４】
たとえば上記各実施の形態では、コスト計算条件設定部４１は、探索の起点から終点までの直線距離と目的地方角とに基づいて、目的地が現在地の後方の所定距離以下に設定されたか否かを判断し、コスト計算条件４６として設定する係数を選択している。この他にもたとえば、コスト計算条件設定部４１は、探索の起点から終点までの直線距離のみに基づいて、目的地が現在地の後方の所定距離以下に設定されたか否かを判断し、コスト計算条件４６として設定する係数を選択したりするようにしてもよい。また、コスト計算条件設定部４１は、直線距離ではなく、探索の起点から終点までの最短の経路における距離に基づいて、目的地が現在地の後方の所定距離以下に設定されたか否かを判断し、コスト計算条件４６として設定する係数を選択するようにしてもよい。
【０１４５】
上記各実施の形態では、コスト計算条件設定部４１は、探索の起点から終点までの直線距離が２ｋｍ以下か否かを判断して、コスト計算条件４６として設定する係数を選択している。この他にもたとえば、コスト計算条件設定部４１は、たとえば１ｋｍ以下か否かとか、５ｋｍ以下か否かとかの所定の任意の距離以下か否かに基づいて、目的地が現在地の後方の所定距離以下に設定されたか否かを判断し、コスト計算条件４６として設定する係数を選択するようにしてもよい。同様に、コスト計算条件設定部４１は、目的地方向が、たとえば１３５度から２２５度の範囲内か否かなどに基づいて、目的地が現在地の後方の所定距離以下に設定されたか否かを判断し、コスト計算条件４６として設定する係数を選択するようにしてもよい。
【０１４６】
この他にもたとえば、コスト計算条件設定部４１は、自車の後方となる道路およびその後方となる道路から所定の距離（たとえば１ｋｍなど）の範囲内に、目的地があるか否かを判断して、コスト計算条件４６として設定する係数を選択するようにしてもよい。自車の後方となる道路は、さらに現在地から所定の距離以下となる範囲内に制限するとよい。これらの場合、コスト計算条件設定部４１は、たとえば上述した範囲内に目的地がある場合に、目的地が現在地の後方の所定距離以下に設定されたと判断し、Ｕターン優先係数や道なり劣後係数を設定するようにすればよい。
【０１４７】
上記各実施の形態では、コスト計算条件設定部４１は、目的地が現在地の後方の至近距離に設定されたか否かのみを判断している。この他にもたとえば、コスト計算条件設定部４１は、探索の起点から終点までの直線距離あるいは目的地方向について複数段階にて判断し、その段階毎に、異なる値の係数を使い分けて設定するようにしてもよい。また、コスト計算条件設定部４１は、その段階毎に、たとえばＵターン優先係数と道なり劣後係数などの異なる種類の係数を切り替えて設定するようにしてもよい。同様に、目的地方角の大きさに応じて、その係数の値を変化させるようにしてもよい。たとえば、自車の進行方向から１８０度に近い領域の係数値を低くし、９０度または２７０度に近い領域の係数値を高く（＜＝１）するようにする。
【０１４８】
上記各実施の形態では、リンクあるいはノードごとに個別に係数を乗算し、それを加算することで候補経路のコストを計算している。この他にもたとえば、リンクデータ群およびノードデータ群のコスト情報のみに基づいて得られる経路全体のコストに、係数を乗算し、その演算結果を、候補経路のコストとして計算するようにしてもよい。
【０１４９】
上記各実施の形態では、コスト計算部４３，７３，８３は、各候補経路のコストを１つ計算している。この他にもたとえば、コスト計算部４３，７３，８３は、各候補経路について、複数のコストを計算するようにしてもよい。この場合、案内経路選択部４４は、各候補経路の複数のコストに基づいて総合的に判断し、最適と思われるものを案内経路として選択するようにすればよい。
【０１５０】
上記各実施の形態は、カーナビゲーションシステムに適用した場合の例である。この他にもたとえば、本発明は、歩行者、自転車などの経路を案内するナビゲーションシステムに適用することができる。また、ナビゲーションシステムは、携帯電話端末と、それと無線通信回線を介して接続されるナビゲーション用サーバとで構成されていてもよい。
【産業上の利用可能性】
【０１５１】
本発明は、カーナビゲーションシステムなどに利用することができる。
【図面の簡単な説明】
【０１５２】
【図１】図１は、本発明の実施の形態１に係るカーナビゲーションシステムを示す構成図である。
【図２】図２は、図１中の記憶デバイスの記憶内容を示す説明図である。
【図３】図３は、ある地域の道路と、リンクおよびノードとの関係を説明する図である。
【図４】図４は、図１中のＣＰＵが案内経路生成プログラムを実行することで、カーナビゲーションシステムに実現される経路探索時の機能を示すブロック図である。
【図５】図５は、図１中のＣＰＵが経路案内プログラムを実行することで、カーナビゲーションシステムに実現される経路案内時の機能を示すブロック図である。
【図６】図６は、図４に示すカーナビゲーションシステムの経路探索時の動作を示すフローチャートである。
【図７】図７は、図１中の液晶デバイスに表示される地図および案内経路の一例を示す表示画面である。
【図８】図８は、本発明の実施の形態２に係るカーナビゲーションシステムにおいて、経路探索時に実現される機能を示すブロック図である。
【図９】図９は、図８に示すカーナビゲーションシステムの経路探索時の動作を示すフローチャートである。
【図１０】図１０は、本発明の実施の形態３に係るカーナビゲーションシステムにおいて、経路探索時に実現される機能を示すブロック図である。
【図１１】図１１は、図１０に示すカーナビゲーションシステムの経路探索時の動作を示すフローチャートである。
【符号の説明】
【０１５３】
１５ 記憶デバイス（コスト情報記憶手段、優先係数記憶手段、劣後係数記憶手段）
３５ 目的地
４０ 現在位置マーク（現在地）
４１ コスト計算条件設定部（判断手段）
４３ コスト計算部（コスト計算手段）
４４ 案内経路選択部（選択手段）
５６ 経路案内部（経路案内手段）
７２ コスト計算条件設定部（判断手段）
７３ コスト計算部（コスト計算手段）
８２ コスト計算条件設定部（判断手段）
８３ コスト計算部（コスト計算手段）
【技術分野】
【０００１】
本発明は、案内経路探索装置および案内経路探索方法に関する。
【背景技術】
【０００２】
特許文献１は、車両用誘導装置を開示する。この車両用誘導装置は、経路探索時に車両が存在するリンクに対して、該経路探索時の該車両の進行方向と逆方向になるリンクが経路として選択されることを制限する。具体的には、Ｕターン側のリンクのコストに所定値を加算したり、係数を掛けたりする。
【０００３】
また、特許文献１は、リンクコストの変更値を適当な値に設定することにより、市街地等において、車両の進行方向側の次の交差点ノードまでの距離が非常に大きい場合、または進行方向が行き止まりになっているような場合には、Ｕターンをするリンクを含む経路のコストが相対的に低くなり、このＵターンをするリンクを含む経路が探索結果として得られるようにすることができるとしている。
【０００４】
【特許文献１】特開平８−１５９７９３号公報（特許請求の範囲、発明の詳細な説明、段落００３１、段落００３２など）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来の案内経路探索装置は、特許文献１に記載される従来の車両用誘導装置において経路探索時にはＵターン側のリンクのコストに所定値を加算したり、係数を掛けたりしているように、Ｕターン規制、道なり優先（自車の向き、すなわち進行方向前方のリンクなどのコストを下げる）などの条件の下で、探索された各候補経路のコストを計算し、そのコストが低いものを案内経路として選択している。
【０００６】
その結果、道なり優先の場合には、目的地が設定されると、自車の進行方向を判断し、その進行方向前方へ道なりに進んでから目的地へ向かう経路が選択され易くなる。別の言い方をすれば、現在地においてＵターンする経路が探索されずに済む。
【０００７】
しかしながら、このように道なり優先の条件が設定されている場合、たとえば現在地の後方の至近距離に目的地が設定され、明らかにＵターンなどをして目的地へ向うのが最も早い場合であっても、道なりに直進した後、その道を外れて目的地に向かう経路が、案内経路として選択されてしまう。
【０００８】
本発明は、現在地の後方の至近距離に目的地がある場合に、適切な経路が選択される案内経路探索装置および案内経路探索方法を得ることを目的とする。
【課題を解決するための手段】
【０００９】
本発明に係る案内経路探索装置は、経路探索の際に、現在地での進行方向前方のリンクおよび／またはノードのコスト情報の値を低くして進行方向前方のリンクおよび／またはノードを優先させる道なり優先制御を実行する案内経路探索装置において、起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、現在地の後方の所定距離以下であるか否かを判断する判断手段と、経路探索の起点から終点までの経路として選択されるリンクおよび／またはノードのコスト情報を記憶するコスト情報記憶手段と、判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、道なり優先制御を禁止し、コスト情報記憶手段に記憶されるリンクおよび／またはノードのコスト情報を用いて、探索された経路のコストを計算するコスト計算手段と、コスト計算手段により計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択する選択手段と、を有するものである。
【００１０】
本発明に係る他の案内経路探索装置は、経路探索の起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、現在地の後方の所定距離以下であるか否かを判断する判断手段と、経路探索の起点から終点までの経路として選択されるリンクおよび／またはノードのコスト情報を記憶するコスト情報記憶手段と、判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、コスト情報記憶手段に記憶される各リンクおよび／またはノードのコスト情報を用いて、進行方向前方へ進む経路より進行方向後方へ進む経路の方が選択され易くなるようにコスト情報を調整して、探索された経路のコストを計算するコスト計算手段と、コスト計算手段により計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択する選択手段と、を有するものである。
【００１１】
本発明に係る他の案内経路探索装置は、上述した発明の構成に加えて、コスト計算手段が、現在地から進行方向後方となるリンクおよび／またはノードのコスト情報として、コスト情報記憶手段に記憶されるそのリンクおよび／またはノードのコスト情報より小さな値を有するコスト情報を使用して、探索された経路のコストを計算し、選択手段が、コストが最も低い経路を案内経路として選択するものである。
【００１２】
本発明に係る他の案内経路探索装置は、上述した各発明の構成に加えて、コスト情報記憶手段に記憶されるリンクまたはノードのコスト情報から、現在地から進行方向後方となるリンクまたはノードのコスト情報を得る際に、コスト情報の値を小さくするＵターン優先係数を記憶する優先係数記憶手段を有し、コスト計算手段が、判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地から進行方向後方となるリンクおよび／またはノードについて、コスト情報記憶手段に記憶されるそのリンクおよび／またはノードのコスト情報にＵターン優先係数を適用したコスト情報を使用して、探索された経路のコストを計算し、選択手段が、コストが最も低い経路を案内経路として選択するものである。
【００１３】
本発明に係る他の案内経路探索装置は、上述した各発明の構成に加えて、コスト計算手段が、現在地から進行方向前方となるリンクおよび／またはノードのコスト情報として、コスト情報記憶手段に記憶されるそのリンクおよび／またはノードのコスト情報より大きな値を有するコスト情報を使用して、探索された経路のコストを計算し、選択手段が、コストが最も低い経路を案内経路として選択するものである。
【００１４】
本発明に係る他の案内経路探索装置は、上述した各発明の構成に加えて、コスト情報記憶手段に記憶されるリンクまたはノードのコスト情報から、現在地から進行方向前方となるリンクまたはノードのコスト情報を得る際に、コスト情報の値を大きくする道なり劣後係数を記憶する劣後係数記憶手段を有し、コスト計算手段が、判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地から進行方向前方となるリンクまたはノードについて、コスト情報記憶手段に記憶されるそのリンクまたはノードのコスト情報に道なり劣後係数を適用したコスト情報を使用して、探索された経路のコストを計算し、選択手段が、コストが最も低い経路を案内経路として選択するものである。
【００１５】
本発明に係る案内経路探索方法は、起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、現在地の後方の所定距離以下であるか否かを判断するステップと、経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地での進行方向前方のリンクおよび／またはノードのコスト情報の値を低くして進行方向前方のリンクおよび／またはノードを優先させる道なり優先制御を禁止し、コスト情報記憶手段に記憶されるリンクおよび／またはノードのコスト情報を用いて、探索された経路のコストを計算するステップと、計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択するステップと、を有するものである。
【００１６】
本発明に係る他の案内経路探索方法は、経路探索の起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、現在地の後方の所定距離以下であるか否かを判断するステップと、経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、コスト情報記憶手段に記憶されるリンクおよび／またはノードのコスト情報を用いて、進行方向前方へ進む経路より進行方向後方へ進む経路の方が選択され易くなるようにコスト情報を調整して、探索された経路のコストを計算するステップと、計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択するステップと、を有するものである。
【発明の効果】
【００１７】
本発明では、現在地の後方の至近距離に目的地がある場合に、適切な経路が選択される。
【発明を実施するための最良の形態】
【００１８】
以下、本発明の実施の形態に係る案内経路探索装置および案内経路探索方法を、図面に基づいて説明する。案内経路探索装置は、カーナビゲーションシステムの一部として説明する。案内経路探索方法は、カーナビゲーションシステムの動作の一部として説明する。
【００１９】
実施の形態１．
図１は、本発明の実施の形態１に係るカーナビゲーションシステムを示す構成図である。カーナビゲーションシステムは、現在地から、目的地あるいは経由地への車両の案内経路を探索し、その案内経路で車両が移動するように経路を案内するものである。
【００２０】
カーナビゲーションシステムは、メインコンピュータ１を有する。メインコンピュータ１は、プログラムを実行するＣＰＵ２（中央処理装置）と、ＣＰＵ２が実行しているプログラムやデータを記憶するＲＡＭ３（ランダムアクセスメモリ）と、周辺機器が接続される入出力ポート４と、これらを接続するシステムバス５と、を有する。
【００２１】
入出力ポート４には、液晶デバイス１１と、タッチパネル１２と、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）受信機１３と、ＶＩＣＳ（Ｖｅｈｉｃｌｅ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）受信機１４と、コスト情報記憶手段、優先係数記憶手段および劣後係数記憶手段としての記憶デバイス１５と、が接続される。
【００２２】
液晶デバイス１１は、液晶ディスプレイパネルなどといった表示部を有する。液晶デバイス１１は、表示データに基づき、表示部に画像を表示する。
【００２３】
タッチパネル１２は、透明なスクリーンを有する。透明なスクリーンは、液晶デバイス１１の表示部に重ねて配設される。タッチパネル１２は、透明なスクリーン内の指が触れた位置を検知し、検出した位置の位置情報を出力する。
【００２４】
ＧＰＳ受信機１３は、ＧＰＳ衛星からのＧＰＳ電波を受信する。ＧＰＳ電波は、ＧＰＳ衛星の位置情報と時間情報とを有する。ＧＰＳ受信機１３は、たとえば３つ以上のＧＰＳ衛星からのＧＰＳ電波を受信すると、それら複数のＧＰＳ衛星に対するＧＰＳ受信機１３の相対位置を演算し、その相対位置に基づいてＧＰＳ受信機１３の地球上の位置情報を生成する。地球上の位置情報は、たとえば世界測地系での緯度経度の値として表現される。ＧＰＳ受信機１３は、生成したＧＰＳ受信機１３の位置情報を出力する。
【００２５】
ＶＩＣＳ受信機１４は、電波ビーコン、光ビーコンあるいはＦＭ多重放送により送信される交通情報を受信する。交通情報には、道路の混雑度を示す渋滞情報や、道路の通行止め時間帯などを示す交通規制情報が含まれる。ＶＩＣＳ受信機１４は、受信した交通情報を出力する。
【００２６】
記憶デバイス１５は、たとえばハードディスクドライブなどにより構成される。図２は、図１中の記憶デバイス１５が記憶する内容を示す説明図である。記憶デバイス１５は、ナビゲーションプログラムと、ナビゲーションデータとを記憶する。ナビゲーションプログラムは、案内経路生成プログラム２１と、経路案内プログラム２２と、を有する。ナビゲーションデータは、地点データ群２４と、リンクデータ群２５と、ノードデータ群２６２６と、コスト計算条件リスト２７と、地図データ２８と、を有する。
【００２７】
なお、記憶デバイス１５に記憶されるナビゲーションプログラムとナビゲーションデータとは、たとえばＤＶＤ（デジタル・バーサタイル・ディスク）−ＲＯＭ（リード・オンリィ・メモリ）などのコンピュータ読み取り可能な記録媒体や伝送媒体を介して、記憶デバイス１５に保存されるようにしてもよい。また、ナビゲーションプログラムとナビゲーションデータとは、コンピュータ読み取り可能な記録媒体に記憶されていてもよい。この場合、記憶デバイス１５は、この記録媒体のデータを読み取るドライブなどにより構成される。
【００２８】
地点データ群２４は、複数のレコードを有する。地点データ群２４の各レコードは、１つの地点のデータを有する。各レコードは、その地点にある建物、店舗、施設などの名称、その地点の位置情報などを有する。地点データ群２４の複数の地点は、目的地３５、経由地あるいは出発地などとして選択可能な地点である。
【００２９】
リンクデータ群２５およびノードデータ群２６は、カーナビゲーションシステムが、車両の経路探索や経路案内において使用するデータである。車両は、道路を移動する。道路には、交差点などの道路の分岐点がある。ナビゲーションシステムでは、この道路の分岐点などをノードとして取り扱う。２つの分岐点の間の道路などをリンクとして取り扱う。リンクの両端は、ノードに接続される。ノードには、１つ以上のリンクが接続される。
【００３０】
図３は、ある地域の道路と、リンクおよびノードとの関係を説明する図である。図３（Ａ）は、ある地域の道路を示す図である。図３（Ｂ）は、その地域に対応付けられるノードおよびリンクを示す図である。図３（Ｂ）において、各ノードは、四角形で示され、リンクは、矢印で示される。
【００３１】
図３（Ａ）に示す地域には、第一の国道３１と、第一の地方道３２とが、図の横方向に沿って並行に通っている。また、第二の国道３３と、第二の地方道３４とが、図の縦に通っている。第二の国道３３は、第一の国道３１と、第一の地方道３２と交差する。第二の地方道３４は、第一の地方道３２と交差し、第一の国道３１につきあたる。
【００３２】
このような地域の道路は、図３（Ｂ）に示すように、複数のリンクおよび複数のノードとしてデータ化される。ノードは、第二の国道３３と第一の国道３１との交差点３６、第二の国道３３と第一の地方道３２との交差点３７、第二の地方道３４と第一の国道３１との交差点（第二の地方道３４のつきあたり）３８、および、第二の地方道３４と第一の地方道３２との交差点３９に対応付けて設けられる。この地域のノードは、合計４つになる。
【００３３】
また、このような地域の道路と対応づけて、リンクは、交差点と交差点との間の区間毎に設けられる。具体的には、図の横方向に沿う第一の国道３１は、２つのノードを有する。したがって、この片側二車線（計４車線）の道路は、６本のリンクで構成される。同様に、第一の地方道３２は、６本のリンクで構成される。第二の国道３３は、６本のリンクで構成される。第二の地方道３４は、４本のリンクで構成される。この地域のリンクは、合計２２本となる。
【００３４】
リンクデータ群２５は、複数のレコードを有する。リンクデータ群２５の各レコードは、１つのリンクのデータを有する。各レコードは、そのリンクに関する交通規制情報や、そのリンクの距離、そのリンクを通過するコスト情報、そのリンクに固有の識別番号、そのリンクが接続されるノードの識別番号などを有する。リンクに関する交通規制情報には、たとえば、一方通行路、時間帯通行禁止、右折禁止、Ｕターン禁止、道幅（幅員）などの情報がある。なお、各レコードには、１つのリンクではなく、１つの道路のすべてのリンクが対応付けられていてもよい。
【００３５】
ノードデータ群２６は、複数のレコードを有する。ノードデータ群２６の各レコードは、１つのノードのデータを有する。各レコードは、そのノードの位置情報、そのノードに関する交通規制情報、そのノードを通過するコスト情報、そのノードに固有の識別番号、そのノードに接続されるリンクの識別番号などを有する。ノードに関する交通規制情報としては、たとえば、信号機の有無、右折禁止、Ｕターン禁止などの情報がある。
【００３６】
ノードを通過するコスト情報およびリンクを通過するコスト情報は、それらの通過し易さあるいは通過し難さに応じた値を有する。これらのコスト情報は、通過し難いほど大きな値を有する。
【００３７】
なお、実際に演算に使用するコスト情報そのものは、記憶デバイス１５においてたとえば道路種別などと対応付けて記憶され、これらノードデータ群２６およびリンクデータ群２５の各レコードは、この種別の指定情報を有するデータ構造になっていてもよい。また、コスト情報の値は、通過し易さのみに応じた値ではなく、たとえば、道路の有料無料に応じた値、道路の走りやすさに応じた値、道路の景観の良否に応じた値、道路の交通量に応じた値、あるいはそれらを組み合わせた値などになっていてもよい。
【００３８】
図２に戻り、記憶デバイス１５に記憶されるコスト計算条件リスト２７は、経路のコストを計算するときの計算条件を有する。具体的にはたとえば、コスト計算条件リスト２７は、渋滞係数、道なり優先係数などの各種の係数を記憶する。
【００３９】
渋滞係数は、渋滞しているリンクおよびノードのコスト情報に乗算される係数である。道なり優先係数は、１より大きい値を有する。これにより、渋滞しているリンクおよびノードの通過コストを上げることができる。
【００４０】
道なり優先とは、たとえば車両の進行方向や走行車線が予め判っている場合、その進行方向の道路あるいは車線が、その他の道路に比べて、案内経路として相対的に選択され易くすることである。道なり優先係数は、その道なりのリンクのコスト情報に乗算される係数である。道なり優先係数は、１より小さい値を有する。これにより、車両の進行方向の道路の通過コストを下げることができる。
【００４１】
地図データ２８は、液晶ディスプレイに地図を表示するために使用するデータである。このような地図データ２８としては、たとえば、二次元あるいは三次元のベクトル地図データ２８がある。ベクトル地図データ２８は、地図の背景画像となる背景データと、その背景画像の上に描画されるベクトルデータと、を有する。背景画像は、たとえば公園、河川、池などを色分けした画像データである。ベクトルデータは、たとえば道路毎の描画データである。なお、地図データ２８は、この他にも、ランドマーク用の三次元のポリゴンデータや、各地点に対応付けられたアイコンデータなどを備えていてもよい。
【００４２】
案内経路生成プログラム２１は、ＣＰＵ２に実行されることで、メインコンピュータ１に、案内経路を生成するための各種の機能を実現する。図４は、図１中のＣＰＵ２が案内経路生成プログラム２１を実行することで、カーナビゲーションシステムに実現される機能を示すブロック図である。図１中のＣＰＵ２が案内経路生成プログラム２１を実行することで、判断手段としてのコスト計算条件設定部４１と、候補経路生成部４２と、コスト計算手段としてのコスト計算部４３と、選択手段としての案内経路選択部４４と、が実現される。
【００４３】
コスト計算条件設定部４１は、コスト計算条件リスト２７に基づいて、探索時の車両の状況などに応じたコスト計算条件４６を生成し、記憶デバイス１５に記憶させる。コスト計算条件４６は、たとえば、道なり優先にて探索する状況下では、道なり優先係数を有する。
【００４４】
候補経路生成部４２は、リンクデータ群２５およびノードデータ群２６を使用して、探索の起点から終点までの経路を探索し、記憶デバイス１５に記憶させる。探索した経路は、探索の起点と終点とを１または複数のリンクおよびノードで繋いだものとなる。候補経路生成部４２は、その探索した経路のデータを、候補経路として記憶デバイス１５に記憶させる。複数の候補経路により、記憶デバイス１５には、候補経路リスト４７が記憶される。なお、車両の現在地あるいは出発地などが、経路探索の起点として利用される。目的地３５あるいは経由地などが、経路探索の終点として利用される。
【００４５】
コスト計算部４３は、候補経路生成部４２により探索された候補経路のコストを計算する。
【００４６】
案内経路選択部４４は、コストが最も低い候補経路を案内経路４８として選択し、記憶デバイス１５に記憶させる。
【００４７】
経路案内プログラム２２は、ＣＰＵ２に実行されることで、メインコンピュータ１に、経路を案内するための各種の機能を実現する。図５は、図１中のＣＰＵ２が経路案内プログラム２２を実行することで、カーナビゲーションシステムに実現される機能を示すブロック図である。図１中のＣＰＵ２が経路案内プログラム２２を実行することで、経路案内手段としての経路案内部５６が実現される。
【００４８】
経路案内部５６は、記憶デバイス１５に記憶されている案内経路４８および地図データ２８を読み込み、これらを用いて、液晶デバイス１１に案内経路４８および現在地の周辺地図などを表示させる。なお、経路案内部５６は、必要に応じて図示外のスピーカから音声案内を出力させるようにしてもよい。
【００４９】
次に、以上の構成を有する実施の形態１に係るカーナビゲーションシステムの動作を説明する。まず、図４を参照しながら、案内経路４８の探索処理について説明する。
【００５０】
また、以下の説明では、案内経路４８の生成処理の具体例として、図３（Ａ）において自車位置マーク４０にて示すように、車両は、第二の国道３３と第二の地方道３４との間において、第一の国道３１を走行しているものとする。この自車位置マーク４０がある場所が現在地となる。
【００５１】
また、目的地３５が、この第一の国道３１において、車両の走行方向後方で且つ２ｋｍ以内の距離に設定された場合を例として説明する。目的地３５は、たとえば地点データを液晶デバイス１１に表示し、その表示においてタッチパネル１２が出力する操作位置情報に基づいて選択した地点を、目的地３５として設定すればよい。
【００５２】
自車位置マーク４０（現在地）の位置情報４９および目的地３５の位置情報５０は、記憶デバイス１５に記憶される。
【００５３】
また、記憶デバイス１５には、自車位置マーク４０（現在地）の位置情報４９および目的地３５の位置情報５０のほかにも、ＶＩＣＳ受信機１４が受信した交通情報に含まれる渋滞情報あるいは交通規制情報（渋滞・交通規制情報５１）が記憶されているものとする。
【００５４】
なお、経路探索における自車の現在地の位置情報４９としては、たとえばＧＰＳ受信機１３が生成したＧＰＳ受信機１３の位置情報が使用できる。自車の現在地としては、他にもたとえば、ＧＰＳ受信機１３の位置情報に基づいて特定されるリンク上の位置であってもよい。この場合、自車の現在地は、たとえば、ＧＰＳ受信機１３の位置情報からそのリンクへ垂線を下ろしたときのその垂線とリンクとが交差する地点が、自車の現在地となる。このように自車が存在しているリンクが特定されている場合、図３（Ｂ）に示すように、自車位置マーク４０は、このマッチングしているリンク上の当該地点に表示されることになる。
【００５５】
図６は、図４に示すカーナビゲーションシステムの経路探索時の動作を示すフローチャートである。
【００５６】
タッチパネル１２などから、目的地３５の選択などに伴って探索開始指示があると、コスト計算条件設定部４１は、コスト計算条件４６の設定処理を開始する。コスト計算条件設定部４１は、まず、探索の起点として、記憶デバイス１５に記憶されている現在地を選択するとともに、探索の終点として記憶デバイス１５に記憶されている目的地３５あるいは経由地を選択する。
【００５７】
探索の起点および終点を選択すると、コスト計算条件設定部４１は、経路探索条件の設定を開始する。コスト計算条件設定部４１は、コスト計算条件リスト２７に記憶されている渋滞係数などを、コスト計算条件４６として記憶デバイス１５に記憶させる。
【００５８】
コスト計算条件設定部４１は、また、探索の起点から終点までの直線距離を演算する。コスト計算条件設定部４１は、探索の起点から終点までの直線距離が２ｋｍ以下か否かを判断する（ステップＳＴ１）。
【００５９】
探索の起点から終点までの直線距離が２ｋｍより長い場合、コスト計算条件設定部４１は、コスト計算条件リスト２７から道なり優先係数を読み込み、読み込んだ道なり優先係数をコスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２）。
【００６０】
探索の起点から終点までの直線距離が２ｋｍ以下である場合、コスト計算条件設定部４１は、自車の進行方向を基準として、探索の起点から目的地３５を見た方向の角度（以下、目的地方角とよぶ。）を計算する。自車の進行方向としては、停車時の進行方向であっても、その時のＧＰＳ受信機１３からの位置情報に基づいて特定される方向であっても、自車がマッチングしているリンクの方向であってもよい。そして、コスト計算条件設定部４１は、目的地方角が９０度から２７０度の範囲内か否かを判断する（ステップＳＴ３）。
【００６１】
目的地方角が９０度より小さいか、もしくは、２７０度より大きい場合、コスト計算条件設定部４１は、コスト計算条件リスト２７から道なり優先係数を読み込み、読み込んだ道なり優先係数をコスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２）。
【００６２】
以上のコスト計算条件４６の設定処理により、記憶デバイス１５には、道なり優先係数などの各種の係数がコスト計算条件４６として記憶される。自車の現在位置から目的地３５までの距離が２ｋｍ以下であって、且つ、目的地方角が９０度以上且つ２７０度以下である場合には、道なり優先係数は、コスト計算条件４６として設定されない。探索の起点と終点との位置関係がこれ以外の位置関係の場合には、道なり優先係数は、コスト計算条件４６として設定される。
【００６３】
たとえば、図３（Ａ）では、半円のハッチングが施された部分が、自車の現在位置から２ｋｍ以下の距離であって、且つ、目的地方角が９０度以上且つ２７０度以下となる区域となる。図３（Ａ）の目的地３５は、この半円のハッチングが施された部分内にある。この場合、コスト計算条件設定部４１は、道なり優先係数を、コスト計算条件４６として設定しない。
【００６４】
コスト計算条件４６の設定処理が終了すると、コスト計算条件設定部４１は、候補経路生成部４２に候補経路の生成を指示する。
【００６５】
なお、コスト計算条件設定部４１は、コスト計算条件４６の設定処理の開始前に、候補経路生成部４２に候補経路の生成を指示するようにしてもよい。コスト計算条件設定部４１は、たとえばＶＩＣＳ受信機１４からの渋滞情報受信に伴う探索開始指示などがあった場合などには、コスト計算条件４６の設定処理をすることなく、候補経路生成部４２に候補経路の生成を指示するようにしてもよい。コスト計算条件設定部４１は、ＧＰＳ受信機１３からの位置情報の変化が少ないことなどを検出し、コスト計算条件４６の設定処理をすることなく、自発的に候補経路生成部４２に候補経路の生成を指示するようにしてもよい。
【００６６】
候補経路生成部４２は、リンクデータ群２５およびノードデータ群２６を使用して、候補経路を生成する（ステップＳＴ４）。具体的には、候補経路生成部４２は、ノードの位置情報やリンクのノードに対する接続情報を用いてリンクをノードに繋ぎ、探索の起点から終点までのリンクの鎖を生成する。候補経路生成部４２は、この探索の起点から終点までのリンクの鎖を、候補経路として生成する。
【００６７】
探索の起点（現在地）４０と終点（目的地３５）とが図３（Ａ）に示すような位置関係にある場合、候補経路生成部４２は、たとえば、自車がマップマッチングしているリンクＬ１を最初のリンクとして、図３（Ｂ）に示すように、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路を生成する。この候補経路は、自車の進行方向へ真直に進んでから、終点に向かう経路である。この候補経路は、その途中においてＵターンすることはない。
【００６８】
また、候補経路生成部４２は、たとえば、自車がマップマッチングしているリンクと同一道路上の反対車線のリンクＬ６を最初のリンクとして、図３（Ｂ）に示すように、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路を生成する。この候補経路は、自車の現在地においてＵターンしてから、終点に向かう経路である。
【００６９】
この候補経路の生成処理において、候補経路生成部４２は、リンクデータ群２５、ノードデータ群２６、渋滞・交通規制情報５１などの情報を参照し、走行可能な経路を探索する。たとえば、仮に図３（Ａ）の第一の国道３１においてＵターン禁止や交差点以外での右折禁止などの交通規制情報がある場合、候補経路生成部４２は、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路は生成しない。他にもたとえば、仮に第二の地方道３４において交差点３８での右折禁止時間帯があり、その時間帯に該当するときには、候補経路生成部４２は、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路を生成しない。
【００７０】
候補経路生成部４２は、生成した候補経路を記憶デバイス１５に記憶させる。これにより、記憶デバイス１５には、候補経路リスト４７が記憶される。
【００７１】
記憶デバイス１５に候補経路が記憶されると、コスト計算部４３は、各候補経路のコストを計算する（ステップＳＴ５）。
【００７２】
コスト計算部４３は、まず、候補経路に含まれる各リンクおよび各ノードについて、１つ１つの個別の通過コストを計算する。
【００７３】
このとき、コスト計算条件４６にたとえば道なり優先係数が設定されている場合、コスト計算部４３は、その条件に該当するリンクあるいはノードのリンクデータ群２５あるいはノードデータ群２６におけるコスト情報に、その係数を乗算し、その演算結果を当該リンクあるいはノードの個別の通過コストとする。これにより、道なりに該当する道路の通過コストは低くなる。
【００７４】
また、渋滞・交通規制情報５１において渋滞が発生している道路のリンクについては、コスト計算部４３は、そのリンクについて渋滞係数を乗算する。渋滞係数は、１以上の係数である。これにより、渋滞している経路の通過コストは高くなる。
【００７５】
コスト計算条件４６に係数が設定されていないリンクおよびノードについては、コスト計算部４３は、そのリンクあるいはノードのリンクデータ群２５あるいはノードデータ群２６におけるコスト情報をそのまま、そのリンクあるいはノードの個別の通過コストとする。
【００７６】
候補経路に含まれるすべてのリンクおよびすべてのノードの個別の通過コストを計算したら、コスト計算部４３は、そのすべての個別の通過コストを加算し、その演算結果をその候補経路のコストとする。なお、コスト計算部４３は、リンクあるいはノード毎の個別の通過コストを乗算したり、所定の演算式にて計算したりすることで、候補経路のコストを計算するようにしてもよい。
【００７７】
具体的にはたとえば、先の「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路の場合、コスト計算部４３は、リンクＬ１、ノードＮ１、リンクＬ２、ノードＮ２、リンクＬ３、ノードＮ３、リンクＬ４、ノードＮ４およびリンクＬ５のそれぞれの個別の通過コストを計算し、それらを加算した値を、候補経路のコストとして計算する。
【００７８】
また、図３（Ａ）の場合、半円のハッチング内に目的地３５がある。そのため、コスト計算条件４６として、道なり優先係数が設定されていない。したがって、コスト計算部４３は、リンクＬ１およびノードＮ１の個別の通過コストとして、リンクデータ群２５およびノードデータ群２６に記憶されるそれぞれのコスト情報をそのまま、そのリンクあるいはノードの個別の通過コストとして使用して、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストを計算する。
【００７９】
他にもたとえば、コスト計算部４３は、リンクＬ６、ノードＮ４およびリンクＬ５のそれぞれの個別の通過コストを計算し、それを加算して「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストとして計算する。
【００８０】
記憶デバイス１５に記憶される各候補経路のコストが計算されると、案内経路選択部４４は、その記憶デバイス１５に記憶される複数の候補経路（候補経路リスト４７）の中から、コストが最も低い候補経路を選択する（ステップＳＴ６）。
【００８１】
図３（Ａ）の場合、半円のハッチング内に目的地３５がある。そのため、コスト計算条件４６として、道なり優先係数が設定されずに、各候補経路のコストが計算される。したがって、案内経路選択部４４は、リンクデータ群２５およびノードデータ群２６のコスト情報に基づいて生成した「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストと、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストと、を比較する。
【００８２】
「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストは、コスト計算条件４６において道なり優先係数などが設定されていない限り、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストより低い。したがって、案内経路選択部４４は、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路を、案内経路４８として選択する。
【００８３】
案内経路選択部４４は、選択した１つの候補経路を、案内経路４８として記憶デバイス１５に記憶させる。
【００８４】
以上の案内経路４８の探索処理により、記憶デバイス１５には、探索の起点から終点までの案内経路４８が記憶される。図３（Ａ）の場合には、案内経路４８として「起点→Ｌ６→Ｎ４→Ｌ５→終点」という経路が記憶デバイス１５に記憶される。この「起点→Ｌ６→Ｎ４→Ｌ５→終点」という経路は、自車の現在地においてＵターンしてから、終点に向かう経路である。
【００８５】
なお、仮に図３の目的地３５が半円の外側に位置している場合、コスト計算条件４６として道なり優先係数が設定されることで、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストが「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストより高くなる場合、記憶デバイス１５には、案内経路４８として「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という経路が記憶される。この経路は、自車の現在地から進行方向に直進してから、Ｕターンすることなく、終点に向かう経路である。
【００８６】
次に、図５を参照しながら、案内経路４８を用いた経路案内について説明する。
【００８７】
経路案内部５６は、ＧＰＳ受信機１３からの位置情報を読み込む。経路案内部５６は、ＧＰＳ受信機１３からの位置情報を自車の位置情報として、自車の周辺の案内経路４８および地図データ２８を記憶デバイス１５から読み込む。経路案内部５６は、読み込んだ案内経路４８および地図データ２８から表示データを生成する。経路案内部５６は、自車位置マーク４０を含む表示データを生成する。経路案内部５６は、生成した表示データを液晶デバイス１１へ出力する。液晶デバイス１１は、表示データに基づき、表示部に地図および案内経路４８を表示する。
【００８８】
図７は、液晶デバイス１１に表示される地図および案内経路の一例を示す表示画面である。表示画面には、自車位置マーク４０と、案内する経路と、地図と、目的地３５とが表示される。さらに、液晶デバイス１１には、自車位置マーク４０のある現在地からＵターンして目的地３５へ向かう案内経路６１が表示される。
【００８９】
経路案内部５６は、周期的に、ＧＰＳ受信機１３からの位置情報を読み込む。経路案内部５６は、ＧＰＳ受信機１３からの位置情報により特定される自車の位置が、液晶デバイス１１に表示させている自車位置マーク４０の位置から移動したか否かを判断する。
【００９０】
自車の位置が移動したと判断したら、経路案内部５６は、その新たな自車の位置を基準として、自車の周辺の案内経路４８および地図データ２８を記憶デバイス１５から読み込み、表示データを生成する。液晶デバイス１１は、経路案内部５６により生成された表示データを表示する。
【００９１】
なお、仮に、先の「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という経路が案内経路である場合、図７の点線で示す経路６２が案内経路として表示される。
【００９２】
また、経路案内部５６は、ＧＰＳ受信機１３からの位置情報を読み込んだら、自車位置の移動を判断することなく、新たな表示データを生成するようにしてもよい。経路案内部５６は、図示外のジャイロセンサからの移動量および移動方向に関する情報に基づいて、自車の現在地を判断するようにしてもよい。
【００９３】
このように、経路案内において、カーナビゲーションシステムは、ＧＰＳ受信機１３からの位置情報を自車の位置情報として用い、その自車の位置の周辺の地図および案内経路４８を、液晶デバイス１１に表示し続ける。したがって、車両の運転手が、液晶デバイス１１に表示される案内経路４８にそって自車位置マーク４０が移動するように車両を運転することで、車両は、現在地などから目的地３５あるいは経由地に移動する。
【００９４】
以上のように、この実施の形態１に係るカーナビゲーションシステムは、探索の起点となる現在地から終点までの直線距離が２ｋｍ以下の距離であって、且つ、起点から終点を見る目的地方角が９０度以上且つ２７０度以下である場合には、探索の終点が現在地の後方の至近距離に設定されたと判断している。これにより、カーナビゲーションシステムは、実際に探索の起点となる現在地から終点までの候補経路を探索する前に、簡単な演算処理により、探索の終点が現在地の後方の至近距離に設定されたか否かを判断することができる。
【００９５】
また、この実施の形態１に係るカーナビゲーションシステムは、探索の終点が現在地の後方の所定距離以下に設定された場合には、リンクデータ群２５およびノードデータ群２６に記憶されるリンクおよびノードのコスト情報をそのまま加算して、各候補経路のコストを計算する。つまり、コスト計算部４３は、各候補経路のコストを、道なり優先の条件下で計算しない。
【００９６】
したがって、カーナビゲーションシステムは、探索の終点が現在地の後方の所定距離以下に設定されたと判断した場合には、車両をＵターンさせる経路を案内経路４８として生成することが可能である。
【００９７】
その結果、カーナビゲーションシステムは、上述した条件に該当するようにＵターンした方が明らかに早く目的地３５に到達することができるような場合においては、道なり優先のコスト計算条件４６の下で探索した場合の案内経路４８に比べて目的地３５に早く到達することができる、そのＵターンをする経路を案内することができる。
【００９８】
また、この実施の形態１に係るカーナビゲーションシステムは、探索の終点が現在地の後方の所定距離以下に設定されたか否かを判断して、道なり優先係数をコスト計算に使用するか否かを制御している。コスト計算部４３は、設定された条件下で、各候補経路のコストを計算する。したがって、たとえば探索の終点が現在地の後方の至近距離に設定されたと判断した場合であっても、道なりに進んで目的地に向う経路が選択され得る。
【００９９】
なお、この実施の形態１では、経路探索の起点として現在地を使用している。探索の起点としては、現在地のほかにも、経由地などが出発地として選択されうる。カーナビゲーションシステムは、経由地などから目的地３５や他の経由地への経路を探索することもある。したがって、コスト計算条件設定部４１は、探索の起点から終点までの直線距離の判断に先立って、たとえば探索の起点が現在地であるか否かを判断し、探索の起点が現在地である場合において、探索の起点から終点までの直線距離の判断およびそれ以降の処理を実施するようにしてもよい。これにより、現在地からの経路探索と、経由地からの経路探索などとを区別して、たとえば現在地とは異なる場所である経由地から目的地３５までの直線距離が２ｋｍ以下であるような探索をする場合において、道なり優先を解除した探索条件下での経路探索をしてしまうことを予防することができる。
【０１００】
実施の形態２．
図８は、本発明の実施の形態２に係るカーナビゲーションシステムにおいて、案内経路の探索時に実現される機能を示すブロック図である。
【０１０１】
記憶デバイス１５に記憶されるコスト計算条件リスト７１は、渋滞係数、道なり優先係数、Ｕターン優先係数などの各種の係数を記憶する。
【０１０２】
Ｕターン優先とは、たとえば車両の進行方向や走行車線が予め判っている場合、その進行方向とは逆向きに進む道路あるいは車線が、その他の道路に比べて、案内経路４８として相対的に選択され易くすることである。Ｕターン優先係数は、その進行方向とは逆方向となるリンクのコスト情報に乗算される係数である。Ｕターン優先係数は、１より小さい値を有する。これにより、車両の進行方向とは逆方向への道路の通過コストを下げることができる。
【０１０３】
コスト計算条件設定部７２は、コスト計算条件リスト７１に基づいて、探索時の車両の状況などに応じたコスト計算条件４６を生成し、記憶デバイス１５に記憶させる。コスト計算条件４６は、たとえば、Ｕターン優先にて探索する状況下では、Ｕターン優先係数を有する。コスト計算条件設定部７２は、判断手段として機能する。
【０１０４】
コスト計算部７３は、候補経路リスト４７として記憶デバイス１５に記憶される各候補経路のコストを計算する。コスト計算部７３は、コスト計算手段として機能する。
【０１０５】
図８に示すこれ以外の構成要素は、実施の形態１に係る同名の構成要素と同じ機能を有するものであり、実施の形態１と同名の構成と同一の符号を付してその説明を省略する。また、実施の形態２に係るカーナビゲーションシステムにおいて、経路の案内時に実現される機能は、実施の形態１と同様であり、その説明を省略する。
【０１０６】
なお、このコスト計算条件設定部７２およびコスト計算部７３は、記憶デバイス１５に記憶される案内経路生成プログラムがＣＰＵ２に実行されることで、候補経路生成部４２および案内経路選択部４４とともに、実現される。
【０１０７】
次に、以上の構成を有する実施の形態２に係るカーナビゲーションシステムの動作を説明する。
【０１０８】
図９は、図８に示すカーナビゲーションシステムの経路探索時の動作を示すフローチャートである。
【０１０９】
タッチパネル１２などからの探索開始指示に基づいて探索の起点となる現在地および終点となる目的地３５を選択した後、コスト計算条件設定部７２は、コスト計算条件４６の設定を開始する。コスト計算条件設定部７２は、コスト計算条件リスト７１に記憶されている渋滞係数などを、コスト計算条件４６として記憶デバイス１５に記憶させる。
【０１１０】
コスト計算条件設定部７２は、探索の起点から終点までの直線距離が２ｋｍ以下か否かを判断し（ステップＳＴ１）、探索の起点から終点までの直線距離が２ｋｍより長い場合、コスト計算条件リスト７１に記憶されている道なり優先係数を、コスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２）。
【０１１１】
探索の起点から終点までの直線距離が２ｋｍ以下である場合、コスト計算条件設定部７２は、目的地方角が９０度から２７０度の範囲内か否かを判断し（ステップＳＴ３）、目的地方角が９０度より小さいか、もしくは、２７０度より大きい場合、道なり優先係数をコスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２）。
【０１１２】
目的地方角が９０度から２７０度の範囲内である場合、コスト計算条件設定部７２は、コスト計算条件リスト７１に記憶されているＵターン優先係数を、コスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ１１）。
【０１１３】
以上のコスト計算条件４６の設定処理により、図３（Ａ）のハッチングが施された部分内に目的地３５がある場合、コスト計算条件設定部７２は、コスト計算条件４６として、道なり優先係数を設定せずに、渋滞係数、Ｕターン優先係数を設定する。目的地３５がそれ以外の場所にある場合には、コスト計算条件設定部７２は、コスト計算条件４６として、渋滞係数、道なり優先係数を設定する。
【０１１４】
コスト計算条件４６の設定処理が終了すると、コスト計算条件設定部７２は、候補経路生成部４２に候補経路の生成を指示する。候補経路生成部４２は、リンクデータ群２５およびノードデータ群２６を使用して、候補経路を生成する（ステップＳＴ４）。記憶デバイス１５に候補経路が記憶されると、コスト計算部７３は、各候補経路のコストを計算する（ステップＳＴ５）。記憶デバイス１５に記憶される各候補経路のコストが計算されると、案内経路選択部４４は、その記憶デバイス１５に記憶される複数の候補経路（候補経路リスト４７）の中から、コストが最も低い候補経路を選択する（ステップＳＴ６）。案内経路選択部４４は、選択した１つの候補経路を、案内経路４８として記憶デバイス１５に記憶させる。
【０１１５】
ところで、コスト計算条件４６としてＵターン優先係数が設定されている場合、コスト計算部７３は、探索の起点および終点が図３（Ａ）の状態である場合において「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストを演算する際に、以下のように個別の通過コストを計算する。すなわち、コスト計算部７３は、リンクＬ６についてリンクデータ群に記憶されているコスト情報に、Ｕターン優先係数を乗算し、その演算結果をリンクＬ６の個別の通過コストとする。コスト計算部７３は、ノードＮ４についてノードデータ群に記憶されているコスト情報に、Ｕターン優先係数を乗算し、その演算結果をノードＮ４の個別の通過コストとする。コスト計算部７３は、リンクＬ５についてリンクデータ群に記憶されているコスト情報に、Ｕターン優先係数を乗算し、その演算結果をリンクＬ５の個別の通過コストとする。
【０１１６】
したがって、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストは、リンクデータ群２５およびノードデータ群２６に記憶されているコスト情報をそのままそれぞれの個別の通過コストとする場合にくらべて、小さくなる。そして、案内経路選択部４４は、この小さくなった「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストと、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストとを比較する。
【０１１７】
その結果、たとえばリンクデータ群２５およびノードデータ群２６に記憶されているコスト情報をそのまま個別の通過コストとして演算した場合には、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストが、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストより高くなる場合であったとしても、その「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストを下げて、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路が案内経路として選択され易くすることができる。
【０１１８】
以上のように、この実施の形態２に係るカーナビゲーションシステムは、探索の起点となる現在地から終点までの直線距離が２ｋｍ以下の距離であって、且つ、起点から終点を見る目的地方角が９０度以上且つ２７０度以下である場合には、探索の終点が現在地の後方の至近距離に設定されたと判断し、Ｕターン優先の条件下で各候補経路のコストを計算する。
【０１１９】
したがって、カーナビゲーションシステムは、探索の終点が現在地の後方の所定距離以下に設定されたと判断した場合には、車両をＵターンさせる経路のコストが他の経路のコストに比べて相対的に低くなり、その車両をＵターンさせる経路が案内経路４８として生成され易くなる。
【０１２０】
その結果、カーナビゲーションシステムは、上述した条件に該当するようにＵターンした方が明らかに早く目的地３５に到達することができるような場合においては、道なり優先のコスト計算条件４６の下で探索した場合の案内経路４８に比べて目的地３５に早く到達することができる、そのＵターンをする経路を案内することができる。
【０１２１】
実施の形態３．
図１０は、本発明の実施の形態３に係るカーナビゲーションシステムにおいて、案内経路の探索時に実現される機能を示すブロック図である。
【０１２２】
記憶デバイス１５に記憶されるコスト計算条件リスト８１は、渋滞係数、道なり優先係数、道なり劣後係数、などの各種の係数を記憶する。
【０１２３】
道なり劣後とは、たとえば車両の進行方向や走行車線が予め判っている場合、その進行方向へ進む道路あるいは車線が、その他の道路に比べて、案内経路４８として相対的に選択され難くすることである。道なり劣後係数は、その進行方向となるリンクのコスト情報に乗算される係数である。道なり劣後係数は、１より大きい値を有する。これにより、車両の進行方向への道路の通過コストを上げることができる。
【０１２４】
コスト計算条件設定部８２は、コスト計算条件リスト８１に基づいて、探索時の車両の状況などに応じたコスト計算条件４６を生成し、記憶デバイス１５に記憶させる。コスト計算条件４６は、たとえば、道なり劣後にて探索する状況下では、道なり劣後係数を有する。コスト計算条件設定部８２は、判断手段として機能する。
【０１２５】
コスト計算部８３は、候補経路リスト４７として記憶デバイス１５に記憶される各候補経路のコストを計算する。コスト計算部８３は、コスト計算手段として機能する。
【０１２６】
図８に示すこれ以外の構成要素は、実施の形態１に係る同名の構成要素と同じ機能を有するものであり、実施の形態１と同名の構成と同一の符号を付してその説明を省略する。また、実施の形態３に係るカーナビゲーションシステムにおいて、経路の案内時に実現される機能は、実施の形態１と同様であり、その説明を省略する。
【０１２７】
なお、このコスト計算条件設定部８２およびコスト計算部８３は、記憶デバイス１５に記憶される案内経路生成プログラムがＣＰＵ２に実行されることで、候補経路生成部４２および案内経路選択部４４とともに、実現される。
【０１２８】
次に、以上の構成を有する実施の形態３に係るカーナビゲーションシステムの動作を説明する。
【０１２９】
図１１は、図１０に示すカーナビゲーションシステムの経路探索時の動作を示すフローチャートである。
【０１３０】
タッチパネル１２などからの探索開始指示に基づいて探索の起点となる現在地および終点となる目的地３５を選択した後、コスト計算条件設定部８２は、コスト計算条件４６の設定を開始する。コスト計算条件設定部８２は、コスト計算条件リスト８１に記憶されている渋滞係数などを、コスト計算条件４６として記憶デバイス１５に記憶させる。
【０１３１】
コスト計算条件設定部８２は、探索の起点から終点までの直線距離が２ｋｍ以下か否かを判断し（ステップＳＴ１）、探索の起点から終点までの直線距離が２ｋｍより長い場合、コスト計算条件リスト８１に記憶されている道なり優先係数を、コスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２）。
【０１３２】
探索の起点から終点までの直線距離が２ｋｍ以下である場合、コスト計算条件設定部８２は、目的地方角が９０度から２７０度の範囲内か否かを判断し（ステップＳＴ３）、目的地方角が９０度より小さいか、もしくは、２７０度より大きい場合、道なり優先係数をコスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２）。
【０１３３】
目的地方角が９０度から２７０度の範囲内である場合、コスト計算条件設定部８２は、コスト計算条件リスト８１に記憶されている道なり劣後係数を、コスト計算条件４６として記憶デバイス１５に記憶させる（ステップＳＴ２１）。
【０１３４】
以上のコスト計算条件４６の設定処理により、図３（Ａ）のハッチングが施された部分内に目的地３５がある場合、コスト計算条件設定部８２は、コスト計算条件４６として、道なり優先係数を設定せずに、渋滞係数、道なり劣後係数を設定する。目的地３５がそれ以外の場所にある場合には、コスト計算条件設定部８２は、コスト計算条件４６として、渋滞係数、道なり優先係数を設定する。
【０１３５】
コスト計算条件４６の設定処理が終了すると、コスト計算条件設定部８２は、候補経路生成部４２に候補経路の生成を指示する。候補経路生成部４２は、リンクデータ群２５およびノードデータ群２６を使用して、候補経路を生成する（ステップＳＴ４）。記憶デバイス１５に候補経路が記憶されると、コスト計算部８３は、各候補経路のコストを計算する（ステップＳＴ５）。記憶デバイス１５に記憶される各候補経路のコストが計算されると、案内経路選択部４４は、その記憶デバイス１５に記憶される複数の候補経路（候補経路リスト４７）の中から、コストが最も低い候補経路を選択する（ステップＳＴ６）。案内経路選択部４４は、選択した１つの候補経路を、案内経路４８として記憶デバイス１５に記憶させる。
【０１３６】
ところで、コスト計算条件４６として道なり劣後係数が設定されている場合、コスト計算部８３は、探索の起点および終点が図３（Ａ）の状態である場合において「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストを演算する際に、以下のように個別の通過コストを計算する。すなわち、コスト計算部８３は、各リンク（たとえばリンクＬ１）についてリンクデータ群に記憶されているコスト情報に、道なり劣後係数を乗算し、その演算結果をそのリンク（たとえばリンクＬ１）の個別の通過コストとする。コスト計算部８３は、各ノード（たとえばＮ１）についてノードデータ群に記憶されているコスト情報に、道なり劣後係数を乗算し、その演算結果をそのノード（たとえばＮ１）の個別の通過コストとする。
【０１３７】
したがって、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストは、リンクデータ群２５およびノードデータ群２６に記憶されているコスト情報をそのままそれぞれの個別の通過コストとする場合にくらべて、大きくなる。そして、案内経路選択部４４は、この大きくなった「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストと、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストと、を比較する。
【０１３８】
その結果、たとえばリンクデータ群２５およびノードデータ群２６に記憶されているコスト情報をそのまま個別の通過コストとして演算した場合には、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路のコストが、「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストより高くなる場合であったとしても、その「起点→Ｌ１→Ｎ１→Ｌ２→Ｎ２→Ｌ３→Ｎ３→Ｌ４→Ｎ４→Ｌ５→終点」という候補経路のコストを上げて、「起点→Ｌ６→Ｎ４→Ｌ５→終点」という候補経路が案内経路として選択され易くすることができる。
【０１３９】
以上のように、この実施の形態３に係るカーナビゲーションシステムは、探索の起点となる現在地から終点までの直線距離が２ｋｍ以下の距離であって、且つ、起点から終点を見る目的地方角が９０度以上且つ２７０度以下である場合には、探索の終点が現在地の後方の至近距離に設定されたと判断し、道なり劣後の条件下で各候補経路のコストを計算する。
【０１４０】
したがって、カーナビゲーションシステムは、探索の終点が現在地の後方の所定距離以下に設定されたと判断した場合には、道なりに進む経路のコストが他の経路のコストに比べて相対的に高くなり、車両をＵターンさせる経路は、その道なりに進む経路のコストに比べて相対的に低くなり、その車両をＵターンさせる経路が案内経路４８として生成され易くなる。
【０１４１】
その結果、カーナビゲーションシステムは、上述した条件に該当するようにＵターンした方が明らかに早く目的地３５に到達することができるような場合においては、道なり優先のコスト計算条件４６の下で探索した場合の案内経路４８に比べて目的地３５に早く到達することができる、そのＵターンをする経路を案内することができる。
【０１４２】
なお、この実施の形態３では、カーナビゲーションシステムは、探索の終点が現在地の後方の所定距離以下に設定されたと判断した場合には、道なりに進む経路のコストを、他の経路のコストに比べて相対的に高くしている。この他にもたとえば、探索の終点が現在地の後方の所定距離以下に設定されたと判断した場合には、カーナビゲーションシステムは、この実施の形態３のように道なりに進む経路のコストを、他の経路のコストに比べて相対的に高くするとともに、実施の形態２のように車両をＵターンさせる経路のコストを他の経路のコストに比べて相対的に低くするようにしてもよい。
【０１４３】
以上の各実施の形態は、本発明の好適な実施の形態の例であるが、本発明はこれに限定されるものではなく、発明の要旨を逸脱しない範囲において、種々の変形、変更が可能である。
【０１４４】
たとえば上記各実施の形態では、コスト計算条件設定部４１は、探索の起点から終点までの直線距離と目的地方角とに基づいて、目的地が現在地の後方の所定距離以下に設定されたか否かを判断し、コスト計算条件４６として設定する係数を選択している。この他にもたとえば、コスト計算条件設定部４１は、探索の起点から終点までの直線距離のみに基づいて、目的地が現在地の後方の所定距離以下に設定されたか否かを判断し、コスト計算条件４６として設定する係数を選択したりするようにしてもよい。また、コスト計算条件設定部４１は、直線距離ではなく、探索の起点から終点までの最短の経路における距離に基づいて、目的地が現在地の後方の所定距離以下に設定されたか否かを判断し、コスト計算条件４６として設定する係数を選択するようにしてもよい。
【０１４５】
上記各実施の形態では、コスト計算条件設定部４１は、探索の起点から終点までの直線距離が２ｋｍ以下か否かを判断して、コスト計算条件４６として設定する係数を選択している。この他にもたとえば、コスト計算条件設定部４１は、たとえば１ｋｍ以下か否かとか、５ｋｍ以下か否かとかの所定の任意の距離以下か否かに基づいて、目的地が現在地の後方の所定距離以下に設定されたか否かを判断し、コスト計算条件４６として設定する係数を選択するようにしてもよい。同様に、コスト計算条件設定部４１は、目的地方向が、たとえば１３５度から２２５度の範囲内か否かなどに基づいて、目的地が現在地の後方の所定距離以下に設定されたか否かを判断し、コスト計算条件４６として設定する係数を選択するようにしてもよい。
【０１４６】
この他にもたとえば、コスト計算条件設定部４１は、自車の後方となる道路およびその後方となる道路から所定の距離（たとえば１ｋｍなど）の範囲内に、目的地があるか否かを判断して、コスト計算条件４６として設定する係数を選択するようにしてもよい。自車の後方となる道路は、さらに現在地から所定の距離以下となる範囲内に制限するとよい。これらの場合、コスト計算条件設定部４１は、たとえば上述した範囲内に目的地がある場合に、目的地が現在地の後方の所定距離以下に設定されたと判断し、Ｕターン優先係数や道なり劣後係数を設定するようにすればよい。
【０１４７】
上記各実施の形態では、コスト計算条件設定部４１は、目的地が現在地の後方の至近距離に設定されたか否かのみを判断している。この他にもたとえば、コスト計算条件設定部４１は、探索の起点から終点までの直線距離あるいは目的地方向について複数段階にて判断し、その段階毎に、異なる値の係数を使い分けて設定するようにしてもよい。また、コスト計算条件設定部４１は、その段階毎に、たとえばＵターン優先係数と道なり劣後係数などの異なる種類の係数を切り替えて設定するようにしてもよい。同様に、目的地方角の大きさに応じて、その係数の値を変化させるようにしてもよい。たとえば、自車の進行方向から１８０度に近い領域の係数値を低くし、９０度または２７０度に近い領域の係数値を高く（＜＝１）するようにする。
【０１４８】
上記各実施の形態では、リンクあるいはノードごとに個別に係数を乗算し、それを加算することで候補経路のコストを計算している。この他にもたとえば、リンクデータ群およびノードデータ群のコスト情報のみに基づいて得られる経路全体のコストに、係数を乗算し、その演算結果を、候補経路のコストとして計算するようにしてもよい。
【０１４９】
上記各実施の形態では、コスト計算部４３，７３，８３は、各候補経路のコストを１つ計算している。この他にもたとえば、コスト計算部４３，７３，８３は、各候補経路について、複数のコストを計算するようにしてもよい。この場合、案内経路選択部４４は、各候補経路の複数のコストに基づいて総合的に判断し、最適と思われるものを案内経路として選択するようにすればよい。
【０１５０】
上記各実施の形態は、カーナビゲーションシステムに適用した場合の例である。この他にもたとえば、本発明は、歩行者、自転車などの経路を案内するナビゲーションシステムに適用することができる。また、ナビゲーションシステムは、携帯電話端末と、それと無線通信回線を介して接続されるナビゲーション用サーバとで構成されていてもよい。
【産業上の利用可能性】
【０１５１】
本発明は、カーナビゲーションシステムなどに利用することができる。
【図面の簡単な説明】
【０１５２】
【図１】図１は、本発明の実施の形態１に係るカーナビゲーションシステムを示す構成図である。
【図２】図２は、図１中の記憶デバイスの記憶内容を示す説明図である。
【図３】図３は、ある地域の道路と、リンクおよびノードとの関係を説明する図である。
【図４】図４は、図１中のＣＰＵが案内経路生成プログラムを実行することで、カーナビゲーションシステムに実現される経路探索時の機能を示すブロック図である。
【図５】図５は、図１中のＣＰＵが経路案内プログラムを実行することで、カーナビゲーションシステムに実現される経路案内時の機能を示すブロック図である。
【図６】図６は、図４に示すカーナビゲーションシステムの経路探索時の動作を示すフローチャートである。
【図７】図７は、図１中の液晶デバイスに表示される地図および案内経路の一例を示す表示画面である。
【図８】図８は、本発明の実施の形態２に係るカーナビゲーションシステムにおいて、経路探索時に実現される機能を示すブロック図である。
【図９】図９は、図８に示すカーナビゲーションシステムの経路探索時の動作を示すフローチャートである。
【図１０】図１０は、本発明の実施の形態３に係るカーナビゲーションシステムにおいて、経路探索時に実現される機能を示すブロック図である。
【図１１】図１１は、図１０に示すカーナビゲーションシステムの経路探索時の動作を示すフローチャートである。
【符号の説明】
【０１５３】
１５ 記憶デバイス（コスト情報記憶手段、優先係数記憶手段、劣後係数記憶手段）
３５ 目的地
４０ 現在位置マーク（現在地）
４１ コスト計算条件設定部（判断手段）
４３ コスト計算部（コスト計算手段）
４４ 案内経路選択部（選択手段）
５６ 経路案内部（経路案内手段）
７２ コスト計算条件設定部（判断手段）
７３ コスト計算部（コスト計算手段）
８２ コスト計算条件設定部（判断手段）
８３ コスト計算部（コスト計算手段）
【特許請求の範囲】
【請求項１】
経路探索の際に、現在地での進行方向前方のリンクおよび／またはノードのコスト情報の値を低くして進行方向前方のリンクおよび／またはノードを優先させる道なり優先制御を実行する案内経路探索装置において、
起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、上記現在地の後方の所定距離以下であるか否かを判断する判断手段と、
経路探索の起点から終点までの経路として選択されるリンクおよび／またはノードのコスト情報を記憶するコスト情報記憶手段と、
上記判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、上記道なり優先制御を禁止し、上記コスト情報記憶手段に記憶されるリンクおよび／またはノードのコスト情報を用いて、探索された経路のコストを計算するコスト計算手段と、
上記コスト計算手段により計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択する選択手段と、
を有することを特徴とする案内経路探索装置。
【請求項２】
経路探索の起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、上記現在地の後方の所定距離以下であるか否かを判断する判断手段と、
経路探索の起点から終点までの経路として選択されるリンクおよび／またはノードのコスト情報を記憶するコスト情報記憶手段と、
上記判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、上記コスト情報記憶手段に記憶される各リンクおよび／またはノードのコスト情報を用いて、進行方向前方へ進む経路より進行方向後方へ進む経路の方が選択され易くなるように上記コスト情報を調整して、探索された経路のコストを計算するコスト計算手段と、
上記コスト計算手段により計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択する選択手段と、
を有することを特徴とする案内経路探索装置。
【請求項３】
前記コスト計算手段は、現在地から進行方向後方となるリンクおよび／またはノードのコスト情報として、前記コスト情報記憶手段に記憶されるそのリンクおよび／またはノードのコスト情報より小さな値を有するコスト情報を使用して、探索された経路のコストを計算し、
前記選択手段は、コストが最も低い経路を案内経路として選択すること、
を特徴とする請求項２記載の案内経路探索装置。
【請求項４】
前記コスト情報記憶手段に記憶されるリンクまたはノードのコスト情報から、現在地から進行方向後方となるリンクまたはノードのコスト情報を得る際に、コスト情報の値を小さくするＵターン優先係数を記憶する優先係数記憶手段を有し、
前記コスト計算手段は、前記判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地から進行方向後方となるリンクおよび／またはノードについて、前記コスト情報記憶手段に記憶されるそのリンクおよび／またはノードのコスト情報に上記Ｕターン優先係数を適用したコスト情報を使用して、探索された経路のコストを計算し、
前記選択手段は、コストが最も低い経路を案内経路として選択すること、
を特徴とする請求項２記載の案内経路探索装置。
【請求項５】
前記コスト計算手段は、現在地から進行方向前方となるリンクおよび／またはノードのコスト情報として、前記コスト情報記憶手段に記憶されるそのリンクおよび／またはノードのコスト情報より大きな値を有するコスト情報を使用して、探索された経路のコストを計算し、
前記選択手段は、コストが最も低い経路を案内経路として選択すること、
を特徴とする請求項２または３記載の案内経路探索装置。
【請求項６】
前記コスト情報記憶手段に記憶されるリンクまたはノードのコスト情報から、現在地から進行方向前方となるリンクまたはノードのコスト情報を得る際に、コスト情報の値を大きくする道なり劣後係数を記憶する劣後係数記憶手段を有し、
前記コスト計算手段は、前記判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地から進行方向前方となるリンクまたはノードについて、前記コスト情報記憶手段に記憶されるそのリンクまたはノードのコスト情報に上記道なり劣後係数を適用したコスト情報を使用して、探索された経路のコストを計算し、
前記選択手段は、コストが最も低い経路を案内経路として選択すること、
を特徴とする請求項５記載の案内経路探索装置。
【請求項７】
起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、上記現在地の後方の所定距離以下であるか否かを判断するステップと、
経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地での進行方向前方のリンクおよび／またはノードのコスト情報の値を低くして進行方向前方のリンクおよび／またはノードを優先させる道なり優先制御を禁止し、コスト情報記憶手段に記憶されるリンクおよび／またはノードのコスト情報を用いて、探索された経路のコストを計算するステップと、
計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択するステップと、
を有することを特徴とする案内経路探索方法。
【請求項８】
経路探索の起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、上記現在地の後方の所定距離以下であるか否かを判断するステップと、
経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、コスト情報記憶手段に記憶されるリンクおよび／またはノードのコスト情報を用いて、進行方向前方へ進む経路より進行方向後方へ進む経路の方が選択され易くなるように上記コスト情報を調整して、探索された経路のコストを計算するステップと、
計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択するステップと、
を有することを特徴とする案内経路探索方法。
【請求項１】
経路探索の際に、現在地での進行方向前方のリンクおよび／またはノードのコスト情報の値を低くして進行方向前方のリンクおよび／またはノードを優先させる道なり優先制御を実行する案内経路探索装置において、
起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、上記現在地の後方の所定距離以下であるか否かを判断する判断手段と、
経路探索の起点から終点までの経路として選択されるリンクおよび／またはノードのコスト情報を記憶するコスト情報記憶手段と、
上記判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、上記道なり優先制御を禁止し、上記コスト情報記憶手段に記憶されるリンクおよび／またはノードのコスト情報を用いて、探索された経路のコストを計算するコスト計算手段と、
上記コスト計算手段により計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択する選択手段と、
を有することを特徴とする案内経路探索装置。
【請求項２】
経路探索の起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、上記現在地の後方の所定距離以下であるか否かを判断する判断手段と、
経路探索の起点から終点までの経路として選択されるリンクおよび／またはノードのコスト情報を記憶するコスト情報記憶手段と、
上記判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、上記コスト情報記憶手段に記憶される各リンクおよび／またはノードのコスト情報を用いて、進行方向前方へ進む経路より進行方向後方へ進む経路の方が選択され易くなるように上記コスト情報を調整して、探索された経路のコストを計算するコスト計算手段と、
上記コスト計算手段により計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択する選択手段と、
を有することを特徴とする案内経路探索装置。
【請求項３】
前記コスト計算手段は、現在地から進行方向後方となるリンクおよび／またはノードのコスト情報として、前記コスト情報記憶手段に記憶されるそのリンクおよび／またはノードのコスト情報より小さな値を有するコスト情報を使用して、探索された経路のコストを計算し、
前記選択手段は、コストが最も低い経路を案内経路として選択すること、
を特徴とする請求項２記載の案内経路探索装置。
【請求項４】
前記コスト情報記憶手段に記憶されるリンクまたはノードのコスト情報から、現在地から進行方向後方となるリンクまたはノードのコスト情報を得る際に、コスト情報の値を小さくするＵターン優先係数を記憶する優先係数記憶手段を有し、
前記コスト計算手段は、前記判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地から進行方向後方となるリンクおよび／またはノードについて、前記コスト情報記憶手段に記憶されるそのリンクおよび／またはノードのコスト情報に上記Ｕターン優先係数を適用したコスト情報を使用して、探索された経路のコストを計算し、
前記選択手段は、コストが最も低い経路を案内経路として選択すること、
を特徴とする請求項２記載の案内経路探索装置。
【請求項５】
前記コスト計算手段は、現在地から進行方向前方となるリンクおよび／またはノードのコスト情報として、前記コスト情報記憶手段に記憶されるそのリンクおよび／またはノードのコスト情報より大きな値を有するコスト情報を使用して、探索された経路のコストを計算し、
前記選択手段は、コストが最も低い経路を案内経路として選択すること、
を特徴とする請求項２または３記載の案内経路探索装置。
【請求項６】
前記コスト情報記憶手段に記憶されるリンクまたはノードのコスト情報から、現在地から進行方向前方となるリンクまたはノードのコスト情報を得る際に、コスト情報の値を大きくする道なり劣後係数を記憶する劣後係数記憶手段を有し、
前記コスト計算手段は、前記判断手段により経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地から進行方向前方となるリンクまたはノードについて、前記コスト情報記憶手段に記憶されるそのリンクまたはノードのコスト情報に上記道なり劣後係数を適用したコスト情報を使用して、探索された経路のコストを計算し、
前記選択手段は、コストが最も低い経路を案内経路として選択すること、
を特徴とする請求項５記載の案内経路探索装置。
【請求項７】
起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、上記現在地の後方の所定距離以下であるか否かを判断するステップと、
経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、現在地での進行方向前方のリンクおよび／またはノードのコスト情報の値を低くして進行方向前方のリンクおよび／またはノードを優先させる道なり優先制御を禁止し、コスト情報記憶手段に記憶されるリンクおよび／またはノードのコスト情報を用いて、探索された経路のコストを計算するステップと、
計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択するステップと、
を有することを特徴とする案内経路探索方法。
【請求項８】
経路探索の起点となる現在地およびその現在地における現在の進行方向を基準として、経路探索の終点となる目的地あるいは経由地の相対的な位置関係が、上記現在地の後方の所定距離以下であるか否かを判断するステップと、
経路探索の終点が経路探索の起点の後方の所定距離以下に設定されたと判断された場合には、コスト情報記憶手段に記憶されるリンクおよび／またはノードのコスト情報を用いて、進行方向前方へ進む経路より進行方向後方へ進む経路の方が選択され易くなるように上記コスト情報を調整して、探索された経路のコストを計算するステップと、
計算されたコストを用いて、探索された複数の経路のコストを比較し、その複数の経路の中から１つの経路を案内経路として選択するステップと、
を有することを特徴とする案内経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００６−１１９０７８（Ｐ２００６−１１９０７８Ａ）
【公開日】平成１８年５月１１日（２００６．５．１１）
【国際特許分類】
【出願番号】特願２００４−３０９４５４（Ｐ２００４−３０９４５４）
【出願日】平成１６年１０月２５日（２００４．１０．２５）
【出願人】（０００００３５９５）株式会社ケンウッド (1,981)
【Ｆターム（参考）】
【公開日】平成１８年５月１１日（２００６．５．１１）
【国際特許分類】
【出願日】平成１６年１０月２５日（２００４．１０．２５）
【出願人】（０００００３５９５）株式会社ケンウッド (1,981)
【Ｆターム（参考）】
[ Back to top ]