JP6646731B2 - サーバ装置、通信端末、経路探索システム及びコンピュータプログラム - Google Patents

Description

本発明は、移動体の移動案内を行う為の案内経路を探索するサーバ装置、通信端末、経路探索システム及びコンピュータプログラムに関する。

近年、車両の走行案内を行い、運転者が所望の目的地に容易に到着できるようにしたナビゲーション装置が車両に搭載されていることが多い。ここで、ナビゲーション装置とは、ＧＰＳ受信機などにより自車の現在位置を検出し、その現在位置に対応する地図情報をＤＶＤ−ＲＯＭやＨＤＤなどの記録媒体またはネットワークを通じて取得して液晶モニタに表示することが可能な装置である。また、上記ナビゲーション装置では、所望する目的地を設定すると、出発地（例えば自車の現在位置）から設定された目的地までの最適経路を探索する経路探索機能を備えており、更に、探索された経路（案内経路）に従って走行の案内を行う走行案内機能についても備えている。また、近年は携帯電話機、ＰＤＡ（Personal Digital Assistant）、スマートフォン、パーソナルコンピュータ等においても上記ナビゲーション装置と同様の機能を有するものがある（以下、ナビゲーション装置を含めて通信端末という）。

ここで、日本全国においては毎年新しい道路（新設道路）が建設されている。また、これに伴って、既存の道路がなくなったり、交差点が追加されたり、既存の道路や交差点の形状が変更されたりする。その際、通信端末が有する地図情報が作成された後に新しく作られた新設道路等に関する情報は、地図情報に登録されていないという問題がある。即ち、新設道路等を含まない地図情報を持つ通信端末では、新設道路等が経路探索や案内の対象とならないため、新設道路等を通過しない遠回りの案内経路を探索したり、実在する道路や交差点が地図画像上では案内されない等の適切な走行案内が行われない場合がある。

そこで、近年では経路探索を通信端末側では行わずに最新の地図情報を有する外部のサーバ装置に実行させ、サーバ装置から案内経路を取得する構成（以下、センタールート探索という）について提案されている。しかしながら、センタールート探索を行った場合には、最新の地図情報に基づいて経路が探索できる一方で、案内経路を設定するまでに通信端末とサーバ装置との間で所定回数の通信を行う必要があることから、通信端末で経路探索を行う場合と比較して案内経路を設定するまでにより長い時間が必要となっていた。その結果、経路探索要求を行ってからしばらくの間において案内経路に基づく走行案内を行うことができない問題が生じていた。

そこで、特開２００９−１９９２４号公報には、センタールート探索を行う際において、サーバ装置に加えてナビゲーション装置側でも経路探索を行い、現在位置から所定距離範囲内についてはナビゲーション装置側で探索された経路（以下、ローカルルートという）を用いた案内経路を設定する技術について提案されている。更に、センタールート探索により探索された経路（以下、センタールートという）をナビゲーション装置が受信した場合に、車両の現在位置からローカルルートに沿って所定距離離れた地点がセンタールート上にない場合には、該地点からセンタールートへと接続する経路（以下、接続ルートという）を更に探索し、ローカルルート、接続ルート及びセンタールートの３つのルートを繋ぐ経路を案内経路として設定することについても記載されている。

特開２００９−１９９２４号公報（第７−８頁）

ここで、上記特許文献１の技術では、ナビゲーション装置がサーバ装置へ経路探索の要求を行った時点の車両の現在位置から目的地までの経路がセンタールートとなる。即ち、サーバ装置へ経路探索の要求を行った時点からセンタールートを受信するまでの車両の走行については何ら考慮されずにセンタールートが決定されていた。

従って、サーバ装置へ経路探索の要求を行ってからの車両の走行経路がセンタールート上を走行していれば、センタールートが車両の推奨経路となり得るが、サーバ装置へ経路探索の要求を行ってからの車両の走行経路がセンタールートと異なる経路となった場合（即ちセンタールートを受信した時点の車両の位置がセンタールート上に無い場合）については、必ずしもセンタールートが現在の車両の推奨経路となるとは限らない。

例えば、図１３に示すようにサーバ装置へ経路探索の要求を行た時点の車両の位置が地点Ｘである場合には、地点Ｘから目的地までの推奨経路１０１がセンタールートとして検索され、ナビゲーション装置へと配信される。しかしながら、車両が経路探索要求後にセンタールートと異なる経路を走行し、センタールートを受信した時点で地点Ｙにある場合には、地点Ｙからは推奨経路１０１よりも経路１０２の方が目的地へのより推奨される経路となる。

しかしながら、特許文献１では上述したように接続ルートを探索することによって経路１０２ではなく、センタールートである推奨経路１０１に強引に誘導する経路を案内経路とするので、現在の車両にとって最も推奨される経路以外の経路が案内経路となる問題があった。

本発明は前記従来における問題点を解消するためになされたものであり、サーバ装置へ経路探索の要求を行ってからの移動体（通信端末の設置された車両や通信端末を所持するユーザ等）の移動についても考慮してセンタールートを探索することが可能となるので、現在の移動体に対して最も適切な案内経路を設定することを可能にしたサーバ装置、通信端末、経路探索システム及びコンピュータプログラムを提供することを目的とする。

前記目的を達成するため本発明に係るサーバ装置は、通信端末と双方向通信可能に接続され、前記通信端末から出発地、目的地、及び出発地から目的地への経路探索要求を受信するとともに、受信した前記経路探索要求に応じて探索した経路を前記通信端末へと配信するサーバ装置である。具体的には、前記通信端末から前記経路探索要求を取得した場合に、前記通信端末が有する端末側地図情報を用いて探索された出発地から目的地までの経路である端末推奨経路について、出発地から所定距離分の経路である対象経路に関する経路情報を取得する経路情報取得手段と、前記サーバ装置が有する装置側地図情報と前記経路情報とを用いて、前記対象経路の少なくとも一部を含む目的地までの経路を探索する経路探索手段と、前記経路探索手段により探索された経路を前記通信端末へと配信する経路配信手段と、を有する。
尚、「対象経路に関する経路情報」とは、対象経路の道路列（リンク列）や座標列等の対象経路の具体的な形状を特定する情報以外に、対象経路の始点や終点等の対象経路を特定し得る地点に関する情報についても含む。
また、「対象経路の少なくとも一部を含む経路」とは、対象経路の全体を含む経路に加えて、対象経路の一部区間や対象経路上の地点を含む経路についても含む。
また、「目的地までの経路を探索」とは、コスト値を用いて複数の経路候補の中から最適な経路を選択することに加えて、複数の経路を接続して目的地までの経路を形成すること等についても含む。

また、本発明に係るコンピュータプログラムは、双方向通信可能に接続された通信端末からの経路探索要求に応じて経路を探索するとともに探索された経路を通信端末へと配信するコンピュータプログラムである。具体的には、サーバ装置を、前記通信端末から前記経路探索要求を取得した場合に、前記通信端末が有する端末側地図情報を用いて探索された出発地から目的地までの経路である端末推奨経路について、出発地から所定距離分の経路である対象経路に関する経路情報を取得する経路情報取得手段と、前記サーバ装置が有する装置側地図情報と前記経路情報とを用いて、前記対象経路の少なくとも一部を含む目的地までの経路を探索する経路探索手段と、前記経路探索手段により探索された経路を前記通信端末へと配信する経路配信手段と、して機能させる。

また、本発明に係る通信端末は、サーバ装置と双方向通信可能に接続され、前記サーバ装置へと出発地、目的地、及び出発地から目的地への経路探索要求を送信するとともに、前記経路探索要求に応じて前記サーバ装置において探索及び配信された経路を取得する通信端末である。具体的には、前記通信端末が有する端末側地図情報を用いて出発地から目的地までの経路を探索する端末推奨経路探索手段と、前記経路探索要求とともに、前記端末推奨経路探索手段により探索された経路である端末推奨経路について、出発地から所定距離分の経路である対象経路に関する経路情報を前記サーバ装置へと送信する探索要求送信手段と、前記経路探索要求に応じて前記サーバ装置において前記サーバ装置が有する装置側地図情報と前記経路情報とを用いて探索された経路であって、前記対象経路の少なくとも一部を含む目的地までの経路を、前記サーバ装置から受信する経路受信手段と、を有する。

また、本発明に係る経路探索システムは、通信端末と、前記通信端末と双方向通信可能に接続され、前記通信端末から出発地、目的地、及び出発地から目的地への経路探索要求を受信するとともに、受信した前記経路探索要求に応じて探索した経路を前記通信端末へと配信するサーバ装置とを有する。そして、前記通信端末は、前記通信端末が有する端末側地図情報を用いて出発地から目的地までの経路を探索する端末推奨経路探索手段と、前記経路探索要求とともに、前記端末推奨経路探索手段により探索された経路である端末推奨経路について、出発地から所定距離分の経路である対象経路に関する経路情報を前記サーバ装置へと送信する探索要求送信手段と、前記経路探索要求に応じて前記サーバ装置において探索された経路を前記サーバ装置から受信する経路受信手段と、を有し、前記サーバ装置は、前記経路探索要求及び前記経路情報を前記通信端末から受信する探索要求受信手段と、前記サーバ装置が有する装置側地図情報と前記経路情報とを用いて、前記対象経路の少なくとも一部を含む目的地までの経路を探索する経路探索手段と、前記経路探索手段により探索された経路を前記通信端末へと配信する経路配信手段と、を有する。

