ナビゲーション装置、経路探索サーバ、および経路探索システム
【課題】経路探索システムにおいて、経路探索サーバ（サーバ装置）から得た誘導経路を逸脱した場合に、サーバ装置から新たな誘導経路の提供を受けることなく、最新の地図データが反映された新たな誘導経路を生成する。
【解決手段】経路探索システム７のサーバ装置１は、出発地から目的地までの誘導経路を探索する誘導経路探索部１３０と、予め経路逸脱を想定した予備経路を探索する予備経路探索部１４０とを備え、誘導経路および予備経路に関する情報をナビゲーション装置２に送信する。ナビゲーション装置２は、経路逸脱を検出すると、予備経路の中から現在位置に最も近いノードで構成される予備経路を選択する。そして、ナビゲーション装置２は、現在位置から当該ノードをつなぐ補足経路を探索し、予備経路と補足経路とを合成した経路を新たな誘導経路として経路案内を継続する。
【解決手段】経路探索システム７のサーバ装置１は、出発地から目的地までの誘導経路を探索する誘導経路探索部１３０と、予め経路逸脱を想定した予備経路を探索する予備経路探索部１４０とを備え、誘導経路および予備経路に関する情報をナビゲーション装置２に送信する。ナビゲーション装置２は、経路逸脱を検出すると、予備経路の中から現在位置に最も近いノードで構成される予備経路を選択する。そして、ナビゲーション装置２は、現在位置から当該ノードをつなぐ補足経路を探索し、予備経路と補足経路とを合成した経路を新たな誘導経路として経路案内を継続する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置、経路探索サーバ、および経路探索システムに関するものである。
【背景技術】
【０００２】
放送や通信装置を介して外部の情報センタから最新情報を受信し、その最新情報を考慮して目的地までの経路を誘導するナビゲーション装置が普及しつつある。例えば、交通情報センタからＦＭ多重放送等で提供される渋滞や旅行時間等の最新の交通情報を受信し、その交通情報を考慮した目的地までの最短時間の経路を計算して経路を案内する機能は、ナビゲーション装置の基本機能として定着しつつある。そして、より速く目的地まで到着可能な経路で、より精度良く到着時刻を予測できるよう、車両の通過予定時刻の予測交通情報を情報センタから取得して目的地までの最適経路を計算し誘導するナビゲーション装置も利用されるようになった。また、情報センタで最新の交通情報を反映して計算した最適経路を取得し目的地までの経路を案内するようにしたシステムもある。
【０００３】
交通情報に限らず、外部サイトが有する膨大かつ最新情報を端末に取り込んでナビゲーションサービスを充実させようとする動きがある。例えば、自宅での旅行計画をサポートするポータルサイトでは、動的に変動する施設や道路の利用料金、施設利用状況やイベント情報等の最新情報を考慮した目的地までの経路情報、出発時間、休憩場所等の属性情報を提供している。ポータルサイトで計画した旅行情報をメディアないし通信を介してカーナビ装置に転送することで、目的地までの経路や誘導案内にも利用できるようにしたサービスも存在する。
【０００４】
例えば、カーナビゲーション装置（以下、カーナビ装置という）の要求に応じてセンタで経路探索を行いその結果をカーナビ装置に提供するナビゲーションシステムが開示されている（特許文献１参照）。カーナビ装置で経路探索を行わないことで装置を安価に構成することを目的としているが、センタが最新情報を有していれば、最新情報が反映された経路情報を得ることができる。しかしながら、カーナビ装置では、誘導中に車両が経路から逸脱することがあるため、経路を逸脱した時には再経路探索により車両位置から目的地までの新しい経路情報を提供する必要がある。特許文献１に記載された技術では、端末に経路探索機能を有していないため、経路を逸脱するとセンタから新たな経路情報を得る手続きを行う必要がある。そこで経路を逸脱した場合の対処法として、車両側からのリクエストを受信する度に目的地までの経路を再探索する方法が開示されている（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平１０−１９５８８公報
【特許文献２】特開平２００１−１４７１３２公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特許文献２に記載された技術は、センタに接続する度に目的地までの経路が更新され車両側に提供されるので、経路を逸脱しても新たな誘導経路を用いて目的地までの経路案内を継続することができる。さらに、走行中の通信状態が悪くセンタから経路情報が得られない場合に備え、車両側は受信した経路情報を蓄積し、通信不可を検出すると蓄積した経路情報を用いて経路案内をするようにしている。
【０００７】
しかしながら、誘導経路を走行中は、センタに通信接続するたびに車両位置から目的地までの再計算した誘導経路を車両側に提供するようにしているので、通信コストの増加という課題が残る。また、経路を逸脱した際の対処方法についても、センタから端末装置に車両位置からの新たな経路を配信し、その配信の失敗が継続すると、車両位置が蓄積した経路情報から離れてしまうため経路案内が継続できなくなる事態がしばしば生じることになると予想される。
【０００８】
このような背景に鑑みて本発明がなされたのであり、本発明は、経路逸脱時に新たな誘導経路をセンタから取得する際に生じる通信コストの増加や通信の不安定性による誘導案内のサービス劣化を防ぎ、経路探索サーバ（センタ）が備える最新情報を反映した誘導経路を提供する、ナビゲーション装置、経路探索サーバ、および経路探索システムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
前記課題を解決するために、本発明のナビゲーション装置、経路探索サーバ、および経路探索システムは、経路探索サーバが、出発地から目的地までの誘導経路を探索する誘導経路探索部と、予め経路逸脱を想定した予備経路を探索する予備経路探索部とを備え、誘導経路探索部が探索した誘導経路と、予備経路探索部が探索した予備経路とをナビゲーション装置に送信する。そして、ナビゲーション装置の経路案内部が誘導経路の経路逸脱を検出すると、経路探索部が予備経路の中から現在位置に最も近いノードで構成される予備経路を選択する。そして、経路探索部は、現在位置から当該ノードをつなぐ補足経路を探索し、予備経路と補足経路とを合成した経路を新たな誘導経路として経路案内を継続することを特徴とする。
【００１０】
すなわち、ユーザは、経路を逸脱した時、一時的な電波障害等により経路探索サーバとの通信接続ができず、新たな経路情報が得られないといった、通信の不安定性に悩まされることなく、経路探索サーバが備える最新情報が反映された経路情報を利用しつづけることができるようになり、経路誘導に関わる情報配信の信頼性を向上させることができる。
さらに、提供される予備経路は、目的地までの到達条件を満たす経路に限定し配信するので、経路探索サーバからナビゲーション装置に配信する情報量を削減することができる。
【発明の効果】
【００１１】
本発明によれば、経路逸脱時に新たな誘導経路を取得する際に生じる通信コストの増加や通信の不安定性による誘導案内のサービス劣化を防ぎ、経路探索サーバが備える最新情報を反映した誘導経路を提供するナビゲーション装置、経路探索サーバ、および経路探索システムを提供することができる。
【図面の簡単な説明】
【００１２】
【図１】本実施形態に係る経路探索システムの構成例を示す機能ブロック図である。
【図２】本実施形態に係る経路探索システムの全体の動作手順を示すフローチャートである。
【図３】本実施形態に係るサーバ装置の予備経路探索部が行う予備経路提供エリア設定処理の動作手順を示すフローチャートである。
【図４】本実施形態に係る予備経路提供エリアを示す図である。
【図５】本実施形態に係るサーバ装置の予備経路探索部が行う予備経路提供エリア設定処理の他の動作手順を示すフローチャートである。
【図６】本実施形態に係る予備経路提供エリア設定処理における分岐率について説明するため図である。
【図７】本実施形態に係る予備経路提供エリアの他の例を示す図である。
【図８】本実施形態に係るサーバ装置の予備経路探索部が行う到達コスト条件設定処理の動作手順を示すフローチャートである。
【図９】本実施形態に係る到達コスト条件設定処理を説明するための図である。
【図１０】本実施形態に係るサーバ装置の予備経路探索部が行う予備経路設定処理の動作手順を示すフローチャートである。
【図１１】本実施形態に係る予備経路設定処理を説明するための図である。
【図１２】本実施形態に係るナビゲーション装置の経路案内制御部が行う予備経路情報に基づく誘導経路設定処理の動作手順を示すフローチャートである。
【図１３】本実施形態に係るナビゲーション装置の予備経路情報に基づく誘導経路設定処理を説明するための図である。
【図１４】本実施形態に係るナビゲーション装置が、サーバ装置から経由地点群に関する情報を取得し、誘導経路と予備経路を探索する動作手順を示すフローチャートである。
【図１５】本実施形態に係る経路探索システムにおける経由地点群を用いた誘導経路および予備経路の設定処理について説明するための図である。
【発明を実施するための形態】
【００１３】
次に、本発明を実施するための形態（「実施形態」という）について、適宜図面を参照しながら詳細に説明する。
【００１４】
図１は、本実施形態に係る経路探索システム７の構成例を示す機能ブロック図である。
図１に示すように、本実施形態における経路探索システム７は、サーバ装置（経路探索サーバ）１とナビゲーション装置２とを備えて構成される。また、サーバ装置１とナビゲーション装置２とは、通信ネットワーク３に接続され基地局４を介して、無線通信手段により接続されている。さらに、サーバ装置１は、ブロードバンドネットワーク６を介して、外部情報センタ５に接続されている。
【００１５】
図１に示すように、サーバ装置１は、制御部１０と、補助記憶部１１と、通信部１２と、メモリ部１３と、入出力部１４とを含んで構成される。
【００１６】
制御部１０は、ナビゲーション装置２からの要求を受けて、後記する補助記憶部１１に記憶されたマスタ地図データベース１１１を用いて経路を探索する機能を有し、外部情報取得部１１０と、経路要求処理部１２０と、誘導経路探索部１３０と、予備経路探索部１４０と、経路情報送信部１５０とを含んで構成される。なお、この制御部１０の機能は、例えばサーバ装置１の補助記憶部１１に記憶されたプログラムをＣＰＵ（Central Processing Unit）がメモリ部１３に展開し実行することで実現される。
【００１７】
外部情報取得部１１０は、外部情報センタ５から交通情報や天候、施設情報等の様々な情報（音声や映像情報を含む）を取得し、補助記憶部１１内の外部情報データベース１１２に記憶する。
ここで、外部情報センタ５は、交通情報センタ５１、天気情報センタ５２、観光情報センタ５３等により構成される。この外部情報センタ５から、現況の交通情報、予測交通情報、事故や災害情報、通行規制情報、降水量等の天気情報、観光地の観光ルートや観光施設の営業時間等を含めた観光情報が、ブロードバンドネットワーク６を通じてサーバ装置１に提供される。
【００１８】
経路要求処理部１２０は、ナビゲーション装置２から送信される経路要求情報を受信して、その要求内容を解析し、解析した結果を誘導経路探索部１３０に伝える。このとき、ナビゲーション装置２から取得する経路要求情報とは、経路探索に必要な現在位置（あるいは出発点）、目的地、走行予定日時、探索条件等の情報であり、さらに誘導経路を逸脱したときに利用する予備経路の探索要求情報が含まれる。
【００１９】
探索条件は、有料道路を優先するか、距離ないし時間を優先するか、交通状況を考慮するか等が設定される。また、人気ルートやお勧めルート等、条件として曖昧性を含めたものも受け付けることが可能である。この場合は、経路要求処理部１２０において、曖昧な探索条件から具体的な条件に変換する変換処理を行う。
【００２０】
例えば、経路要求処理部１２０は、「人気ルート」であれば走行頻度の高い道路、「お勧めルート」であればユーザの注目度の高い地点を経由する道路、というように具体的に情報検索可能な表現に変換し、その表現文から検索キーを生成する。生成した検索キーにヒットする情報が外部情報データベース１１２に存在しない場合、あるいは最新情報を必要とする場合、その検索キーを用いて外部情報取得部１１０が必要な情報を外部情報センタ５から収集し、収集した情報を外部情報データベース１１２に記憶する。
交通情報や天候情報等の比較的に短い期間で変動する情報で、経路探索条件として頻繁に利用される情報については、外部情報取得部１１０は、定期的に外部情報センタ５から収集するようにして外部情報データベース１１１に記憶し、常に最新情報が保たれるようにする。
【００２１】
誘導経路探索部１３０は、経路要求処理部１２０で解析した要求を受け付け、経路探索に必要な情報をマスタ地図データベース１１１および前記最新情報が保たれている外部情報データベース１１２から参照し、出発地から目的地までの誘導経路を計算する。
経路探索のアルゴリズムとしては、例えば、出発地から目的地に向かって最小コストとなる経路を求めるダイクストラ法が用いられる。
【００２２】
予備経路探索部１４０は、経路要求処理部１２０が取得した経路要求情報に予備経路の探索要求情報が含まれる場合、誘導経路探索部１３０が探索した誘導経路に関わる予備経路を探索する。例えば、誘導経路の近傍ノード（交差点）を出発地とした目的地までの予備経路を探索する。
【００２３】
経路情報送信部１５０は、誘導経路探索部１３０が探索した誘導経路と予備経路探索部１４０が探索した予備経路とを含めた経路情報を生成し、通信部１２および通信ネットワーク３を介して、ナビゲーション装置２に送信する。
【００２４】
次に、補助記憶部１１は、ハードディスクやフラッシュメモリ等の記憶手段からなり、マスタ地図データベース１１１と、外部情報データベース１１２と、制御部１０を制御するプログラム（図示せず）とを含んで構成される。
【００２５】
マスタ地図データベース１１１は、経路案内に必要な最新の道路データがマスタ地図データとして記憶されている。
また、外部情報データベース１１２は、通信部１２を介して外部情報取得部１１０が、外部情報センタ５から交通情報、天気情報、観光情報等をブロードバンドネットワーク６を介して取得した情報を記憶する。
【００２６】
通信部１２は、ナビゲーション装置２から通信ネットワーク３を介して送信された経路要求情報を受信し、また、外部情報センタ５からブロードバンドネットワーク６を介して送信された情報を受信する。そして、通信部１２は、経路情報送信部１５０が生成した経路情報をナビゲーション装置２へ送信する。
【００２７】
メモリ部１３は、制御部１０の制御により、補助記憶部１１に記憶されたマスタ地図データベース１１１等から読み出された地図情報や、通信部１２が取得した情報を一時的に記憶しておく記憶手段であり、ＲＡＭ（Random Access Memory）やキャッシュメモリ等により構成される。
【００２８】
入出力部１４は、例えば、キーボード、あるいはタッチパネル等を含んで構成され、外部からサーバ装置１への指示を受け付ける。また、制御部１０の処理結果等を液晶モニタ等の表示手段に出力する。
【００２９】
次に、ナビゲーション装置２について説明する。ナビゲーション装置２は、サーバ装置１と通信ネットワーク３を介して接続され、サーバ装置１から経路情報と、後記する予備経路情報とを取得する。
【００３０】
このナビゲーション装置２は、経路案内制御部２０と、補助記憶部２１と、通信部２２と、メモリ部２３と、入出力部２４と、表示部２５と、衛星電波受信部２６とを含んで構成される。
【００３１】
経路案内制御部２０は、通信部２２を介してサーバ装置１から取得した経路情報に基づき、経路案内の処理を行い、経路案内中に誘導経路を逸脱した場合には、予めサーバ装置１から取得した予備経路に基づき、経路案内を行う。また、経路案内制御部２０は、位置情報取得部２１０と、探索条件設定部２２０と、経路要求送信部２３０と、経路情報取得部２４０と、経路探索部２５０と、経路案内部２６０とを含んで構成される。なお、この経路案内制御部２０の機能は、例えばナビゲーション装置２の補助記憶部２１に記憶されたプログラムをＣＰＵがメモリ部２３に展開し実行することで実現される。
【００３２】
位置情報取得部（現在位置算出手段）２１０は、衛星電波受信部２６が衛星から受信した情報を取得して、ナビゲーション装置２の現在位置（自車位置）を算出する。
【００３３】
探索条件設定部２２０は、経路案内の際に必要な出発地や目的地、距離あるいは時間を優先するか、有料道路を優先するか、交通状況を考慮するか等を、入出力部２４を介して設定する。また、探索条件設定部２２０の処理により、誘導経路を逸脱した際の予備経路を予めサーバ装置１から取得しておくか否かの情報が入出力部２４を介して設定される。なお、請求項に記載した出発地設定手段および目的地設定手段は、この探索条件設定部２２０に相当する。
【００３４】
経路要求送信部（送信手段）２３０は、位置情報取得部２１０が算出した現在位置、および探索条件設定部２２０により設定された、出発地、目的地、距離あるいは時間優先等の探索条件、そして、予備経路の探索をユーザが設定した場合には、予備経路の探索要求情報を含む、経路要求情報を生成し、通信部２２を介してサーバ装置１へ送信する。
【００３５】
経路情報取得部（受信手段）２４０は、サーバ装置１から送信された経路情報を、通信部２２を介して取得する。そして、経路情報取得部２４０は、経路情報に含まれる誘導経路に関する情報を、補助記憶部２１内に誘導経路情報２１１として記憶する。また、経路情報に含まれる予備経路に関する情報を、経路情報取得部２４０は、補助記憶部２１内に予備経路情報として記憶する。
【００３６】
経路探索部２５０は、ナビゲーション装置２がサーバ装置１から誘導経路情報２１１を取得していない場合に、補助記憶部２１内の地図データベース２１３と、入出力部２４を介して取得したユーザ入力情報と、位置情報取得部２１０から取得した現在位置の位置情報とに基づいて、目的地までの誘導経路を探索する。
また、経路探索部２５０は、補足経路探索部２５１を備えて構成される。補足経路探索部２５１は、経路案内中に誘導経路を逸脱した場合、現在地から予めサーバ装置１より取得した予備経路に到達するまでの補足経路、あるいは、現在地からもとの誘導経路に復帰するまでの補足経路の探索を行う。ここで、現在地を出発点として、サーバ装置１から得た経路（誘導経路あるいは予備経路）を構成するノードの中から車両の進行方向で現在地に最も近いノードを選択し、前記ノードに到達するまでの経路を補足経路とする。
【００３７】
経路案内部（経路選択手段）２６０は、補助記憶部２１に記憶された誘導経路情報２１１と、位置情報取得部２１０から取得した現在位置の位置情報とに基づいて、目的地までの経路案内を行う。また、経路案内中に誘導経路を逸脱した場合には、補足経路探索部２５１が探索した予備経路までの補足経路に基づき予備経路までの誘導案内を行い、その後補助記憶部２１に記憶された予備経路情報２１２に基づいて、目的地までの経路案内を行う。なお、請求項に記載した経路選択手段と、その経路選択手段を構成する逸脱判断手段および誘導経路再設定手段は、この経路案内部２６０に相当する。
また、ナビゲーション装置２がサーバ装置１から誘導経路情報２１１および予備経路情報２１２を取得していない場合には、経路探索部２５０が補助記憶部２１内の地図データベース２１３を用いて探索した経路に基づいて経路案内を行う。
【００３８】
次に、補助記憶部２１は、ハードディスクやフラッシュメモリ等の記憶装置からなり、誘導経路情報２１１と、予備経路情報２１２と、地図データベース２１３と、経路案内制御部２０を制御するプログラム（図示せず）とを含んで構成される。
【００３９】
誘導経路情報２１１は、サーバ装置１から取得した経路情報に含まれる誘導経路に関す情報を、経路情報取得部２４０の処理により、補助記憶部２１内に記憶した情報である。
予備経路情報２１２は、同様に、サーバ装置１から取得した経路情報に含まれる予備経路に関する情報を、経路情報取得部２４０の処理により、補助記憶部２１内に記憶した情報である。
【００４０】
地図データベース２１３は、誘導案内に必要な地図データを記憶する。
本実施形態において、地図データは、道路データと、目的地を施設名や電話番号等で絞り込んで検索するための目的地検索用データと、表示部２５に地図背景を描画するための背景描画用データと、交差点の右左折案内や走行レーンの案内等を行うための経路誘導用データとを含んで構成させる。
この道路データは、道路を画面表示したり、目的地までの推奨ルートを、例えばダイクストラ法を用いて計算するために、各道路のネットワークを道路リンクと呼ばれる小区間が接続した集合体で表現され、道路リンクの座標や、道路リンク間の接続情報、道路リンクの通過所要時間や距離等を示すコスト情報を、記憶するものである。また、この道路リンクを構成するノード（交差点）の位置情報（緯度・経度）等を含むノード情報が記憶されている。
【００４１】
通信部２２は、経路要求送信部２３０が生成した経路要求情報を、通信ネットワーク３を介してサーバ装置１へ送信する。また、通信部２２は、サーバ装置１から送信された経路情報を受信し、経路案内制御部２０内の経路情報取得部２４０に引き渡す。
【００４２】
メモリ部２３は、経路案内制御部２０の制御により、補助記憶部２１に記憶された誘導経路情報２１１や予備経路情報２１２等から読み出された情報や、通信部２２が取得した情報を一時的に記憶しておく記憶手段であり、ＲＡＭやキャッシュメモリ等により構成される。
【００４３】
入出力部２４は、例えば、リモコン、タッチパネル等を含んで構成され、外部からのナビゲーション装置２への指示を受け付ける。また、経路案内制御部２０の制御のもと、ナビゲーション装置２の各種処理に応じて、音声案内等を図示されていないスピーカを通じて出力する。
【００４４】
表示部２５は、液晶ディスプレイ等で構成されており、経路案内制御部２０の制御のもとに、ナビゲーション処理に応じて、道路状況あるいは誘導案内等を表示する。
【００４５】
衛星電波受信部２６は、ナビゲーション装置２の現在位置を算出するために必要となる衛星からの電波を受信する。衛星からの電波を受信することでその衛星の位置が求まるとともに、ナビゲーション装置２（衛星電波受信部２６）から衛星までの距離（擬似距離）が求まる。そして、４つ以上の衛星から電波を受信することで、ナビゲーション装置２の正確な現在位置が求まる。
【００４６】
なお、図１では、外部情報センタ５から得た最新のコンテンツを考慮した経路をサーバ装置１で探索しナビゲーション装置２に提供するようにしたが、従来の交通情報サービス同様、外部情報センタ５で得た最新コンテンツをナビゲーション装置２に提供することで最新コンテンツを反映した経路を探索する方法もある。しかし、サービス向上を目的にサーバ装置１で扱うコンテンツ量を増やし、コンテンツの更新サイクルを短くした場合、ナビゲーション装置２に提供すべきコンテンツデータが増加し、通信負荷（通信費用や通信時間）の問題が顕在化してくる。故に図１に示すようにサーバ装置１で経路探索を行い、ナビゲーション装置２に提供するデータを必要最小限に抑えることで、コンテンツを増やしても通信負荷を押さえることができる。
【００４７】
次に、図１を参照しつつ、図２に沿って、本実施形態に係る経路検索システム７の処理の流れについて説明する。
図２は、本実施形態に係る経路探索システム７の全体の動作手順を示すフローチャートである。
【００４８】
まず、ナビゲーション装置２は、入出力部２４を介して目的地や探索条件等が入力され、経路案内制御部２０内の探索条件設定部２２０において、探索条件が設定される（ステップＳ２０１）。
次に、探索条件設定部２２０は、ナビゲーション装置２が備える経路探索部２５０において補助記憶部２１内の地図データベース２１３を用いて誘導経路を探索するか、それとも、誘導経路の探索をサーバ装置１に要求するためサーバ装置１に接続するか、を判定する（ステップＳ２０２）。この判定は、探索条件設定部２２０が、入出力部２４を介して表示部２５に設定画面を表示し、ユーザ入力を促して経路探索の処理開始時あるいは予めユーザが設定できるようにする。
【００４９】
ステップＳ２０２において、探索条件設定部２２０が、サーバ装置１に接続の要求をしないと判定した場合は（ステップＳ２０２→Ｎｏ）、ナビゲーション装置２が備える経路探索部２５０において目的地までの誘導経路を探索する（ステップＳ２０４）。
一方、サーバ装置１に接続要求すると判定した場合は（ステップＳ２０２→Ｙｅｓ）、探索条件設定部２２０に設定された目的地、探索条件、現在位置等を含めた経路要求情報を経路要求送信部２３０がサーバ装置１に送信する（ステップＳ２０３）。
【００５０】
次に、サーバ装置１の制御部１０内の経路要求処理部１２０は、通信部１２を介してナビゲーション装置２から経路要求情報を受信する（ステップＳ１０１）。
そして、受信した経路要求情報に含まれる現在位置（ないし出発地）、目的地、探索条件等の情報を経路要求処理部１２０から受け取った誘導経路探索部１３０が、目的地までの誘導経路を探索する（ステップＳ１０２）。
【００５１】
また、経路要求処理部１２０は、経路要求情報に予備経路の探索要求が含まれているか否かを判断する（ステップＳ１０３）。
この予備経路の探索要求は、ナビゲーション装置２の探索条件設定部２２０が、入出力部２４を介して表示部２５に設定画面を表示し、ユーザ入力を促して経路探索の処理開始時あるいは予めユーザが設定できるようにする。
予備経路の探索要求が含まれていない場合は（ステップＳ１０３→Ｎｏ）、ステップＳ１０８へ進む。一方、予備経路の探索要求が含まれている場合は（ステップＳ１０３→Ｙｅｓ）、次のステップＳ１０４の予備経路提供エリア設定処理へ進む。
【００５２】
ステップＳ１０４において、予備経路探索部１４０は、誘導経路の近傍において予備経路を提供するエリアを設定する（後記する図３、図５参照）。
ここで、予備経路を設定するエリアを定めるのは、サーバ装置１に複数ユーザから経路要求が集中すると、一時的にサーバ負荷が増大し応答時間が長くなること、また、移動中の通信状況を考慮するとできるだけ速やかに経路情報を返信すべきことによる。そのためには、予備経路を探索するための計算量を必要最小限に留めて、探索処理の応答時間を所定時間内に維持する必要がある。そこで、計算量を抑えるために、探索エリアを必要最小限に狭めることが有効となる。予備経路を提供するエリアは、誘導経路沿いにその誘導経路から所定距離内のエリアを対象とする方法、その誘導経路を含むメッシュ領域を対象とする方法等考えられるが、ここではさらにエリアを絞り込む方法として、誘導経路のコストを用いた絞込みを行う。
【００５３】
ここで、誘導経路のコストには、誘導経路の所定地点間を移動する場合の距離、旅行時間、費用（燃料消費量、高速代金、その移動時間にかかる人件費等）、ＣＯ２排出量等を設定することができるが、本実施形態においては、誘導経路の所定地点間の距離を前提に説明する。つまり、２地点間の距離が短ければコストが低く、距離が長ければコストが高い経路となる。また、２点間において出発地点から到達地点までにかかるコストを到達コストとして以下説明する。
【００５４】
次に、予備経路探索部１４０は、到達コスト条件設定処理を行う（ステップＳ１０５）。予備経路探索部１４０が、この処理を行うことにより、予備経路提供エリアを設定した上で、さらにその提供エリア内において、基準となる所定の到達コスト以内という到達コスト条件を満たした範囲内で予備経路の設定ができる。つまり、予備経路提供エリア内であっても、遠回りで距離や時間等のコストが所定値以上かかる到達コストの経路は、予備経路として設定しないようにする。なお、到達コスト条件設定処理の詳細については、図８において詳細に説明する。
【００５５】
そして、予備経路探索部１４０は、ステップＳ１０４で設定された予備経路提供エリア内において、ステップＳ１０５で設定された到達コスト条件満たすノード（交差点）について、予備経路設定処理を行う（ステップＳ１０６）。なお、この予備経路設定処理については、図１０において詳細に説明する。
【００５６】
次に、予備経路探索部１４０は、予備経路提供エリア内の全てノードを処理したか否かを判断する（ステップＳ１０７）。全てのノードの処理を終えていない場合には（ステップＳ１０７→Ｎｏ）、ステップＳ１０６に戻り処理を続ける。一方、全てのノードの処理を終えている場合には（ステップＳ１０７→Ｙｅｓ）、次のステップＳ１０８へ進む。
【００５７】
ステップＳ１０８において、経路情報送信部１５０は、誘導経路探索部１３０が探索した誘導経路情報と、予備経路探索部１４０が設定した予備経路情報とを含む経路情報を、ナビゲーション装置２へ送信する（ステップＳ１０８）。
【００５８】
次に、ナビゲーション装置２の経路情報取得部２４０は、サーバ装置１から誘導経路情報と予備経路情報とを含んだ経路情報を、通信部２２を介して取得する（ステップＳ２０５）。
【００５９】
続いて、ステップＳ２０４あるいはＳ２０５において取得した誘導経路情報を用いて、経路案内部２６０は、位置情報取得部２１０から得た現在位置の位置情報と合わせて目的地までの経路案内を行う（ステップＳ２０６）。
【００６０】
次に、経路案内部２６０は、現在位置が目的地に到着したか否かを判断する（ステップＳ２０７）。目的地に到着していれば（ステップＳ２０７→Ｙｅｓ）、経路案内部２６０は処理を終える。一方、目的地に到着していなければ（ステップＳ２０７→Ｎｏ）、経路案内部２６０は、現在位置が誘導経路から逸脱しているか否かを判断する（ステップＳ２０８）。
【００６１】
現在位置が誘導経路を逸脱していなければ（ステップＳ２０８→Ｎｏ）、ステップＳ２０６へ戻り誘導経路の案内処理を続ける。一方、経路案内部２６０が、誘導経路を逸脱していると判断した場合は（ステップＳ２０８→Ｙｅｓ）、次のステップＳ２０９へ進む。
【００６２】
ステップＳ２０９において、経路案内部２６０は、補助記憶部２１の予備経路情報２１２に、誘導経路案内中の誘導経路に対応した予備経路情報が記憶されているか否かを判断する（ステップＳ２０９）。予備経路情報が記憶されていない場合には（ステップＳ２０９→Ｎｏ）、ステップＳ２０４へ戻り、経路探索部２５０が、補助記憶部２１内の地図データベース２１３を用いて、経路探索を行う。
一方、予備経路情報が記憶されている場合には、次のステップＳ２１０へ進み、経路案内部２６０は、予備経路情報に基づいて、現在位置から目的地までの新たな経路を誘導経路として設定する処理を行う（ステップＳ２１０）。なお、この予備経路情報に基づく誘導経路設定処理については、後記する図１２において詳細に説明する。
そして、経路案内部２６０は、ステップＳ２０６へ戻り、予備経路に基づいて設定された誘導経路の案内処理を続ける。
【００６３】
以上の手順は、ナビゲーション装置２からの経路要求に応じてサーバ装置１が誘導経路情報および予備経路情報を提供することを想定しているが、自動車等に搭載されたナビゲーション装置２とは異なる端末装置としてパーソナルコンピュータや携帯電話等を用いて自宅や出先から旅行計画を行う際に、サーバ装置１に目的地までの経路を要求するようにしてもよい。この場合、サーバ装置１に一時的に経路を記憶する記憶手段を設けておき、端末装置からサーバ装置１に予め計画した誘導経路を要求すると、サーバ装置1に既に記憶されている誘導経路を端末装置に送信するようにすることもできる。
【００６４】
なお、これまで本実施形態においては、現在位置を出発地として説明してきたが、ナビゲーション装置２が他に入力手段を備えるか、または入出力部２４からにより入力された位置を出発地としてもよい。
【００６５】
次に、図２のステップＳ１０４における予備経路提供エリア設定処理について説明する。
【００６６】
（予備経路提供エリア設定処理についての実施形態１）
図３は、本実施形態に係るサーバ装置１の予備経路探索部１４０が行う予備経路提供エリア設定処理の動作手順を示すフローチャートである。また、図４は、本実施形態に係る予備経路提供エリアを示す図である。
【００６７】
まず、予備経路探索部１４０は、図２のステップＳ１０２で探索した誘導経路を分割し（ステップＳ３０１）、補助記憶部１１内のマスタ地図データベース１１１から、誘導経路の各分割点のうちの一つを読み込む（ステップＳ３０２）。ここで、誘導経路を分割するための分割点Ｐiは経路を構成するノード（交差点）をとる。ただし、経路分割が可能であれば経路付近のノードを用いても、メッシュや行政区の境界点でも構わない。図４に示す例においては、分割点Ｐi（ｉ＝１〜ｎ−１）を、経路（符号４５０）上のノードＰ2,Ｐ3とする。
【００６８】
次に、予備経路探索部１４０は、分割経路のコストＴiを基準コストに設定し、分割経路の起点から同コストで移動可能なエリアＡiを設定する（ステップＳ３０３）。
図４に示す例においては、現在位置（符号４００）すなわちノードＰ1（誘導経路の出発点）から分割点ノードＰ2までが最初の分割経路となり、予備経路探索部１４０が、分割経路のノードＰ1からノードＰ2に向かうコストＴ1を基準コストとして設定する。そして、予備経路探索部１４０は、ノードＰ1から基準コストＴ1で移動可能なエリアＡ1を設定する。
【００６９】
次に、予備経路探索部１４０は、分割経路の終点から設定した基準コストＴiで移動可能なエリアＢiを設定する（ステップＳ３０４）。
図４に示す例においては、ノードＰ2からノードＰ1に向かって基準コストＴ1で移動可能なエリアＢ1を、予備経路探索部１４０が設定する。
【００７０】
続いて、予備経路探索部１４０は、エリアＡiとエリアＢiとが重なるエリアＣiを分割経路の提供エリアとする（ステップＳ３０５）。
図４に示す例においては、予備経路探索部１４０は、Ａ1とＢ1とが重なるエリアＣ1を分割経路の予備経路提供エリアとする。
【００７１】
そして、予備経路探索部１４０は、全ての分割経路の提供エリアを設定したか否かを判断する（ステップＳ３０６）。ここで、全ての分割経路の提供エリアを設定した場合には（ステップＳ３０６→Ｙｅｓ）、次のステップＳ３０７に進む。一方、設定していない分割経路の提供エリアがある場合には、ステップＳ３０２へ戻り処理を続ける。
【００７２】
続いて、予備経路探索部１４０は、ステップＳ３０７において、全てのエリアＣ1〜n-1を含むエリアを予備経路の提供エリアと設定する。
図４においては、ステップＳ３０２〜Ｓ３０５の処理を繰り返すことにより、分割経路Ｐ2〜Ｐ3の基準コストＴ2に基づいた予備経路提供エリアＣ2、分割経路Ｐ3〜Ｐ4の基準コストＴ3に基づいた予備経路提供エリアＣ3が設定され、目的地Ｐ4に到達するまでの全分割経路の提供エリアが設定される。そして、設定したエリアＣ1〜Ｃ3を包含するエリアを誘導経路Ｐ1〜Ｐ4の予備経路提供エリア（符号４０１）として設定する。ここで提供エリアとして若干のマージンを含めたより広いエリア（符号４０２）としてもよい。
このようにすることで、予備経路探索部１４０により、予備経路提供エリアが設定される。
【００７３】
（予備経路提供エリア設定処理についての実施形態２）
図５は、本実施形態に係るサーバ装置１の予備経路探索部１４０が行う予備経路提供エリア設定処理の他の動作手順を示すフローチャートである。
【００７４】
まず、予備経路探索部１４０は、図２のステップＳ１０２で探索した誘導経路を構成する経路の分岐点としてノード（交差点）Ｐi（ｉ＝１〜ｎ）の一つを、補助記憶部１１内のマスタ地図データベース１１１から読み込む（ステップＳ５０１）。
【００７５】
次に、予備経路探索部１４０は、読み込んだノード（交差点）についてのノード情報からそのノードの分岐数、分岐率を取得する（ステップＳ５０２）。
ここで、分岐数は、そのノードから分岐する道路リンク数をそのまま用いてもよいが、ここでは車両等がそのノードに進入する進入リンクを除いた道路リンク数とする。
また分岐率は、そのノードにおいて、複数のリンクに交通量が分岐して流出するほど大きな値を持つようにする指標である。
【００７６】
図６は、本実施形態に係る予備経路提供エリア設定処理における分岐率について説明するため図である。
図６に示すように、ある時間帯においてノードＰへの進入リンクとなる道路リンクＬinの交通量を１０００、脱出リンクとなる道路リンクＬ1、Ｌ2、Ｌ3の交通量を各々２００，３００，５００とする。各脱出リンクに流出する交通量の割合は、Ｌ1において２００÷１０００＝０．２、Ｌ2において３００÷１０００＝０．３、Ｌ3において５００÷１０００＝０．５となる。最大値０．５で各方向における割合値を正規化すると、Ｌ1方向が０．４、Ｌ2方向が０．６、Ｌ3方向が１となる。Ｌ3方向を除きこれらの平均値を求めると（０．４＋０．６）÷２＝０．５となり、本実施形態においては、この値を、当該時間帯における進入リンクＬinの時のノードＰの分岐率とする。この分岐率を例えば一日２４時間を単位時間で分割した全ての単位時間帯および進入リンク毎に算出する。進入リンク毎に算出した分岐率の平均値を計算し、進入リンクに関係なく各ノードにおいて一つの分岐率を持つようにしてもよい。
【００７７】
なお、本実施形態において、分岐率は、分岐数と共にノード情報としてマスタ地図データベース１１１に予め記憶されているものとする。ただし、外部情報センタ５から分岐率を取得してマスタ地図データベース１１１に記憶するようにしてもよい。また、サーバ装置１の構成要素として分岐率を計算する分岐率算出手段を新たに設け、外部情報センタ５から取得した交通情報（交通量を含む）に基づいて分岐率を計算するようにしてもよい。さらに、ナビゲーション装置２からの経路要求情報と共に走行データを受信し、その走行データから分岐率を算出する方法も考えられる。
【００７８】
図５に戻り、予備経路探索部１４０は、ステップＳ５０３において、ノードに関する提供エリアＣiを、以下の式（１）に示すように、ノードに接続される分岐数や分岐率に基づいて設定する。
【００７９】
提供エリアＣi＝ 基準半径ｒ×分岐数×分岐率 （分岐率＞０） … 式（１）
【００８０】
ここで、基準半径ｒは、ノードを中心としたエリアの半径である。例えば、ナビゲーション装置２の走行速度を仮に６０ｋｍ/ｈとし、経路逸脱から２分以内に移動可能な範囲に存在するノードを予備経路として保障するようにして６０ｋｍ/ｈ÷６０×２＝２ｋｍを基準半径ｒとする。また、分岐率は０以上となるような最小値を予め設定しておく。
【００８１】
次に、予備経路探索部１４０は、全てのノードの提供エリアを設定したか否かを判断する（ステップＳ５０４）。そして、全てのノードの提供エリアの設定がされていなければ（ステップＳ５０４→Ｎｏ）、ステップＳ５０１へ戻り処理を続ける。一方、全てのノードの提供エリアの設定が終わっていれば（ステップＳ５０４→Ｙｅｓ）、次のステップＳ５０５へ進む。
【００８２】
ステップＳ５０５において、予備経路探索部１４０は、設定した全ての提供エリア Ｃ1〜nを予備経路の提供エリアとする。
具体的には、予備経路探索部１４０が、全分岐点に関わる提供エリアＣiを設定し、その全提供エリアＣi、あるいは全提供エリアＣiを包含するエリアを予備経路の提供エリアとする。
【００８３】
図７は、本実施形態に係る予備経路提供エリアの他の例を示す図である。
図７に示すように、ノードＰ2は分岐数が多く分岐率も高いことから、提供エリアＣ2（符号７０１）が広く設定される。これより様々な方向に車両が分岐し経路を逸脱するリスクも高い箇所で、そのリスクに応じて予備経路を提供することができる。ノードＰ3は、例えば、分岐数は多いが分岐率が小さいため、ノードＰ3での経路逸脱のリスクは低いとし、提供エリアＣ3（符号７０２）はＣ2（符号７０１）に比べて小さくなる。
【００８４】
図７に示すノードＰiの設定において、誘導経路を構成する全てのノードについて提供エリアを設定するのではなく、誘導経路を構成するノードの中で分岐数や分岐率の高いノードを対象に提供エリアを選択するようにしてもよい。さらに、現在位置付近は移動距離が短いため大きく迷うリスクが低く、目的地周辺も目的地に近づくにつれて、移動距離が短くなるので大きく迷うことがないことから、中間地点のノードよりも提供エリアを狭くとるようにしてもよい。
【００８５】
（到達コスト条件設定処理）
次に、図２のステップＳ１０５における到達コスト条件設定処理について説明する。
図８は、本実施形態に係るサーバ装置１の予備経路探索部１４０が行う到達コスト条件設定処理の動作手順を示すフローチャートである。また、図９は本実施形態に係る到達コスト条件設定処理を説明するための図である。この到達コスト条件設定処理においては、到達コスト条件を適用するエリア（条件設定対象エリア）を設定し、到達コスト条件を設定する。
【００８６】
まず、予備経路探索部１４０は、図２のステップＳ１０２で、すでに読み込んである現在位置と目的地に加えて、図３のステップＳ３０１で分割した分割経路の起点Ｐiおよび終点Ｐi+1のノード情報（ノード座標等）を、補助記憶部１１のマスタ地図データベース１１１から読み込む（ステップＳ８０１）。
【００８７】
次に、起点Ｐiから目的地までの到達コストＴＰ(i)を基準として、予備経路探索部１４０は、目的地から当該到達コストＴＰ(i)において到達可能なエリアＥＰ(i)を設定する（ステップＳ８０２）。図９に示す例では、起点Ｐi＝Ｐ1のとき、ＴＰ(i)＝ＴＰ１＝Ｔ1＋Ｔ2＋Ｔ3を基準として、当該到達コストＴＰ１以下で到達可能なエリアＥＰ(i)（符号９０１）を設定する。ここで、例えば、目的地への到達コストが所要時間やＣＯ２排出量等であった場合には、これらを距離に換算した値からエリアＥＰ(1)（符号９０１）を設定する。
【００８８】
続いて、予備経路探索部１４０は、分割経路の終点Ｐi+1から目的地までの到達コストＴＰ(i＋1)を基準として、目的地から当該到達コストＴＰ(i＋1)以下で到達可能なエリア ＥＰ(i＋1)を設定する（ステップＳ８０３）。図９に示す例では、起点Ｐi+1＝Ｐ2のとき、ＴＰ(i＋1)＝ＴＰ２＝Ｔ2＋Ｔ3を基準として、当該到達コストＴＰ２以下で到達可能なエリアＥＰ(2)（符号９０２）を設定する。
【００８９】
そして、予備経路探索部１４０は、予備経路提供エリア（符号４０１）内において、ステップＳ８０２で設定したエリアＥＰ(i)と一致し、ステップＳ８０３で設定したエリアＥＰ(i＋1)との境界までを条件設定対象エリアとする（ステップＳ８０４）。図９に示す例では、予備経路提供エリア（符号４０１）内において、エリアＥＰ１以内であり、エリアＥＰ２と境界するエリア（符号９１１）が、条件設定対象エリアとなる。
【００９０】
次に、予備経路探索部１４０は、ステップＳ８０４で設定した条件設定対象エリア内に存在するノードから目的地に向かう経路の到達コスト条件を、以下の式（２）をもとに設定する（ステップＳ８０５）。
【００９１】
到達コスト条件 ≦ ＴＰ(i)＋ α・Ｔｃ … 式（２）
【００９２】
式（２）において、Ｔｃは予め設定したマージンコスト、αは目的地に近づくに従ってマージンコストＴｃが小さくなるようにした重みパラメータで、例えば式（３）により設定する。
【００９３】
α＝（Ｔ−∂Ｔ）／Ｔ … 式（３）
【００９４】
Ｔは当該誘導経路の出発点から目的地までの所要コスト、∂Ｔは出発点から当該対象エリア内の所定地点までの移動コストである。
図９に示す例においては、エリアＥＰ１内における到達コスト条件ＴＰ１が、
ＴＰ１ ≦ Ｔ1＋Ｔ2＋Ｔ3＋αＴｃ
と設定される。
【００９５】
そして、予備経路探索部１４０は、分割経路の終点が目的地であるか否かを判断する（ステップＳ８０６）。分割経路の終点が目的地でなければ（ステップＳ８０６→Ｎｏ）、ステップＳ８０１に戻り処理を続ける。
図９に示す例においては、エリアＥＰ２内における到達コスト条件ＴＰ２が、
ＴＰ２ ≦ Ｔ2＋Ｔ3＋αＴｃ
と設定され、エリアＥＰ３内における到達コスト条件ＴＰ３が、
ＴＰ３ ≦ Ｔ3＋αＴｃ
と設定される。
【００９６】
一方、分割経路の終点が目的地であれば（ステップＳ８０６→Ｙｅｓ）、予備経路探索部１４０は、到達コスト条件設定処理を終える。
【００９７】
（予備経路設定処理）
次に、図２のステップＳ１０６における予備経路設定処理について説明する。
図１０は、本実施形態に係るサーバ装置１の予備経路探索部１４０が行う予備経路設定処理の動作手順を示すフローチャートである。
【００９８】
図１０において、まず、サーバ装置１の予備経路探索部１４０は、図２のステップＳ１０４において設定した予備経路提供エリアを参照する（ステップＳ１００１）。
そして、予備経路探索部１４０は、補助記憶部１１のマスタ地図データベース１１１を参照して、当該予備経路提供エリア内に存在する全てのノードを検索する（ステップＳ１００２）。
ここで、検索したノードのノード情報（ノード座標等）やノードに接続される道路の種別や道路幅等の道路情報により、幹線道路に接続されるノード（交差点）のみを対象とすることで検索ノード数を絞ることも可能である。
【００９９】
次に、予備経路探索部１４０は、検索したノードのうちの一つを選択する（ステップＳ１００３）。そして、選択したノードが到達コスト条件を設定したどの条件設定対象エリアに存在するかを判断し、図８のステップＳ８０５で設定した到達コスト条件を設定する（ステップ１００４）。
【０１００】
そして、予備経路探索部１４０は、当該ノードから目的地までの経路を探索する（ステップＳ１００５）。そして、その探索した経路が、ステップＳ１００４で設定した到達コスト条件を満たすか否かを判断する（ステップＳ１００６）。当該経路の目的値までの到達コストが所定値より大きく、到達コスト条件を満たさない場合には（ステップＳ１００６→Ｎｏ）、ステップＳ１００８へ進む。一方、当該経路の目的地までの到達コストが所定値以下であり、到達コスト条件を満たす場合には（ステップＳ１００６→Ｙｅｓ）、予備経路探索部１４０は、当該経路を予備経路として設定する（ステップＳ１００７）。
【０１０１】
続いて、予備経路探索部１４０は、予備経路提供エリア内にある全てのノードを処理したか否かを判断する（ステップＳ１００８）。まだ、処理していないノードがある場合には（ステップＳ１００８→Ｎｏ）、ステップＳ１００３に戻り処理を続ける。一方、全てノードの処理を終えた場合には（ステップＳ１００８→Ｙｅｓ）、予備経路設定処理を終了する。
【０１０２】
次に、図１０に示した予備経路設定処理を図１１を参照して具体的に説明する。
図１１は本実施形態に係る予備経路設定処理を説明するための図である。
【０１０３】
図１１に示すように、図１０のステップＳ１００２において、予備経路探索部１４０により、予備経路を探索するための候補ノードとして、予備経路提供エリア（符号４０１）内に存在するノードＰ20，Ｐ21，Ｐ30，Ｐ31，Ｐ32，Ｐ33，Ｐ40が検索されたとする。
【０１０４】
次に、これらの検索されたノードのうちの一つ例えばＰ20を、予備経路探索部１４０が選択する（ステップＳ１００３）。そして、予備経路探索部１４０は、ノードＰ20が条件設定対象エリア（符号９１１）内に位置することから、図８のステップＳ８０５で設定したエリアＥＰ１の到達コスト条件を設定する（ステップＳ１００４）。
ＴＰ１ ≦ Ｔ1＋Ｔ2＋Ｔ3＋αＴｃ … 式（４）
【０１０５】
続いて、予備経路探索部１４０は、ノードＰ20から目的地ノードＰ4までの経路を検索し（ステップＳ１００５）、当該経路の到達コストが、数式（４）の条件を満たすか否かを判断する（ステップＳ１００６）。そして、式（４）の条件を満たす場合に（ステップＳ１００６→Ｙｅｓ）、予備経路探索部１４０は、ステップＳ１００５で検索したノードＰ20から目的地であるノードＰ4までの経路を、予備経路として設定する（ステップＳ１００７）。
この一連の処理を、予備経路探索部１４０は、ステップＳ１００２で検索した全てのノードについて実行し、予備経路として設定する処理を行う。
このようにすることで、予備経路探索部１４０は、所定の到達コスト以下の予備経路だけを抽出し設定することができる。
【０１０６】
（ナビゲーション装置の予備経路情報に基づく誘導経路設定処理）
次に、図２のステップＳ２１０におけるナビゲーション装置２の予備経路情報に基づく誘導経路設定処理について説明する。
図１２は、本実施形態に係るナビゲーション装置２の経路案内制御部２０が行う予備経路情報に基づく誘導経路設定処理の動作手順を示すフローチャートである。
【０１０７】
図２のステップＳ２０８において、ナビゲーション装置２の経路案内部２６０が、誘導経路を逸脱したと判断し（ステップＳ２０８→Ｙｅｓ）、かつステップ２０８において、サーバ装置１より当該誘導経路に関する予備経路情報が補助記憶部２１に記憶されていた場合（ステップＳ２０９→Ｙｅｓ）、補足経路探索部２５１は、次のように予備経路情報に基づく誘導経路設定処理を行う。
【０１０８】
まず、補足経路探索部２５１は、補助記憶部２１の予備経路情報２１２に記憶された予備経路情報を参照し、現在位置に最も近いノードを構成ノード（始終点および中間ノード）とする予備経路を選択する（ステップＳ１２０１）。このとき現在位置からの距離に加えてナビゲーション装置２の進行方向を考慮し、進行方向にあるノードを優先し予備経路を選択する。
【０１０９】
次に、補足経路探索部２５１は、選択した予備経路を構成する、現在位置に最も近い構成ノードを仮目的地として、現在位置から仮目的地までの経路を探索する（ステップＳ１２０２）。探索した経路は現在位置と予備経路とをつなぐための補足経路として用いる。
【０１１０】
続いて、補足経路探索部２５１は、経路逸脱してからしばらく走行し続けると、現在位置が距離的にも時間的にも予備経路から遠く離れてしまうことが考えられるため、現在地から仮目的地までの到達コストが予め設定した所定値を超えるか否か判断する（ステップＳ１２０３）。到達コストが所定値以下の場合は（ステップＳ１２０３→Ｎｏ）、補足経路探索部２５１は、補足経路と予備経路とを合成した経路を、現在位置から目的地までの新たな誘導経路として設定する（ステップＳ１２０４）。
【０１１１】
このようにすることで、ナビゲーション装置２は、経路を逸脱しても、予め取得した予備経路を用いて、サーバ装置１との通信を行わず、新たな経路を設定し目的地まで経路案内をすることができる。予備経路はサーバ装置１が提供した経路であるため、経路を逸脱してもサーバ装置１に再度経路要求することなく、サーバ装置１が備える最新情報が反映された経路を利用して経路案内を継続することができる。
【０１１２】
一方、ステップＳ１２０３において、補足経路の到達コストが所定値を超えている場合は（ステップＳ１２０３→Ｙｅｓ）、経路案内部２６０は、表示部２５や音声案内を用いて、サーバ装置１から得た経路による誘導が継続できないことをユーザに通知する（ステップＳ１２０５）。
【０１１３】
次に、経路案内部２６０は、探索条件設定部２２０を介して、サーバ装置１に再接続し新たな経路を要求するか否かを判断する（ステップＳ１２０６）。新たな経路を要求する場合は（ステップＳ１２０６→Ｙｅｓ）、経路要求送信部２３０が、サーバ装置１に新たな経路要求情報を送信する（ステップＳ１２０７）。
【０１１４】
そして、経路要求送信部２３０は、ナビゲーション装置２が移動中、トンネルやビル等の構造物による遮蔽により通信状態が不安定な場合もあるので、通信エラーが発生しているか否かを監視する（ステップＳ１２０８）。通信エラーが発生していない場合には（ステップＳ１２０８→Ｎｏ）、図２のステップＳ２０５に戻り、サーバ装置１から経路情報を取得して処理を進める。
一方、通信エラーが発生した場合には（ステップＳ１２０８→Ｙｅｓ）、経路要求送信部２３０は、何回リトライを行ったかを記憶しておき、リトライ数が所定値を超えたか否かを判断する（ステップＳ１２０９）。このリトライ数が所定値を超えていない場合には（ステップＳ１２０９→Ｎｏ）、経路要求送信部２３０は、ステップＳ１２０７へ戻り処理を続ける。一方、リトライ数が所定値を超えた場合には（ステップＳ１２０９→Ｙｅｓ）、サーバ装置１との通信接続をあきらめ、経路探索部２５０が、ナビゲーション装置２の補助記憶部２１に記憶された地図データベース２１３を用いて、現在位置から目的地までの誘導経路の探索を行う（ステップＳ１２１０）。
【０１１５】
ステップＳ１２１０において、ナビゲーション装置２が備える到達コストを用いて経路探索を行った結果、先にサーバ装置１が提供した誘導経路と異なる経路が探索されることもあるが、予備経路が無効かつ通信不安定となった場合でも、目的地までの経路誘導を継続することを優先し、ナビゲーション装置２の経路探索を利用する。
【０１１６】
次に、この図１２に示したナビゲーション装置２の予備経路情報に基づく誘導経路設定処理について具体的に説明する。
図１３は、本実施形態に係るナビゲーション装置２の予備経路情報に基づく誘導経路設定処理を説明するための図である。図１３に示す例は、ナビゲーション装置２が誘導経路（符号４５０）を逸脱して現在位置（符号４００）に位置する場合に、補足経路探索部２５１が、予備経路を用いて新たな誘導経路を提供することを示している。
【０１１７】
まず、補足経路探索部２５１は、現在位置（符号４００）に最も近いノードＰ20を構成ノードとし、構成ノードＰ20を始点とする予備経路（符号１３００）を選択する（ステップＳ１２０１）。予備経路（符号１３００）はノードＰ20を始点とした目的地Ｐ4までの経路である。
次に、補足経路探索部２５１は、現在位置（符号４００）から構成ノードＰ20をつなぐ補足経路を探索する（ステップＳ１２０２）。ただし、現在位置（符号４００）が予備経路（符号１３００）の中間ノードであるＰ32に近い場合は、Ｐ32が構成ノードとして設定される場合もある。また、予備経路を用いた新たな誘導経路に切り替えることを行わず、元の経路に戻る経路を利用することも可能である。その場合は、元の誘導経路上で現在位置（符号４００）に最も近い、あるいは現在位置（符号４００）から最小コストで到達可能なノード（図ではＰ21）を仮目的地として補足経路を探索する。補足経路の探索は、現在位置近傍に存在するノードが仮目的地として設定されるため、移動距離が短く、ナビゲーション装置２が備える地図データベース２１３を用いた到達コストを用いて補足経路を探索しても、サーバ装置１で算出した経路との到達コストの差は大きくならない。
【０１１８】
このようにすることで、ナビゲーション装置２は、経路逸脱をした場合に、再度サーバ装置１に経路要求することなく、予めサーバ装置１から取得した最新の地図データに基づく予備経路情報を利用して、経路案内を続けることができる。
【０１１９】
以上のように、本実施形態に係るナビゲーション装置、経路探索サーバ（サーバ装置）、および経路探索システムによれば、サーバ装置１から提供される誘導経路を用いて目的地までの経路を誘導し、誘導経路に従って経路を走行中に経路逸脱した場合でも、現在地から目的地までの新たな経路をサーバ装置１に要求することなく、既に取得した予備経路を用いて新たな誘導経路を生成することができる。そのため、誘導経路取得に伴う通信コストが軽減し、さらには不安定な通信状態の影響を受けることなく、目的地までの経路案内を継続することができる。
【０１２０】
すなわち、ユーザは、経路を逸脱した時、一時的な電波障害等によりサーバ装置との通信接続ができず、新たな経路情報が得られないといった、通信の不安定性に悩まされることがなく、サーバ装置が備える最新情報が反映された経路情報を利用し続けることができる。それにより、経路誘導に関わる情報配信の信頼性を向上させることができる。
さらに、提供される予備経路は、目的地までの到達コスト条件を満たす経路に限定し配信されるので、サーバ装置からナビゲーション装置に配信する情報量を削減することができる。
【０１２１】
また、サーバ装置１は、外部情報センタ５からの情報を用いて、交通情報に限らず施設の利用状況やイベント情報等の最新情報を反映した誘導経路、さらに複数車両の走行データに基づいて走行頻度の高い人気経路や、ドライバから提供されたお勧めの経路や施設といった、ナビゲーション装置２が備える探索条件（距離や時間、有料道路等）よりも豊富な条件を取り入れた誘導経路を探索できる。従って、より利用者の要求に近い経路が提供されるようになり、ナビゲーション装置２の利用者に対しても利便性を向上させることができる。
【０１２２】
（誘導経路および予備経路の設定処理についての変形例）
次に、図１の経路探索システム７における誘導経路および予備経路の設定処理の変形例について説明する。図２に示した経路検索システム７の処理においては、サーバ装置１の誘導経路探索部１３０がマスタ地図データベース１１１を用いて誘導経路の探索を行い、予備経路探索部１４０がその誘導経路に関する予備経路を探索し、誘導経路情報と予備経路情報とを経路情報としてナビゲーション装置２へ送信する構成とした。
ここでは、サーバ装置１からナビゲーション装置２に提供される経路情報の配信量を低減させるために、サーバ装置１の経路情報送信部１５０が、誘導経路および予備経路を構成するノード情報から複数の代表ノード（例えば、幹線道路が交わる交差点）を選択して経由地点群とし、その経由地点（座標と経由する順番を含む）群を経路情報としてナビゲーション装置２へ配信する処理を行い、ナビゲーション装置２側で、経路探索処理を行う実施形態について説明する。
【０１２３】
図１４は、ナビゲーション装置２が、サーバ装置１から経由地点群に関する情報を取得し、誘導経路と予備経路を探索する動作手順を示すフローチャートである。
以下、図１４を参照して、ナビゲーション装置２が行う誘導経路および予備経路の設定処理について説明する。
【０１２４】
まず、ナビゲーション装置２の経路情報取得部２４０が、サーバ装置１から経路情報として、誘導経路および予備経路に含まれる経由地点群に関する情報を取得する。そして、経路探索部２５０は、経路を生成するための対象となる経由地点群の一つを参照する（ステップＳ１４０１）。
【０１２５】
次に、経路探索部２５０は、参照した経由地点群に含まれる全ての経由地点を読み込む（ステップＳ１４０２）。
そして、経路探索部２５０は、読み込んだ経由地点の一つを選択して、経由地点群における最終経由地点か否か判断する（ステップＳ１４０３）。最終経由地点でなければ（ステップＳ１４０３→Ｎｏ）、経路探索部２５０は、選択した経由地点の次の経由地点までの補足経路を探索する（ステップＳ１４０４）。一方、経路探索部２５０が最終経由地点であると判断した場合には（ステップＳ１４０３→Ｙｅｓ）、最終経由地点から目的地までの補足経路を探索する（ステップＳ１４０５）。このステップＳ１４０３からＳ１４０５までの処理を行うことで、経由地点と次の経由地点との間の各補足経路が経路探索部２５０により探索され、最終経由地点と目的地までの補足経路も探索される。
【０１２６】
続いて、経路探索部２５０は、これらの探索した各補足経路を結合して候補経路を生成する（ステップＳ１４０６）。
【０１２７】
次に、経路探索部２５０は、参照した経由地点群が誘導経路用の経由地点群であるか否かを判断する（ステップＳ１４０７）。そして、誘導経路用の経由地点群であれば（ステップＳ１４０７→Ｙｅｓ）、誘導経路として、補助記憶部２１の誘導経路情報２１１に記憶する（ステップＳ１４０８）。一方、誘導経路用の経由地点群ではなく（ステップＳ１４０７→Ｎｏ）、予備経路用の経由地点群であれば、補助記憶部２１の予備経路情報２１２に予備経路として記憶する（ステップＳ１４０９）。
【０１２８】
次に、経路探索部２５０は、全ての経由地点群を処理したか否か判断する（ステップＳ１４１０）。まだ処理していない経由地点群があれば（ステップＳ１４１０→Ｎｏ）、ステップＳ１４０１に戻り次の経由地点群について処理を続ける。一方、全ての経由地点群を処理していれば（ステップＳ１４１０→Ｙｅｓ）、処理を終える。
【０１２９】
図１５は、図１４のフローチャートで示した経由地点群を用いた誘導経路および予備経路の設定処理について説明するための図である。
図１５に示すように、誘導経路Ｒ100の経由地点として、ノードＰ101が示されている。また、予備経路の経由地点として、予備経路Ｒ110を生成するための経由地点群、ノードＰ111，Ｐ112が示され、予備経路Ｒ120を生成するための経由地点群として、ノードＰ121，Ｐ122が示され、予備経路Ｒ130を生成するための経由地点群として、ノードＰ131，Ｐ132，Ｐ133が示され、各経由地点群がサーバ装置１により配信される。
【０１３０】
そして、例えば、経路探索部２５０は、各経由地点群のうち、予備経路Ｒ110を構成するノードＰ111，Ｐ112の経由地点群を参照し（ステップＳ１４０１）、経由地点群のノードＰ111，Ｐ112を読み込み（ステップＳ１４０２）、ノードＰ111とノードＰ112間の補足経路と探索し（ステップＳ１４０４）、最終経由地点であるノードＰ112から目的地までの補足経路を探索する（ステップＳ１４０５）。そして、各補足経路を結合して予備経路Ｒ110を予備経路情報２１２として補助記憶部２１に記憶する。
【０１３１】
このようにすることで、本実施形態に係る変形例によれば、サーバ装置１からナビゲーション装置２に提供される経路情報の配信量を低減させることができる。そして、誘導経路に従って経路を走行中に経路を逸脱した場合でも、現在地から目的地までの新たな経路をサーバ装置１に要求することなく、取得した経由地点群に基づく情報により生成した予備経路を用いて、目的地までの経路案内を継続できる。
なお、この変形例において、経由地点群は誘導経路および予備経路上のノード（交差点）に限らず、誘導経路周辺に存在する施設やランドマーク等の地点情報でも構わないものである。
【符号の説明】
【０１３２】
１ サーバ装置（経路探索サーバ）
２ ナビゲーション装置
３ 通信ネットワーク
４ 基地局
５ 外部情報センタ
６ ブロードバンドネットワーク
７ 経路探索システム
１０ 制御部
１１，２１ 補助記憶部
１２，２２ 通信部
１３，２３ メモリ部
１４，２４ 入出力部
２０ 経路案内制御部
２５ 表示部
２６ 衛星電波受信部
５１ 交通情報センタ
５２ 天気情報センタ
５３ 観光情報センタ
１１０ 外部情報取得部
１１１ マスタ地図データベース
１１２ 外部情報データベース
１２０ 経路要求処理部
１３０ 誘導経路探索部
１４０ 予備経路探索部
１５０ 経路情報送信部
２１０ 位置情報取得部（現在位置算出手段）
２１１ 誘導経路情報
２１２ 予備経路情報
２１３ 地図データベース
２２０ 探索条件設定部（出発地設定手段，目的地設定手段）
２３０ 経路要求送信部（送信手段）
２４０ 経路情報取得部（受信手段）
２５０ 経路探索部
２５１ 補足経路探索部
２６０ 経路案内部（経路選択手段）
【技術分野】
【０００１】
本発明は、ナビゲーション装置、経路探索サーバ、および経路探索システムに関するものである。
【背景技術】
【０００２】
放送や通信装置を介して外部の情報センタから最新情報を受信し、その最新情報を考慮して目的地までの経路を誘導するナビゲーション装置が普及しつつある。例えば、交通情報センタからＦＭ多重放送等で提供される渋滞や旅行時間等の最新の交通情報を受信し、その交通情報を考慮した目的地までの最短時間の経路を計算して経路を案内する機能は、ナビゲーション装置の基本機能として定着しつつある。そして、より速く目的地まで到着可能な経路で、より精度良く到着時刻を予測できるよう、車両の通過予定時刻の予測交通情報を情報センタから取得して目的地までの最適経路を計算し誘導するナビゲーション装置も利用されるようになった。また、情報センタで最新の交通情報を反映して計算した最適経路を取得し目的地までの経路を案内するようにしたシステムもある。
【０００３】
交通情報に限らず、外部サイトが有する膨大かつ最新情報を端末に取り込んでナビゲーションサービスを充実させようとする動きがある。例えば、自宅での旅行計画をサポートするポータルサイトでは、動的に変動する施設や道路の利用料金、施設利用状況やイベント情報等の最新情報を考慮した目的地までの経路情報、出発時間、休憩場所等の属性情報を提供している。ポータルサイトで計画した旅行情報をメディアないし通信を介してカーナビ装置に転送することで、目的地までの経路や誘導案内にも利用できるようにしたサービスも存在する。
【０００４】
例えば、カーナビゲーション装置（以下、カーナビ装置という）の要求に応じてセンタで経路探索を行いその結果をカーナビ装置に提供するナビゲーションシステムが開示されている（特許文献１参照）。カーナビ装置で経路探索を行わないことで装置を安価に構成することを目的としているが、センタが最新情報を有していれば、最新情報が反映された経路情報を得ることができる。しかしながら、カーナビ装置では、誘導中に車両が経路から逸脱することがあるため、経路を逸脱した時には再経路探索により車両位置から目的地までの新しい経路情報を提供する必要がある。特許文献１に記載された技術では、端末に経路探索機能を有していないため、経路を逸脱するとセンタから新たな経路情報を得る手続きを行う必要がある。そこで経路を逸脱した場合の対処法として、車両側からのリクエストを受信する度に目的地までの経路を再探索する方法が開示されている（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平１０−１９５８８公報
【特許文献２】特開平２００１−１４７１３２公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特許文献２に記載された技術は、センタに接続する度に目的地までの経路が更新され車両側に提供されるので、経路を逸脱しても新たな誘導経路を用いて目的地までの経路案内を継続することができる。さらに、走行中の通信状態が悪くセンタから経路情報が得られない場合に備え、車両側は受信した経路情報を蓄積し、通信不可を検出すると蓄積した経路情報を用いて経路案内をするようにしている。
【０００７】
しかしながら、誘導経路を走行中は、センタに通信接続するたびに車両位置から目的地までの再計算した誘導経路を車両側に提供するようにしているので、通信コストの増加という課題が残る。また、経路を逸脱した際の対処方法についても、センタから端末装置に車両位置からの新たな経路を配信し、その配信の失敗が継続すると、車両位置が蓄積した経路情報から離れてしまうため経路案内が継続できなくなる事態がしばしば生じることになると予想される。
【０００８】
このような背景に鑑みて本発明がなされたのであり、本発明は、経路逸脱時に新たな誘導経路をセンタから取得する際に生じる通信コストの増加や通信の不安定性による誘導案内のサービス劣化を防ぎ、経路探索サーバ（センタ）が備える最新情報を反映した誘導経路を提供する、ナビゲーション装置、経路探索サーバ、および経路探索システムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
前記課題を解決するために、本発明のナビゲーション装置、経路探索サーバ、および経路探索システムは、経路探索サーバが、出発地から目的地までの誘導経路を探索する誘導経路探索部と、予め経路逸脱を想定した予備経路を探索する予備経路探索部とを備え、誘導経路探索部が探索した誘導経路と、予備経路探索部が探索した予備経路とをナビゲーション装置に送信する。そして、ナビゲーション装置の経路案内部が誘導経路の経路逸脱を検出すると、経路探索部が予備経路の中から現在位置に最も近いノードで構成される予備経路を選択する。そして、経路探索部は、現在位置から当該ノードをつなぐ補足経路を探索し、予備経路と補足経路とを合成した経路を新たな誘導経路として経路案内を継続することを特徴とする。
【００１０】
すなわち、ユーザは、経路を逸脱した時、一時的な電波障害等により経路探索サーバとの通信接続ができず、新たな経路情報が得られないといった、通信の不安定性に悩まされることなく、経路探索サーバが備える最新情報が反映された経路情報を利用しつづけることができるようになり、経路誘導に関わる情報配信の信頼性を向上させることができる。
さらに、提供される予備経路は、目的地までの到達条件を満たす経路に限定し配信するので、経路探索サーバからナビゲーション装置に配信する情報量を削減することができる。
【発明の効果】
【００１１】
本発明によれば、経路逸脱時に新たな誘導経路を取得する際に生じる通信コストの増加や通信の不安定性による誘導案内のサービス劣化を防ぎ、経路探索サーバが備える最新情報を反映した誘導経路を提供するナビゲーション装置、経路探索サーバ、および経路探索システムを提供することができる。
【図面の簡単な説明】
【００１２】
【図１】本実施形態に係る経路探索システムの構成例を示す機能ブロック図である。
【図２】本実施形態に係る経路探索システムの全体の動作手順を示すフローチャートである。
【図３】本実施形態に係るサーバ装置の予備経路探索部が行う予備経路提供エリア設定処理の動作手順を示すフローチャートである。
【図４】本実施形態に係る予備経路提供エリアを示す図である。
【図５】本実施形態に係るサーバ装置の予備経路探索部が行う予備経路提供エリア設定処理の他の動作手順を示すフローチャートである。
【図６】本実施形態に係る予備経路提供エリア設定処理における分岐率について説明するため図である。
【図７】本実施形態に係る予備経路提供エリアの他の例を示す図である。
【図８】本実施形態に係るサーバ装置の予備経路探索部が行う到達コスト条件設定処理の動作手順を示すフローチャートである。
【図９】本実施形態に係る到達コスト条件設定処理を説明するための図である。
【図１０】本実施形態に係るサーバ装置の予備経路探索部が行う予備経路設定処理の動作手順を示すフローチャートである。
【図１１】本実施形態に係る予備経路設定処理を説明するための図である。
【図１２】本実施形態に係るナビゲーション装置の経路案内制御部が行う予備経路情報に基づく誘導経路設定処理の動作手順を示すフローチャートである。
【図１３】本実施形態に係るナビゲーション装置の予備経路情報に基づく誘導経路設定処理を説明するための図である。
【図１４】本実施形態に係るナビゲーション装置が、サーバ装置から経由地点群に関する情報を取得し、誘導経路と予備経路を探索する動作手順を示すフローチャートである。
【図１５】本実施形態に係る経路探索システムにおける経由地点群を用いた誘導経路および予備経路の設定処理について説明するための図である。
【発明を実施するための形態】
【００１３】
次に、本発明を実施するための形態（「実施形態」という）について、適宜図面を参照しながら詳細に説明する。
【００１４】
図１は、本実施形態に係る経路探索システム７の構成例を示す機能ブロック図である。
図１に示すように、本実施形態における経路探索システム７は、サーバ装置（経路探索サーバ）１とナビゲーション装置２とを備えて構成される。また、サーバ装置１とナビゲーション装置２とは、通信ネットワーク３に接続され基地局４を介して、無線通信手段により接続されている。さらに、サーバ装置１は、ブロードバンドネットワーク６を介して、外部情報センタ５に接続されている。
【００１５】
図１に示すように、サーバ装置１は、制御部１０と、補助記憶部１１と、通信部１２と、メモリ部１３と、入出力部１４とを含んで構成される。
【００１６】
制御部１０は、ナビゲーション装置２からの要求を受けて、後記する補助記憶部１１に記憶されたマスタ地図データベース１１１を用いて経路を探索する機能を有し、外部情報取得部１１０と、経路要求処理部１２０と、誘導経路探索部１３０と、予備経路探索部１４０と、経路情報送信部１５０とを含んで構成される。なお、この制御部１０の機能は、例えばサーバ装置１の補助記憶部１１に記憶されたプログラムをＣＰＵ（Central Processing Unit）がメモリ部１３に展開し実行することで実現される。
【００１７】
外部情報取得部１１０は、外部情報センタ５から交通情報や天候、施設情報等の様々な情報（音声や映像情報を含む）を取得し、補助記憶部１１内の外部情報データベース１１２に記憶する。
ここで、外部情報センタ５は、交通情報センタ５１、天気情報センタ５２、観光情報センタ５３等により構成される。この外部情報センタ５から、現況の交通情報、予測交通情報、事故や災害情報、通行規制情報、降水量等の天気情報、観光地の観光ルートや観光施設の営業時間等を含めた観光情報が、ブロードバンドネットワーク６を通じてサーバ装置１に提供される。
【００１８】
経路要求処理部１２０は、ナビゲーション装置２から送信される経路要求情報を受信して、その要求内容を解析し、解析した結果を誘導経路探索部１３０に伝える。このとき、ナビゲーション装置２から取得する経路要求情報とは、経路探索に必要な現在位置（あるいは出発点）、目的地、走行予定日時、探索条件等の情報であり、さらに誘導経路を逸脱したときに利用する予備経路の探索要求情報が含まれる。
【００１９】
探索条件は、有料道路を優先するか、距離ないし時間を優先するか、交通状況を考慮するか等が設定される。また、人気ルートやお勧めルート等、条件として曖昧性を含めたものも受け付けることが可能である。この場合は、経路要求処理部１２０において、曖昧な探索条件から具体的な条件に変換する変換処理を行う。
【００２０】
例えば、経路要求処理部１２０は、「人気ルート」であれば走行頻度の高い道路、「お勧めルート」であればユーザの注目度の高い地点を経由する道路、というように具体的に情報検索可能な表現に変換し、その表現文から検索キーを生成する。生成した検索キーにヒットする情報が外部情報データベース１１２に存在しない場合、あるいは最新情報を必要とする場合、その検索キーを用いて外部情報取得部１１０が必要な情報を外部情報センタ５から収集し、収集した情報を外部情報データベース１１２に記憶する。
交通情報や天候情報等の比較的に短い期間で変動する情報で、経路探索条件として頻繁に利用される情報については、外部情報取得部１１０は、定期的に外部情報センタ５から収集するようにして外部情報データベース１１１に記憶し、常に最新情報が保たれるようにする。
【００２１】
誘導経路探索部１３０は、経路要求処理部１２０で解析した要求を受け付け、経路探索に必要な情報をマスタ地図データベース１１１および前記最新情報が保たれている外部情報データベース１１２から参照し、出発地から目的地までの誘導経路を計算する。
経路探索のアルゴリズムとしては、例えば、出発地から目的地に向かって最小コストとなる経路を求めるダイクストラ法が用いられる。
【００２２】
予備経路探索部１４０は、経路要求処理部１２０が取得した経路要求情報に予備経路の探索要求情報が含まれる場合、誘導経路探索部１３０が探索した誘導経路に関わる予備経路を探索する。例えば、誘導経路の近傍ノード（交差点）を出発地とした目的地までの予備経路を探索する。
【００２３】
経路情報送信部１５０は、誘導経路探索部１３０が探索した誘導経路と予備経路探索部１４０が探索した予備経路とを含めた経路情報を生成し、通信部１２および通信ネットワーク３を介して、ナビゲーション装置２に送信する。
【００２４】
次に、補助記憶部１１は、ハードディスクやフラッシュメモリ等の記憶手段からなり、マスタ地図データベース１１１と、外部情報データベース１１２と、制御部１０を制御するプログラム（図示せず）とを含んで構成される。
【００２５】
マスタ地図データベース１１１は、経路案内に必要な最新の道路データがマスタ地図データとして記憶されている。
また、外部情報データベース１１２は、通信部１２を介して外部情報取得部１１０が、外部情報センタ５から交通情報、天気情報、観光情報等をブロードバンドネットワーク６を介して取得した情報を記憶する。
【００２６】
通信部１２は、ナビゲーション装置２から通信ネットワーク３を介して送信された経路要求情報を受信し、また、外部情報センタ５からブロードバンドネットワーク６を介して送信された情報を受信する。そして、通信部１２は、経路情報送信部１５０が生成した経路情報をナビゲーション装置２へ送信する。
【００２７】
メモリ部１３は、制御部１０の制御により、補助記憶部１１に記憶されたマスタ地図データベース１１１等から読み出された地図情報や、通信部１２が取得した情報を一時的に記憶しておく記憶手段であり、ＲＡＭ（Random Access Memory）やキャッシュメモリ等により構成される。
【００２８】
入出力部１４は、例えば、キーボード、あるいはタッチパネル等を含んで構成され、外部からサーバ装置１への指示を受け付ける。また、制御部１０の処理結果等を液晶モニタ等の表示手段に出力する。
【００２９】
次に、ナビゲーション装置２について説明する。ナビゲーション装置２は、サーバ装置１と通信ネットワーク３を介して接続され、サーバ装置１から経路情報と、後記する予備経路情報とを取得する。
【００３０】
このナビゲーション装置２は、経路案内制御部２０と、補助記憶部２１と、通信部２２と、メモリ部２３と、入出力部２４と、表示部２５と、衛星電波受信部２６とを含んで構成される。
【００３１】
経路案内制御部２０は、通信部２２を介してサーバ装置１から取得した経路情報に基づき、経路案内の処理を行い、経路案内中に誘導経路を逸脱した場合には、予めサーバ装置１から取得した予備経路に基づき、経路案内を行う。また、経路案内制御部２０は、位置情報取得部２１０と、探索条件設定部２２０と、経路要求送信部２３０と、経路情報取得部２４０と、経路探索部２５０と、経路案内部２６０とを含んで構成される。なお、この経路案内制御部２０の機能は、例えばナビゲーション装置２の補助記憶部２１に記憶されたプログラムをＣＰＵがメモリ部２３に展開し実行することで実現される。
【００３２】
位置情報取得部（現在位置算出手段）２１０は、衛星電波受信部２６が衛星から受信した情報を取得して、ナビゲーション装置２の現在位置（自車位置）を算出する。
【００３３】
探索条件設定部２２０は、経路案内の際に必要な出発地や目的地、距離あるいは時間を優先するか、有料道路を優先するか、交通状況を考慮するか等を、入出力部２４を介して設定する。また、探索条件設定部２２０の処理により、誘導経路を逸脱した際の予備経路を予めサーバ装置１から取得しておくか否かの情報が入出力部２４を介して設定される。なお、請求項に記載した出発地設定手段および目的地設定手段は、この探索条件設定部２２０に相当する。
【００３４】
経路要求送信部（送信手段）２３０は、位置情報取得部２１０が算出した現在位置、および探索条件設定部２２０により設定された、出発地、目的地、距離あるいは時間優先等の探索条件、そして、予備経路の探索をユーザが設定した場合には、予備経路の探索要求情報を含む、経路要求情報を生成し、通信部２２を介してサーバ装置１へ送信する。
【００３５】
経路情報取得部（受信手段）２４０は、サーバ装置１から送信された経路情報を、通信部２２を介して取得する。そして、経路情報取得部２４０は、経路情報に含まれる誘導経路に関する情報を、補助記憶部２１内に誘導経路情報２１１として記憶する。また、経路情報に含まれる予備経路に関する情報を、経路情報取得部２４０は、補助記憶部２１内に予備経路情報として記憶する。
【００３６】
経路探索部２５０は、ナビゲーション装置２がサーバ装置１から誘導経路情報２１１を取得していない場合に、補助記憶部２１内の地図データベース２１３と、入出力部２４を介して取得したユーザ入力情報と、位置情報取得部２１０から取得した現在位置の位置情報とに基づいて、目的地までの誘導経路を探索する。
また、経路探索部２５０は、補足経路探索部２５１を備えて構成される。補足経路探索部２５１は、経路案内中に誘導経路を逸脱した場合、現在地から予めサーバ装置１より取得した予備経路に到達するまでの補足経路、あるいは、現在地からもとの誘導経路に復帰するまでの補足経路の探索を行う。ここで、現在地を出発点として、サーバ装置１から得た経路（誘導経路あるいは予備経路）を構成するノードの中から車両の進行方向で現在地に最も近いノードを選択し、前記ノードに到達するまでの経路を補足経路とする。
【００３７】
経路案内部（経路選択手段）２６０は、補助記憶部２１に記憶された誘導経路情報２１１と、位置情報取得部２１０から取得した現在位置の位置情報とに基づいて、目的地までの経路案内を行う。また、経路案内中に誘導経路を逸脱した場合には、補足経路探索部２５１が探索した予備経路までの補足経路に基づき予備経路までの誘導案内を行い、その後補助記憶部２１に記憶された予備経路情報２１２に基づいて、目的地までの経路案内を行う。なお、請求項に記載した経路選択手段と、その経路選択手段を構成する逸脱判断手段および誘導経路再設定手段は、この経路案内部２６０に相当する。
また、ナビゲーション装置２がサーバ装置１から誘導経路情報２１１および予備経路情報２１２を取得していない場合には、経路探索部２５０が補助記憶部２１内の地図データベース２１３を用いて探索した経路に基づいて経路案内を行う。
【００３８】
次に、補助記憶部２１は、ハードディスクやフラッシュメモリ等の記憶装置からなり、誘導経路情報２１１と、予備経路情報２１２と、地図データベース２１３と、経路案内制御部２０を制御するプログラム（図示せず）とを含んで構成される。
【００３９】
誘導経路情報２１１は、サーバ装置１から取得した経路情報に含まれる誘導経路に関す情報を、経路情報取得部２４０の処理により、補助記憶部２１内に記憶した情報である。
予備経路情報２１２は、同様に、サーバ装置１から取得した経路情報に含まれる予備経路に関する情報を、経路情報取得部２４０の処理により、補助記憶部２１内に記憶した情報である。
【００４０】
地図データベース２１３は、誘導案内に必要な地図データを記憶する。
本実施形態において、地図データは、道路データと、目的地を施設名や電話番号等で絞り込んで検索するための目的地検索用データと、表示部２５に地図背景を描画するための背景描画用データと、交差点の右左折案内や走行レーンの案内等を行うための経路誘導用データとを含んで構成させる。
この道路データは、道路を画面表示したり、目的地までの推奨ルートを、例えばダイクストラ法を用いて計算するために、各道路のネットワークを道路リンクと呼ばれる小区間が接続した集合体で表現され、道路リンクの座標や、道路リンク間の接続情報、道路リンクの通過所要時間や距離等を示すコスト情報を、記憶するものである。また、この道路リンクを構成するノード（交差点）の位置情報（緯度・経度）等を含むノード情報が記憶されている。
【００４１】
通信部２２は、経路要求送信部２３０が生成した経路要求情報を、通信ネットワーク３を介してサーバ装置１へ送信する。また、通信部２２は、サーバ装置１から送信された経路情報を受信し、経路案内制御部２０内の経路情報取得部２４０に引き渡す。
【００４２】
メモリ部２３は、経路案内制御部２０の制御により、補助記憶部２１に記憶された誘導経路情報２１１や予備経路情報２１２等から読み出された情報や、通信部２２が取得した情報を一時的に記憶しておく記憶手段であり、ＲＡＭやキャッシュメモリ等により構成される。
【００４３】
入出力部２４は、例えば、リモコン、タッチパネル等を含んで構成され、外部からのナビゲーション装置２への指示を受け付ける。また、経路案内制御部２０の制御のもと、ナビゲーション装置２の各種処理に応じて、音声案内等を図示されていないスピーカを通じて出力する。
【００４４】
表示部２５は、液晶ディスプレイ等で構成されており、経路案内制御部２０の制御のもとに、ナビゲーション処理に応じて、道路状況あるいは誘導案内等を表示する。
【００４５】
衛星電波受信部２６は、ナビゲーション装置２の現在位置を算出するために必要となる衛星からの電波を受信する。衛星からの電波を受信することでその衛星の位置が求まるとともに、ナビゲーション装置２（衛星電波受信部２６）から衛星までの距離（擬似距離）が求まる。そして、４つ以上の衛星から電波を受信することで、ナビゲーション装置２の正確な現在位置が求まる。
【００４６】
なお、図１では、外部情報センタ５から得た最新のコンテンツを考慮した経路をサーバ装置１で探索しナビゲーション装置２に提供するようにしたが、従来の交通情報サービス同様、外部情報センタ５で得た最新コンテンツをナビゲーション装置２に提供することで最新コンテンツを反映した経路を探索する方法もある。しかし、サービス向上を目的にサーバ装置１で扱うコンテンツ量を増やし、コンテンツの更新サイクルを短くした場合、ナビゲーション装置２に提供すべきコンテンツデータが増加し、通信負荷（通信費用や通信時間）の問題が顕在化してくる。故に図１に示すようにサーバ装置１で経路探索を行い、ナビゲーション装置２に提供するデータを必要最小限に抑えることで、コンテンツを増やしても通信負荷を押さえることができる。
【００４７】
次に、図１を参照しつつ、図２に沿って、本実施形態に係る経路検索システム７の処理の流れについて説明する。
図２は、本実施形態に係る経路探索システム７の全体の動作手順を示すフローチャートである。
【００４８】
まず、ナビゲーション装置２は、入出力部２４を介して目的地や探索条件等が入力され、経路案内制御部２０内の探索条件設定部２２０において、探索条件が設定される（ステップＳ２０１）。
次に、探索条件設定部２２０は、ナビゲーション装置２が備える経路探索部２５０において補助記憶部２１内の地図データベース２１３を用いて誘導経路を探索するか、それとも、誘導経路の探索をサーバ装置１に要求するためサーバ装置１に接続するか、を判定する（ステップＳ２０２）。この判定は、探索条件設定部２２０が、入出力部２４を介して表示部２５に設定画面を表示し、ユーザ入力を促して経路探索の処理開始時あるいは予めユーザが設定できるようにする。
【００４９】
ステップＳ２０２において、探索条件設定部２２０が、サーバ装置１に接続の要求をしないと判定した場合は（ステップＳ２０２→Ｎｏ）、ナビゲーション装置２が備える経路探索部２５０において目的地までの誘導経路を探索する（ステップＳ２０４）。
一方、サーバ装置１に接続要求すると判定した場合は（ステップＳ２０２→Ｙｅｓ）、探索条件設定部２２０に設定された目的地、探索条件、現在位置等を含めた経路要求情報を経路要求送信部２３０がサーバ装置１に送信する（ステップＳ２０３）。
【００５０】
次に、サーバ装置１の制御部１０内の経路要求処理部１２０は、通信部１２を介してナビゲーション装置２から経路要求情報を受信する（ステップＳ１０１）。
そして、受信した経路要求情報に含まれる現在位置（ないし出発地）、目的地、探索条件等の情報を経路要求処理部１２０から受け取った誘導経路探索部１３０が、目的地までの誘導経路を探索する（ステップＳ１０２）。
【００５１】
また、経路要求処理部１２０は、経路要求情報に予備経路の探索要求が含まれているか否かを判断する（ステップＳ１０３）。
この予備経路の探索要求は、ナビゲーション装置２の探索条件設定部２２０が、入出力部２４を介して表示部２５に設定画面を表示し、ユーザ入力を促して経路探索の処理開始時あるいは予めユーザが設定できるようにする。
予備経路の探索要求が含まれていない場合は（ステップＳ１０３→Ｎｏ）、ステップＳ１０８へ進む。一方、予備経路の探索要求が含まれている場合は（ステップＳ１０３→Ｙｅｓ）、次のステップＳ１０４の予備経路提供エリア設定処理へ進む。
【００５２】
ステップＳ１０４において、予備経路探索部１４０は、誘導経路の近傍において予備経路を提供するエリアを設定する（後記する図３、図５参照）。
ここで、予備経路を設定するエリアを定めるのは、サーバ装置１に複数ユーザから経路要求が集中すると、一時的にサーバ負荷が増大し応答時間が長くなること、また、移動中の通信状況を考慮するとできるだけ速やかに経路情報を返信すべきことによる。そのためには、予備経路を探索するための計算量を必要最小限に留めて、探索処理の応答時間を所定時間内に維持する必要がある。そこで、計算量を抑えるために、探索エリアを必要最小限に狭めることが有効となる。予備経路を提供するエリアは、誘導経路沿いにその誘導経路から所定距離内のエリアを対象とする方法、その誘導経路を含むメッシュ領域を対象とする方法等考えられるが、ここではさらにエリアを絞り込む方法として、誘導経路のコストを用いた絞込みを行う。
【００５３】
ここで、誘導経路のコストには、誘導経路の所定地点間を移動する場合の距離、旅行時間、費用（燃料消費量、高速代金、その移動時間にかかる人件費等）、ＣＯ２排出量等を設定することができるが、本実施形態においては、誘導経路の所定地点間の距離を前提に説明する。つまり、２地点間の距離が短ければコストが低く、距離が長ければコストが高い経路となる。また、２点間において出発地点から到達地点までにかかるコストを到達コストとして以下説明する。
【００５４】
次に、予備経路探索部１４０は、到達コスト条件設定処理を行う（ステップＳ１０５）。予備経路探索部１４０が、この処理を行うことにより、予備経路提供エリアを設定した上で、さらにその提供エリア内において、基準となる所定の到達コスト以内という到達コスト条件を満たした範囲内で予備経路の設定ができる。つまり、予備経路提供エリア内であっても、遠回りで距離や時間等のコストが所定値以上かかる到達コストの経路は、予備経路として設定しないようにする。なお、到達コスト条件設定処理の詳細については、図８において詳細に説明する。
【００５５】
そして、予備経路探索部１４０は、ステップＳ１０４で設定された予備経路提供エリア内において、ステップＳ１０５で設定された到達コスト条件満たすノード（交差点）について、予備経路設定処理を行う（ステップＳ１０６）。なお、この予備経路設定処理については、図１０において詳細に説明する。
【００５６】
次に、予備経路探索部１４０は、予備経路提供エリア内の全てノードを処理したか否かを判断する（ステップＳ１０７）。全てのノードの処理を終えていない場合には（ステップＳ１０７→Ｎｏ）、ステップＳ１０６に戻り処理を続ける。一方、全てのノードの処理を終えている場合には（ステップＳ１０７→Ｙｅｓ）、次のステップＳ１０８へ進む。
【００５７】
ステップＳ１０８において、経路情報送信部１５０は、誘導経路探索部１３０が探索した誘導経路情報と、予備経路探索部１４０が設定した予備経路情報とを含む経路情報を、ナビゲーション装置２へ送信する（ステップＳ１０８）。
【００５８】
次に、ナビゲーション装置２の経路情報取得部２４０は、サーバ装置１から誘導経路情報と予備経路情報とを含んだ経路情報を、通信部２２を介して取得する（ステップＳ２０５）。
【００５９】
続いて、ステップＳ２０４あるいはＳ２０５において取得した誘導経路情報を用いて、経路案内部２６０は、位置情報取得部２１０から得た現在位置の位置情報と合わせて目的地までの経路案内を行う（ステップＳ２０６）。
【００６０】
次に、経路案内部２６０は、現在位置が目的地に到着したか否かを判断する（ステップＳ２０７）。目的地に到着していれば（ステップＳ２０７→Ｙｅｓ）、経路案内部２６０は処理を終える。一方、目的地に到着していなければ（ステップＳ２０７→Ｎｏ）、経路案内部２６０は、現在位置が誘導経路から逸脱しているか否かを判断する（ステップＳ２０８）。
【００６１】
現在位置が誘導経路を逸脱していなければ（ステップＳ２０８→Ｎｏ）、ステップＳ２０６へ戻り誘導経路の案内処理を続ける。一方、経路案内部２６０が、誘導経路を逸脱していると判断した場合は（ステップＳ２０８→Ｙｅｓ）、次のステップＳ２０９へ進む。
【００６２】
ステップＳ２０９において、経路案内部２６０は、補助記憶部２１の予備経路情報２１２に、誘導経路案内中の誘導経路に対応した予備経路情報が記憶されているか否かを判断する（ステップＳ２０９）。予備経路情報が記憶されていない場合には（ステップＳ２０９→Ｎｏ）、ステップＳ２０４へ戻り、経路探索部２５０が、補助記憶部２１内の地図データベース２１３を用いて、経路探索を行う。
一方、予備経路情報が記憶されている場合には、次のステップＳ２１０へ進み、経路案内部２６０は、予備経路情報に基づいて、現在位置から目的地までの新たな経路を誘導経路として設定する処理を行う（ステップＳ２１０）。なお、この予備経路情報に基づく誘導経路設定処理については、後記する図１２において詳細に説明する。
そして、経路案内部２６０は、ステップＳ２０６へ戻り、予備経路に基づいて設定された誘導経路の案内処理を続ける。
【００６３】
以上の手順は、ナビゲーション装置２からの経路要求に応じてサーバ装置１が誘導経路情報および予備経路情報を提供することを想定しているが、自動車等に搭載されたナビゲーション装置２とは異なる端末装置としてパーソナルコンピュータや携帯電話等を用いて自宅や出先から旅行計画を行う際に、サーバ装置１に目的地までの経路を要求するようにしてもよい。この場合、サーバ装置１に一時的に経路を記憶する記憶手段を設けておき、端末装置からサーバ装置１に予め計画した誘導経路を要求すると、サーバ装置1に既に記憶されている誘導経路を端末装置に送信するようにすることもできる。
【００６４】
なお、これまで本実施形態においては、現在位置を出発地として説明してきたが、ナビゲーション装置２が他に入力手段を備えるか、または入出力部２４からにより入力された位置を出発地としてもよい。
【００６５】
次に、図２のステップＳ１０４における予備経路提供エリア設定処理について説明する。
【００６６】
（予備経路提供エリア設定処理についての実施形態１）
図３は、本実施形態に係るサーバ装置１の予備経路探索部１４０が行う予備経路提供エリア設定処理の動作手順を示すフローチャートである。また、図４は、本実施形態に係る予備経路提供エリアを示す図である。
【００６７】
まず、予備経路探索部１４０は、図２のステップＳ１０２で探索した誘導経路を分割し（ステップＳ３０１）、補助記憶部１１内のマスタ地図データベース１１１から、誘導経路の各分割点のうちの一つを読み込む（ステップＳ３０２）。ここで、誘導経路を分割するための分割点Ｐiは経路を構成するノード（交差点）をとる。ただし、経路分割が可能であれば経路付近のノードを用いても、メッシュや行政区の境界点でも構わない。図４に示す例においては、分割点Ｐi（ｉ＝１〜ｎ−１）を、経路（符号４５０）上のノードＰ2,Ｐ3とする。
【００６８】
次に、予備経路探索部１４０は、分割経路のコストＴiを基準コストに設定し、分割経路の起点から同コストで移動可能なエリアＡiを設定する（ステップＳ３０３）。
図４に示す例においては、現在位置（符号４００）すなわちノードＰ1（誘導経路の出発点）から分割点ノードＰ2までが最初の分割経路となり、予備経路探索部１４０が、分割経路のノードＰ1からノードＰ2に向かうコストＴ1を基準コストとして設定する。そして、予備経路探索部１４０は、ノードＰ1から基準コストＴ1で移動可能なエリアＡ1を設定する。
【００６９】
次に、予備経路探索部１４０は、分割経路の終点から設定した基準コストＴiで移動可能なエリアＢiを設定する（ステップＳ３０４）。
図４に示す例においては、ノードＰ2からノードＰ1に向かって基準コストＴ1で移動可能なエリアＢ1を、予備経路探索部１４０が設定する。
【００７０】
続いて、予備経路探索部１４０は、エリアＡiとエリアＢiとが重なるエリアＣiを分割経路の提供エリアとする（ステップＳ３０５）。
図４に示す例においては、予備経路探索部１４０は、Ａ1とＢ1とが重なるエリアＣ1を分割経路の予備経路提供エリアとする。
【００７１】
そして、予備経路探索部１４０は、全ての分割経路の提供エリアを設定したか否かを判断する（ステップＳ３０６）。ここで、全ての分割経路の提供エリアを設定した場合には（ステップＳ３０６→Ｙｅｓ）、次のステップＳ３０７に進む。一方、設定していない分割経路の提供エリアがある場合には、ステップＳ３０２へ戻り処理を続ける。
【００７２】
続いて、予備経路探索部１４０は、ステップＳ３０７において、全てのエリアＣ1〜n-1を含むエリアを予備経路の提供エリアと設定する。
図４においては、ステップＳ３０２〜Ｓ３０５の処理を繰り返すことにより、分割経路Ｐ2〜Ｐ3の基準コストＴ2に基づいた予備経路提供エリアＣ2、分割経路Ｐ3〜Ｐ4の基準コストＴ3に基づいた予備経路提供エリアＣ3が設定され、目的地Ｐ4に到達するまでの全分割経路の提供エリアが設定される。そして、設定したエリアＣ1〜Ｃ3を包含するエリアを誘導経路Ｐ1〜Ｐ4の予備経路提供エリア（符号４０１）として設定する。ここで提供エリアとして若干のマージンを含めたより広いエリア（符号４０２）としてもよい。
このようにすることで、予備経路探索部１４０により、予備経路提供エリアが設定される。
【００７３】
（予備経路提供エリア設定処理についての実施形態２）
図５は、本実施形態に係るサーバ装置１の予備経路探索部１４０が行う予備経路提供エリア設定処理の他の動作手順を示すフローチャートである。
【００７４】
まず、予備経路探索部１４０は、図２のステップＳ１０２で探索した誘導経路を構成する経路の分岐点としてノード（交差点）Ｐi（ｉ＝１〜ｎ）の一つを、補助記憶部１１内のマスタ地図データベース１１１から読み込む（ステップＳ５０１）。
【００７５】
次に、予備経路探索部１４０は、読み込んだノード（交差点）についてのノード情報からそのノードの分岐数、分岐率を取得する（ステップＳ５０２）。
ここで、分岐数は、そのノードから分岐する道路リンク数をそのまま用いてもよいが、ここでは車両等がそのノードに進入する進入リンクを除いた道路リンク数とする。
また分岐率は、そのノードにおいて、複数のリンクに交通量が分岐して流出するほど大きな値を持つようにする指標である。
【００７６】
図６は、本実施形態に係る予備経路提供エリア設定処理における分岐率について説明するため図である。
図６に示すように、ある時間帯においてノードＰへの進入リンクとなる道路リンクＬinの交通量を１０００、脱出リンクとなる道路リンクＬ1、Ｌ2、Ｌ3の交通量を各々２００，３００，５００とする。各脱出リンクに流出する交通量の割合は、Ｌ1において２００÷１０００＝０．２、Ｌ2において３００÷１０００＝０．３、Ｌ3において５００÷１０００＝０．５となる。最大値０．５で各方向における割合値を正規化すると、Ｌ1方向が０．４、Ｌ2方向が０．６、Ｌ3方向が１となる。Ｌ3方向を除きこれらの平均値を求めると（０．４＋０．６）÷２＝０．５となり、本実施形態においては、この値を、当該時間帯における進入リンクＬinの時のノードＰの分岐率とする。この分岐率を例えば一日２４時間を単位時間で分割した全ての単位時間帯および進入リンク毎に算出する。進入リンク毎に算出した分岐率の平均値を計算し、進入リンクに関係なく各ノードにおいて一つの分岐率を持つようにしてもよい。
【００７７】
なお、本実施形態において、分岐率は、分岐数と共にノード情報としてマスタ地図データベース１１１に予め記憶されているものとする。ただし、外部情報センタ５から分岐率を取得してマスタ地図データベース１１１に記憶するようにしてもよい。また、サーバ装置１の構成要素として分岐率を計算する分岐率算出手段を新たに設け、外部情報センタ５から取得した交通情報（交通量を含む）に基づいて分岐率を計算するようにしてもよい。さらに、ナビゲーション装置２からの経路要求情報と共に走行データを受信し、その走行データから分岐率を算出する方法も考えられる。
【００７８】
図５に戻り、予備経路探索部１４０は、ステップＳ５０３において、ノードに関する提供エリアＣiを、以下の式（１）に示すように、ノードに接続される分岐数や分岐率に基づいて設定する。
【００７９】
提供エリアＣi＝ 基準半径ｒ×分岐数×分岐率 （分岐率＞０） … 式（１）
【００８０】
ここで、基準半径ｒは、ノードを中心としたエリアの半径である。例えば、ナビゲーション装置２の走行速度を仮に６０ｋｍ/ｈとし、経路逸脱から２分以内に移動可能な範囲に存在するノードを予備経路として保障するようにして６０ｋｍ/ｈ÷６０×２＝２ｋｍを基準半径ｒとする。また、分岐率は０以上となるような最小値を予め設定しておく。
【００８１】
次に、予備経路探索部１４０は、全てのノードの提供エリアを設定したか否かを判断する（ステップＳ５０４）。そして、全てのノードの提供エリアの設定がされていなければ（ステップＳ５０４→Ｎｏ）、ステップＳ５０１へ戻り処理を続ける。一方、全てのノードの提供エリアの設定が終わっていれば（ステップＳ５０４→Ｙｅｓ）、次のステップＳ５０５へ進む。
【００８２】
ステップＳ５０５において、予備経路探索部１４０は、設定した全ての提供エリア Ｃ1〜nを予備経路の提供エリアとする。
具体的には、予備経路探索部１４０が、全分岐点に関わる提供エリアＣiを設定し、その全提供エリアＣi、あるいは全提供エリアＣiを包含するエリアを予備経路の提供エリアとする。
【００８３】
図７は、本実施形態に係る予備経路提供エリアの他の例を示す図である。
図７に示すように、ノードＰ2は分岐数が多く分岐率も高いことから、提供エリアＣ2（符号７０１）が広く設定される。これより様々な方向に車両が分岐し経路を逸脱するリスクも高い箇所で、そのリスクに応じて予備経路を提供することができる。ノードＰ3は、例えば、分岐数は多いが分岐率が小さいため、ノードＰ3での経路逸脱のリスクは低いとし、提供エリアＣ3（符号７０２）はＣ2（符号７０１）に比べて小さくなる。
【００８４】
図７に示すノードＰiの設定において、誘導経路を構成する全てのノードについて提供エリアを設定するのではなく、誘導経路を構成するノードの中で分岐数や分岐率の高いノードを対象に提供エリアを選択するようにしてもよい。さらに、現在位置付近は移動距離が短いため大きく迷うリスクが低く、目的地周辺も目的地に近づくにつれて、移動距離が短くなるので大きく迷うことがないことから、中間地点のノードよりも提供エリアを狭くとるようにしてもよい。
【００８５】
（到達コスト条件設定処理）
次に、図２のステップＳ１０５における到達コスト条件設定処理について説明する。
図８は、本実施形態に係るサーバ装置１の予備経路探索部１４０が行う到達コスト条件設定処理の動作手順を示すフローチャートである。また、図９は本実施形態に係る到達コスト条件設定処理を説明するための図である。この到達コスト条件設定処理においては、到達コスト条件を適用するエリア（条件設定対象エリア）を設定し、到達コスト条件を設定する。
【００８６】
まず、予備経路探索部１４０は、図２のステップＳ１０２で、すでに読み込んである現在位置と目的地に加えて、図３のステップＳ３０１で分割した分割経路の起点Ｐiおよび終点Ｐi+1のノード情報（ノード座標等）を、補助記憶部１１のマスタ地図データベース１１１から読み込む（ステップＳ８０１）。
【００８７】
次に、起点Ｐiから目的地までの到達コストＴＰ(i)を基準として、予備経路探索部１４０は、目的地から当該到達コストＴＰ(i)において到達可能なエリアＥＰ(i)を設定する（ステップＳ８０２）。図９に示す例では、起点Ｐi＝Ｐ1のとき、ＴＰ(i)＝ＴＰ１＝Ｔ1＋Ｔ2＋Ｔ3を基準として、当該到達コストＴＰ１以下で到達可能なエリアＥＰ(i)（符号９０１）を設定する。ここで、例えば、目的地への到達コストが所要時間やＣＯ２排出量等であった場合には、これらを距離に換算した値からエリアＥＰ(1)（符号９０１）を設定する。
【００８８】
続いて、予備経路探索部１４０は、分割経路の終点Ｐi+1から目的地までの到達コストＴＰ(i＋1)を基準として、目的地から当該到達コストＴＰ(i＋1)以下で到達可能なエリア ＥＰ(i＋1)を設定する（ステップＳ８０３）。図９に示す例では、起点Ｐi+1＝Ｐ2のとき、ＴＰ(i＋1)＝ＴＰ２＝Ｔ2＋Ｔ3を基準として、当該到達コストＴＰ２以下で到達可能なエリアＥＰ(2)（符号９０２）を設定する。
【００８９】
そして、予備経路探索部１４０は、予備経路提供エリア（符号４０１）内において、ステップＳ８０２で設定したエリアＥＰ(i)と一致し、ステップＳ８０３で設定したエリアＥＰ(i＋1)との境界までを条件設定対象エリアとする（ステップＳ８０４）。図９に示す例では、予備経路提供エリア（符号４０１）内において、エリアＥＰ１以内であり、エリアＥＰ２と境界するエリア（符号９１１）が、条件設定対象エリアとなる。
【００９０】
次に、予備経路探索部１４０は、ステップＳ８０４で設定した条件設定対象エリア内に存在するノードから目的地に向かう経路の到達コスト条件を、以下の式（２）をもとに設定する（ステップＳ８０５）。
【００９１】
到達コスト条件 ≦ ＴＰ(i)＋ α・Ｔｃ … 式（２）
【００９２】
式（２）において、Ｔｃは予め設定したマージンコスト、αは目的地に近づくに従ってマージンコストＴｃが小さくなるようにした重みパラメータで、例えば式（３）により設定する。
【００９３】
α＝（Ｔ−∂Ｔ）／Ｔ … 式（３）
【００９４】
Ｔは当該誘導経路の出発点から目的地までの所要コスト、∂Ｔは出発点から当該対象エリア内の所定地点までの移動コストである。
図９に示す例においては、エリアＥＰ１内における到達コスト条件ＴＰ１が、
ＴＰ１ ≦ Ｔ1＋Ｔ2＋Ｔ3＋αＴｃ
と設定される。
【００９５】
そして、予備経路探索部１４０は、分割経路の終点が目的地であるか否かを判断する（ステップＳ８０６）。分割経路の終点が目的地でなければ（ステップＳ８０６→Ｎｏ）、ステップＳ８０１に戻り処理を続ける。
図９に示す例においては、エリアＥＰ２内における到達コスト条件ＴＰ２が、
ＴＰ２ ≦ Ｔ2＋Ｔ3＋αＴｃ
と設定され、エリアＥＰ３内における到達コスト条件ＴＰ３が、
ＴＰ３ ≦ Ｔ3＋αＴｃ
と設定される。
【００９６】
一方、分割経路の終点が目的地であれば（ステップＳ８０６→Ｙｅｓ）、予備経路探索部１４０は、到達コスト条件設定処理を終える。
【００９７】
（予備経路設定処理）
次に、図２のステップＳ１０６における予備経路設定処理について説明する。
図１０は、本実施形態に係るサーバ装置１の予備経路探索部１４０が行う予備経路設定処理の動作手順を示すフローチャートである。
【００９８】
図１０において、まず、サーバ装置１の予備経路探索部１４０は、図２のステップＳ１０４において設定した予備経路提供エリアを参照する（ステップＳ１００１）。
そして、予備経路探索部１４０は、補助記憶部１１のマスタ地図データベース１１１を参照して、当該予備経路提供エリア内に存在する全てのノードを検索する（ステップＳ１００２）。
ここで、検索したノードのノード情報（ノード座標等）やノードに接続される道路の種別や道路幅等の道路情報により、幹線道路に接続されるノード（交差点）のみを対象とすることで検索ノード数を絞ることも可能である。
【００９９】
次に、予備経路探索部１４０は、検索したノードのうちの一つを選択する（ステップＳ１００３）。そして、選択したノードが到達コスト条件を設定したどの条件設定対象エリアに存在するかを判断し、図８のステップＳ８０５で設定した到達コスト条件を設定する（ステップ１００４）。
【０１００】
そして、予備経路探索部１４０は、当該ノードから目的地までの経路を探索する（ステップＳ１００５）。そして、その探索した経路が、ステップＳ１００４で設定した到達コスト条件を満たすか否かを判断する（ステップＳ１００６）。当該経路の目的値までの到達コストが所定値より大きく、到達コスト条件を満たさない場合には（ステップＳ１００６→Ｎｏ）、ステップＳ１００８へ進む。一方、当該経路の目的地までの到達コストが所定値以下であり、到達コスト条件を満たす場合には（ステップＳ１００６→Ｙｅｓ）、予備経路探索部１４０は、当該経路を予備経路として設定する（ステップＳ１００７）。
【０１０１】
続いて、予備経路探索部１４０は、予備経路提供エリア内にある全てのノードを処理したか否かを判断する（ステップＳ１００８）。まだ、処理していないノードがある場合には（ステップＳ１００８→Ｎｏ）、ステップＳ１００３に戻り処理を続ける。一方、全てノードの処理を終えた場合には（ステップＳ１００８→Ｙｅｓ）、予備経路設定処理を終了する。
【０１０２】
次に、図１０に示した予備経路設定処理を図１１を参照して具体的に説明する。
図１１は本実施形態に係る予備経路設定処理を説明するための図である。
【０１０３】
図１１に示すように、図１０のステップＳ１００２において、予備経路探索部１４０により、予備経路を探索するための候補ノードとして、予備経路提供エリア（符号４０１）内に存在するノードＰ20，Ｐ21，Ｐ30，Ｐ31，Ｐ32，Ｐ33，Ｐ40が検索されたとする。
【０１０４】
次に、これらの検索されたノードのうちの一つ例えばＰ20を、予備経路探索部１４０が選択する（ステップＳ１００３）。そして、予備経路探索部１４０は、ノードＰ20が条件設定対象エリア（符号９１１）内に位置することから、図８のステップＳ８０５で設定したエリアＥＰ１の到達コスト条件を設定する（ステップＳ１００４）。
ＴＰ１ ≦ Ｔ1＋Ｔ2＋Ｔ3＋αＴｃ … 式（４）
【０１０５】
続いて、予備経路探索部１４０は、ノードＰ20から目的地ノードＰ4までの経路を検索し（ステップＳ１００５）、当該経路の到達コストが、数式（４）の条件を満たすか否かを判断する（ステップＳ１００６）。そして、式（４）の条件を満たす場合に（ステップＳ１００６→Ｙｅｓ）、予備経路探索部１４０は、ステップＳ１００５で検索したノードＰ20から目的地であるノードＰ4までの経路を、予備経路として設定する（ステップＳ１００７）。
この一連の処理を、予備経路探索部１４０は、ステップＳ１００２で検索した全てのノードについて実行し、予備経路として設定する処理を行う。
このようにすることで、予備経路探索部１４０は、所定の到達コスト以下の予備経路だけを抽出し設定することができる。
【０１０６】
（ナビゲーション装置の予備経路情報に基づく誘導経路設定処理）
次に、図２のステップＳ２１０におけるナビゲーション装置２の予備経路情報に基づく誘導経路設定処理について説明する。
図１２は、本実施形態に係るナビゲーション装置２の経路案内制御部２０が行う予備経路情報に基づく誘導経路設定処理の動作手順を示すフローチャートである。
【０１０７】
図２のステップＳ２０８において、ナビゲーション装置２の経路案内部２６０が、誘導経路を逸脱したと判断し（ステップＳ２０８→Ｙｅｓ）、かつステップ２０８において、サーバ装置１より当該誘導経路に関する予備経路情報が補助記憶部２１に記憶されていた場合（ステップＳ２０９→Ｙｅｓ）、補足経路探索部２５１は、次のように予備経路情報に基づく誘導経路設定処理を行う。
【０１０８】
まず、補足経路探索部２５１は、補助記憶部２１の予備経路情報２１２に記憶された予備経路情報を参照し、現在位置に最も近いノードを構成ノード（始終点および中間ノード）とする予備経路を選択する（ステップＳ１２０１）。このとき現在位置からの距離に加えてナビゲーション装置２の進行方向を考慮し、進行方向にあるノードを優先し予備経路を選択する。
【０１０９】
次に、補足経路探索部２５１は、選択した予備経路を構成する、現在位置に最も近い構成ノードを仮目的地として、現在位置から仮目的地までの経路を探索する（ステップＳ１２０２）。探索した経路は現在位置と予備経路とをつなぐための補足経路として用いる。
【０１１０】
続いて、補足経路探索部２５１は、経路逸脱してからしばらく走行し続けると、現在位置が距離的にも時間的にも予備経路から遠く離れてしまうことが考えられるため、現在地から仮目的地までの到達コストが予め設定した所定値を超えるか否か判断する（ステップＳ１２０３）。到達コストが所定値以下の場合は（ステップＳ１２０３→Ｎｏ）、補足経路探索部２５１は、補足経路と予備経路とを合成した経路を、現在位置から目的地までの新たな誘導経路として設定する（ステップＳ１２０４）。
【０１１１】
このようにすることで、ナビゲーション装置２は、経路を逸脱しても、予め取得した予備経路を用いて、サーバ装置１との通信を行わず、新たな経路を設定し目的地まで経路案内をすることができる。予備経路はサーバ装置１が提供した経路であるため、経路を逸脱してもサーバ装置１に再度経路要求することなく、サーバ装置１が備える最新情報が反映された経路を利用して経路案内を継続することができる。
【０１１２】
一方、ステップＳ１２０３において、補足経路の到達コストが所定値を超えている場合は（ステップＳ１２０３→Ｙｅｓ）、経路案内部２６０は、表示部２５や音声案内を用いて、サーバ装置１から得た経路による誘導が継続できないことをユーザに通知する（ステップＳ１２０５）。
【０１１３】
次に、経路案内部２６０は、探索条件設定部２２０を介して、サーバ装置１に再接続し新たな経路を要求するか否かを判断する（ステップＳ１２０６）。新たな経路を要求する場合は（ステップＳ１２０６→Ｙｅｓ）、経路要求送信部２３０が、サーバ装置１に新たな経路要求情報を送信する（ステップＳ１２０７）。
【０１１４】
そして、経路要求送信部２３０は、ナビゲーション装置２が移動中、トンネルやビル等の構造物による遮蔽により通信状態が不安定な場合もあるので、通信エラーが発生しているか否かを監視する（ステップＳ１２０８）。通信エラーが発生していない場合には（ステップＳ１２０８→Ｎｏ）、図２のステップＳ２０５に戻り、サーバ装置１から経路情報を取得して処理を進める。
一方、通信エラーが発生した場合には（ステップＳ１２０８→Ｙｅｓ）、経路要求送信部２３０は、何回リトライを行ったかを記憶しておき、リトライ数が所定値を超えたか否かを判断する（ステップＳ１２０９）。このリトライ数が所定値を超えていない場合には（ステップＳ１２０９→Ｎｏ）、経路要求送信部２３０は、ステップＳ１２０７へ戻り処理を続ける。一方、リトライ数が所定値を超えた場合には（ステップＳ１２０９→Ｙｅｓ）、サーバ装置１との通信接続をあきらめ、経路探索部２５０が、ナビゲーション装置２の補助記憶部２１に記憶された地図データベース２１３を用いて、現在位置から目的地までの誘導経路の探索を行う（ステップＳ１２１０）。
【０１１５】
ステップＳ１２１０において、ナビゲーション装置２が備える到達コストを用いて経路探索を行った結果、先にサーバ装置１が提供した誘導経路と異なる経路が探索されることもあるが、予備経路が無効かつ通信不安定となった場合でも、目的地までの経路誘導を継続することを優先し、ナビゲーション装置２の経路探索を利用する。
【０１１６】
次に、この図１２に示したナビゲーション装置２の予備経路情報に基づく誘導経路設定処理について具体的に説明する。
図１３は、本実施形態に係るナビゲーション装置２の予備経路情報に基づく誘導経路設定処理を説明するための図である。図１３に示す例は、ナビゲーション装置２が誘導経路（符号４５０）を逸脱して現在位置（符号４００）に位置する場合に、補足経路探索部２５１が、予備経路を用いて新たな誘導経路を提供することを示している。
【０１１７】
まず、補足経路探索部２５１は、現在位置（符号４００）に最も近いノードＰ20を構成ノードとし、構成ノードＰ20を始点とする予備経路（符号１３００）を選択する（ステップＳ１２０１）。予備経路（符号１３００）はノードＰ20を始点とした目的地Ｐ4までの経路である。
次に、補足経路探索部２５１は、現在位置（符号４００）から構成ノードＰ20をつなぐ補足経路を探索する（ステップＳ１２０２）。ただし、現在位置（符号４００）が予備経路（符号１３００）の中間ノードであるＰ32に近い場合は、Ｐ32が構成ノードとして設定される場合もある。また、予備経路を用いた新たな誘導経路に切り替えることを行わず、元の経路に戻る経路を利用することも可能である。その場合は、元の誘導経路上で現在位置（符号４００）に最も近い、あるいは現在位置（符号４００）から最小コストで到達可能なノード（図ではＰ21）を仮目的地として補足経路を探索する。補足経路の探索は、現在位置近傍に存在するノードが仮目的地として設定されるため、移動距離が短く、ナビゲーション装置２が備える地図データベース２１３を用いた到達コストを用いて補足経路を探索しても、サーバ装置１で算出した経路との到達コストの差は大きくならない。
【０１１８】
このようにすることで、ナビゲーション装置２は、経路逸脱をした場合に、再度サーバ装置１に経路要求することなく、予めサーバ装置１から取得した最新の地図データに基づく予備経路情報を利用して、経路案内を続けることができる。
【０１１９】
以上のように、本実施形態に係るナビゲーション装置、経路探索サーバ（サーバ装置）、および経路探索システムによれば、サーバ装置１から提供される誘導経路を用いて目的地までの経路を誘導し、誘導経路に従って経路を走行中に経路逸脱した場合でも、現在地から目的地までの新たな経路をサーバ装置１に要求することなく、既に取得した予備経路を用いて新たな誘導経路を生成することができる。そのため、誘導経路取得に伴う通信コストが軽減し、さらには不安定な通信状態の影響を受けることなく、目的地までの経路案内を継続することができる。
【０１２０】
すなわち、ユーザは、経路を逸脱した時、一時的な電波障害等によりサーバ装置との通信接続ができず、新たな経路情報が得られないといった、通信の不安定性に悩まされることがなく、サーバ装置が備える最新情報が反映された経路情報を利用し続けることができる。それにより、経路誘導に関わる情報配信の信頼性を向上させることができる。
さらに、提供される予備経路は、目的地までの到達コスト条件を満たす経路に限定し配信されるので、サーバ装置からナビゲーション装置に配信する情報量を削減することができる。
【０１２１】
また、サーバ装置１は、外部情報センタ５からの情報を用いて、交通情報に限らず施設の利用状況やイベント情報等の最新情報を反映した誘導経路、さらに複数車両の走行データに基づいて走行頻度の高い人気経路や、ドライバから提供されたお勧めの経路や施設といった、ナビゲーション装置２が備える探索条件（距離や時間、有料道路等）よりも豊富な条件を取り入れた誘導経路を探索できる。従って、より利用者の要求に近い経路が提供されるようになり、ナビゲーション装置２の利用者に対しても利便性を向上させることができる。
【０１２２】
（誘導経路および予備経路の設定処理についての変形例）
次に、図１の経路探索システム７における誘導経路および予備経路の設定処理の変形例について説明する。図２に示した経路検索システム７の処理においては、サーバ装置１の誘導経路探索部１３０がマスタ地図データベース１１１を用いて誘導経路の探索を行い、予備経路探索部１４０がその誘導経路に関する予備経路を探索し、誘導経路情報と予備経路情報とを経路情報としてナビゲーション装置２へ送信する構成とした。
ここでは、サーバ装置１からナビゲーション装置２に提供される経路情報の配信量を低減させるために、サーバ装置１の経路情報送信部１５０が、誘導経路および予備経路を構成するノード情報から複数の代表ノード（例えば、幹線道路が交わる交差点）を選択して経由地点群とし、その経由地点（座標と経由する順番を含む）群を経路情報としてナビゲーション装置２へ配信する処理を行い、ナビゲーション装置２側で、経路探索処理を行う実施形態について説明する。
【０１２３】
図１４は、ナビゲーション装置２が、サーバ装置１から経由地点群に関する情報を取得し、誘導経路と予備経路を探索する動作手順を示すフローチャートである。
以下、図１４を参照して、ナビゲーション装置２が行う誘導経路および予備経路の設定処理について説明する。
【０１２４】
まず、ナビゲーション装置２の経路情報取得部２４０が、サーバ装置１から経路情報として、誘導経路および予備経路に含まれる経由地点群に関する情報を取得する。そして、経路探索部２５０は、経路を生成するための対象となる経由地点群の一つを参照する（ステップＳ１４０１）。
【０１２５】
次に、経路探索部２５０は、参照した経由地点群に含まれる全ての経由地点を読み込む（ステップＳ１４０２）。
そして、経路探索部２５０は、読み込んだ経由地点の一つを選択して、経由地点群における最終経由地点か否か判断する（ステップＳ１４０３）。最終経由地点でなければ（ステップＳ１４０３→Ｎｏ）、経路探索部２５０は、選択した経由地点の次の経由地点までの補足経路を探索する（ステップＳ１４０４）。一方、経路探索部２５０が最終経由地点であると判断した場合には（ステップＳ１４０３→Ｙｅｓ）、最終経由地点から目的地までの補足経路を探索する（ステップＳ１４０５）。このステップＳ１４０３からＳ１４０５までの処理を行うことで、経由地点と次の経由地点との間の各補足経路が経路探索部２５０により探索され、最終経由地点と目的地までの補足経路も探索される。
【０１２６】
続いて、経路探索部２５０は、これらの探索した各補足経路を結合して候補経路を生成する（ステップＳ１４０６）。
【０１２７】
次に、経路探索部２５０は、参照した経由地点群が誘導経路用の経由地点群であるか否かを判断する（ステップＳ１４０７）。そして、誘導経路用の経由地点群であれば（ステップＳ１４０７→Ｙｅｓ）、誘導経路として、補助記憶部２１の誘導経路情報２１１に記憶する（ステップＳ１４０８）。一方、誘導経路用の経由地点群ではなく（ステップＳ１４０７→Ｎｏ）、予備経路用の経由地点群であれば、補助記憶部２１の予備経路情報２１２に予備経路として記憶する（ステップＳ１４０９）。
【０１２８】
次に、経路探索部２５０は、全ての経由地点群を処理したか否か判断する（ステップＳ１４１０）。まだ処理していない経由地点群があれば（ステップＳ１４１０→Ｎｏ）、ステップＳ１４０１に戻り次の経由地点群について処理を続ける。一方、全ての経由地点群を処理していれば（ステップＳ１４１０→Ｙｅｓ）、処理を終える。
【０１２９】
図１５は、図１４のフローチャートで示した経由地点群を用いた誘導経路および予備経路の設定処理について説明するための図である。
図１５に示すように、誘導経路Ｒ100の経由地点として、ノードＰ101が示されている。また、予備経路の経由地点として、予備経路Ｒ110を生成するための経由地点群、ノードＰ111，Ｐ112が示され、予備経路Ｒ120を生成するための経由地点群として、ノードＰ121，Ｐ122が示され、予備経路Ｒ130を生成するための経由地点群として、ノードＰ131，Ｐ132，Ｐ133が示され、各経由地点群がサーバ装置１により配信される。
【０１３０】
そして、例えば、経路探索部２５０は、各経由地点群のうち、予備経路Ｒ110を構成するノードＰ111，Ｐ112の経由地点群を参照し（ステップＳ１４０１）、経由地点群のノードＰ111，Ｐ112を読み込み（ステップＳ１４０２）、ノードＰ111とノードＰ112間の補足経路と探索し（ステップＳ１４０４）、最終経由地点であるノードＰ112から目的地までの補足経路を探索する（ステップＳ１４０５）。そして、各補足経路を結合して予備経路Ｒ110を予備経路情報２１２として補助記憶部２１に記憶する。
【０１３１】
このようにすることで、本実施形態に係る変形例によれば、サーバ装置１からナビゲーション装置２に提供される経路情報の配信量を低減させることができる。そして、誘導経路に従って経路を走行中に経路を逸脱した場合でも、現在地から目的地までの新たな経路をサーバ装置１に要求することなく、取得した経由地点群に基づく情報により生成した予備経路を用いて、目的地までの経路案内を継続できる。
なお、この変形例において、経由地点群は誘導経路および予備経路上のノード（交差点）に限らず、誘導経路周辺に存在する施設やランドマーク等の地点情報でも構わないものである。
【符号の説明】
【０１３２】
１ サーバ装置（経路探索サーバ）
２ ナビゲーション装置
３ 通信ネットワーク
４ 基地局
５ 外部情報センタ
６ ブロードバンドネットワーク
７ 経路探索システム
１０ 制御部
１１，２１ 補助記憶部
１２，２２ 通信部
１３，２３ メモリ部
１４，２４ 入出力部
２０ 経路案内制御部
２５ 表示部
２６ 衛星電波受信部
５１ 交通情報センタ
５２ 天気情報センタ
５３ 観光情報センタ
１１０ 外部情報取得部
１１１ マスタ地図データベース
１１２ 外部情報データベース
１２０ 経路要求処理部
１３０ 誘導経路探索部
１４０ 予備経路探索部
１５０ 経路情報送信部
２１０ 位置情報取得部（現在位置算出手段）
２１１ 誘導経路情報
２１２ 予備経路情報
２１３ 地図データベース
２２０ 探索条件設定部（出発地設定手段，目的地設定手段）
２３０ 経路要求送信部（送信手段）
２４０ 経路情報取得部（受信手段）
２５０ 経路探索部
２５１ 補足経路探索部
２６０ 経路案内部（経路選択手段）
【特許請求の範囲】
【請求項１】
通信ネットワークを介してサーバに接続されるナビゲーション装置において、
現在位置を算出する現在位置算出手段と、
出発地を設定する出発地設定手段と、
目的地を設定する目的地設定手段と、
前記出発地設定手段で設定された出発地と、前記目的地設定手段で設定された目的地と、を前記サーバに送信する送信手段と、
前記送信手段で送信された出発地と、目的地と、に応じた誘導経路と、前記誘導経路とは異なる出発地を有する予備経路と、を受信する受信手段と、
前記受信手段で受信した誘導経路と、予備経路と、のうち、前記現在位置算出手段で算出された現在位置から一番近い誘導経路または予備経路を設定すべき経路として選択する経路選択手段と、
から構成されることを特徴としたナビゲーション装置。
【請求項２】
前記経路選択手段は、
前記受信手段で受信した前記誘導経路上から前記現在位置算出手段で算出された現在位置が逸脱しているかどうかを判断する逸脱判断手段と、
前記逸脱判断手段で現在位置が誘導経路上から逸脱していると判断された場合に、前記受信手段で受信した予備経路を誘導経路とする誘導経路再設定手段と、
から構成されることを特徴とした請求項１に記載のナビゲーション装置。
【請求項３】
通信ネットワークを介してナビゲーション装置に接続される経路探索システムに用いられる経路探索サーバであって、
経路探索に必要な道路データを格納するマスタ地図データベースが記憶される記憶部と、
前記マスタ地図データベースを参照して、出発地から目的地までの誘導経路を探索する誘導経路探索部と、
前記誘導経路探索部が探索した前記誘導経路の近傍に存在するノードから目的地までの予備経路を探索する予備経路探索部と、
を備えることを特徴とする経路探索サーバ。
【請求項４】
前記予備経路探索部は、
前記誘導経路探索部が探索した前記誘導経路を分割し、前記分割した分割点間の経路における到達コストを基準とし、前記基準とした到達コストで前記分割点から到達可能なエリアを設定し、前記設定したエリア内に存在するノードを前記マスタ地図データベースから検索し、前記検索されたノードから目的地までの経路を、前記マスタ地図データベースを用いて探索し、前記探索された経路を前記予備経路とすること
を特徴とする請求項３に記載の経路探索サーバ。
【請求項５】
前記予備経路探索部は、
前記誘導経路探索部が探索した前記誘導経路を分割し、前記分割した分割点から目的地までの到達コストに基づいて所定値を設定し、前記設定した所定値より少ない到達コストで目的地に到達可能な経路を前記予備経路とすること
を特徴とする請求項４に記載の経路探索サーバ。
【請求項６】
前記予備経路探索部は、
前記誘導経路探索部が探索した前記誘導経路を構成する各ノードに関するノード情報を、前記マスタ地図データベースから取得し、前記ノード情報に含まれる分岐数および分岐する各リンクの交通量に関する指標である分岐率に基づいて、前記予備経路を提供するエリアを決定し、前記決定したエリア内に存在するノードを前記マスタ地図データベースから検索し、前記検索されたノードから目的地までの経路を、前記マスタ地図データベースを用いて探索し、前記探索された経路を前記予備経路とすること
を特徴とする請求項５に記載の経路探索サーバ。
【請求項７】
ナビゲーション装置が経路案内に必要とする経路情報を、通信ネットワークを介して接続する経路探索サーバが経路探索することにより取得して前記経路案内を行う経路探索システムであって、
前記経路探索サーバは、
前記ナビゲーション装置との間で、前記経路探索に関する情報の送受信を行う通信部と、
経路探索に必要な道路データを格納するマスタ地図データベースが記憶される記憶部と、
前記マスタ地図データベースを参照して、出発地から目的地までの誘導経路を探索する誘導経路探索部と、
前記誘導経路探索部が探索した前記誘導経路の近傍に存在するノードから目的地までの予備経路を探索する予備経路探索部と、
前記誘導経路探索部が探索した誘導経路情報および前記予備経路探索部が探索した予備経路情報を含む経路情報を、前記通信部を介してナビゲーション装置に送信する経路情報送信部と、を備え、
前記ナビゲーション装置は、
衛星からの測位用の電波を受信する衛星電波受信部と、
前記衛星電波受信部が受信した電波を用いて現在位置を算出する位置情報取得部と、
前記経路探索サーバとの間で、前記経路探索に関する情報の送受信を行う通信部と、
前記経路探索サーバから、前記通信部を介して前記経路情報を取得する経路情報取得部と、
前記経路情報取得部が取得した前記経路情報に含まれる前記誘導経路情報および前記予備経路情報、並びに経路案内に必要な地図データが格納される地図データベースが記憶される記憶部と、
前記記憶部に記憶された前記誘導経路情報を用いて、前記誘導経路の経路案内を行う経路案内部と、
前記経路案内部が、前記位置情報取得部が算出した現在位置を取得することにより、前記誘導経路を逸脱したと判断した場合に、前記記憶部に記憶された前記予備経路情報を用いて、現在位置に最も近い前記予備経路を新たな誘導経路として設定する経路探索部と、
を備えることを特徴とする経路探索システム。
【請求項８】
前記経路探索サーバの前記誘導経路探索部は、
前記探索した誘導経路を構成するノードから選択した複数のノードを誘導経路の経由地点群として設定し、
前記予備経路探索部は、
前記探索した予備経路を構成するノードから選択した複数のノードを予備経路の経由地点群として設定し、
前記経路情報送信部は、前記設定された誘導経路の経由地点群と前記予備経路の経由地点群とを前記経路情報として前記ナビゲーション装置に送信し、
前記ナビゲーション装置の前記経路探索部は、
前記誘導経路の経由地点群に含まれる前記複数のノードを取得し、前記複数のノード間の経路を、前記地図データベースを用いて探索し、前記探索された経路を結合して前記誘導経路を生成し、
前記予備経路の経由地点群に含まれる前記複数のノードを取得し、前記複数のノード間の経路を、前記地図データベースを用いて探索し、前記探索された経路を結合して前記予備経路を生成すること
を特徴とする請求項７に記載の経路探索システム。
【請求項１】
通信ネットワークを介してサーバに接続されるナビゲーション装置において、
現在位置を算出する現在位置算出手段と、
出発地を設定する出発地設定手段と、
目的地を設定する目的地設定手段と、
前記出発地設定手段で設定された出発地と、前記目的地設定手段で設定された目的地と、を前記サーバに送信する送信手段と、
前記送信手段で送信された出発地と、目的地と、に応じた誘導経路と、前記誘導経路とは異なる出発地を有する予備経路と、を受信する受信手段と、
前記受信手段で受信した誘導経路と、予備経路と、のうち、前記現在位置算出手段で算出された現在位置から一番近い誘導経路または予備経路を設定すべき経路として選択する経路選択手段と、
から構成されることを特徴としたナビゲーション装置。
【請求項２】
前記経路選択手段は、
前記受信手段で受信した前記誘導経路上から前記現在位置算出手段で算出された現在位置が逸脱しているかどうかを判断する逸脱判断手段と、
前記逸脱判断手段で現在位置が誘導経路上から逸脱していると判断された場合に、前記受信手段で受信した予備経路を誘導経路とする誘導経路再設定手段と、
から構成されることを特徴とした請求項１に記載のナビゲーション装置。
【請求項３】
通信ネットワークを介してナビゲーション装置に接続される経路探索システムに用いられる経路探索サーバであって、
経路探索に必要な道路データを格納するマスタ地図データベースが記憶される記憶部と、
前記マスタ地図データベースを参照して、出発地から目的地までの誘導経路を探索する誘導経路探索部と、
前記誘導経路探索部が探索した前記誘導経路の近傍に存在するノードから目的地までの予備経路を探索する予備経路探索部と、
を備えることを特徴とする経路探索サーバ。
【請求項４】
前記予備経路探索部は、
前記誘導経路探索部が探索した前記誘導経路を分割し、前記分割した分割点間の経路における到達コストを基準とし、前記基準とした到達コストで前記分割点から到達可能なエリアを設定し、前記設定したエリア内に存在するノードを前記マスタ地図データベースから検索し、前記検索されたノードから目的地までの経路を、前記マスタ地図データベースを用いて探索し、前記探索された経路を前記予備経路とすること
を特徴とする請求項３に記載の経路探索サーバ。
【請求項５】
前記予備経路探索部は、
前記誘導経路探索部が探索した前記誘導経路を分割し、前記分割した分割点から目的地までの到達コストに基づいて所定値を設定し、前記設定した所定値より少ない到達コストで目的地に到達可能な経路を前記予備経路とすること
を特徴とする請求項４に記載の経路探索サーバ。
【請求項６】
前記予備経路探索部は、
前記誘導経路探索部が探索した前記誘導経路を構成する各ノードに関するノード情報を、前記マスタ地図データベースから取得し、前記ノード情報に含まれる分岐数および分岐する各リンクの交通量に関する指標である分岐率に基づいて、前記予備経路を提供するエリアを決定し、前記決定したエリア内に存在するノードを前記マスタ地図データベースから検索し、前記検索されたノードから目的地までの経路を、前記マスタ地図データベースを用いて探索し、前記探索された経路を前記予備経路とすること
を特徴とする請求項５に記載の経路探索サーバ。
【請求項７】
ナビゲーション装置が経路案内に必要とする経路情報を、通信ネットワークを介して接続する経路探索サーバが経路探索することにより取得して前記経路案内を行う経路探索システムであって、
前記経路探索サーバは、
前記ナビゲーション装置との間で、前記経路探索に関する情報の送受信を行う通信部と、
経路探索に必要な道路データを格納するマスタ地図データベースが記憶される記憶部と、
前記マスタ地図データベースを参照して、出発地から目的地までの誘導経路を探索する誘導経路探索部と、
前記誘導経路探索部が探索した前記誘導経路の近傍に存在するノードから目的地までの予備経路を探索する予備経路探索部と、
前記誘導経路探索部が探索した誘導経路情報および前記予備経路探索部が探索した予備経路情報を含む経路情報を、前記通信部を介してナビゲーション装置に送信する経路情報送信部と、を備え、
前記ナビゲーション装置は、
衛星からの測位用の電波を受信する衛星電波受信部と、
前記衛星電波受信部が受信した電波を用いて現在位置を算出する位置情報取得部と、
前記経路探索サーバとの間で、前記経路探索に関する情報の送受信を行う通信部と、
前記経路探索サーバから、前記通信部を介して前記経路情報を取得する経路情報取得部と、
前記経路情報取得部が取得した前記経路情報に含まれる前記誘導経路情報および前記予備経路情報、並びに経路案内に必要な地図データが格納される地図データベースが記憶される記憶部と、
前記記憶部に記憶された前記誘導経路情報を用いて、前記誘導経路の経路案内を行う経路案内部と、
前記経路案内部が、前記位置情報取得部が算出した現在位置を取得することにより、前記誘導経路を逸脱したと判断した場合に、前記記憶部に記憶された前記予備経路情報を用いて、現在位置に最も近い前記予備経路を新たな誘導経路として設定する経路探索部と、
を備えることを特徴とする経路探索システム。
【請求項８】
前記経路探索サーバの前記誘導経路探索部は、
前記探索した誘導経路を構成するノードから選択した複数のノードを誘導経路の経由地点群として設定し、
前記予備経路探索部は、
前記探索した予備経路を構成するノードから選択した複数のノードを予備経路の経由地点群として設定し、
前記経路情報送信部は、前記設定された誘導経路の経由地点群と前記予備経路の経由地点群とを前記経路情報として前記ナビゲーション装置に送信し、
前記ナビゲーション装置の前記経路探索部は、
前記誘導経路の経由地点群に含まれる前記複数のノードを取得し、前記複数のノード間の経路を、前記地図データベースを用いて探索し、前記探索された経路を結合して前記誘導経路を生成し、
前記予備経路の経由地点群に含まれる前記複数のノードを取得し、前記複数のノード間の経路を、前記地図データベースを用いて探索し、前記探索された経路を結合して前記予備経路を生成すること
を特徴とする請求項７に記載の経路探索システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１１−７７４６（Ｐ２０１１−７７４６Ａ）
【公開日】平成２３年１月１３日（２０１１．１．１３）
【国際特許分類】
【出願番号】特願２００９−１５３９４１（Ｐ２００９−１５３９４１）
【出願日】平成２１年６月２９日（２００９．６．２９）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
【公開日】平成２３年１月１３日（２０１１．１．１３）
【国際特許分類】
【出願日】平成２１年６月２９日（２００９．６．２９）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
[ Back to top ]