(57)【要約】【課題】  通信型車両ナビゲーションシステムにおいて、車両が当初の誘導経路から逸脱したときであっても、サーバ装置から新たな誘導経路の配信を受けることなく、車載端末装置１において新たな誘導経路を求め、表示することを可能にする。【解決手段】  サーバ装置４において、走行開始時に表示する誘導経路を探索した後すぐに、最短経路アルゴリズムにより各ノードから目的地までの最短経路のデータ（復帰経路指示データ４２３）を求め、そのデータを、誘導経路を含む配信地図データ４２４とともに車載端末装置１へ配信する。車載端末装置１は、車両が誘導経路から逸脱すると、復帰経路指示データ４２３に基づき逸脱地点からの新たな誘導経路又は復帰経路を求め、表示する。【選択図】      図２
2005069751.tif 000002
【特許請求の範囲】
【請求項１】
車載端末装置と通信ネットワークを介して接続された通信型車両ナビゲーションシステムのサーバ装置であって、
前記車載端末装置から配信される現在位置と目的地のデータに基づき、地図データベースを参照し、現在位置から目的地までの誘導経路データを求める誘導経路探索手段と、
前記地図データベースから前記誘導経路近傍の領域について誘導可能な道路を含む地図データを切り出す地図切り出し手段と、
前記切り出した誘導可能な道路により構成される道路網について、最短経路アルゴリズムに基づき、前記道路網の各々のリンクから目的地までの復帰経路指示データを求める復帰経路探索手段と、
前記誘導経路データ及び切り出された地図データを配信地図データへ変換する手段と、
前記復帰経路指示データを前記配信地図データに同伴させて車載端末装置へ配信する手段と、
を備えることを特徴とする通信型車両ナビゲーションシステムのサーバ装置。
【請求項２】
車載端末装置と通信ネットワークを介して接続された通信型車両ナビゲーションシステムのサーバ装置であって、
前記車載端末装置から配信される現在位置と目的地のデータに基づき、地図データベースを参照し、現在位置から目的地までの誘導経路データを求める誘導経路探索手段と、
前記地図データベースから前記誘導経路近傍の領域について誘導可能な道路を含む地図データを切り出す地図切り出し手段と、
前記切り出した誘導可能な道路により構成される道路網について、最短経路アルゴリズムに基づき、前記道路網の各々のリンクから目的地までの復帰経路指示データを求める復帰経路探索手段と、
前記誘導経路データ及び切り出された地図データを配信地図データへ変換する手段と、
前記復帰経路指示データを、前記配信地図データにおけるリンク列データに付属するフラグデータへ変換し、前記変換したフラグデータを、前記配信地図データに付加するフラグ付加手段と、
前記配信地図データを車載端末装置へ配信する手段と、
を備えることを特徴とする通信型車両ナビゲーションシステムのサーバ装置。
【請求項３】
車載端末装置と通信ネットワークを介して接続された通信型車両ナビゲーションシステムのサーバ装置において、そのサーバ装置のコンピュータを、
前記車載端末装置から配信される現在位置と目的地のデータに基づき、地図データベースを参照し、現在位置から目的地までの誘導経路データを求める誘導経路探索手段、
前記地図データベースから前記誘導経路近傍の領域について誘導可能な道路を含む地図データを切り出す地図切り出し手段、
前記切り出した誘導可能な道路により構成される道路網について、最短経路アルゴリズムに基づき、前記道路網の各々のリンクから目的地までの復帰経路指示データを求める復帰経路探索手段、
前記誘導経路データ及び切り出された地図データを配信地図データへ変換する手段、
前記復帰経路指示データを前記配信地図データに同伴させて車載端末装置へ配信する手段、
として機能させることを特徴とする通信型車両ナビゲーションシステムのサーバ装置のプログラム。
【請求項４】
車載端末装置と通信ネットワークを介して接続された通信型車両ナビゲーションシステムのサーバ装置において、そのサーバ装置のコンピュータを、
前記車載端末装置から配信される現在位置と目的地のデータに基づき、地図データベースを参照し、現在位置から目的地までの誘導経路データを求める誘導経路探索手段、
前記地図データベースから前記誘導経路近傍の領域について誘導可能な道路を含む地図データを切り出す地図切り出し手段、
前記切り出した誘導可能な道路により構成される道路網について、最短経路アルゴリズムに基づき、前記道路網の各々のリンクから目的地までの復帰経路指示データを求める復帰経路探索手段、
前記誘導経路データ及び切り出された地図データを配信地図データへ変換する手段、
前記復帰経路指示データを、前記配信地図データにおけるリンク列データに付属するフラグデータへ変換し、前記変換したフラグデータを、前記配信地図データに付加するフラグ付加手段、
前記配信地図データを車載端末装置へ配信する手段、
として機能させることを特徴とする通信型車両ナビゲーションシステムのサーバ装置のプログラム。
【請求項５】
請求項１に記載のサーバ装置と通信ネットワークを介して接続された通信型車両ナビゲーションシステムの車載端末装置であって、
前記サーバ装置から配信される前記配信地図データに基づき、誘導経路及びその近傍の地図を表示する誘導経路表示手段と、
ＧＰＳを含む車両位置センサからの入力データに基づき、当該車両の現在位置を求め、その現在位置が前記誘導経路から逸脱しているか否かを判定するロケータ手段と、
前記ロケータ手段により当該車両の現在位置が前記誘導経路から逸脱していると判定されたときに、前記サーバ装置からすでに配信されている前記復帰経路指示データに基づき前記復帰経路を求め、前記復帰経路を前記誘導経路及びその近傍の地図中に表示する復帰経路表示手段と、
を備えることを特徴とする通信型ナビゲーションシステムの車載端末装置。
【請求項６】
請求項２に記載のサーバ装置と通信ネットワークを介して接続された通信型車両ナビゲーションシステムの車載端末装置であって、
前記サーバ装置から配信される前記配信地図データに基づき、誘導経路及びその近傍の地図を表示する誘導経路表示手段と、
ＧＰＳを含む車両位置センサからの入力データに基づき、当該車両の現在位置を求め、その現在位置が前記誘導経路から逸脱しているか否かを判定するロケータ手段と、
前記ロケータ手段により当該車両の現在位置が前記誘導経路から逸脱していると判定されたときに、前記サーバ装置からすでに配信されている前記配信地図データ中のフラグデータに基づき前記復帰経路を求め、前記復帰経路を前記誘導経路及びその近傍の地図中に表示する復帰経路表示手段と、
を備えることを特徴とする通信型ナビゲーションシステムの車載端末装置。
【請求項７】
前記表示された誘導経路を消去し、前記復帰経路の中で前記当該車両の現在位置から目的地に至る最適経路である代替経路を表示する代替経路表示手段を、
さらに備えることを特徴とする請求項５又は請求項６に記載の通信型ナビゲーションシステムの車載端末装置。
【請求項８】
請求項１に記載のサーバ装置と通信ネットワークを介して接続された通信型車両ナビゲーションシステムの車載端末装置において、その車載端末装置のプロセッサに、
前記サーバ装置から配信される前記配信地図データに基づき、誘導経路及びその近傍の地図を表示する誘導経路表示手段、
ＧＰＳを含む車両位置センサからの入力データに基づき、当該車両の現在位置を求め、その現在位置が前記誘導経路から逸脱しているか否かを判定するロケータ手段、
前記ロケータ手段により当該車両の現在位置が前記誘導経路から逸脱していると判定されたときに、前記サーバ装置からすでに配信されている前記復帰経路指示データに基づき、前記復帰経路を求め、前記復帰経路を前記誘導経路及びその近傍の地図中に表示する復帰経路表示手段、
として機能させることを特徴とする通信型車両ナビゲーションシステムの車載端末装置のプログラム。
【請求項９】
請求項２に記載のサーバ装置と通信ネットワークを介して接続された通信型車両ナビゲーションシステムの車載端末装置において、その車載端末装置のプロセッサに、
前記サーバ装置から配信される前記配信地図データに基づき、誘導経路及びその近傍の地図を表示する誘導経路表示手段、
ＧＰＳを含む車両位置センサからの入力データに基づき、当該車両の現在位置を求め、その現在位置が前記誘導経路から逸脱しているか否かを判定するロケータ手段、
前記ロケータ手段により当該車両の現在位置が前記誘導経路から逸脱していると判定されたときに、前記サーバ装置からすでに配信されている前記配信地図データ中のフラグデータに基づき、前記復帰経路を求め、前記復帰経路を前記誘導経路及びその近傍の地図中に表示する復帰経路表示手段、
として機能させることを特徴とする通信型車両ナビゲーションシステムの車載端末装置のプログラム。
【請求項１０】
前記車載端末装置のプロセッサに、さらに、
前記表示された誘導経路を消去し、前記復帰経路の中で前記当該車両の現在位置から目的地に至る最適経路である代替経路を表示する代替経路表示手段、
として機能させることを特徴とする請求項８又は請求項９に記載の通信型車両ナビゲーションシステムの車載端末装置のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＧＰＳ（Global Positioning System）による車両ナビゲーションシステムに係り、特に、公衆通信ネットワークを介して車載端末装置とサーバ装置との間でデータの授受を行う通信型車両ナビゲーションのサーバ装置、車載端末装置及びそのプログラムに関する。
【背景技術】
【０００２】
近年、通信コストの低下や通信スピードの向上に伴い、通信型車両ナビゲーションシステムが注目を集めている。通信型車両ナビゲーションシステムでは、全国規模の広域の地図データがサーバ装置に保管され、サーバ装置が車載端末装置からの要求に応じて誘導経路を求め、その誘導経路及びその近傍地域の地図データが車載端末装置に配信される。そのため、全国規模の広域の地図データを保管するＤＶＤ（Digital Versatile Disk）等の大容量の記憶装置は、車載端末装置にとって不要のものとなる。また、誘導経路探索処理等も車載端末装置では実行する必要がなくなるので、車載端末装置のプロセッサの処理負荷は大幅に軽減される。その結果、車載端末装置のコストダウンを図ることができる。
【０００３】
一方で、通信型車両ナビゲーションシステムでは、誘導中の車両が誘導経路から逸脱したときに行う誘導経路の再探索（以下、「誘導経路の再探索」を「リルート」という。）後の処置において以下のような弱点が現れてくる。
車両ナビゲーションシステムでは、誘導中の車両が誘導経路から逸脱すると、リルートして新しい誘導経路なり、元の誘導経路へ復帰する経路なりをユーザへ知らせる必要がある。従って、通信型ナビゲーションシステムでは、サーバ装置でリルートして、その結果を車載端末装置へ配信する。しかし、車両の走行中にあっては通信不安定なエリアや通信不能なエリアなどが存在するために、その配信は必ずしも安定的にできるとは限らない。しかも、再配信のために余分な通信のコストがかかる。なお、その通信不安定又は通信不能の時間はわずかであっても、ユーザにとっては、通信型ナビゲーションシステムの使い勝手の悪さとなって印象付けられる。
【０００４】
この弱点を克服する試みはすでに開始されている。例えば、特許文献１には、差分データにより地図データを送信する、あるいは、地図に表現されている情報を粗くする等の方法によりリルート時の通信量を削減する技術が開示されている。通信量が削減されると、通信時間が短くて済むので、通信の安定性は向上し、通信コストも低減される。
また、特許文献２には、誘導経路情報を分割しトンネル等通信不能エリアを事前に検知することにより、通信不能エリアでの通信を避ける技術が開示されている。
さらに、特許文献２及び特許文献３には、通信不能などのためにリルート情報を車載端末装置に配信できない場合には、車載端末装置が独力で当初の誘導経路に復帰する経路を求め、それを表示する技術が開示されている。また、特許文献４には、最適な誘導経路の他に誘導経路に準ずる第２、第３の経路をあらかじめ求めておき、それらを表示することによって、利用者の経路選択の自由度を高め、かつ、走行時のリルートを回避する技術が開示されている。
【特許文献１】特開２００２−１０７１６９号公報（段落番号００５４〜０１０５、図２２〜図４１）
【特許文献２】特開２００１−１４７１３２号公報（段落番号００２５〜００９９、図１〜図７）
【特許文献３】特開２００３−０７５１８０号公報（段落番号０１１８〜０１５９、図４〜図８）
【特許文献４】特開２００２−１３９３３６号公報（段落番号００４４〜００６９、図２〜図６）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、前記特許文献１ないし特許文献３に開示されているいずれの技術においても、リルートに際してはサーバ装置と車載端末装置との間で通信がなされる。従って、これらの技術は、前記走行中での通信不安定性の問題又は通信コストが増加する問題のいずれに対しても、十分な解決手段とはなっていない。
また、特許文献２又は特許文献３に開示されている技術において、車載端末装置が独力で求める誘導経路は、最適経路という意味での精度は高いものではなく、ともかくも元の経路へ復帰できればいいという程度の経路である。さらに、特許文献４に開示されている技術で求められる第２、第３の誘導経路は、出発地からの準最適経路であって、逸脱が発生した位置からの最適経路ではない。
【０００６】
そこで、本発明の目的は、リルートの際に生じる走行中での通信不安定性の問題及び通信コストが増加する問題を根本的に解決するとともに、車載端末装置において独力でリルートのための最適な誘導経路を求めることが可能な通信型車両ナビゲーションシステムのサーバ装置、端末装置及びそれらのプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
前記課題を解決するため、本発明では、車両が誘導経路から逸脱してもサーバ装置と車載端末装置との間で通信をしなくても済むようにする。
そのために、サーバ装置には、現在位置から目的地までの誘導経路データを求める誘導経路探索手段（プログラム）に加えて、誘導経路近傍の地図を切り出し、それに含まれる誘導可能な道路リンクに対して目的地までの最短経路を探索し、復帰経路指示データを作成する手段（プログラム）を設ける。そして、サーバ装置は、誘導すべき経路を求めたすぐ後に、その復帰経路指示データを作成し、それを、誘導経路データを含む地図データに同伴させて又は組み込んで車載端末装置に配信するようにする。
【０００８】
一方、車載端末装置には、サーバ装置から配信される復帰経路指示データに基づきリルートのための復帰経路を求める手段（プログラム）、及び、それを表示する手段（プログラム）を設ける。そして、車載端末装置は、車両が走行途中で誘導経路から逸脱したときに、その復帰経路指示データに基づき独力でリルートのための復帰経路を求め、それを表示するようにする。
【発明の効果】
【０００９】
本発明によれば、車両が誘導経路から逸脱するようなときには、車載端末装置はすでに最短経路アルゴリズムに基づいた復帰経路指示データの配信を受けているので、実際に逸脱したときには、サーバ装置から何ら新しい情報の配信を受けなくとも、先に配信された復帰経路指示データをもとに目的地又は元の誘導経路までの復帰経路を求めることができ、それを表示することができる。従って、車両がいつどこで誘導経路から逸脱しようとも、車載装置とサーバ装置の間で通信をする必要はない。すなわち、従来、通信型車両ナビゲーションシステムの弱点とされてきた走行途中での通信の不安定性の問題、さらには、そのとき必要となる通信コストの問題には関わる必要がない。これらの問題は解決されたといってよい。
また、復帰経路指示データは、当初の誘導経路近傍の道路リンク各々から目的地までの最短経路を示すデータとなっているため、車両がどこで誘導経路から逸脱しようとも、車載装置は、目的地までの最適の経路を表示することができる。
【発明を実施するための最良の形態】
【００１０】
＜システムの構成＞
以下、本発明の実施の形態について、適宜図面を参照しながら詳細に説明する。
まず、図１及び図２に従い、本発明が適用される通信型車両ナビゲーションシステムの構成について説明する。ここで、図１は、通信型車両ナビゲーションシステムにおける車載端末装置１の構成例を示した図、図２は、通信型車両ナビゲーションシステムにおけるサーバ装置４の構成例を示した図である。
【００１１】
図１及び図２に示すように、通信型車両ナビゲーションシステムは、経路誘導を必要とする車両に積載される車載端末装置１と、その車載端末装置１と通信装置２及び公衆通信ネットワーク３を介して接続されるサーバ装置４により構成される。ここで、通信装置２とは携帯電話等であり、公衆通信ネットワーク３とは、電話回線のネットワークやインタネットプロトコルのネットワークを含んだものである。
【００１２】
図１において、車載端末装置１は、情報処理装置としての端末プロセッサ１１に、入力と出力の機能を兼ね備えたタッチパネルディスプレイ１２、人工衛星の電波を受信するＧＰＳ（Global Positioning System）受信機１３、ジャイロスコープ等の方向センサ１４、車輪の回転速度を入力する車速センサ１５、スピーカ１６、マイク１７等が接続される構成となっている。また、端末プロセッサ１１は、ＣＰＵ（Central Processing Unit）１１１に、端末ソフトウエア６を格納するフラッシュメモリ１１３、サーバ装置４から配信されるデータを格納するＤＲＡＭ（Dynamic Random Access Memory）１１２、タッチパネルディスプレイ１２の表示を制御するグラフィックスプロセッサ１１６とグラフィックスメモリ１１７、タッチパネルディスプレイからの入力を受けるシリアルＩ／Ｆ（Ｉ／Ｆはインタフェースの略。以下、この明細書において同じ。）１１８、ＧＰＳ受信機１３、方向センサ１４及び車速センサ１５とインタフェースするセンサ系Ｉ／Ｆ１１４、携帯電話等の通信装置２とインタフェースする通信装置Ｉ／Ｆ１１５等が接続された構成となっている。
【００１３】
図２において、また、サーバ装置４は、サーバコンピュータ４１に、ハードディスク装置４２、モニタディスプレイ４３、キーボード４４、マウス４５等が接続された構成となっている。また、サーバコンピュータ４１は、ＣＰＵ４１１に、いわゆるＢＩＯＳ（Basic Input Output System）を格納するフラッシュメモリ４１３、サーバソフトウエア７を格納するＤＲＡＭ４１２、モニタディスプレイ４３の表示を制御するグラフィックスプロセッサ４１８とグラフィックスメモリ４１９、ハードディスク装置４２とインタフェースするＳＣＳＩ（Small Computer System Interface）４１５、公衆通信ネットワーク３とインタフェースするネットワークＩ／Ｆ４１７、キーボード４４やマウス４５とインタフェースするＵＳＢ（Universal Serial Bus）Ｉ／Ｆ４１４等が接続された構成となっている。そして、ハードディスク装置４２には、サーバソフトウエア７及び地図データベース４２１が保管され、必要に応じて経路探索データベース４２２、復帰経路指示データ４２３、配信地図データ４２４等が作成され、一時的に保管される。
【００１４】
図３は、端末ソフトウエア６及びサーバソフトウエア７の構成例を示した図である。
端末ソフトウエア６は、端末プロセッサ１１のフラッシュメモリ１１３に格納され、その実行により端末プロセッサに種々の機能を実現するためのプログラムである。端末ソフトウエア６は、大きくは、ユーザーインタフェース６１、ツール６２、ＯＳ（Operating System）６３により構成される。ここで、ツール６２は、車載端末プロセッサ１１を通信型車両ナビゲーションシステムの端末として機能するようにするために、地図管理６２１、ロケータ６２２、通信６２３、地図表示６２４、誘導経路表示６２５、復帰経路表示６２６、代替経路表示６２７等のアプリケーションプログラムを含んでいる。また、ＯＳ６３は、ファイル管理ドライバ６３１、センサ系ドライバ６３２、通信装置ドライバ６３３、シリアルＩ／Ｆドライバ６３４、グラフィックスドライバ６３５、サウンドドライバ６３６等種々のインタフェースを制御するドライバを含んでいる。
【００１５】
サーバソフトウエア７は、大きくは、ナビゲーションアプリケーション７１、サーバミドルウエア７２、データベース管理ソフトウエア７３、サーバＯＳ７４により構成される。ここで、ナビゲーションアプリケーション７１は、サーバコンピュータ４１を通信型車両ナビゲーションシステムのサーバ装置４として機能するようにするためのアプリケーションプログラムであり、目的地検索７１１、誘導経路探索７１２、地図切り出し７１３、復帰経路探索７１４、配信地図変換７１５等のプログラムを含んでいる。また、サーバミドルウエア７２は、そのナビゲーションアプリケーション７１の各プログラムの記述と動作を容易にするためのプログラムであり、ＨＴＴＰ（Hyper Text Transfer Protocol）サーバ７２１、ＣＧＩ（Common Gateway Interface）７２２、データベースアクセス７２３等を含んでいる。
【００１６】
＜サーバ装置の動作及び処理内容＞
図４ないし図１３に従って、通信型車両ナビゲーションシステムにおけるサーバ装置の動作及び処理内容について詳しく説明する。なお、このとき、図２のサーバ装置４の構成例、及び、図３のサーバソフトウエア７の構成例を適宜参照する。
【００１７】
通信型車両ナビゲーションシステムにおいては、車両の走行の開始つまりドライブ開始に当たって、ユーザは車載端末装置１で目的地を設定し、目的地までの誘導経路を得ようとする。そこで、車載端末装置１は、電源が投入されるとＧＰＳにより現在位置の緯度及び経度のデータを取得し、タッチパネルディスプレイ１２等によって入力される目的地や誘導経路を探索するときの条件（例えば、時間優先の最短時間経路、高速道路優先の経路等々）を取得する。そして、それら出発地の緯度・経度、目的地の緯度・経度、探索条件のデータをＣＧＩパラメータテーブルとしてサーバ装置４へ配信する。ここで、このＣＧＩパラメータテーブルには、復帰経路フラグ（リルートフラグ）が含まれている。この復帰経路フラグは、そのオン状態のときにサーバ装置４に対して復帰経路を求めることを要求する。なお、このようなＣＧＩパラメータテーブルのデータは、車載端末装置１からサーバ装置４へのＵＲＬ形式の要求として表現することができ、例えば、
HTTP://servername/route.cgi?src=N35.40.39,E139.46.20&dest=N35.32.52,E139.47.28
&cond=time,freeway&reroute=on  のように記述され、"src=N35.40.39,E139.46.20"が出発地の緯度・経度を表し、"dest=N35.32.52,E139.47.28"が目的地の緯度・経度を表し、"cond=time,freeway"が探索条件を表し、"reroute=on"が復帰経路フラグに対応していて復帰経路を求めることを表す。また、探索条件の"time,freeway"は時間優先かつ高速道路優先の探索条件を表している。
【００１８】
図４は、サーバ装置４における誘導経路探索及び復帰経路探索処理のフローを示した図である。また、図５はその処理の内容を説明するための参考図である。
サーバ装置４は、車載端末装置１からＣＧＩパラメータテーブルの配信を受けると、現在位置から目的地までの誘導経路の探索を開始する。まず、現在位置及び目的地の緯度、経度のデータに基づき地図データベース４２１をアクセスし、現在位置すなわち出発地および目的地近傍の探索可能な道路を抽出し、出発地リンクＬｓと目的地リンクＬｅを決定する（Ｓ７１２０）。また、この処理において経路探索データベース４２２を作成する。ここで、探索可能な道路とは、誘導経路になりうる道路をいい、地図に表示されていても幅の狭い側道等は含まれない。ここで、リンクとはノードによって区切られる道路をいい、ノードとは交差点のことをいう（ただし、現実には道路の途中であってもノードが設定されることがある）。
【００１９】
次に、経路探索データベース４２２にアクセスし、出発地リンクＬｓから目的地リンクＬｅまでの経路探索処理を行い、その中から最適の経路を誘導経路として抽出する（Ｓ７１２１）。ここで、最適の経路とは、ＣＧＩパラメータテーブルの検索条件によって指定される条件について最適となる経路である。そして、抽出した誘導経路に従い地図データベース４２１にアクセスし、その誘導経路を道路形状に現す点列に変換する（Ｓ７１２２）。さらに、誘導経路の道路形状の点列に沿うように、地図の切り出し範囲Ｒを決定し（Ｓ７１２３）、地図データベース４２１にアクセスし、その中から切り出し範囲Ｒ内の地図を切り出す（Ｓ７１２４）。図５に、地図切り出し範囲Ｒ及び誘導経路の例が示されている。
【００２０】
次に、ＣＧＩパラメータテーブルにおける復帰経路フラグの状態をチェックし、復帰経路フラグがオフの場合は（Ｓ７１２５でＮｏ）、経路探索処理（Ｓ７１２１）の結果得られた誘導経路及び切り出した地図を配信地図データ４２４に変換する（Ｓ７１２６）。そして、その配信地図データ４２４を車載端末装置１へ配信する。
また、復帰経路フラグがオンの場合は（Ｓ７１２５でＹｅｓ）、切り出し範囲Ｒ内の探索可能道路に対して復帰経路探索処理を実行する（Ｓ７１２７）。そして、経路探索処理（Ｓ７１２１）の結果得られた誘導経路及び切り出した地図を配信地図データ４２４に変換し（Ｓ７１２８）、さらに、復帰経路探索処理（Ｓ７１２７）の結果得られる復帰経路の情報を、配信地図データ４２４中の道路リンク列のデータに付属する復帰フラグデータとして、その付加処理を行う（Ｓ７１２９）。そして、その復帰フラグデータが付加された配信地図データ４２４を車載端末装置１へ配信する。
【００２１】
図６は、配信地図データ４２４のデータ構造の例を示した図である。配信地図データ４２４は、誘導経路データ４２４１、地図データ４２４２によって構成され、地図データ４２４２は複数のメッシュデータ４２４３から成り、メッシュデータ４２４３は、複数の道路データ４２４４、複数の背景データ４２４５及び複数の名称データ４２４６から成る。さらに、道路データ４２４４は複数の道路リンク列データ４２４７から成り、道路リンク列データ４２４７は複数の点データ４２４８から成る。なお、図６において＊印を付したデータは、複数個あることを示している。
【００２２】
図７は、道路データ４２４４の詳細な構造の例を示した図である。道路データ４２４４は、複数の道路リンク列データ４２４７によって構成され、各道路リンク列データ４２４７には、復帰方向有無フラグ及び代替誘導有無フラグが付されるとともに、点データ４２４８が並んでいる構造となっている。ここで、点データは基本的には位置座標の並びのデータをいい、交差点だけでなく、交差点の間の点も含む。ただし、ここでは説明の都合上、点データは交差点に付されたデータをいうものとし、以後ノードデータと呼ぶ。従って、ノードデータ４２４８は、図７に示すように、交差点ＩＤ、位置座標、同一交差点ＩＤ（その交差点が他の道路リンク列データに含まれるとき、その交差点に付される交差点ＩＤ）、道路の種別（県道２号線、昭和通り等のデータ）、その他道路情報、復帰方向フラグ及び代替誘導フラグが並んだ構造となっている。ここで、復帰方向有無フラグ、代替誘導有無フラグ、復帰方向フラグ及び代替誘導フラグは、図４の処理フローの復帰フラグ付加処理（Ｓ７１２９）において付加される。
【００２３】
次に、図４の処理フローにおける復帰経路探索処理（Ｓ７１２７）及び復帰フラグ付加処理（Ｓ７１２９）について以下さらに詳しく説明する。
なお、復帰フラグのオン／オフにより処理のフローを変えているのは、サーバ装置４が従来型の車載端末装置にも対応できるようにするためである。すなわち、従来型の車載端末装置から配信されるＣＧＩパラメータテーブルにおいては復帰経路フラグがオンになることはない（Ｓ７１２５でＮｏ）ので、復帰経路探索処理（Ｓ７１２７）及び復帰フラグ付加処理（Ｓ７１２９）は行われない。それらの処理は、本実施の形態の車載端末装置１においてこの復帰経路フラグがオンに設定され、そのフラグがサーバ装置４に配信されたとき実行される。
【００２４】
まず、復帰経路探索処理（Ｓ７１２７）について説明をする。この処理は、先に求められた誘導経路に対応して設定された地図の切り出し範囲内の探索可能道路に対して復帰経路または代替経路を求める処理である。ここで、復帰経路とは、車両が当初の誘導経路から逸脱したときの位置から目的地又は当初の誘導経路までに到達する経路をいう。また、代替経路とは誘導経路の中で目的地に到達する最適経路をいう。ここで、最適の条件は車載端末装置１から配信されるＣＧＩテーブルの検索条件によって決定される。
【００２５】
目的地までの最適経路は、いわゆる最短経路アルゴリズムによって求められる。最短経路アルゴリズムでは、道路網をノードとリンクで構成し、各々のリンクにコストを定義し、任意の２点間をつなぐリンクのコストの総和が最小になるものを求める。従って、ノードは交差点に相当し、リンクは交差点間をつなぐ道路に相当する。また、リンクコストは、交差点間の距離や交差点間の走行時間に相当し、最適化の条件によって定められる。
なお、本実施の形態においては出発地および目的地はリンクとしているので、この最短経路アルゴリズム適用に当たっては、それらをノードに変換する必要がある。ここでは、簡単のために、車両の現在位置に近いノードが選択されるものとする。
【００２６】
図８は、最短経路アルゴリズムを説明するための道路網におけるノード、リンク及びリンクコストの例を示した図である。ここで、丸の節点はノードを表し、丸の中にノード番号が付されている。また、ノードをつなぐ線がリンクを表し、そのそばに記載されている矢印と数字は、その矢印方向へ進行するときのリンクコストを表す。また、道路が一方通行の場合には、片方向のみにリンクコストが定義され、定義されていない方向のリンクコストは∞である。これらリンクコストを、リンクコスト行列（ｄij ）として表記する。ここで、ｄij は、ノードiからノードj 方向のリンクコストであり、つながりのないノード間のリンクコストは∞である。
【００２７】
最短経路アルゴリズムで最もよく用いられるのは、ダイクストラ法である。図９は、ダイクストラ法による最短経路探索処理のフローを示した図である。通常、最短経路は、出発点から目的地に向かって最短の経路を求めるが、ここでは、経路探索の際に設定された目的地を逆に処理の出発地と見立てることにより、地図の切り出し範囲内の探索可能道路に対して目的地から全ノードまでの最短経路を求める。すなわち、全ノードについて目的地までの最短経路が得られることになる。
【００２８】
図９のダイクストラ法において与えられるデータは、リンクコスト行列（ｄij ）であり、求めるデータは、ノード番号の集合｛ｐi｝と経路コストの集合｛ｖi｝である。ここで、ｐi は、ノードiから目的地ノードに至る最短経路上の一つ先方のノード番号を表し、ｖi は、ノードiから目的地ノードに至る最短経路のリンクコストの和を表す。
以下、全ノードの集合をＮ、全ノード数をｎ、未処理ノードの集合をＭとして、図９の処理フローについて説明をする。
【００２９】
まず、目的地の番号をeとすれば、ｖe＝0、ｖj＝∞（j=1,…,n, j≠e）、Ｍ＝Ｎ−[e]、i＝e を初期値として設定する（Ｓ７１４０）。
次に、ｄij ＜∞であるｊ∈Ｍに対してｖj＜ｖi＋ｄijならば、ｖj＝ｖi＋ｄijとおき、ｐj＝i とおく（Ｓ７１４１）。これは、ノードi につながるノードjを求めて、ノードj についてすでに求められている目的地ノードまでのリンクコストの和ノードｖj と、ノードjからノードiを経由して目的地に至る経路のリンクコストの和ｖi＋ｄjiを比較し、もし、ノードiを経由するリンクコストの和が小さければ、ノードjまでの最短経路をノードiを経由するものに変更することを意味している。
次に、未処理ノードの集合Ｍに含まれる全てのノードjについてｖjを取り出し、その中から最小になるｖjを求め、そのときのjをj0とする（Ｓ７１４２）。そして、ノードj0を未処理ノード集合Ｍから除外し、それを新たな未処理ノードの集合Ｍとし、ステップＳ７１４１を処理するときの基準となるノードiを、i＝j0とする（Ｓ７１４３）。
これらステップＳ７１４１〜ステップ７１４３までを、未処理ノードの集合Ｍが空になるまで繰り返し、最終的に得られるｐiとｖi（j=1,…,n, j≠e）が、ダイクストラ法で求める最短経路ノードの集合｛ｐi｝と最短経路コストの集合｛ｖi｝となる。
【００３０】
図１０は、図８の道路網の例についてダイクストラ法によって求めた目的地までの最短経路（太線で示した経路）を示した図である。ここで、各ノードのそばの括弧内に記載した数字は、それぞれ各ノードについて求められたｐiとｖiを（ｖi，ｐi）として示している。また、枠外に｛ｐi｝と｛ｖi｝を示している。ｐiは、ノードiから目的地ノードに至る最短経路上の一つ先方のノード番号を示しているので、この番号をたどることによって、目的地まで到達することができる。ちなみに、この例では、ｐ2＝４であるので、ノード２から目的地までの最短経路はノード４へ延び、また、ｐ4＝６であるのでその経路が目的地ノードに到達したことがわかる。すなわち、ダイクストラ法によって全てのノードについて目的地に至る最短経路を求めることができる。
【００３１】
従って、最短経路ノードの集合｛ｐi｝と最短経路コストの集合｛ｖi｝のデータがあれば、車両が道路網上のどこで当初の誘導経路から逸脱しようとも、車両の現在位置から最も近いノードに行きさえすれば、目的地ノードまで到達する経路を示すことができる。ただ、誘導経路から逸脱したとき、走行している経路が前記のダイクストラ法で求めた誘導経路上にない場合、例えば、図１０の例でノード１から２へ行く道路に逸脱した場合には、前方に進んだほうがいいのか、引き返したほうがいいのかすぐには分からない。そこで、それを直感的に分かるようにするために、復帰方向行列（ｒij ）を導入する。ｒij は、リンクijに逸脱した場合、ノードiとノードjのどちらへ進むべきかを方向によって示したものであり、その進むべき方向が、リンクijの方向（ノードi からノードj への方向）と同一方向の場合にｒij＝ 1 と定義し、逆方向の場合にｒij ＝ -1 と定義する。この復帰方向行列における各リンクに対して定められた進行方向を、推奨針路と呼ぶことにする。
【００３２】
図１１は、復帰方向行列の成分ｒij を設定する規則を示した図である。その規則は、前記定義によるが、設定の基本的な考え方は、ノードiとノードjをつなぐリンクijに対して、ｖi＜ｖjならば、ｒij ＝ -1, ｒji＝ 1 と設定する。すなわち、ノードi の目的地までのリンクコストの和ｖiがノードj の目的地までのリンクコストの和ｖjより小さければ、ノードjからノードi へ行った方が最適経路を選択することになる。また、当然ながら、ｄij ＝∞、ｄji ＝∞ならば、ノードi とノードj にはリンクがないので、ｒij ＝ｒji＝ 0とする。また、片方向だけリンクが存在するｄij ＝∞、ｄji ＜∞の場合は、ｖi 、ｖj の値に関わらず、ｒij ＝ -1、ｒji＝ 1 とする。さらに、ｖi＝ｖjならば、どちらへ行っても同じなので、リンクijが当初の誘導経路に近くなる方向のとき、ｒij＝ 1 とし、遠くなる方向のとき、ｒij ＝ -1と定める。なお、図示していないが、始点と終点が同じノードのリンクｒii＝ 0 とする。
【００３３】
図１２は、図８の道路網の例に対して求めた復帰方向行列（ｒij ）である。図１２の各リンクに付された矢印は、ｒij に対応する推奨針路の方向である。すなわち、この矢印に沿って進めば、車両が誘導経路と共に配信される地図上のどこで誘導経路を逸脱しようとも、目的地まで到達することができる。なお、目的地を除く各ノードに付されている黒丸は、その付されているリンクが、前記ダイクストラ法で求めた｛ｐi｝によるリンクiｐi であることを示している。すなわち、その黒丸側のリンクを辿って行けば、そのノードからの最適経路に従って目的地に到達することができる。
【００３４】
以上の説明から分かるように、最短経路ノードの集合｛ｐi｝と復帰方向行列（ｒij ）があれば、復帰経路及び代替経路を求めることができる。従って、車両走行開始時すなわちドライブ開始時に、誘導経路を含む配信地図データ４２４とともにこれらのデータを車載端末装置１へ配信しておけば、車両がどこで誘導経路から逸脱しようとも、車載端末装置１は、最短経路ノードの集合｛ｐi｝と復帰方向行列（ｒij ）のデータを用いて復帰経路及び代替経路を求めることができる。そこで、最短経路ノードの集合｛ｐi｝と復帰方向行列（ｒij ）のデータを総称して復帰経路指示データ４２３という。
【００３５】
図１３は、復帰フラグ付加処理Ｓ７１２９におけるフラグデータ付加処理のフローを示した図である。フラグデータ付加処理は、復帰経路指示データ４２３のデータに基づき配信地図データ４２４の道路リンク列データ４２４７にフラグデータを付加する処理である。従って、この処理に対する入力データは、最短経路ノードの集合｛ｐi｝、復帰方向行列（ｒij ）及び図７の道路リンク列データ４２４７において復帰方向有無フラグ、代替誘導有無フラグ、復帰方向フラグ及び代替誘導フラグを除いたデータである。図１３に示すフラグデータ付加処理において、これらのフラグデータを作成し、付加する。
なお、図１３に示すフラグ付加処理のフローは、一つの道路リンク列データ４２４７を取り出し、その道路リンク列データ４２４７にフラグを付ける処理のフローである。道路リンク列データ４２４７は通常複数個あるので、全ての道路リンク列データ４２４７にフラグを付けるには、複数回この処理を実行する。
【００３６】
まず前処理として、処理対象とする道路リンクの各ノードデータから交差点ＩＤを取り出し、これを、｛ｐi｝及び（ｒij ）を求めたときのノード番号に変換し、それらを順にk(1),k(2),…,k(n) とする。そして、道路リンク列データ４２４７の各道路リンクに付属する復帰方向有無フラグ及び代替誘導有無フラグをオンにして、この道路リンクには復帰方向フラグと代替誘導フラグが設定されていることを表すとともに、カウンタをｉ＝１に初期化する（Ｓ７１５２０）。
次に、与えられたｉに対してｒk(i)k(i+1) ＝１ならば（Ｓ７１５２１でＹｅｓ）、交差点k(i)に対する復帰方向フラグをオンにし（Ｓ７１５２２）、さらに、ｐk(i) ＝k(i+1) ならば、代替誘導フラグもオンにする（Ｓ７１５２３）。一方、ｒk(i)k(i+1) ＝-１ならば（Ｓ７１５２５でＹｅｓ）、交差点k(i)に対する復帰方向フラグをオフにし（Ｓ７１５２６）、さらに、ｐk(i+1) ＝k(i) ならば、代替誘導フラグもオフにする（Ｓ７１５２７）。
次に、カウンタｉを＋１して（Ｓ７１５２４）、ステップＳ７１５２１からステップＳ７１５２８までの処理をｉがｎになるまで繰り返す（Ｓ７１５２８）。この処理により、各ノードに推奨針路の起点となるノードか否かを表す復帰方向フラグと、あるノードがそのノードを含むリンクにおいて代替経路の起点となるか（図７における黒丸となるか）否かを表す代替誘導フラグが設定される。
【００３７】
以上の処理によって、図７における各道路リンク列データ４２４７に復帰方向有無フラグ及び代替誘導有無フラグ、並びに、復帰方向フラグ及び代替誘導フラグが付加され、そのデータが配信地図データ４２４として車載端末装置１へ配信される。従って、車載端末装置１は、これらのフラグを参照することによって、復帰方向や代替誘導経路を表示することになる。
【００３８】
＜車載端末装置の動作及び処理内容＞
以下、図１４ないし図２０に従って、通信型車両ナビゲーションシステムにおける車載端末装置１の動作及び処理内容について詳しく説明する。
図１４は、走行開始時に車載端末装置１に表示される誘導経路の例である。
車載端末装置１は、以上に説明したサーバ装置４によって、走行開始時点において復帰方向フラグ及び代替誘導フラグが付加された配信地図データ４２４の配信を受ける。この
データに基づき、図１４に示すような現在位置（出発地）及び誘導経路を含む地図を表示することができる。
図１４の表示例の場合、出発地は、誘導可能な道路のリンク上に乗っておらず、小さな路地か側道かあるいは広大な駐車場の中にいるものと推定される。このようなときは、出発地リンクは出発の現在位置から最も近いリンクが選ばれる。ここでは、出発地に隣接する北東側リンクの道路が選ばれている。そして、そのリンクから目的地までの誘導経路が例えば太線で表示されている。
【００３９】
図１５は、車載端末装置１において誘導経路とともに復帰方向を表示した例である。ここで、実線の矢印は、代替誘導フラグによる復帰方向であり、破線の矢印は、復帰方向フラグによる復帰方向である。なお、矢印は、道路の側に表示するのではなく、道路の上に表示してもよく、実線の矢印と破線の矢印の区別は、異なる色によってしてもよい。
車両が誘導経路から逸脱するのは、必ずしも走行途中だけとは限らない。図１４のように、出発地が誘導可能な道路上に乗っていないときも、逸脱しているとみなすことができる。このような場合に、復帰方向を表示するとドライバにとって非常に便利である。ちなみに、出発地にある車両が経路探索の結果設定された誘導経路の誘導開始地点となる北東側リンクの道路へ出ようとしても、実際にその道路への出口がなければ、例えば北西側リンクの道路など実際に出口が設けられている他のリンクへ出ざるを得ない。このとき、北西側リンクには、復帰方向が表示されているので、どのように進めば元の誘導経路に戻ることができるか、容易に判断することができる。また、実線の矢印に沿って進めば、最適経路に従って目的地まで到達することができる。このように、現在位置から誘導経路に向かう方向のみならず、現在位置周辺の道路についても復帰方向を表示することにより、誘導経路に至る経路を容易に判断し選択することが出来るようになる。
【００４０】
なお、この時点で、車載端末装置１は、復帰方向フラグ及び代替誘導フラグが付加された配信地図データ４２４の配信を受けているので、復帰方向を求め、地図と共に復帰方向を表示することができる。また、走行途中において、誘導経路から逸脱した場合にも、同様の復帰方向を表示することができ、ドライバは道に迷うこともなく、適切な経路に従って、目的地又は元の誘導経路へ達することができる。しかも、そのとき車載端末装置１はサーバ装置４と通信する必要はない。
【００４１】
復帰方向フラグの表示は、次のようにして行う。図７の道路リンク列データ４２４７において、ノードデータ４２４８を取り出し、その中の復帰方向フラグ及び代替誘導フラグを参照する。そして、もし、代替誘導フラグがオンであれば、その道路リンク列の方向に実線の矢印を表示し、もし、代替誘導フラグがオフであれば、復帰方向フラグがオンのときに、道路リンク列の方向に破線の矢印を表示し、復帰方向フラグがオフのときに、道路リンク列の逆方向に破線の矢印を表示する。ここで、道路リンク列データの方向とは、道路リンク列データ４２４７において、交差点ＩＤが示すノードの連なりが構成するリンク列の方向である。
【００４２】
ここで、車両が走行中に誘導経路から逸脱した場合について補足説明をしておく。
車両が走行中に誘導経路から外れると、「経路から外れました」という警告のメッセージに続き、いわゆる「ターン・バイ・ターン方式」における誘導のように、現在走行している道路のリンクに対応した復帰方向フラグの情報に基づいて、運転者に対して元の誘導経路に復帰するための進行方向を提示する。この時の進行方向の指示は、以上に説明した復帰方向フラグに基づいて行われる。
なお、通常、運転を誤って誘導経路からそれてしまった直後、あるいは運転者が意図して一時的に誘導経路から逸脱した直後には、走行している経路が一方通行ではない場合、そのリンクに設定された推奨針路に基づき、運転者に対してそのリンクを引き返すように指示が出されてしまう。この様な場合には、誘導経路から外れた直後に出される復帰方向の指示は、経路からの逸脱を通知する性格を備えているが、推奨針路と逆の方向に走ってしまい常に引き返すように指示されていると、引き返すために方向転換をすることが難しい道路を運転している場合などには、運転者がこの指示を煩わしく感じることが考えられる。
【００４３】
そこで、推奨針路と逆の方向に走行している場合には、現在走行しているリンクの終端のノードが他のリンクに繋がっている場合、現在走行しているリンクが次に来るノード（つまり、現在走行しているリンクの終点のノード）において図１２に示すような黒丸が付されたリンクでない場合、走行中のリンクに終端から復帰経路を提示しても良いことになる。そこで、現在走行中のリンクに対して推奨針路とは逆の向きに走行している場合、リンクの中間点を通過してしまったら、今度はそのままの向きで走行するように指示するようにしても良い。そして、次のノードから所定距離内に接近した時には、次にノードにおける代替誘導フラグに基づいて、進行方向を指示するようにする。
さらに、道路データの各ノードに対して復帰方向ラグや代替誘導フラグと共に復帰経路探索処理Ｓ７１２７において求めた各ノードにおけるリンクコストの和ｖiが付された形式で配信地図データ４２４が車載端末装置１に配信されてくるのであれば、リンク両端のノードにおけるリンクコストの内分比で分けられた区間を通過してしまった後は、現在走行中のリンクにおける推奨針路とは逆の向きに走行している場合でも、そのまま走行するように指示を出すようにしても良い。
【００４４】
図１６は、車載端末装置１において代替経路を求めるフローを示した図である。
まず、ロケータ６２２により車両が道路に乗っているか否かを判定する（Ｓ６２７０）。その結果、車両が道路に乗っている場合は（Ｓ６２７０でＹｅｓ）、ロケータ６２２のマップマッチング処理により道路リンクＬを決定し、それを代替経路の開始リンクＬ0とし、リンクのカウンタｉ＝１とする（Ｓ６２７２）。また、車両が道路に乗っていない場合は（Ｓ６２７０でＮｏ）、全ての道路リンク列データ４２４７から車両位置に最近傍の道路リンクＬを抽出し、それを代替経路の開始リンクＬ0とし、リンクのカウンタｉ＝１とする（Ｓ６２７１）。
【００４５】
次に、道路リンクＬiの両端のノード（Ｎ１，Ｎ２）を求め、Ｎ１の復帰方向フラグがオンならＮ＝Ｎ２、オフならＮ＝Ｎ１とする（Ｓ６２７３）。ここで、Ｎは、図７におけるノードデータ４２４８の交差点ＩＤに相当する。
さらに、そのＮのノードデータ４２４８の代替誘導フラグがオフのときには、そのノードデータ４２４８中の同一交差点ＩＤに記載されているデータと同一の交差点ＩＤを持つノードデータ４２４８を、他の道路リンク列データ４２４７の中から抽出する。ここで、同一交差点ＩＤは１つとは限定されないので、抽出されるノードデータも２以上あることもある。そこで、抽出されたノードデータ４２４８のうち、さらに、その代替誘導フラグがオンであるものを見つけ、Ｎをその交差点ＩＤで置き換える（Ｓ６２７４）。
【００４６】
次に、Ｎを含む道路リンクに対し、Ｎのノードデータ４２４８の復帰方向フラグがオンならば、Ｌ＝（Ｎ，Ｎの順方向ノード）とし、オフならば、Ｌ＝（Ｎ，Ｎの逆方向ノード）とする（Ｓ６２７５）。
そして、Ｌが目的地リンクであるか否かをチェックし、目的地リンクでない場合は（Ｓ６２７６でＮｏ）、Ｌi＝Ｌ、ｉ＝ｉ＋１とし（Ｓ６２７７）、ステップＳ６２７３ないしステップＳ６２７６の処理を繰り返す。また、Ｌが目的地リンクである場合は（Ｓ６２７６でＹｅｓ）、それまでに求められたリンク列Ｌ0,…,Ｌiを代替経路として出力する（Ｓ６２７８）。
【００４７】
図１７は、車載端末装置１において代替経路を表示した例である。この例においては、代替経路は元の誘導経路と同じように表示されているが、実際には、元の誘導経路の表示がされたまま、元の誘導経路の表示とは異なる目立つ色で、代替経路が表示される。また、元の誘導経路は、消去する表示としてもよく、目立たない薄い表示としてもよい。
また、代替経路が表示されるタイミングは、車両が誘導経路から逸脱したときである。この例の場合、車両は、図１４の出発時に路地にあって、出発リンクを出発地に最も近い北東側の道路リンクに定められ、目的地までの誘導経路が表示されたものの、路地から北東側の道路リンクへ出ることができず、やむなく路地を西北上した状況にあるものとする。この場合、車両が北西側の道路リンクに接近し、北東側の道路リンクよりも近いと判断されると、車両は北西側の道路リンクにあるとみなされる。その時点で、車両は誘導経路を逸脱したことになり、代替経路が表示される。
【００４８】
ナビゲーションシステムのユーザにとって、図１７のように誘導経路をシステムが勝手に変更すると戸惑うこともある。そのため図１５に示すように単に復帰方向のみを表示して、実際の復帰経路の選択は運転者にゆだねる方が都合がよいこともあるし、また、この後に説明する図１９に示すように元の誘導経路につながる経路を表示する方が都合がよいこともある。そこで、どのような表示の方法を選択するかは、ユーザによって指定できるようにする。そのために、車載端末装置１に表示モード選択専用のボタンを付けておく。あるいは、代わりにタッチパネルによるソフトボタンを設けておく。また、マイクによる音声入力で、表示モードを選択できるようにしておいてもよい。
【００４９】
図１８は、車載端末装置１において誘導経路までの復帰経路を求めるフローを示した図である。誘導経路までの復帰経路を求めるフローは、代替誘導フラグを利用しない点で、図１６の代替経路を求めるフローと異なるが、多くの部分は同じである。即ち、図１６に示したフローでは、リンクを探索する際に、代替経路フラグがオンになっているノードを持つリンクを辿っていったが、このフローでは、より誘導経路に近くなる様に復帰経路が設定されるリンクを選択するようにして、当初の誘導経路に繋がるリンクを求めてゆく。まず、前処理部分のステップＳ６２７１０ないしステップＳ６２７１３は、代替経路を求めるフローにおけるステップＳ６２７０ないしステップＳ６２７３に同じである。
これらの処理によってノードＮが与えられると、そのノードデータに記載されている同一交差点ＩＤと同一の交差点ＩＤを持つノードデータを、他の道路リンク列データ４２４７の中から検索、抽出する。そして、抽出されたノードの復帰方向フラグがオンならば、Ｌ’＝（Ｎ，Ｎの順方向のノード）とし、復帰方向フラグがオフならば、Ｌ’＝（Ｎ，Ｎの逆方向のノード）とする。ここで、前記同一交差点ＩＤが複数ある場合には、同様のＬ’が複数個得られるので、その場合は、誘導経路に最も近いものを、Ｌとして選択する（Ｓ６２７１４）。
【００５０】
次に、Ｌが誘導経路に含まれるか否かチェックし、誘導経路に含まれない場合は（Ｓ６２７１５でＮｏ）、Ｌi＝Ｌ、ｉ＝ｉ＋１とし（Ｓ６２７１６）、ステップＳ６２７１３ないしステップＳ６２７１５の処理を繰り返す。また、Ｌが誘導経路である場合は（Ｓ６２７１５でＹｅｓ）、それまでに求められたリンク列Ｌ0,…,Ｌiを誘導経路までの復帰経路として出力する（Ｓ６２７１８）。
【００５１】
図１９は、誘導経路までの復帰経路を表示した例である。この図に示すように、図１７の代替経路の表示とは異なり、誘導経路までの復帰経路が表示されるため、いずれ当初の誘導経路又は目的地に到達することが分かっていても、誘導経路とは異なる経路となりうる代替経路の場合に比べ、運転者に安心感を与えることが出来る。
【００５２】
図２０は、同一交差点ＩＤを補足説明するための図である。図２０に示す道路網において道路リンク列とは、例えば、（１，２，４，６）のノード列をつなぐリンク列、（１，３，５，６）のノード列をつなぐリンク列、（２，３，４）のノード列をつなぐリンク列をいう。このとき、各ノードには、交差点ＩＤが付されるが、その交差点ＩＤは、リンク列ごとに別個に付される。そのため、多くの場合、各ノードは複数の交差点ＩＤを持つことになる。図２０において、交差点ＩＤは各ノードの下に記載された番号であり、例えば、ノード２は、交差点ＩＤとして１０２と３０２を持っている。そこで、図７におけるノードデータ４２４８には、そのリンク列データとして与えられる交差点ＩＤと、その交差点と同一の交差点ＩＤを記憶するフィールドが確保されている。なお、同一交差点ＩＤの数は必ずしも１とは限らない。
【００５３】
以上説明した実施の形態において、サーバ装置４は、初めに求めた誘導経路に対して定める地図の切り出し範囲内に含まれる角度迂路について、あらかじめ最短経路アルゴリズムに基づいた復帰経路指示データ４２３を作成し、その復帰経路指示データ４２３を、目的地までの誘導経路を含む配信地図データ４２４にフラグデータという形で組み込んで、車載端末装置に配信する。この復帰経路指示データ４２３により、地図の切り出し範囲内の各道路についてどの方向に走行すれば目的地に接近するのか、そして交差点ではどの道を選択すればより目的地に近くなるのかを求めることが出来る。また、車載端末装置１は、配信された配信地図データ４２４をもとに独力で目的地までの代替経路又は元の誘導経路までの復帰経路を求めることができる。そのため、車載端末装置１は、車両がどこで誘導経路から逸脱しようとも、サーバ装置４と新たな通信をすることなく、最適経路に基づいた代替経路なり、復帰経路なりを表示することができる。
また、当然ながら、車両がさらに逸脱を繰り返して、車載端末装置１が当初に配信を受けた配信地図データ４２４の範囲外に出たときには、車載端末装置１は、サーバ装置４に通信し、リルートを要求する。
【００５４】
＜その他の実施の形態＞
以上、本発明について好適な実施の形態について一例を示したが、本発明は前記実施の形態に限定されず、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
例えば、前記実施の形態においては、サーバ装置４は、復帰経路指示データ４２３を、配信地図データ４２４にフラグデータという形で組み込んで、車載端末装置に配信したが、復帰経路指示データ４２３をそのままの形で車載端末装置１へ配信してもよい。この場合、最短経路ノードの集合｛ｐi｝と復帰方向行列（ｒij ）を、フラグデータを含まない配信地図データとともに車載端末装置１へ配信する。
車載装置１においては、最短経路ノードの集合｛ｐi｝と復帰方向行列（ｒij ）の配信を受ければ、図１５ないし図１９で説明した復帰方向の表示、代替経路の表示及び誘導経路までの復帰経路の表示は問題なく行うことができる。ちなみに、図１５に示す復帰方向フラグは、配信地図データ４２４の道路リンク列データ４２７から各道路リンクの両端のノード番号（交差点ＩＤ）を取り出し、それに基づき復帰方向行列（ｒij ）を参照すれば、容易に表示することができる。また、図１７のような代替経路の表示については、図１６の処理フローで示したステップＳ６２７０ないしＳ６２７３と同様にして開始リンクのノードＮさえ求めれば、代替経路は、最短経路ノードの集合｛ｐi｝によって容易に求めることができる。さらに、図１９の誘導経路につながる復帰経路を求める図１８の処理については、ステップＳ６２７１３及びステップＳ６２７１４においてリンクの両端のノードが求められているので、そのリンクの復帰方向フラグは、復帰方向行列（ｒij ）によって容易に求めることができる。
【図面の簡単な説明】
【００５５】
【図１】本発明が適用される通信型車両ナビゲーションシステムにおける車載端末装置の構成例を示した図である。
【図２】本発明が適用される通信型車両ナビゲーションシステムにおけるサーバ装置の構成例を示した図である。
【図３】端末ソフトウエア及びサーバソフトウエアの構成例を示した図である。
【図４】サーバ装置における誘導経路探索及び復帰経路探索処理のフローを示した図である。
【図５】サーバ装置における誘導経路探索及び復帰経路探索処理の内容を説明するための参考図である。
【図６】配信地図データのデータ構造の例を示した図である。
【図７】配信地図データにおける道路データの詳細な構造の例を示した図である。
【図８】最短経路アルゴリズムを説明するための道路網におけるノード、リンク及びリンクコストの例を示した図である。
【図９】ダイクストラ法による最短経路探索処理のフローを示した図である。
【図１０】ダイクストラ法によって求めた目的地までの最短経路を示した図である。
【図１１】復帰方向行列の成分ｒij を設定する規則を示した図である。
【図１２】図１１の道路網の例に対して求めた復帰方向行列（ｒij ）を示した図である。
【図１３】フラグデータ付加処理のフローを示した図である。
【図１４】走行開始時に車載端末装置に表示される誘導経路の例を示した図である。
【図１５】車載端末装置に誘導経路とともに復帰方向を表示した例である。
【図１６】車載端末装置において代替経路を求めるフローを示した図である。
【図１７】車載端末装置に代替経路を表示した例を示した図である。
【図１８】車載端末装置において誘導経路までの復帰経路を求めるフローを示した図である。
【図１９】車載端末装置に誘導経路までの復帰経路を表示した例を示した図である。
【図２０】同一交差点ＩＤについて補足説明するための図である。
【符号の説明】
【００５６】
１    車載端末装置
２    通信装置
３    公衆通信ネットワーク
４    サーバ装置
４２１    地図データベース
４２３    復帰経路指示データ
４２４    配信地図データ
７１２    誘導経路探索プログラム
７１３    地図切り出しプログラム
７１４    復帰経路探索プログラム
７１５    配信地図変換プログラム
６２２    ロケータプログラム
６２５    誘導経路表示プログラム
６２６    復帰経路表示プログラム
６２７    代替経路表示プログラム
【図１】
2005069751.tif 000003
【図２】
2005069751.tif 000004
【図３】
2005069751.tif 000005
【図４】
2005069751.tif 000006
【図５】
2005069751.tif 000007
【図６】
2005069751.tif 000008
【図７】
2005069751.tif 000009
【図８】
2005069751.tif 000010
【図９】
2005069751.tif 000011
【図１０】
2005069751.tif 000012
【図１１】
2005069751.tif 000013
【図１２】
2005069751.tif 000014
【図１３】
2005069751.tif 000015
【図１４】
2005069751.tif 000016
【図１５】
2005069751.tif 000017
【図１６】
2005069751.tif 000018
【図１７】
2005069751.tif 000019
【図１８】
2005069751.tif 000020
【図１９】
2005069751.tif 000021
【図２０】
2005069751.tif 000022