前記構成を有する本発明に係るサーバ装置、通信端末、経路探索システム及びコンピュータプログラムによれば、センタールート探索を行う際において、通信端末において探索される推奨経路の内、出発地から所定距離内の経路、即ち経路探索要求をサーバ装置へと送信した後に移動体（通信端末の設置された車両や通信端末を所持するユーザ等）が走行すると予想される経路を含むセンタールートとするので、サーバ装置へ経路探索の要求を行ってからの移動体の移動についても考慮してセンタールートを探索することが可能となる。その結果、現在の移動体に対して最も適切な案内経路を設定することが可能となる。

第１実施形態に係る経路探索システムを示した概略構成図である。 第１実施形態に係る経路探索システムの構成を示したブロック図である。 第１実施形態に係る通信端末の制御系を模式的に示すブロック図である。 第１実施形態に係る経路探索処理プログラムのフローチャートである。 通信端末において探索された端末推奨経路について示した図である。 サーバ側の経路探索処理のサブ処理プログラムのフローチャートである。 基準道路列を示した図である。 サーバ装置において探索されたサーバ推奨経路について示した図である。 第２実施形態に係る経路探索処理プログラムのフローチャートである。 通信端末からサーバ装置へと送信される経路情報について示した図である。 第３実施形態に係る経路探索処理プログラムのフローチャートである。 第３実施形態に係るサーバ側の経路探索処理のサブ処理プログラムのフローチャートである。 従来技術の問題点について説明した図である。

以下、本発明に係るサーバ装置、通信端末、経路探索システム及びコンピュータプログラムを具体化した第１実施形態乃至第３実施形態について図面を参照しつつ詳細に説明する。

〔第１実施形態〕
先ず、第１実施形態に係る経路探索システム１の概略構成について図１及び図２を用いて説明する。図１は第１実施形態に係る経路探索システム１を示した概略構成図である。図２は第１実施形態に係る経路探索システム１の構成を示したブロック図である。

図１に示すように、第１実施形態に係る経路探索システム１は、地図情報センタ２が備えるサーバ装置３と、ユーザ４が所持する通信端末５と、を基本的に有する。また、サーバ装置３と通信端末５は通信ネットワーク網６を介して互いに電子データを送受信可能に構成されている。尚、通信端末５としては例えば携帯電話機、スマートフォン、タブレット型端末、パーソナルコンピュータ、ナビゲーション装置等がある。また、ユーザ４は車両に乗車している状態であっても良いし、車両に乗車していない状態であっても良い。

ここで、サーバ装置３は、通信端末５の要求に応じて経路探索の実行を行う。具体的には、通信端末５において目的地が設定された場合や経路の再探索（リルート）を行う場合に、通信端末５からサーバ装置３へと出発地や目的地等の経路探索に必要な情報が経路探索要求とともに送信される（但し、再探索の場合には目的地に関する情報は必ずしも送信する必要は無い）。そして経路探索要求を受信したサーバ装置３は、サーバ装置３の有する地図情報を用いて経路探索を行い、出発地から目的地までの推奨経路を特定する。その後、特定された推奨経路を要求元の通信端末５へと送信する。そして、通信端末５は受信した推奨経路を案内経路に設定し、案内経路に従って移動案内を行う。それによって、経路探索時点において通信端末５が有する地図情報が古いバージョンの地図情報であったとしても、サーバ装置３が有する最新バージョンの地図情報に基づいて適切な案内経路を設定することが可能となる。また、特に第１実施形態では、サーバ装置３だけではなく通信端末５においても通信端末５が有する地図情報を用いて経路探索を行い、通信端末５で探索された推奨経路（以下、端末推奨経路という）を経路探索要求とともにサーバ装置３へと送信する。そして、サーバ装置３は後述のように端末推奨経路を用いて経路探索を行う。

一方、通信端末５は、ユーザ４が所持し、ナビ機能を備えた情報端末が用いられ、例えば携帯電話機、スマートフォン、タブレット型端末、パーソナルコンピュータ、ナビゲーション装置等が該当する。

ここで、ナビ機能は、ユーザが指定した条件に該当する経路を探索したり、ユーザ４の現在位置周辺の地図画像を表示したり、表示された地図画像中においてユーザ４の現在位置を表示したり、設定された案内経路に沿った移動案内を行う機能が該当する。尚、上記ナビ機能の全てを通信端末５が備えている必要はなく、少なくとも経路の探索を行う機能と設定された案内経路に沿った移動案内を行う機能とを有していれば本願発明を構成することが可能である。

また、通信ネットワーク網６は全国各地に配置された多数の基地局と、各基地局を管理及び制御する通信会社とを含み、基地局及び通信会社を有線（光ファイバー、ＩＳＤＮ等）又は無線で互いに接続することにより構成されている。ここで、基地局は通信端末５との通信をするトランシーバー（送受信機）とアンテナを有する。そして、基地局は通信会社の間で無線通信を行う一方、通信ネットワーク網６の末端となり、基地局の電波が届く範囲（セル）にある通信端末５の通信をサーバ装置３との間で中継する役割を持つ。

続いて、経路探索システム１におけるサーバ装置３の構成について図２を用いてより詳細に説明する。サーバ装置３は、図２に示すようにサーバ制御ＥＣＵ１１と、サーバ制御ＥＣＵ１１に接続された情報記録手段としての装置側地図ＤＢ１２と、サーバ側通信装置１３とを備える。

サーバ制御ＥＣＵ１１（エレクトロニック・コントロール・ユニット）は、サーバ装置３の全体の制御を行う電子制御ユニットであり、演算装置及び制御装置としてのＣＰＵ２１、並びにＣＰＵ２１が各種の演算処理を行うにあたってワーキングメモリとして使用されるＲＡＭ２２、制御用のプログラムのほか、後述の経路探索処理プログラム（図４参照）等が記録されたＲＯＭ２３、ＲＯＭ２３から読み出したプログラムを記憶するフラッシュメモリ２４等の内部記憶装置を備えている。尚、サーバ制御ＥＣＵ１１は、後述の通信端末５のＥＣＵとともに処理アルゴリズムとしての各種手段を有する。例えば、経路情報取得手段は、通信端末５から経路探索要求を取得した場合に、通信端末５が有する地図情報を用いて探索された出発地から目的地までの経路である端末推奨経路について、出発地から所定距離分の経路である対象経路に関する経路情報を取得する。経路探索手段は、サーバ装置３が有する地図情報と経路情報とを用いて、対象経路の少なくとも一部を含む目的地までの経路を探索する。経路配信手段は、経路探索手段により探索された経路を通信端末５へと配信する。

また、装置側地図ＤＢ１２は、外部からの入力データや入力操作に基づいて登録された最新のバージョンの地図情報である装置側地図情報２５が、エリア毎（例えば２０ｋｍ四方のレベル１０のメッシュ毎）に区分されて記憶される記憶手段である。ここで、バージョンとは地図情報が作成された時期を特定する為の作成時期情報であり、バージョンを参照することによって地図情報が作成された時期を特定することが可能となっている。

ここで、上記装置側地図情報２５は、通信端末５に格納されている地図情報と基本的に同一の構成を有しており、道路網を始めとして経路探索、経路案内及び地図表示に必要な各種情報から構成されている。例えば、道路（リンク）に関するリンクデータ、ノード点に関するノードデータ、各交差点に関する交差点データ、施設等の地点に関する地点データ、地図を表示するための地図表示データ、経路を探索するための探索データ、地点を検索するための検索データ等からなる。

探索データとしては、後述のように出発地（例えば車両の現在位置）から設定された目的地までの経路を探索する経路探索処理に使用される各種データについて記録されている。例えば、交差点に対する経路として適正の程度を数値化したコスト（以下、交差点コストという）や道路を構成するリンクに対する経路として適正の程度を数値化したコスト（以下、リンクコストという）等の探索コストを算出する為に使用するコスト算出データが記憶されている。

また、装置側地図ＤＢ１２には、上記装置側地図情報２５とは別に最新バージョンの地図情報に対応して通信端末５において現在位置の特定や案内経路に沿った簡易走行案内を行う為の情報である移動案内情報２６についてもエリア毎（例えば２．５ｋｍ四方のレベル１３のメッシュ毎）に区分されて記憶されている。

ここで、移動案内情報２６は、ユーザの現在位置のマップマッチングを行うのに必要となるマッチングデータと、案内交差点での右左折案内等の案内経路に沿ってユーザに移動を行わせる為の案内に必要となる案内データと、地図画像や案内画面を表示する為の表示データとを含む。尚、マッチングデータは例えば道路形状を特定する為のデータからなる。また、案内データは例えば交差点の形状や交差点と道路の接続関係を特定する為のデータからなる。また、表示データは、通信端末５のディスプレイに道路網を含む地図画像や移動案内を行う為の案内画面を表示する為のデータからなる。

