経路探索装置および経路探索方法
【課題】ユーザが出発地から目的地まで往復移動する場合であってもユーザの精神的負担を極力軽減できるようにした経路探索装置および経路探索方法を提供する。
【解決手段】制御装置は、往路の経路を探索するときに、往路および復路が一致する条件を満たす往路の総コストと、当該往路の総コストが最小となる往路の最小総コスト（Ｒａ＿ｍｉｎ）との差（ΔＲａ）が第１所定値未満（Ｔ１３）となる往路および復路に絞り込む。そして、往路および復路が一致する条件を満たす復路の総コストと、当該復路の総コストが最小となる最小総コスト（Ｒｂ＿ｍｉｎ）との差（ΔＲｂ）が第２所定値未満（Ｔ１５）の条件を満たす往路および復路について往復経路の探索結果とする。
【解決手段】制御装置は、往路の経路を探索するときに、往路および復路が一致する条件を満たす往路の総コストと、当該往路の総コストが最小となる往路の最小総コスト（Ｒａ＿ｍｉｎ）との差（ΔＲａ）が第１所定値未満（Ｔ１３）となる往路および復路に絞り込む。そして、往路および復路が一致する条件を満たす復路の総コストと、当該復路の総コストが最小となる最小総コスト（Ｒｂ＿ｍｉｎ）との差（ΔＲｂ）が第２所定値未満（Ｔ１５）の条件を満たす往路および復路について往復経路の探索結果とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路を探索するための経路探索装置および経路探索方法に関する。
【背景技術】
【０００２】
この種の経路探索装置は様々な態様で開発が進んでいる（例えば特許文献１〜２参照）。特許文献１の技術思想では、過去の走行経路を誘導経路として設定することを提案しており、過去に走行したことがある走行経路の終端に相当する地点を出発地とし、走行経路の始端に相当する地点を目的地として誘導経路を設定している。また、特許文献２記載の技術思想では、算出した経路に対する実際の離脱走行経路を記憶し、次回の算出経路に反映するようにしている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１０−８９９９６号公報
【特許文献２】特開２００１−１２４５７８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ユーザが出発地から目的地まで道路を往復する場合、初めて通過する道路は途中の道路状況の知識がないため往復移動中の精神的負担が強い。そこで、前述の特許文献の技術思想では、往復移動するときに往路と同一の道路を復路として設定することでユーザの精神的負担を緩和するようにしている。
【０００５】
しかしながら、前述の特許文献の技術思想では、往路の走行経路が例えば一方通行などであり、復路を走行すると交通規則に反する部分が存在するとき、交通規則に従い迂回するようにしているため、総コストの高い復路を案内されたり、往路とは相当異なる復路が案内される場合もある。この場合、出発地から目的地まで往復移動する場合、ユーザの精神的負担は緩和されない。
【０００６】
本発明は、上記事情に鑑みてなされたもので、その目的は、ユーザが出発地から目的地まで往復移動する場合、ユーザの精神的負担を極力軽減できるようにした経路探索方法および経路探索装置を提供することにある。
【課題を解決するための手段】
【０００７】
請求項１，１１記載の発明によれば、往路と復路が一致する条件を満たす往復経路のうち、往路の総コストが最小となる往復経路を特定し、特定した最小総コストとの差が第１所定値未満となる総コストの往路からなる往復経路を抽出して探索結果の候補とするため、往路および復路が一致する往復経路について往路の総コストが極力少なくなるように絞り込むことができる。
【０００８】
さらに、抽出された往復経路のうち、復路の総コストが最小となる往復経路を特定し、特定した最小総コストとの差が第２所定値未満となる総コストの復路からなる往復経路を抽出して往復経路の探索結果とするため、往路および復路が一致する経路について復路の総コストが極力少なくなるように絞り込むことができる。このため、ユーザは、往路に一致した復路であって総コストが極力少なくなる復路を戻ることができ、経路の設定時点においても経路を往復移動するときにもユーザの安心感を増すことができる。これにより、ユーザの精神的負担を極力軽減できる。
【０００９】
請求項２記載の発明によれば、請求項１記載の条件を満たすと共に、さらに往路および復路の総コストの総和の最も少ない往路および復路を往復経路の探索結果とするため、往復経路の総負荷の少ない経路を設定することができ、ユーザの精神的負担を軽減できる。
【００１０】
請求項３記載の発明によれば、ユーザが往路を通過する時間帯を考慮して復路の総コストを算出するため、ユーザの実移動態様に合わせて往路の総コストを算出でき、より実用的な経路を探索できる。
【００１１】
請求項４記載の発明によれば、ユーザが復路を通過する時間帯を考慮して復路の総コストを算出するため、ユーザの実移動態様に合わせて復路の総コストを算出でき、より実用的な経路を探索できる。
【００１２】
請求項５記載の発明によれば、過去に移動したことがある経験経路を部分的に適用し、過去に移動したことがない経路について部分的に往路および復路が一致する経路を探索するため、ユーザは過去に経験した道路を含む経路を往復移動することになるため、ユーザは安心感を増すことができ、ユーザの精神的負担を極力軽減できる。
【００１３】
請求項６、８−１１記載の発明によれば、所定の条件を満たすときに経路が一致すると判定しているため、より実用的な経路を探索できる。
請求項７記載の発明によれば、往路と復路が一致する往復経路の往路の到着時間と、往路の最短到着時間との間で第１所定時間以上の乖離がある場合、または／および、往路と復路が一致する往復経路の復路の到着時間と復路の最短到着時間との間で第２所定時間以上の乖離がある場合、は、往路と復路が一致する経路とその往路／復路の到着時間と、往路／復路ごとの最短到着経路とその往路／復路の到着時間を探索し通知する。
【００１４】
このため、ユーザは、往路および復路が一致する場合の往復経路およびその往路および復路の到着時間、と共に、往路／復路ごとの最短到着経路とその往路／復路の到着時間を知ることができ、ユーザが所望の経路を選択して通行することができる。
【００１５】
なお、本発明における「往路の総コスト」「復路の総コスト」とは、移動体が例えば車両の場合、ユーザが往路または復路を運転した場合の総負荷について数値により示したものである。例えば、出発地から目的地までの総コストは、当該出発地から目的地までの距離、通行道路の車線数、右折数、左折数、通行道路の渋滞の有無およびその程度、通行道路の車両通行規制、合流の有無やその回数、レーン変更回数などの少なくとも一部または全部の要素を、総じて数値に置き換えてカウントした結果を示している。
【００１６】
したがって、これらの総コストが高ければ例えば車両の場合には運転の負荷が高く、総コストが低ければ運転の負荷が低い。例えば車両ではなく、歩行者が所持する経路探索装置の場合であっても、出発地から目的地までの距離が長ければ移動負荷が高く、距離が短ければ移動負荷が低いため、歩行者などが経路探索装置を所持する場合でも本発明は同様に適用できる。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１実施形態における電気的構成を概略的に示すブロック図
【図２】リンクの定義の説明図
【図３】経路案内処理を説明するフローチャート
【図４】経路探索処理を説明するフローチャート
【図５】往路および復路の一致を説明するための説明図
【図６】往復経路の総コストの総和の一例を示す説明図
【図７】経路の一例を示す説明図
【図８】比較例を示す図７相当図
【図９】本発明の第２実施形態における経路設定例を示す説明図
【図１０】移動履歴情報の一例を示す図
【図１１】本発明の第３実施形態を示すシステム構成図
【発明を実施するための形態】
【００１８】
（第１実施形態）
以下、本発明の経路探索方法、経路探索装置を車両用ナビゲーション装置に適用した第１実施形態について図１ないし図８を参照しながら説明する。図１は、車両用ナビゲーション装置の電気的構成を概略的なブロック図によって示している。
【００１９】
図１に示すように、車両用ナビゲーション装置１は制御装置２を備え、当該制御装置（制御ユニット）２に、位置検出器３、地図データ入力器４、操作スイッチ群５、ＶＩＣＳ（登録商標）受信機６、通信装置７、外部メモリ８、表示装置９、音声コントローラ１０、音声認識部１１、リモコンセンサ１２を接続して構成される。リモコンセンサ１２にはリモコン１３が赤外線接続され、音声コントローラ１０にはスピーカ１４が接続され、音声認識部１１にはマイク１５が接続される。
【００２０】
制御装置２は、例えばマイクロコンピュータを主体として構成されたものであり、ＣＰＵ、ＲＡＭ、ＲＯＭ及びＩ／Ｏバス（何れも図示せず）を備え、各種の制御プログラムを実行して装置全体の動作を制御する。経路探索装置Ａは、制御装置２が実行するソフトウェアにより実現されるものである。
【００２１】
位置検出器３は、Ｇセンサ３ａ、ジャイロスコープ３ｂ、距離センサ３ｃ、ＧＰＳ受信機３ｄ等を備えて構成され、これらの各構成要素は互いに性質の異なる検出誤差を有している。制御装置２はこれら各構成要素から入力した検出信号を互いに補間して車両の現在位置を特定する。
【００２２】
この場合、位置検出器３は、要求される検出精度で車両の現在位置を検出可能であれば、これら全ての構成要素を備える必要はなく、又、ステアリングの舵角を検出するステアリングセンサや各車輪の回転を検出する車輪センサ等が組み合わされて構成されていても良い。
【００２３】
地図データ入力器４は、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、メモリカード又はＨＤＤ等の記録媒体を装着し、地図データやマップマッチング用データ等を入力する。操作スイッチ群５は、表示装置９の周辺に配置されるメカニカルキーや表示装置９の表示画面上に形成されるタッチキーから構成され、例えばユーザが何らかの操作（例えばメニュー表示選択、目的地設定、経路探索、経路案内開始、表示画面変更及び音量調整等）を行った旨を検出すると、操作検出信号を制御装置２に出力する。
【００２４】
ＶＩＣＳ受信機６は、広域通信網を通じて広域通信を行い、ＶＩＣＳセンター装置（図示せず）から送信されたＶＩＣＳ情報について広域通信網を通じて受信する。外部メモリ８は、ＨＤＤ等の大容量記憶装置から構成されている。
【００２５】
表示装置９は、例えばカラー液晶ディスプレイにより構成され、メニュー選択画面、目的地設定画面、経路案内画面等の各種の表示画面を表示すると共に、車両の現在位置を表す現在位置マークや走行軌跡等を地図データの地図上に重ねて表示する。尚、表示装置９は、有機ＥＬやプラズマディスプレイ装置等から構成されていても良い。
【００２６】
音声コントローラ１０は、例えば警告音や経路案内の案内音声等をスピーカ１４から出力させる。音声認識部１１は、制御装置２により動作が制御され、起動状態ではマイク１５から入力した音声を音声認識アルゴリズムにしたがって音声認識可能な状態とする。リモコンセンサ１２は、リモコン１３から送信された操作検出信号を受信すると、その受信した操作検出信号を制御装置２に出力する。
【００２７】
制御装置２は、地図データを取得する地図データ取得部、車両の現在位置と地図データ取得部により取得された地図データ内の道路データとを使用して車両の現在位置が存在する道路を特定するマップマッチング部、マップマッチング部により特定された車両の現在位置からユーザにより設定された目的地までの経路を探索する経路探索部２ａ、経路探索部により探索された経路及び地図データ内の道路データや交差点の位置データ等に基づいて経路案内に必要な地点を算出して経路案内する経路案内部、車両の現在位置周辺の地図や高速道路の略図や交差点付近の拡大図等を描画する表示制御部等を備えている。経路探索部２ａが経路探索手段として動作する。
【００２８】
図２は、地図データとして記憶される道路データの概要を示している。
地図データは、各交差点Ｃの中央に設定されるノードＮや、このノードＮ間を結合するリンクＬを含んだ道路データにより構成される。例えば、片側一車線の直線道路では、図２に示されるように、車両Ｃａが左側通行している場合を考慮すると、各交差点Ｃの中央に設定されたノードＮ間を結合するリンクＬが道路幅方向の中央に設定されている。
【００２９】
このリンクＬには、複数のノードＮ間を結合する間に複数の形状点が設定されており、当該複数の形状点に対応して形状データ（例えば幅、高さ等）が設定されており、当該形状データに応じた道路データが記憶されている。リンクＬには、それぞれリンクＩＤ（リンク識別情報）が付されており、交差点Ｃを結合する道路毎、道幅の異なる道路毎にそれぞれ異なるＩＤ（識別情報）が付された状態で管理されている。
【００３０】
上記構成において、ユーザが出発地において出発地と目的地との間で往路Ｒａおよび復路Ｒｂを往復設定した場合の経路探索方法について説明する。
一般に、ユーザがナビゲーション機能の経路案内を利用するときには、例えば未知の道路を走行する場合に使用する。特に女性などの特定ユーザは、出発地（現在位置）から目的地まで往復移動し、他施設に寄り道することなく移動できれば良い場合もある。このような場合、出発地から目的地までの往路Ｒａを設定するときに、往路Ｒａおよび復路Ｒｂの双方（往復経路）を設定できると良い。すると、ユーザは、往路Ｒａを走行した経験を活かして復路Ｒｂを戻ることができるため、往路Ｒａを走行するときにも復路Ｒｂを走行するときにも安心感が得られる。そこで、本実施形態では、出発地において出発地から目的地までの往路Ｒａを設定するとき、往路Ｒａおよび復路Ｒｂを共に設定可能に構成している。
【００３１】
図３は、経路案内処理をフローチャートにより概略的に示している。まず、操作スイッチ群５のユーザ操作により目的地が設定される（Ｓ１）。目的地が設定されると、制御装置２は、現在位置から目的地に至るまでの往復の経路探索処理を行う（Ｓ２）。この経路探索処理では、出発地（現在位置）から目的地に至るまでの往路Ｒａの探索と共に目的地から出発地（現在位置）に戻るまでの復路Ｒｂの探索も行う。
【００３２】
図４は、経路探索処理をフローチャートにより示している。まず、経路探索処理において、制御装置２は出発地（現在位置）から目的地までの往路Ｒａについてダイクストラ法を用いて探索する（Ｔ１）。次に、制御装置２は目的地から現在位置までの往路Ｒａに一致した復路Ｒｂを探索し（Ｔ２）、往路Ｒａと復路Ｒｂが一致する経路（往復経路）が存在するか否かを判定する（Ｔ３）。
【００３３】
ここで、「往路と復路（往復経路）が一致」とは、以下の（１）〜（３）のうち少なくとも（１）を含む何れか１または複数、または全部を含む条件を満たすことを示している。
【００３４】
（１）往路Ｒａおよび復路Ｒｂが同一リンクＩＤのリンクＬであれば往路Ｒａおよび復路Ｒｂが一致。
（２）往路Ｒａおよび復路Ｒｂが異なるリンクＩＤであっても、以下の（Ａ）〜（Ｄ）の条件を全て満たす場合に一致。
【００３５】
（Ａ）道路名称が同じ（名称が無い場合は、この条件は除外）
（Ｂ）道路種別が同じ
（Ｃ）それぞれのリンクＬの逆方向ベクトルの方位差が所定値以内
（Ｄ）それぞれのリンクＬ間の距離が所定距離以内
（３）高速道路のインターチェンジ（ＩＣ）、ジャンクション（ＪＣＴ）についてリンクＬがそれぞれ構成されている場合には、当該インターチェンジのリンクＬの前後のリンクＬ、ジャンクションのリンクＬの前後のリンクＬについて（２）の条件を満たせば一致と判定する。（２）の条件としては、（Ｅ）それぞれのリンクＬが共に一方通行で、且つ通行可能方向が双方逆向き、の条件を加入して考慮しても良い。
【００３６】
（１）の条件は、例えば、図２に示すように、片道一車線の道路などにリンクＬが一つ設定されていることを考慮しているものであり、この場合、リンクＩＤは一致するため、往路Ｒａおよび復路Ｒｂが一致すると判定する。（２）の条件は、互いに離間した互いに逆方向に走行可能な道路を対象としている。
【００３７】
図５は（２）の条件説明を示している。図５に示す道路Ｒ１は図示上方向に一方通行であり、道路Ｒ２は図示下方向に一方通行となっている。これは、例えば高速道路などのように道路Ｒ１および道路Ｒ２間に障害物が存在し、当該障害物を避けて道路が設けられている場合を考慮している。
【００３８】
地図データには各道路Ｒ１、Ｒ２毎に別々のリンクＬ１、Ｌ２が付されていることがあり、これらのリンクＬ１、Ｌ２が道路Ｒ１、Ｒ２別に記憶されていることがある。この場合には、道路Ｒ１の通行方向と道路Ｒ２の通行方向とはほぼ逆方向となっている。
【００３９】
このようなときには、地図データには（２）の（Ａ）に示すように、道路名称が同じに設定されている場合や、道路名称が何れにも付されていない場合もある。また、地図データには（２）の（Ｂ）に示すように、道路種別（国道、県道、市道など）が同一に設定されている。そこで、（２）の（Ａ）、（Ｂ）をそれぞれ条件の一つとして往路Ｒａおよび復路Ｒｂが一致するか否かを判定すると良い。
【００４０】
また、図５に示す道路Ｒ１と道路Ｒ２の方位は互いにほぼ逆方向であるもののわずかに方位差が存在する。そこで、（２）の（Ｃ）に示すように、リンクＬの逆方向ベクトルの方位差θが所定値以内に設定されていることを条件として往路Ｒａおよび復路Ｒｂが一致すると判定すると良い。
【００４１】
また、図５に示すように、道路Ｒ１と道路Ｒ２の方位が互いにほぼ逆方向に設定されているものの、道路Ｒ１と道路Ｒ２との間に距離Ｗは多少離れている。そこで、（２）の（Ｄ）に示すように、各リンクＬ間の距離Ｗが所定距離以内に配置されることを条件として往路Ｒａおよび復路Ｒｂが一致すると判定しても良い。このような（２）の（Ｃ）、（Ｄ）を条件の一つとすると良い。このような（２）の条件を加えることにより、ユーザが普段道路を通行するときの印象に極力合致するように「一致した往路Ｒａおよび復路Ｒｂ（往復経路）」を判定でき的確な経路の判定処理を行うことができる。
【００４２】
すなわち、「往路および復路（往復経路）が一致する経路」とは、（１）に示すように、片側一車線、片側複数車線など車両Ｃａが互いに対向して通行可能でリンクＬが一つしか設定されていない道路に限られず、必要に応じて前述の所定の（２）の（Ａ）〜（Ｄ）の条件を満たした場合にも適用できる。
【００４３】
図４に戻って、制御装置２は往路Ｒａと復路Ｒｂが一致した経路が存在すると判定した場合（Ｔ３：ＹＥＳ）には、次のステップＴ４以降の処理を行う。ステップＴ４において、制御装置２は、往路Ｒａの総コストを算出する（Ｔ４）。この往路Ｒａの総コストは、ユーザが往路Ｒａを車両運転した場合の運転負荷を一つの指標により示している。
【００４４】
例えば、出発地（現在位置）から目的地までの総コストは、当該出発地（現在位置）から目的地までの距離、通行道路の車線数、右折数、左折数、通行道路の渋滞の有無およびその程度、通行道路の車両通行規制、合流の有無やその回数、レーン変更回数などの各要素を、総じて数値に置き換えてカウントした結果を示している。なお、これらの要素のうち少なくとも一部をカウントするようにしても良い。
【００４５】
例えば、日本の場合、「右折」は対向車線を走行する車両等に配慮する必要があり、「左折」はその必要がないため、「右折」は「左折」よりも運転負荷（コスト）が高く設定される。また、通行道路が渋滞すると、運転者のストレスが高まるため、運転負荷のコストが高く設定されている。このように各道路には、その道路態様や道路状況などに応じてコストを算出でき、ステップＴ４において、制御装置２は往路Ｒａの総コストを算出することにより道路状況を数値により置き換えることができる。往路Ｒａと復路Ｒｂについて同一道路を走行する場合にも右折数や左折数が異なるため、同一道路を走行した場合でも総コストが異なる。
【００４６】
次に、往路Ｒａの総コストが最小総コスト（Ｒａ＿ｍｉｎ）を下回ったか否かを判定し（Ｔ５）、下回っていれば往路Ｒａの最小総コスト（Ｒａ＿ｍｉｎ）を更新する（Ｔ６）。このステップＴ５およびＴ６の処理は、往路Ｒａおよび復路Ｒｂの一致した条件を満たす往復経路の中でユーザの運転負荷が最も少ない往路Ｒａを判定するために行われる。
【００４７】
次に、復路Ｒｂの総コストを算出し（Ｔ７）、復路Ｒｂの総コストが最小総コスト（Ｒｂ＿ｍｉｎ）を下回ったか否かを判定し（Ｔ８）、下回っていれば復路Ｒｂの最小総コスト（Ｒｂ＿ｍｉｎ）を更新する（Ｔ９）。これらのステップＴ７〜Ｔ９の処理は、往路Ｒａおよび復路Ｒｂの一致した条件を満たす往復経路の中でユーザの運転負荷が最も少ない復路Ｒｂを判定するために行われる。
【００４８】
そして、現在位置から目的地まで往路Ｒａおよび復路Ｒｂ（往復経路）が互いに一致した全ての経路を探索してコストを算出完了したか否かを判定し（Ｔ１０）、現在位置から目的地まで往復経路が一致した全往路Ｒａ、復路Ｒｂの総コストを算出完了していれば（Ｔ１０：ＹＥＳ）、ステップＴ１１の処理に進む。算出完了しなければ（Ｔ１０：ＮＯ）、ステップＴ１に戻って処理を繰り返す。これにより、現在位置から目的地までの往復経路を全て探索し、当該往復経路に応じた往路Ｒａの最小総コスト（Ｒａ＿ｍｉｎ）と、復路Ｒｂの最小総コスト（Ｒｂ＿ｍｉｎ）を算出できる。
【００４９】
次に、往路Ｒａの総コストと往路Ｒａに一致する復路Ｒｂの総コストの総和を算出し、昇順に並べ換える（Ｔ１１）。この理由は、往復経路の総運転負荷が軽い順に並べ換えるためである。図６は、往復経路の総コストの総和を昇順に並べ替えた後の一例を示している。この図６において、往路Ｒａ、復路Ｒｂに添え字「１」〜「４」を付して経路を表している。これらが同一の添え字となる往路Ｒａおよび復路Ｒｂは、往路Ｒａおよび復路Ｒｂが一致すると判定された経路を示している。すなわち、例えば往路Ｒａ２と復路Ｒｂ２とはステップＴ３において「一致」と判定されており、往路Ｒａ１と復路Ｒｂ１とは「一致」と判定されていることを示している。
【００５０】
この図６の一行目に示すように、往路Ｒａ２の総コストが「１０２」、復路Ｒｂ２の総コストが「１０３」であるときには、総コストの総和は「２０５」となる。この場合、総コストの総和がその他の往復経路の総コストの総和よりも少ないため優先順位が最も上位とされている。図６の二行目に示すように、往路Ｒａ３の総コストが「１２８」、復路Ｒｂ３の総コストが「１０２」であるときには、総コストの総和は前記の往復経路（Ｒａ２、Ｒｂ２）に次いで少ないため、その優先順位が２番目として設定されている。
【００５１】
この例に示すように、復路Ｒｂ３の総コストが「１０２」であり、復路Ｒｂ２の総コスト「１０３」よりも少なく、ユーザによる運転負荷が復路Ｒｂ２よりも復路Ｒｂ３の方が軽い場合もあるが、全体の往復経路を考慮した場合には、往復経路の総運転負荷が軽い往復経路（Ｒａ２、Ｒｂ２）を選択することが望ましい。このため、往復経路の総コストの総和が最も少ない往復経路（Ｒａ２、Ｒｂ２）について最も優先順位を高くしている。
【００５２】
図４に戻って、ステップＴ１２以降の処理について当該往復経路の総コストの総和の少ない順に実行する。この後、往路Ｒａについて当該往路Ｒａの最小総コスト（Ｒａ＿ｍｉｎ）との総コスト差（ΔＲａ）を算出し（Ｔ１２）、当該総コスト差ΔＲａが第１所定値を下回らなければ、ステップＴ１２に戻って処理を繰り返す。総コスト差ΔＲａが第１所定値を下回ったときにステップＴ１４の処理に進む。すなわち、このステップＴ１２では、往路Ｒａの総コストと最小総コスト（Ｒａ＿ｍｉｎ）との差が第１所定値未満である往路Ｒａを選択して絞り込む処理を行っている。例えば、第１所定値が「５」と予め設定されているときには、図６に示す例では、往路Ｒａ２の総コスト「１０２」と最小総コスト「１０２」との差が「０」であるため、ステップＴ１２の条件を満たすこととなる。
【００５３】
次に、ステップＴ１４において、復路についても同様に復路Ｒｂの総コストと当該復路の最小総コスト（Ｒｂ＿ｍｉｎ）との総コスト差（ΔＲｂ）を算出し、当該総コスト差ΔＲｂが第２所定値を下回らなければ（Ｔ１５：ＮＯ）、ステップＴ１２に戻って再度処理を繰り返し、総コスト差（ΔＲｂ）が第２所定値を下回ったときにステップＴ１６の処理に進む。すなわち、このステップＴ１５では、復路Ｒｂの総コストと最小総コスト（Ｒｂ＿ｍｉｎ）との差が第２所定値未満である復路Ｒｂを選択して絞り込む処理を行っている。例えば、第２所定値が「５」と予め設定されているときには、図６に示す例では、復路Ｒｂ２の総コスト「１０３」と最小総コスト「１０２」との差が「１」であるため、ステップＴ１２の条件を満たすこととなる。なお、第１所定値と第２所定値は同一値に設定されていても互いに異なる値に設定されていても良い。また、第１所定値よりも第２所定値は小さな値に設定されていてもよい。この意味は、経路設定時に復路の状況を正確に判断するのは往路に比べて難しいためである。すなわち、今から（経路設定時から）すぐに走行する可能性が高い往路に比べて、時間的にかなり経過した後に走行するであろう復路の道路状況（渋滞等）を判断することは困難となる。そこで、復路を選択するための基準（閾値）を往路に比べて厳しくすることで、こうした変化にも対応できる可能性が高まる。つまりこのようにすればユーザにとってより精神的負荷が少ない復路(往復経路)が選択できる可能性が高まる。
【００５４】
このようなステップＴ１２、Ｔ１５の条件を満たしたことを条件として、往路Ｒａおよび復路Ｒｂの経路設定を行う（Ｔ１６）。このようにして往復経路を絞り込み、この条件を満たした往復経路を設定する。この場合、往復経路の総コストの総和の小さい順に処理を行っているため、往復経路の総運転負荷の極力少ない経路を設定することができる。
【００５５】
なお、図４のステップＴ３において、制御装置２は往路に一致した復路が存在しないと判定した場合には（Ｔ３：ＮＯ）、全ての経路を検索したか否かを判定し（Ｔ１７）、全ての往路、復路が一致しなければ（Ｔ１７：ＮＯ）、「往復経路が一致する道路がありません」などのように表示装置９の表示画面、スピーカ１４を通じてユーザに通知し、従来通り、往路のみ、復路のみの探索処理を行い（Ｔ１９）、経路探索処理を終了する。
【００５６】
この後、図３に戻って、制御装置２は、画面表示処理（画面表示制御処理）を行い（Ｓ３）ながら目的地に到達する（Ｓ５：ＹＥＳ）まで往路案内処理を行う（Ｓ４）。目的地に到達した（Ｓ５：ＹＥＳ）としても、制御装置２は出発地をメモリに記憶しているため、ユーザの指示があると（Ｓ６）、出発地を目的地に設定し（Ｓ７）、目的地に到達する（Ｓ１０：ＹＥＳ）まで、画面表示処理および復路案内処理を行う（Ｓ８、Ｓ９）。この後、車両Ｃａが復路Ｒｂを通行して目的地（当初の出発地）に到達する（Ｓ１０：ＹＥＳ）と、制御装置２は図３に示す経路案内処理を終了する。
【００５７】
図７（ａ）および図７（ｂ）は、往路Ｒａと復路Ｒｂが一致する場合を示しており、図８（ａ）および図８（ｂ）は、往路Ｒａと復路Ｒｂが異なる場合を示している。例えば、図８（ａ）および図８（ｂ）に示すように、往路Ｒａと復路Ｒｂが異なる場合には、ユーザが出発地（Ｓ）から目的地（Ｇ）まで往復移動する場合には、異なる道路を通過することになるため、ユーザが不安感を抱くこともある。
【００５８】
本実施形態では、図７（ａ）および図７（ｂ）に示すように、ユーザは一旦通行した往路Ｒａに一致する復路Ｒｂを戻ることになるため、例えば出発地（Ｓ）において経路を設定するときにおいても、往路Ｒａおよび復路Ｒｂを走行中においてもユーザの安心感を増すことができ、ユーザの精神的負担を極力軽減できる。
【００５９】
前述のステップＴ４において、往路Ｒａの総コストを計算するときには、時間通行規制や渋滞予測データを使用し往路Ｒａの総コストを計算すると良い。ユーザが往路Ｒａを通過する時間を指定しても良い。前述のステップＴ７において、復路Ｒｂの総コストを計算するときには、時間通行規制や渋滞予測データを使用し復路Ｒｂの総コストを計算すると良い。ユーザが復路Ｒｂを通過する時間を指定しても良い。
【００６０】
また、例えば制御装置２にスケジュールデータを管理するソフトウェアが組み込まれており、当該ソフトウェアにより参照されたスケジュールデータにより往路Ｒａを通過する時間帯を設定し当該設定された時間帯の往路Ｒａの総コストを計算するようにしても良い。復路Ｒｂについても同様に、復路Ｒｂを通過する時間帯を設定し当該設定された時間帯の復路Ｒｂの総コストを計算するようにしても良い。
【００６１】
出発地、目的地、往路の出発時間、到着時間帯別に走行経路情報とその後の行動履歴情報を収集して推測するようにしても良い。これらの方法によりユーザが復路を通過する時間帯を考慮して復路Ｒｂの総コストを算出すると良い。すると、ユーザの実移動態様に合わせて復路Ｒｂの総コストを算出することができ、より実用的な経路を探索できる。
【００６２】
以上、説明したように、本実施形態によれば、往路Ｒａを設定するときに、往路Ｒａおよび復路Ｒｂが一致する条件を満たすと共に、往路Ｒａの総コストと往路Ｒａの最小総コスト（Ｒａ＿ｍｉｎ）との差が第１所定値未満で且つ復路Ｒｂの総コストと復路Ｒｂの最小総コスト（Ｒｂ＿ｍｉｎ）との差が第２所定値未満の条件を満たす往復経路を探索結果として設定するため、経路の設定時点においても経路を往復移動するときにもユーザの安心感を増すことができ、たとえユーザが出発地から目的地まで往復移動する場合であってもユーザの精神的負担を極力軽減できる。
【００６３】
ユーザが復路Ｒｂを通過する時間帯を考慮して復路Ｒｂの総コストを算出すると、ユーザの実移動態様に合わせて復路Ｒｂの総コストを算出することができ、より実用的な経路を探索できる。
【００６４】
（変形例）
前述の第１実施形態では、往路Ｒａの探索の際に復路Ｒｂが往路Ｒａと一致するような経路を探索している。つまり、復路Ｒｂが往路Ｒａと一致しないような往路Ｒａを経路探索結果から除外していることを示している。また、往路Ｒａのみを探索した場合に最適経路となる場合、復路Ｒｂのみが最適経路となる場合であっても、当該往復経路を経路探索結果から除外していることを示している。
【００６５】
例えば、図６に示す復路Ｒｂ３は、その総コストが最小総コスト（Ｒｂ＿ｍｉｎ）に一致するため、復路Ｒｂのみの総コストを算出したときに最適経路として設定されることになるが、この場合にも前述実施形態では、当該往復経路（Ｒａ３、Ｒｂ３）を除外している。
【００６６】
第１実施形態においては、（１）〜（３）の条件を満たす条件下で往路Ｒａを探索することになるが、（１）の条件のみを満たす経路で往路Ｒａを探索した後、所定時間以上経過した場合に（２）の条件を加えた経路で往路Ｒａを探索しても良い。なお、（１）における同一リンクＩＤの条件を満たす往復経路を設定する条件にて往復経路（ＲａおよびＲｂ）を探索することが望ましい。これは、同一リンクＩＤの往復経路であれば、全く同一の道路を往復移動するためユーザの安心感がより増すためである。
【００６７】
また、次のように変形しても良い。すなわち、制御装置２は往路と復路が一致する往復経路のうちの往路Ｒａの到着時間を検出し、さらに、往路Ｒａのみの最適経路を探索してその往路Ｒｂの最短到着時間を検出し、当該往復経路の往路Ｒａの到着時間と往路Ｒａのみの最適経路を探索した往路Ｒａの最短到着時間との間で第１所定時間以上の乖離がある場合には、その旨をユーザに表示装置９の表示画面、スピーカ１４などを通じてユーザに通知し、ユーザに経路の選択を促す。
【００６８】
また逆に、制御装置２は往復経路の復路Ｒｂの到着時間を検出し、さらに、復路Ｒｂのみの最適経路を探索してその復路Ｒｂの最短到着時間を検出し、往復経路の復路Ｒｂの到着時間と、復路Ｒｂのみの最適経路を探索した復路Ｒｂの最短到着時間との間で第２所定時間以上の乖離がある場合には、その旨をユーザに表示装置９の表示画面、スピーカ１４などを通じてユーザに通知し、ユーザに経路の選択を促す。
【００６９】
すると、ユーザは、往復経路が一致する場合の往復経路（Ｒａ、Ｒｂ）およびその往路および復路の到着時間、と共に、往路Ｒａ／復路Ｒｂごとの最短到着経路とその往路Ｒａ／復路Ｒｂの到着時間を知ることができ、ユーザは所望の経路を選択して通行できる。
【００７０】
（第２実施形態）
図９および図１０は、本発明の第２実施形態を示すもので、前述実施形態と異なるところは、過去に移動したことがある経験経路を部分的に適用し、過去に移動したことがない経路について部分的に往路および復路が一致する経路を探索するところにある。前述実施形態と同一部分については同一符号を付して説明を省略し、以下、異なる部分について説明する。
【００７１】
図９は、過去に走行したことがある経路を部分的に適用し、過去に未走行の経路について部分的に往路および復路が一致した経路を探索する場合の説明図を示している。
さて、前記実施形態を適用すると、過去に走行していようがいまいが、往路と復路が一致する条件を満たす往復経路が探索されることになる。しかし例えば往路と復路が一致していなくとも、それぞれが過去に何度も走行したことのある慣れた道であればユーザの精神的負担はない。一方、一度も走行したことのない道路であれば、往路と復路が一致していると安心感をもたらすことが出来る。
【００７２】
この図９には、ユーザが過去に走行したことがある道路をＲ３（往路および復路）として示している。この道路Ｒ３は、ユーザが車両Ｃａを運転したことがある道路であり、制御装置２の内部メモリなどに移動履歴情報として予め記憶されている道路である。図１０は、移動履歴情報の一例を示している。この図１０に示すように、移動履歴情報は、出発地情報（座標、時刻）、目的地情報（座標、時刻）、通過経路情報（リンクＬのリンクＩＤ）などを含む情報を示している。
【００７３】
つまり、よりユーザに安心感をもたらすためには、地点Ｒ３ｚから出発地Ｓまでの往復経路はたとえそれが一致していなくとも過去に走行したことのあるＲ３（往路および復路）を優先的に案内するようにし、一方地点Ｒ３ｚから目的地Ｇまでの往復経路については本発明の往復経路探索による往路と復路が一致するような経路を案内するように構成するのが好ましい。
【００７４】
すなわち本実施形態では、ユーザが往復経路を探索開始するときに、制御装置２はユーザの設定経路（設定出発地、設定目的地、設定経由地）の往復経路の探索結果の一部に、通過経路情報（リンクＬのリンクＩＤ）が含まれているか否か判定し、当該情報が記憶されていればこの経路を一部含む往復経路を優先的に探索する一方、過去に走行したことのない経路については前記実施形態の方法による探索を行うのである。
【００７５】
図９の例では、制御装置２は、経験道路Ｒ３の端部Ｒ３ｚから目的地（Ｇ）に至るまで往路Ｒａ２および復路Ｒｂ２が一致する往復経路を探索している。ユーザは、出発地（Ｓ）から目的地（Ｇ）に至るまでの間に、経験した道路Ｒ３を含む経路を往復走行することになるため、ユーザは一層安心感を増すことができる。これにより、ユーザの精神的負担を極力軽減できる。
【００７６】
（第３実施形態）
図１１は、本発明の第３実施形態を示すもので、前述実施形態と異なるところは、経路探索装置が移動体の外部に設置されており、当該経路探索装置から車両に搭載された移動支援端末装置に経路探索情報を送信しているところにある。前述実施形態と同一または類似機能を有する部分については同一符号を付して説明を省略し、以下、異なる部分について説明する。
【００７７】
図１１は、本実施形態の説明図を示している。前述実施形態では、経路探索装置Ａがナビゲーション装置１内に搭載された例を示しているが、本実施形態では、この経路探索処理をその外部のセンタ装置２０で実行し、その経路計算結果について基地局２１を通じて移動支援端末装置２２に転送する例を示す。
【００７８】
車両Ｃａには移動支援端末装置２２が搭載されており、当該移動支援端末装置２２はセンタ装置２０との間で無線通信処理を行う通信装置（図示せず）を搭載している。この移動支援端末装置２２は、センタ装置２０との間で基地局２１を通じて無線通信接続し、出発地、経由地、目的地等の経路条件を送信する。
【００７９】
そして、センタ装置２０は、前述した図４に示す経路探索処理を行い、往路Ｒａと復路Ｒｂとが一致する経路で前述した総コストの条件を満たすか否かを判定し、条件を満たす経路情報を移動体Ｃａの移動支援端末装置２２に配信する。車両Ｃａ側では移動支援端末装置２２が車両Ｃａの移動支援を行う。
【００８０】
本実施形態によれば、経路探索装置Ａが車両Ｃａの外部に設置されており、経路探索装置Ａから車両Ｃａに搭載された移動支援端末装置２２に経路探索情報を送信しているため、ユーザは前述実施形態とほぼ同様の恩恵を受けることができる。なお、移動支援端末装置２２は前述実施形態のナビゲーション装置１との間で電気的接続（例えばＬＡＮ接続）されていても良いし、ナビゲーション装置１自体が移動支援端末装置２２として構成されていても良い。
【００８１】
なお、車両Ｃａ側の移動支援端末装置２２が、前述した移動履歴情報を収集する移動履歴情報収集機能を備えていても良い。移動支援端末装置２２はこの移動履歴情報収集機能により得た情報をセンタ装置２０に送信し、センタ装置２０は収集した移動体（車両Ｃａ、歩行者）の移動履歴情報から得た過去に移動した経験経路を部分的に適用できる場合に適用し、過去に移動したことがない経路部分の往路Ｒａおよび復路Ｒｂについて経路探索する。
【００８２】
このような移動履歴情報は、ユーザがたとえ車両Ｃａを売買したとしても、センタ装置２０側ではユーザ毎に恒久的に保存可能なデータとなる。したがって、ユーザが車両Ｃａを乗り換えたとしても、センタ装置２０が移動履歴情報を集中管理しているため、ユーザは意識することなくユーザは前述実施形態とほぼ同様の恩恵を受けることができ、特に有効な経路探索処理形態となる。また、この移動履歴情報は膨大な情報量となる。このため、移動支援端末装置２２側で処理負荷が膨大となり処理し切れない場合であっても、本実施形態の経路探索処理形態は特に有効な処理形態となる。
【００８３】
（他の実施形態）
本発明は、前述した実施形態に限定されるものではなく、例えば、以下に示す変形または拡張が可能である。
【００８４】
地図データとしてノードＮのデータが存在する場合に適用しているが、ノードＮの情報を含まなくても良い。地図データとしてリンクＬの情報を含んでいれば良い。
往路Ｒａおよび復路Ｒｂが一致する条件を満たす往路Ｒａの総コストと当該往路Ｒａの最小総コストの差が第１所定値未満となる条件で、且つ、復路Ｒｂの総コストと当該復路Ｒｂの最小総コストの差が第２所定値未満となり、さらに、往路Ｒａの総コストおよび復路Ｒｂの総コストの総和の最も少ない往路Ｒａおよび復路Ｒｂを探索結果とする実施形態を示したが、ステップＴ１１に説明した条件については省いても良い。
【００８５】
すなわち、ステップＴ１１において総和の少ない順（昇順）に並べ替え、総和の少ない順にステップＴ１２〜Ｔ１５の処理を行うことで往路Ｒａおよび復路Ｒｂを探索しているが、このステップＴ１１の処理を省いても良い。
【００８６】
移動体として車両Ｃａに適用した実施形態を主に示しているが、歩行者であっても良いことは言うまでもなく、経路探索装置Ａは移動体に搭載されたものに限定されるわけではなく、移動体用に携帯可能なネットブック（パーソナルコンピュータ）、インターネットテレビ、携帯電話機、スマートフォン、電子書籍端末、携帯ゲーム機等の移動体用の装置に適用できる。
【００８７】
また、上記実施形態において、図４のステップＴ１２からＴ１５の処理順は、まず往路の総コストが最小総コストに対して第１所定値未満であるものを抽出し、次に復路の総コストが最小総コストに対して第２所定値未満であるものを抽出していた。しかし、これに限らず、まず復路のコストにより候補を抽出し、次いで往路のコストによりその抽出された候補を絞り込むように処理しても構わない。つまり現状の符号を援用すると、現行Ｔ１２→Ｔ１３→Ｔ１４→Ｔ１５の処理順に対して、Ｔ１４→Ｔ１５→Ｔ１２→Ｔ１３のように処理順を変更することも当然可能である。
【符号の説明】
【００８８】
図面中、２は制御装置、２ａは経路探索部（経路探索手段）、Ａは経路探索装置を示す。
【技術分野】
【０００１】
本発明は、経路を探索するための経路探索装置および経路探索方法に関する。
【背景技術】
【０００２】
この種の経路探索装置は様々な態様で開発が進んでいる（例えば特許文献１〜２参照）。特許文献１の技術思想では、過去の走行経路を誘導経路として設定することを提案しており、過去に走行したことがある走行経路の終端に相当する地点を出発地とし、走行経路の始端に相当する地点を目的地として誘導経路を設定している。また、特許文献２記載の技術思想では、算出した経路に対する実際の離脱走行経路を記憶し、次回の算出経路に反映するようにしている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１０−８９９９６号公報
【特許文献２】特開２００１−１２４５７８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ユーザが出発地から目的地まで道路を往復する場合、初めて通過する道路は途中の道路状況の知識がないため往復移動中の精神的負担が強い。そこで、前述の特許文献の技術思想では、往復移動するときに往路と同一の道路を復路として設定することでユーザの精神的負担を緩和するようにしている。
【０００５】
しかしながら、前述の特許文献の技術思想では、往路の走行経路が例えば一方通行などであり、復路を走行すると交通規則に反する部分が存在するとき、交通規則に従い迂回するようにしているため、総コストの高い復路を案内されたり、往路とは相当異なる復路が案内される場合もある。この場合、出発地から目的地まで往復移動する場合、ユーザの精神的負担は緩和されない。
【０００６】
本発明は、上記事情に鑑みてなされたもので、その目的は、ユーザが出発地から目的地まで往復移動する場合、ユーザの精神的負担を極力軽減できるようにした経路探索方法および経路探索装置を提供することにある。
【課題を解決するための手段】
【０００７】
請求項１，１１記載の発明によれば、往路と復路が一致する条件を満たす往復経路のうち、往路の総コストが最小となる往復経路を特定し、特定した最小総コストとの差が第１所定値未満となる総コストの往路からなる往復経路を抽出して探索結果の候補とするため、往路および復路が一致する往復経路について往路の総コストが極力少なくなるように絞り込むことができる。
【０００８】
さらに、抽出された往復経路のうち、復路の総コストが最小となる往復経路を特定し、特定した最小総コストとの差が第２所定値未満となる総コストの復路からなる往復経路を抽出して往復経路の探索結果とするため、往路および復路が一致する経路について復路の総コストが極力少なくなるように絞り込むことができる。このため、ユーザは、往路に一致した復路であって総コストが極力少なくなる復路を戻ることができ、経路の設定時点においても経路を往復移動するときにもユーザの安心感を増すことができる。これにより、ユーザの精神的負担を極力軽減できる。
【０００９】
請求項２記載の発明によれば、請求項１記載の条件を満たすと共に、さらに往路および復路の総コストの総和の最も少ない往路および復路を往復経路の探索結果とするため、往復経路の総負荷の少ない経路を設定することができ、ユーザの精神的負担を軽減できる。
【００１０】
請求項３記載の発明によれば、ユーザが往路を通過する時間帯を考慮して復路の総コストを算出するため、ユーザの実移動態様に合わせて往路の総コストを算出でき、より実用的な経路を探索できる。
【００１１】
請求項４記載の発明によれば、ユーザが復路を通過する時間帯を考慮して復路の総コストを算出するため、ユーザの実移動態様に合わせて復路の総コストを算出でき、より実用的な経路を探索できる。
【００１２】
請求項５記載の発明によれば、過去に移動したことがある経験経路を部分的に適用し、過去に移動したことがない経路について部分的に往路および復路が一致する経路を探索するため、ユーザは過去に経験した道路を含む経路を往復移動することになるため、ユーザは安心感を増すことができ、ユーザの精神的負担を極力軽減できる。
【００１３】
請求項６、８−１１記載の発明によれば、所定の条件を満たすときに経路が一致すると判定しているため、より実用的な経路を探索できる。
請求項７記載の発明によれば、往路と復路が一致する往復経路の往路の到着時間と、往路の最短到着時間との間で第１所定時間以上の乖離がある場合、または／および、往路と復路が一致する往復経路の復路の到着時間と復路の最短到着時間との間で第２所定時間以上の乖離がある場合、は、往路と復路が一致する経路とその往路／復路の到着時間と、往路／復路ごとの最短到着経路とその往路／復路の到着時間を探索し通知する。
【００１４】
このため、ユーザは、往路および復路が一致する場合の往復経路およびその往路および復路の到着時間、と共に、往路／復路ごとの最短到着経路とその往路／復路の到着時間を知ることができ、ユーザが所望の経路を選択して通行することができる。
【００１５】
なお、本発明における「往路の総コスト」「復路の総コスト」とは、移動体が例えば車両の場合、ユーザが往路または復路を運転した場合の総負荷について数値により示したものである。例えば、出発地から目的地までの総コストは、当該出発地から目的地までの距離、通行道路の車線数、右折数、左折数、通行道路の渋滞の有無およびその程度、通行道路の車両通行規制、合流の有無やその回数、レーン変更回数などの少なくとも一部または全部の要素を、総じて数値に置き換えてカウントした結果を示している。
【００１６】
したがって、これらの総コストが高ければ例えば車両の場合には運転の負荷が高く、総コストが低ければ運転の負荷が低い。例えば車両ではなく、歩行者が所持する経路探索装置の場合であっても、出発地から目的地までの距離が長ければ移動負荷が高く、距離が短ければ移動負荷が低いため、歩行者などが経路探索装置を所持する場合でも本発明は同様に適用できる。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１実施形態における電気的構成を概略的に示すブロック図
【図２】リンクの定義の説明図
【図３】経路案内処理を説明するフローチャート
【図４】経路探索処理を説明するフローチャート
【図５】往路および復路の一致を説明するための説明図
【図６】往復経路の総コストの総和の一例を示す説明図
【図７】経路の一例を示す説明図
【図８】比較例を示す図７相当図
【図９】本発明の第２実施形態における経路設定例を示す説明図
【図１０】移動履歴情報の一例を示す図
【図１１】本発明の第３実施形態を示すシステム構成図
【発明を実施するための形態】
【００１８】
（第１実施形態）
以下、本発明の経路探索方法、経路探索装置を車両用ナビゲーション装置に適用した第１実施形態について図１ないし図８を参照しながら説明する。図１は、車両用ナビゲーション装置の電気的構成を概略的なブロック図によって示している。
【００１９】
図１に示すように、車両用ナビゲーション装置１は制御装置２を備え、当該制御装置（制御ユニット）２に、位置検出器３、地図データ入力器４、操作スイッチ群５、ＶＩＣＳ（登録商標）受信機６、通信装置７、外部メモリ８、表示装置９、音声コントローラ１０、音声認識部１１、リモコンセンサ１２を接続して構成される。リモコンセンサ１２にはリモコン１３が赤外線接続され、音声コントローラ１０にはスピーカ１４が接続され、音声認識部１１にはマイク１５が接続される。
【００２０】
制御装置２は、例えばマイクロコンピュータを主体として構成されたものであり、ＣＰＵ、ＲＡＭ、ＲＯＭ及びＩ／Ｏバス（何れも図示せず）を備え、各種の制御プログラムを実行して装置全体の動作を制御する。経路探索装置Ａは、制御装置２が実行するソフトウェアにより実現されるものである。
【００２１】
位置検出器３は、Ｇセンサ３ａ、ジャイロスコープ３ｂ、距離センサ３ｃ、ＧＰＳ受信機３ｄ等を備えて構成され、これらの各構成要素は互いに性質の異なる検出誤差を有している。制御装置２はこれら各構成要素から入力した検出信号を互いに補間して車両の現在位置を特定する。
【００２２】
この場合、位置検出器３は、要求される検出精度で車両の現在位置を検出可能であれば、これら全ての構成要素を備える必要はなく、又、ステアリングの舵角を検出するステアリングセンサや各車輪の回転を検出する車輪センサ等が組み合わされて構成されていても良い。
【００２３】
地図データ入力器４は、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、メモリカード又はＨＤＤ等の記録媒体を装着し、地図データやマップマッチング用データ等を入力する。操作スイッチ群５は、表示装置９の周辺に配置されるメカニカルキーや表示装置９の表示画面上に形成されるタッチキーから構成され、例えばユーザが何らかの操作（例えばメニュー表示選択、目的地設定、経路探索、経路案内開始、表示画面変更及び音量調整等）を行った旨を検出すると、操作検出信号を制御装置２に出力する。
【００２４】
ＶＩＣＳ受信機６は、広域通信網を通じて広域通信を行い、ＶＩＣＳセンター装置（図示せず）から送信されたＶＩＣＳ情報について広域通信網を通じて受信する。外部メモリ８は、ＨＤＤ等の大容量記憶装置から構成されている。
【００２５】
表示装置９は、例えばカラー液晶ディスプレイにより構成され、メニュー選択画面、目的地設定画面、経路案内画面等の各種の表示画面を表示すると共に、車両の現在位置を表す現在位置マークや走行軌跡等を地図データの地図上に重ねて表示する。尚、表示装置９は、有機ＥＬやプラズマディスプレイ装置等から構成されていても良い。
【００２６】
音声コントローラ１０は、例えば警告音や経路案内の案内音声等をスピーカ１４から出力させる。音声認識部１１は、制御装置２により動作が制御され、起動状態ではマイク１５から入力した音声を音声認識アルゴリズムにしたがって音声認識可能な状態とする。リモコンセンサ１２は、リモコン１３から送信された操作検出信号を受信すると、その受信した操作検出信号を制御装置２に出力する。
【００２７】
制御装置２は、地図データを取得する地図データ取得部、車両の現在位置と地図データ取得部により取得された地図データ内の道路データとを使用して車両の現在位置が存在する道路を特定するマップマッチング部、マップマッチング部により特定された車両の現在位置からユーザにより設定された目的地までの経路を探索する経路探索部２ａ、経路探索部により探索された経路及び地図データ内の道路データや交差点の位置データ等に基づいて経路案内に必要な地点を算出して経路案内する経路案内部、車両の現在位置周辺の地図や高速道路の略図や交差点付近の拡大図等を描画する表示制御部等を備えている。経路探索部２ａが経路探索手段として動作する。
【００２８】
図２は、地図データとして記憶される道路データの概要を示している。
地図データは、各交差点Ｃの中央に設定されるノードＮや、このノードＮ間を結合するリンクＬを含んだ道路データにより構成される。例えば、片側一車線の直線道路では、図２に示されるように、車両Ｃａが左側通行している場合を考慮すると、各交差点Ｃの中央に設定されたノードＮ間を結合するリンクＬが道路幅方向の中央に設定されている。
【００２９】
このリンクＬには、複数のノードＮ間を結合する間に複数の形状点が設定されており、当該複数の形状点に対応して形状データ（例えば幅、高さ等）が設定されており、当該形状データに応じた道路データが記憶されている。リンクＬには、それぞれリンクＩＤ（リンク識別情報）が付されており、交差点Ｃを結合する道路毎、道幅の異なる道路毎にそれぞれ異なるＩＤ（識別情報）が付された状態で管理されている。
【００３０】
上記構成において、ユーザが出発地において出発地と目的地との間で往路Ｒａおよび復路Ｒｂを往復設定した場合の経路探索方法について説明する。
一般に、ユーザがナビゲーション機能の経路案内を利用するときには、例えば未知の道路を走行する場合に使用する。特に女性などの特定ユーザは、出発地（現在位置）から目的地まで往復移動し、他施設に寄り道することなく移動できれば良い場合もある。このような場合、出発地から目的地までの往路Ｒａを設定するときに、往路Ｒａおよび復路Ｒｂの双方（往復経路）を設定できると良い。すると、ユーザは、往路Ｒａを走行した経験を活かして復路Ｒｂを戻ることができるため、往路Ｒａを走行するときにも復路Ｒｂを走行するときにも安心感が得られる。そこで、本実施形態では、出発地において出発地から目的地までの往路Ｒａを設定するとき、往路Ｒａおよび復路Ｒｂを共に設定可能に構成している。
【００３１】
図３は、経路案内処理をフローチャートにより概略的に示している。まず、操作スイッチ群５のユーザ操作により目的地が設定される（Ｓ１）。目的地が設定されると、制御装置２は、現在位置から目的地に至るまでの往復の経路探索処理を行う（Ｓ２）。この経路探索処理では、出発地（現在位置）から目的地に至るまでの往路Ｒａの探索と共に目的地から出発地（現在位置）に戻るまでの復路Ｒｂの探索も行う。
【００３２】
図４は、経路探索処理をフローチャートにより示している。まず、経路探索処理において、制御装置２は出発地（現在位置）から目的地までの往路Ｒａについてダイクストラ法を用いて探索する（Ｔ１）。次に、制御装置２は目的地から現在位置までの往路Ｒａに一致した復路Ｒｂを探索し（Ｔ２）、往路Ｒａと復路Ｒｂが一致する経路（往復経路）が存在するか否かを判定する（Ｔ３）。
【００３３】
ここで、「往路と復路（往復経路）が一致」とは、以下の（１）〜（３）のうち少なくとも（１）を含む何れか１または複数、または全部を含む条件を満たすことを示している。
【００３４】
（１）往路Ｒａおよび復路Ｒｂが同一リンクＩＤのリンクＬであれば往路Ｒａおよび復路Ｒｂが一致。
（２）往路Ｒａおよび復路Ｒｂが異なるリンクＩＤであっても、以下の（Ａ）〜（Ｄ）の条件を全て満たす場合に一致。
【００３５】
（Ａ）道路名称が同じ（名称が無い場合は、この条件は除外）
（Ｂ）道路種別が同じ
（Ｃ）それぞれのリンクＬの逆方向ベクトルの方位差が所定値以内
（Ｄ）それぞれのリンクＬ間の距離が所定距離以内
（３）高速道路のインターチェンジ（ＩＣ）、ジャンクション（ＪＣＴ）についてリンクＬがそれぞれ構成されている場合には、当該インターチェンジのリンクＬの前後のリンクＬ、ジャンクションのリンクＬの前後のリンクＬについて（２）の条件を満たせば一致と判定する。（２）の条件としては、（Ｅ）それぞれのリンクＬが共に一方通行で、且つ通行可能方向が双方逆向き、の条件を加入して考慮しても良い。
【００３６】
（１）の条件は、例えば、図２に示すように、片道一車線の道路などにリンクＬが一つ設定されていることを考慮しているものであり、この場合、リンクＩＤは一致するため、往路Ｒａおよび復路Ｒｂが一致すると判定する。（２）の条件は、互いに離間した互いに逆方向に走行可能な道路を対象としている。
【００３７】
図５は（２）の条件説明を示している。図５に示す道路Ｒ１は図示上方向に一方通行であり、道路Ｒ２は図示下方向に一方通行となっている。これは、例えば高速道路などのように道路Ｒ１および道路Ｒ２間に障害物が存在し、当該障害物を避けて道路が設けられている場合を考慮している。
【００３８】
地図データには各道路Ｒ１、Ｒ２毎に別々のリンクＬ１、Ｌ２が付されていることがあり、これらのリンクＬ１、Ｌ２が道路Ｒ１、Ｒ２別に記憶されていることがある。この場合には、道路Ｒ１の通行方向と道路Ｒ２の通行方向とはほぼ逆方向となっている。
【００３９】
このようなときには、地図データには（２）の（Ａ）に示すように、道路名称が同じに設定されている場合や、道路名称が何れにも付されていない場合もある。また、地図データには（２）の（Ｂ）に示すように、道路種別（国道、県道、市道など）が同一に設定されている。そこで、（２）の（Ａ）、（Ｂ）をそれぞれ条件の一つとして往路Ｒａおよび復路Ｒｂが一致するか否かを判定すると良い。
【００４０】
また、図５に示す道路Ｒ１と道路Ｒ２の方位は互いにほぼ逆方向であるもののわずかに方位差が存在する。そこで、（２）の（Ｃ）に示すように、リンクＬの逆方向ベクトルの方位差θが所定値以内に設定されていることを条件として往路Ｒａおよび復路Ｒｂが一致すると判定すると良い。
【００４１】
また、図５に示すように、道路Ｒ１と道路Ｒ２の方位が互いにほぼ逆方向に設定されているものの、道路Ｒ１と道路Ｒ２との間に距離Ｗは多少離れている。そこで、（２）の（Ｄ）に示すように、各リンクＬ間の距離Ｗが所定距離以内に配置されることを条件として往路Ｒａおよび復路Ｒｂが一致すると判定しても良い。このような（２）の（Ｃ）、（Ｄ）を条件の一つとすると良い。このような（２）の条件を加えることにより、ユーザが普段道路を通行するときの印象に極力合致するように「一致した往路Ｒａおよび復路Ｒｂ（往復経路）」を判定でき的確な経路の判定処理を行うことができる。
【００４２】
すなわち、「往路および復路（往復経路）が一致する経路」とは、（１）に示すように、片側一車線、片側複数車線など車両Ｃａが互いに対向して通行可能でリンクＬが一つしか設定されていない道路に限られず、必要に応じて前述の所定の（２）の（Ａ）〜（Ｄ）の条件を満たした場合にも適用できる。
【００４３】
図４に戻って、制御装置２は往路Ｒａと復路Ｒｂが一致した経路が存在すると判定した場合（Ｔ３：ＹＥＳ）には、次のステップＴ４以降の処理を行う。ステップＴ４において、制御装置２は、往路Ｒａの総コストを算出する（Ｔ４）。この往路Ｒａの総コストは、ユーザが往路Ｒａを車両運転した場合の運転負荷を一つの指標により示している。
【００４４】
例えば、出発地（現在位置）から目的地までの総コストは、当該出発地（現在位置）から目的地までの距離、通行道路の車線数、右折数、左折数、通行道路の渋滞の有無およびその程度、通行道路の車両通行規制、合流の有無やその回数、レーン変更回数などの各要素を、総じて数値に置き換えてカウントした結果を示している。なお、これらの要素のうち少なくとも一部をカウントするようにしても良い。
【００４５】
例えば、日本の場合、「右折」は対向車線を走行する車両等に配慮する必要があり、「左折」はその必要がないため、「右折」は「左折」よりも運転負荷（コスト）が高く設定される。また、通行道路が渋滞すると、運転者のストレスが高まるため、運転負荷のコストが高く設定されている。このように各道路には、その道路態様や道路状況などに応じてコストを算出でき、ステップＴ４において、制御装置２は往路Ｒａの総コストを算出することにより道路状況を数値により置き換えることができる。往路Ｒａと復路Ｒｂについて同一道路を走行する場合にも右折数や左折数が異なるため、同一道路を走行した場合でも総コストが異なる。
【００４６】
次に、往路Ｒａの総コストが最小総コスト（Ｒａ＿ｍｉｎ）を下回ったか否かを判定し（Ｔ５）、下回っていれば往路Ｒａの最小総コスト（Ｒａ＿ｍｉｎ）を更新する（Ｔ６）。このステップＴ５およびＴ６の処理は、往路Ｒａおよび復路Ｒｂの一致した条件を満たす往復経路の中でユーザの運転負荷が最も少ない往路Ｒａを判定するために行われる。
【００４７】
次に、復路Ｒｂの総コストを算出し（Ｔ７）、復路Ｒｂの総コストが最小総コスト（Ｒｂ＿ｍｉｎ）を下回ったか否かを判定し（Ｔ８）、下回っていれば復路Ｒｂの最小総コスト（Ｒｂ＿ｍｉｎ）を更新する（Ｔ９）。これらのステップＴ７〜Ｔ９の処理は、往路Ｒａおよび復路Ｒｂの一致した条件を満たす往復経路の中でユーザの運転負荷が最も少ない復路Ｒｂを判定するために行われる。
【００４８】
そして、現在位置から目的地まで往路Ｒａおよび復路Ｒｂ（往復経路）が互いに一致した全ての経路を探索してコストを算出完了したか否かを判定し（Ｔ１０）、現在位置から目的地まで往復経路が一致した全往路Ｒａ、復路Ｒｂの総コストを算出完了していれば（Ｔ１０：ＹＥＳ）、ステップＴ１１の処理に進む。算出完了しなければ（Ｔ１０：ＮＯ）、ステップＴ１に戻って処理を繰り返す。これにより、現在位置から目的地までの往復経路を全て探索し、当該往復経路に応じた往路Ｒａの最小総コスト（Ｒａ＿ｍｉｎ）と、復路Ｒｂの最小総コスト（Ｒｂ＿ｍｉｎ）を算出できる。
【００４９】
次に、往路Ｒａの総コストと往路Ｒａに一致する復路Ｒｂの総コストの総和を算出し、昇順に並べ換える（Ｔ１１）。この理由は、往復経路の総運転負荷が軽い順に並べ換えるためである。図６は、往復経路の総コストの総和を昇順に並べ替えた後の一例を示している。この図６において、往路Ｒａ、復路Ｒｂに添え字「１」〜「４」を付して経路を表している。これらが同一の添え字となる往路Ｒａおよび復路Ｒｂは、往路Ｒａおよび復路Ｒｂが一致すると判定された経路を示している。すなわち、例えば往路Ｒａ２と復路Ｒｂ２とはステップＴ３において「一致」と判定されており、往路Ｒａ１と復路Ｒｂ１とは「一致」と判定されていることを示している。
【００５０】
この図６の一行目に示すように、往路Ｒａ２の総コストが「１０２」、復路Ｒｂ２の総コストが「１０３」であるときには、総コストの総和は「２０５」となる。この場合、総コストの総和がその他の往復経路の総コストの総和よりも少ないため優先順位が最も上位とされている。図６の二行目に示すように、往路Ｒａ３の総コストが「１２８」、復路Ｒｂ３の総コストが「１０２」であるときには、総コストの総和は前記の往復経路（Ｒａ２、Ｒｂ２）に次いで少ないため、その優先順位が２番目として設定されている。
【００５１】
この例に示すように、復路Ｒｂ３の総コストが「１０２」であり、復路Ｒｂ２の総コスト「１０３」よりも少なく、ユーザによる運転負荷が復路Ｒｂ２よりも復路Ｒｂ３の方が軽い場合もあるが、全体の往復経路を考慮した場合には、往復経路の総運転負荷が軽い往復経路（Ｒａ２、Ｒｂ２）を選択することが望ましい。このため、往復経路の総コストの総和が最も少ない往復経路（Ｒａ２、Ｒｂ２）について最も優先順位を高くしている。
【００５２】
図４に戻って、ステップＴ１２以降の処理について当該往復経路の総コストの総和の少ない順に実行する。この後、往路Ｒａについて当該往路Ｒａの最小総コスト（Ｒａ＿ｍｉｎ）との総コスト差（ΔＲａ）を算出し（Ｔ１２）、当該総コスト差ΔＲａが第１所定値を下回らなければ、ステップＴ１２に戻って処理を繰り返す。総コスト差ΔＲａが第１所定値を下回ったときにステップＴ１４の処理に進む。すなわち、このステップＴ１２では、往路Ｒａの総コストと最小総コスト（Ｒａ＿ｍｉｎ）との差が第１所定値未満である往路Ｒａを選択して絞り込む処理を行っている。例えば、第１所定値が「５」と予め設定されているときには、図６に示す例では、往路Ｒａ２の総コスト「１０２」と最小総コスト「１０２」との差が「０」であるため、ステップＴ１２の条件を満たすこととなる。
【００５３】
次に、ステップＴ１４において、復路についても同様に復路Ｒｂの総コストと当該復路の最小総コスト（Ｒｂ＿ｍｉｎ）との総コスト差（ΔＲｂ）を算出し、当該総コスト差ΔＲｂが第２所定値を下回らなければ（Ｔ１５：ＮＯ）、ステップＴ１２に戻って再度処理を繰り返し、総コスト差（ΔＲｂ）が第２所定値を下回ったときにステップＴ１６の処理に進む。すなわち、このステップＴ１５では、復路Ｒｂの総コストと最小総コスト（Ｒｂ＿ｍｉｎ）との差が第２所定値未満である復路Ｒｂを選択して絞り込む処理を行っている。例えば、第２所定値が「５」と予め設定されているときには、図６に示す例では、復路Ｒｂ２の総コスト「１０３」と最小総コスト「１０２」との差が「１」であるため、ステップＴ１２の条件を満たすこととなる。なお、第１所定値と第２所定値は同一値に設定されていても互いに異なる値に設定されていても良い。また、第１所定値よりも第２所定値は小さな値に設定されていてもよい。この意味は、経路設定時に復路の状況を正確に判断するのは往路に比べて難しいためである。すなわち、今から（経路設定時から）すぐに走行する可能性が高い往路に比べて、時間的にかなり経過した後に走行するであろう復路の道路状況（渋滞等）を判断することは困難となる。そこで、復路を選択するための基準（閾値）を往路に比べて厳しくすることで、こうした変化にも対応できる可能性が高まる。つまりこのようにすればユーザにとってより精神的負荷が少ない復路(往復経路)が選択できる可能性が高まる。
【００５４】
このようなステップＴ１２、Ｔ１５の条件を満たしたことを条件として、往路Ｒａおよび復路Ｒｂの経路設定を行う（Ｔ１６）。このようにして往復経路を絞り込み、この条件を満たした往復経路を設定する。この場合、往復経路の総コストの総和の小さい順に処理を行っているため、往復経路の総運転負荷の極力少ない経路を設定することができる。
【００５５】
なお、図４のステップＴ３において、制御装置２は往路に一致した復路が存在しないと判定した場合には（Ｔ３：ＮＯ）、全ての経路を検索したか否かを判定し（Ｔ１７）、全ての往路、復路が一致しなければ（Ｔ１７：ＮＯ）、「往復経路が一致する道路がありません」などのように表示装置９の表示画面、スピーカ１４を通じてユーザに通知し、従来通り、往路のみ、復路のみの探索処理を行い（Ｔ１９）、経路探索処理を終了する。
【００５６】
この後、図３に戻って、制御装置２は、画面表示処理（画面表示制御処理）を行い（Ｓ３）ながら目的地に到達する（Ｓ５：ＹＥＳ）まで往路案内処理を行う（Ｓ４）。目的地に到達した（Ｓ５：ＹＥＳ）としても、制御装置２は出発地をメモリに記憶しているため、ユーザの指示があると（Ｓ６）、出発地を目的地に設定し（Ｓ７）、目的地に到達する（Ｓ１０：ＹＥＳ）まで、画面表示処理および復路案内処理を行う（Ｓ８、Ｓ９）。この後、車両Ｃａが復路Ｒｂを通行して目的地（当初の出発地）に到達する（Ｓ１０：ＹＥＳ）と、制御装置２は図３に示す経路案内処理を終了する。
【００５７】
図７（ａ）および図７（ｂ）は、往路Ｒａと復路Ｒｂが一致する場合を示しており、図８（ａ）および図８（ｂ）は、往路Ｒａと復路Ｒｂが異なる場合を示している。例えば、図８（ａ）および図８（ｂ）に示すように、往路Ｒａと復路Ｒｂが異なる場合には、ユーザが出発地（Ｓ）から目的地（Ｇ）まで往復移動する場合には、異なる道路を通過することになるため、ユーザが不安感を抱くこともある。
【００５８】
本実施形態では、図７（ａ）および図７（ｂ）に示すように、ユーザは一旦通行した往路Ｒａに一致する復路Ｒｂを戻ることになるため、例えば出発地（Ｓ）において経路を設定するときにおいても、往路Ｒａおよび復路Ｒｂを走行中においてもユーザの安心感を増すことができ、ユーザの精神的負担を極力軽減できる。
【００５９】
前述のステップＴ４において、往路Ｒａの総コストを計算するときには、時間通行規制や渋滞予測データを使用し往路Ｒａの総コストを計算すると良い。ユーザが往路Ｒａを通過する時間を指定しても良い。前述のステップＴ７において、復路Ｒｂの総コストを計算するときには、時間通行規制や渋滞予測データを使用し復路Ｒｂの総コストを計算すると良い。ユーザが復路Ｒｂを通過する時間を指定しても良い。
【００６０】
また、例えば制御装置２にスケジュールデータを管理するソフトウェアが組み込まれており、当該ソフトウェアにより参照されたスケジュールデータにより往路Ｒａを通過する時間帯を設定し当該設定された時間帯の往路Ｒａの総コストを計算するようにしても良い。復路Ｒｂについても同様に、復路Ｒｂを通過する時間帯を設定し当該設定された時間帯の復路Ｒｂの総コストを計算するようにしても良い。
【００６１】
出発地、目的地、往路の出発時間、到着時間帯別に走行経路情報とその後の行動履歴情報を収集して推測するようにしても良い。これらの方法によりユーザが復路を通過する時間帯を考慮して復路Ｒｂの総コストを算出すると良い。すると、ユーザの実移動態様に合わせて復路Ｒｂの総コストを算出することができ、より実用的な経路を探索できる。
【００６２】
以上、説明したように、本実施形態によれば、往路Ｒａを設定するときに、往路Ｒａおよび復路Ｒｂが一致する条件を満たすと共に、往路Ｒａの総コストと往路Ｒａの最小総コスト（Ｒａ＿ｍｉｎ）との差が第１所定値未満で且つ復路Ｒｂの総コストと復路Ｒｂの最小総コスト（Ｒｂ＿ｍｉｎ）との差が第２所定値未満の条件を満たす往復経路を探索結果として設定するため、経路の設定時点においても経路を往復移動するときにもユーザの安心感を増すことができ、たとえユーザが出発地から目的地まで往復移動する場合であってもユーザの精神的負担を極力軽減できる。
【００６３】
ユーザが復路Ｒｂを通過する時間帯を考慮して復路Ｒｂの総コストを算出すると、ユーザの実移動態様に合わせて復路Ｒｂの総コストを算出することができ、より実用的な経路を探索できる。
【００６４】
（変形例）
前述の第１実施形態では、往路Ｒａの探索の際に復路Ｒｂが往路Ｒａと一致するような経路を探索している。つまり、復路Ｒｂが往路Ｒａと一致しないような往路Ｒａを経路探索結果から除外していることを示している。また、往路Ｒａのみを探索した場合に最適経路となる場合、復路Ｒｂのみが最適経路となる場合であっても、当該往復経路を経路探索結果から除外していることを示している。
【００６５】
例えば、図６に示す復路Ｒｂ３は、その総コストが最小総コスト（Ｒｂ＿ｍｉｎ）に一致するため、復路Ｒｂのみの総コストを算出したときに最適経路として設定されることになるが、この場合にも前述実施形態では、当該往復経路（Ｒａ３、Ｒｂ３）を除外している。
【００６６】
第１実施形態においては、（１）〜（３）の条件を満たす条件下で往路Ｒａを探索することになるが、（１）の条件のみを満たす経路で往路Ｒａを探索した後、所定時間以上経過した場合に（２）の条件を加えた経路で往路Ｒａを探索しても良い。なお、（１）における同一リンクＩＤの条件を満たす往復経路を設定する条件にて往復経路（ＲａおよびＲｂ）を探索することが望ましい。これは、同一リンクＩＤの往復経路であれば、全く同一の道路を往復移動するためユーザの安心感がより増すためである。
【００６７】
また、次のように変形しても良い。すなわち、制御装置２は往路と復路が一致する往復経路のうちの往路Ｒａの到着時間を検出し、さらに、往路Ｒａのみの最適経路を探索してその往路Ｒｂの最短到着時間を検出し、当該往復経路の往路Ｒａの到着時間と往路Ｒａのみの最適経路を探索した往路Ｒａの最短到着時間との間で第１所定時間以上の乖離がある場合には、その旨をユーザに表示装置９の表示画面、スピーカ１４などを通じてユーザに通知し、ユーザに経路の選択を促す。
【００６８】
また逆に、制御装置２は往復経路の復路Ｒｂの到着時間を検出し、さらに、復路Ｒｂのみの最適経路を探索してその復路Ｒｂの最短到着時間を検出し、往復経路の復路Ｒｂの到着時間と、復路Ｒｂのみの最適経路を探索した復路Ｒｂの最短到着時間との間で第２所定時間以上の乖離がある場合には、その旨をユーザに表示装置９の表示画面、スピーカ１４などを通じてユーザに通知し、ユーザに経路の選択を促す。
【００６９】
すると、ユーザは、往復経路が一致する場合の往復経路（Ｒａ、Ｒｂ）およびその往路および復路の到着時間、と共に、往路Ｒａ／復路Ｒｂごとの最短到着経路とその往路Ｒａ／復路Ｒｂの到着時間を知ることができ、ユーザは所望の経路を選択して通行できる。
【００７０】
（第２実施形態）
図９および図１０は、本発明の第２実施形態を示すもので、前述実施形態と異なるところは、過去に移動したことがある経験経路を部分的に適用し、過去に移動したことがない経路について部分的に往路および復路が一致する経路を探索するところにある。前述実施形態と同一部分については同一符号を付して説明を省略し、以下、異なる部分について説明する。
【００７１】
図９は、過去に走行したことがある経路を部分的に適用し、過去に未走行の経路について部分的に往路および復路が一致した経路を探索する場合の説明図を示している。
さて、前記実施形態を適用すると、過去に走行していようがいまいが、往路と復路が一致する条件を満たす往復経路が探索されることになる。しかし例えば往路と復路が一致していなくとも、それぞれが過去に何度も走行したことのある慣れた道であればユーザの精神的負担はない。一方、一度も走行したことのない道路であれば、往路と復路が一致していると安心感をもたらすことが出来る。
【００７２】
この図９には、ユーザが過去に走行したことがある道路をＲ３（往路および復路）として示している。この道路Ｒ３は、ユーザが車両Ｃａを運転したことがある道路であり、制御装置２の内部メモリなどに移動履歴情報として予め記憶されている道路である。図１０は、移動履歴情報の一例を示している。この図１０に示すように、移動履歴情報は、出発地情報（座標、時刻）、目的地情報（座標、時刻）、通過経路情報（リンクＬのリンクＩＤ）などを含む情報を示している。
【００７３】
つまり、よりユーザに安心感をもたらすためには、地点Ｒ３ｚから出発地Ｓまでの往復経路はたとえそれが一致していなくとも過去に走行したことのあるＲ３（往路および復路）を優先的に案内するようにし、一方地点Ｒ３ｚから目的地Ｇまでの往復経路については本発明の往復経路探索による往路と復路が一致するような経路を案内するように構成するのが好ましい。
【００７４】
すなわち本実施形態では、ユーザが往復経路を探索開始するときに、制御装置２はユーザの設定経路（設定出発地、設定目的地、設定経由地）の往復経路の探索結果の一部に、通過経路情報（リンクＬのリンクＩＤ）が含まれているか否か判定し、当該情報が記憶されていればこの経路を一部含む往復経路を優先的に探索する一方、過去に走行したことのない経路については前記実施形態の方法による探索を行うのである。
【００７５】
図９の例では、制御装置２は、経験道路Ｒ３の端部Ｒ３ｚから目的地（Ｇ）に至るまで往路Ｒａ２および復路Ｒｂ２が一致する往復経路を探索している。ユーザは、出発地（Ｓ）から目的地（Ｇ）に至るまでの間に、経験した道路Ｒ３を含む経路を往復走行することになるため、ユーザは一層安心感を増すことができる。これにより、ユーザの精神的負担を極力軽減できる。
【００７６】
（第３実施形態）
図１１は、本発明の第３実施形態を示すもので、前述実施形態と異なるところは、経路探索装置が移動体の外部に設置されており、当該経路探索装置から車両に搭載された移動支援端末装置に経路探索情報を送信しているところにある。前述実施形態と同一または類似機能を有する部分については同一符号を付して説明を省略し、以下、異なる部分について説明する。
【００７７】
図１１は、本実施形態の説明図を示している。前述実施形態では、経路探索装置Ａがナビゲーション装置１内に搭載された例を示しているが、本実施形態では、この経路探索処理をその外部のセンタ装置２０で実行し、その経路計算結果について基地局２１を通じて移動支援端末装置２２に転送する例を示す。
【００７８】
車両Ｃａには移動支援端末装置２２が搭載されており、当該移動支援端末装置２２はセンタ装置２０との間で無線通信処理を行う通信装置（図示せず）を搭載している。この移動支援端末装置２２は、センタ装置２０との間で基地局２１を通じて無線通信接続し、出発地、経由地、目的地等の経路条件を送信する。
【００７９】
そして、センタ装置２０は、前述した図４に示す経路探索処理を行い、往路Ｒａと復路Ｒｂとが一致する経路で前述した総コストの条件を満たすか否かを判定し、条件を満たす経路情報を移動体Ｃａの移動支援端末装置２２に配信する。車両Ｃａ側では移動支援端末装置２２が車両Ｃａの移動支援を行う。
【００８０】
本実施形態によれば、経路探索装置Ａが車両Ｃａの外部に設置されており、経路探索装置Ａから車両Ｃａに搭載された移動支援端末装置２２に経路探索情報を送信しているため、ユーザは前述実施形態とほぼ同様の恩恵を受けることができる。なお、移動支援端末装置２２は前述実施形態のナビゲーション装置１との間で電気的接続（例えばＬＡＮ接続）されていても良いし、ナビゲーション装置１自体が移動支援端末装置２２として構成されていても良い。
【００８１】
なお、車両Ｃａ側の移動支援端末装置２２が、前述した移動履歴情報を収集する移動履歴情報収集機能を備えていても良い。移動支援端末装置２２はこの移動履歴情報収集機能により得た情報をセンタ装置２０に送信し、センタ装置２０は収集した移動体（車両Ｃａ、歩行者）の移動履歴情報から得た過去に移動した経験経路を部分的に適用できる場合に適用し、過去に移動したことがない経路部分の往路Ｒａおよび復路Ｒｂについて経路探索する。
【００８２】
このような移動履歴情報は、ユーザがたとえ車両Ｃａを売買したとしても、センタ装置２０側ではユーザ毎に恒久的に保存可能なデータとなる。したがって、ユーザが車両Ｃａを乗り換えたとしても、センタ装置２０が移動履歴情報を集中管理しているため、ユーザは意識することなくユーザは前述実施形態とほぼ同様の恩恵を受けることができ、特に有効な経路探索処理形態となる。また、この移動履歴情報は膨大な情報量となる。このため、移動支援端末装置２２側で処理負荷が膨大となり処理し切れない場合であっても、本実施形態の経路探索処理形態は特に有効な処理形態となる。
【００８３】
（他の実施形態）
本発明は、前述した実施形態に限定されるものではなく、例えば、以下に示す変形または拡張が可能である。
【００８４】
地図データとしてノードＮのデータが存在する場合に適用しているが、ノードＮの情報を含まなくても良い。地図データとしてリンクＬの情報を含んでいれば良い。
往路Ｒａおよび復路Ｒｂが一致する条件を満たす往路Ｒａの総コストと当該往路Ｒａの最小総コストの差が第１所定値未満となる条件で、且つ、復路Ｒｂの総コストと当該復路Ｒｂの最小総コストの差が第２所定値未満となり、さらに、往路Ｒａの総コストおよび復路Ｒｂの総コストの総和の最も少ない往路Ｒａおよび復路Ｒｂを探索結果とする実施形態を示したが、ステップＴ１１に説明した条件については省いても良い。
【００８５】
すなわち、ステップＴ１１において総和の少ない順（昇順）に並べ替え、総和の少ない順にステップＴ１２〜Ｔ１５の処理を行うことで往路Ｒａおよび復路Ｒｂを探索しているが、このステップＴ１１の処理を省いても良い。
【００８６】
移動体として車両Ｃａに適用した実施形態を主に示しているが、歩行者であっても良いことは言うまでもなく、経路探索装置Ａは移動体に搭載されたものに限定されるわけではなく、移動体用に携帯可能なネットブック（パーソナルコンピュータ）、インターネットテレビ、携帯電話機、スマートフォン、電子書籍端末、携帯ゲーム機等の移動体用の装置に適用できる。
【００８７】
また、上記実施形態において、図４のステップＴ１２からＴ１５の処理順は、まず往路の総コストが最小総コストに対して第１所定値未満であるものを抽出し、次に復路の総コストが最小総コストに対して第２所定値未満であるものを抽出していた。しかし、これに限らず、まず復路のコストにより候補を抽出し、次いで往路のコストによりその抽出された候補を絞り込むように処理しても構わない。つまり現状の符号を援用すると、現行Ｔ１２→Ｔ１３→Ｔ１４→Ｔ１５の処理順に対して、Ｔ１４→Ｔ１５→Ｔ１２→Ｔ１３のように処理順を変更することも当然可能である。
【符号の説明】
【００８８】
図面中、２は制御装置、２ａは経路探索部（経路探索手段）、Ａは経路探索装置を示す。
【特許請求の範囲】
【請求項１】
往路と復路が一致する条件を満たす往復経路のうち、往路の総コストが最小となる往復経路を特定し、前記特定した最小総コストとの差が第１所定値未満となる総コストの往路からなる往復経路を抽出すると共に、
前記抽出された往復経路のうち、復路の総コストが最小となる往復経路を特定し、前記特定した最小総コストとの差が第２所定値未満となる総コストの復路からなる往復経路を抽出して探索結果とする経路探索手段を備えたことを特徴とする経路探索装置。
【請求項２】
前記経路探索手段は、請求項１記載の条件を満たす往路および復路であって、前記往路の総コストおよび復路の総コストの総和の最も少ない往路および復路を往復経路の探索結果とすることを特徴とする経路探索装置。
【請求項３】
前記経路探索手段は、前記往路を通過する時間帯を考慮して往路の総コストを算出することを特徴とする請求項１または２記載の経路探索装置。
【請求項４】
前記経路探索手段は、前記復路を通過する時間帯を考慮して復路の総コストを算出することを特徴とする請求項１ないし３の何れかに記載の経路探索装置。
【請求項５】
前記経路探索手段は、過去に移動したことがある経験経路を部分的に適用し、過去に移動したことがない経路について部分的に往路および復路が一致する経路を往復経路として探索することを特徴とする請求項１ないし４の何れかに記載の経路探索装置。
【請求項６】
前記経路探索手段が、リンクＩＤの付された道路のリンクを記憶する地図データに基いて往復経路が一致する経路を探索するときには、
往路と復路が同一のリンクＩＤの道路であることを条件として往路および復路が一致すると判定することを特徴とする請求項１ないし５の何れかに記載の経路探索装置。
【請求項７】
前記経路探索手段が、リンクＩＤの付された道路のリンクを記憶する地図データに基いて往復経路が一致する経路を探索するときには、
往路と復路が一致する往復経路の往路の到着時間と、往路のみの最短到着時間との間で第１所定時間以上の乖離がある場合、または／および、往路と復路が一致する往復経路の復路の到着時間と復路のみの最短到着時間との間で第２所定時間以上の乖離がある場合、は、
往路と復路が一致する経路とその往路／復路の到着時間と、往路／復路ごとの最短到着経路とその往路／復路の到着時間を探索し通知することを特徴とする請求項１ないし６の何れかに記載の経路探索装置。
【請求項８】
前記経路探索手段が、リンクＩＤの付された道路のリンクを記憶する地図データに基いて往復経路が一致する経路を探索するときには、
往路と復路が異なるリンクＩＤの道路であるときに、道路名称が無いまたは互いに同一、かつ、道路種別が同一、かつ、リンクＩＤのリンク方向を示す方位差が所定値以内、かつ、それぞれのリンクＩＤの間の距離が所定距離以内であることを所定条件として往路および復路が一致すると判定することを特徴とする請求項１ないし７の何れかに記載の経路探索装置。
【請求項９】
前記経路探索手段が、リンクＩＤの付された道路のリンクを記憶する地図データに基いて往復経路が一致する経路を探索するときには、
往路と復路が異なるリンクＩＤの道路であるときに、高速道路のインターチェンジ、ジャンクションのリンクの前後のリンクについて前記所定条件を満たしていることを条件として往路および復路が一致すると判定することを特徴とする請求項８記載の経路探索装置。
【請求項１０】
前記経路探索手段が、リンクＩＤの付された道路のリンクを記憶する地図データに基いて往復経路が一致する経路を探索するときには、
往路と復路が異なるリンクＩＤの道路であるときに、それぞれのリンクが共に一方通行で且つ通行可能方向が双方逆向きであることを条件に加入して往路および復路が一致すると判定することを特徴とする請求項８または９記載の経路探索装置。
【請求項１１】
往路と復路が一致する条件を満たす往復経路のうち、往路の総コストが最小となる往復経路を特定し、前記特定した最小総コストとの差が第１所定値未満となる総コストの往路からなる往復経路を抽出すると共に、
前記抽出された往復経路のうち、復路の総コストが最小となる往復経路を特定し、前記特定した最小総コストとの差が第２所定値未満となる総コストの復路からなる往復経路を抽出して探索結果とすることを特徴とする経路探索方法。
【請求項１】
往路と復路が一致する条件を満たす往復経路のうち、往路の総コストが最小となる往復経路を特定し、前記特定した最小総コストとの差が第１所定値未満となる総コストの往路からなる往復経路を抽出すると共に、
前記抽出された往復経路のうち、復路の総コストが最小となる往復経路を特定し、前記特定した最小総コストとの差が第２所定値未満となる総コストの復路からなる往復経路を抽出して探索結果とする経路探索手段を備えたことを特徴とする経路探索装置。
【請求項２】
前記経路探索手段は、請求項１記載の条件を満たす往路および復路であって、前記往路の総コストおよび復路の総コストの総和の最も少ない往路および復路を往復経路の探索結果とすることを特徴とする経路探索装置。
【請求項３】
前記経路探索手段は、前記往路を通過する時間帯を考慮して往路の総コストを算出することを特徴とする請求項１または２記載の経路探索装置。
【請求項４】
前記経路探索手段は、前記復路を通過する時間帯を考慮して復路の総コストを算出することを特徴とする請求項１ないし３の何れかに記載の経路探索装置。
【請求項５】
前記経路探索手段は、過去に移動したことがある経験経路を部分的に適用し、過去に移動したことがない経路について部分的に往路および復路が一致する経路を往復経路として探索することを特徴とする請求項１ないし４の何れかに記載の経路探索装置。
【請求項６】
前記経路探索手段が、リンクＩＤの付された道路のリンクを記憶する地図データに基いて往復経路が一致する経路を探索するときには、
往路と復路が同一のリンクＩＤの道路であることを条件として往路および復路が一致すると判定することを特徴とする請求項１ないし５の何れかに記載の経路探索装置。
【請求項７】
前記経路探索手段が、リンクＩＤの付された道路のリンクを記憶する地図データに基いて往復経路が一致する経路を探索するときには、
往路と復路が一致する往復経路の往路の到着時間と、往路のみの最短到着時間との間で第１所定時間以上の乖離がある場合、または／および、往路と復路が一致する往復経路の復路の到着時間と復路のみの最短到着時間との間で第２所定時間以上の乖離がある場合、は、
往路と復路が一致する経路とその往路／復路の到着時間と、往路／復路ごとの最短到着経路とその往路／復路の到着時間を探索し通知することを特徴とする請求項１ないし６の何れかに記載の経路探索装置。
【請求項８】
前記経路探索手段が、リンクＩＤの付された道路のリンクを記憶する地図データに基いて往復経路が一致する経路を探索するときには、
往路と復路が異なるリンクＩＤの道路であるときに、道路名称が無いまたは互いに同一、かつ、道路種別が同一、かつ、リンクＩＤのリンク方向を示す方位差が所定値以内、かつ、それぞれのリンクＩＤの間の距離が所定距離以内であることを所定条件として往路および復路が一致すると判定することを特徴とする請求項１ないし７の何れかに記載の経路探索装置。
【請求項９】
前記経路探索手段が、リンクＩＤの付された道路のリンクを記憶する地図データに基いて往復経路が一致する経路を探索するときには、
往路と復路が異なるリンクＩＤの道路であるときに、高速道路のインターチェンジ、ジャンクションのリンクの前後のリンクについて前記所定条件を満たしていることを条件として往路および復路が一致すると判定することを特徴とする請求項８記載の経路探索装置。
【請求項１０】
前記経路探索手段が、リンクＩＤの付された道路のリンクを記憶する地図データに基いて往復経路が一致する経路を探索するときには、
往路と復路が異なるリンクＩＤの道路であるときに、それぞれのリンクが共に一方通行で且つ通行可能方向が双方逆向きであることを条件に加入して往路および復路が一致すると判定することを特徴とする請求項８または９記載の経路探索装置。
【請求項１１】
往路と復路が一致する条件を満たす往復経路のうち、往路の総コストが最小となる往復経路を特定し、前記特定した最小総コストとの差が第１所定値未満となる総コストの往路からなる往復経路を抽出すると共に、
前記抽出された往復経路のうち、復路の総コストが最小となる往復経路を特定し、前記特定した最小総コストとの差が第２所定値未満となる総コストの復路からなる往復経路を抽出して探索結果とすることを特徴とする経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１２−１０７８７８（Ｐ２０１２−１０７８７８Ａ）
【公開日】平成２４年６月７日（２０１２．６．７）
【国際特許分類】
【出願番号】特願２０１０−２５４７９０（Ｐ２０１０−２５４７９０）
【出願日】平成２２年１１月１５日（２０１０．１１．１５）
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
【公開日】平成２４年６月７日（２０１２．６．７）
【国際特許分類】
【出願日】平成２２年１１月１５日（２０１０．１１．１５）
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
[ Back to top ]