ルート探索装置
【課題】ユーザの希望する経路長の周回ルートを探索できるようにする。
【解決手段】出発地を含む所定領域に存在するノードを抽出し、経由地としての選択しやすさの度合いを示すスコアが規定されたノード評価テーブルに規定されたスコアに基づき、抽出したノードに対するスコアを算出し（Ｓ２００）、周回ルートの経路長が予め設定された経路長を基準とする予め定められた範囲内となるように、抽出した各ノードの中からスコア順に経由地を順次特定して往路経路を探索するとともに往路経路の最終経由地から出発地に至る復路経路を探索する（Ｓ２０８〜Ｓ２２６）。
【解決手段】出発地を含む所定領域に存在するノードを抽出し、経由地としての選択しやすさの度合いを示すスコアが規定されたノード評価テーブルに規定されたスコアに基づき、抽出したノードに対するスコアを算出し（Ｓ２００）、周回ルートの経路長が予め設定された経路長を基準とする予め定められた範囲内となるように、抽出した各ノードの中からスコア順に経由地を順次特定して往路経路を探索するとともに往路経路の最終経由地から出発地に至る復路経路を探索する（Ｓ２０８〜Ｓ２２６）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、周回ルートを探索するルート探索装置に関する。
【背景技術】
【０００２】
従来、予め定められたルートを１又は複数記憶し、いずれか１つのルートを選択すると、そのルートを構成する複数の地点のいずれか１つを出発点にしてルートをめぐり元に戻ってくる経路を計算し、ユーザに表示する装置が提案されている（例えば、特許文献１参照）。
【特許文献１】特開平１１−１１８５００号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記特許文献１に記載の装置は、予め定められたルートの中から特定のルートを選択するようになっているため、必ずしもユーザの希望する経路長のルートが提示されるとは限らない。例えば、自車位置を出発地として所定経路長の周回ルートを探索してドライブしたい場合、上記特許文献１に記載の装置では、ユーザの満足する周回ルートを探索するのは困難である。
【０００４】
本発明は上記点に鑑みたもので、ユーザの希望する経路長の周回ルートを探索できるようにすることを目的とする。
【課題を解決するための手段】
【０００５】
本発明の第１の特徴は、出発地から任意のノードを経由地として当該出発地へ戻る周回ルートを探索するルート探索装置であって、周回ルートの経路長を設定する設定手段と、ノードの条件に対し、経由地としての選択しやすさの度合いを示すスコアが規定されたテーブルを記憶する記憶手段と、出発地を含む所定領域に存在するノードを抽出するとともに、抽出したノードの条件とテーブルに規定されたスコアに基づき、抽出した各ノードに対するスコアを算出するスコア算出手段と、周回ルートの経路長が設定手段によって設定された経路長を基準とする予め定められた範囲内となるように、スコア算出手段によって算出されたスコア順に抽出した各ノードの中から経由地を順次特定して往路経路を探索するとともに往路経路の最終経由地から出発地に至る復路経路を探索する経路探索手段と、経路探索手段によって探索された往路経路と復路経路を周回ルートとして決定する周回ルート決定手段と、を備えたことである。
【０００６】
このような構成では、周回ルートの経路長が設定された経路長を基準とする予め定められた範囲内となるように、算出されたスコア順に抽出した各ノードの中から経由地を順次特定して往路経路が探索されるとともに往路経路の最終経由地から出発地に至る復路経路が探索されるので、ユーザの希望する経路長の周回ルートを探索することができる。
【０００７】
また、本発明の第２の特徴は、設定手段は、更に、複数の優先すべき経路条件の中から少なくとも１つを経路条件項目として設定するもので、テーブルには、経路条件項目毎に対応するスコアが規定されており、設定手段によって経路条件項目の少なくとも１つが設定された場合、設定された経路条件項目に該当するノードが経由地として選択されやすくなるように、設定された経路条件項目に対応するテーブルのスコアを更新するテーブル更新手段と、を備えたことである。
【０００８】
このような構成では、設定された経路条件項目に該当するノードが経由地として選択されやすくなるように、設定された経路条件項目に対応するテーブルのスコアが更新されるので、設定された経路条件項目に該当するノードを優先的に経由地として選択した経路を探索することが可能である。
【０００９】
また、本発明の第３の特徴は、設定手段は、更に、指定された特定のノードをユーザ指定経由地として設定するもので、テーブルには、ユーザ指定経由地に対応するスコアが規定されており、設定手段によって特定のノードがユーザ指定経由地として設定された場合、テーブル更新手段は、設定された特定のノードが経由地として選択されやすくなるように、設定された特定のノードに対応するテーブルのスコアを更新することである。
【００１０】
このような構成では、設定された特定のノードが経由地として選択されやすくなるように、設定された特定のノードに対応するテーブルのスコアが更新されるので、設定された特定のノードを優先的に経由地として選択した経路を探索することが可能である。
【００１１】
また、本発明の第４の特徴は、経路探索手段は、設定手段によって設定された経路長の半分以上となるまで、抽出した各ノードの中から経由地を順次特定して往路経路を探索することである。
【００１２】
また、本発明の第５の特徴は、経路探索手段が、往路経路を探索する際に、同一スコアのノードが複数ある場合、近くのノードから先に経由地として特定することである。
【００１３】
また、本発明の第６の特徴は、経路探索手段は、経路探索手段によって探索された周回ルートの経路長が設定手段によって設定された経路長を基準とする予め定められた範囲よりも長いか否かを判定する判定手段を備え、判定手段によって周回ルートの経路長が設定手段によって設定された経路長を基準とする予め定められた範囲よりも長いと判定された場合、往路経路の最終経由地を手前のノードに変更して、往路経路および復路経路を探索することである。
【００１４】
このような構成では、周回ルートの経路長が設定手段によって設定された経路長を基準とする予め定められた範囲よりも長いと判定された場合、往路経路の最終経由地を手前のノードに変更して、往路経路および復路経路が探索されるので、よりユーザの希望する経路長の周回ルートを探索しやすくすることが可能である。
【発明を実施するための最良の形態】
【００１５】
（第１実施形態）
本発明の第１実施形態に係るルート探索装置の構成を図１に示す。本実施形態に係るルート探索装置はナビゲーション装置１として構成されている。本ナビゲーション装置１は、位置検出器１０、地図データ入力器１５、操作スイッチ群１６、外部メモリ１８、表示装置１９、送受信機２０、音声コントローラ２１、スピーカ２２、音声認識装置２３、マイク２４、リモコンセンサ２５と、これら各装置が接続された制御装置１７を備えている。
【００１６】
位置検出器１０は、いずれも周知の地磁気センサ１１、ジャイロスコープ１２、距離センサ１３およびＧＰＳ受信機１４等のセンサを有しており、これらセンサの各々の性質に基づいた自車位置を特定するための情報を制御装置１７に出力する。
【００１７】
地図データ入力器１５は、地図データが記憶された地図データ記憶媒体（図示せず）から、該地図データ記憶媒体に格納されている位置検出の精度向上のためのいわゆるマップマッチング用データ、地図データ及び目印データを含む各種データを入力するための装置である。地図データ記憶媒体としては、そのデータ量からＣＤ−ＲＯＭまたはＤＶＤ−ＲＯＭを用いるのが一般的であるが、メモリカード、ＨＤＤ等を用いてもよい。
【００１８】
操作スイッチ群１６は、表示装置１９のディスプレイに重ねて設けられたタッチスイッチおよび表示装置１９のディスプレイの周囲に設けられたメカニカルなスイッチ等によって構成され、ユーザの操作に応じた信号を出力する。
【００１９】
外部メモリ１８は、不揮発性の記憶媒体であり、電源をオフしても消去すべきでないデータや、制御装置１７の処理において頻繁に使用されるデータ等が記憶される。なお、外部メモリ１８としては、ハードディスクやメモリカード等の記憶媒体を用いるとよい。
【００２０】
表示装置１９は、液晶、有機ＥＬ等のフルカラー表示が可能なディスプレイを有し、制御装置１７から入力される映像信号に応じた映像をディスプレイに表示させる。
【００２１】
送受信機２０は、ＶＩＣＳセンタ５とデータの送受信を行うための装置である。送受信機置１２は、ＶＩＣＳセンタ５からの交通情報等を受信し、ＶＩＣＳセンタ５へ車両情報、ユーザ情報等を送信する。
【００２２】
音声認識装置２３は、マイク２４を介して入力される音声信号と、内部に記憶する認識辞書（図示せず）中の語彙データ（比較対象パターン）とを照合して音声認識を行い、音声認識の結果を音声コントローラ２１に入力する。
【００２３】
音声コントローラ２１は、音声認識装置２３の認識結果を制御装置１７へ出力するとともに、制御装置１７から入力される音声信号をスピーカ２２へ出力する。また、音声コントローラ２１は、マイク２４から入力される音声信号に応じた音声をスピーカ２２からトークバック出力（音声出力）させる。
【００２４】
リモコンセンサ２５は、ユーザの操作に基づいて赤外線等による無線信号を送信するリモコン２５ａから受信した信号を制御装置１７へ出力する。
【００２５】
制御装置１７は、ＣＰＵ、ＲＯＭ、ＲＡＭ、Ｉ／Ｏ等を備えたコンピュータとして構成されている。制御装置１７のＣＰＵは、ＲＯＭに記憶されたプログラムに従って各種処理を実行する。制御装置１７のＣＰＵが実行する処理としては、位置検出器１０から入力される情報に基づいて自車位置を特定する自車位置特定処理、地図縮尺を変更する地図縮尺変更処理、メニュー表示などを行うメニュー表示選択処理、ユーザの操作に応じて目的位置を設定する目的地設定処理、自車位置（出発地）から目的地に至る最適な案内経路を探索する経路探索処理、探索した案内経路に従って経路案内を行う経路案内処理、自車位置を修正する自車位置修正処理、スピーカ２２から出力する音量を調整する音量調整処理等がある。
【００２６】
上記した構成において、ユーザの操作に応じて目的地が設定されると、制御装置１７は、自車位置特定処理によって特定した自車位置から目的地に至る最適な案内経路を探索し、探索した案内経路を表示装置１９のディスプレイに表示させる。なお、最適な案内経路を探索する手法としては、ダイクストラ法などが知られている。
【００２７】
また、本実施形態おける制御装置１７は、出発地から任意のノードを経由地として当該出発地へ戻る周回ルートを探索する周回ルート探索処理を実施する機能を備えている。
【００２８】
本実施形態における外部メモリ１８には、ノードの条件に対し、経由地としての選択しやすさの度合いを示すスコアが規定されたノード評価テーブルおよび経路計算に用いられるリンクコスト係数が規定された経路計算リンクコスト係数テーブルが記憶されている。
【００２９】
図２に、ノード評価テーブルの構成例を示す。図に示すように、ノード評価テーブルには、海沿い、山道、裏道、ユーザ指定経由地等の各条件（基準）に対し、経由地としての選択しやすさの度合いを示すスコアが規定されている。なお、図２に示されているノード評価テーブルは一例であり、実際には、様々な条件（基準）に対してスコアが規定されている。また、本実施形態では、スコアが高いほど経由地として選択されやすくなっている。
【００３０】
図３に、経路計算リンクコスト係数テーブルの構成例を示す。図に示すように、経路計算リンクコスト係数テーブルには、車線数、道幅、信号機の有無、右左折などを条件（基準）とする各パラメータに対し、リンクコスト係数が規定されている。なお、本実施形態では、リンクコスト係数が低いほど探索されやすくなっている。
【００３１】
なお、ノード評価テーブルのスコアおよび経路計算リンクコスト係数テーブルのリンクコスト係数は、予め基準値が設定されているが、以下に示す経路条件項目の設定処理によって更新される。
【００３２】
図４に、制御装置１７による経路条件項目の設定処理のフローチャートを示す。ユーザの操作に応じて設定条件項目の設定処理の開始が指示されると、制御装置１７は、図４に示す処理を実施する。
【００３３】
まず、周回ルートの距離または時間を設定する（Ｓ１００）。ここでは、図５に示す経路条件項目例に示される周回ルートの経路長（キロメートル）または所要時間（分）を設定する。具体的には、周回ルートの経路長および周回ルートの所要時間を促す画面を表示させ、この画面に従って周回ルートの経路長が入力された場合には周回ルートの経路長をＲＡＭに記憶し、画面に従って周回ルートの所要時間が入力された場合には、所要時間を経路長に換算してＲＡＭに記憶する。
【００３４】
次に、ユーザ条件の設定を行う（Ｓ１０２）。具体的には、図５に示す経路条件項目例に示される海沿い優先、山道優先、裏道優先、燃費優先等、優先すべき経路条件の中から選択された項目を示すフラグをＲＡＭに記憶するとともに、特定のノードが経由地指定された場合には、経由地指定されたノードをＲＡＭに記憶する。
【００３５】
次に、先のＳ１０２にて設定されたユーザ条件に従って、ノード評価テーブルおよび経路計算リンクコスト係数テーブルを更新する（Ｓ１０４）。
【００３６】
海沿い優先を示すフラグがＲＡＭに記憶されている場合、図２に示したノード評価テーブルにおける海沿いに対するスコアを基準値から無限大に更新する。
【００３７】
同様に、山道優先を示すフラグがＲＡＭに記憶されている場合、ノード評価テーブルにおける山道優先に対するスコアを基準値から無限大に更新する。
【００３８】
また、裏道優先を示すフラグがＲＡＭに記憶されている場合、ノード評価テーブルにおける裏道優先に対するスコアを基準値から無限大に更新するとともに、図３に示した経路計算リンクコスト係数テーブルの「道幅狭い」と「道幅狭窄」の項目のリンクコスト係数を予め定められた値だけ低くする。
【００３９】
また、燃費優先を示すフラグがＲＡＭに記憶されている場合、図３に示した経路計算リンクコスト係数テーブルの「信号機無し」の項目のリンクコスト係数を予め定められた値だけ低くするとともに、「右左折する」の項目のリンクコスト係数を予め定められた値だけ高くする。
【００４０】
また、特定のノードが経由地指定された場合、ノード評価テーブルにおける経由地指定に対するスコアを基準値から無限大に更新する。
【００４１】
そして、ノード評価テーブルおよび経路計算リンクコスト係数テーブルの更新が終了すると、本処理を終了する。
【００４２】
本実施形態における制御装置１７は、上記した設定条件項目の設定処理設定条件項目の設定処理が終了した後、ユーザの操作によって周回ルート探索処理の開始が指示されると、図６に示す経路作成処理を開始する。
【００４３】
まず、自車位置より経路条件距離の距離にあるノードの評価を行う（Ｓ２００）。具体的には、Ｓ１００にて設定された周回ルートの経路長を経路条件距離Ｘとして、地図データから自車位置を中心とする半径Ｘ／２の領域に含まれるノードを抽出するとともに、抽出したノードの条件とノード評価テーブルに規定されたスコアに基づき、抽出した各ノードに対するスコアを算出する。例えば、経路条件距離Ｘが１０キロメートルの場合、自車位置を中心とする半径５キロメートルの領域に含まれる各ノードに対するスコアを算出する。
【００４４】
なお、本実施系形態では、図５に示した経路条件項目のうち、周回ルートの経路長（Ｘ＝１０キロメートル）のみが設定され、ノード評価テーブルのスコアおよび経路計算リンクコスト係数テーブルのリンクコスト係数は、予め設定された基準値のままとなっているものとして説明する。
【００４５】
次に、経路条件に合うノードがあるか否かを判定する（Ｓ２０２）。具体的には、自車位置を中心とする半径Ｘ／２の領域にノードが存在するか否かに基づいて経路条件に合うノードがあるか否かを判定する。
【００４６】
ここで、自車位置を中心とする半径Ｘ／２の領域にノードが存在しない場合、Ｓ２０２の判定はＮＯとなり、次に、設定された経路条件に従って周回ルートを探索できない旨をユーザへ通知し（Ｓ２０４）、本処理を終了する。
【００４７】
また、自車位置を中心とする半径Ｘ／２の領域にノードが存在する場合、Ｓ２０２の判定はＹＥＳとなり、以下、Ｓ２０６〜Ｓ２１８に示す処理において、図７に示す往路経路作成データを作成しながらＳ２００にて算出されたスコア順に抽出した各ノードの中から経由地を順次特定して往路経路を探索する処理を実施する。
【００４８】
まず、Ｓ２０６では、自車位置をノードＡとして設定する。具体的には、図６に示した往路経路作成データのノードＡに自車位置を設定する。
【００４９】
次に、ノードＢを抽出する（Ｓ２０８）。具体的には、Ｓ２００にて算出されたスコアの最も高いノードをノードＢとして特定する。なお、スコアの最も高いノードが複数ある場合には、自車位置に近いノードを優先的にノードＢとして抽出する。例えば、図８（ａ）に示すノード１１のスコアが最も高い場合、ノード１１をノードＢとして特定する。
【００５０】
次に、ノードＡとノードＢ間の経路計算を行う（Ｓ２１０）。ノードＡとノードＢ間の経路計算は、ノード間のリンク長および経路計算リンクコスト係数テーブルに規定されたリンクコスト係数に基づき、ダイクストラ法などを用いて探索することができる。
【００５１】
次に、経路計算結果から道なり距離Ｌを積算する（Ｓ２１２）。具体的には、ノードＡとノードＢ間の道なり距離Ｌを算出するとともに、往路経路作成データの道なり距離Ｌとして追加記憶する。
【００５２】
次に、経由ノードキューに経由するノードすべてを追加する（Ｓ２１４）。具体的には、ノードＢとして特定したノード番号を往路経路作成データの経由ノードキューとして追加記憶する。
【００５３】
次に、ノードＡをノードＢに置き換える（Ｓ２１６）。図７に示すように、往路経路作成データにおける前段のノードＢをノードＡとして設定する。
【００５４】
次に、道なり距離Ｌが経路条件距離Ｘ／２以上か否かを判定する（Ｓ２１８）。道なり距離Ｌが経路条件距離Ｘ／２未満の場合、Ｓ２１８の判定はＮＯとなり、Ｓ２０８へ戻り、上記した往路経路を探索する処理を繰り返し実施する。なお、上記した往路経路の探索処理では、同一のノードが複数回経由地として設定されないように、Ｓ２０８において往路経路作成データの経由ノードキューに含まれるノードはノードＢとして特定しないように制約が設けられている。
【００５５】
例えば、図８（ａ）において、ノード１１、ノード１２、ノード１３、ノード７、ノード６、ノード３、ノード２の順にスコアが高くなっている場合、図８（ｂ）に示すように、自車位置からノード１１、ノード１２、ノード１３、ノード７、ノード６、ノード３、ノード２が経由地として順次特定され、図７に示したような往路経路作成データが作成される。
【００５６】
そして、経路条件距離Ｘが１０キロメートルに設定されている場合、ノード２まで経由すると道なり距離Ｌが５．３キロメートルとなるため、Ｓ２１８の判定はＹＥＳとなり、次に、例外条件経路であるか否かを判定する（Ｓ２２０）。例外条件経路は、往路経路と後述する復路経路とが一致する場合と、周回ルートの経路長が経路条件距離Ｘを超過してしまう場合のいずれかである。ここでは、Ｓ２２６にてＮＯと判定されるものとして説明する。
【００５７】
以下、Ｓ２２２〜Ｓ２２６に示す処理において、図９に示すような復路経路作成データを作成しながら往路経路の最終経由地から自車位置に至る復路経路を探索する処理を実施する。
【００５８】
まず、往路経路作成データの経由ノードキューから往路経路の最終経由地となっているノード２を折り返し地点として復路経路作成データのノードＴに設定する（Ｓ２２２）。
【００５９】
次に、ノードＴから自車位置への経路計算を行う（Ｓ２２４）。ノードＴから自車位置への経路計算は、ノード間のリンク長および経路計算リンクコスト係数テーブルに規定されたリンクコスト係数などに基づき、ダイクストラ法などを用いて探索することができる。
【００６０】
次に、ノードＴから自車位置へ戻る復路経路の道なり距離Ｌを積算し（Ｓ２２６）、図９に示すように、計算した復路経路の道なり距離Ｌに往路経路の道なり距離Ｌを加算して復路経路作成データの道なり距離Ｌとして記憶する。
【００６１】
次に、往路経路と復路経路を積算した道なり距離Ｌが、経路条件距離Ｘを基準とする予め定められた範囲（例えば、Ｘ±５００メートル）内に含まれるか、経路条件距離Ｘを基準とする予め定められた範囲よりも短いか、あるいは経路条件距離Ｘを基準とする予め定められた範囲よりも長いか否かを比較判定する（Ｓ２２８）。
【００６２】
例えば、図８（ｃ）に示すようにノード２からノード５、ノード８、ノード１０、ノード１６を経由して自車位置に至る復路が探索され、往路経路と復路経路を積算した道なり距離Ｌが１２．３キロメートルとなった場合、往路経路と復路経路を積算した道なり距離Ｌが経路条件距離Ｘを基準とする予め定められた範囲（例えば、９．５キロメートル〜１０．５キロメートル）に含まれないと判定され、次に、往路経路の最終経由地を１つ手前のノードに変更する（Ｓ２３０）。例えば、図８（ｂ）に示されているようにノード２が往路経路の最終経由地として仮決定されている場合、往路経路の最終経由地をノード２の１つ手前のノード３に変更する。
【００６３】
そして、Ｓ２２２にて、復路経路作成データのノードＴをノード２からノード３に変更し、再度、復路経路を探索する。例えば、図８（ｄ）に示すようにノード３からノード１６を経由して自車位置に至る復路が探索され、その道なり距離Ｌが９．６キロメートルとなると、Ｓ２２８の判定は往路経路と復路経路を積算した道なり距離Ｌが、経路条件距離Ｘを基準とする予め定められた範囲内に含まれると判定され、次に、探索された往路経路と復路経路からなる周回ルートを案内経路として決定する（Ｓ２３２）。
【００６４】
なお、ユーザの操作により経路案内の開始が指示されると、制御装置１７は、探索した周回ルートに従って経路案内を行う経路案内処理を開始する。
【００６５】
また、Ｓ２２８にて、往路経路と復路経路を積算した道なり距離Ｌが、経路条件距離Ｘを基準とする予め定められた範囲よりも短いと判定された場合、Ｓ２０８へ戻り、再度、往路経路の探索処理を実施する。
【００６６】
また、Ｓ２２０〜Ｓ２２４の復路経路の探索処理の結果、周回ルートが例外条件経路となってしまう場合、Ｓ２２６の判定はＹＥＳとなり、例外経路になる旨をユーザに確認する（Ｓ２３４）。例えば、往路と復路が同じ周回ルートとなる場合には、「往路と復路が同じ周回ルートとなります」といったメッセージとともに「ＹＥＳ」、「ＮＯ」を選択可能に表示させる。また、周回ルートの経路長が経路条件距離よりも長くなる場合には、「周回ルートの経路長が経路条件距離よりも長くなります」といったメッセージとともに「ＹＥＳ」、「ＮＯ」を選択可能に表示させる。
【００６７】
ユーザの操作により、往路と復路が同じとなる周回ルートでもよいことが確認された場合、または周回ルートの経路長が経路条件距離よりも長くなってもよいことが確認された場合、Ｓ２３２へ進み、探索した経路を周回ルートとして決定する。
【００６８】
また、往路と復路が同じとなる周回ルートではよくないことが確認された場合、または周回ルートの経路長が経路条件距離を基準とする予め定められた範囲よりも長くなってはならないことが確認された場合、条件を満たさないことをユーザへ通知する（Ｓ２３６）。例えば、「条件を満たす周回ルートを探索できませんでした。再度、条件を変更して探索してください」といったメッセージを表示させ、探索した経路を周回ルートとして決定することなく、本処理を終了する。
【００６９】
上記した構成によれば、周回ルートの経路長が設定された経路長を基準とする予め定められた範囲内となるように、算出されたスコア順に抽出した各ノードの中から経由地を順次特定して往路経路が探索されるとともに往路経路の最終経由地から出発地に至る復路経路が探索されるので、ユーザの希望する経路長の周回ルートを探索することができる。
【００７０】
また、設定された経路条件項目に該当するノードが経由地として選択されやすくなるように、設定された経路条件項目に対応するテーブルのスコアが更新されるので、設定された経路条件項目に該当するノードを優先的に経由地として選択した経路を探索することが可能である。
【００７１】
また、設定された特定のノードが経由地として選択されやすくなるように、設定された特定のノードに対応するテーブルのスコアが更新されるので、設定された特定のノードを優先的に経由地として選択した経路を探索することが可能である。
【００７２】
また、周回ルートの経路長が設定された経路長を基準とする予め定められた範囲よりも長いと判定された場合、往路経路の最終経由地を手前のノードに変更して、往路経路および復路経路が探索されるので、よりユーザの希望する経路長の周回ルートを探索しやすくすることが可能である。
【００７３】
（第２実施形態）
本発明の第２実施形態に係るルート探索装置の構成は、図１に示した第１実施形態の構成と同じである。また、ルート探索装置の処理についても、図４、図６に示した第１実施形態の処理と同じである。上記第１実施形態では、図５に示した経路条件項目のうち、周回ルートの経路長のみが設定され、ノード評価テーブルのスコアおよび経路計算リンクコスト係数テーブルのリンクコスト係数は、予め設定された基準値のままとなっているものとして説明したが、本実施形態では、周回ルートの経路長が設定され、更に、海沿い優先が選択されたものとして説明する。
【００７４】
このように、ユーザの操作によっての海沿い優先が選択されると、図４に示した経路条件項目の設定処理によって、図２に示したノード評価テーブルにおける海沿いに対するスコアが基準値から無限大に更新される。
【００７５】
そして、図６に示した経路作成処理のＳ２００にて、海沿いに存在するノードのスコアが無限大となるように、地図データから自車位置を中心とする半径Ｘ／２の領域に含まれるノードのスコアが算出される。例えば、図１０（ａ）に示すように海沿いのノード１、ノード２、ノード３、ノード４、ノード５のスコアが無限大となるようにノードのスコアが算出される。
【００７６】
そして、図１０（ｂ）に示すように、自車位置から海沿いのノードの中で自車位置に最も近いノード３を経由してノード２に至る往路経路が探索される。すなわち、自車位置からノード１０、ノード１１、ノード３を経由してノード２に至る往路経路が探索される。
【００７７】
その後、ノード２を折り返し地点（ノードＴ）として、図１０（ｃ）に示すように、ノード２からノード７、ノード８、ノード９、ノード１０を経由して自車位置に至る復路経路が探索される。
【００７８】
このようにして、設定された周回ルートの経路長の予め定められた範囲内で、海沿いを優先した周回ルートが探索される。
【００７９】
（他の実施形態）
なお、本発明は上記実施形態に限定されるものではなく、本発明の趣旨に基づいて種々なる形態で実施することができる。
【００８０】
例えば、上記実施形態では、Ｓ２００にて、地図データから自車位置を中心とする半径Ｘ／２の領域に含まれるノードを抽出する例を示したが、例えば、自車位置を含む一定区画の領域に含まれるノードを抽出するようにしてもよい。
【００８１】
また、上記第１実施形態では、図８（ｂ）において、ノード１１、ノード１２、ノード１３、ノード７、ノード６、ノード３、ノード２のように隣接するノード順にスコアが高くなっている例を示したが、このように隣接するノード順にスコアが高くなっていなくても、スコアの高い順にノードをノードＢとして特定することができる。
【００８２】
また、上記第１実施形態では、Ｓ２２２において、復路経路作成データの経由ノードキューと関係なくノードＴから自車位置への経路計算を行う例を示したが、復路経路作成データの経由ノードキューに含まれるノードを含まないようにノードＴから自車位置への経路計算を行うようにしてもよい。このように、復路経路作成データの経由ノードキューに含まれるノードを含まないようにノードＴから自車位置への経路計算を行うことで、往路経路の経由地を経由しないように復路経路を探索することが可能である。
【００８３】
また、上記実施形態では、Ｓ２２０において、往路経路と復路経路とが一致する場合と、周回ルートの経路長が経路条件距離Ｘを超過してしまう場合のいずれかを例外条件経路として、探索された経路が例外経路であるか否かを判定する例を示したが、例えば、往路経路と復路経路とが一致する場合のみを例外経路として、探索された経路が例外経路であるか否かを判定してもよく、また、周回ルートの経路長が経路条件距離Ｘを超過してしまう場合のみを例外経路として、探索された経路が例外経路であるか否かを判定してもよい。
【００８４】
また、上記実施形態では、Ｓ２２８において、往路経路と復路経路を積算した道なり距離Ｌが、経路条件距離Ｘを基準とする予め定められた範囲内に含まれるか、経路条件距離Ｘを基準とする予め定められた範囲よりも短いか、あるいは経路条件距離Ｘを基準とする予め定められた範囲よりも長いか否かを比較判定する例を示したが、例えば、往路経路と復路経路を積算した道なり距離Ｌが、経路条件距離Ｘを基準とする予め定められた範囲よりも長いか否かについてのみ判定するようにしてもよい。
【００８５】
また、上記実施形態では、Ｓ２３０において、往路経路の最終経由地を１つ手前のノードに変更する例を示したが、例えば、２つ以上手前に変更するようにしてもよい。
【００８６】
なお、上記実施形態における構成と特許請求の範囲の構成との対応関係について説明すると、Ｓ１００、Ｓ１０２が設定手段に相当し、外部メモリ１８が記憶手段に相当し、Ｓ２００がスコア算出手段に相当し、Ｓ２０８〜Ｓ２２８、Ｓ２３０が経路探索手段に相当し、Ｓ２３２が周回ルート決定手段に相当し、Ｓ１０４がテーブル更新手段に相当し、Ｓ２３０が判定手段に相当する。
【図面の簡単な説明】
【００８７】
【図１】本発明の第１実施形態に係るルート探索装置の構成を示す図である。
【図２】ノード評価テーブルの構成例を示す図である。
【図３】経路計算リンクコスト係数テーブルの構成例を示す図である。
【図４】制御装置による経路条件項目の設定処理のフローチャートである。
【図５】経路条件項目例を示す図である。
【図６】制御装置による経路作成処理のフローチャートである。
【図７】往路経路作成データの一例を示す図である。
【図８】第１実施形態に係る往路経路探索と復路経路探索について説明するための図である。
【図９】往路経路作成データの一例を示す図である。
【図１０】第２実施形態に係る往路経路探索と復路経路探索について説明するための図である。
【符号の説明】
【００８８】
１…ナビゲーション装置、１０…位置検出器、１１…地磁気センサ、
１２…ジャイロスコープ、１３…距離センサ、１４…ＧＰＳ受信機、
１５…地図データ入力器、１６…操作スイッチ群、１７…制御装置、
１８…外部メモリ、１９…表示装置、２０…送受信機、２１…音声コントローラ、
２２…スピーカ、２３…音声認識装置、２４…マイク、２５…リモコンセンサ。
【技術分野】
【０００１】
本発明は、周回ルートを探索するルート探索装置に関する。
【背景技術】
【０００２】
従来、予め定められたルートを１又は複数記憶し、いずれか１つのルートを選択すると、そのルートを構成する複数の地点のいずれか１つを出発点にしてルートをめぐり元に戻ってくる経路を計算し、ユーザに表示する装置が提案されている（例えば、特許文献１参照）。
【特許文献１】特開平１１−１１８５００号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記特許文献１に記載の装置は、予め定められたルートの中から特定のルートを選択するようになっているため、必ずしもユーザの希望する経路長のルートが提示されるとは限らない。例えば、自車位置を出発地として所定経路長の周回ルートを探索してドライブしたい場合、上記特許文献１に記載の装置では、ユーザの満足する周回ルートを探索するのは困難である。
【０００４】
本発明は上記点に鑑みたもので、ユーザの希望する経路長の周回ルートを探索できるようにすることを目的とする。
【課題を解決するための手段】
【０００５】
本発明の第１の特徴は、出発地から任意のノードを経由地として当該出発地へ戻る周回ルートを探索するルート探索装置であって、周回ルートの経路長を設定する設定手段と、ノードの条件に対し、経由地としての選択しやすさの度合いを示すスコアが規定されたテーブルを記憶する記憶手段と、出発地を含む所定領域に存在するノードを抽出するとともに、抽出したノードの条件とテーブルに規定されたスコアに基づき、抽出した各ノードに対するスコアを算出するスコア算出手段と、周回ルートの経路長が設定手段によって設定された経路長を基準とする予め定められた範囲内となるように、スコア算出手段によって算出されたスコア順に抽出した各ノードの中から経由地を順次特定して往路経路を探索するとともに往路経路の最終経由地から出発地に至る復路経路を探索する経路探索手段と、経路探索手段によって探索された往路経路と復路経路を周回ルートとして決定する周回ルート決定手段と、を備えたことである。
【０００６】
このような構成では、周回ルートの経路長が設定された経路長を基準とする予め定められた範囲内となるように、算出されたスコア順に抽出した各ノードの中から経由地を順次特定して往路経路が探索されるとともに往路経路の最終経由地から出発地に至る復路経路が探索されるので、ユーザの希望する経路長の周回ルートを探索することができる。
【０００７】
また、本発明の第２の特徴は、設定手段は、更に、複数の優先すべき経路条件の中から少なくとも１つを経路条件項目として設定するもので、テーブルには、経路条件項目毎に対応するスコアが規定されており、設定手段によって経路条件項目の少なくとも１つが設定された場合、設定された経路条件項目に該当するノードが経由地として選択されやすくなるように、設定された経路条件項目に対応するテーブルのスコアを更新するテーブル更新手段と、を備えたことである。
【０００８】
このような構成では、設定された経路条件項目に該当するノードが経由地として選択されやすくなるように、設定された経路条件項目に対応するテーブルのスコアが更新されるので、設定された経路条件項目に該当するノードを優先的に経由地として選択した経路を探索することが可能である。
【０００９】
また、本発明の第３の特徴は、設定手段は、更に、指定された特定のノードをユーザ指定経由地として設定するもので、テーブルには、ユーザ指定経由地に対応するスコアが規定されており、設定手段によって特定のノードがユーザ指定経由地として設定された場合、テーブル更新手段は、設定された特定のノードが経由地として選択されやすくなるように、設定された特定のノードに対応するテーブルのスコアを更新することである。
【００１０】
このような構成では、設定された特定のノードが経由地として選択されやすくなるように、設定された特定のノードに対応するテーブルのスコアが更新されるので、設定された特定のノードを優先的に経由地として選択した経路を探索することが可能である。
【００１１】
また、本発明の第４の特徴は、経路探索手段は、設定手段によって設定された経路長の半分以上となるまで、抽出した各ノードの中から経由地を順次特定して往路経路を探索することである。
【００１２】
また、本発明の第５の特徴は、経路探索手段が、往路経路を探索する際に、同一スコアのノードが複数ある場合、近くのノードから先に経由地として特定することである。
【００１３】
また、本発明の第６の特徴は、経路探索手段は、経路探索手段によって探索された周回ルートの経路長が設定手段によって設定された経路長を基準とする予め定められた範囲よりも長いか否かを判定する判定手段を備え、判定手段によって周回ルートの経路長が設定手段によって設定された経路長を基準とする予め定められた範囲よりも長いと判定された場合、往路経路の最終経由地を手前のノードに変更して、往路経路および復路経路を探索することである。
【００１４】
このような構成では、周回ルートの経路長が設定手段によって設定された経路長を基準とする予め定められた範囲よりも長いと判定された場合、往路経路の最終経由地を手前のノードに変更して、往路経路および復路経路が探索されるので、よりユーザの希望する経路長の周回ルートを探索しやすくすることが可能である。
【発明を実施するための最良の形態】
【００１５】
（第１実施形態）
本発明の第１実施形態に係るルート探索装置の構成を図１に示す。本実施形態に係るルート探索装置はナビゲーション装置１として構成されている。本ナビゲーション装置１は、位置検出器１０、地図データ入力器１５、操作スイッチ群１６、外部メモリ１８、表示装置１９、送受信機２０、音声コントローラ２１、スピーカ２２、音声認識装置２３、マイク２４、リモコンセンサ２５と、これら各装置が接続された制御装置１７を備えている。
【００１６】
位置検出器１０は、いずれも周知の地磁気センサ１１、ジャイロスコープ１２、距離センサ１３およびＧＰＳ受信機１４等のセンサを有しており、これらセンサの各々の性質に基づいた自車位置を特定するための情報を制御装置１７に出力する。
【００１７】
地図データ入力器１５は、地図データが記憶された地図データ記憶媒体（図示せず）から、該地図データ記憶媒体に格納されている位置検出の精度向上のためのいわゆるマップマッチング用データ、地図データ及び目印データを含む各種データを入力するための装置である。地図データ記憶媒体としては、そのデータ量からＣＤ−ＲＯＭまたはＤＶＤ−ＲＯＭを用いるのが一般的であるが、メモリカード、ＨＤＤ等を用いてもよい。
【００１８】
操作スイッチ群１６は、表示装置１９のディスプレイに重ねて設けられたタッチスイッチおよび表示装置１９のディスプレイの周囲に設けられたメカニカルなスイッチ等によって構成され、ユーザの操作に応じた信号を出力する。
【００１９】
外部メモリ１８は、不揮発性の記憶媒体であり、電源をオフしても消去すべきでないデータや、制御装置１７の処理において頻繁に使用されるデータ等が記憶される。なお、外部メモリ１８としては、ハードディスクやメモリカード等の記憶媒体を用いるとよい。
【００２０】
表示装置１９は、液晶、有機ＥＬ等のフルカラー表示が可能なディスプレイを有し、制御装置１７から入力される映像信号に応じた映像をディスプレイに表示させる。
【００２１】
送受信機２０は、ＶＩＣＳセンタ５とデータの送受信を行うための装置である。送受信機置１２は、ＶＩＣＳセンタ５からの交通情報等を受信し、ＶＩＣＳセンタ５へ車両情報、ユーザ情報等を送信する。
【００２２】
音声認識装置２３は、マイク２４を介して入力される音声信号と、内部に記憶する認識辞書（図示せず）中の語彙データ（比較対象パターン）とを照合して音声認識を行い、音声認識の結果を音声コントローラ２１に入力する。
【００２３】
音声コントローラ２１は、音声認識装置２３の認識結果を制御装置１７へ出力するとともに、制御装置１７から入力される音声信号をスピーカ２２へ出力する。また、音声コントローラ２１は、マイク２４から入力される音声信号に応じた音声をスピーカ２２からトークバック出力（音声出力）させる。
【００２４】
リモコンセンサ２５は、ユーザの操作に基づいて赤外線等による無線信号を送信するリモコン２５ａから受信した信号を制御装置１７へ出力する。
【００２５】
制御装置１７は、ＣＰＵ、ＲＯＭ、ＲＡＭ、Ｉ／Ｏ等を備えたコンピュータとして構成されている。制御装置１７のＣＰＵは、ＲＯＭに記憶されたプログラムに従って各種処理を実行する。制御装置１７のＣＰＵが実行する処理としては、位置検出器１０から入力される情報に基づいて自車位置を特定する自車位置特定処理、地図縮尺を変更する地図縮尺変更処理、メニュー表示などを行うメニュー表示選択処理、ユーザの操作に応じて目的位置を設定する目的地設定処理、自車位置（出発地）から目的地に至る最適な案内経路を探索する経路探索処理、探索した案内経路に従って経路案内を行う経路案内処理、自車位置を修正する自車位置修正処理、スピーカ２２から出力する音量を調整する音量調整処理等がある。
【００２６】
上記した構成において、ユーザの操作に応じて目的地が設定されると、制御装置１７は、自車位置特定処理によって特定した自車位置から目的地に至る最適な案内経路を探索し、探索した案内経路を表示装置１９のディスプレイに表示させる。なお、最適な案内経路を探索する手法としては、ダイクストラ法などが知られている。
【００２７】
また、本実施形態おける制御装置１７は、出発地から任意のノードを経由地として当該出発地へ戻る周回ルートを探索する周回ルート探索処理を実施する機能を備えている。
【００２８】
本実施形態における外部メモリ１８には、ノードの条件に対し、経由地としての選択しやすさの度合いを示すスコアが規定されたノード評価テーブルおよび経路計算に用いられるリンクコスト係数が規定された経路計算リンクコスト係数テーブルが記憶されている。
【００２９】
図２に、ノード評価テーブルの構成例を示す。図に示すように、ノード評価テーブルには、海沿い、山道、裏道、ユーザ指定経由地等の各条件（基準）に対し、経由地としての選択しやすさの度合いを示すスコアが規定されている。なお、図２に示されているノード評価テーブルは一例であり、実際には、様々な条件（基準）に対してスコアが規定されている。また、本実施形態では、スコアが高いほど経由地として選択されやすくなっている。
【００３０】
図３に、経路計算リンクコスト係数テーブルの構成例を示す。図に示すように、経路計算リンクコスト係数テーブルには、車線数、道幅、信号機の有無、右左折などを条件（基準）とする各パラメータに対し、リンクコスト係数が規定されている。なお、本実施形態では、リンクコスト係数が低いほど探索されやすくなっている。
【００３１】
なお、ノード評価テーブルのスコアおよび経路計算リンクコスト係数テーブルのリンクコスト係数は、予め基準値が設定されているが、以下に示す経路条件項目の設定処理によって更新される。
【００３２】
図４に、制御装置１７による経路条件項目の設定処理のフローチャートを示す。ユーザの操作に応じて設定条件項目の設定処理の開始が指示されると、制御装置１７は、図４に示す処理を実施する。
【００３３】
まず、周回ルートの距離または時間を設定する（Ｓ１００）。ここでは、図５に示す経路条件項目例に示される周回ルートの経路長（キロメートル）または所要時間（分）を設定する。具体的には、周回ルートの経路長および周回ルートの所要時間を促す画面を表示させ、この画面に従って周回ルートの経路長が入力された場合には周回ルートの経路長をＲＡＭに記憶し、画面に従って周回ルートの所要時間が入力された場合には、所要時間を経路長に換算してＲＡＭに記憶する。
【００３４】
次に、ユーザ条件の設定を行う（Ｓ１０２）。具体的には、図５に示す経路条件項目例に示される海沿い優先、山道優先、裏道優先、燃費優先等、優先すべき経路条件の中から選択された項目を示すフラグをＲＡＭに記憶するとともに、特定のノードが経由地指定された場合には、経由地指定されたノードをＲＡＭに記憶する。
【００３５】
次に、先のＳ１０２にて設定されたユーザ条件に従って、ノード評価テーブルおよび経路計算リンクコスト係数テーブルを更新する（Ｓ１０４）。
【００３６】
海沿い優先を示すフラグがＲＡＭに記憶されている場合、図２に示したノード評価テーブルにおける海沿いに対するスコアを基準値から無限大に更新する。
【００３７】
同様に、山道優先を示すフラグがＲＡＭに記憶されている場合、ノード評価テーブルにおける山道優先に対するスコアを基準値から無限大に更新する。
【００３８】
また、裏道優先を示すフラグがＲＡＭに記憶されている場合、ノード評価テーブルにおける裏道優先に対するスコアを基準値から無限大に更新するとともに、図３に示した経路計算リンクコスト係数テーブルの「道幅狭い」と「道幅狭窄」の項目のリンクコスト係数を予め定められた値だけ低くする。
【００３９】
また、燃費優先を示すフラグがＲＡＭに記憶されている場合、図３に示した経路計算リンクコスト係数テーブルの「信号機無し」の項目のリンクコスト係数を予め定められた値だけ低くするとともに、「右左折する」の項目のリンクコスト係数を予め定められた値だけ高くする。
【００４０】
また、特定のノードが経由地指定された場合、ノード評価テーブルにおける経由地指定に対するスコアを基準値から無限大に更新する。
【００４１】
そして、ノード評価テーブルおよび経路計算リンクコスト係数テーブルの更新が終了すると、本処理を終了する。
【００４２】
本実施形態における制御装置１７は、上記した設定条件項目の設定処理設定条件項目の設定処理が終了した後、ユーザの操作によって周回ルート探索処理の開始が指示されると、図６に示す経路作成処理を開始する。
【００４３】
まず、自車位置より経路条件距離の距離にあるノードの評価を行う（Ｓ２００）。具体的には、Ｓ１００にて設定された周回ルートの経路長を経路条件距離Ｘとして、地図データから自車位置を中心とする半径Ｘ／２の領域に含まれるノードを抽出するとともに、抽出したノードの条件とノード評価テーブルに規定されたスコアに基づき、抽出した各ノードに対するスコアを算出する。例えば、経路条件距離Ｘが１０キロメートルの場合、自車位置を中心とする半径５キロメートルの領域に含まれる各ノードに対するスコアを算出する。
【００４４】
なお、本実施系形態では、図５に示した経路条件項目のうち、周回ルートの経路長（Ｘ＝１０キロメートル）のみが設定され、ノード評価テーブルのスコアおよび経路計算リンクコスト係数テーブルのリンクコスト係数は、予め設定された基準値のままとなっているものとして説明する。
【００４５】
次に、経路条件に合うノードがあるか否かを判定する（Ｓ２０２）。具体的には、自車位置を中心とする半径Ｘ／２の領域にノードが存在するか否かに基づいて経路条件に合うノードがあるか否かを判定する。
【００４６】
ここで、自車位置を中心とする半径Ｘ／２の領域にノードが存在しない場合、Ｓ２０２の判定はＮＯとなり、次に、設定された経路条件に従って周回ルートを探索できない旨をユーザへ通知し（Ｓ２０４）、本処理を終了する。
【００４７】
また、自車位置を中心とする半径Ｘ／２の領域にノードが存在する場合、Ｓ２０２の判定はＹＥＳとなり、以下、Ｓ２０６〜Ｓ２１８に示す処理において、図７に示す往路経路作成データを作成しながらＳ２００にて算出されたスコア順に抽出した各ノードの中から経由地を順次特定して往路経路を探索する処理を実施する。
【００４８】
まず、Ｓ２０６では、自車位置をノードＡとして設定する。具体的には、図６に示した往路経路作成データのノードＡに自車位置を設定する。
【００４９】
次に、ノードＢを抽出する（Ｓ２０８）。具体的には、Ｓ２００にて算出されたスコアの最も高いノードをノードＢとして特定する。なお、スコアの最も高いノードが複数ある場合には、自車位置に近いノードを優先的にノードＢとして抽出する。例えば、図８（ａ）に示すノード１１のスコアが最も高い場合、ノード１１をノードＢとして特定する。
【００５０】
次に、ノードＡとノードＢ間の経路計算を行う（Ｓ２１０）。ノードＡとノードＢ間の経路計算は、ノード間のリンク長および経路計算リンクコスト係数テーブルに規定されたリンクコスト係数に基づき、ダイクストラ法などを用いて探索することができる。
【００５１】
次に、経路計算結果から道なり距離Ｌを積算する（Ｓ２１２）。具体的には、ノードＡとノードＢ間の道なり距離Ｌを算出するとともに、往路経路作成データの道なり距離Ｌとして追加記憶する。
【００５２】
次に、経由ノードキューに経由するノードすべてを追加する（Ｓ２１４）。具体的には、ノードＢとして特定したノード番号を往路経路作成データの経由ノードキューとして追加記憶する。
【００５３】
次に、ノードＡをノードＢに置き換える（Ｓ２１６）。図７に示すように、往路経路作成データにおける前段のノードＢをノードＡとして設定する。
【００５４】
次に、道なり距離Ｌが経路条件距離Ｘ／２以上か否かを判定する（Ｓ２１８）。道なり距離Ｌが経路条件距離Ｘ／２未満の場合、Ｓ２１８の判定はＮＯとなり、Ｓ２０８へ戻り、上記した往路経路を探索する処理を繰り返し実施する。なお、上記した往路経路の探索処理では、同一のノードが複数回経由地として設定されないように、Ｓ２０８において往路経路作成データの経由ノードキューに含まれるノードはノードＢとして特定しないように制約が設けられている。
【００５５】
例えば、図８（ａ）において、ノード１１、ノード１２、ノード１３、ノード７、ノード６、ノード３、ノード２の順にスコアが高くなっている場合、図８（ｂ）に示すように、自車位置からノード１１、ノード１２、ノード１３、ノード７、ノード６、ノード３、ノード２が経由地として順次特定され、図７に示したような往路経路作成データが作成される。
【００５６】
そして、経路条件距離Ｘが１０キロメートルに設定されている場合、ノード２まで経由すると道なり距離Ｌが５．３キロメートルとなるため、Ｓ２１８の判定はＹＥＳとなり、次に、例外条件経路であるか否かを判定する（Ｓ２２０）。例外条件経路は、往路経路と後述する復路経路とが一致する場合と、周回ルートの経路長が経路条件距離Ｘを超過してしまう場合のいずれかである。ここでは、Ｓ２２６にてＮＯと判定されるものとして説明する。
【００５７】
以下、Ｓ２２２〜Ｓ２２６に示す処理において、図９に示すような復路経路作成データを作成しながら往路経路の最終経由地から自車位置に至る復路経路を探索する処理を実施する。
【００５８】
まず、往路経路作成データの経由ノードキューから往路経路の最終経由地となっているノード２を折り返し地点として復路経路作成データのノードＴに設定する（Ｓ２２２）。
【００５９】
次に、ノードＴから自車位置への経路計算を行う（Ｓ２２４）。ノードＴから自車位置への経路計算は、ノード間のリンク長および経路計算リンクコスト係数テーブルに規定されたリンクコスト係数などに基づき、ダイクストラ法などを用いて探索することができる。
【００６０】
次に、ノードＴから自車位置へ戻る復路経路の道なり距離Ｌを積算し（Ｓ２２６）、図９に示すように、計算した復路経路の道なり距離Ｌに往路経路の道なり距離Ｌを加算して復路経路作成データの道なり距離Ｌとして記憶する。
【００６１】
次に、往路経路と復路経路を積算した道なり距離Ｌが、経路条件距離Ｘを基準とする予め定められた範囲（例えば、Ｘ±５００メートル）内に含まれるか、経路条件距離Ｘを基準とする予め定められた範囲よりも短いか、あるいは経路条件距離Ｘを基準とする予め定められた範囲よりも長いか否かを比較判定する（Ｓ２２８）。
【００６２】
例えば、図８（ｃ）に示すようにノード２からノード５、ノード８、ノード１０、ノード１６を経由して自車位置に至る復路が探索され、往路経路と復路経路を積算した道なり距離Ｌが１２．３キロメートルとなった場合、往路経路と復路経路を積算した道なり距離Ｌが経路条件距離Ｘを基準とする予め定められた範囲（例えば、９．５キロメートル〜１０．５キロメートル）に含まれないと判定され、次に、往路経路の最終経由地を１つ手前のノードに変更する（Ｓ２３０）。例えば、図８（ｂ）に示されているようにノード２が往路経路の最終経由地として仮決定されている場合、往路経路の最終経由地をノード２の１つ手前のノード３に変更する。
【００６３】
そして、Ｓ２２２にて、復路経路作成データのノードＴをノード２からノード３に変更し、再度、復路経路を探索する。例えば、図８（ｄ）に示すようにノード３からノード１６を経由して自車位置に至る復路が探索され、その道なり距離Ｌが９．６キロメートルとなると、Ｓ２２８の判定は往路経路と復路経路を積算した道なり距離Ｌが、経路条件距離Ｘを基準とする予め定められた範囲内に含まれると判定され、次に、探索された往路経路と復路経路からなる周回ルートを案内経路として決定する（Ｓ２３２）。
【００６４】
なお、ユーザの操作により経路案内の開始が指示されると、制御装置１７は、探索した周回ルートに従って経路案内を行う経路案内処理を開始する。
【００６５】
また、Ｓ２２８にて、往路経路と復路経路を積算した道なり距離Ｌが、経路条件距離Ｘを基準とする予め定められた範囲よりも短いと判定された場合、Ｓ２０８へ戻り、再度、往路経路の探索処理を実施する。
【００６６】
また、Ｓ２２０〜Ｓ２２４の復路経路の探索処理の結果、周回ルートが例外条件経路となってしまう場合、Ｓ２２６の判定はＹＥＳとなり、例外経路になる旨をユーザに確認する（Ｓ２３４）。例えば、往路と復路が同じ周回ルートとなる場合には、「往路と復路が同じ周回ルートとなります」といったメッセージとともに「ＹＥＳ」、「ＮＯ」を選択可能に表示させる。また、周回ルートの経路長が経路条件距離よりも長くなる場合には、「周回ルートの経路長が経路条件距離よりも長くなります」といったメッセージとともに「ＹＥＳ」、「ＮＯ」を選択可能に表示させる。
【００６７】
ユーザの操作により、往路と復路が同じとなる周回ルートでもよいことが確認された場合、または周回ルートの経路長が経路条件距離よりも長くなってもよいことが確認された場合、Ｓ２３２へ進み、探索した経路を周回ルートとして決定する。
【００６８】
また、往路と復路が同じとなる周回ルートではよくないことが確認された場合、または周回ルートの経路長が経路条件距離を基準とする予め定められた範囲よりも長くなってはならないことが確認された場合、条件を満たさないことをユーザへ通知する（Ｓ２３６）。例えば、「条件を満たす周回ルートを探索できませんでした。再度、条件を変更して探索してください」といったメッセージを表示させ、探索した経路を周回ルートとして決定することなく、本処理を終了する。
【００６９】
上記した構成によれば、周回ルートの経路長が設定された経路長を基準とする予め定められた範囲内となるように、算出されたスコア順に抽出した各ノードの中から経由地を順次特定して往路経路が探索されるとともに往路経路の最終経由地から出発地に至る復路経路が探索されるので、ユーザの希望する経路長の周回ルートを探索することができる。
【００７０】
また、設定された経路条件項目に該当するノードが経由地として選択されやすくなるように、設定された経路条件項目に対応するテーブルのスコアが更新されるので、設定された経路条件項目に該当するノードを優先的に経由地として選択した経路を探索することが可能である。
【００７１】
また、設定された特定のノードが経由地として選択されやすくなるように、設定された特定のノードに対応するテーブルのスコアが更新されるので、設定された特定のノードを優先的に経由地として選択した経路を探索することが可能である。
【００７２】
また、周回ルートの経路長が設定された経路長を基準とする予め定められた範囲よりも長いと判定された場合、往路経路の最終経由地を手前のノードに変更して、往路経路および復路経路が探索されるので、よりユーザの希望する経路長の周回ルートを探索しやすくすることが可能である。
【００７３】
（第２実施形態）
本発明の第２実施形態に係るルート探索装置の構成は、図１に示した第１実施形態の構成と同じである。また、ルート探索装置の処理についても、図４、図６に示した第１実施形態の処理と同じである。上記第１実施形態では、図５に示した経路条件項目のうち、周回ルートの経路長のみが設定され、ノード評価テーブルのスコアおよび経路計算リンクコスト係数テーブルのリンクコスト係数は、予め設定された基準値のままとなっているものとして説明したが、本実施形態では、周回ルートの経路長が設定され、更に、海沿い優先が選択されたものとして説明する。
【００７４】
このように、ユーザの操作によっての海沿い優先が選択されると、図４に示した経路条件項目の設定処理によって、図２に示したノード評価テーブルにおける海沿いに対するスコアが基準値から無限大に更新される。
【００７５】
そして、図６に示した経路作成処理のＳ２００にて、海沿いに存在するノードのスコアが無限大となるように、地図データから自車位置を中心とする半径Ｘ／２の領域に含まれるノードのスコアが算出される。例えば、図１０（ａ）に示すように海沿いのノード１、ノード２、ノード３、ノード４、ノード５のスコアが無限大となるようにノードのスコアが算出される。
【００７６】
そして、図１０（ｂ）に示すように、自車位置から海沿いのノードの中で自車位置に最も近いノード３を経由してノード２に至る往路経路が探索される。すなわち、自車位置からノード１０、ノード１１、ノード３を経由してノード２に至る往路経路が探索される。
【００７７】
その後、ノード２を折り返し地点（ノードＴ）として、図１０（ｃ）に示すように、ノード２からノード７、ノード８、ノード９、ノード１０を経由して自車位置に至る復路経路が探索される。
【００７８】
このようにして、設定された周回ルートの経路長の予め定められた範囲内で、海沿いを優先した周回ルートが探索される。
【００７９】
（他の実施形態）
なお、本発明は上記実施形態に限定されるものではなく、本発明の趣旨に基づいて種々なる形態で実施することができる。
【００８０】
例えば、上記実施形態では、Ｓ２００にて、地図データから自車位置を中心とする半径Ｘ／２の領域に含まれるノードを抽出する例を示したが、例えば、自車位置を含む一定区画の領域に含まれるノードを抽出するようにしてもよい。
【００８１】
また、上記第１実施形態では、図８（ｂ）において、ノード１１、ノード１２、ノード１３、ノード７、ノード６、ノード３、ノード２のように隣接するノード順にスコアが高くなっている例を示したが、このように隣接するノード順にスコアが高くなっていなくても、スコアの高い順にノードをノードＢとして特定することができる。
【００８２】
また、上記第１実施形態では、Ｓ２２２において、復路経路作成データの経由ノードキューと関係なくノードＴから自車位置への経路計算を行う例を示したが、復路経路作成データの経由ノードキューに含まれるノードを含まないようにノードＴから自車位置への経路計算を行うようにしてもよい。このように、復路経路作成データの経由ノードキューに含まれるノードを含まないようにノードＴから自車位置への経路計算を行うことで、往路経路の経由地を経由しないように復路経路を探索することが可能である。
【００８３】
また、上記実施形態では、Ｓ２２０において、往路経路と復路経路とが一致する場合と、周回ルートの経路長が経路条件距離Ｘを超過してしまう場合のいずれかを例外条件経路として、探索された経路が例外経路であるか否かを判定する例を示したが、例えば、往路経路と復路経路とが一致する場合のみを例外経路として、探索された経路が例外経路であるか否かを判定してもよく、また、周回ルートの経路長が経路条件距離Ｘを超過してしまう場合のみを例外経路として、探索された経路が例外経路であるか否かを判定してもよい。
【００８４】
また、上記実施形態では、Ｓ２２８において、往路経路と復路経路を積算した道なり距離Ｌが、経路条件距離Ｘを基準とする予め定められた範囲内に含まれるか、経路条件距離Ｘを基準とする予め定められた範囲よりも短いか、あるいは経路条件距離Ｘを基準とする予め定められた範囲よりも長いか否かを比較判定する例を示したが、例えば、往路経路と復路経路を積算した道なり距離Ｌが、経路条件距離Ｘを基準とする予め定められた範囲よりも長いか否かについてのみ判定するようにしてもよい。
【００８５】
また、上記実施形態では、Ｓ２３０において、往路経路の最終経由地を１つ手前のノードに変更する例を示したが、例えば、２つ以上手前に変更するようにしてもよい。
【００８６】
なお、上記実施形態における構成と特許請求の範囲の構成との対応関係について説明すると、Ｓ１００、Ｓ１０２が設定手段に相当し、外部メモリ１８が記憶手段に相当し、Ｓ２００がスコア算出手段に相当し、Ｓ２０８〜Ｓ２２８、Ｓ２３０が経路探索手段に相当し、Ｓ２３２が周回ルート決定手段に相当し、Ｓ１０４がテーブル更新手段に相当し、Ｓ２３０が判定手段に相当する。
【図面の簡単な説明】
【００８７】
【図１】本発明の第１実施形態に係るルート探索装置の構成を示す図である。
【図２】ノード評価テーブルの構成例を示す図である。
【図３】経路計算リンクコスト係数テーブルの構成例を示す図である。
【図４】制御装置による経路条件項目の設定処理のフローチャートである。
【図５】経路条件項目例を示す図である。
【図６】制御装置による経路作成処理のフローチャートである。
【図７】往路経路作成データの一例を示す図である。
【図８】第１実施形態に係る往路経路探索と復路経路探索について説明するための図である。
【図９】往路経路作成データの一例を示す図である。
【図１０】第２実施形態に係る往路経路探索と復路経路探索について説明するための図である。
【符号の説明】
【００８８】
１…ナビゲーション装置、１０…位置検出器、１１…地磁気センサ、
１２…ジャイロスコープ、１３…距離センサ、１４…ＧＰＳ受信機、
１５…地図データ入力器、１６…操作スイッチ群、１７…制御装置、
１８…外部メモリ、１９…表示装置、２０…送受信機、２１…音声コントローラ、
２２…スピーカ、２３…音声認識装置、２４…マイク、２５…リモコンセンサ。
【特許請求の範囲】
【請求項１】
出発地から任意のノードを経由地として当該出発地へ戻る周回ルートを探索するルート探索装置であって、
前記周回ルートの経路長を設定する設定手段と、
前記ノードの条件に対し、経由地としての選択しやすさの度合いを示すスコアが規定されたテーブルを記憶する記憶手段と、
前記出発地を含む所定領域に存在するノードを抽出するとともに、前記抽出したノードの条件と前記テーブルに規定された前記スコアに基づき、前記抽出した各ノードに対するスコアを算出するスコア算出手段と、
前記周回ルートの経路長が前記設定手段によって設定された前記経路長を基準とする予め定められた範囲内となるように、前記スコア算出手段によって算出された前記スコア順に前記抽出した各ノードの中から経由地を順次特定して往路経路を探索するとともに前記往路経路の最終経由地から前記出発地に至る復路経路を探索する経路探索手段と、
前記経路探索手段によって探索された前記往路経路と前記復路経路を前記周回ルートとして決定する周回ルート決定手段と、を備えたことを特徴とするルート探索装置。
【請求項２】
前記設定手段は、更に、複数の優先すべき経路条件の中から少なくとも１つを経路条件項目として設定するもので、
前記テーブルには、前記経路条件項目毎に対応するスコアが規定されており、
前記設定手段によって前記経路条件項目の少なくとも１つが設定された場合、設定された前記経路条件項目に該当するノードが前記経由地として選択されやすくなるように、設定された前記経路条件項目に対応する前記テーブルの前記スコアを更新するテーブル更新手段と、を備えたことを特徴とする請求項１に記載のルート探索装置。
【請求項３】
前記設定手段は、更に、指定された特定のノードをユーザ指定経由地として設定するもので、
前記テーブルには、前記ユーザ指定経由地に対応するスコアが規定されており、
前記設定手段によって前記特定のノードが前記ユーザ指定経由地として設定された場合、前記テーブル更新手段は、設定された前記特定のノードが前記経由地として選択されやすくなるように、設定された前記特定のノードに対応する前記テーブルの前記スコアを更新することを特徴とする請求項１または２に記載のルート探索装置。
【請求項４】
前記経路探索手段は、前記設定手段によって設定された前記経路長の半分以上となるまで、前記抽出した各ノードの中から経由地を順次特定して往路経路を探索することを特徴とする請求項１ないし３のいずれか１つに記載のルート探索装置。
【請求項５】
前記経路探索手段は、前記往路経路を探索する際に、同一スコアのノードが複数ある場合、近くのノードから先に前記経由地として特定することを特徴とする請求項１ないし４のいずれか１つに記載のルート探索装置。
【請求項６】
前記経路探索手段は、前記経路探索手段によって探索された前記周回ルートの経路長が前記設定手段によって設定された前記経路長を基準とする予め定められた範囲よりも長いか否かを判定する判定手段を備え、
前記判定手段によって前記周回ルートの経路長が前記設定手段によって設定された前記経路長を基準とする予め定められた範囲よりも長いと判定された場合、前記往路経路の最終経由地を手前のノードに変更して、前記往路経路および前記復路経路を探索することを特徴とする請求項１ないし５のいずれか１つに記載のルート探索装置。
【請求項１】
出発地から任意のノードを経由地として当該出発地へ戻る周回ルートを探索するルート探索装置であって、
前記周回ルートの経路長を設定する設定手段と、
前記ノードの条件に対し、経由地としての選択しやすさの度合いを示すスコアが規定されたテーブルを記憶する記憶手段と、
前記出発地を含む所定領域に存在するノードを抽出するとともに、前記抽出したノードの条件と前記テーブルに規定された前記スコアに基づき、前記抽出した各ノードに対するスコアを算出するスコア算出手段と、
前記周回ルートの経路長が前記設定手段によって設定された前記経路長を基準とする予め定められた範囲内となるように、前記スコア算出手段によって算出された前記スコア順に前記抽出した各ノードの中から経由地を順次特定して往路経路を探索するとともに前記往路経路の最終経由地から前記出発地に至る復路経路を探索する経路探索手段と、
前記経路探索手段によって探索された前記往路経路と前記復路経路を前記周回ルートとして決定する周回ルート決定手段と、を備えたことを特徴とするルート探索装置。
【請求項２】
前記設定手段は、更に、複数の優先すべき経路条件の中から少なくとも１つを経路条件項目として設定するもので、
前記テーブルには、前記経路条件項目毎に対応するスコアが規定されており、
前記設定手段によって前記経路条件項目の少なくとも１つが設定された場合、設定された前記経路条件項目に該当するノードが前記経由地として選択されやすくなるように、設定された前記経路条件項目に対応する前記テーブルの前記スコアを更新するテーブル更新手段と、を備えたことを特徴とする請求項１に記載のルート探索装置。
【請求項３】
前記設定手段は、更に、指定された特定のノードをユーザ指定経由地として設定するもので、
前記テーブルには、前記ユーザ指定経由地に対応するスコアが規定されており、
前記設定手段によって前記特定のノードが前記ユーザ指定経由地として設定された場合、前記テーブル更新手段は、設定された前記特定のノードが前記経由地として選択されやすくなるように、設定された前記特定のノードに対応する前記テーブルの前記スコアを更新することを特徴とする請求項１または２に記載のルート探索装置。
【請求項４】
前記経路探索手段は、前記設定手段によって設定された前記経路長の半分以上となるまで、前記抽出した各ノードの中から経由地を順次特定して往路経路を探索することを特徴とする請求項１ないし３のいずれか１つに記載のルート探索装置。
【請求項５】
前記経路探索手段は、前記往路経路を探索する際に、同一スコアのノードが複数ある場合、近くのノードから先に前記経由地として特定することを特徴とする請求項１ないし４のいずれか１つに記載のルート探索装置。
【請求項６】
前記経路探索手段は、前記経路探索手段によって探索された前記周回ルートの経路長が前記設定手段によって設定された前記経路長を基準とする予め定められた範囲よりも長いか否かを判定する判定手段を備え、
前記判定手段によって前記周回ルートの経路長が前記設定手段によって設定された前記経路長を基準とする予め定められた範囲よりも長いと判定された場合、前記往路経路の最終経由地を手前のノードに変更して、前記往路経路および前記復路経路を探索することを特徴とする請求項１ないし５のいずれか１つに記載のルート探索装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２００８−１２８７７９（Ｐ２００８−１２８７７９Ａ）
【公開日】平成２０年６月５日（２００８．６．５）
【国際特許分類】
【出願番号】特願２００６−３１３００５（Ｐ２００６−３１３００５）
【出願日】平成１８年１１月２０日（２００６．１１．２０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
【公開日】平成２０年６月５日（２００８．６．５）
【国際特許分類】
【出願日】平成１８年１１月２０日（２００６．１１．２０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
[ Back to top ]