そして、サーバ制御ＥＣＵ１１は、後述のように通信端末５から経路探索要求を受信した場合には、装置側地図情報２５を用いて出発地から目的地までの経路探索を行う。そして、探索された経路を要求のあった通信端末５へと配信する。また、サーバ制御ＥＣＵ１１は、移動案内情報２６についても必要に応じて通信端末５に対して配信を行う。具体的には、通信端末５が今後に移動する可能性のあるエリア（例えば、通信端末５の現在位置周辺、通信端末５で設定された案内経路の周辺）であって、通信端末５が有する地図情報のバージョンが装置側地図情報２５よりも古いエリアを対象として、対象エリアの移動案内情報２６を通信端末５に対して配信するように構成する。

一方、サーバ側通信装置１３は通信端末５と通信ネットワーク網６を介して通信を行う為の通信装置である。また、通信端末５以外にインターネット網や、交通情報センタ、例えば、ＶＩＣＳ（登録商標：Vehicle Information and Communication System）センタやプローブセンタ等から送信された渋滞情報、規制情報、交通事故情報等の各情報から成る交通情報の受信についても可能である。

次に、通信端末５の概略構成について図３を用いて説明する。尚、以下の説明では通信端末５として車両に設置されたナビゲーション装置を用い、移動体として特に車両の走行案内を行う場合を例に挙げて説明する。但し、ナビゲーション装置の代わりに、携帯電話機、タブレット型端末、パーソナルコンピュータ等を用いても良い。また、携帯電話機、タブレット型端末を用いる場合には、車両以外の移動体（例えば、歩行者、自転車等）の移動案内を行うことも可能である。図３は第１実施形態に係る通信端末５であるナビゲーション装置の制御系を模式的に示すブロック図である。

図３に示すように第１実施形態に係る通信端末５は、通信端末５であるナビゲーション装置が搭載された車両（移動体）の現在位置を検出する現在位置検出部３１と、各種のデータが記録されたデータ記録部３２と、入力された情報に基づいて、各種の演算処理を行うナビゲーションＥＣＵ３３と、ユーザからの操作を受け付ける操作部３４と、ユーザに対して地図や目的地までの案内経路を表示する液晶ディスプレイ３５と、経路案内に関する音声ガイダンスを出力するスピーカ３６と、記憶媒体であるＤＶＤを読み取るＤＶＤドライブ３７と、サーバ装置３やＶＩＣＳセンタ等との間で通信を行う通信モジュール３８と、を有する。

以下に、通信端末５を構成する各構成要素について順に説明する。
現在位置検出部３１は、ＧＰＳ４１、車速センサ４２、ステアリングセンサ４３、ジャイロセンサ４４等からなり、現在の車両の位置、方位、車両の走行速度、現在時刻等を検出することが可能となっている。ここで、特に車速センサ４２は、車両の移動距離や車速を検出する為のセンサであり、車両の駆動輪の回転に応じてパルスを発生させ、パルス信号をナビゲーションＥＣＵ３３に出力する。そして、ナビゲーションＥＣＵ３３は発生するパルスを計数することにより駆動輪の回転速度や移動距離を算出する。尚、上記４種類のセンサを通信端末５が全て備える必要はなく、これらの内の１又は複数種類のセンサのみを通信端末５が備える構成としても良い。

また、データ記録部３２は、外部記憶装置及び記録媒体としてのハードディスク（図示せず）と、ハードディスクに記録された端末側地図ＤＢ４５、バージョン管理ＤＢ４６、キャッシュ４７及び所定のプログラム等を読み出すとともにハードディスクに所定のデータを書き込む為のドライバである記録ヘッド（図示せず）とを備えている。尚、データ記録部３２をハードディスクの代わりにメモリーカードやＣＤやＤＶＤ等の光ディスクにより構成しても良い。

ここで、端末側地図ＤＢ４５は、通信端末５における経路探索や走行案内に用いられる端末側地図情報４８が記憶される記憶手段である。

ここで、端末側地図ＤＢ４５に記憶される端末側地図情報４８は、前記した装置側地図情報２５と同様に道路網を始めとして経路探索、経路案内及び地図表示に必要な各種情報から構成されており、例えば、道路（リンク）に関するリンクデータ、ノード点に関するノードデータ、各交差点に関する交差点データ、施設等の地点に関する地点データ、地図を表示するための地図表示データ、経路を探索するための探索データ、地点を検索するための検索データ等からなる。

また、端末側地図ＤＢ４５に記憶される端末側地図情報４８は、不図示の地図配信サーバから配信された地図更新情報や記録メディアから取得した地図更新情報に基づいて、該当箇所のデータを新たなデータに書き換えることによって区画単位（例えばメッシュ単位）で新たなバージョンの地図情報に更新される。また、端末側地図ＤＢ４５には、地図情報に対応して通信端末５において現在位置の特定、案内経路に沿った走行案内、画像の表示を行う為の移動案内情報２６についてもエリア毎（例えば２．５ｋｍ四方のレベル１３のメッシュ毎）に区分されて記憶されている。

また、バージョン管理ＤＢ４６は、現在、端末側地図ＤＢ４５に記憶されている端末側地図情報４８のバージョンを特定する情報（例えばバージョン番号、最終更新日時等）を、地図情報の区画単位（例えばメッシュ単位）毎に記録する記憶手段である。尚、バージョン管理ＤＢ４６は、端末側地図情報４８が新たなバージョンの地図情報に更新されるのに伴って、その内容が更新される。

また、キャッシュ４７は、サーバ装置３から配信された移動案内情報２６が一時的に保管される記憶手段である。第１実施形態に係る経路探索システム１では、前述したように車両が今後に走行する可能性のあるエリア（例えば、車両の現在位置周辺、通信端末５で設定された案内経路の周辺）であって、通信端末５が有する端末側地図情報４８のバージョンが装置側地図情報２５よりも古いエリアを対象として、移動案内情報２６がサーバ装置３から配信され、キャッシュ４７に記憶される。ここで、移動案内情報２６は前述したように最新の地図情報に対応して通信端末５において現在位置の特定、案内経路に沿った簡易走行案内、画像の表示を行う為の情報である。

そして、ナビゲーションＥＣＵ３３は、通信端末５が有する端末側地図情報４８のバージョンが装置側地図情報２５よりも古いエリアに関しては、端末側地図ＤＢ４５に格納する古いバージョンの地図情報や移動案内情報ではなく、キャッシュ４７に格納された新しいバージョンの移動案内情報２６を用いて車両の現在位置の特定、案内経路に沿った走行案内、画像の表示等を行う。尚、キャッシュ４７の記憶領域が不足した場合には、キャッシュ４７に格納された移動案内情報２６の内、優先度の低いものから順に削除される。

一方、ナビゲーションＥＣＵ（エレクトロニック・コントロール・ユニット）３３は、通信端末５の全体の制御を行う電子制御ユニットであり、演算装置及び制御装置としてのＣＰＵ５１、並びにＣＰＵ５１が各種の演算処理を行うにあたってワーキングメモリとして使用されるとともに、経路が探索されたときの経路データ等が記憶されるＲＡＭ５２、制御用のプログラムのほか、後述の経路探索処理プログラム（図４参照）等が記録されたＲＯＭ５３、ＲＯＭ５３から読み出したプログラムを記憶するフラッシュメモリ５４等の内部記憶装置を備えている。尚、ナビゲーションＥＣＵ３３は、サーバ装置３のＥＣＵとともに処理アルゴリズムとしての各種手段を有する。例えば、端末推奨経路探索手段は、出発地から目的地までの経路を探索する。探索要求送信手段は、経路探索要求とともに、端末推奨経路探索手段により探索された経路である端末推奨経路について、出発地から先の連続する道路列を特定する経路情報をサーバ装置３へと送信する。経路受信手段は、経路探索要求に応じてサーバ装置３において探索された経路を受信する、

操作部３４は、走行開始地点としての出発地及び走行終了地点としての目的地を入力する際等に操作され、各種のキー、ボタン等の複数の操作スイッチ（図示せず）を有する。そして、ナビゲーションＥＣＵ３３は、各スイッチの押下等により出力されるスイッチ信号に基づき、対応する各種の動作を実行すべく制御を行う。尚、操作部３４は液晶ディスプレイ３５の前面に設けたタッチパネルを有しても良い。また、マイクと音声認識装置を有しても良い。

また、液晶ディスプレイ３５には、道路を含む地図画像、交通情報、操作案内、操作メニュー、キーの案内、出発地から目的地までの案内経路、案内経路に沿った案内情報、ニュース、天気予報、時刻、メール、テレビ番組等が表示される。尚、液晶ディスプレイ３５の代わりに、ＨＵＤやＨＭＤを用いても良い。

また、スピーカ３６は、ナビゲーションＥＣＵ３３からの指示に基づいて案内経路に沿った走行を案内する音声ガイダンスや、交通情報の案内を出力する。

また、ＤＶＤドライブ３７は、ＤＶＤやＣＤ等の記録媒体に記録されたデータを読み取り可能なドライブである。そして、読み取ったデータに基づいて音楽や映像の再生、端末側地図ＤＢ４５の更新等が行われる。尚、ＤＶＤドライブ３７に替えてメモリーカードを読み書きする為のカードスロットを設けても良い。

また、通信モジュール３８は、例えば、サーバ装置３やＶＩＣＳ（登録商標）センタやプローブセンタ等から送信された地図更新情報、経路情報、移動案内情報、交通情報等の各情報を受信する為の通信装置であり、例えば携帯電話機やＤＣＭが該当する。

