(57)【特許請求の範囲】
【請求項１】
経路案内サーバ装置との情報交換を行うナビゲーション端末装置であって、
道路リンクデータを含む端末地図データと、
移動体の出発地から目的地までの移動経路を、前記移動体が前記移動経路を移動する際の移動コストに関する所定の探索条件に基づき、前記端末地図データを用いて探索する端末経路探索手段と、
前記出発地、前記目的地および前記所定の探索条件を含む経路素片要求を前記経路案内サーバ装置へ送信する送信手段と、
前記経路素片要求に応じて、前記端末経路探索手段により探索された前記移動経路を含む所定領域内の経路素片を、前記経路案内サーバ装置から受信する受信手段と、
前記経路素片に基づいて、前記移動経路に含まれかつ第１の道路リンク群によって構成される少なくとも一部の区間経路の始終点と同一の始終点を有する他の区間経路を構成する第２の道路リンク群に前記第１の道路リンク群を置き換えることにより、前記移動経路を構成する全ての道路リンクの位置に関する位置参照データと、前記全ての道路リンクの移動コストに関するコストデータとを含む経路データを更新する更新手段とを備え、
前記経路素片は、前記経路案内サーバ装置で探索された前記出発地から前記目的地までの複数の経路に前記所定領域内の複数の道路リンクの各々が含まれた頻度が所定値以上である一部の道路リンクで構成されることを特徴とするナビゲーション端末装置。
【請求項２】
請求項１に記載のナビゲーション端末装置において、
前記受信手段は、前記経路素片要求に応じて、前記経路素片の位置に関する位置参照データと前記経路素片の移動コストに関するコストデータとが含まれる経路素片データを、前記経路素片として前記経路案内サーバ装置から受信し、
前記更新手段は、前記第２の道路リンク群の位置に関する位置参照データと前記第２の道路リンク群の移動コストに関するコストデータとが前記経路素片データに含まれるとき、前記経路素片データに基づいて前記経路データを更新することを特徴とするナビゲーション端末装置。
【請求項３】
請求項２に記載のナビゲーション端末装置において、
前記第２の道路リンク群に含まれる前記経路素片を、前記経路素片データに基づき前記所定領域内で選択する選択手段をさらに備えることを特徴とするナビゲーション端末装置。
【請求項４】
請求項１乃至３のいずれか１項に記載のナビゲーション端末装置において、
前記更新手段により更新された前記経路データに対応する更新された移動経路にしたがって前記移動体を誘導するための誘導情報を生成する誘導情報生成手段をさらに備えることを特徴とするナビゲーション端末装置。
【請求項５】
請求項４に記載のナビゲーション端末装置において、
前記端末地図データは、道路形状の情報と、交差点位置の情報と、車線についての情報と、右左折方向についての情報とを含む付加情報のデータを、前記道路リンクデータに対応付けて含み、
前記誘導情報生成手段は、前記更新された移動経路を構成する道路リンクを前記道路リンクデータに対応付けることにより得られる前記付加情報のデータに基づいて、前記誘導情報を生成することを特徴とするナビゲーション端末装置。
【請求項６】
請求項２に記載のナビゲーション端末装置において、
前記端末経路探索手段により探索された前記移動経路を出力するときは第１の態様で出力し、前記更新手段により更新された前記経路データに対応する更新された移動経路を出力するときは前記第１の態様とは異なる第２の態様で出力する出力手段をさらに備えることを特徴とするナビゲーション端末装置。
【請求項７】
請求項６に記載のナビゲーション端末装置において、
前記出力手段は、前記受信手段による前記経路素片データの受信状態を出力することを特徴とするナビゲーション端末装置。
【請求項８】
請求項７に記載のナビゲーション端末装置において、
前記出力手段は、前記受信手段による前記経路素片データの受信が終了し、かつ前記更新手段による前記経路データの更新が終了すると、前記端末経路探索手段により探索された前記移動経路を前記第１の態様で出力し、かつ前記更新された移動経路を前記第２の態様で出力することを特徴とするナビゲーション端末装置。
【請求項９】
請求項６に記載のナビゲーション端末装置において、
前記更新された移動経路にしたがって前記移動体を誘導するための誘導情報を生成する誘導情報生成手段をさらに備え、
前記出力手段は、前記誘導情報生成手段により前記誘導情報が生成されると、前記端末経路探索手段により探索された前記移動経路を出力せずに、前記更新された移動経路を前記第２の態様で出力することを特徴とするナビゲーション端末装置。
【請求項１０】
請求項１乃至９のいずれか１項に記載のナビゲーション端末装置と、
前記経路案内サーバ装置とを備える経路案内システムであって、
前記経路案内サーバ装置は、
サーバ地図データと、
前記送信手段により送信された前記経路素片要求を受け付ける要求受付手段と、
複数のナビゲーション端末装置のために、前記出発地から前記目的地までの前記複数の経路を、前記所定の探索条件に基づき、前記サーバ地図データを用いて探索するサーバ経路探索手段と、
前記要求受付手段により受け付けられた前記経路素片要求に応じて、前記頻度に関する頻度情報を取得する頻度情報取得手段と、
前記要求受付手段により受け付けられた前記経路素片要求に応じて、前記複数の経路を分割することにより前記経路素片を生成する経路素片生成手段と、
前記経路素片生成手段により生成された前記経路素片を、前記ナビゲーション端末装置の前記受信手段へ配信する配信手段とを有することを特徴とする経路案内システム。
【請求項１１】
請求項１０に記載の経路案内システムにおける経路案内サーバ装置。
【請求項１２】
請求項１１に記載の経路案内サーバ装置において、
前記複数のナビゲーション端末装置のために探索された前記複数の経路の複数の始点および複数の終点は、それぞれ、前記出発地および前記目的地から所定距離以内に位置していることを特徴とする経路案内サーバ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路案内に好適な経路案内システムに関する。
【背景技術】
【０００２】
近年、道路の混雑状況をはじめ様々な情報センタから送信される最新の情報を、放送や通信を介して受信し、その受信した最新情報を考慮した目的地までの適切な経路を車両のドライバに提供するナビゲーション装置の普及が進んでいる。
【０００３】
例えば、交通情報センタからＦＭ多重放送などで提供される渋滞や旅行時間などの最新の交通情報を受信し、その交通情報を考慮した目的地までの最短時間の経路を計算して目的地までの経路を表示装置に表示する機能は、ナビゲーション装置の基本機能として定着している。より早く目的地まで到着可能な経路で、より精度よく到着時刻を予測できるように、自車両の通過予定時刻の予測交通情報を情報センタから取得して、目的地までの最適経路計算に利用するナビゲーション装置も現れている。情報センタで最新の交通情報を反映して計算した最適経路を取得し、目的地までの経路を案内するようにしたナビゲーション装置も商品化されている。
【０００４】
交通情報に限らず、外部の様々なサイト（情報センタ）が有する膨大かつ最新の情報を端末に取り込んでナビゲーション機能を充実させるサービスも存在する。例えば、自宅での旅行計画をサポートするポータルサイトでは、動的に変動する施設や道路の利用料金、施設利用状況、イベント情報などの最新情報を考慮した目的地までの経路情報、出発時間、休憩場所などの情報を提供している。そのようなポータルサイトで計画した旅行情報を通信や可搬の記憶メディアを介してナビゲーション装置に転送し、その情報をナビゲーション装置における目的地までの経路の誘導案内にも利用できるようにしたサービスも存在する。
【０００５】
このようなサービスにおいて、情報センタからナビゲーション機能を有する端末装置に対して対象道路区間と事象を提供する技術には、例えば特開２００２−２２８４６８号公報に開示される技術がある。送信側は、対象道路区間に含まれるノードを選出し、そのノードの座標データを送信し、受信側は、送信されたノード座標を地図にマッチングし、マッチングした地点を経由する経路探索を行い、対象道路区間を特定する。対象道路区間に含まれるノードを選出することで、送信側（情報センタ）から受信側（端末装置）に対象道路区間を送信する際の通信コストを削減することを目的としている。
【０００６】
一方、特開２００４―７７２５４号公報は、端末装置において、センタが有する最新情報を用いて確度の高い情報案内を行うには、できるだけ最新の情報を反映したデータを保有することが望ましいとして、端末地図で計算した経路とセンタ地図で計算した経路とを比較し、両経路の差異を検出したときに、差異部分に該当するセンタ地図データを端末装置に送信し、端末地図を更新する方法を開示している。端末装置が最新地図に更新されるので、端末装置の経路計算で情報センタと同じ最新情報を反映した経路が得られるようになる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００２−２２８４６８号公報
【特許文献２】特開２００４−０７７２５４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
経路案内サーバの推奨経路を端末装置で利用する場合、従来技術では、推奨経路のノード座標列データ、あるいは推奨経路を計算するための差分地図データを経路案内サーバから端末装置に送信するので、送信するデータ量が大きくなるという問題がある。また、端末装置で経路案内サーバから送信された推奨経路のノード座標列から経路を再現するには、端末地図へのマッチング処理と、マッチングしたノードを経由する経路探索処理が必要であり、経路を正しく再現するためにノードを多く選択すると、経路再現のための端末処理負荷が増えるので、経路を要求してから提示されるまでの待ち時間が長くなる。差分地図データが提供される場合においても、経路計算する前に差分地図データによる地図更新処理が必要となるため、経路が提示されるまでの待ち時間が生じる。
【課題を解決するための手段】
【０００９】
（１）請求項１に記載のナビゲーション端末装置は、経路案内サーバ装置との情報交換を行うナビゲーション端末装置であって、道路リンクデータを含む端末地図データと、移動体の出発地から目的地までの移動経路を、移動体が移動経路を移動する際の移動コストに関する所定の探索条件に基づき、端末地図データを用いて探索する端末経路探索手段と、出発地、目的地および所定の探索条件を含む経路素片要求を経路案内サーバ装置へ送信する送信手段と、経路素片要求に応じて、端末経路探索手段により探索された移動経路を含む所定領域内の経路素片を、経路案内サーバ装置から受信する受信手段と、経路素片に基づいて、移動経路に含まれかつ第１の道路リンク群によって構成される少なくとも一部の区間経路の始終点と同一の始終点を有する他の区間経路を構成する第２の道路リンク群に第１の道路リンク群を置き換えることにより、移動経路を構成する全ての道路リンクの位置に関する位置参照データと、全ての道路リンクの移動コストに関するコストデータとを含む経路データを更新する更新手段とを備え、経路素片は、経路案内サーバ装置で探索された出発地から目的地までの複数の経路に所定領域内の複数の道路リンクの各々が含まれた頻度が所定値以上である一部の道路リンクで構成されることを特徴とする。
（２）請求項１０に記載の経路案内システムは、請求項１乃至９のいずれか１項に記載のナビゲーション端末装置と、経路案内サーバ装置とを備える経路案内システムであって、経路案内サーバ装置は、サーバ地図データと、送信手段により送信された経路素片要求を受け付ける要求受付手段と、複数のナビゲーション端末装置のために、出発地から目的地までの複数の経路を、所定の探索条件に基づき、サーバ地図データを用いて探索するサーバ経路探索手段と、要求受付手段により受け付けられた経路素片要求に応じて、頻度に関する頻度情報を取得する頻度情報取得手段と、要求受付手段により受け付けられた経路素片要求に応じて、複数の経路を分割することにより経路素片を生成する経路素片生成手段と、経路素片生成手段により生成された経路素片を、ナビゲーション端末装置の受信手段へ配信する配信手段とを有することを特徴とする。
（３）請求項１１に記載の経路案内サーバ装置は、請求項１０に記載の経路案内システムにおける経路案内サーバ装置である。
【発明の効果】
【００１０】
本発明によれば、経路を複数の道路区間に分割（経路素片）し、経路を再現するために必要な経路素片のみを伝送するので、端末装置に送信される情報量が小さく通信負荷が軽減される。更に、端末装置は、全経路ではなく、経路素片を受信し端末地図に対応付けるので、経路を再現するための処理負荷が軽減される。通信負荷および端末処理負荷が軽減されるので、サーバ経路を取得し経路案内を開始するまでの操作待ちが短くなる。
【００１１】
更に、本発明では、端末装置において端末地図と経路素片を用いて経路を探索するので、経路を逸脱、あるいはサーバ装置から経路情報を得るまでの時間の車両移動により現在位置が更新されても、サーバ装置に再接続することなく目的地までの経路が得られる。
【図面の簡単な説明】
【００１２】
【図１】経路案内サーバおよびナビゲーション装置の機能ブロック構成を示す図である。
【図２】サーバ装置１において、経路素片を生成する処理を説明するフローチャートである。
【図３】図２を補足説明する補足図である。
【図４】サーバ装置１において、経路素片を生成するもう1つの方法を説明するフローチャートである。
【図５】図４を補足説明する補足図である。
【図６】ナビゲーション端末５において、経路素片を用いて経路を再現する処理を説明するフローチャートである。
【図７】図６を補足説明する補足図である。
【図８】サーバ装置１において、経路素片生成部１８で生成される経路素片データの一例である。
【図９】ナビゲーション端末５において、経路素片を用いて経路を生成する処理の一例を説明するフローチャートである。
【図１０】図９を補足説明する補足図である。
【図１１】ナビゲーション端末５において、経路素片を用いて経路を生成する処理のもう一つの例を説明するフローチャートである。
【図１２】ナビゲーション端末５での経路表示の一例を示す図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施形態について詳しく説明する。
【００１４】
＜経路案内システムの全体構成  サーバ・端末＞
図１は、本発明の実施形態に関わる経路案内システムの全体構成を示した図である。本例では、サーバ装置１とナビゲーション端末５が、互いに通信することにより経路案内システムを構成する一実施の形態を想定し説明する。図１において、本実施形態に関わるサーバ装置１は、通信ネットワーク２に接続され携帯電話などの基地局３を介し、無線通信手段により車両４に搭載されるナビゲーション端末５に接続される。また、ブロードバンドネットワーク７を介して、交通情報センタ、天気情報センタ、観光情報センタなどの外部情報センタ６にも接続される。
【００１５】
サーバ装置１は、図示しないＣＰＵ（Central Processing Unit）、メモリ装置、ハードディスク装置などを含んで構成されたいわゆるコンピュータ（情報処理装置）によって構成される。そして、そのサーバ装置１は、機能的には、図１に示すように、通信インタフェース部１０、外部情報取得部１１、外部情報取得データベース１２、端末要求受付部１３、経路条件設定部１４、経路探索部１５、第一の地図データ１６、第二の地図データ１７、経路素片生成部１８、情報提供部１９などの機能ブロックを含んで構成される。なお、これらの機能ブロックは、上記ＣＰＵが半導体メモリやハードディスク装置に記憶されているプログラムを実行することによって実現される。
【００１６】
図１において、外部情報取得部１１は、外部情報センタ６から交通情報や天候、施設情報などの様々な情報を取得し、外部情報データベース１２に蓄積する。端末要求受付部１３は、ナビゲーション装置５から送信される経路要求を受信して、該要求内容を解析し、解析した結果を経路条件設定部１４に反映する。経路要求には、経路探索に必要な車両位置（あるいは出発地）、目的地、走行予定日時、探索条件などの情報を含んでいる。探索条件としては、一般的に有料道路を優先するか、距離ないし時間を優先するか、交通状況を考慮するか等が用いられるが、他のドライバが多く利用する人気ルートやお勧めルート等、センタで如何ように解釈可能な曖昧性を含めた条件を受け付けることも可能とする。
【００１７】
この場合は、経路条件設定部１４において、曖昧な探索条件から具体的な条件に変換する変換処理を行う。例えば、「人気ルートであれば」走行頻度の高い道路、「お勧めルート」であれば、利用者の注目度の高い地点を経由する道路、というように具体的に情報検索可能な表現に変換し、該表現文から検索キーを生成する。生成した検索キーにヒットする情報が、外部情報データベース１２に存在しない場合、あるいは最新情報を必要とした場合、該検索キーを用いて外部情報取得部１２を介し必要な情報を外部情報センタ６から収集する。収集した情報は外部情報データベース１３に蓄積する。交通情報や天候情報はどの比較的に短い期間で変動する情報で、経路探索条件として頻繁に利用される情報については、定期的に外部情報センタ６から収集するようにして、外部情報データベース１２に蓄積し、常に新しい情報が保たれるようにする。
【００１８】
経路探索部１５は、経路条件設定部１４で設定された探索地点（出発地、目的地、経由地）と探索コスト（時間、距離、料金、燃料消費量等の移動コスト）、外部情報データベース１２に蓄積された交通情報や観光スポット等の情報を参照し、経路要求に応じて複数の地図データ（１６および１７）を選択し、それを用いて目的地までの経路を計算する。経路素片生成部１８は、経路探索部１５で計算し得られた経路を少なくとも１つ以上の道路区間（区間経路、道路リンク列、１つまたは複数の道路リンク）に分割し、所定の基準を満たす経路素片を生成する。道路リンクは道路リンク番号で管理される。地図データを参照することにより、道路リンク番号を用いて道路リンクの位置を参照可能である。 情報提供部１９は、経路素片生成部１８で生成した経路素片を含めて、サーバ装置１が推奨する経路情報とした応答データを作成し、ナビゲーション装置５に配信する。
【００１９】
ナビゲーション端末５は、図１に示すように、本体部５１に表示部５２、携帯電話機５３、ＧＰＳ（Global Positioning System）受信機５４等が接続され構成される。ここで、本体部５１は、メモリやハードディスク装置といった記憶装置を含んで構成された小型のコンピュータによって構成される。なお、記憶装置５５に代えて、または加えてＤＶＤ（Digital Versatile Disk）や可搬のメモリカードなどを用いても良い。本体部５１は、携帯電話５３によって携帯電話の基地局３と通信し、さらに、通信ネットワーク２を介してサーバ装置１に接続しても同様である。
【００２０】
ナビゲーション端末５は、サーバ装置に経路要求を送信することによって、サーバ装置１から誘導経路の提供を受けることができる。本発明では、サーバ装置１から誘導経路を再現するための経路材料となる経路素片が提供される。ナビゲーション端末５は、経路素片を用いて誘導経路を再現し、その誘導経路に従った誘導指示情報を表示部５２へ出力する。なお、経路誘導指示情報は、スピーカなどを用いて音声として出力してもよい。
【００２１】
本体部５１は、通信インターフェース５１０、情報取得部５１１、経路素片記憶部５１２、経路探索部５１３、経路情報記憶部５１４、地図データ５１５、位置情報取得部５１６、経路案内部５１７、入出力インターフェース部５１８、コンテンツ要求部５１９等の機能ブロックを含んで構成される。
【００２２】
コンテンツ要求部５１９は、通信インターフェース部５１０を介してサーバ装置１に接続され、入出力インターフェース部５１８で設定されたユーザ入力情報と、位置情報取得部５１６から得た位置情報に基づいて、出発地（現在地）、目的地等の地点情報と、時間優先、距離優先、料金優先などの探索条件を指定し、目的地までの誘導経路をサーバ装置１に要求する。情報取得部５１１は、サーバ装置１から上記要求に対応した経路情報を受信して経路素片記憶部５１２に記憶する。上記経路情報は、目的地までの経路を含む所定領域内の１つまたは複数の道路リンクで構成される経路素片で構成される。経路素片は上述したようにサーバ装置１で生成される。経路探索部５１３は、上記サーバ装置１に要求した探索条件と同じ探索条件を設定し、経路素片記憶部５１２に記憶された経路素片と地図データ５１５を用い目的地までの経路を探索する。このとき、入出力インターフェース部５１８で出発地点が現在位置に指定されていれば、経路探索部５１３は、位置情報取得部５１６から得た位置情報を出発地点として経路を計算する。得られた経路は、経路情報記憶部５１４に記憶される。経路案内部５１７は、上記経路が経路素片で構成されていた場合、上記経路素片を地図データ５１５に含まれる道路リンクデータに対応付けて上記地図データに基づく経路情報を生成し、上記経路情報から右左折交差点等の経路案内情報を生成する。生成された経路案内情報は、入出力インターフェース部５１８により表示部５２に表示される。表示に限らず、ナビゲーション装置５が音声出力手段を有する場合は、音声で誘導情報の概略（通過地点や路線名など）を利用者に通知しても良い。
【００２３】
尚、本実施の形態における端末装置には、ナビゲーション端末５を用いるものとして説明したが、同等の機能を有する通信端末を用いても構わない。
【００２４】
＜サーバ装置１の処理フロー＞
図２は、図１の経路案内システムを構成するサーバ装置１において、経路素片を生成する処理の詳細なアルゴリズムを示すフローチャートである。図３は、図２の処理手順を補足説明するための補足図である。
【００２５】
サーバ装置１は、ナビゲーション端末５から経路要求を受け付けると（Ｓ２０）、経路要求に含まれる出発地点、目的地点から、それらの地点が含まれる探索エリア３００を設定する（Ｓ２１）。経路要求に経由地が含まれている場合は、上記経由地を含む探索エリア３００を設定する。探索エリア３００において、上記経路要求と同じような探索条件にて生成された経路素片が過去の経路要求に対する処理で既に経路素片記憶部１８１に保持されていた場合（Ｓ２２がＹｅｓ）、上記経路素片記憶部１８１から該当する経路素片を検索、参照（Ｓ２８）して経路情報応答データを生成し、ナビゲーション端末５に配信する（Ｓ２７）。経路素片が保持されていなければ（Ｓ２２がＮｏ）、上記探索エリア内に存在する地点（ノード）から仮の出発地点（３１１、３１２、３１３）と目的地点（３２１、３２２、３２３）のペアを複数選択し、上記経路要求にて指定された探索条件に基づき、上記選択した仮の出発地点Ｏ’から仮の目的地点Ｄ’に向かう複数の経路を計算する（Ｓ２３）。各経路を構成する道路リンクの出現数、即ち経路として選択された回数を道路リンク毎に集計し（Ｓ２４）、経路数に対する経路として選択された回数の比率（頻度）が所定値以上の道路区間３０を選択することにより、仮の出発地点Ｏ’から仮の目的地点Ｄ’に向かう複数の経路を分割する（Ｓ２５）。選択した道路区間を経路素片として経路素片データを生成し（Ｓ２７）、生成した経路素片データをナビゲーション端末５に配信する（Ｓ２７）。
【００２６】
ステップＳ２３の探索地点選択は、ステップＳ２３１〜Ｓ２３４の手順に従う。まず、探索エリア内のノードを近傍ノード同士で複数グループ（３１０、３２０，３３０，３４０）に分類する（Ｓ２３１）。本例において、グループ３１０はノード３１１，３１２，３１３、グループ３２０はノード３２１，３２２，３２３、グループ３３０はノード３３１，３３２、３３３，３３４、グループ３４０はノード３４１，３４２，３４３で構成される。このようなノードの分類は、例えばクラスタリング分析を用い、式（１）に示すクラスタｉ，ｊ間のユークリッド距離ｄｉｊに基づいて各ノードを併合していく方法がある。ｋは特性指標を示しており、ここでは平面座標系上の近傍地点同士を併合するので、各座標軸をその特性指標としｄｉｊを計算する。採用するクラスタ数は、クラスタを構成するノード数とクラスタｉ，ｊ間のユークリッド距離に基づいて決定する。
【数１】
0005599830.tif 000002
【００２７】
上記出発地Ｏが属するノードグループを始点グループ３１０として選択し（Ｓ２３２）、目的地Ｄが属するグループを終点グループ３２０として選択する（Ｓ２３３）。始点グループ３１０のノード３１１，３１２，３１３を探索開始始点、終点グループ３２０のノード３２１，３２２，３２３を探索終了地点に各々設定し、経路を計算する（Ｓ２３４）。
【００２８】
クラスタリング分析を用いず、出発地Ｏからの距離（または移動時間）が所定範囲内に存在するノードを始点グループ、目的地Ｄからの距離（または移動時間）が所定範囲内に存在するノードを終点グループとして同様に各地点間の経路を計算しても良い。
【００２９】
図４は、サーバ装置１において、経路素片を生成する処理のもう1つの方法を示すフローチャートである。図５は、図４の処理手順を補足説明するための補足図である。本例では、図１のステップＳ２３〜２５において経路選択頻度の高い道路区間３０を選択して経路素片とする代わりに、ステップＳ４０〜Ｓ４４によりナビゲーション端末５で計算される経路と相異なる道路区間で経路素片を生成する。
【００３０】
まず、経路探索部１５は、第一の地図データ１６と外部情報データベース１２に蓄積された交通情報等の最新コンテンツを参照し、ナビゲーション端末５から受信した経路要求に含まれる出発地点から目的地点までの第一の経路を計算する（Ｓ４０）。次に、第二の地図データ１７を用いて上記出発地点から目的地点までの第二の経路を計算する（Ｓ４１）。ここで、第二の地図データ１７は、ナビゲーション端末５が有する地図データ５１５と同じものを使用する。ナビゲーション端末５から受信した経路要求メッセージに第二の経路が含まれるときは、ステップＳ４１において、サーバ装置１は、第二の経路を計算する代わりに、受信した経路要求メッセージから第二の経路を取得してもよい。 サーバ装置１は、複数の地図データを有し、ナビゲーション端末５が送信する経路要求に含められる地図バージョン情報に応じて第二の地図データ１７を選択し第二の経路を計算する。第一の経路は、サーバ装置１が有する最新地図とコンテンツが反映された経路５０で、第二の経路はナビゲーション端末５で計算される経路５１となる。第一の経路５０と第二の経路５１とを比較し（Ｓ４２）、第二の経路に含まれない第一の経路の特定の道路区間を構成する特定の道路リンク群（ノードｎａおよびｎｃ間の道路リンク、ならびにノードｎｃおよびｎｂ間の道路リンク）を選択することにより、第一の経路５０を分割する（Ｓ４３）。出発地点Ｏから目的地点Ｄに向かって、順次相異なる道路区間を選択する処理を繰り返す（Ｓ４４）。
【００３１】
＜ナビゲーション端末５の処理フロー＞
図６は、ナビゲーション端末５において、受信した経路素片を用いてサーバ装置１が推奨する経路を再現する処理方法を示すフローチャートである。図７は、図６の経路再現処理を補足説明するための補足説明図である。
【００３２】
入出力インターフェース部５１８において経路探索条件が設定されると（Ｓ６００）、経路探索部５１３による経路探索処理が起動される。経路探索部５１３は、設定された経路探索条件に基づいて、地図データ５１５を用いて出発地点から目的地点までの経路７０（経由地点が指定されていれば、設定された経由地点を経由する経路）を計算する（Ｓ６０１）。同時に、サーバ装置１に上記経路探索条件を含めた経路要求を送信する（Ｓ６０２）。上記要求に対する応答として、サーバ装置１から経路素片を含む経路情報を受信し（Ｓ６０３）、受信した経路素片の始終点ノードが上記経路７０に含まれている場合、上記経路７０を受信した経路素片で順次修正していく。例えば、図７において経路素片７１は経路７０の構成ノードｄ１を始点、ｄ２を終点、経路素片７２はノードｄ３始点、ノードｄ４を終点、経路素片７３はノードｄ５を始点、目的地点Ｄを終点とし、ノードｄ１〜ｄ５はいずれも経路７０の構成ノードである。そこで、上記経路素片は全て経路７０の修正に用いられ、経路７０に含まれる道路区間（区間経路）７４、７５、７６を上記経路素片７１，７２，７３で置き換える（Ｓ６０４）。経路案内部５１７は、上記経路素片による修正が終了した経路に基づいて右左折案内などの誘導案内情報を生成し（Ｓ６０５）、サーバ装置１が推奨する経路の再現処理を終了する。生成した経路と誘導案内情報は、入出力インターフェース部５１８を介して表示および音声案内にてユーザに通知される。
【００３３】
＜経路素片データ＞
図８は、経路素片生成部１８で生成される経路素片データの一例である。経路素片データ８０は、経路素片を識別するための経路素片番号、経路素片を構成する道路リンク番号（位置参照データ）、 経路素片の方向（例えば、リンク番号順ないしノード番号順に対して０が順方向、１が逆方向とする）、経路素片のコスト、経路素片から目的地点方向への推定到達コスト、経路素片を構成するノード番号が含まれる一方、道路形状データは含まれない。推定到達コストは、各経路素片（の終点ノード）から目的地点あるいは目的ノードグループまでの平均到達コストである。また経路素片データ８０は、探索条件に応じて複数データ存在する。例えば、日、日種、時刻、探索コスト（時間優先、距離優先、燃費や料金など）によって異なる経路素片データが生成される。ナビゲーション端末５の経路要求に応じた経路素片データを配信する。
【００３４】
＜ナビゲーション端末５の処理フロー  素片データを用いた詳細説明＞
図９は、ステップＳ６０４の経路修正方法をより詳細に示すフローチャートである。図１０は、図９を補足説明するための補足図で、経路素片による経路リスト更新の一例を示す。
【００３５】
経路サーバ装置１から配信された経路素片データを順次読み込む（Ｓ９０１）。全ての経路素片データについて読み込み終了したら（Ｓ９０２がｙｅｓ）本経路修正処理を終了する。上記経路素片がナビゲーション端末５で計算した経路７０を構成する道路区間（区間経路）に該当する場合（Ｓ９０３がｙｅｓ）、上記経路７０の当該道路区間を上記経路素片で置き換え、経路７０を更新する（Ｓ９０４）。例えば、図１０において、経路データ１００１は、経路７０の更新前の経路、経路データ１００２は、サーバ装置１から提供された経路素片データ８０を用いて更新した後の経路を示す。経路データ１００１および１００２は、道路リンク番号、すなわち位置参照データと、移動コストを表すコストデータとを含む。 経路素片データ８０には、経路７０を構成する開始リンク０４０５から終了リンク０６０８に一致する道路区間が含まれ、経路７０を表す上記経路素片データを更新することで、道路リンク０４０５、０５０６、０６０８を移動コスト３４０で通過する更新された経路が生成される。本例では、経路７０の構成リンクと経路素片データの構成リンクを対比させ、更新対象となる道路区間を特定したが、経路７０の構成ノードと経路素片データの構成ノードと対比させ道路区間を特定しても同様である。
【００３６】
＜ナビゲーション端末５の処理フロー  経路素片で経路生成＞
図１１は、図６のステップＳ６０４と異なってナビゲーション端末５が有する地図データ５１５を用いず、サーバ装置１から提供された経路素片データを用いて経路を得る方法を示すフローチャートである。
【００３７】
ナビゲーション端末５は、経路素片データを受信すると（Ｓ６０３）、上記経路素片データから、出発ノードが含まれる経路素片を選択し、経路候補ｐｉとする（出発経路素片）。ここで、経路候補ｐｉが複数存在する場合は（Ｓ１１０２）、出発ノード（あるいは出発ノードを含む経路素片）から経路候補ｐｉへの到達コストｇ（ｐｉ）（出発ノードを含む経路素片の場合は初期コスト０）と、当該経路候補ｐｉから目的地付近への推定到達コストｈ（ｐｉ）（経路素片データ８０の推定到達コストを参照）の和が最小となる経路素片を選択し経路候補ｐｉとする（Ｓ１１０３）。上記経路候補ｐｉを目的地までの経路の構成要素に含め（Ｓ１１０５）、上記経路候補ｐｉが目的地ノードに未到達であれば（Ｓ１１０５がｎｏ）、経路構成要素のインデクスiを更新し（Ｓ１１０６）、上記探索候補ｐｉに接続する経路素片を上記経路素片データから検索し、次の探索候補ｐｉを設定する。上記経路候補ｐｉが目的地ノードに到達したら（Ｓ１１０５がｙｅｓ）、経路素片番号で構成される経路を端末地図に対応付け、図１０の経路データ１００２（道路リンク番号、すなわち位置参照データと、移動コストを表すコストデータとを含む）に示すような端末地図の道路リンクから成る経路情報に変換する（Ｓ１１０８）。 ステップＳ６０５では、上記道路リンクから成る経路から当該道路リンクの付加情報を参照し、道路形状、交差点位置、車線情報、右左折方向などの付加情報を得て経路情報を生成し、本経路探索処理を終了する。
【００３８】
本実施の形態において、経路素片データの位置参照をリンク番号やノード番号を用いたが、サーバ装置１とナビゲーション端末５の地図データが異なり、共通の道路リンク番号、ノード番号で位置参照ができない場合、緯度経度や地図座標系の２次元座標、あるいは更に高さ情報を含む３次元座標を用いて位置を表現しても良い。経路素片のみが位置座標で表現されるので、通信負荷および端末負荷は従来の全経路を配信するよりも小さい。
【００３９】
＜ナビゲーション端末５  表示例＞
図１２は、ナビゲーション端末５において、経路素片データを用いた経路を生成する際に表示部５２に表示される表示画面の一例である。
【００４０】
符号１２０１は、ステップＳ６０１で計算された、出発地１２２０から目的地１２２１までの端末経路１２２０を地図上に表示した例である。端末経路１２２０はサーバ装置１が有する最新コンテンツが反映された経路ではないため、誘導経路が確定するまで誘導経路１２３０と異なる態様（本例では端末経路１２２０を点線で表現）で表示する。また、サーバ装置１と接続して情報取得部５１により経路素片データが受信される場合は、その受信状態を表示する（１２４０、１２４１，１２４２，１２４３）。ステップＳ６０３およびＳ６０４において、経路素片データを受信し終えると受信終了の旨を表示し、さらに端末経路１２２０を更新し終えると、表示画面１２０２に遷移する。表示画面１２０２においては、端末経路１２２０の更新箇所１２２１を端末経路１２２０とは異なる態様で示している。ステップＳ６０５で経路の誘導情報が生成されると表示画面１２０３に遷移し、経路誘導を開始する。
【００４１】
符号１２１０、１２１１、１２１２は自車位置を示している。走行中、ユーザが経路を要求してから、サーバ装置１の経路情報を反映した経路を出力し誘導が開始されるまで、自車位置は時々刻々と更新される。本実施形態によれば、ナビゲーション端末５が有する経路探索部５１３において、サーバ装置１から得た経路素片データと端末地図データ５１５に基づいて経路を計算するので、経路を更新する度にサーバ装置１に接続する必要なく、サーバ装置１が有する最新コンテンツを加味した経路を反映し、常に自車位置を出発地点とした経路を提供することができる。これは、経路を逸脱したときも同様で、例えば表示画面１２０３に表示される経路を逸脱したとしても、サーバ装置１に再接続することなく、経路素片記憶部５１２に保持されている経路素片を用いて、逸脱した地点から目的地までの経路が計算される。
【符号の説明】
【００４２】
１      サーバ装置                    ２      通信ネットワーク
３      基地局                        ４      車両
５      ナビゲーション装置            ６      外部情報センタ
７      ブロードバンドネットワーク    １０    通信インターフェース部
１１    外部情報取得部                １２    外部情報データベース
１３    端末要求受付部                １４    経路条件設定部
１５    経路探索部                    １６    第一の地図データ
１７    第二の地図データ              １８    経路素片生成部
１９    情報提供部                    ５１    本体部
５２    表示部                        ５３    携帯電話機
５４    ＧＰＳ受信機                  ５５    記憶装置
５１０  通信インターフェース部        ５１１  情報取得部
５１２  経路素片記憶部                ５１３  経路探索部
５１４  経路情報記憶部                ５１５  地図データ
５１６  位置情報取得部                ５１７  経路案内部
５１８  入出力インターフェース部      ５１９  コンテンツ要求部
【図１】
0005599830.tif 000003
【図２】
0005599830.tif 000004
【図３】
0005599830.tif 000005
【図４】
0005599830.tif 000006
【図５】
0005599830.tif 000007
【図６】
0005599830.tif 000008
【図７】
0005599830.tif 000009
【図８】
0005599830.tif 000010
【図９】
0005599830.tif 000011
【図１０】
0005599830.tif 000012
【図１１】
0005599830.tif 000013
【図１２】
0005599830.tif 000014