経路案内サーバ装置、ナビゲーション装置、経路案内システムおよび経路案内方法
【課題】サーバ装置から送信される位置座標ベースの経路を、ナビゲーション装置の地図データのリンク番号またはノード番号の経路として誤りなく再現する。
【解決手段】サーバ装置１は、ナビゲーション装置２によって指定された始点から終点までの経路を探索し、その探索した経路に含まれるノードの全部または一部を経由ノードとして選出し、その選出した経由ノードのそれぞれについて、そのそれぞれの経由ノードから所定の距離以上離れた前記経路上の地点を、経由ノードの補足地点としてそれぞれ設定し、その経由ノードそれぞれの座標情報と補足地点の座標情報とを含んだ情報を経路情報として、ナビゲーション装置２へ送信する。ナビゲーション装置２は、サーバ装置１から送信された経由ノードの座標情報と補足地点の座標情報とに基づき、経由ノードおよび経由ノードに接続する道路リンクを、地図データベース２１３の識別番号によって同定する。
【解決手段】サーバ装置１は、ナビゲーション装置２によって指定された始点から終点までの経路を探索し、その探索した経路に含まれるノードの全部または一部を経由ノードとして選出し、その選出した経由ノードのそれぞれについて、そのそれぞれの経由ノードから所定の距離以上離れた前記経路上の地点を、経由ノードの補足地点としてそれぞれ設定し、その経由ノードそれぞれの座標情報と補足地点の座標情報とを含んだ情報を経路情報として、ナビゲーション装置２へ送信する。ナビゲーション装置２は、サーバ装置１から送信された経由ノードの座標情報と補足地点の座標情報とに基づき、経由ノードおよび経由ノードに接続する道路リンクを、地図データベース２１３の識別番号によって同定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、車両の経路案内に好適な経路案内サーバ装置、ナビゲーション装置、経路案内システムおよび経路案内方法に関する。
【背景技術】
【０００２】
近年、道路の混雑状況をはじめ様々な情報センタから送信される最新の情報を、放送や通信装置を介して受信し、その受信した最新情報を考慮した目的地までの適切な経路を車両のドライバに提供するカーナビゲーション装置（以下、ナビゲーション装置と記載）の普及が目覚しい。
【０００３】
例えば、交通情報センタからＦＭ多重放送などで提供される渋滞や旅行時間などの最新の交通情報を受信し、その交通情報を考慮した目的地までの最短時間の経路を計算して目的地までの経路を表示装置に表示する機能は、ナビゲーション装置の基本機能として定着しているといってよい。そして、今では、より速く目的地まで到着可能な経路で、より精度よく到着時刻を予測できるように当該車両の通過予定時刻の予測交通情報を情報センタから取得して、目的地までの最適経路計算に利用するナビゲーション装置も現れ、また、情報センタで最新の交通情報を反映して計算した最適経路を取得し、目的地までの経路を案内するようにしたナビゲーション装置も商品化されている。
【０００４】
さらには、交通情報に限らず、外部の様々なサイト（情報センタ）が有する膨大かつ最新の情報を端末に取り込んでナビゲーションサービスを充実させようとする動きがある。例えば、自宅での旅行計画をサポートするポータルサイトでは、動的に変動する施設や道路の利用料金、施設利用状況、イベント情報などの最新情報を考慮した目的地までの経路情報、出発時間、休憩場所などの情報を提供している。そして、そのようなポータルサイトで計画した旅行情報を通信や可搬の記憶メディアを介してナビゲーション装置に転送し、その情報をナビゲーション装置における目的地までの経路の誘導案内にも利用できるようにしたサービスも存在する。
【０００５】
ところで、目的地までの経路情報を表現する方法には、（ａ）地図データで用いられている道路リンクのリンク番号や、道路リンクの接続点であるノード（一般的には交差点）のノード番号を用いて、経路に含まれる複数のリンク番号またはノード番号の連なりとして表す方法、（ｂ）経路を点列で表し、その各点の緯度・経度などの位置座標の連なりとして表す方法、の２つの方法がある。
【０００６】
情報センタから与えられる経路情報をナビゲーション装置で正しく再現するには、前記（ａ）の方法が望ましい。しかしながら、ナビゲーション装置のメーカが異なり、地図データの形式が異なる場合、あるいは、地図データの形式が同じでも地図バージョンが異なる場合には、同じ道路であっても、同じ道路リンク番号が付されているとは限らない。従って、（ａ）の方法では、情報センタが経路情報をナビゲーション装置に提供する場合、その相互間に道路リンク番号の互換性がないことが大きな問題となる。
【０００７】
それに対し、前記（ｂ）の方法では、経路情報が経路を表す点列の各点の緯度・経度の座標情報によって表されるので、地図データの形式や道路リンク番号の互換性の問題は生じない。しかしながら、この方法では、情報センタとナビゲーション装置との間で地図データが異なり、さらに、例えば、当該経路に接近して並走したり、分岐したりする道路が存在するような場合には、両者の地図データに表された道路位置の緯度・経度の座標情報の誤差のために、情報センタが指定する座標位置をナビゲーション装置の地図データの道路位置に正しく対応させることができないことがある。すなわち、前記（ｂ）の方法には、情報センタが送信する経路情報を、ナビゲーション装置が必ずしも正しく再現することができないという問題がある。
【０００８】
さらに、前記（ｂ）の方法の場合、経路情報は、緯度・経度の座標情報で表された多数の点列データによって表されるので、その情報量が大きくなるという問題がある。情報センタからナビゲーション装置へ送信する経路情報の情報量が大きくなると、その分、通信路の通信負荷が増大するとともに、通信費も増大する。
【０００９】
そこで、こうした通信の情報量を削減する方法として、経路の形状点の座標情報を間引いたり、直線や曲線などで道路形状を近似したりすることが、しばしば、行われており、特許文献１には、その一例が開示されている。
【００１０】
特許文献１によれば、情報センタは、送信しようとしている経路情報に含まれるノードのノード情報のうち、間欠的に選出したノードのノード情報（ノードの座標情報＋属性情報など）を送信する。ナビゲーション装置は、その間欠的に選出されたノードのノード情報（座標情報）に基づき、マップマッチングによりナビゲーション装置の地図データ上で、前記間欠的に選出されたノードのノード番号を特定する。そして、ノード番号が特定されたノード、つまり、前記選出されたノードの相互間をつなぐ経路に含まれるノード、つまり、間引かれたノードのノード番号を経路探索により求める。こうして、ナビゲーション装置は、情報センタが指定した経路を再現する。
【００１１】
また、特許文献１によれば、単なるノード位置座標のマップマッチングでは、誤差の発生を免れ得ないと判断し、情報センタから送信されるノード情報には、ノードの座標情報だけでなく、ノードの属性情報や、そのノードの進入リンク、脱出リンクの属性情報（形状情報など）が含められ、属性情報のマッチングも行われる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００２−２２８４６８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、とくに都市部の道路など、複数の道路が交差するノード周辺には、複数のノードが隣接して存在することも多く、また、それらのノードに付随する属性情報が同じであったり、類似していたりすることも多い。従って、特許文献１に開示されているようなノードの座標情報や属性情報だけでのマッチング処理では、ノードのマップマッチングを誤り、情報センタから送信された経路情報を正しい経路に再現できない事態が生じる恐れが残っている。
【００１４】
そこで、本発明の目的は、情報センタ（経路案内サーバ装置）の地図データとナビゲーション装置の地図データとが異なる場合であっても、情報センタから送信される位置座標ベースで表された経路を、ナビゲーション装置が自身の地図データに基づくリンク番号またはノード番号ベースの経路で誤りなく再現することを可能とする経路案内サーバ装置、ナビゲーション装置、経路案内システムおよび経路案内方法を提供することにある。
【課題を解決するための手段】
【００１５】
本発明に係る経路案内システムにおいては、経路案内サーバ装置は、ナビゲーション装置から送信される始点および終点の情報を含んだ経路探索要求情報に基づき、その始点から終点までの経路を探索し、その探索した経路に含まれるノードのうち、全部または一部のノードを経由ノードとして選出し、その選出した経由ノードそれぞれに対し、その経由ノードから所定の距離以上離れた前記経路上に補足地点を設定し、前記経由ノードの座標情報と前記補足地点の座標情報とを含んだ情報を経路情報としてナビゲーション装置へ送信する。そして、ナビゲーション装置は、受信した経由ノードの座標情報と補足地点の座標情報とに基づき、その経由ノードおよび経由ノードに接続する道路リンクを、自身が有する地図データの識別番号によって同定する。
【００１６】
すなわち、本発明では、ナビゲーション装置は、経由ノードの座標情報だけでなく、その経由ノードを特定しやすくするための補足地点の座標情報も得ることができる。従って、ナビゲーション装置は、経路案内サーバ装置から送信された経路情報に含まれる経由ノードを自身が有する地図データにおけるノードに同定することが容易になる。
【発明の効果】
【００１７】
本発明によれば、情報センタ（経路案内サーバ装置）の地図データとナビゲーション装置の地図データとが異なる場合であっても、情報センタから送信される位置座標ベースで表された経路情報を、ナビゲーション装置が自身の地図データに基づくリンク番号またはノード番号ベースの経路で誤りなく再現することが可能になる。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施形態に係る経路案内システムを含んだシステム全体の構成の例を示した図。
【図２】本発明の実施形態に係る経路案内システムの全体の動作手順の例を示したフローチャート。
【図３】本発明の実施形態に係るサーバ装置における経由地情報の生成処理の処理フローの例を示した図。
【図４】本発明の実施形態に係る経由地の選出および補足地点の設定を説明するための図。
【図５】本発明の実施形態に係るサーバ装置における補足地点の設定処理の処理フローの例を示した図。
【図６】本発明の実施形態に係るサーバ装置からナビゲーション装置に提供される経由地情報のデータフォーマットの例を示した図。
【図７】本発明の実施形態に係るナビゲーション装置における経由地の同定処理および経路探索処理（図２のステップＳ２０８およびＳ２０９）の処理フローの例を示した図。
【図８】本発明の実施形態に係るナビゲーション装置における経路合成処理（図２のステップＳ２１０）の処理フローの例を示した図。
【図９】本発明の実施形態に係るナビゲーション装置における経路合成を説明するための図。
【図１０】本発明の実施形態に係るサーバ装置における経由地情報生成処理の処理フローの第１の変形例を示した図。
【図１１】本発明の実施形態に係るサーバ装置における経由地情報生成処理の処理フローの第１の変形例に係る経由地情報の設定処理において経由地の選出方法を説明するための図。
【図１２】本発明の実施形態に係るサーバ装置における経由地情報の生成処理の処理フローの第３の変形例を示した図。
【図１３】本発明の実施形態に係るサーバ装置における経由地情報の生成処理の処理フローの第３の変形例に係る経由地情報の設定処理において経由地の選出方法を説明するための図。
【図１４】本実施形態に係る経由地情報の生成処理における交通量の分岐分散率について説明するための図。
【発明を実施するための形態】
【００１９】
以下、図面を参照して本発明の実施形態について詳しく説明する。
【００２０】
＜全体構成＞
図１は、本発明の実施形態に係る経路案内システムを含んだシステム全体の構成の例を示した図である。
【００２１】
図１に示すように、経路案内システム７は、道路を走行する車両に搭載されるナビゲーション装置２と、そのナビゲーション装置２に誘導経路情報などを提供する情報センタの経路案内サーバとして機能するサーバ装置１と、を含んで構成される。このとき、サーバ装置１とナビゲーション装置２とは、通信ネットワーク３および基地局４を介して接続され、また、サーバ装置１は、ブロードバンドネットワーク６を介して、外部情報センタ５にも接続されている。
【００２２】
なお、ここでいうブロードバンドネットワーク６は、インターネットなど公衆通信用のネットワークであり、また、通信ネットワーク３は、携帯電話の通信業者などが所有する専用のネットワークである。なお、基地局４とナビゲーション装置２との間は、無線通信区間であり、その区間の通信には携帯電話の電波を用いるものとするが、IEEE802.11シリーズ規格の無線ＬＡＮ（Local Area Network）や、モバイルＷｉＭＡＸなどの電波を用いてもよい。あるいは、ＦＭ多重放送などの放送手段を用いてもよい。
【００２３】
また、外部情報センタ５は、具体的には、交通情報センタ５１、施設情報センタ５２、観光情報センタ５３などを含んで構成される。そして、外部情報センタ５の各情報センタ５１，５２，５３からは、それぞれ、交通事故や道路工事などを考慮した最新の交通渋滞情報、通行料金や施設営業日時などの施設情報、観光地の観光ルートや観光施設の営業時間などを含めた観光情報などの情報が、ブロードバンドネットワーク６を通じてサーバ装置１に提供される。
【００２４】
＜サーバ装置の構成＞
図１に示すように、サーバ装置１は、制御部１０と、補助記憶部１１と、通信部１２と、メモリ部１３と、入出力部１４と、を含んで構成される。
【００２５】
制御部１０は、ナビゲーション装置２からの要求を受けて、後記する補助記憶部１１に記憶された地図データベース１１１を用いて経路を探索する機能を有し、外部情報取得部１１０と、経路要求処理部１２０と、誘導経路探索部１３０と、経由地情報生成部１４０と、経路情報送信部１５０とを含んで構成される。なお、制御部１０の機能は、例えば、図示しないＣＰＵ（Central Processing Unit）が、サーバ装置１の補助記憶部１１に記憶されたプログラムをメモリ部１３に展開し、実行することによって実現される。
【００２６】
外部情報取得部１１０は、外部情報センタ５から交通情報や天候、施設情報などの様々な情報（音声や映像情報を含む）を取得し、補助記憶部１１内の外部情報データベース１１２に記憶する。
【００２７】
経路要求処理部１２０は、ナビゲーション装置２から送信される経路要求情報を受信して、その要求内容を解析し、解析した結果を誘導経路探索部１３０に伝える。このとき、ナビゲーション装置２から取得する経路要求情報とは、経路探索に必要な出発地（あるいは現在位置）、目的地、走行予定日時、探索条件、端末識別番号、利用している地図の位置表現形式やバージョンなどを含む情報である。
【００２８】
そして、その探索条件には、有料道路を優先するか、距離または時間を優先するか、交通状況を考慮するか、などの条件が設定される。また、探索条件で、通行料割引を最大限に利用する経路、通行料割引や燃料消費量、移動時間などを考慮した経済的な経路、ＣＯ２排出量などの環境を考慮する経路などを指定することもできる。
【００２９】
さらには、人気ルートやお勧めルートなど、曖昧な条件を探索条件に含んでもよい。その場合は、経路要求処理部１２０は、曖昧な探索条件を具体的な探索条件に変換する。例えば、経路要求処理部１２０は、探索条件が「人気ルート」であれば、「走行頻度の高い道路からなる経路」に、また、「お勧めルート」であれば、「ユーザの注目度の高い地点を経由する経路」に変換する、というように情報検索可能な表現の条件に変換し、その表現文から検索キーを生成する。そして、生成した検索キーに一致する情報が外部情報データベース１１２に存在しない場合、あるいは、最新情報を必要とする場合、その検索キーを用いて外部情報取得部１１０が必要な情報を外部情報センタ５から収集し、収集した情報を外部情報データベース１１２に記憶する。
【００３０】
なお、外部情報取得部１１０は、交通情報や施設情報などの比較的に短い期間で変動する情報で、経路探索条件として頻繁に利用される情報については、所定の時間ごとに定期的に外部情報センタ５から収集するようにして外部情報データベース１１２に記憶し、常に最新情報が保たれるようにする。
【００３１】
誘導経路探索部１３０は、経路要求処理部１２０で解析した要求を受け付け、経路探索に必要な情報を地図データベース１１１および外部情報データベース１１２から取得し、出発地から目的地までの誘導経路を計算する。このとき、経路探索のアルゴリズムとしては、例えば、出発地から目的地に向かって最小コストとなる経路を求めるダイクストラ法が用いられるのが一般的であるが、他の数学的手法を用いて計算してもよい。
【００３２】
経由地情報生成部１４０は、誘導経路探索部１３０が計算した誘導経路に含まれる交差点のノードから後記する手順に従って経由ノードを選出するとともに、前記誘導経路に含まれ、かつ、前記選出した各経由ノードを始点とする各リンク上に、そのそれぞれの経由ノードを特定し易くするための補足地点を設定する。そして、経由地情報生成部１４０は、前記経由ノードとその補足地点の情報に基づき、経由ノード情報（経由ノードの座標情報や、ノード種別、交差点名称などの属性情報）、補足地点情報（補足地点の座標情報、分岐方向など）、前記補足地点が含まれるリンクの属性情報（リンク種別、道路種別、規制情報など）を含んだ経由地情報を生成する。
【００３３】
経路情報送信部１５０は、経由地情報生成部１４０によって生成された経由地情報に基づき、所定の配信用データ形式に従った経路情報を生成し、通信部１２および通信ネットワーク３を介して、ナビゲーション装置２に送信する。
【００３４】
次に、補助記憶部１１は、ハードディスク装置やフラッシュメモリなどの記憶装置によって構成され、地図データベース１１１、外部情報データベース１１２などの情報を記憶する。
【００３５】
ここで、地図データベース１１１は、経路案内に必要な最新の道路データを含む地図データを記憶する。その場合、地図データ更新に伴う複数バージョンの地図データを、同時に記憶していてもよい。また、外部情報データベース１１２は、外部情報取得部１１０が、通信部１２およびブロードバンドネットワーク６を介して、外部情報センタ５から取得した交通情報、施設情報、観光情報などの情報を記憶する。
【００３６】
通信部１２は、ナビゲーション装置２から通信ネットワーク３を介して送信された経路要求情報を受信するとともに、外部情報センタ５からブロードバンドネットワーク６を介して送信された情報を受信する。また、通信部１２は、経路情報送信部１５０が生成した経路情報をナビゲーション装置２へ送信する。
【００３７】
メモリ部１３は、ＲＡＭ（Random Access Memory）などによって構成され、制御部１０の図示しないＣＰＵが実行するためのプログラムを記憶するとともに、そのプログラムに従って、ＣＰＵが地図データベース１１１などから読み出した地図情報や、通信部１２により取得した情報などを一時的に記憶する。
【００３８】
入出力部１４は、キーボード、マウス、タッチパネルなどの入力装置や、液晶ディスプレイなどの表示装置を含んで構成され、入力装置を介して外部からのサーバ装置１への指示入力を受け付けるとともに、制御部１０の処理によって得られる各種処理結果を表示装置などに出力する。
【００３９】
＜ナビゲーション装置の構成＞
図１に示すように、ナビゲーション装置２は、経路案内制御部２０と、補助記憶部２１と、通信部２２と、メモリ部２３と、入出力部２４と、表示部２５と、衛星電波受信部２６とを含んで構成される。
【００４０】
経路案内制御部２０は、通信部２２を介してサーバ装置１から送信された経由地情報を含んだ経路情報に基づき、その経由地情報によって指定される経由地を経由する経路を、誘導経路として再現し、経路案内を行う。そして、その経路案内制御部２０は、位置情報取得部２１０と、経路情報取得部２２０と、探索条件設定部２３０と、経路要求送信部２４０と、経由地同定部２５０と、経路探索部２６０、経路合成部２７０、経路案内部２８０と、を含んで構成される。なお、経路案内制御部２０の機能は、例えば、図示しないＣＰＵが、ナビゲーション装置２の補助記憶部２１に記憶されたプログラムをメモリ部２３に展開し、実行することによって実現される。
【００４１】
位置情報取得部２１０は、衛星電波受信部２６が複数のＧＰＳ（Global Positioning System）衛星から受信した情報を取得して、ナビゲーション装置２の現在位置（自車位置）を算出する。なお、現在位置の算出に当たっては、車両の方位センサや速度センサなどから得られるデータを用いて、前記ＧＰＳ衛星から受信した情報に基づき算出した現在位置を補正するようにしてもよい。
【００４２】
探索条件設定部２３０は、入出力部２４を介して、経路案内に必要な目的地および探索条件（経路探索するとき、経路の距離または所要時間のいずれを優先するか、有料道路を優先するか、交通状況を考慮するか、費用を考慮するか、環境を考慮するかなどの条件）のデータを設定する。
【００４３】
経路要求送信部２４０は、位置情報取得部２１０が算出した現在位置、および、探索条件設定部２３０により設定された目的地および探索条件を含む経路要求情報を生成し、通信部２２を介してサーバ装置１へ送信する。
【００４４】
経路情報取得部２２０は、前記送信した経路要求情報に応答して、サーバ装置１から送信される経由地情報からなる経路情報を、通信部２２を介して取得するとともに、その経路情報に含まれる誘導経路に関する情報を、補助記憶部２１内に経由地情報２１１として記憶する。
【００４５】
経由地同定部２５０は、経由地情報２１１に記憶された経由地情報を参照し、その経由地情報によって指定される経由地が、地図データベース２１３に格納されている道路データのどの道路リンクまたはノードに相当するかを、全ての経由地について同定する。ここで、経由地情報は、後記するように、複数の経由ノード情報と、それに対応する補足地点情報（座標情報、分岐方向など）、属性情報（ノード種別や交差点名称など）を含んで構成されており、経由地同定部２５０は、各経由ノードと補足地点を始終点とする仮のリンクを構成し、地図データベース２１３の道路リンクに対して、座標、方向、仮のリンクの属性情報（リンク種別、道路種別、規制情報など）などを、リンク単位で照合するマッチング処理を行う。
【００４６】
経路探索部２６０は、サーバ装置１から送信された経路情報（経由地情報２１１）に基づき、前記経由地同定部２５０によって同定された経由地を経由する出発地から目的地までの経路を、前記探索条件設定部２３０にて設定された条件と同じ条件で探索し、探索した経路（経路Ｒ１）の情報を誘導経路情報２１２として記憶する。
【００４７】
また、経路探索部２６０は、サーバ装置１から送信された経路情報（つまり、経路Ｒ１を表す情報）に含まれる出発地および目的地が、それぞれ、衛星電波受信部２６によって得られた現在位置、および、入出力部２４によって指定された最終目的地と異なる場合には、衛星電波受信部２６によって得られた現在位置からサーバ装置１から送信された経路情報に含まれる出発地までの経路（経路Ｒ０）、および、サーバ装置１から送信された経路情報に含まれる目的地から入出力部２４によって指定された最終目的地までの経路（経路Ｒ２）をそれぞれ探索する。
【００４８】
さらに、経路探索部２６０は、経路情報取得部２２０がサーバ装置１から経路情報（経由地情報２１１）を受信していない場合には、入出力部２４を介して入力された目的地および探索条件の情報と、位置情報取得部２１０によって取得した現在位置の位置情報とに基づいて、補助記憶部２１内の地図データベース２１３を参照して、目的地までの誘導経路（経路Ｒ３０）を探索する。
【００４９】
経路合成部２７０は、経路探索部２６０で探索した経路Ｒ０、経路Ｒ１、経路Ｒ２を接続合成した経路を最終的な誘導経路（経路Ｒ３）とし、誘導経路情報２１２に記憶する。
【００５０】
経路案内部２８０は、補助記憶部２１に誘導経路情報２１２として記憶された誘導経路（経路Ｒ３）と、位置情報取得部２１０によって取得された現在位置の位置情報と、に基づいて目的地までの経路案内を行う。また、経路情報取得部２２０がサーバ装置１から経路情報（経由地情報２１１）を受信していない場合には、前記探索した経路Ｒ３０に基づいて経路案内を行う。
【００５１】
次に、補助記憶部２１は、ハードディスク装置やフラッシュメモリなどの記憶装置によって構成され、経由地情報２１１、誘導経路情報２１２、地図データベース２１３などの情報を記憶する。
【００５２】
ここで、経由地情報２１１は、サーバ装置１から送信された経由地情報を含む誘導経路に関する経路情報を、補助記憶部２１に記憶した情報である。また、誘導経路情報２１２は、経由地情報２１１によって指定される経由地を含んで探索された出発地点から目的地までの誘導経路（経路Ｒ３またはＲ３０）の経路情報を、補助記憶部２１に記憶した情報である。
【００５３】
また、地図データベース２１３は、経由地の同定、経路探索、誘導案内に必要な地図データを補助記憶部２１に記憶したものである。このような地図データは、道路のリンクデータやノードデータからなる道路データ、目的地を施設名や電話番号などで絞り込んで検索するための目的地検索用データ、表示部２５に地図背景を描画するための背景描画用データ、交差点の右左折案内や走行レーンの案内などを行うための経路誘導用データなどを含んで構成される。
【００５４】
このとき、道路データのリンクデータは、そのリンクの位置を表す座標情報、リンク同士の接続情報のほかに、リンク長、リンク通過所要時間（リンク旅行時間）などのリンクコスト情報や、そのリンクの属性情報（リンク種別、道路種別、規制情報など）を含んで構成される。また、ノードデータは、ノードの位置情報や属性情報（ノード種別や交差点名称など）を含んで構成される。
【００５５】
通信部２２は、経路要求送信部２４０が生成した経路要求情報を、通信ネットワーク３を介してサーバ装置１へ送信する。また、通信部２２は、サーバ装置１から送信された経路情報を受信し、経路案内制御部２０内の経路情報取得部２２０に引き渡す。
【００５６】
メモリ部２３は、ＲＡＭやフラッシュメモリなどによって構成され、経路案内制御部２０の図示しないＣＰＵが実行するためのプログラムを記憶するとともに、地図データベース２１３を記憶するとともに、前記プログラムの実行に従って、作成される経由地情報２１１や誘導経路情報２１２などのデータを適宜記憶する。
【００５７】
入出力部２４は、例えば、リモコン装置、タッチパネルなどを含んで構成され、外部からのナビゲーション装置２への指示を受け付ける。さらに、入出力部２４は、スピーカを備え、経路案内制御部２０が制御する各種の制御処理に応じて、その処理状況や処理結果の音声案内をそのスピーカを介して出力してもよい。
【００５８】
表示部２５は、液晶ディスプレイなどによって構成され、経路案内制御部２０の制御の下に、経路案内部２８０に組み込まれている所定の処理に従って出力される、自車の現在位置近傍の地図や、目的地までの誘導経路や、交差点における誘導案内情報などを表示する。
【００５９】
衛星電波受信部２６は、ナビゲーション装置２の現在位置を算出するために必要となるＧＰＳ衛星からの電波を受信する。衛星電波受信部２６は、通常、４個のＧＰＳ衛星から送信される位置情報や時刻情報などを受信するとともに、そのそれぞれの受信時刻を取得する。位置情報取得部２１０は、それらの時刻情報などに基づき、各ＧＰＳ衛星までの距離（擬似距離）を求め、その距離情報やＧＰＳ衛星の位置情報に基づき、自車の現在位置を算出する。
【００６０】
＜経路案内システムの動作＞
続いて、図１を参照しつつ、図２に沿って、経路案内システム７の全体の動作手順について、詳しく説明する。図２は、本発明の実施形態に係る経路案内システム７の全体の動作手順の例を示したフローチャートである。
【００６１】
図１を参照して説明したように、サーバ装置１の制御部１０は、指定された出発地から指定された目的地までの経路を誘導経路探索部１３０により探索することができる。また、ナビゲーション装置２の経路案内制御部２０は、現在地または指定された出発地から指定された目的地までの経路を経路探索部２６０により探索することができる。
【００６２】
そこで、経路案内システム７の動作は、まず、その経路探索をサーバ装置１で行うか、または、ナビゲーション装置２で行うか、を決定することから開始される。それは、サーバ装置１によって探索される経路と、ナビゲーション装置２によって探索される経路と、は必ずしも同じにはならないからである。当然ではあるが、サーバ装置１ほうが、ナビゲーション装置２よりも、付加価値の高い経路を探索することができる。
【００６３】
ちなみに、サーバ装置１が保持する地図データベース１１１は、ナビゲーション装置２が保持する地図データベース２１３よりも、情報量が豊富であり、しかも、最新の情報が反映されたものとなっている。例えば、サーバ装置１の地図データベース１１１は、つねに、最新バージョンの地図データに更新され、また、そのリンク旅行時間なども、交通情報センタ５１から得られる最新の道路の渋滞情報などが反映されたものとなっている。それに対し、ナビゲーション装置２の地図データベース２１３は、必ずしも、最新バージョンの地図データではなく、しかも、そのリンク旅行時間にも最新の道路の渋滞情報などが反映されているわけではない。
【００６４】
そこで、ユーザは、まず、ナビゲーション装置２の入出力部２４を介して、出発地、目的地および経路の様々な探索条件（時間優先、距離優先、費用優先、エコ優先、高速道路優先など）を設定する。すなわち、ナビゲーション装置２の経路案内制御部２０は、探索条件設定部２３０の処理により、出発地および目的地を含めた経路の探索条件の設定を促すメッセージを表示部２５の表示装置に表示するとともに、その表示に応答するユーザが入出力部２４を介して入力する情報に基づき、出発地および目的地を含む経路の探索条件を設定する（ステップＳ２０１）。
【００６５】
このとき、その探索条件の中には、経路探索を「サーバ装置１で行うか」あるいは「ナビゲーション装置２で行うか」を選択する条件が含まれている。そこで、ユーザは、そのいずれかを選択するための指示情報を入力する。
【００６６】
次に、経路案内制御部２０は、ユーザが入力する指示情報に基づき、ナビゲーション装置２をサーバ装置１に接続するか否かを判定する（ステップＳ２０２）。すなわち、ユーザが入力する指示情報が「経路探索をサーバ装置１で行う」であった場合、つまり、ナビゲーション装置２をサーバ装置１に接続する場合には（ステップＳ２０２→Ｙｅｓ）、経路案内制御部２０は、出発地（この場合の出発地は、ユーザが指定する出発地、または、車両の現在位置のいずれか）、目的地、探索条件などの情報を含んだ経路要求情報をサーバ装置１に送信する（ステップＳ２０３）。
【００６７】
一方、ユーザが入力する指示情報が「経路探索をナビゲーション装置２で行う」であった場合、つまり、ナビゲーション装置２をサーバ装置１に接続しない場合には（ステップＳ２０２→Ｎｏ）、経路案内制御部２０は、ナビゲーション装置２をサーバ装置１に接続することなく、自身のナビゲーション装置２の補助記憶部２１に記憶されている地図データベース２１３を用いて、目的地までの誘導経路を探索する（ステップＳ２０４）。
【００６８】
次に、ステップＳ２０３の処理により、経路要求情報がサーバ装置１へ送信されると、サーバ装置１の制御部１０は、経路要求処理部１２０の処理により、通信部１２を介して経路要求情報を受信する（ステップＳ１０１）。そして、制御部１０は、誘導経路探索部１３０の処理により、前記の経路要求情報に含まれる出発地（または、車両の現在位置）、目的地、探索条件などによって指定される誘導経路を探索する（ステップＳ１０２）。
【００６９】
ここで、誘導経路の探索においては、制御部１０は、誘導経路の評価指標として、誘導経路の距離、旅行時間、費用（燃料消費量、高速代金、その旅行にかかる人件費など）、ＣＯ２排出量などを設定することができる。また、このとき用いる旅行時間としては、予め地図データベース１１１に記憶された各道路リンクの旅行時間の他に、交通情報センタ５１から取得した現況交通情報や予測交通情報に基づいて計算された各道路リンクの旅行時間を用いることもできる。
【００７０】
そして、ステップＳ１０２の誘導経路の探索処理により、誘導経路の計算に失敗し、指定された探索条件に適った誘導経路を見つけることができなかった場合には（ステップＳ１０３→Ｎｏ）、制御部１０は、経路情報送信部１５０の処理として、経路情報が得られなかったこと（つまり、「経由地情報無し」）を示した情報を、ナビゲーション装置２に送信する（ステップＳ１０４）。
【００７１】
一方、ステップＳ１０２の誘導経路の探索処理により、探索条件に適った誘導経路を見つけることができた場合には（ステップＳ１０３→Ｙｅｓ）、制御部１０は、その誘導経路情報をナビゲーション装置２へ送信することになるが、本実施形態では、誘導経路情報を緯度・経度の座標情報ベースで表すものとし、情報量削減のために、誘導経路を表す経由地の数を削減する。
【００７２】
そこで、制御部１０は、経由地情報生成部１４０の処理により、その誘導経路に含まれるノード（つまり、交差点）の中から経由ノードを選出し、さらに、その選出した経由ノードの特定を容易化するための補足地点を設定し、その経由ノードおよび補足地点の情報に基づき、経由地情報を生成する（ステップＳ１０５）。なお、経由地情報の生成については、別途、図３および図４を用いて、また、経由地情報の構成については、図６を用いて詳細に説明する。
【００７３】
次に、制御部１０は、経路情報送信部１５０の処理により、通信部１２を介して、前記生成した経由地情報をナビゲーション装置２に送信する（ステップＳ１０６）。
【００７４】
続いて、ナビゲーション装置２の経路案内制御部２０は、経路情報取得部２２０の処理により、サーバ装置１から送信された経由地情報を受信し（ステップＳ２０５）、その受信した経由地情報が「経由地情報無し」を示した情報であった場合には（ステップＳ２０６→Ｙｅｓ）、自身のナビゲーション装置２の補助記憶部２１に記憶されている地図データベース２１３を用いて、目的地までの誘導経路を探索する（ステップＳ２０４）。一方、受信した経由地情報が有意な経由地情報であった場合（つまり、「経由地情報あり」の場合）には（ステップＳ２０６→Ｎｏ）、その受信した経由地情報を、補助記憶部２１の経由地情報２１１として記憶しておく（ステップＳ２０７）。
【００７５】
次に、制御部１０は、経由地同定部２５０の処理により、補助記憶部２１の経由地情報２１１および地図データベース２１３を参照し、経由地情報２１１に含まれる経由ノード情報および補足地点情報によって指定される誘導経路の経由ノードを、地図データベース２１３を用いてマップマッチングし、前記経由ノードを地図データベース２１３における道路データのノード番号またはリンク番号に対応付ける経由地の同定処理を実行する（ステップＳ２０８）。なお、経由地同定処理の詳細については、別途、図７を用いて詳しく説明する。
【００７６】
次に、制御部１０は、経路探索部２６０の処理により、前記同定された経由地のノードまたはリンクを出発地側から順に結ぶ経路を探索し（ステップＳ２０９）、その探索した経路（経路Ｒ１）を補助記憶部２１の誘導経路情報２１２に記憶する。また、サーバ装置１から得られた誘導経路（つまり、経路Ｒ１）の出発地および目的地が、ナビゲーション装置２の現在位置および最終目的地と異なる場合には、制御部１０は、さらに、その現在位置から経路Ｒ１の出発地までの経路（経路Ｒ０）と、経路Ｒ１の目的地から最終目的地までの経路（経路Ｒ２）と、を各々探索する。
【００７７】
そして、前記経路探索の結果、複数の誘導経路（経路Ｒ０、経路Ｒ１、経路Ｒ２）が求められていた場合には、制御部１０は、経路合成部２７０の処理により、それらの経路Ｒ０、経路Ｒ１、経路Ｒ２を接続し、全体の誘導経路を生成する経路合成処理を実行する（ステップＳ２１０）。なお、経路合成処理の詳細については、別途、図８および図９を用いて詳しく説明する。
【００７８】
次に、制御部１０は、経路案内部２８０の処理により、ステップＳ２１０あるいはステップ２０４で生成した誘導経路を用い、かつ、位置情報取得部２１０を介して取得した現在位置の位置情報を用いて、自車位置近傍の地図や交差点での進路指示などを表示部２５の表示装置に表示する経路案内処理を実行する（ステップＳ２１１）。さらに、制御部１０は、現在位置が目的地に到着したか否かを判定し（ステップＳ２１２）、目的地に到着していない場合には（ステップＳ２１２→Ｎｏ）、再度、経路案内処理を実行し（ステップＳ２１１）、目的地に到着した場合には（ステップＳ２１２→Ｙｅｓ）、ナビゲーション装置２における全体の処理を終了する。
【００７９】
以上、図２を用いて説明した経路案内システム７では、サーバ装置１が、ナビゲーション装置２から送信される経路要求に応じた誘導経路を探索し、その誘導経路に基づき、経由地情報を生成し、生成した経由地情報をナビゲーション装置２に提供することを想定している。このとき、サーバ装置１の端末装置として、ナビゲーション装置２の代わりに、例えば、自宅や会社などに設置されたパーソナルコンピュータや、個人情報端末としての携帯電話などを用いてもよい。
【００８０】
この場合、パーソナルコンピュータや携帯電話は、自宅や出先から旅行計画を立案するのに便利であり、サーバ装置１から経由地情報を受信するステップ（ステップＳ２０５）、または、経由地を結ぶ誘導経路探索をするステップ（ステップＳ２０９）まで処理することができる。そこで、パーソナルコンピュータや携帯電話は、サーバ装置１から取得した経由地情報、または、経由地情報に基づき探索された誘導経路情報を、例えば、ＵＳＢ（Universal Serial Bus）メモリなどの可搬記憶媒体に記憶させる。そして、その可搬記憶媒体をナビゲーション装置２に接続すれば、パーソナルコンピュータや携帯電話を用いて立案した旅行計画などによって得られた経由地情報、または、その経由地情報に基づき探索された誘導経路情報を、ナビゲーション装置２へ転送することができる。すなわち、ユーザは、パーソナルコンピュータや携帯電話を用いて立案した旅行計画の経路を、ナビゲーション装置２で活用することができる。
【００８１】
次に、図３および図４を参照して、サーバ装置１における経由地情報の生成処理（図２のステップＳ１０５）について、詳細に説明する。ここで、図３は、本発明の実施形態に係るサーバ装置１における経由地情報の生成処理の処理フローの例を示した図である。また、図４は、本発明の実施形態に係る経由地の選出および補足地点の設定を説明するための図である。
【００８２】
図３に示すように、制御部１０は、まず、図２のステップＳ１０２で探索した誘導経路に含まれる交差点ノードを分岐数の多い順にソートし（ステップＳ３０１）、分岐数の多い交差点ノードから順に経由ノードＰiを選出する（ステップＳ３０２）。そして、前記誘導経路に含まれる交差点ノードの全ノードを選出していない場合には（ステップＳ３０３→Ｎｏ）、ステップＳ３０２の経由ノードの選出を繰り返して行う。
【００８３】
一方、全ノードを選出し（ステップＳ３０３→Ｙｅｓ）、選出した経由ノードの数が最大数Ｎを超えると（ステップＳ３０７→Ｙｅｓ）、制御部１０は、選出した経由ノード間の距離（１つ前に選出した経由ノードＰi-1とそのとき選出した経由ノードＰiとの間の距離）が所定値以下の経由ノードＰiを間引き（ステップＳ３０４）、狭いエリアに経由ノードが密集することを防ぐ。ここで、経由ノードの最大数Ｎは、経由地情報をナビゲーション装置２に配信する際の通信負荷（料金や時間）を考慮して設定された値である。
【００８４】
以上のようにして、経由ノードの選出が終了すると（ステップＳ３０４の終了、または、ステップＳ３０７→Ｎｏ）、選出した各経由ノードから経路方向に分岐する道路上の地点を補足地点として設定する（ステップＳ３０５）。なお、補足地点の設定処理については、別途、図５を用いて詳細に説明する。
【００８５】
なお、ここでは、分岐数の多い交差点ノードを優先して経由ノードの選定を行う方法について説明したが、始点Ｓから直線距離あるいは道路に沿って所定距離以上離れた交差点ノードを対象に経由ノードの選定を行うようにしてもよい。これより、ナビゲーション装置２がサーバ装置１に経路を要求している間に車両移動により始点Ｓを通過しても、Ｓ２０９においてサーバ装置１から得られた全ての経由ノードを有効に経路を探索することができる。また、既に通過した経由ノードを再度経由する経路が計算されることを未然に防ぐことができる。前記通過した経由ノードを再度経由する経路が計算されてしまうという問題については、Ｓ２０９において通過した経由ノードを検出し、該経由ノードを除く経由ノードを結ぶ経路を探索する方法をとっても解消可能である。
【００８６】
ここで、図４を参照して、補足地点について説明しておく。図４において、Ｓは始点（出発地）、Ｅは終点（目的地）、実線は誘導経路、破線は誘導経路ではない道路を表し、また、白丸印は、誘導経路上の経由地（始点Ｓおよび終点Ｅを含む）を表している。このとき、網掛けされた丸印Ｐaは、経由地Ｐaに対して設けられた補足地点を表す。
【００８７】
このような補足地点は、ナビゲーション装置２が経由地情報を受信したとき、誘導経路を誤ることなく特定するために付加する情報であり、例えば、図４の例では、経由地Ｐiに補足地点Ｐaを付加することによって、誘導経路に含まれる経路５０１を、誘導経路に含まれない経由地Ｐaから分岐する経路５０２と間違えることなく特定することが可能となる。
【００８８】
再度、図３を参照すると、制御部１０は、前記選出した経由ノードの座標情報および属性情報（ノード属性、交差点名称など）からなる経由ノード情報と、前記設定した補足地点の座標情報からなる補足地点情報と、前記経由ノードから補足地点に向かい、その補足地点を含む道路リンクの属性情報（道路種別、リンク種別、レーン数、幅員など）と、により経由地情報を生成する（ステップＳ３０６）。なお、経由地情報の構成については、別途、図６を用いて詳細に説明する。
【００８９】
次に、図５を参照（適宜、図４も参照）して、サーバ装置１における補足地点の設定処理（図３のステップＳ３０５）について、詳細に説明する。ここで、図５は、本発明の実施形態に係るサーバ装置１における補足地点の設定処理の処理フローの例を示した図である。
【００９０】
制御部１０は、補足地点の設定の処理を開始すると、それまでに選出しておいた経由ノードＰiを誘導経路に沿って順に選択し（ステップＳ４００）、それ以降の処理により、経由ノードＰi毎に補足地点を設定する。
【００９１】
制御部１０は、まず、経由ノードＰiから所定の距離Ｌ以上離れた経路上の形状補間点を経由ノードＰiの補足地点候補Ｐa’として選択する（ステップＳ４０１）。なお、形状補間点は、地図データベース１１１の地図データにおいて、道路リンクの形状を表現するために設けられた座標情報（緯度・経度情報）を有する道路リンク上の点である。
【００９２】
制御部１０は、次に、地図データベース１１１を参照し、補足地点候補Ｐa’の近傍に設定した所定の大きさのエリアＡ内（図４で、破線の矩形で囲った部分）に誘導経路以外の道路が存在するか否かを判定し（ステップＳ４０２）、誘導経路以外の道路が存在しない場合には（ステップＳ４０２→Ｎｏ）、補足地点候補Ｐa’を当該経由ノードＰiの補足地点Ｐaとして確定させる（ステップＳ４１０）。
【００９３】
一方、前記エリアＡ内に誘導経路以外の道路が存在する場合には（ステップＳ４０２→Ｙｅｓ）、制御部１０は、そのエリアＡ内の道路の１つを選択し、選択した道路の形状補間点と誘導経路上の補足地点候補Ｐa’との直線距離を計算し、Ｐa’に最も近い形状補間点Ｐb（図４参照）を選択する（ステップＳ４０３）。
【００９４】
次に、制御部１０は、経由ノードＰiと形状補間点Ｐbとを結ぶ直線距離ｄを計算し（ステップＳ４０４）、その直線距離ｄが所定の距離Ｌよりも短い場合には（ステップＳ４０５→Ｙｅｓ）、誘導経路上に次の形状補間点が存在するか否かを判定し（ステップＳ４０７）、形状補間点が存在すれば（ステップＳ４０７→Ｙｅｓ）、その形状補間点を新たに補足地点候補Ｐa’とし（ステップＳ４０８）、ステップＳ４０２へ戻り、ステップＳ４０２以降の処理を繰り返して実行する。また、次の形状補間点が存在しない場合には（ステップＳ４０７→Ｎｏ）、誘導経路上の次のノードを新たに補足地点候補Ｐa’とし（ステップＳ４０９）、ステップＳ４０２へ戻り、ステップ４０２以降の処理を繰り返して実行する。
【００９５】
また、ステップＳ４０５において、直線距離ｄが所定の距離Ｌ以上である場合には（ステップＳ４０５→Ｎｏ）、制御部１０は、エリアＡに存在する全ての道路の選択が終了したか否かを判定し（ステップＳ４０６）、その選択が終了していない場合には（ステップＳ４０６→Ｎｏ）、ステップＳ４０３へ戻り、ステップＳ４０３以降の処理を繰り返して実行する。
【００９６】
また、ステップＳ４０６において、エリアＡに存在する全ての道路の選択が終了した場合には（ステップＳ４０６→Ｙｅｓ）、補足地点候補Ｐa’を当該経由ノードＰiの補足地点Ｐaとして確定させる（ステップＳ４１０）。
【００９７】
次に、制御部１０は、誘導経路上の全ての経由ノードＰiについて補足地点Ｐaを設定したか否かを判定し（ステップＳ４１１）、全ての経由ノードＰiについての設定が終了していない場合には（ステップＳ４１１→Ｎｏ）、ステップＳ４００へ戻り、ステップＳ４００以降の処理を繰り返して実行する。また、全ての経由ノードＰiについての設定が終了している場合には（ステップＳ４１１→Ｙｅｓ）、この補足地点設定処理を終了する。
【００９８】
以上のようにして、各経由ノードＰiの補足地点Ｐaは、それぞれの周辺の道路と密接していない地点に設定される。従って、サーバ装置１で設定された補足地点の座標値が、ナビゲーション装置２側の地図データベース２１３に記憶されている道路データの座標値と若干ずれたとしても、周辺道路と離れた位置、つまり、道路が密集していない位置に補足地点Ｐaが設定されているので、ナビゲーション装置２では、サーバ装置１から送信された誘導経路の経由ノードＰiの位置を、誘導経路とは異なる道路リンクに誤認識する可能性は極めて低くなる。
【００９９】
図６は、本発明の実施形態に係るサーバ装置１からナビゲーション装置２に提供される経由地情報のデータフォーマットの例を示した図である。図６に示すように、経由地情報は、経由ノード数、経由ノード座標、補足地点座標、属性情報を含んで構成される。
【０１００】
ここで、経由ノード座標および補足地点座標における座標値には、メーカやバーションなどが異なる地図データ間で共通に扱うことが可能な緯度・経度の値を用いるが、地図座標系の変換が可能な場合は、正規化座標（メッシュ座標、Ｘ座標、Ｙ座標）を用いても構わない。
【０１０１】
属性情報は、経由ノードの種別（交差点、料金所、ジャンクション、サービスエリアやパーキングエリアへの出入り口など）、経由ノードの交差点名称、経由ノードから補足地点への分岐方向θ（図４に示すように、真北を基準に時計回りの角度）、経由ノードから補足地点に向かう道路の道路種別（国道、県道など）、同道路のリンク種別（交差点内、トンネル、高架など）、次の経由ノードまでの距離など、経由ノードや、誘導経路の目的地方向に沿って経由ノードに接続されたリンクを特定する情報を含む。また、図示をしていないが、通行料金の割引サービスが有効な経路の場合には有効なサービスと割引前後の料金情報、環境考慮した経路の場合にはＣＯ２の削減量といった環境に関わる情報、他に消費燃料情報や経路沿いの休憩箇所や観光スポットなど、経路に関わる様々な情報を含める。
【０１０２】
なお、属性情報には、前記情報の他に地図データベース１１１に含まれているノードおよび道路リンクに関わる他の属性情報（レーン数や幅員など）を追加してもよいが、ナビゲーション装置２に経由地情報を提供する際の通信負荷を増加させるので、必要最小限に留めることが望ましい。
【０１０３】
図７は、本発明の実施形態に係るナビゲーション装置２における経由地の同定処理および経路探索処理（図２のステップＳ２０８およびＳ２０９）の処理フローの例を示した図である。
【０１０４】
ナビゲーション装置２の経路案内制御部２０は、まず、補助記憶部２１の経由地情報２１１を参照して、経由地順に、経由ノード情報、補足地点情報、属性情報を読み込み（ステップＳ７０１）、これらの情報によって表される経由ノードと補足地点とを結ぶ仮のリンクを構成する（ステップＳ７０２）。
【０１０５】
次に、経路案内制御部２０は、この仮のリンクの属性情報（座標、道路種別およびリンク種別）を用いて、地図データベース２１３に記憶されている道路データから、この仮のリンクに対応する候補道路を検索する（ステップＳ７０３）。
【０１０６】
そして、ステップＳ７０３での検索の結果、候補道路が見つかった場合（ステップＳ７０４→Ｙｅｓ）、経路案内制御部２０は、その候補道路に含まれる交差点ノードの中から、経由ノードの座標および属性（ノード種別や名称）に該当するノードを検索する（ステップＳ７０５）。
【０１０７】
そして、ステップＳ７０５の検索の結果、経路案内制御部２０は、経由ノードの座標値およびノード属性情報に該当するノードがあった場合には（ステップＳ７０６→Ｙｅｓ）、その該当したノードの地図データベース２１３で管理されているノード番号を、前記経由ノードに対応付ける（ステップＳ７０７）。
【０１０８】
さらに、経路案内制御部２０は、前記ノード番号のノードから、前記仮のリンクの方向または属性情報に含まれる分岐方向θに分岐する道路リンクを検索する（ステップＳ７０８）。そして、その検索の結果、該当する道路リンクがあった場合には（ステップＳ７０９→Ｙｅｓ）、その該当した道路リンクの地図データベース２１３で管理されているリンク番号を、前記仮のリンクに対応付け（ステップＳ７１０）、前記該当リンクを、地図データベース２１３の道路データに基づく誘導経路の経由リンクとする。
【０１０９】
次に、経路案内制御部２０は、全ての経由ノードの同定の処理を終了したか否かを判定し（ステップＳ７１１）、終了していない場合には（ステップＳ７１１→Ｎｏ）、ステップＳ７０１へ戻り、ステップＳ７０１以降の処理を繰り返して実行する。
【０１１０】
以上のようにして、経路案内制御部２０は、経由地情報に含まれる各経由ノードに対して、各経由ノードに対応する地図データベース２１３上のノード番号を対応付け、さらに、誘導経路に沿って、その経由ノードから目的地方向に分岐する道路リンク（以下、経由リンクと呼ぶ）のリンク番号を対応付けることができる。
【０１１１】
なお、ノード番号またはリンク番号を対応付ける過程で、地図データベース２１３上に該当する候補道路が見つからなかった場合（ステップＳ７０４→Ｎｏ）、該当するノードが見つからなかった場合（ステップＳ７０６→Ｎｏ）、該当するリンクが見つからなかった場合には（ステップＳ７０９→Ｎｏ）、当該経由ノードに対応する道路が存在しなかったと判定し、ノード番号またはリンク番号の対応付けを省略する。
【０１１２】
また、ステップＳ７０６において該当するノードが見つからなかった場合には（ステップＳ７０６→Ｎｏ）、経路案内制御部２０は、さらに、当該経由ノードが誘導経路の始終点として設定されたノードであるか否かを判定する（ステップＳ７１５）。そして、その判定の結果、始終点（図４における始点Ｓおよび終点Ｅ）のいずれかに設定されたノードであった場合には（ステップＳ７１５→Ｙｅｓ）、それぞれ、１つ次または１つ前の経由ノードを始終点ノードに設定する（ステップＳ７１６）。すなわち、当該ノードが始点であれば１つ次の経由ノードは始点とし、終点であれば１つ前の経由ノードを終点とする。なお、始終点情報は、経由ノードの属性情報として与えられているものとする。
【０１１３】
このように、始終点をナビゲーション装置２の地図データベース２１３で同定できなかった場合に、始終点を設定し直すことによって、始終点が同定できなかったことによる経路の再現エラーを防止することができる。従って、ナビゲーション装置２では、自身が有する地図データベース２１３を用いて、サーバ装置１が提供した誘導経路を極力利用できるようになる。
【０１１４】
次に、経路案内制御部２０は、全ての経由ノードの同定の処理を終了した場合には（ステップＳ７１１→Ｙｅｓ）、その同定の処理で同定した経由リンクを経由する始点Ｓから終点Ｅまでの経路を探索し（ステップＳ７１２）、地図データベース２１３に基づくリンク番号で表した誘導経路を得る。このようにして得た誘導経路を、以下、「再現した誘導経路」、または、単に、「再現経路」と呼ぶ。
【０１１５】
次に、経路案内制御部２０は、再現経路上の経由ノード間距離と、サーバ装置１から送信された経由地情報に含まれるに含まれる経由ノード間距離（図６参照：属性情報の次の経由ノードまでの距離）とを比較し、そのいずれかが所定の値以上に乖離している場合は（ステップＳ７１３→Ｙｅｓ）、経路が正確に再現できていない可能性のあることを利用者に提示するために経路再現エラーを出力する（ステップＳ７１４）。
【０１１６】
図８は、本発明の実施形態に係るナビゲーション装置２における経路合成処理（図２のステップＳ２１０）の処理フローの例を示した図である。また、図９は、その経路合成を説明するための図である。
【０１１７】
図９において、実線で示された経路Ｒ１は、サーバ装置１から送信された経由地情報に基づいてナビゲーション装置２の経路探索部２６０により探索された、始点Ｓから終点Ｅに向かう誘導経路の再現経路である。また、地点Ｏは、衛星電波受信部２６によって受信された情報に基づき得られた車両の現在位置、Ｄは入出力部２４を介してユーザが設定した目的地を示す。また、破線で示された経路Ｒ０は、現在位置Ｏから始点Ｓに向かう経路、経路Ｒ２は、終点Ｅから目的地Ｄに向かう経路を表している。
【０１１８】
まず、経路案内制御部２０は、車両の現在位置Ｏと経路Ｒ１の始点Ｓの座標情報を参照し（ステップＳ８０１）、両者の座標情報が異なる場合には（ステップＳ８０２→Ｙｅｓ）、現在位置Ｏを始点、経路Ｒ１の始点Ｓを終点に設定し（ステップＳ８０３）、経路探索部２６０により現在地Ｏから始点Ｓに向かう経路Ｒ０を探索する（ステップＳ８０４）。なお、両者の座標情報が同じである場合は（ステップＳ８０２→Ｎｏ）、ステップＳ８０３およびステップＳ８０４を実行する必要はない。
【０１１９】
次に、経路案内制御部２０は、経路Ｒ１の終点Ｅと目的地Ｄの位置が異なる場合は（ステップＳ８０５→Ｙｅｓ）、終点Ｅを始点、目的地Ｄを終点に設定し（ステップＳ８０６）、経路探索部２６０により終点Ｅから目的地Ｄに向かう経路Ｒ２を探索する（ステップＳ８０７）。なお、両者の座標情報が同じである場合は（ステップＳ８０５→Ｎｏ）、ステップＳ８０６およびステップＳ８０７を実行する必要はない。
【０１２０】
さらに、経路案内制御部２０は、前記探索した経路Ｒ０、Ｒ１、Ｒ２の複数経路を各始終点で接続し、出発地Ｏから目的地Ｄへ向かう誘導経路を生成する（ステップＳ８０８）。このように、複数経路を接続して１つの経路とすることにより、出発地や目的地でスピーカなどを介して出力される「経路案内を開始します」、「目的地に到着します」などの音声メッセージなどが経路途中で出力されることを防ぎ、経路Ｒ０、Ｒ１、Ｒ２の接続点でも、交差点手前で通過予定の交差点までの距離、右左折方向、案内交差点拡大図などの案内情報をユーザに提示することが可能となる。
【０１２１】
以上のように、本実施形態では、経路案内制御部２０がサーバ装置１に対して誘導経路の探索要求をするときの出発地（始点Ｓ）および目的地（終点Ｅ）と、車両走行時に得られた、または、設定された現在位置（出発地Ｏ）および目的地（最終の目的地Ｄ）と、が相違することは、経路案内システム７の動作において前提とされている。その前提に基づき、経路案内制御部２０には、経路合成部２７０が設けられ、その経路合成部２７０の処理により、経路Ｒ０、Ｒ１、Ｒ２をつなぎ合わせて１つの誘導経路にすることができる。
【０１２２】
この経路合成部２７０の機能は、ナビゲーション装置２を利用するユーザにとって好都合である。例えば、横浜から長野まで走行する場合、サーバ装置１に対しては、始点Ｓおよび終点Ｅとして、それぞれ横浜および長野の主要な交差点を設定し、経路Ｒ１を得ることができ、その経路は、通常、幹線道路であり、渋滞などの影響を受けやすい。従って、その経路Ｒ１をサーバ装置１で探索する意義が認められる。
【０１２３】
一方、現在地Ｏから始点Ｓまでの経路Ｒ０や終点Ｅから目的地Ｄまでの経路Ｒ２は、幹線道路から外れた市街地の細い街路であったり、地方の山道であったりする。そのような場合、サーバ装置１の地図データベース１１１であっても、ナビゲーション装置２の地図データベース２１３であっても、その地図データは、現実の道路状況を十分に反映し得ていないことが多い。従って、例えば、横浜の主要な交差点に到達するまでの道路や、長野の主要な交差点から最終目的地に到るまでの道路では、車両は、地図にない道路など誘導経路から外れて走行することが多くなる。また、そのような道路事情では、ナビゲーション装置２は、サーバ装置１から送信された経路を正しく再現することもできなくなる。
【０１２４】
すなわち、現在位置Ｏから最終目的地Ｄまでを通した誘導経路をサーバ装置１で探索する意義は薄く、本実施形態のように、経路Ｒ０や経路Ｒ２は、ナビゲーション装置２で探索するほうがより合理的といえる。しかも、本実施形態の場合、経路Ｒ０、Ｒ１、Ｒ２は、１本の誘導経路として合成されるので、ユーザにとって不都合は生じない。従って、本実施形態に係る経路案内システム７は、ユーザに安定した誘導経路を提供することができるようになる。
【０１２５】
続いて、図１０〜図１４を参照して、本発明の実施形態の変形例について説明する。
【０１２６】
＜実施形態の第１の変形例＞
図１０は、本発明の実施形態に係るサーバ装置１における経由地情報生成処理の処理フローの第１の変形例を示した図である。また、図１１は、その第１の変形例に係る経由地情報の設定処理において経由地の選出方法を説明するための図である。
【０１２７】
図１１において、太い破線で示された誘導経路１１０１は、サーバ装置１の誘導経路探索部１３０により探索された始点Ｓから終点Ｅまでの誘導経路を示す。また、細い破線で示された経路１１０２，１１０３は、それぞれ、始点Ｓから終点Ｅに向かう第２の経路、第３の経路を示す。ノードＰi1およびノードＰi2は、誘導経路１１０１の経由ノード、地点Ｐa1および地点Ｐa2は、それぞれ、ノードＰi1およびノードＰi2を補足する補足地点を示す。
【０１２８】
また、区間Ｚは、誘導経路の経路情報をナビゲーション装置２で再現するとき、渋滞や規制発生などの通行するのが困難または通行するのに異常に時間がかかる区間であり、ユーザとしては必ず避けるようにしたい回避区間を示している。また、Ｐzは、区間Ｚ（以下、回避区間Ｚと記載）の進入側に存在する交差点のノードである。
【０１２９】
図１０に示すように、サーバ装置１の制御部１０は、誘導経路１１０１の始点Ｓから終点Ｅに向かって、道路リンクを順に取得し、その周辺道路の交通状況を参照する（ステップＳ１００１）。なお、サーバ装置１は、交通情報センタ５１などから、予め渋滞情報や通行規制などの交通状況のデータを取得し、外部情報データベース１１２などに記憶しておくものとする。
【０１３０】
そして、制御部１０は、その周辺道路に渋滞や規制などのために回避すべき回避区間Ｚが存在するか否かを判定し（ステップＳ１００２）、回避区間Ｚが存在した場合は（ステップＳ１００２→Ｙｅｓ）、回避区間Ｚの進入側ノードＰzに接続する誘導経路１１０１上のノードＰi1およびＰi2を経由ノードとして選出する（ステップＳ１００３）。さらに、制御部１０は、図５で説明した補足地点の設定フローに従って、経由ノードＰi1および経由ノードＰi2をそれぞれ補足する補足地点Ｐa1およびＰa2を設定する（ステップＳ１００４）。また、回避区間Ｚが存在しない場合は（ステップＳ１００２→Ｎｏ）、制御部１０は、ステップＳ１００３およびステップＳ１００４の実行を省略する。
【０１３１】
次に、制御部１０は、以上の回避区間Ｚの存在の判定を目的地（終点Ｅ）に到達するまで繰り返した否かを判定し（ステップＳ１００５）、目的地に到達するまで繰り返していない場合には（ステップＳ１００５→Ｎｏ）、ステップＳ１００１へ戻って、ステップＳ１００１以下の処理を繰り返して実行する。また、目的地に到達するまで繰り返した場合には（ステップＳ１００５→Ｙｅｓ）、この経由地情報生成処理を終了する。
【０１３２】
以上のようにして、回避区間Ｚを回避可能な経由ノードＰi1，Ｐi2を選出し、その経由ノードＰi1，Ｐi2に対して補足地点Ｐa1，Ｐa2を設定することができる。従って、ナビゲーション装置２の経路案内制御部２０は、このような経由地情報を受信した場合には、経路１１０２，１１０３のように回避区間Ｚを通過する経路を再現することはなく、サーバ装置１が探索した誘導経路１１０１を正しく再現することができるようになる。
【０１３３】
＜実施形態の第２の変形例＞
以上に示した実施形態の変形例では、回避区間Ｚを回避するように経由ノードを設定したが、回避区間Ｚの進入側ノードＰzを回避ノード、回避区間Ｚ近傍に回避地点Ｐazを設定し、回避ノードＰzと回避地点Ｐazを、図６で説明した経由地情報に含めてナビゲーション装置２に提供するようにしてもよい。
【０１３４】
この場合、ナビゲーション装置２の経由地同定処理（図７参照）において、経路案内制御部２０は、経由リンクの同定処理と同様に、回避区間Ｚを含む道路リンク（地図データベース２１３の道路データにおける道路リンク）を検出する。そして、次に実行する経路探索処理において、前記検出した回避区間Ｚを含む道路リンクを回避するように、回避区間Ｚに対応する道路リンクのコストを最大に設定し、始点Ｓから終点Ｅまでの経路を探索する。このようにすれば、回避区間Ｚが誘導経路に含まれることはないので、回避区間Ｚを回避した誘導経路１１０１を再現することができる。
【０１３５】
＜実施形態の第３の変形例＞
図１２は、本発明の実施形態に係るサーバ装置１における経由地情報の生成処理の処理フローの第３の変形例を示した図である。また、図１３は、その第３の変形例に係る経由地情報の設定処理において経由地の選出方法を説明するための図である。
【０１３６】
図１３において、地点Ｏは車両の現在位置、地点Ｄは最終の目的地、地点Ｓおよび地点Ｅは、サーバ装置１に経路探索を要求するときの始点および終点である。ここでは、地点Ｓおよび地点Ｅは、高速道路の入口ＩＣ（インターチェンジ）および出口ＩＣであるとする。また、その高速道路の途中には、料金体系などが変わる地点Ｐiがあるとし、例えば、入口ＩＣから地点ＰiのＩＣまでは大幅な割引料金が適用されているとする。
【０１３７】
このような場合には、ユーザは、入口ＩＣから地点ＰiのＩＣまで高速道路を利用し、地点ＰiのＩＣで高速道路を出ることを考える。そこで、本実施形態の変形例では、このような通行料金割引に関係するノードが存在した場合には、そのノードを必ず経由地に設定するようにする。そうすれば、ナビゲーション装置２では、その通行料金割引に関係するノードを経由する誘導経路を誤りなく再現することができる。従って、ユーザは、車両が地点ＰiのＩＣへ到達したとき、そのＩＣから一般道へ降りることもできる。
【０１３８】
以下、通行料金割引に関係するノードを経由地とする場合の経由地情報の生成処理について、図１２を参照して説明する。
【０１３９】
サーバ装置１の制御部１０は、探索した誘導経路（図１３で、実線で示した地点Ｓから地点Ｅまでの誘導経路１３００）に関係する有料道路の通行料金情報を参照し（ステップＳ１２０１）、誘導経路１３００に含まれるノードに通行料金体系が変わるノードが存在するか否かを判定し（ステップＳ１２０２）、通行料金体系が変わるノードが存在した場合には（ステップ１２０２→Ｙｅｓ）、そのノードを経由ノードＰiとして選出する（ステップＳ１２０３）。なお、制御部１０は、施設情報センタ５２などから有料道路の通行料金情報を予め取得しておき、外部情報データベース１１２などに記憶しておくものとする。
【０１４０】
次に、制御部１０は、図５で説明した補足地点の設定フローに従って、経由ノードＰiに対する補足地点Ｐa（図示せず）を設定する（ステップＳ１２０４）。なお、通行料金が変わるノードが存在しない場合には（ステップ１２０２→Ｎｏ）、制御部１０は、ステップＳ１２０３およびステップＳ１２０４の実行を省略する。
【０１４１】
次に、制御部１０は、以上のような処理を目的地（地点Ｅ）に到達するまで繰り返したか否かを判定し（ステップＳ１２０５）、目的地に到達するまで繰り返していない場合には（ステップＳ１２０５→Ｎｏ）、ステップＳ１２０１へ戻って、ステップＳ１２０１以下の処理を繰り返して実行する。また、目的地に到達するまで繰り返した場合には（ステップＳ１１０５→Ｙｅｓ）、この経由地情報生成処理を終了する。
【０１４２】
以上のような場合においては、サーバ装置１からナビゲーション装置２へ送信する経由地情報のノードの属性情報の中に、例えば、通行料金の割引率や適用範囲などの情報を含めておき、表示部２５にその通行料金の割引率などを表示してもよい。
【０１４３】
＜実施形態の第４の変形例＞
先に説明した本発明の実施形態では、図３に示したように、サーバ装置１における経由地情報の生成処理では、経由地ノードをそのノードから分岐する道路リンク数の多い順に選出したが、経由地ノードの選出は、さらに、他の方法に基づき選出してもよい。
【０１４４】
例えば、経由地情報の生成処理では、分岐数の代わりに交通量の分岐分散率を用いてもよい。ここで、交通量の分岐分散率は、誘導経路に沿って当該ノードに進入する交通量が複数のリンクに分岐するとき、交通量が各脱出リンクに平均の交通量に分散して流出するほど大きくなるような値をいう。
【０１４５】
以下、図１４を参照して、交通量の分岐分散率について説明する。図１４は、本実施形態に係る経由地情報の生成処理における交通量の分岐分散率について説明するための図である。図１４において、白丸印Ｐはノードを表し、矢印Ｌinは進入リンクを表し、３つの矢印Ｌ１，Ｌ２，Ｌ３は脱出リンクを表している。
【０１４６】
例えば、ある時間帯においてノードＰへの進入リンクＬinの交通量を１０００、脱出リンクＬ１，Ｌ２，Ｌ３の交通量を各々２００，３００，５００とする。このとき、各脱出リンクＬ１，Ｌ２，Ｌ３に流出する交通量の割合は、Ｌ1において２００÷１０００＝０．２、Ｌ2において３００÷１０００＝０．３、Ｌ3において５００÷１０００＝０．５となる。最大値０．５で各方向における割合の値を正規化すると、Ｌ1方向が０．４、Ｌ2方向が０．６、Ｌ3方向が１となる。Ｌ3方向を除きこれらの平均値を求めると（０．４＋０．６）÷２＝０．５となり、本実施形態においては、この値を、当該時間帯における進入リンクＬinのノードＰの分岐分散率と呼ぶ。
【０１４７】
このようにして求めた値を分岐分散率というのは、前記したように、交通量が各脱出リンクに平均的に分散する場合には、その値が大きくなり、交通量が特定の脱出リンクに集中する場合には、その値が小さくなるからである。ちなみに、図５の例で、各脱出リンクＬ１，Ｌ２，Ｌ３の交通量がすべて同じであった場合には、各脱出リンクＬ１，Ｌ２，Ｌ３の交通量を、その最大値で正規化した場合の値は、いずれも１になるので、その最大値を除いた２つの値の平均値も１となる。一方、進入交通量がある１つの脱出リンクに集中した場合には、他の２つの脱出リンクの交通量は、０となるので、その最大値で正規化した場合の値は、いずれも０になり、その平均値も０となる。すなわち、交通量が各脱出リンクＬ１，Ｌ２，Ｌ３に全く等しく分散したときには、分岐分散率は、最大値の１となり、交通量が各脱出リンクＬ１，Ｌ２，Ｌ３のいずれか１つに集中したときには、分岐分散率は、最小値の０となる。
【０１４８】
なお、このような分岐分散率は、例えば、各ノードの進入リンク毎に、１日２４時間を単位時間で分割した全ての単位時間帯ごとに算出して定められる。なお、各ノードの進入リンク毎ではなく、進入リンク毎に算出された分岐率の平均値を計算し、その平均値を進入リンクに関係のない各ノードの分岐分散率と定めてもよい。
【０１４９】
なお、本実施形態の変形例では、分岐分散率は、分岐数とともにノード情報として地図データベース１１１に予め記憶されているものとする。ただし、制御部１０が、外部情報センタ５から分岐分散率を取得して、地図データベース１１１に記憶するようにしてもよい。また、サーバ装置１の構成要素として、分岐分散率を計算する分岐率算出部を新たに設け、外部情報センタ５から取得した交通情報（交通量を含む）に基づいて分岐分散率を計算するようにしてもよい。さらに、ナビゲーション装置２からの経路要求情報とともに、車両の走行実績データを受信し、その走行実績データを蓄積することによって、分岐分散率を算出してもよい。
【０１５０】
さらに、経由地を選出する他の方法として、探索条件に施設（コンビニエンスストアや飲食店、サービスエリア／パーキングエリアなどの休憩地点）などの立ち寄り地点が指定された場合、経由ノードの分岐先の道路リンクに立ち寄り地点が存在するノードを優先して経由地ノードとして選出するようにしてもよい。この場合、立ち寄り地点は、交差点ノードと限らないため、立ち寄り地点を含む施設の位置を経由ノードの補足地点としてもよい。
【０１５１】
＜その他の実施形態の変形例＞
さらに、先に説明した本発明の実施形態では、図２のステップＳ２０３において、ナビゲーション装置２は、サーバ装置１に対し経路情報の送信を要求しているが、この実施形態の変形例では、経路情報だけでなく交通情報を併せて要求するようにする。その場合には、サーバ装置１は、誘導経路の探索に失敗、つまり、誘導経路が見つからなかったときに（ステップＳ１０３→Ｎｏ）、「経由地情報無し」を示した情報をナビゲーション装置２に送信するとともに（ステップＳ１０４）、関連する地域の渋滞情報などの交通情報を送信する。そうすれば、ナビゲーション装置２は、その交通情報を利用して自身が有する経路探索部２６０の機能により、目的地までの経路を探索することができる。
【０１５２】
また、先に説明した本発明の実施形態では、ナビゲーション装置２がサーバ装置１へ送信する経路要求情報には、ナビゲーション装置２が有する地図データベース２１３の地図データフォーマットの識別情報およびそのバージョン情報を含めるとはしていないが、その情報を経路要求情報に含めてもよい。
【０１５３】
その場合には、サーバ装置１は、その地図データフォーマットの識別情報およびバージョン情報を判定し、地図データベース１１１の中に、その地図データフォーマットと同じフォーマットで同じバージョンの地図データを有していたときには、その同じフォーマットで同じバージョンの地図データを用いて、ナビゲーション装置２から求められた経路探索を行い、その結果としての経由地情報をナビゲーション装置２へ送信する。
【０１５４】
この場合には、ナビゲーション装置２は、自身が有する地図データベース２１３と同じフォーマットで同じバージョンの地図データに基づき作成された経由地情報を取得することになるので、その経由地情報からはほとんど誤りが生じない経路を再現することができる。
【符号の説明】
【０１５５】
１ サーバ装置
２ ナビゲーション装置
３ 通信ネットワーク
４ 基地局
５ 外部情報センタ
６ ブロードバンドネットワーク
７ 経路案内システム
１０ 制御部
１１ 補助記憶部
１２ 通信部
１３ メモリ部
１４ 入出力部
２０ 経路案内制御部
２１ 補助記憶部
２２ 通信部
２３ メモリ部
２４ 入出力部
２５ 表示部
２６ 衛星電波受信部
５１ 交通情報センタ
５２ 施設情報センタ
５３ 観光情報センタ
１１０ 外部情報取得部
１１１ 地図データベース
１１２ 外部情報データベース
１２０ 経路要求処理部
１３０ 誘導経路探索部
１４０ 経由地情報生成部
１５０ 経路情報送信部
２１０ 位置情報取得部
２１１ 経由地情報
２１２ 誘導経路情報
２１３ 地図データベース
２２０ 経路情報取得部
２３０ 探索条件設定部
２４０ 経路要求送信部
２５０ 経由地同定部
２６０ 経路探索部
２７０ 経路合成部
２８０ 経路案内部
【技術分野】
【０００１】
本発明は、車両の経路案内に好適な経路案内サーバ装置、ナビゲーション装置、経路案内システムおよび経路案内方法に関する。
【背景技術】
【０００２】
近年、道路の混雑状況をはじめ様々な情報センタから送信される最新の情報を、放送や通信装置を介して受信し、その受信した最新情報を考慮した目的地までの適切な経路を車両のドライバに提供するカーナビゲーション装置（以下、ナビゲーション装置と記載）の普及が目覚しい。
【０００３】
例えば、交通情報センタからＦＭ多重放送などで提供される渋滞や旅行時間などの最新の交通情報を受信し、その交通情報を考慮した目的地までの最短時間の経路を計算して目的地までの経路を表示装置に表示する機能は、ナビゲーション装置の基本機能として定着しているといってよい。そして、今では、より速く目的地まで到着可能な経路で、より精度よく到着時刻を予測できるように当該車両の通過予定時刻の予測交通情報を情報センタから取得して、目的地までの最適経路計算に利用するナビゲーション装置も現れ、また、情報センタで最新の交通情報を反映して計算した最適経路を取得し、目的地までの経路を案内するようにしたナビゲーション装置も商品化されている。
【０００４】
さらには、交通情報に限らず、外部の様々なサイト（情報センタ）が有する膨大かつ最新の情報を端末に取り込んでナビゲーションサービスを充実させようとする動きがある。例えば、自宅での旅行計画をサポートするポータルサイトでは、動的に変動する施設や道路の利用料金、施設利用状況、イベント情報などの最新情報を考慮した目的地までの経路情報、出発時間、休憩場所などの情報を提供している。そして、そのようなポータルサイトで計画した旅行情報を通信や可搬の記憶メディアを介してナビゲーション装置に転送し、その情報をナビゲーション装置における目的地までの経路の誘導案内にも利用できるようにしたサービスも存在する。
【０００５】
ところで、目的地までの経路情報を表現する方法には、（ａ）地図データで用いられている道路リンクのリンク番号や、道路リンクの接続点であるノード（一般的には交差点）のノード番号を用いて、経路に含まれる複数のリンク番号またはノード番号の連なりとして表す方法、（ｂ）経路を点列で表し、その各点の緯度・経度などの位置座標の連なりとして表す方法、の２つの方法がある。
【０００６】
情報センタから与えられる経路情報をナビゲーション装置で正しく再現するには、前記（ａ）の方法が望ましい。しかしながら、ナビゲーション装置のメーカが異なり、地図データの形式が異なる場合、あるいは、地図データの形式が同じでも地図バージョンが異なる場合には、同じ道路であっても、同じ道路リンク番号が付されているとは限らない。従って、（ａ）の方法では、情報センタが経路情報をナビゲーション装置に提供する場合、その相互間に道路リンク番号の互換性がないことが大きな問題となる。
【０００７】
それに対し、前記（ｂ）の方法では、経路情報が経路を表す点列の各点の緯度・経度の座標情報によって表されるので、地図データの形式や道路リンク番号の互換性の問題は生じない。しかしながら、この方法では、情報センタとナビゲーション装置との間で地図データが異なり、さらに、例えば、当該経路に接近して並走したり、分岐したりする道路が存在するような場合には、両者の地図データに表された道路位置の緯度・経度の座標情報の誤差のために、情報センタが指定する座標位置をナビゲーション装置の地図データの道路位置に正しく対応させることができないことがある。すなわち、前記（ｂ）の方法には、情報センタが送信する経路情報を、ナビゲーション装置が必ずしも正しく再現することができないという問題がある。
【０００８】
さらに、前記（ｂ）の方法の場合、経路情報は、緯度・経度の座標情報で表された多数の点列データによって表されるので、その情報量が大きくなるという問題がある。情報センタからナビゲーション装置へ送信する経路情報の情報量が大きくなると、その分、通信路の通信負荷が増大するとともに、通信費も増大する。
【０００９】
そこで、こうした通信の情報量を削減する方法として、経路の形状点の座標情報を間引いたり、直線や曲線などで道路形状を近似したりすることが、しばしば、行われており、特許文献１には、その一例が開示されている。
【００１０】
特許文献１によれば、情報センタは、送信しようとしている経路情報に含まれるノードのノード情報のうち、間欠的に選出したノードのノード情報（ノードの座標情報＋属性情報など）を送信する。ナビゲーション装置は、その間欠的に選出されたノードのノード情報（座標情報）に基づき、マップマッチングによりナビゲーション装置の地図データ上で、前記間欠的に選出されたノードのノード番号を特定する。そして、ノード番号が特定されたノード、つまり、前記選出されたノードの相互間をつなぐ経路に含まれるノード、つまり、間引かれたノードのノード番号を経路探索により求める。こうして、ナビゲーション装置は、情報センタが指定した経路を再現する。
【００１１】
また、特許文献１によれば、単なるノード位置座標のマップマッチングでは、誤差の発生を免れ得ないと判断し、情報センタから送信されるノード情報には、ノードの座標情報だけでなく、ノードの属性情報や、そのノードの進入リンク、脱出リンクの属性情報（形状情報など）が含められ、属性情報のマッチングも行われる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００２−２２８４６８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、とくに都市部の道路など、複数の道路が交差するノード周辺には、複数のノードが隣接して存在することも多く、また、それらのノードに付随する属性情報が同じであったり、類似していたりすることも多い。従って、特許文献１に開示されているようなノードの座標情報や属性情報だけでのマッチング処理では、ノードのマップマッチングを誤り、情報センタから送信された経路情報を正しい経路に再現できない事態が生じる恐れが残っている。
【００１４】
そこで、本発明の目的は、情報センタ（経路案内サーバ装置）の地図データとナビゲーション装置の地図データとが異なる場合であっても、情報センタから送信される位置座標ベースで表された経路を、ナビゲーション装置が自身の地図データに基づくリンク番号またはノード番号ベースの経路で誤りなく再現することを可能とする経路案内サーバ装置、ナビゲーション装置、経路案内システムおよび経路案内方法を提供することにある。
【課題を解決するための手段】
【００１５】
本発明に係る経路案内システムにおいては、経路案内サーバ装置は、ナビゲーション装置から送信される始点および終点の情報を含んだ経路探索要求情報に基づき、その始点から終点までの経路を探索し、その探索した経路に含まれるノードのうち、全部または一部のノードを経由ノードとして選出し、その選出した経由ノードそれぞれに対し、その経由ノードから所定の距離以上離れた前記経路上に補足地点を設定し、前記経由ノードの座標情報と前記補足地点の座標情報とを含んだ情報を経路情報としてナビゲーション装置へ送信する。そして、ナビゲーション装置は、受信した経由ノードの座標情報と補足地点の座標情報とに基づき、その経由ノードおよび経由ノードに接続する道路リンクを、自身が有する地図データの識別番号によって同定する。
【００１６】
すなわち、本発明では、ナビゲーション装置は、経由ノードの座標情報だけでなく、その経由ノードを特定しやすくするための補足地点の座標情報も得ることができる。従って、ナビゲーション装置は、経路案内サーバ装置から送信された経路情報に含まれる経由ノードを自身が有する地図データにおけるノードに同定することが容易になる。
【発明の効果】
【００１７】
本発明によれば、情報センタ（経路案内サーバ装置）の地図データとナビゲーション装置の地図データとが異なる場合であっても、情報センタから送信される位置座標ベースで表された経路情報を、ナビゲーション装置が自身の地図データに基づくリンク番号またはノード番号ベースの経路で誤りなく再現することが可能になる。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施形態に係る経路案内システムを含んだシステム全体の構成の例を示した図。
【図２】本発明の実施形態に係る経路案内システムの全体の動作手順の例を示したフローチャート。
【図３】本発明の実施形態に係るサーバ装置における経由地情報の生成処理の処理フローの例を示した図。
【図４】本発明の実施形態に係る経由地の選出および補足地点の設定を説明するための図。
【図５】本発明の実施形態に係るサーバ装置における補足地点の設定処理の処理フローの例を示した図。
【図６】本発明の実施形態に係るサーバ装置からナビゲーション装置に提供される経由地情報のデータフォーマットの例を示した図。
【図７】本発明の実施形態に係るナビゲーション装置における経由地の同定処理および経路探索処理（図２のステップＳ２０８およびＳ２０９）の処理フローの例を示した図。
【図８】本発明の実施形態に係るナビゲーション装置における経路合成処理（図２のステップＳ２１０）の処理フローの例を示した図。
【図９】本発明の実施形態に係るナビゲーション装置における経路合成を説明するための図。
【図１０】本発明の実施形態に係るサーバ装置における経由地情報生成処理の処理フローの第１の変形例を示した図。
【図１１】本発明の実施形態に係るサーバ装置における経由地情報生成処理の処理フローの第１の変形例に係る経由地情報の設定処理において経由地の選出方法を説明するための図。
【図１２】本発明の実施形態に係るサーバ装置における経由地情報の生成処理の処理フローの第３の変形例を示した図。
【図１３】本発明の実施形態に係るサーバ装置における経由地情報の生成処理の処理フローの第３の変形例に係る経由地情報の設定処理において経由地の選出方法を説明するための図。
【図１４】本実施形態に係る経由地情報の生成処理における交通量の分岐分散率について説明するための図。
【発明を実施するための形態】
【００１９】
以下、図面を参照して本発明の実施形態について詳しく説明する。
【００２０】
＜全体構成＞
図１は、本発明の実施形態に係る経路案内システムを含んだシステム全体の構成の例を示した図である。
【００２１】
図１に示すように、経路案内システム７は、道路を走行する車両に搭載されるナビゲーション装置２と、そのナビゲーション装置２に誘導経路情報などを提供する情報センタの経路案内サーバとして機能するサーバ装置１と、を含んで構成される。このとき、サーバ装置１とナビゲーション装置２とは、通信ネットワーク３および基地局４を介して接続され、また、サーバ装置１は、ブロードバンドネットワーク６を介して、外部情報センタ５にも接続されている。
【００２２】
なお、ここでいうブロードバンドネットワーク６は、インターネットなど公衆通信用のネットワークであり、また、通信ネットワーク３は、携帯電話の通信業者などが所有する専用のネットワークである。なお、基地局４とナビゲーション装置２との間は、無線通信区間であり、その区間の通信には携帯電話の電波を用いるものとするが、IEEE802.11シリーズ規格の無線ＬＡＮ（Local Area Network）や、モバイルＷｉＭＡＸなどの電波を用いてもよい。あるいは、ＦＭ多重放送などの放送手段を用いてもよい。
【００２３】
また、外部情報センタ５は、具体的には、交通情報センタ５１、施設情報センタ５２、観光情報センタ５３などを含んで構成される。そして、外部情報センタ５の各情報センタ５１，５２，５３からは、それぞれ、交通事故や道路工事などを考慮した最新の交通渋滞情報、通行料金や施設営業日時などの施設情報、観光地の観光ルートや観光施設の営業時間などを含めた観光情報などの情報が、ブロードバンドネットワーク６を通じてサーバ装置１に提供される。
【００２４】
＜サーバ装置の構成＞
図１に示すように、サーバ装置１は、制御部１０と、補助記憶部１１と、通信部１２と、メモリ部１３と、入出力部１４と、を含んで構成される。
【００２５】
制御部１０は、ナビゲーション装置２からの要求を受けて、後記する補助記憶部１１に記憶された地図データベース１１１を用いて経路を探索する機能を有し、外部情報取得部１１０と、経路要求処理部１２０と、誘導経路探索部１３０と、経由地情報生成部１４０と、経路情報送信部１５０とを含んで構成される。なお、制御部１０の機能は、例えば、図示しないＣＰＵ（Central Processing Unit）が、サーバ装置１の補助記憶部１１に記憶されたプログラムをメモリ部１３に展開し、実行することによって実現される。
【００２６】
外部情報取得部１１０は、外部情報センタ５から交通情報や天候、施設情報などの様々な情報（音声や映像情報を含む）を取得し、補助記憶部１１内の外部情報データベース１１２に記憶する。
【００２７】
経路要求処理部１２０は、ナビゲーション装置２から送信される経路要求情報を受信して、その要求内容を解析し、解析した結果を誘導経路探索部１３０に伝える。このとき、ナビゲーション装置２から取得する経路要求情報とは、経路探索に必要な出発地（あるいは現在位置）、目的地、走行予定日時、探索条件、端末識別番号、利用している地図の位置表現形式やバージョンなどを含む情報である。
【００２８】
そして、その探索条件には、有料道路を優先するか、距離または時間を優先するか、交通状況を考慮するか、などの条件が設定される。また、探索条件で、通行料割引を最大限に利用する経路、通行料割引や燃料消費量、移動時間などを考慮した経済的な経路、ＣＯ２排出量などの環境を考慮する経路などを指定することもできる。
【００２９】
さらには、人気ルートやお勧めルートなど、曖昧な条件を探索条件に含んでもよい。その場合は、経路要求処理部１２０は、曖昧な探索条件を具体的な探索条件に変換する。例えば、経路要求処理部１２０は、探索条件が「人気ルート」であれば、「走行頻度の高い道路からなる経路」に、また、「お勧めルート」であれば、「ユーザの注目度の高い地点を経由する経路」に変換する、というように情報検索可能な表現の条件に変換し、その表現文から検索キーを生成する。そして、生成した検索キーに一致する情報が外部情報データベース１１２に存在しない場合、あるいは、最新情報を必要とする場合、その検索キーを用いて外部情報取得部１１０が必要な情報を外部情報センタ５から収集し、収集した情報を外部情報データベース１１２に記憶する。
【００３０】
なお、外部情報取得部１１０は、交通情報や施設情報などの比較的に短い期間で変動する情報で、経路探索条件として頻繁に利用される情報については、所定の時間ごとに定期的に外部情報センタ５から収集するようにして外部情報データベース１１２に記憶し、常に最新情報が保たれるようにする。
【００３１】
誘導経路探索部１３０は、経路要求処理部１２０で解析した要求を受け付け、経路探索に必要な情報を地図データベース１１１および外部情報データベース１１２から取得し、出発地から目的地までの誘導経路を計算する。このとき、経路探索のアルゴリズムとしては、例えば、出発地から目的地に向かって最小コストとなる経路を求めるダイクストラ法が用いられるのが一般的であるが、他の数学的手法を用いて計算してもよい。
【００３２】
経由地情報生成部１４０は、誘導経路探索部１３０が計算した誘導経路に含まれる交差点のノードから後記する手順に従って経由ノードを選出するとともに、前記誘導経路に含まれ、かつ、前記選出した各経由ノードを始点とする各リンク上に、そのそれぞれの経由ノードを特定し易くするための補足地点を設定する。そして、経由地情報生成部１４０は、前記経由ノードとその補足地点の情報に基づき、経由ノード情報（経由ノードの座標情報や、ノード種別、交差点名称などの属性情報）、補足地点情報（補足地点の座標情報、分岐方向など）、前記補足地点が含まれるリンクの属性情報（リンク種別、道路種別、規制情報など）を含んだ経由地情報を生成する。
【００３３】
経路情報送信部１５０は、経由地情報生成部１４０によって生成された経由地情報に基づき、所定の配信用データ形式に従った経路情報を生成し、通信部１２および通信ネットワーク３を介して、ナビゲーション装置２に送信する。
【００３４】
次に、補助記憶部１１は、ハードディスク装置やフラッシュメモリなどの記憶装置によって構成され、地図データベース１１１、外部情報データベース１１２などの情報を記憶する。
【００３５】
ここで、地図データベース１１１は、経路案内に必要な最新の道路データを含む地図データを記憶する。その場合、地図データ更新に伴う複数バージョンの地図データを、同時に記憶していてもよい。また、外部情報データベース１１２は、外部情報取得部１１０が、通信部１２およびブロードバンドネットワーク６を介して、外部情報センタ５から取得した交通情報、施設情報、観光情報などの情報を記憶する。
【００３６】
通信部１２は、ナビゲーション装置２から通信ネットワーク３を介して送信された経路要求情報を受信するとともに、外部情報センタ５からブロードバンドネットワーク６を介して送信された情報を受信する。また、通信部１２は、経路情報送信部１５０が生成した経路情報をナビゲーション装置２へ送信する。
【００３７】
メモリ部１３は、ＲＡＭ（Random Access Memory）などによって構成され、制御部１０の図示しないＣＰＵが実行するためのプログラムを記憶するとともに、そのプログラムに従って、ＣＰＵが地図データベース１１１などから読み出した地図情報や、通信部１２により取得した情報などを一時的に記憶する。
【００３８】
入出力部１４は、キーボード、マウス、タッチパネルなどの入力装置や、液晶ディスプレイなどの表示装置を含んで構成され、入力装置を介して外部からのサーバ装置１への指示入力を受け付けるとともに、制御部１０の処理によって得られる各種処理結果を表示装置などに出力する。
【００３９】
＜ナビゲーション装置の構成＞
図１に示すように、ナビゲーション装置２は、経路案内制御部２０と、補助記憶部２１と、通信部２２と、メモリ部２３と、入出力部２４と、表示部２５と、衛星電波受信部２６とを含んで構成される。
【００４０】
経路案内制御部２０は、通信部２２を介してサーバ装置１から送信された経由地情報を含んだ経路情報に基づき、その経由地情報によって指定される経由地を経由する経路を、誘導経路として再現し、経路案内を行う。そして、その経路案内制御部２０は、位置情報取得部２１０と、経路情報取得部２２０と、探索条件設定部２３０と、経路要求送信部２４０と、経由地同定部２５０と、経路探索部２６０、経路合成部２７０、経路案内部２８０と、を含んで構成される。なお、経路案内制御部２０の機能は、例えば、図示しないＣＰＵが、ナビゲーション装置２の補助記憶部２１に記憶されたプログラムをメモリ部２３に展開し、実行することによって実現される。
【００４１】
位置情報取得部２１０は、衛星電波受信部２６が複数のＧＰＳ（Global Positioning System）衛星から受信した情報を取得して、ナビゲーション装置２の現在位置（自車位置）を算出する。なお、現在位置の算出に当たっては、車両の方位センサや速度センサなどから得られるデータを用いて、前記ＧＰＳ衛星から受信した情報に基づき算出した現在位置を補正するようにしてもよい。
【００４２】
探索条件設定部２３０は、入出力部２４を介して、経路案内に必要な目的地および探索条件（経路探索するとき、経路の距離または所要時間のいずれを優先するか、有料道路を優先するか、交通状況を考慮するか、費用を考慮するか、環境を考慮するかなどの条件）のデータを設定する。
【００４３】
経路要求送信部２４０は、位置情報取得部２１０が算出した現在位置、および、探索条件設定部２３０により設定された目的地および探索条件を含む経路要求情報を生成し、通信部２２を介してサーバ装置１へ送信する。
【００４４】
経路情報取得部２２０は、前記送信した経路要求情報に応答して、サーバ装置１から送信される経由地情報からなる経路情報を、通信部２２を介して取得するとともに、その経路情報に含まれる誘導経路に関する情報を、補助記憶部２１内に経由地情報２１１として記憶する。
【００４５】
経由地同定部２５０は、経由地情報２１１に記憶された経由地情報を参照し、その経由地情報によって指定される経由地が、地図データベース２１３に格納されている道路データのどの道路リンクまたはノードに相当するかを、全ての経由地について同定する。ここで、経由地情報は、後記するように、複数の経由ノード情報と、それに対応する補足地点情報（座標情報、分岐方向など）、属性情報（ノード種別や交差点名称など）を含んで構成されており、経由地同定部２５０は、各経由ノードと補足地点を始終点とする仮のリンクを構成し、地図データベース２１３の道路リンクに対して、座標、方向、仮のリンクの属性情報（リンク種別、道路種別、規制情報など）などを、リンク単位で照合するマッチング処理を行う。
【００４６】
経路探索部２６０は、サーバ装置１から送信された経路情報（経由地情報２１１）に基づき、前記経由地同定部２５０によって同定された経由地を経由する出発地から目的地までの経路を、前記探索条件設定部２３０にて設定された条件と同じ条件で探索し、探索した経路（経路Ｒ１）の情報を誘導経路情報２１２として記憶する。
【００４７】
また、経路探索部２６０は、サーバ装置１から送信された経路情報（つまり、経路Ｒ１を表す情報）に含まれる出発地および目的地が、それぞれ、衛星電波受信部２６によって得られた現在位置、および、入出力部２４によって指定された最終目的地と異なる場合には、衛星電波受信部２６によって得られた現在位置からサーバ装置１から送信された経路情報に含まれる出発地までの経路（経路Ｒ０）、および、サーバ装置１から送信された経路情報に含まれる目的地から入出力部２４によって指定された最終目的地までの経路（経路Ｒ２）をそれぞれ探索する。
【００４８】
さらに、経路探索部２６０は、経路情報取得部２２０がサーバ装置１から経路情報（経由地情報２１１）を受信していない場合には、入出力部２４を介して入力された目的地および探索条件の情報と、位置情報取得部２１０によって取得した現在位置の位置情報とに基づいて、補助記憶部２１内の地図データベース２１３を参照して、目的地までの誘導経路（経路Ｒ３０）を探索する。
【００４９】
経路合成部２７０は、経路探索部２６０で探索した経路Ｒ０、経路Ｒ１、経路Ｒ２を接続合成した経路を最終的な誘導経路（経路Ｒ３）とし、誘導経路情報２１２に記憶する。
【００５０】
経路案内部２８０は、補助記憶部２１に誘導経路情報２１２として記憶された誘導経路（経路Ｒ３）と、位置情報取得部２１０によって取得された現在位置の位置情報と、に基づいて目的地までの経路案内を行う。また、経路情報取得部２２０がサーバ装置１から経路情報（経由地情報２１１）を受信していない場合には、前記探索した経路Ｒ３０に基づいて経路案内を行う。
【００５１】
次に、補助記憶部２１は、ハードディスク装置やフラッシュメモリなどの記憶装置によって構成され、経由地情報２１１、誘導経路情報２１２、地図データベース２１３などの情報を記憶する。
【００５２】
ここで、経由地情報２１１は、サーバ装置１から送信された経由地情報を含む誘導経路に関する経路情報を、補助記憶部２１に記憶した情報である。また、誘導経路情報２１２は、経由地情報２１１によって指定される経由地を含んで探索された出発地点から目的地までの誘導経路（経路Ｒ３またはＲ３０）の経路情報を、補助記憶部２１に記憶した情報である。
【００５３】
また、地図データベース２１３は、経由地の同定、経路探索、誘導案内に必要な地図データを補助記憶部２１に記憶したものである。このような地図データは、道路のリンクデータやノードデータからなる道路データ、目的地を施設名や電話番号などで絞り込んで検索するための目的地検索用データ、表示部２５に地図背景を描画するための背景描画用データ、交差点の右左折案内や走行レーンの案内などを行うための経路誘導用データなどを含んで構成される。
【００５４】
このとき、道路データのリンクデータは、そのリンクの位置を表す座標情報、リンク同士の接続情報のほかに、リンク長、リンク通過所要時間（リンク旅行時間）などのリンクコスト情報や、そのリンクの属性情報（リンク種別、道路種別、規制情報など）を含んで構成される。また、ノードデータは、ノードの位置情報や属性情報（ノード種別や交差点名称など）を含んで構成される。
【００５５】
通信部２２は、経路要求送信部２４０が生成した経路要求情報を、通信ネットワーク３を介してサーバ装置１へ送信する。また、通信部２２は、サーバ装置１から送信された経路情報を受信し、経路案内制御部２０内の経路情報取得部２２０に引き渡す。
【００５６】
メモリ部２３は、ＲＡＭやフラッシュメモリなどによって構成され、経路案内制御部２０の図示しないＣＰＵが実行するためのプログラムを記憶するとともに、地図データベース２１３を記憶するとともに、前記プログラムの実行に従って、作成される経由地情報２１１や誘導経路情報２１２などのデータを適宜記憶する。
【００５７】
入出力部２４は、例えば、リモコン装置、タッチパネルなどを含んで構成され、外部からのナビゲーション装置２への指示を受け付ける。さらに、入出力部２４は、スピーカを備え、経路案内制御部２０が制御する各種の制御処理に応じて、その処理状況や処理結果の音声案内をそのスピーカを介して出力してもよい。
【００５８】
表示部２５は、液晶ディスプレイなどによって構成され、経路案内制御部２０の制御の下に、経路案内部２８０に組み込まれている所定の処理に従って出力される、自車の現在位置近傍の地図や、目的地までの誘導経路や、交差点における誘導案内情報などを表示する。
【００５９】
衛星電波受信部２６は、ナビゲーション装置２の現在位置を算出するために必要となるＧＰＳ衛星からの電波を受信する。衛星電波受信部２６は、通常、４個のＧＰＳ衛星から送信される位置情報や時刻情報などを受信するとともに、そのそれぞれの受信時刻を取得する。位置情報取得部２１０は、それらの時刻情報などに基づき、各ＧＰＳ衛星までの距離（擬似距離）を求め、その距離情報やＧＰＳ衛星の位置情報に基づき、自車の現在位置を算出する。
【００６０】
＜経路案内システムの動作＞
続いて、図１を参照しつつ、図２に沿って、経路案内システム７の全体の動作手順について、詳しく説明する。図２は、本発明の実施形態に係る経路案内システム７の全体の動作手順の例を示したフローチャートである。
【００６１】
図１を参照して説明したように、サーバ装置１の制御部１０は、指定された出発地から指定された目的地までの経路を誘導経路探索部１３０により探索することができる。また、ナビゲーション装置２の経路案内制御部２０は、現在地または指定された出発地から指定された目的地までの経路を経路探索部２６０により探索することができる。
【００６２】
そこで、経路案内システム７の動作は、まず、その経路探索をサーバ装置１で行うか、または、ナビゲーション装置２で行うか、を決定することから開始される。それは、サーバ装置１によって探索される経路と、ナビゲーション装置２によって探索される経路と、は必ずしも同じにはならないからである。当然ではあるが、サーバ装置１ほうが、ナビゲーション装置２よりも、付加価値の高い経路を探索することができる。
【００６３】
ちなみに、サーバ装置１が保持する地図データベース１１１は、ナビゲーション装置２が保持する地図データベース２１３よりも、情報量が豊富であり、しかも、最新の情報が反映されたものとなっている。例えば、サーバ装置１の地図データベース１１１は、つねに、最新バージョンの地図データに更新され、また、そのリンク旅行時間なども、交通情報センタ５１から得られる最新の道路の渋滞情報などが反映されたものとなっている。それに対し、ナビゲーション装置２の地図データベース２１３は、必ずしも、最新バージョンの地図データではなく、しかも、そのリンク旅行時間にも最新の道路の渋滞情報などが反映されているわけではない。
【００６４】
そこで、ユーザは、まず、ナビゲーション装置２の入出力部２４を介して、出発地、目的地および経路の様々な探索条件（時間優先、距離優先、費用優先、エコ優先、高速道路優先など）を設定する。すなわち、ナビゲーション装置２の経路案内制御部２０は、探索条件設定部２３０の処理により、出発地および目的地を含めた経路の探索条件の設定を促すメッセージを表示部２５の表示装置に表示するとともに、その表示に応答するユーザが入出力部２４を介して入力する情報に基づき、出発地および目的地を含む経路の探索条件を設定する（ステップＳ２０１）。
【００６５】
このとき、その探索条件の中には、経路探索を「サーバ装置１で行うか」あるいは「ナビゲーション装置２で行うか」を選択する条件が含まれている。そこで、ユーザは、そのいずれかを選択するための指示情報を入力する。
【００６６】
次に、経路案内制御部２０は、ユーザが入力する指示情報に基づき、ナビゲーション装置２をサーバ装置１に接続するか否かを判定する（ステップＳ２０２）。すなわち、ユーザが入力する指示情報が「経路探索をサーバ装置１で行う」であった場合、つまり、ナビゲーション装置２をサーバ装置１に接続する場合には（ステップＳ２０２→Ｙｅｓ）、経路案内制御部２０は、出発地（この場合の出発地は、ユーザが指定する出発地、または、車両の現在位置のいずれか）、目的地、探索条件などの情報を含んだ経路要求情報をサーバ装置１に送信する（ステップＳ２０３）。
【００６７】
一方、ユーザが入力する指示情報が「経路探索をナビゲーション装置２で行う」であった場合、つまり、ナビゲーション装置２をサーバ装置１に接続しない場合には（ステップＳ２０２→Ｎｏ）、経路案内制御部２０は、ナビゲーション装置２をサーバ装置１に接続することなく、自身のナビゲーション装置２の補助記憶部２１に記憶されている地図データベース２１３を用いて、目的地までの誘導経路を探索する（ステップＳ２０４）。
【００６８】
次に、ステップＳ２０３の処理により、経路要求情報がサーバ装置１へ送信されると、サーバ装置１の制御部１０は、経路要求処理部１２０の処理により、通信部１２を介して経路要求情報を受信する（ステップＳ１０１）。そして、制御部１０は、誘導経路探索部１３０の処理により、前記の経路要求情報に含まれる出発地（または、車両の現在位置）、目的地、探索条件などによって指定される誘導経路を探索する（ステップＳ１０２）。
【００６９】
ここで、誘導経路の探索においては、制御部１０は、誘導経路の評価指標として、誘導経路の距離、旅行時間、費用（燃料消費量、高速代金、その旅行にかかる人件費など）、ＣＯ２排出量などを設定することができる。また、このとき用いる旅行時間としては、予め地図データベース１１１に記憶された各道路リンクの旅行時間の他に、交通情報センタ５１から取得した現況交通情報や予測交通情報に基づいて計算された各道路リンクの旅行時間を用いることもできる。
【００７０】
そして、ステップＳ１０２の誘導経路の探索処理により、誘導経路の計算に失敗し、指定された探索条件に適った誘導経路を見つけることができなかった場合には（ステップＳ１０３→Ｎｏ）、制御部１０は、経路情報送信部１５０の処理として、経路情報が得られなかったこと（つまり、「経由地情報無し」）を示した情報を、ナビゲーション装置２に送信する（ステップＳ１０４）。
【００７１】
一方、ステップＳ１０２の誘導経路の探索処理により、探索条件に適った誘導経路を見つけることができた場合には（ステップＳ１０３→Ｙｅｓ）、制御部１０は、その誘導経路情報をナビゲーション装置２へ送信することになるが、本実施形態では、誘導経路情報を緯度・経度の座標情報ベースで表すものとし、情報量削減のために、誘導経路を表す経由地の数を削減する。
【００７２】
そこで、制御部１０は、経由地情報生成部１４０の処理により、その誘導経路に含まれるノード（つまり、交差点）の中から経由ノードを選出し、さらに、その選出した経由ノードの特定を容易化するための補足地点を設定し、その経由ノードおよび補足地点の情報に基づき、経由地情報を生成する（ステップＳ１０５）。なお、経由地情報の生成については、別途、図３および図４を用いて、また、経由地情報の構成については、図６を用いて詳細に説明する。
【００７３】
次に、制御部１０は、経路情報送信部１５０の処理により、通信部１２を介して、前記生成した経由地情報をナビゲーション装置２に送信する（ステップＳ１０６）。
【００７４】
続いて、ナビゲーション装置２の経路案内制御部２０は、経路情報取得部２２０の処理により、サーバ装置１から送信された経由地情報を受信し（ステップＳ２０５）、その受信した経由地情報が「経由地情報無し」を示した情報であった場合には（ステップＳ２０６→Ｙｅｓ）、自身のナビゲーション装置２の補助記憶部２１に記憶されている地図データベース２１３を用いて、目的地までの誘導経路を探索する（ステップＳ２０４）。一方、受信した経由地情報が有意な経由地情報であった場合（つまり、「経由地情報あり」の場合）には（ステップＳ２０６→Ｎｏ）、その受信した経由地情報を、補助記憶部２１の経由地情報２１１として記憶しておく（ステップＳ２０７）。
【００７５】
次に、制御部１０は、経由地同定部２５０の処理により、補助記憶部２１の経由地情報２１１および地図データベース２１３を参照し、経由地情報２１１に含まれる経由ノード情報および補足地点情報によって指定される誘導経路の経由ノードを、地図データベース２１３を用いてマップマッチングし、前記経由ノードを地図データベース２１３における道路データのノード番号またはリンク番号に対応付ける経由地の同定処理を実行する（ステップＳ２０８）。なお、経由地同定処理の詳細については、別途、図７を用いて詳しく説明する。
【００７６】
次に、制御部１０は、経路探索部２６０の処理により、前記同定された経由地のノードまたはリンクを出発地側から順に結ぶ経路を探索し（ステップＳ２０９）、その探索した経路（経路Ｒ１）を補助記憶部２１の誘導経路情報２１２に記憶する。また、サーバ装置１から得られた誘導経路（つまり、経路Ｒ１）の出発地および目的地が、ナビゲーション装置２の現在位置および最終目的地と異なる場合には、制御部１０は、さらに、その現在位置から経路Ｒ１の出発地までの経路（経路Ｒ０）と、経路Ｒ１の目的地から最終目的地までの経路（経路Ｒ２）と、を各々探索する。
【００７７】
そして、前記経路探索の結果、複数の誘導経路（経路Ｒ０、経路Ｒ１、経路Ｒ２）が求められていた場合には、制御部１０は、経路合成部２７０の処理により、それらの経路Ｒ０、経路Ｒ１、経路Ｒ２を接続し、全体の誘導経路を生成する経路合成処理を実行する（ステップＳ２１０）。なお、経路合成処理の詳細については、別途、図８および図９を用いて詳しく説明する。
【００７８】
次に、制御部１０は、経路案内部２８０の処理により、ステップＳ２１０あるいはステップ２０４で生成した誘導経路を用い、かつ、位置情報取得部２１０を介して取得した現在位置の位置情報を用いて、自車位置近傍の地図や交差点での進路指示などを表示部２５の表示装置に表示する経路案内処理を実行する（ステップＳ２１１）。さらに、制御部１０は、現在位置が目的地に到着したか否かを判定し（ステップＳ２１２）、目的地に到着していない場合には（ステップＳ２１２→Ｎｏ）、再度、経路案内処理を実行し（ステップＳ２１１）、目的地に到着した場合には（ステップＳ２１２→Ｙｅｓ）、ナビゲーション装置２における全体の処理を終了する。
【００７９】
以上、図２を用いて説明した経路案内システム７では、サーバ装置１が、ナビゲーション装置２から送信される経路要求に応じた誘導経路を探索し、その誘導経路に基づき、経由地情報を生成し、生成した経由地情報をナビゲーション装置２に提供することを想定している。このとき、サーバ装置１の端末装置として、ナビゲーション装置２の代わりに、例えば、自宅や会社などに設置されたパーソナルコンピュータや、個人情報端末としての携帯電話などを用いてもよい。
【００８０】
この場合、パーソナルコンピュータや携帯電話は、自宅や出先から旅行計画を立案するのに便利であり、サーバ装置１から経由地情報を受信するステップ（ステップＳ２０５）、または、経由地を結ぶ誘導経路探索をするステップ（ステップＳ２０９）まで処理することができる。そこで、パーソナルコンピュータや携帯電話は、サーバ装置１から取得した経由地情報、または、経由地情報に基づき探索された誘導経路情報を、例えば、ＵＳＢ（Universal Serial Bus）メモリなどの可搬記憶媒体に記憶させる。そして、その可搬記憶媒体をナビゲーション装置２に接続すれば、パーソナルコンピュータや携帯電話を用いて立案した旅行計画などによって得られた経由地情報、または、その経由地情報に基づき探索された誘導経路情報を、ナビゲーション装置２へ転送することができる。すなわち、ユーザは、パーソナルコンピュータや携帯電話を用いて立案した旅行計画の経路を、ナビゲーション装置２で活用することができる。
【００８１】
次に、図３および図４を参照して、サーバ装置１における経由地情報の生成処理（図２のステップＳ１０５）について、詳細に説明する。ここで、図３は、本発明の実施形態に係るサーバ装置１における経由地情報の生成処理の処理フローの例を示した図である。また、図４は、本発明の実施形態に係る経由地の選出および補足地点の設定を説明するための図である。
【００８２】
図３に示すように、制御部１０は、まず、図２のステップＳ１０２で探索した誘導経路に含まれる交差点ノードを分岐数の多い順にソートし（ステップＳ３０１）、分岐数の多い交差点ノードから順に経由ノードＰiを選出する（ステップＳ３０２）。そして、前記誘導経路に含まれる交差点ノードの全ノードを選出していない場合には（ステップＳ３０３→Ｎｏ）、ステップＳ３０２の経由ノードの選出を繰り返して行う。
【００８３】
一方、全ノードを選出し（ステップＳ３０３→Ｙｅｓ）、選出した経由ノードの数が最大数Ｎを超えると（ステップＳ３０７→Ｙｅｓ）、制御部１０は、選出した経由ノード間の距離（１つ前に選出した経由ノードＰi-1とそのとき選出した経由ノードＰiとの間の距離）が所定値以下の経由ノードＰiを間引き（ステップＳ３０４）、狭いエリアに経由ノードが密集することを防ぐ。ここで、経由ノードの最大数Ｎは、経由地情報をナビゲーション装置２に配信する際の通信負荷（料金や時間）を考慮して設定された値である。
【００８４】
以上のようにして、経由ノードの選出が終了すると（ステップＳ３０４の終了、または、ステップＳ３０７→Ｎｏ）、選出した各経由ノードから経路方向に分岐する道路上の地点を補足地点として設定する（ステップＳ３０５）。なお、補足地点の設定処理については、別途、図５を用いて詳細に説明する。
【００８５】
なお、ここでは、分岐数の多い交差点ノードを優先して経由ノードの選定を行う方法について説明したが、始点Ｓから直線距離あるいは道路に沿って所定距離以上離れた交差点ノードを対象に経由ノードの選定を行うようにしてもよい。これより、ナビゲーション装置２がサーバ装置１に経路を要求している間に車両移動により始点Ｓを通過しても、Ｓ２０９においてサーバ装置１から得られた全ての経由ノードを有効に経路を探索することができる。また、既に通過した経由ノードを再度経由する経路が計算されることを未然に防ぐことができる。前記通過した経由ノードを再度経由する経路が計算されてしまうという問題については、Ｓ２０９において通過した経由ノードを検出し、該経由ノードを除く経由ノードを結ぶ経路を探索する方法をとっても解消可能である。
【００８６】
ここで、図４を参照して、補足地点について説明しておく。図４において、Ｓは始点（出発地）、Ｅは終点（目的地）、実線は誘導経路、破線は誘導経路ではない道路を表し、また、白丸印は、誘導経路上の経由地（始点Ｓおよび終点Ｅを含む）を表している。このとき、網掛けされた丸印Ｐaは、経由地Ｐaに対して設けられた補足地点を表す。
【００８７】
このような補足地点は、ナビゲーション装置２が経由地情報を受信したとき、誘導経路を誤ることなく特定するために付加する情報であり、例えば、図４の例では、経由地Ｐiに補足地点Ｐaを付加することによって、誘導経路に含まれる経路５０１を、誘導経路に含まれない経由地Ｐaから分岐する経路５０２と間違えることなく特定することが可能となる。
【００８８】
再度、図３を参照すると、制御部１０は、前記選出した経由ノードの座標情報および属性情報（ノード属性、交差点名称など）からなる経由ノード情報と、前記設定した補足地点の座標情報からなる補足地点情報と、前記経由ノードから補足地点に向かい、その補足地点を含む道路リンクの属性情報（道路種別、リンク種別、レーン数、幅員など）と、により経由地情報を生成する（ステップＳ３０６）。なお、経由地情報の構成については、別途、図６を用いて詳細に説明する。
【００８９】
次に、図５を参照（適宜、図４も参照）して、サーバ装置１における補足地点の設定処理（図３のステップＳ３０５）について、詳細に説明する。ここで、図５は、本発明の実施形態に係るサーバ装置１における補足地点の設定処理の処理フローの例を示した図である。
【００９０】
制御部１０は、補足地点の設定の処理を開始すると、それまでに選出しておいた経由ノードＰiを誘導経路に沿って順に選択し（ステップＳ４００）、それ以降の処理により、経由ノードＰi毎に補足地点を設定する。
【００９１】
制御部１０は、まず、経由ノードＰiから所定の距離Ｌ以上離れた経路上の形状補間点を経由ノードＰiの補足地点候補Ｐa’として選択する（ステップＳ４０１）。なお、形状補間点は、地図データベース１１１の地図データにおいて、道路リンクの形状を表現するために設けられた座標情報（緯度・経度情報）を有する道路リンク上の点である。
【００９２】
制御部１０は、次に、地図データベース１１１を参照し、補足地点候補Ｐa’の近傍に設定した所定の大きさのエリアＡ内（図４で、破線の矩形で囲った部分）に誘導経路以外の道路が存在するか否かを判定し（ステップＳ４０２）、誘導経路以外の道路が存在しない場合には（ステップＳ４０２→Ｎｏ）、補足地点候補Ｐa’を当該経由ノードＰiの補足地点Ｐaとして確定させる（ステップＳ４１０）。
【００９３】
一方、前記エリアＡ内に誘導経路以外の道路が存在する場合には（ステップＳ４０２→Ｙｅｓ）、制御部１０は、そのエリアＡ内の道路の１つを選択し、選択した道路の形状補間点と誘導経路上の補足地点候補Ｐa’との直線距離を計算し、Ｐa’に最も近い形状補間点Ｐb（図４参照）を選択する（ステップＳ４０３）。
【００９４】
次に、制御部１０は、経由ノードＰiと形状補間点Ｐbとを結ぶ直線距離ｄを計算し（ステップＳ４０４）、その直線距離ｄが所定の距離Ｌよりも短い場合には（ステップＳ４０５→Ｙｅｓ）、誘導経路上に次の形状補間点が存在するか否かを判定し（ステップＳ４０７）、形状補間点が存在すれば（ステップＳ４０７→Ｙｅｓ）、その形状補間点を新たに補足地点候補Ｐa’とし（ステップＳ４０８）、ステップＳ４０２へ戻り、ステップＳ４０２以降の処理を繰り返して実行する。また、次の形状補間点が存在しない場合には（ステップＳ４０７→Ｎｏ）、誘導経路上の次のノードを新たに補足地点候補Ｐa’とし（ステップＳ４０９）、ステップＳ４０２へ戻り、ステップ４０２以降の処理を繰り返して実行する。
【００９５】
また、ステップＳ４０５において、直線距離ｄが所定の距離Ｌ以上である場合には（ステップＳ４０５→Ｎｏ）、制御部１０は、エリアＡに存在する全ての道路の選択が終了したか否かを判定し（ステップＳ４０６）、その選択が終了していない場合には（ステップＳ４０６→Ｎｏ）、ステップＳ４０３へ戻り、ステップＳ４０３以降の処理を繰り返して実行する。
【００９６】
また、ステップＳ４０６において、エリアＡに存在する全ての道路の選択が終了した場合には（ステップＳ４０６→Ｙｅｓ）、補足地点候補Ｐa’を当該経由ノードＰiの補足地点Ｐaとして確定させる（ステップＳ４１０）。
【００９７】
次に、制御部１０は、誘導経路上の全ての経由ノードＰiについて補足地点Ｐaを設定したか否かを判定し（ステップＳ４１１）、全ての経由ノードＰiについての設定が終了していない場合には（ステップＳ４１１→Ｎｏ）、ステップＳ４００へ戻り、ステップＳ４００以降の処理を繰り返して実行する。また、全ての経由ノードＰiについての設定が終了している場合には（ステップＳ４１１→Ｙｅｓ）、この補足地点設定処理を終了する。
【００９８】
以上のようにして、各経由ノードＰiの補足地点Ｐaは、それぞれの周辺の道路と密接していない地点に設定される。従って、サーバ装置１で設定された補足地点の座標値が、ナビゲーション装置２側の地図データベース２１３に記憶されている道路データの座標値と若干ずれたとしても、周辺道路と離れた位置、つまり、道路が密集していない位置に補足地点Ｐaが設定されているので、ナビゲーション装置２では、サーバ装置１から送信された誘導経路の経由ノードＰiの位置を、誘導経路とは異なる道路リンクに誤認識する可能性は極めて低くなる。
【００９９】
図６は、本発明の実施形態に係るサーバ装置１からナビゲーション装置２に提供される経由地情報のデータフォーマットの例を示した図である。図６に示すように、経由地情報は、経由ノード数、経由ノード座標、補足地点座標、属性情報を含んで構成される。
【０１００】
ここで、経由ノード座標および補足地点座標における座標値には、メーカやバーションなどが異なる地図データ間で共通に扱うことが可能な緯度・経度の値を用いるが、地図座標系の変換が可能な場合は、正規化座標（メッシュ座標、Ｘ座標、Ｙ座標）を用いても構わない。
【０１０１】
属性情報は、経由ノードの種別（交差点、料金所、ジャンクション、サービスエリアやパーキングエリアへの出入り口など）、経由ノードの交差点名称、経由ノードから補足地点への分岐方向θ（図４に示すように、真北を基準に時計回りの角度）、経由ノードから補足地点に向かう道路の道路種別（国道、県道など）、同道路のリンク種別（交差点内、トンネル、高架など）、次の経由ノードまでの距離など、経由ノードや、誘導経路の目的地方向に沿って経由ノードに接続されたリンクを特定する情報を含む。また、図示をしていないが、通行料金の割引サービスが有効な経路の場合には有効なサービスと割引前後の料金情報、環境考慮した経路の場合にはＣＯ２の削減量といった環境に関わる情報、他に消費燃料情報や経路沿いの休憩箇所や観光スポットなど、経路に関わる様々な情報を含める。
【０１０２】
なお、属性情報には、前記情報の他に地図データベース１１１に含まれているノードおよび道路リンクに関わる他の属性情報（レーン数や幅員など）を追加してもよいが、ナビゲーション装置２に経由地情報を提供する際の通信負荷を増加させるので、必要最小限に留めることが望ましい。
【０１０３】
図７は、本発明の実施形態に係るナビゲーション装置２における経由地の同定処理および経路探索処理（図２のステップＳ２０８およびＳ２０９）の処理フローの例を示した図である。
【０１０４】
ナビゲーション装置２の経路案内制御部２０は、まず、補助記憶部２１の経由地情報２１１を参照して、経由地順に、経由ノード情報、補足地点情報、属性情報を読み込み（ステップＳ７０１）、これらの情報によって表される経由ノードと補足地点とを結ぶ仮のリンクを構成する（ステップＳ７０２）。
【０１０５】
次に、経路案内制御部２０は、この仮のリンクの属性情報（座標、道路種別およびリンク種別）を用いて、地図データベース２１３に記憶されている道路データから、この仮のリンクに対応する候補道路を検索する（ステップＳ７０３）。
【０１０６】
そして、ステップＳ７０３での検索の結果、候補道路が見つかった場合（ステップＳ７０４→Ｙｅｓ）、経路案内制御部２０は、その候補道路に含まれる交差点ノードの中から、経由ノードの座標および属性（ノード種別や名称）に該当するノードを検索する（ステップＳ７０５）。
【０１０７】
そして、ステップＳ７０５の検索の結果、経路案内制御部２０は、経由ノードの座標値およびノード属性情報に該当するノードがあった場合には（ステップＳ７０６→Ｙｅｓ）、その該当したノードの地図データベース２１３で管理されているノード番号を、前記経由ノードに対応付ける（ステップＳ７０７）。
【０１０８】
さらに、経路案内制御部２０は、前記ノード番号のノードから、前記仮のリンクの方向または属性情報に含まれる分岐方向θに分岐する道路リンクを検索する（ステップＳ７０８）。そして、その検索の結果、該当する道路リンクがあった場合には（ステップＳ７０９→Ｙｅｓ）、その該当した道路リンクの地図データベース２１３で管理されているリンク番号を、前記仮のリンクに対応付け（ステップＳ７１０）、前記該当リンクを、地図データベース２１３の道路データに基づく誘導経路の経由リンクとする。
【０１０９】
次に、経路案内制御部２０は、全ての経由ノードの同定の処理を終了したか否かを判定し（ステップＳ７１１）、終了していない場合には（ステップＳ７１１→Ｎｏ）、ステップＳ７０１へ戻り、ステップＳ７０１以降の処理を繰り返して実行する。
【０１１０】
以上のようにして、経路案内制御部２０は、経由地情報に含まれる各経由ノードに対して、各経由ノードに対応する地図データベース２１３上のノード番号を対応付け、さらに、誘導経路に沿って、その経由ノードから目的地方向に分岐する道路リンク（以下、経由リンクと呼ぶ）のリンク番号を対応付けることができる。
【０１１１】
なお、ノード番号またはリンク番号を対応付ける過程で、地図データベース２１３上に該当する候補道路が見つからなかった場合（ステップＳ７０４→Ｎｏ）、該当するノードが見つからなかった場合（ステップＳ７０６→Ｎｏ）、該当するリンクが見つからなかった場合には（ステップＳ７０９→Ｎｏ）、当該経由ノードに対応する道路が存在しなかったと判定し、ノード番号またはリンク番号の対応付けを省略する。
【０１１２】
また、ステップＳ７０６において該当するノードが見つからなかった場合には（ステップＳ７０６→Ｎｏ）、経路案内制御部２０は、さらに、当該経由ノードが誘導経路の始終点として設定されたノードであるか否かを判定する（ステップＳ７１５）。そして、その判定の結果、始終点（図４における始点Ｓおよび終点Ｅ）のいずれかに設定されたノードであった場合には（ステップＳ７１５→Ｙｅｓ）、それぞれ、１つ次または１つ前の経由ノードを始終点ノードに設定する（ステップＳ７１６）。すなわち、当該ノードが始点であれば１つ次の経由ノードは始点とし、終点であれば１つ前の経由ノードを終点とする。なお、始終点情報は、経由ノードの属性情報として与えられているものとする。
【０１１３】
このように、始終点をナビゲーション装置２の地図データベース２１３で同定できなかった場合に、始終点を設定し直すことによって、始終点が同定できなかったことによる経路の再現エラーを防止することができる。従って、ナビゲーション装置２では、自身が有する地図データベース２１３を用いて、サーバ装置１が提供した誘導経路を極力利用できるようになる。
【０１１４】
次に、経路案内制御部２０は、全ての経由ノードの同定の処理を終了した場合には（ステップＳ７１１→Ｙｅｓ）、その同定の処理で同定した経由リンクを経由する始点Ｓから終点Ｅまでの経路を探索し（ステップＳ７１２）、地図データベース２１３に基づくリンク番号で表した誘導経路を得る。このようにして得た誘導経路を、以下、「再現した誘導経路」、または、単に、「再現経路」と呼ぶ。
【０１１５】
次に、経路案内制御部２０は、再現経路上の経由ノード間距離と、サーバ装置１から送信された経由地情報に含まれるに含まれる経由ノード間距離（図６参照：属性情報の次の経由ノードまでの距離）とを比較し、そのいずれかが所定の値以上に乖離している場合は（ステップＳ７１３→Ｙｅｓ）、経路が正確に再現できていない可能性のあることを利用者に提示するために経路再現エラーを出力する（ステップＳ７１４）。
【０１１６】
図８は、本発明の実施形態に係るナビゲーション装置２における経路合成処理（図２のステップＳ２１０）の処理フローの例を示した図である。また、図９は、その経路合成を説明するための図である。
【０１１７】
図９において、実線で示された経路Ｒ１は、サーバ装置１から送信された経由地情報に基づいてナビゲーション装置２の経路探索部２６０により探索された、始点Ｓから終点Ｅに向かう誘導経路の再現経路である。また、地点Ｏは、衛星電波受信部２６によって受信された情報に基づき得られた車両の現在位置、Ｄは入出力部２４を介してユーザが設定した目的地を示す。また、破線で示された経路Ｒ０は、現在位置Ｏから始点Ｓに向かう経路、経路Ｒ２は、終点Ｅから目的地Ｄに向かう経路を表している。
【０１１８】
まず、経路案内制御部２０は、車両の現在位置Ｏと経路Ｒ１の始点Ｓの座標情報を参照し（ステップＳ８０１）、両者の座標情報が異なる場合には（ステップＳ８０２→Ｙｅｓ）、現在位置Ｏを始点、経路Ｒ１の始点Ｓを終点に設定し（ステップＳ８０３）、経路探索部２６０により現在地Ｏから始点Ｓに向かう経路Ｒ０を探索する（ステップＳ８０４）。なお、両者の座標情報が同じである場合は（ステップＳ８０２→Ｎｏ）、ステップＳ８０３およびステップＳ８０４を実行する必要はない。
【０１１９】
次に、経路案内制御部２０は、経路Ｒ１の終点Ｅと目的地Ｄの位置が異なる場合は（ステップＳ８０５→Ｙｅｓ）、終点Ｅを始点、目的地Ｄを終点に設定し（ステップＳ８０６）、経路探索部２６０により終点Ｅから目的地Ｄに向かう経路Ｒ２を探索する（ステップＳ８０７）。なお、両者の座標情報が同じである場合は（ステップＳ８０５→Ｎｏ）、ステップＳ８０６およびステップＳ８０７を実行する必要はない。
【０１２０】
さらに、経路案内制御部２０は、前記探索した経路Ｒ０、Ｒ１、Ｒ２の複数経路を各始終点で接続し、出発地Ｏから目的地Ｄへ向かう誘導経路を生成する（ステップＳ８０８）。このように、複数経路を接続して１つの経路とすることにより、出発地や目的地でスピーカなどを介して出力される「経路案内を開始します」、「目的地に到着します」などの音声メッセージなどが経路途中で出力されることを防ぎ、経路Ｒ０、Ｒ１、Ｒ２の接続点でも、交差点手前で通過予定の交差点までの距離、右左折方向、案内交差点拡大図などの案内情報をユーザに提示することが可能となる。
【０１２１】
以上のように、本実施形態では、経路案内制御部２０がサーバ装置１に対して誘導経路の探索要求をするときの出発地（始点Ｓ）および目的地（終点Ｅ）と、車両走行時に得られた、または、設定された現在位置（出発地Ｏ）および目的地（最終の目的地Ｄ）と、が相違することは、経路案内システム７の動作において前提とされている。その前提に基づき、経路案内制御部２０には、経路合成部２７０が設けられ、その経路合成部２７０の処理により、経路Ｒ０、Ｒ１、Ｒ２をつなぎ合わせて１つの誘導経路にすることができる。
【０１２２】
この経路合成部２７０の機能は、ナビゲーション装置２を利用するユーザにとって好都合である。例えば、横浜から長野まで走行する場合、サーバ装置１に対しては、始点Ｓおよび終点Ｅとして、それぞれ横浜および長野の主要な交差点を設定し、経路Ｒ１を得ることができ、その経路は、通常、幹線道路であり、渋滞などの影響を受けやすい。従って、その経路Ｒ１をサーバ装置１で探索する意義が認められる。
【０１２３】
一方、現在地Ｏから始点Ｓまでの経路Ｒ０や終点Ｅから目的地Ｄまでの経路Ｒ２は、幹線道路から外れた市街地の細い街路であったり、地方の山道であったりする。そのような場合、サーバ装置１の地図データベース１１１であっても、ナビゲーション装置２の地図データベース２１３であっても、その地図データは、現実の道路状況を十分に反映し得ていないことが多い。従って、例えば、横浜の主要な交差点に到達するまでの道路や、長野の主要な交差点から最終目的地に到るまでの道路では、車両は、地図にない道路など誘導経路から外れて走行することが多くなる。また、そのような道路事情では、ナビゲーション装置２は、サーバ装置１から送信された経路を正しく再現することもできなくなる。
【０１２４】
すなわち、現在位置Ｏから最終目的地Ｄまでを通した誘導経路をサーバ装置１で探索する意義は薄く、本実施形態のように、経路Ｒ０や経路Ｒ２は、ナビゲーション装置２で探索するほうがより合理的といえる。しかも、本実施形態の場合、経路Ｒ０、Ｒ１、Ｒ２は、１本の誘導経路として合成されるので、ユーザにとって不都合は生じない。従って、本実施形態に係る経路案内システム７は、ユーザに安定した誘導経路を提供することができるようになる。
【０１２５】
続いて、図１０〜図１４を参照して、本発明の実施形態の変形例について説明する。
【０１２６】
＜実施形態の第１の変形例＞
図１０は、本発明の実施形態に係るサーバ装置１における経由地情報生成処理の処理フローの第１の変形例を示した図である。また、図１１は、その第１の変形例に係る経由地情報の設定処理において経由地の選出方法を説明するための図である。
【０１２７】
図１１において、太い破線で示された誘導経路１１０１は、サーバ装置１の誘導経路探索部１３０により探索された始点Ｓから終点Ｅまでの誘導経路を示す。また、細い破線で示された経路１１０２，１１０３は、それぞれ、始点Ｓから終点Ｅに向かう第２の経路、第３の経路を示す。ノードＰi1およびノードＰi2は、誘導経路１１０１の経由ノード、地点Ｐa1および地点Ｐa2は、それぞれ、ノードＰi1およびノードＰi2を補足する補足地点を示す。
【０１２８】
また、区間Ｚは、誘導経路の経路情報をナビゲーション装置２で再現するとき、渋滞や規制発生などの通行するのが困難または通行するのに異常に時間がかかる区間であり、ユーザとしては必ず避けるようにしたい回避区間を示している。また、Ｐzは、区間Ｚ（以下、回避区間Ｚと記載）の進入側に存在する交差点のノードである。
【０１２９】
図１０に示すように、サーバ装置１の制御部１０は、誘導経路１１０１の始点Ｓから終点Ｅに向かって、道路リンクを順に取得し、その周辺道路の交通状況を参照する（ステップＳ１００１）。なお、サーバ装置１は、交通情報センタ５１などから、予め渋滞情報や通行規制などの交通状況のデータを取得し、外部情報データベース１１２などに記憶しておくものとする。
【０１３０】
そして、制御部１０は、その周辺道路に渋滞や規制などのために回避すべき回避区間Ｚが存在するか否かを判定し（ステップＳ１００２）、回避区間Ｚが存在した場合は（ステップＳ１００２→Ｙｅｓ）、回避区間Ｚの進入側ノードＰzに接続する誘導経路１１０１上のノードＰi1およびＰi2を経由ノードとして選出する（ステップＳ１００３）。さらに、制御部１０は、図５で説明した補足地点の設定フローに従って、経由ノードＰi1および経由ノードＰi2をそれぞれ補足する補足地点Ｐa1およびＰa2を設定する（ステップＳ１００４）。また、回避区間Ｚが存在しない場合は（ステップＳ１００２→Ｎｏ）、制御部１０は、ステップＳ１００３およびステップＳ１００４の実行を省略する。
【０１３１】
次に、制御部１０は、以上の回避区間Ｚの存在の判定を目的地（終点Ｅ）に到達するまで繰り返した否かを判定し（ステップＳ１００５）、目的地に到達するまで繰り返していない場合には（ステップＳ１００５→Ｎｏ）、ステップＳ１００１へ戻って、ステップＳ１００１以下の処理を繰り返して実行する。また、目的地に到達するまで繰り返した場合には（ステップＳ１００５→Ｙｅｓ）、この経由地情報生成処理を終了する。
【０１３２】
以上のようにして、回避区間Ｚを回避可能な経由ノードＰi1，Ｐi2を選出し、その経由ノードＰi1，Ｐi2に対して補足地点Ｐa1，Ｐa2を設定することができる。従って、ナビゲーション装置２の経路案内制御部２０は、このような経由地情報を受信した場合には、経路１１０２，１１０３のように回避区間Ｚを通過する経路を再現することはなく、サーバ装置１が探索した誘導経路１１０１を正しく再現することができるようになる。
【０１３３】
＜実施形態の第２の変形例＞
以上に示した実施形態の変形例では、回避区間Ｚを回避するように経由ノードを設定したが、回避区間Ｚの進入側ノードＰzを回避ノード、回避区間Ｚ近傍に回避地点Ｐazを設定し、回避ノードＰzと回避地点Ｐazを、図６で説明した経由地情報に含めてナビゲーション装置２に提供するようにしてもよい。
【０１３４】
この場合、ナビゲーション装置２の経由地同定処理（図７参照）において、経路案内制御部２０は、経由リンクの同定処理と同様に、回避区間Ｚを含む道路リンク（地図データベース２１３の道路データにおける道路リンク）を検出する。そして、次に実行する経路探索処理において、前記検出した回避区間Ｚを含む道路リンクを回避するように、回避区間Ｚに対応する道路リンクのコストを最大に設定し、始点Ｓから終点Ｅまでの経路を探索する。このようにすれば、回避区間Ｚが誘導経路に含まれることはないので、回避区間Ｚを回避した誘導経路１１０１を再現することができる。
【０１３５】
＜実施形態の第３の変形例＞
図１２は、本発明の実施形態に係るサーバ装置１における経由地情報の生成処理の処理フローの第３の変形例を示した図である。また、図１３は、その第３の変形例に係る経由地情報の設定処理において経由地の選出方法を説明するための図である。
【０１３６】
図１３において、地点Ｏは車両の現在位置、地点Ｄは最終の目的地、地点Ｓおよび地点Ｅは、サーバ装置１に経路探索を要求するときの始点および終点である。ここでは、地点Ｓおよび地点Ｅは、高速道路の入口ＩＣ（インターチェンジ）および出口ＩＣであるとする。また、その高速道路の途中には、料金体系などが変わる地点Ｐiがあるとし、例えば、入口ＩＣから地点ＰiのＩＣまでは大幅な割引料金が適用されているとする。
【０１３７】
このような場合には、ユーザは、入口ＩＣから地点ＰiのＩＣまで高速道路を利用し、地点ＰiのＩＣで高速道路を出ることを考える。そこで、本実施形態の変形例では、このような通行料金割引に関係するノードが存在した場合には、そのノードを必ず経由地に設定するようにする。そうすれば、ナビゲーション装置２では、その通行料金割引に関係するノードを経由する誘導経路を誤りなく再現することができる。従って、ユーザは、車両が地点ＰiのＩＣへ到達したとき、そのＩＣから一般道へ降りることもできる。
【０１３８】
以下、通行料金割引に関係するノードを経由地とする場合の経由地情報の生成処理について、図１２を参照して説明する。
【０１３９】
サーバ装置１の制御部１０は、探索した誘導経路（図１３で、実線で示した地点Ｓから地点Ｅまでの誘導経路１３００）に関係する有料道路の通行料金情報を参照し（ステップＳ１２０１）、誘導経路１３００に含まれるノードに通行料金体系が変わるノードが存在するか否かを判定し（ステップＳ１２０２）、通行料金体系が変わるノードが存在した場合には（ステップ１２０２→Ｙｅｓ）、そのノードを経由ノードＰiとして選出する（ステップＳ１２０３）。なお、制御部１０は、施設情報センタ５２などから有料道路の通行料金情報を予め取得しておき、外部情報データベース１１２などに記憶しておくものとする。
【０１４０】
次に、制御部１０は、図５で説明した補足地点の設定フローに従って、経由ノードＰiに対する補足地点Ｐa（図示せず）を設定する（ステップＳ１２０４）。なお、通行料金が変わるノードが存在しない場合には（ステップ１２０２→Ｎｏ）、制御部１０は、ステップＳ１２０３およびステップＳ１２０４の実行を省略する。
【０１４１】
次に、制御部１０は、以上のような処理を目的地（地点Ｅ）に到達するまで繰り返したか否かを判定し（ステップＳ１２０５）、目的地に到達するまで繰り返していない場合には（ステップＳ１２０５→Ｎｏ）、ステップＳ１２０１へ戻って、ステップＳ１２０１以下の処理を繰り返して実行する。また、目的地に到達するまで繰り返した場合には（ステップＳ１１０５→Ｙｅｓ）、この経由地情報生成処理を終了する。
【０１４２】
以上のような場合においては、サーバ装置１からナビゲーション装置２へ送信する経由地情報のノードの属性情報の中に、例えば、通行料金の割引率や適用範囲などの情報を含めておき、表示部２５にその通行料金の割引率などを表示してもよい。
【０１４３】
＜実施形態の第４の変形例＞
先に説明した本発明の実施形態では、図３に示したように、サーバ装置１における経由地情報の生成処理では、経由地ノードをそのノードから分岐する道路リンク数の多い順に選出したが、経由地ノードの選出は、さらに、他の方法に基づき選出してもよい。
【０１４４】
例えば、経由地情報の生成処理では、分岐数の代わりに交通量の分岐分散率を用いてもよい。ここで、交通量の分岐分散率は、誘導経路に沿って当該ノードに進入する交通量が複数のリンクに分岐するとき、交通量が各脱出リンクに平均の交通量に分散して流出するほど大きくなるような値をいう。
【０１４５】
以下、図１４を参照して、交通量の分岐分散率について説明する。図１４は、本実施形態に係る経由地情報の生成処理における交通量の分岐分散率について説明するための図である。図１４において、白丸印Ｐはノードを表し、矢印Ｌinは進入リンクを表し、３つの矢印Ｌ１，Ｌ２，Ｌ３は脱出リンクを表している。
【０１４６】
例えば、ある時間帯においてノードＰへの進入リンクＬinの交通量を１０００、脱出リンクＬ１，Ｌ２，Ｌ３の交通量を各々２００，３００，５００とする。このとき、各脱出リンクＬ１，Ｌ２，Ｌ３に流出する交通量の割合は、Ｌ1において２００÷１０００＝０．２、Ｌ2において３００÷１０００＝０．３、Ｌ3において５００÷１０００＝０．５となる。最大値０．５で各方向における割合の値を正規化すると、Ｌ1方向が０．４、Ｌ2方向が０．６、Ｌ3方向が１となる。Ｌ3方向を除きこれらの平均値を求めると（０．４＋０．６）÷２＝０．５となり、本実施形態においては、この値を、当該時間帯における進入リンクＬinのノードＰの分岐分散率と呼ぶ。
【０１４７】
このようにして求めた値を分岐分散率というのは、前記したように、交通量が各脱出リンクに平均的に分散する場合には、その値が大きくなり、交通量が特定の脱出リンクに集中する場合には、その値が小さくなるからである。ちなみに、図５の例で、各脱出リンクＬ１，Ｌ２，Ｌ３の交通量がすべて同じであった場合には、各脱出リンクＬ１，Ｌ２，Ｌ３の交通量を、その最大値で正規化した場合の値は、いずれも１になるので、その最大値を除いた２つの値の平均値も１となる。一方、進入交通量がある１つの脱出リンクに集中した場合には、他の２つの脱出リンクの交通量は、０となるので、その最大値で正規化した場合の値は、いずれも０になり、その平均値も０となる。すなわち、交通量が各脱出リンクＬ１，Ｌ２，Ｌ３に全く等しく分散したときには、分岐分散率は、最大値の１となり、交通量が各脱出リンクＬ１，Ｌ２，Ｌ３のいずれか１つに集中したときには、分岐分散率は、最小値の０となる。
【０１４８】
なお、このような分岐分散率は、例えば、各ノードの進入リンク毎に、１日２４時間を単位時間で分割した全ての単位時間帯ごとに算出して定められる。なお、各ノードの進入リンク毎ではなく、進入リンク毎に算出された分岐率の平均値を計算し、その平均値を進入リンクに関係のない各ノードの分岐分散率と定めてもよい。
【０１４９】
なお、本実施形態の変形例では、分岐分散率は、分岐数とともにノード情報として地図データベース１１１に予め記憶されているものとする。ただし、制御部１０が、外部情報センタ５から分岐分散率を取得して、地図データベース１１１に記憶するようにしてもよい。また、サーバ装置１の構成要素として、分岐分散率を計算する分岐率算出部を新たに設け、外部情報センタ５から取得した交通情報（交通量を含む）に基づいて分岐分散率を計算するようにしてもよい。さらに、ナビゲーション装置２からの経路要求情報とともに、車両の走行実績データを受信し、その走行実績データを蓄積することによって、分岐分散率を算出してもよい。
【０１５０】
さらに、経由地を選出する他の方法として、探索条件に施設（コンビニエンスストアや飲食店、サービスエリア／パーキングエリアなどの休憩地点）などの立ち寄り地点が指定された場合、経由ノードの分岐先の道路リンクに立ち寄り地点が存在するノードを優先して経由地ノードとして選出するようにしてもよい。この場合、立ち寄り地点は、交差点ノードと限らないため、立ち寄り地点を含む施設の位置を経由ノードの補足地点としてもよい。
【０１５１】
＜その他の実施形態の変形例＞
さらに、先に説明した本発明の実施形態では、図２のステップＳ２０３において、ナビゲーション装置２は、サーバ装置１に対し経路情報の送信を要求しているが、この実施形態の変形例では、経路情報だけでなく交通情報を併せて要求するようにする。その場合には、サーバ装置１は、誘導経路の探索に失敗、つまり、誘導経路が見つからなかったときに（ステップＳ１０３→Ｎｏ）、「経由地情報無し」を示した情報をナビゲーション装置２に送信するとともに（ステップＳ１０４）、関連する地域の渋滞情報などの交通情報を送信する。そうすれば、ナビゲーション装置２は、その交通情報を利用して自身が有する経路探索部２６０の機能により、目的地までの経路を探索することができる。
【０１５２】
また、先に説明した本発明の実施形態では、ナビゲーション装置２がサーバ装置１へ送信する経路要求情報には、ナビゲーション装置２が有する地図データベース２１３の地図データフォーマットの識別情報およびそのバージョン情報を含めるとはしていないが、その情報を経路要求情報に含めてもよい。
【０１５３】
その場合には、サーバ装置１は、その地図データフォーマットの識別情報およびバージョン情報を判定し、地図データベース１１１の中に、その地図データフォーマットと同じフォーマットで同じバージョンの地図データを有していたときには、その同じフォーマットで同じバージョンの地図データを用いて、ナビゲーション装置２から求められた経路探索を行い、その結果としての経由地情報をナビゲーション装置２へ送信する。
【０１５４】
この場合には、ナビゲーション装置２は、自身が有する地図データベース２１３と同じフォーマットで同じバージョンの地図データに基づき作成された経由地情報を取得することになるので、その経由地情報からはほとんど誤りが生じない経路を再現することができる。
【符号の説明】
【０１５５】
１ サーバ装置
２ ナビゲーション装置
３ 通信ネットワーク
４ 基地局
５ 外部情報センタ
６ ブロードバンドネットワーク
７ 経路案内システム
１０ 制御部
１１ 補助記憶部
１２ 通信部
１３ メモリ部
１４ 入出力部
２０ 経路案内制御部
２１ 補助記憶部
２２ 通信部
２３ メモリ部
２４ 入出力部
２５ 表示部
２６ 衛星電波受信部
５１ 交通情報センタ
５２ 施設情報センタ
５３ 観光情報センタ
１１０ 外部情報取得部
１１１ 地図データベース
１１２ 外部情報データベース
１２０ 経路要求処理部
１３０ 誘導経路探索部
１４０ 経由地情報生成部
１５０ 経路情報送信部
２１０ 位置情報取得部
２１１ 経由地情報
２１２ 誘導経路情報
２１３ 地図データベース
２２０ 経路情報取得部
２３０ 探索条件設定部
２４０ 経路要求送信部
２５０ 経由地同定部
２６０ 経路探索部
２７０ 経路合成部
２８０ 経路案内部
【特許請求の範囲】
【請求項１】
経路の始点および終点の情報の入力を受け付けて、その始点および終点の情報を含んだ経路探索要求情報を送信するナビゲーション装置に対し、地図データを有し、その地図データを参照して前記始点から前記終点までの経路を探索し、その探索した経路の経路情報を提供する経路案内サーバ装置であって、
前記探索した前記始点から前記終点までの経路に含まれるノードの全部または一部を経由ノードとして選出し、
前記選出した経由ノードのそれぞれについて、そのそれぞれの経由ノードから所定の距離以上離れた前記経路上の地点を、前記経由ノードの補足地点としてそれぞれ設定し、
前記経由ノードそれぞれの座標情報と、前記経由ノードそれぞれに設定された前記補足地点の座標情報と、を含んだ情報を前記経路情報として、前記ナビゲーション装置へ送信すること
を特徴とする経路案内サーバ装置。
【請求項２】
前記経路案内サーバ装置は、
前記経由ノードを選出する場合には、前記地図データを参照して前記始点から前記終点までの経路に含まれるノードのうち、分岐数の多いノードを優先して選出すること
を特徴とする請求項１に記載の経路案内サーバ装置。
【請求項３】
前記経路案内サーバ装置は、各道路リンクの交通量を表した交通量データを、さらに、有し、
前記経由ノードを選出する場合には、前記地図データおよび前記交通量データを参照して、前記始点から前記終点までの経路に含まれるノードのうち、そのノードへの進入リンクの交通量が脱出リンクに分散する程度の値を示す分岐分散率が大きいノードを優先して選出すること
を特徴とする請求項１に記載の経路案内サーバ装置。
【請求項４】
前記経路案内サーバ装置は、各道路リンクの渋滞および交通規制を含む通行の困難度を表した交通状況データを、さらに、有し、
前記経由ノードを選出する場合には、前記地図データおよび前記交通状況データを参照して、前記始点から前記終点までの経路の周辺の道路リンクを対象に、通行の困難度が高く通行を回避すべき道路リンクである通行回避リンクの有無を検索し、前記通行回避リンクが存在したときには、その通行回避リンクの進入側ノードに他のリンクを介して接続する前記経路上のノードを前記経由ノードとして選出すること
を特徴とする請求項１に記載の経路案内サーバ装置。
【請求項５】
前記経路案内サーバ装置は、各道路リンクの渋滞および交通規制を含む通行の困難度を表した交通状況データを、さらに、有し、
前記経由ノードを選出する場合には、前記地図データおよび前記交通状況データを参照して、前記始点から前記終点までの経路の周辺の道路リンクを対象に、通行の困難度が高く通行を回避すべき道路リンクである通行回避リンクの有無を検索し、前記通行回避リンクが存在したときには、前記通行回避リンクについての位置座標および属性情報を含む情報を、前記経路情報に併せて、前記ナビゲーション装置へ送信すること
を特徴とする請求項１に記載の経路案内サーバ装置。
【請求項６】
前記経路案内サーバ装置は、前記経路案内サーバ装置は、有料道路の通行料金についての通行料金情報を、さらに、有し、
前記経由ノードを選出する場合には、前記通行料金情報を参照して、前記始点から前記終点までの経路に含まれるノードのうち、前記有料道路の通行料金の料金計算体系が変わるノードを前記経由ノードとして選出すること
を特徴とする請求項１に記載の経路案内サーバ装置。
【請求項７】
経路の始点および終点の情報の入力を受け付けて、その始点および終点の情報を含んだ経路探索要求情報を経路案内サーバ装置に送信し、その経路探索要求情報に応答して前記経路案内サーバ装置から送信される、前記始点から前記終点までの経路に含まれる経由ノードのそれぞれの座標情報と、その経由ノードのそれぞれに対応付けて設定された補足地点の座標情報と、を含んで構成された経路情報を受信し、前記受信した経路情報と自身が有する地図データとに基づき探索した経路の経路情報を、表示装置に表示するナビゲーション装置であって、
前記受信した経路情報に含まれる前記経由ノードの座標情報と前記補足地点の座標情報とに基づき、前記経由ノードおよび前記経由ノードに接続する道路リンクを、前記自身が有する地図データの識別番号によって同定し、
前記同定した経由ノードおよび道路リンクを経由する前記始点から前記終点までの経路を、前記自身が有する地図データに基づき探索すること
を特徴とするナビゲーション装置。
【請求項８】
前記ナビゲーション装置は、
前記経路探索要求情報に含まれた前記始点および終点の情報と、前記経路探索要求情報が送信された後、再度受け付けられた始点および終点の情報と、が相違する場合には、さらに、
前記自身が有する地図データに基づき、前記再度受け付けた始点から前記経路探索要求情報に含まれた始点までの第１の経路と、前記経路探索要求情報に含まれた終点から前記再度受け付けた終点までの第２の経路と、をそれぞれ探索し、
前記第１の経路と、前記経路案内サーバ装置から送信された経路情報と前記自身が有する地図データに基づき先に探索済の経路と、前記第２の経路と、をつなぎ合わせた経路の経路情報を、前記表示装置に表示すること
を特徴とする請求項７に記載のナビゲーション装置。
【請求項９】
経路の始点および終点の情報の入力を受け付けて、その始点および終点の情報を含んだ経路探索要求情報を送信するナビゲーション装置と、
地図データを有し、その地図データを参照して前記ナビゲーション装置から送信された前記経路探索要求情報に含まれる前記始点から前記終点までの経路を探索し、その探索した経路の経路情報を前記ナビゲーション装置に提供する経路案内サーバ装置と、
を含んでなる経路案内システムであって、
前記経路案内サーバ装置は、
前記探索した前記始点から前記終点までの経路に含まれるノードの全部または一部を経由ノードとして選出し、
前記選出した経由ノードのそれぞれについて、そのそれぞれの経由ノードから所定の距離以上離れた前記経路上の地点を、前記経由ノードの補足地点としてそれぞれ設定し、
前記経由ノードそれぞれの座標情報と、前記経由ノードそれぞれに設定された前記補足地点の座標情報と、を含んだ情報を前記経路情報として、前記ナビゲーション装置へ送信し、
前記ナビゲーション装置は、
前記経路案内サーバ装置から送信された経路情報に含まれる前記経由ノードの座標情報と前記補足地点の座標情報とに基づき、前記経由ノードおよび前記経由ノードに接続する道路リンクを、前記自身が有する地図データの識別番号によって同定し、
前記同定した経由ノードおよび道路リンクを経由する前記始点から前記終点までの経路を、前記自身が有する地図データに基づき探索し、
前記探索した経路の経路情報を前記表示装置に表示すること
を特徴とする経路案内システム。
【請求項１０】
経路の始点および終点の情報の入力を受け付けて、その始点および終点の情報を含んだ経路探索要求情報を送信するナビゲーション装置と、
地図データを有し、その地図データを参照して前記ナビゲーション装置から送信された前記経路探索要求情報に含まれる前記始点から前記終点までの経路を探索し、その探索した経路の経路情報を前記ナビゲーション装置に提供する経路案内サーバ装置と、
によって行われる経路案内方法であって、
前記経路案内サーバ装置は、
前記探索した前記始点から前記終点までの経路に含まれるノードの全部または一部を経由ノードとして選出し、
前記選出した経由ノードのそれぞれについて、そのそれぞれの経由ノードから所定の距離以上離れた前記経路上の地点を、前記経由ノードの補足地点としてそれぞれ設定し、
前記経由ノードそれぞれの座標情報と、前記経由ノードそれぞれに設定された前記補足地点の座標情報と、を含んだ情報を前記経路情報として、前記ナビゲーション装置へ送信し、
前記ナビゲーション装置は、
前記経路案内サーバ装置から送信された経路情報に含まれる前記経由ノードの座標情報と前記補足地点の座標情報とに基づき、前記経由ノードおよび前記経由ノードに接続する道路リンクを、前記自身が有する地図データの識別番号によって同定し、
前記同定した経由ノードおよび道路リンクを経由する前記始点から前記終点までの経路を、前記自身が有する地図データに基づき探索し、
前記探索した経路の経路情報を前記表示装置に表示すること
を特徴とする経路案内方法。
【請求項１】
経路の始点および終点の情報の入力を受け付けて、その始点および終点の情報を含んだ経路探索要求情報を送信するナビゲーション装置に対し、地図データを有し、その地図データを参照して前記始点から前記終点までの経路を探索し、その探索した経路の経路情報を提供する経路案内サーバ装置であって、
前記探索した前記始点から前記終点までの経路に含まれるノードの全部または一部を経由ノードとして選出し、
前記選出した経由ノードのそれぞれについて、そのそれぞれの経由ノードから所定の距離以上離れた前記経路上の地点を、前記経由ノードの補足地点としてそれぞれ設定し、
前記経由ノードそれぞれの座標情報と、前記経由ノードそれぞれに設定された前記補足地点の座標情報と、を含んだ情報を前記経路情報として、前記ナビゲーション装置へ送信すること
を特徴とする経路案内サーバ装置。
【請求項２】
前記経路案内サーバ装置は、
前記経由ノードを選出する場合には、前記地図データを参照して前記始点から前記終点までの経路に含まれるノードのうち、分岐数の多いノードを優先して選出すること
を特徴とする請求項１に記載の経路案内サーバ装置。
【請求項３】
前記経路案内サーバ装置は、各道路リンクの交通量を表した交通量データを、さらに、有し、
前記経由ノードを選出する場合には、前記地図データおよび前記交通量データを参照して、前記始点から前記終点までの経路に含まれるノードのうち、そのノードへの進入リンクの交通量が脱出リンクに分散する程度の値を示す分岐分散率が大きいノードを優先して選出すること
を特徴とする請求項１に記載の経路案内サーバ装置。
【請求項４】
前記経路案内サーバ装置は、各道路リンクの渋滞および交通規制を含む通行の困難度を表した交通状況データを、さらに、有し、
前記経由ノードを選出する場合には、前記地図データおよび前記交通状況データを参照して、前記始点から前記終点までの経路の周辺の道路リンクを対象に、通行の困難度が高く通行を回避すべき道路リンクである通行回避リンクの有無を検索し、前記通行回避リンクが存在したときには、その通行回避リンクの進入側ノードに他のリンクを介して接続する前記経路上のノードを前記経由ノードとして選出すること
を特徴とする請求項１に記載の経路案内サーバ装置。
【請求項５】
前記経路案内サーバ装置は、各道路リンクの渋滞および交通規制を含む通行の困難度を表した交通状況データを、さらに、有し、
前記経由ノードを選出する場合には、前記地図データおよび前記交通状況データを参照して、前記始点から前記終点までの経路の周辺の道路リンクを対象に、通行の困難度が高く通行を回避すべき道路リンクである通行回避リンクの有無を検索し、前記通行回避リンクが存在したときには、前記通行回避リンクについての位置座標および属性情報を含む情報を、前記経路情報に併せて、前記ナビゲーション装置へ送信すること
を特徴とする請求項１に記載の経路案内サーバ装置。
【請求項６】
前記経路案内サーバ装置は、前記経路案内サーバ装置は、有料道路の通行料金についての通行料金情報を、さらに、有し、
前記経由ノードを選出する場合には、前記通行料金情報を参照して、前記始点から前記終点までの経路に含まれるノードのうち、前記有料道路の通行料金の料金計算体系が変わるノードを前記経由ノードとして選出すること
を特徴とする請求項１に記載の経路案内サーバ装置。
【請求項７】
経路の始点および終点の情報の入力を受け付けて、その始点および終点の情報を含んだ経路探索要求情報を経路案内サーバ装置に送信し、その経路探索要求情報に応答して前記経路案内サーバ装置から送信される、前記始点から前記終点までの経路に含まれる経由ノードのそれぞれの座標情報と、その経由ノードのそれぞれに対応付けて設定された補足地点の座標情報と、を含んで構成された経路情報を受信し、前記受信した経路情報と自身が有する地図データとに基づき探索した経路の経路情報を、表示装置に表示するナビゲーション装置であって、
前記受信した経路情報に含まれる前記経由ノードの座標情報と前記補足地点の座標情報とに基づき、前記経由ノードおよび前記経由ノードに接続する道路リンクを、前記自身が有する地図データの識別番号によって同定し、
前記同定した経由ノードおよび道路リンクを経由する前記始点から前記終点までの経路を、前記自身が有する地図データに基づき探索すること
を特徴とするナビゲーション装置。
【請求項８】
前記ナビゲーション装置は、
前記経路探索要求情報に含まれた前記始点および終点の情報と、前記経路探索要求情報が送信された後、再度受け付けられた始点および終点の情報と、が相違する場合には、さらに、
前記自身が有する地図データに基づき、前記再度受け付けた始点から前記経路探索要求情報に含まれた始点までの第１の経路と、前記経路探索要求情報に含まれた終点から前記再度受け付けた終点までの第２の経路と、をそれぞれ探索し、
前記第１の経路と、前記経路案内サーバ装置から送信された経路情報と前記自身が有する地図データに基づき先に探索済の経路と、前記第２の経路と、をつなぎ合わせた経路の経路情報を、前記表示装置に表示すること
を特徴とする請求項７に記載のナビゲーション装置。
【請求項９】
経路の始点および終点の情報の入力を受け付けて、その始点および終点の情報を含んだ経路探索要求情報を送信するナビゲーション装置と、
地図データを有し、その地図データを参照して前記ナビゲーション装置から送信された前記経路探索要求情報に含まれる前記始点から前記終点までの経路を探索し、その探索した経路の経路情報を前記ナビゲーション装置に提供する経路案内サーバ装置と、
を含んでなる経路案内システムであって、
前記経路案内サーバ装置は、
前記探索した前記始点から前記終点までの経路に含まれるノードの全部または一部を経由ノードとして選出し、
前記選出した経由ノードのそれぞれについて、そのそれぞれの経由ノードから所定の距離以上離れた前記経路上の地点を、前記経由ノードの補足地点としてそれぞれ設定し、
前記経由ノードそれぞれの座標情報と、前記経由ノードそれぞれに設定された前記補足地点の座標情報と、を含んだ情報を前記経路情報として、前記ナビゲーション装置へ送信し、
前記ナビゲーション装置は、
前記経路案内サーバ装置から送信された経路情報に含まれる前記経由ノードの座標情報と前記補足地点の座標情報とに基づき、前記経由ノードおよび前記経由ノードに接続する道路リンクを、前記自身が有する地図データの識別番号によって同定し、
前記同定した経由ノードおよび道路リンクを経由する前記始点から前記終点までの経路を、前記自身が有する地図データに基づき探索し、
前記探索した経路の経路情報を前記表示装置に表示すること
を特徴とする経路案内システム。
【請求項１０】
経路の始点および終点の情報の入力を受け付けて、その始点および終点の情報を含んだ経路探索要求情報を送信するナビゲーション装置と、
地図データを有し、その地図データを参照して前記ナビゲーション装置から送信された前記経路探索要求情報に含まれる前記始点から前記終点までの経路を探索し、その探索した経路の経路情報を前記ナビゲーション装置に提供する経路案内サーバ装置と、
によって行われる経路案内方法であって、
前記経路案内サーバ装置は、
前記探索した前記始点から前記終点までの経路に含まれるノードの全部または一部を経由ノードとして選出し、
前記選出した経由ノードのそれぞれについて、そのそれぞれの経由ノードから所定の距離以上離れた前記経路上の地点を、前記経由ノードの補足地点としてそれぞれ設定し、
前記経由ノードそれぞれの座標情報と、前記経由ノードそれぞれに設定された前記補足地点の座標情報と、を含んだ情報を前記経路情報として、前記ナビゲーション装置へ送信し、
前記ナビゲーション装置は、
前記経路案内サーバ装置から送信された経路情報に含まれる前記経由ノードの座標情報と前記補足地点の座標情報とに基づき、前記経由ノードおよび前記経由ノードに接続する道路リンクを、前記自身が有する地図データの識別番号によって同定し、
前記同定した経由ノードおよび道路リンクを経由する前記始点から前記終点までの経路を、前記自身が有する地図データに基づき探索し、
前記探索した経路の経路情報を前記表示装置に表示すること
を特徴とする経路案内方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１１−１３０１６（Ｐ２０１１−１３０１６Ａ）
【公開日】平成２３年１月２０日（２０１１．１．２０）
【国際特許分類】
【出願番号】特願２００９−１５５６２４（Ｐ２００９−１５５６２４）
【出願日】平成２１年６月３０日（２００９．６．３０）
【出願人】（５０９１８６５７９）日立オートモティブシステムズ株式会社 (2,205)
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
【公開日】平成２３年１月２０日（２０１１．１．２０）
【国際特許分類】
【出願日】平成２１年６月３０日（２００９．６．３０）
【出願人】（５０９１８６５７９）日立オートモティブシステムズ株式会社 (2,205)
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
[ Back to top ]