続いて、前記構成を有する経路探索システム１において、サーバ装置３及び通信端末５が実行する経路探索処理プログラムについて図４に基づき説明する。図４は第１実施形態に係る経路探索処理プログラムのフローチャートである。ここで、経路探索処理プログラムは、通信端末５において経路探索を開始する条件を満たした場合（例えば目的地の設定操作を受け付けた場合、車両が通信端末５において設定されている案内経路を離脱した場合等）に実行され、センタールート探索を用いて出発地から目的地までの経路を探索するプログラムである。尚、以下の図４及び図６にフローチャートで示されるプログラムは、サーバ装置３や通信端末５が備えているＲＡＭやＲＯＭに記憶されており、ＣＰＵ２１或いはＣＰＵ５１により実行される。

先ず、図４に基づいて通信端末５のＣＰＵ５１が実行する経路探索処理プログラムについて説明する。ステップ（以下、Ｓと略記する）１において、ＣＰＵ５１は、経路探索の開始条件を満たしたか否か判定する。尚、経路探索の開始条件を満たした場合としては、通信端末５において新たな目的地の設定操作を受け付けた場合、車両が通信端末５において設定されている案内経路を離脱した場合（リルート時）等が該当する。

そして、経路探索の開始条件を満たしたと判定された場合（Ｓ１：ＹＥＳ）には、Ｓ２へと移行する。それに対して、経路探索の開始条件を満たしていないと判定された場合（Ｓ１：ＮＯ）には、当該経路探索処理プログラムを終了する。

Ｓ２においてＣＰＵ５１は、通信端末５が有する端末側地図情報４８を用いて出発地から目的地までの経路探索処理を行い、出発地から目的地までの推奨経路（以下、端末推奨経路という）を特定する。具体的には、端末側地図情報４８に含まれるリンクデータ、ノードデータ、探索データ等に基づいて、リンク（道路）に対する経路として適正の程度を数値化したリンクコストや、交差点（ノード）に対する経路として適正の程度を数値化した交差点コストや、走行に必要な費用の程度を数値化した料金コスト等を算出し、算出された各探索コストを用いて端末推奨経路の探索を行う。例えば公知のダイクストラ法を用い、コスト値の合計が最小となる経路を端末推奨経路とする。尚、ダイクストラ法を用いた経路探索処理は既に公知であるので詳細は省略する。また、出発地は車両の現在位置としても良いし、ユーザにより指定された任意の地点（例えば自宅）としても良い。例えば、車両が案内経路を離脱した場合（リルート時）には車両の現在位置が出発地となる。

次に、Ｓ３においてＣＰＵ５１は、前記Ｓ２の経路探索処理によって探索された端末推奨経路を、通信端末５において車両の走行案内を行う対象となる案内経路として仮設定する。その後、前記Ｓ３で仮設定された案内経路に基づいて車両の走行案内が開始される。例えば、自車位置周辺の道路網を含む地図画像を表示したり、右左折の対象となる案内分岐点が車両の所定距離手前に接近した場合には、案内分岐点の拡大図を表示したり、案内分岐点での車両の進行方向を案内する。また、ＣＰＵ５１は、基本的に端末側地図ＤＢ４５に格納された端末側地図情報４８や移動案内情報２６に基づいて上記走行案内を行う。但し、端末側地図ＤＢ４５に格納された端末側地図情報４８や移動案内情報２６が、車両の現在位置周辺エリアにおいて最新のバージョンでない場合については、移動案内情報２６をサーバ装置３から取得し、取得した移動案内情報２６も用いて上記走行案内を行う。尚、移動案内情報２６は、車両のマップマッチングを行うのに必要となるマッチングデータと、案内交差点での右左折案内等の案内経路に沿って車両に走行を行わせる為の案内に必要となる案内データと、地図画像や案内画面を表示する為の表示データとを含むので、端末側地図ＤＢ４５に格納された端末側地図情報４８や移動案内情報２６が案内経路と対応していなかったとしても、少なくとも車両の現在位置は正しい位置に特定し案内することができ、案内交差点では正しい車両の進行方向を案内することが可能となる。

続いて、Ｓ４においてＣＰＵ５１は、出発地から目的地への経路の探索を要求する為の経路探索要求をサーバ装置３へと送信する。ここで、経路探索要求には、経路探索要求の送信元の通信端末５を特定する端末ＩＤと、経路探索の探索条件である出発地（例えば車両の現在位置）と目的地とを特定する情報と、前記Ｓ２で探索された端末推奨経路を特定する経路情報が含まれている。但し、車両が案内経路を外れたことに伴うリルート時においては、前回の探索時と目的地が基本的に同一となるので、目的地を特定する情報については送信しなくても良い。

また、端末推奨経路を特定する経路情報としては、端末推奨経路の全体を特定する情報を送信しても良いが、第１実施形態では出発地から所定距離Ｌ分の経路（以下、対象経路という）を特定する情報を送信する。より具体的には、出発地から先の対象経路に含まれる連続する道路列を特定する情報を送信する。尚、道路列は第１実施形態ではリンク列とし、一部が所定距離Ｌ以内に含まれるリンクについても送信対象に含める。但し、一部のみ所定距離Ｌ以内に含まれるリンクについては送信対象から除外しても良い。

また、所定距離Ｌは、通信端末５の現在の移動速度（通信端末５が特にナビゲーション装置である場合にはナビゲーション装置が搭載された車両の車速に相当）に基づいて設定される。具体的には、通信端末５は車速センサ４２等のセンサを用いて現在の移動速度Ｖを取得し、所定時間Ｔに移動速度Ｖを乗じた距離を所定距離Ｌとする。また、所定時間Ｔは、通信端末５からサーバ装置３に経路探索要求を送信してからサーバ装置３で探索された経路をサーバ装置３から受信するまでの時間に基づいて設定され、具体的には通信状態が悪い場合や目的地が特に遠方である場合についても考慮し、通信端末５からサーバ装置３に経路探索要求を送信してからサーバ装置３で探索された経路をサーバ装置３から受信し終えるまでに必要と考えられる最長の時間とする。所定時間Ｔは例えば１０ｓｅｃとする。即ち、所定距離Ｌは通信端末５からサーバ装置３に経路探索要求を送信してからサーバ装置３で探索された経路をサーバ装置３から受信するまでの間に、通信端末５が移動し得る最長の距離である。尚、所定時間Ｔを、通信端末５からサーバ装置３に経路探索要求を送信してからサーバ装置３で探索された経路をサーバ装置３から受信し終えるまでに必要な最長の時間ではなく、平均時間としても良い。

例えば前記Ｓ２において図５に示す端末推奨経路７１が探索された場合には、端末推奨経路７１を構成する各リンクの内、出発地から所定距離Ｌ以内の対象経路に含まれる連続するリンクａ〜ｄを特定する情報（例えばリンクＩＤ）が経路情報としてサーバ装置３に送信される。

その後、Ｓ５においてＣＰＵ５１は、経路探索要求に応じてサーバ装置３から送信された探索経路情報を受信する。ここで、前記Ｓ５で受信する探索経路情報は、前記Ｓ４で送信した経路探索要求に基づいてサーバ装置３が最新のバージョンの地図情報である装置側地図情報２５を用いて探索した出発地から目的地までの推奨経路（以下、サーバ推奨経路という）に関する情報である。尚、サーバ推奨経路の詳細については後述する。

続いて、Ｓ６においてＣＰＵ５１は、前記Ｓ５で受信した探索経路情報に基づいて、前記Ｓ３で仮設定された案内経路を、サーバ装置３で探索されたサーバ推奨経路へと差し替える。但し、端末推奨経路とサーバ推奨経路が同一経路である場合については差し替えを行う必要は無い。その後は、前記Ｓ６で差し替えられた案内経路に基づいて車両の走行案内が実施される。

次に、サーバ装置３のＣＰＵ２１が実行する経路探索処理プログラムについて説明する。

先ず、Ｓ１１においてＣＰＵ２１は、経路探索の開始条件を満たした通信端末５から送信される経路探索要求を受信する。尚、経路探索要求には、経路探索要求の送信元の通信端末５を特定する端末ＩＤと、経路探索の探索条件である出発地（例えば車両の現在位置）と目的地とを特定する情報と、前記Ｓ２で探索された端末推奨経路を特定する経路情報が含まれている。

次に、Ｓ１２においてＣＰＵ２１は、後述のサーバ側の経路探索処理（図６）を行う。サーバ側の経路探索処理では、後述のように前記Ｓ１１で受信した経路探索要求と、サーバ装置３が有する装置側地図情報２５とを用いて、出発地から目的地までの経路探索処理を行い、出発地から目的地までの推奨経路（サーバ推奨経路）を特定する。尚、サーバ推奨経路は、通信端末５で探索された端末推奨経路の内、出発地から所定距離以内の対象経路の少なくとも一部を含む経路となる。

続いて、Ｓ１３においてＣＰＵ２１は、前記Ｓ１２で特定したサーバ推奨経路を特定する探索経路情報を、経路探索要求の送信元の通信端末５に対して送信する。その結果、サーバ推奨経路が通信端末５において案内経路に設定されることとなる（Ｓ６）。

次に、前記Ｓ１２において実行されるサーバ側の経路探索処理のサブ処理について図６に基づき説明する。図６はサーバ側の経路探索処理のサブ処理プログラムのフローチャートである。

尚、以下のＳ２１及びＳ２２の処理は、前記Ｓ１１で経路探索要求とともに受信した経路情報によって特定される対象経路のリンク列を構成する各リンクを対象として、出発地から近い順に行う。また、経路情報は、前述したように端末推奨経路の内、出発地から所定距離Ｌ以内における出発地から先の連続するリンク列（例えば図５に示す例ではリンクａ〜ｄ）を特定する情報である。

先ず、Ｓ２１においてＣＰＵ２１は、処理対象のリンクがサーバ装置３の有する装置側地図情報２５に含まれるリンクであるか否か、即ち処理対象のリンクが最新バージョンの地図情報において存在するリンクであるか否かを判定する。

そして、処理対象のリンクがサーバ装置３の有する装置側地図情報２５に含まれるリンクであると判定された場合（Ｓ２１：ＹＥＳ）、即ち処理対象のリンクが最新バージョンの地図情報において存在するリンクである場合には、Ｓ２２へと移行する。Ｓ２２においてＣＰＵ２１は、処理対象のリンクを特定する情報（例えばリンクＩＤ）をフラッシュメモリ２４等に保存する。その後、処理対象のリンクを目的地側に隣接するリンクへと変更した後に、Ｓ２１以降の処理を再度実行する。

一方、処理対象のリンクがサーバ装置３の有する装置側地図情報２５に含まれるリンクでないと判定された場合（Ｓ２１：ＮＯ）、即ち処理対象のリンクが最新バージョンの地図情報において存在しないリンク（廃止された道路等）である場合には、Ｓ２３へと移行する。

Ｓ２３においてＣＰＵ２１は、現時点（前記Ｓ２１でＮＯと判定される時点）までに装置側地図情報２５に含まれると判定されて前記Ｓ２２で保存されたリンク列をフラッシュメモリ２４等から読み出す。尚、読み出されるリンク列は、前記Ｓ１１で経路探索要求とともに受信した経路情報によって特定されるリンク列の内、サーバ装置３が有する装置側地図情報２５に含まれ、且つ出発地を含むリンク列部分である。尚、前記Ｓ２３で読み出されたリンク列を、以下では基準道路列と称する。

例えば、前記Ｓ２において図７に示す端末推奨経路７１が探索された場合であって、出発地から所定距離Ｌ以内にあるリンクａ〜ｄの内、リンクａとリンクｂとリンクｄは装置側地図情報２５に含まれるが、リンクｃが装置側地図情報２５に含まれない場合には、リンクｃよりも出発地側にあるリンクａ及びリンクｂが基準道路列となる。尚、出発地に接続するリンクであるリンクａが装置側地図情報２５に含まれない場合については、基準道路列が無いと判断される。

その後、Ｓ２４においてＣＰＵ２１は、サーバ装置３が有する装置側地図情報２５を用いて基準道路列の終点から目的地までの経路探索処理を行い、基準道路列の終点から目的地までの推奨経路（以下、継続推奨経路という）を特定する。具体的には、装置側地図情報２５に含まれる最新バージョンのリンクデータ、ノードデータ、探索データ等に基づいて、リンク（道路）に対する経路として適正の程度を数値化したリンクコストや、交差点（ノード）に対する経路として適正の程度を数値化した交差点コストや、走行に必要な費用の程度を数値化した料金コスト等を算出し、算出された各探索コストを用いて継続推奨経路の探索を行う。例えば公知のダイクストラ法を用い、コスト値の合計が最小となる経路を継続推奨経路とする。尚、ダイクストラ法を用いた経路探索処理は既に公知であるので詳細は省略する。

尚、前記Ｓ２４でＣＰＵ２１は、基準道路列を通過することを探索条件として、基準道路列の始点から目的地までの推奨経路を探索し、探索された経路を継続推奨経路として特定しても良い。

次に、Ｓ２５においてＣＰＵ２１は、基準道路列と前記Ｓ２４で探索された継続推奨経路を接続し、接続された出発地から目的地までの経路を最終的なサーバ推奨経路として特定する。その後、Ｓ１３へと移行し、特定したサーバ推奨経路を特定する探索経路情報を、経路探索要求の送信元の通信端末５に対して送信する。

例えば、前記Ｓ２において図８に示す端末推奨経路７１が探索された場合であって、リンクａ及びリンクｂが基準道路列である場合には、前記Ｓ２４においてリンクｂの終点Ｘから目的地までの推奨経路である継続推奨経路７２が探索される。そして、リンクａ及びリンクｂのリンク列と継続推奨経路７２とを接続した経路がサーバ推奨経路となる。尚、基準道路列が無い場合（例えば出発地に接続するリンクであるリンクａが装置側地図情報２５に含まれない場合）については、出発地から目的地までの通常の経路探索により探索された経路をサーバ推奨経路とする。

また、前記Ｓ１３でＣＰＵ２１は、必ずしもサーバ推奨経路の全経路を特定する情報を送信する必要は無く、基準道路列を除いた部分（即ち継続推奨経路）を特定する情報のみを送信しても良い。その場合には、通信端末５において前記Ｓ２で探索された端末推奨経路にサーバ装置３から送信された継続推奨経路を接続することによって目的地までの経路を特定することが可能となる。

以上詳細に説明した通り、第１実施形態に係る経路探索システム１、サーバ装置３、通信端末５及びサーバ装置３や通信端末５で実行されるコンピュータプログラムでは、経路探索の開始条件を満たした場合に、通信端末５は通信端末５が有する端末側地図情報４８に基づいて出発地から目的地までの経路を探索し（Ｓ２）、経路探索要求とともに、探索された経路である端末推奨経路について、出発地から所定距離分の連続するリンク列を特定する経路情報をサーバ装置３へと送信する。一方で、サーバ装置３は、経路探索要求を受信した場合に、経路情報によって特定されるリンク列の少なくとも一部を含む出発地から目的地までの経路を探索し（Ｓ２４、Ｓ２５）、探索された経路を通信端末５へと配信する（Ｓ１３）ので、サーバ装置３へ経路探索の要求を行ってからの移動体（通信端末の設置された車両や通信端末を所持するユーザ等）の移動についても考慮してセンタールートを探索することが可能となる。その結果、現在の移動体に対して最も適切な案内経路を設定することが可能となる。

〔第２実施形態〕
次に、第２実施形態に係る経路探索システムについて図９及び図１０に基づいて説明する。尚、以下の説明において上記図１乃至図８の第１実施形態に係る経路探索システム１の構成と同一符号は、前記第１実施形態に係る経路探索システム１等の構成と同一あるいは相当部分を示すものである。

この第２実施形態に係る経路探索システム１の概略構成は、第１実施形態に係る経路探索システム１とほぼ同じ構成である。また、各種制御処理も第１実施形態に係る経路探索システム１とほぼ同じ制御処理である。
ただし、第１実施形態に経路探索システム１が、端末推奨経路を特定する経路情報として、出発地から所定距離Ｌ分の対象経路に含まれる道路列を特定する情報を送信するのに対し、第２実施形態に係る経路探索システム１は、対象経路の終点を特定する情報を送信する点で第１実施形態に係る経路探索システム１と異なっている。

以下に、第２実施形態に係る経路探索システム１において、サーバ装置３及び通信端末５が実行する経路探索処理プログラムについて図９に基づき説明する。図９は第２実施形態に係る経路探索処理プログラムのフローチャートである。

先ず、図９に基づいて通信端末５のＣＰＵ５１が実行する経路探索処理プログラムについて説明する。尚、Ｓ３１〜Ｓ３３については第１実施形態に係る経路探索処理プログラム（図４）のＳ１〜Ｓ３と同様の処理であるので説明は省略する。

Ｓ３４においてＣＰＵ５１は、出発地から目的地への経路の探索を要求する為の経路探索要求をサーバ装置３へと送信する。ここで、経路探索要求には、経路探索要求の送信元の通信端末５を特定する端末ＩＤと、経路探索の探索条件である出発地（例えば車両の現在位置）と目的地とを特定する情報と、前記Ｓ３２で探索された端末推奨経路を特定する経路情報が含まれている。但し、車両が案内経路を外れたことに伴うリルート時においては、前回の探索時と目的地が基本的に同一となるので、目的地を特定する情報については送信しなくても良い。

また、端末推奨経路を特定する経路情報としては、端末推奨経路の全体を特定する情報を送信しても良いが、第２実施形態では出発地から所定距離Ｌ分の対象経路を特定する情報を送信する。より具体的には、対象経路の終点を特定する情報を送信する。

また、所定距離Ｌは、第１実施形態と同様に通信端末５の現在の移動速度（通信端末５が特にナビゲーション装置である場合にはナビゲーション装置が搭載された車両の車速に相当）に基づいて設定される。具体的には、通信端末５は車速センサ４２等のセンサを用いて現在の移動速度Ｖを取得し、所定時間Ｔに移動速度Ｖを乗じた距離を所定距離Ｌとする。また、所定時間Ｔは、通信端末５からサーバ装置３に経路探索要求を送信してからサーバ装置３で探索された経路をサーバ装置３から受信するまでの時間に基づいて設定され、具体的には通信状態が悪い場合や目的地が特に遠方である場合についても考慮し、通信端末５からサーバ装置３に経路探索要求を送信してからサーバ装置３で探索された経路をサーバ装置３から受信し終えるまでに必要と考えられる最長の時間とする。所定時間Ｔは例えば１０ｓｅｃとする。即ち、所定距離Ｌは通信端末５からサーバ装置３に経路探索要求を送信してからサーバ装置３で探索された経路をサーバ装置３から受信するまでの間に、通信端末５が移動し得る最長の距離である。尚、所定時間Ｔを、通信端末５からサーバ装置３に経路探索要求を送信してからサーバ装置３で探索された経路をサーバ装置３から受信し終えるまでに必要な最長の時間ではなく、平均時間としても良い。

例えば前記Ｓ３２において図１０に示す端末推奨経路８１が探索された場合には、端末推奨経路８１において、出発地から所定距離Ｌ離れた地点Ｐを特定する情報（例えば座標）が経路情報としてサーバ装置３に送信される。

その後、Ｓ３５においてＣＰＵ５１は、経路探索要求に応じてサーバ装置３から送信された探索経路情報を受信する。ここで、前記Ｓ３５で受信する探索経路情報は、前記Ｓ３４で送信した経路探索要求に基づいてサーバ装置３が最新のバージョンの地図情報である装置側地図情報２５を用いて探索した出発地から目的地までの推奨経路（サーバ推奨経路）に関する情報である。

続いて、Ｓ３６においてＣＰＵ５１は、前記Ｓ３５で受信した探索経路情報に基づいて、前記Ｓ３３で仮設定された案内経路を、サーバ装置３で探索されたサーバ推奨経路へと差し替える。但し、端末推奨経路とサーバ推奨経路が同一経路である場合については差し替えを行う必要は無い。その後は、前記Ｓ３６で差し替えられた案内経路に基づいて車両の走行案内が実施される。

次に、サーバ装置３のＣＰＵ２１が実行する経路探索処理プログラムについて説明する。

先ず、Ｓ４１においてＣＰＵ２１は、経路探索の開始条件を満たした通信端末５から送信される経路探索要求を受信する。尚、経路探索要求には、経路探索要求の送信元の通信端末５を特定する端末ＩＤと、経路探索の探索条件である出発地（例えば車両の現在位置）と目的地とを特定する情報と、前記Ｓ３２で探索された端末推奨経路を特定する経路情報が含まれている。

次に、Ｓ４２においてＣＰＵ２１は、前述したサーバ側の経路探索処理（図６）を行う。但し、第２実施形態ではサーバ装置３側は対象経路の終点しか特定することができないので、Ｓ２１〜Ｓ２３の処理は行わない。また、前記Ｓ２４及びＳ２５ではサーバ装置３が有する装置側地図情報２５を用いて対象経路の終点から目的地までの経路探索処理を行い、対象経路の終点から目的地までの推奨経路をサーバ推奨経路として特定する。サーバ推奨経路は、端末推奨経路の内、出発地から所定距離以内の対象経路の少なくとも一部を含む経路となる。

続いて、Ｓ４３においてＣＰＵ２１は、前記Ｓ４２で特定したサーバ推奨経路を特定する探索経路情報を、経路探索要求の送信元の通信端末５に対して送信する。その結果、通信端末５において前記Ｓ３２で探索された端末推奨経路にサーバ装置３から送信されたサーバ推奨経路を接続することによって目的地までの経路を特定することが可能となる。その結果、サーバ推奨経路が通信端末５において案内経路に設定されることとなる（Ｓ６）。

以上詳細に説明した通り、第２実施形態に係る経路探索システム１、サーバ装置３、通信端末５及びサーバ装置３や通信端末５で実行されるコンピュータプログラムでは、経路探索の開始条件を満たした場合に、通信端末５は通信端末５が有する端末側地図情報４８に基づいて出発地から目的地までの経路を探索し（Ｓ３２）、経路探索要求とともに、探索された経路である端末推奨経路について、出発地から所定距離だけ離れた地点を特定する経路情報をサーバ装置３へと送信する。一方で、サーバ装置３は、経路探索要求を受信した場合に、装置側地図情報２５を用いて経路探索要求とともに受信した経路情報によって特定される地点から目的地までの経路を探索し、探索された経路を通信端末５へと配信する（Ｓ４３）ので、センタールート探索を行う際において、サーバ装置３へ経路探索の要求を行ってからの移動体（通信端末の設置された車両や通信端末を所持するユーザ等）の移動についても考慮してセンタールートを探索することが可能となる。その結果、現在の移動体に対して最も適切な案内経路を設定することが可能となる。また、特に第２実施形態ではサーバ装置３は通信端末５から対象経路の終点のみ取得すれば良く、対象経路の道路列を特定する情報を取得する必要が無くなるので、通信量を削減することが可能であり、通信端末５のセンタールート取得までの時間についても短縮することが可能となる。

〔第３実施形態〕
次に、第３実施形態に係る経路探索システムについて図１１及び図１２に基づいて説明する。尚、以下の説明において上記図１乃至図８の第１実施形態に係る経路探索システム１の構成と同一符号は、前記第１実施形態に係る経路探索システム１等の構成と同一あるいは相当部分を示すものである。

この第３実施形態に係る経路探索システム１の概略構成は、第１実施形態に係る経路探索システム１とほぼ同じ構成である。また、各種制御処理も第１実施形態に係る経路探索システム１とほぼ同じ制御処理である。
ただし、第１実施形態に経路探索システム１が、端末推奨経路を特定する経路情報を通信端末５からサーバ装置３へと送信することによってサーバ装置３に取得させるのに対し、第３実施形態に係る経路探索システム１は、経路情報を通信端末５からサーバ装置３へと送信せずにサーバ装置３自らが経路探索処理を行うことによって経路情報を取得する点で第１実施形態に係る経路探索システム１と異なっている。また、第３実施形態に係るサーバ装置３は、装置側地図ＤＢ１２に最新のバージョンの地図情報（即ち装置側地図情報２５）以外に過去のバージョンの地図情報についても格納されており、且つ端末側地図情報４８の現在のバージョンについてサーバ装置３が把握していることを前提とする。即ち、サーバ装置３は、最新バージョンの地図情報である装置側地図情報２５以外に、通信端末５が現在有している端末側地図情報４８と実質的に同一の地図情報についても有することを前提とする。

以下に、第３実施形態に係る経路探索システム１において、サーバ装置３及び通信端末５が実行する経路探索処理プログラムについて図１１に基づき説明する。図１１は第３実施形態に係る経路探索処理プログラムのフローチャートである。

先ず、図１１に基づいて通信端末５のＣＰＵ５１が実行する経路探索処理プログラムについて説明する。尚、Ｓ５１〜Ｓ５３については第１実施形態に係る経路探索処理プログラム（図４）のＳ１〜Ｓ３と同様の処理であるので説明は省略する。

Ｓ５４においてＣＰＵ５１は、出発地から目的地への経路の探索を要求する為の経路探索要求をサーバ装置３へと送信する。尚、第１実施形態や第２実施形態と異なり、経路探索要求には、前記Ｓ５２で探索された端末推奨経路を特定する経路情報については含まれない。

その後、Ｓ５５においてＣＰＵ５１は、経路探索要求に応じてサーバ装置３から送信された探索経路情報を受信する。ここで、前記Ｓ５５で受信する探索経路情報は、前記Ｓ５４で送信した経路探索要求に基づいてサーバ装置３が最新のバージョンの地図情報である装置側地図情報２５を用いて探索した出発地から目的地までの推奨経路（サーバ推奨経路）に関する情報である。

続いて、Ｓ５６においてＣＰＵ５１は、前記Ｓ５５で受信した探索経路情報に基づいて、前記Ｓ５３で仮設定された案内経路を、サーバ装置３で探索されたサーバ推奨経路へと差し替える。但し、端末推奨経路とサーバ推奨経路が同一経路である場合については差し替えを行う必要は無い。その後は、前記Ｓ５６で差し替えられた案内経路に基づいて車両の走行案内が実施される。

次に、サーバ装置３のＣＰＵ２１が実行する経路探索処理プログラムについて説明する。

先ず、Ｓ６１においてＣＰＵ２１は、経路探索の開始条件を満たした通信端末５から送信される経路探索要求を受信する。尚、経路探索要求には、経路探索要求の送信元の通信端末５を特定する端末ＩＤと、経路探索の探索条件である出発地（例えば車両の現在位置）と目的地とを特定する情報が含まれている。

次に、Ｓ６２においてＣＰＵ２１は、後述のサーバ側の経路探索処理（図１２）を行う。サーバ側の経路探索処理では、後述のように前記Ｓ１１で受信した経路探索要求と、サーバ装置３が有する装置側地図情報２５とを用いて、出発地から目的地までの経路探索処理を行い、出発地から目的地までの推奨経路（サーバ推奨経路）を特定する。また、サーバ装置３は、サーバ装置３が有する端末側地図情報４８を用いて端末推奨経路を探索し、探索された端末推奨経路の内、出発地から所定距離以内の対象経路の少なくとも一部を含む経路をサーバ推奨経路とする。

続いて、Ｓ６３においてＣＰＵ２１は、前記Ｓ６２で特定したサーバ推奨経路を特定する探索経路情報を、経路探索要求の送信元の通信端末５に対して送信する。その結果、サーバ推奨経路が通信端末５において案内経路に設定されることとなる（Ｓ５６）。

次に、前記Ｓ６２において実行されるサーバ側の経路探索処理のサブ処理について図１２に基づき説明する。図１２はサーバ側の経路探索処理のサブ処理プログラムのフローチャートである。

先ず、Ｓ７１においてＣＰＵ２１は、サーバ装置３が有する端末側地図情報４８（端末側地図情報４８と装置側地図情報２５が同じバージョンである場合には装置側地図情報２５でも良い）を用いて出発地から目的地までの経路探索処理を行い、出発地から目的地までの推奨経路（端末推奨経路）を特定する。尚、前述したようにサーバ装置３は、装置側地図ＤＢ１２に最新のバージョンの地図情報（即ち装置側地図情報２５）以外に過去のバージョンの地図情報についても格納されており、端末側地図情報４８の現在のバージョンに基づいて端末側地図情報４８を特定することが可能である。尚、地図情報以外に経路探索に影響を与える情報（例えば交通情報等）についても、サーバ装置３は通信端末５と同様に取得することとする。従って、前記Ｓ７１において探索される経路は前記Ｓ５２で探索される経路と基本的に同一となる。即ち、前記Ｓ７１はサーバ装置３が、通信端末５の有する地図情報を用いて探索を行った場合に探索されると予想される推奨経路を、通信端末５と通信を行うことなく取得する処理となる。

続いて、Ｓ７２においてＣＰＵ２１は、前記Ｓ７１で特定された端末推奨経路の内、出発地から所定距離Ｌ分の対象経路を特定する。

そして、以下のＳ７３及びＳ７４の処理は、前記Ｓ７２で特定された対象経路のリンク列を構成する各リンクを対象として、出発地から近い順に行う。尚、以降のＳ７３〜Ｓ７７については第１実施形態に係る経路探索処理プログラム（図６）のＳ２１〜Ｓ２５と同様の処理であるので説明は省略する。その後、Ｓ６３へと移行する。

Ｓ６３でＣＰＵ２１は、前記Ｓ７３〜Ｓ７７で特定されたサーバ推奨経路を特定する探索経路情報を、経路探索要求の送信元の通信端末５に対して送信する。

以上詳細に説明した通り、第３実施形態に係る経路探索システム１、サーバ装置３、通信端末５及びサーバ装置３や通信端末５で実行されるコンピュータプログラムでは、経路探索の開始条件を満たした場合に、サーバ装置３は通信端末５が有する端末側地図情報４８に基づいて出発地から目的地までの経路を探索し（Ｓ７１）、探索された経路である端末推奨経路について、出発地から所定距離分の連続するリンク列の少なくとも一部を含む出発地から目的地までの経路を探索し（Ｓ７６、Ｓ７７）、探索された経路を通信端末５へと配信する（Ｓ６３）ので、サーバ装置３へ経路探索の要求を行ってからの移動体（通信端末の設置された車両や通信端末を所持するユーザ等）の移動についても考慮してセンタールートを探索することが可能となる。その結果、現在の移動体に対して最も適切な案内経路を設定することが可能となる。また、特に第３実施形態ではサーバ装置３は通信端末５から端末推奨経路に関する情報を取得する必要が無くなるので、通信量を大きく削減することが可能であり、通信端末５のセンタールート取得までの時間についても短縮することが可能となる。

尚、本発明は前記実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の改良、変形が可能であることは勿論である。
例えば、第１実施形態では、前記Ｓ２１〜Ｓ２３の基準道路列の特定に係る処理をサーバ装置３が行う構成としているが通信端末５が行う構成としても良い。その場合には、端末側地図情報４８にあって装置側地図情報２５には無いリンクを特定する情報を、通信端末５が有する或いはサーバ装置３から取得する必要がある。

また、第１実施形態や第３実施形態では、基準道路列の終点から目的地までの推奨経路である継続推奨経路を探索し（Ｓ２４、Ｓ７６）、基準道路列と継続推奨経路を接続することによってサーバ推奨経路としているが、基準道路列の終点以外の点（例えば終点よりも出発地側のノード）から目的地までの推奨経路を継続推奨経路として探索しても良い。

また、第１実施形態や第３実施形態では、サーバ装置３は経路情報として対象経路に含まれる道路列（リンク列）を取得しているが、対象経路を特定し得る情報であれば他の情報を経路情報として取得しても良い。例えば、対象経路上の座標列を経路情報として取得しても良い。

また、第１実施形態や第３実施形態では、基準道路列をリンク単位で特定しているが、地図情報において道路を区画する単位であればリンク単位以外の単位で特定しても良い。

また、第１実施形態乃至第３実施形態では、通信端末５がサーバ装置３からサーバ推奨経路を受信するまでの間において、端末推奨経路を案内経路に仮設定している（Ｓ３）が、端末推奨経路の案内経路への仮設定は行わないようにしても良い。

また、本発明に係るサーバ装置、通信端末、経路探索システム及びコンピュータプログラムを具体化した実施例について上記に説明したが、サーバ装置は以下の構成を有することも可能であり、その場合には以下の効果を奏する。

例えば、第１の構成は以下のとおりである。
通信端末（５）と双方向通信可能に接続され、前記通信端末から出発地、目的地、及び出発地から目的地への経路探索要求を受信するとともに、受信した前記経路探索要求に応じて探索した経路を前記通信端末へと配信するサーバ装置（３）において、前記通信端末から前記経路探索要求を取得した場合に、前記通信端末が有する端末側地図情報（４８）を用いて探索された出発地から目的地までの経路である端末推奨経路（７１、８１）について、出発地から所定距離分の経路である対象経路に関する経路情報を取得する経路情報取得手段（１１）と、前記サーバ装置が有する装置側地図情報（２５）と前記経路情報とを用いて、前記対象経路の少なくとも一部を含む目的地までの経路を探索する経路探索手段（１１）と、前記経路探索手段により探索された経路を前記通信端末へと配信する経路配信手段（１１）と、を有する。
上記構成を有するサーバ装置によれば、センタールート探索を行う際において、通信端末において探索される推奨経路の内、出発地から所定距離内の経路、即ち経路探索要求をサーバ装置へと送信した後に移動体（通信端末の設置された車両や通信端末を所持するユーザ等）が走行すると予想される経路を含むセンタールートとするので、サーバ装置へ経路探索の要求を行ってからの移動体の移動についても考慮してセンタールートを探索することが可能となる。その結果、現在の移動体に対して最も適切な案内経路を設定することが可能となる。

また、第２の構成は以下のとおりである。
前記端末推奨経路（７１、８１）の探索は前記通信端末（５）において行われ、前記経路情報取得手段（１１）は、前記端末推奨経路を探索した前記通信端末から前記経路情報を取得する。
上記構成を有するサーバ装置によれば、通信端末において探索された推奨経路の内、出発地から所定距離内の経路、即ち経路探索要求をサーバ装置へと送信した後に移動体が走行すると予想される経路を含むセンタールートとするので、サーバ装置へ経路探索の要求を行ってからの移動体の移動についても考慮してセンタールートを探索することが可能となる。

また、第３の構成は以下のとおりである。
前記装置側地図情報（２５）に加えて前記端末側地図情報（４８）についても有し、前記経路情報取得手段（１１）は、前記端末側地図情報を用いて前記端末推奨経路（７１、８１）を探索し、探索された前記端末推奨経路に基づいて前記経路情報を取得する。
上記構成を有するサーバ装置によれば、通信端末において探索されると予想される推奨経路の内、出発地から所定距離内の経路、即ち経路探索要求をサーバ装置へと送信した後に移動体が走行すると予想される経路を含むセンタールートとするので、サーバ装置へ経路探索の要求を行ってからの移動体の移動についても考慮してセンタールートを探索することが可能となる。また、サーバ装置は通信端末から端末推奨経路に関する情報を取得する必要が無くなるので、通信量を大きく削減することが可能であり、通信端末のセンタールート取得までの時間についても短縮することが可能となる。

また、第４の構成は以下のとおりである。
前記経路情報は、前記対象経路に含まれる道路列であって、前記経路探索手段（１１）は、前記道路列の少なくとも一部を通過する目的地までの経路を探索する。
上記構成を有するサーバ装置によれば、通信端末において探索される推奨経路の内、出発地から所定距離内の経路、即ち経路探索要求をサーバ装置へと送信した後に移動体（通信端末の設置された車両や通信端末を所持するユーザ等）が走行すると予想される経路の道路列を含む経路をセンタールートとするので、サーバ装置へ経路探索の要求を行ってからの移動体の移動についても考慮してセンタールートを探索することが可能となる。

また、第５の構成は以下のとおりである。
前記経路情報は、前記道路列を地図情報において道路を区画する道路区画単位で特定する。
上記構成を有するサーバ装置によれば、道路列を経路探索に用いる道路区画単位で特定することが可能となるので、道路列を含む目的地までの経路を装置側地図情報を用いて適切に探索することが可能となる。

また、第６の構成は以下のとおりである。
前記経路特定手段（１１）は、前記経路情報によって特定される前記道路列を構成する各道路区画について、出発地から順に前記装置側地図情報（２５）に含まれる道路区画であるか否かを判定し、前記装置側地図情報に含まれない道路区画があると判定された場合に、該判定時点までに前記装置側地図情報に含まれると判定された道路区画を通過する目的地までの経路を探索する。
上記構成を有するサーバ装置によれば、経路情報によって特定される道路列を構成する各道路区画と装置側地図情報とを比較することによって、経路情報によって特定される道路列の内、装置側地図情報に含まれ、且つ出発地を含む道路列部分をセンタールートに含める道路列として適切に抽出することが可能となる。

また、第７の構成は以下のとおりである。
前記経路情報は、前記対象経路の終点であって、前記経路探索手段（１１）は、前記対象経路の終点から目的地までの経路を探索する。
上記構成を有するサーバ装置によれば、通信端末において探索される推奨経路の内、出発地から所定距離内の経路、即ち経路探索要求をサーバ装置へと送信した後に移動体（通信端末の設置された車両や通信端末を所持するユーザ等）が走行すると予想される経路の終点を含む経路をセンタールートとするので、サーバ装置へ経路探索の要求を行ってからの移動体の移動についても考慮してセンタールートを探索することが可能となる。

また、第８の構成は以下のとおりである。
前記所定距離は、前記通信端末（５）の移動速度に基づく距離である。
上記構成を有するサーバ装置によれば、通信端末の移動速度に応じて対象経路の長さを決定するので、経路探索要求をサーバ装置へと送信した後に移動体（通信端末の設置された車両や通信端末を所持するユーザ等）が走行すると予想される経路を対象経路として特定することが可能となる。また、対象経路の長さを必要以上に長くすることなく、通信端末との間の通信量をできる限り削減することが可能となる。

また、第９の構成は以下のとおりである。
前記所定距離は、前記通信端末（５）が前記サーバ装置（３）に前記経路探索要求を送信してから前記経路探索手段（１１）により探索された経路を受信するまでの時間に基づく距離である。
上記構成を有するサーバ装置によれば、経路探索要求をサーバ装置へと送信した後に移動体（通信端末の設置された車両や通信端末を所持するユーザ等）が走行すると予想される経路を対象経路として特定することが可能となる。また、対象経路の長さを必要以上に長くすることなく、通信端末との間の通信量をできる限り削減することが可能となる。

また、第１０の構成は以下のとおりである。
前記探索要求受信手段（１１）は、移動体が前記通信端末（５）において設定されている案内経路から離脱した場合に、前記経路探索要求を前記通信端末から受信する。
上記構成を有するサーバ装置によれば、特に移動体が案内経路から離脱した場合において、離脱後に長時間にわたって案内経路に基づく移動案内が行われない事象が生じることを防止することができる。また、通信端末の有する地図情報がサーバ装置の有する地図情報と比べて古いバージョンの地図情報であったとしても、途中で分断されることのない適切な案内経路を再探索し、設定することが可能となる。

１ 経路探索システム
２ 地図情報センタ
３ サーバ装置
４ ユーザ
５ 通信端末
１１ サーバ制御ＥＣＵ
１２ 装置側地図ＤＢ
２１ ＣＰＵ
２２ ＲＡＭ
２３ ＲＯＭ
２４ フラッシュメモリ
２５ 装置側地図情報
２６ 移動案内情報
３３ ナビゲーションＥＣＵ
４５ 端末側地図ＤＢ
４８ 端末側地図情報
５１ ＣＰＵ
５２ ＲＡＭ
５３ ＲＯＭ
５４ フラッシュメモリ
７１、８１ 端末推奨経路
７２ 継続推奨経路

Claims (14)

1. 通信端末と双方向通信可能に接続され、前記通信端末から出発地、目的地、及び出発地から目的地への経路探索要求を受信するとともに、受信した前記経路探索要求に応じて探索した経路を前記通信端末へと配信するサーバ装置において、
   前記通信端末から前記経路探索要求を取得した場合に、前記通信端末が有する端末側地図情報を用いて探索された出発地から目的地までの経路である端末推奨経路について、出発地から所定距離分の経路である対象経路に関する経路情報を取得する経路情報取得手段と、
   前記サーバ装置が有する装置側地図情報と前記経路情報とを用いて、前記対象経路の少なくとも一部を含む目的地までの経路を探索する経路探索手段と、
   前記経路探索手段により探索された経路を前記通信端末へと配信する経路配信手段と、を有するサーバ装置。
2. 前記経路配信手段は、前記経路探索手段により探索された経路であるサーバ推奨経路を前記通信端末へと配信することによって、前記端末推奨経路から前記サーバ推奨経路へと前記通信端末の案内経路の差し替えを行わせる請求項１に記載のサーバ装置。
3. 前記端末推奨経路の探索は前記通信端末において行われ、
   前記経路情報取得手段は、前記端末推奨経路を探索した前記通信端末から前記経路情報を取得する請求項１又は請求項２に記載のサーバ装置。
4. 前記装置側地図情報に加えて前記端末側地図情報についても有し、
   前記経路情報取得手段は、前記端末側地図情報を用いて前記端末推奨経路を探索し、探索された前記端末推奨経路に基づいて前記経路情報を取得する請求項１又は請求項２に記載のサーバ装置。
5. 前記経路情報は、前記対象経路に含まれる道路列であって、
   前記経路探索手段は、前記道路列の少なくとも一部を通過する目的地までの経路を探索する請求項１乃至請求項４のいずれかに記載のサーバ装置。
6. 前記経路情報は、前記道路列を地図情報において道路を区画する道路区画単位で特定する情報である請求項５に記載のサーバ装置。
7. 前記経路探索手段は、
   前記経路情報によって特定される前記道路列を構成する各道路区画について、出発地から順に前記装置側地図情報に含まれる道路区画であるか否かを判定し、
   前記装置側地図情報に含まれない道路区画があると判定された場合に、該判定時点までに前記装置側地図情報に含まれると判定された道路区画を通過する目的地までの経路を探索する請求項６に記載のサーバ装置。
8. 前記経路情報は、前記対象経路の終点であって、
   前記経路探索手段は、前記対象経路の終点から目的地までの経路を探索する請求項１乃至請求項４のいずれかに記載のサーバ装置。
9. 前記所定距離は、前記通信端末の移動速度に基づく距離である請求項１乃至請求項８のいずれかに記載のサーバ装置。
10. 前記所定距離は、前記通信端末が前記サーバ装置に前記経路探索要求を送信してから前記経路探索手段により探索された経路を受信するまでの時間に基づく距離である請求項１乃至請求項９のいずれかに記載のサーバ装置。
11. 移動体が前記通信端末において設定されている案内経路から離脱した場合に、前記経路探索要求を前記通信端末から受信する請求項１乃至請求項１０のいずれかに記載のサーバ装置。
12. 通信端末と双方向通信可能に接続され、前記通信端末から出発地、目的地、及び出発地から目的地への経路探索要求を受信するとともに、受信した前記経路探索要求に応じて探索した経路を前記通信端末へと配信するサーバ装置を、
    前記通信端末から前記経路探索要求を取得した場合に、前記通信端末が有する端末側地図情報を用いて探索された出発地から目的地までの経路である端末推奨経路について、出発地から所定距離分の経路である対象経路に関する経路情報を取得する経路情報取得手段と、
    前記サーバ装置が有する装置側地図情報と前記経路情報とを用いて、前記対象経路の少なくとも一部を含む目的地までの経路を探索する経路探索手段と、
    前記経路探索手段により探索された経路を前記通信端末へと配信する経路配信手段と、して機能させる為のコンピュータプログラム。
13. サーバ装置と双方向通信可能に接続され、前記サーバ装置へと出発地、目的地、及び出発地から目的地への経路探索要求を送信するとともに、前記経路探索要求に応じて前記サーバ装置において探索及び配信された経路を取得する通信端末において、
    前記通信端末が有する端末側地図情報を用いて出発地から目的地までの経路を探索する端末推奨経路探索手段と、
    前記経路探索要求とともに、前記端末推奨経路探索手段により探索された経路である端末推奨経路について、出発地から所定距離分の経路である対象経路に関する経路情報を前記サーバ装置へと送信する探索要求送信手段と、
    前記経路探索要求に応じて前記サーバ装置において前記サーバ装置が有する装置側地図情報と前記経路情報とを用いて探索された経路であって、前記対象経路の少なくとも一部を含む目的地までの経路を、前記サーバ装置から受信する経路受信手段と、を有する通信端末。
14. 通信端末と、前記通信端末と双方向通信可能に接続され、前記通信端末から出発地、目的地、及び出発地から目的地への経路探索要求を受信するとともに、受信した前記経路探索要求に応じて探索した経路を前記通信端末へと配信するサーバ装置とを有する経路探索システムにおいて、
    前記通信端末は、
    前記通信端末が有する端末側地図情報を用いて出発地から目的地までの経路を探索する端末推奨経路探索手段と、
    前記経路探索要求とともに、前記端末推奨経路探索手段により探索された経路である端末推奨経路について、出発地から所定距離分の経路である対象経路に関する経路情報を前記サーバ装置へと送信する探索要求送信手段と、
    前記経路探索要求に応じて前記サーバ装置において探索された経路を前記サーバ装置から受信する経路受信手段と、を有し、
    前記サーバ装置は、
    前記経路探索要求及び前記経路情報を前記通信端末から受信する探索要求受信手段と、
    前記サーバ装置が有する装置側地図情報と前記経路情報とを用いて、前記対象経路の少なくとも一部を含む目的地までの経路を探索する経路探索手段と、
    前記経路探索手段により探索された経路を前記通信端末へと配信する経路配信手段と、を有する経路探索システム。

Images