(57)【特許請求の範囲】
【請求項１】
時刻毎の交通情報に基づく複数の交通状況を複数の交通状況パターンに分類する交通状況分類手段と、
前記複数の交通状況パターンの各々に対応して、複数の地点間のすべての組合せについての経路探索演算を行い、前記経路探索演算により得られるすべての経路を経路データベースに格納する経路データベース生成手段と、
前記複数の交通状況パターンの中から、現況交通情報に基づく交通状況に類似した特定交通状況パターンを出力する交通状況照合手段と、
前記交通状況照合手段により出力された前記特定交通状況パターンに基づき、前記経路データベースを参照して、出発地から目的地までの第１経路を検索する経路情報検索手段と、
前記現況交通情報に基づく指標と前記特定交通状況パターンに基づく基準とを比較する比較手段と、
前記現況交通情報に基づく経路探索演算により、前記出発地から前記目的地までの第２経路を探索する動的経路探索手段と、
前記比較手段による前記指標と前記基準とを比較した結果に応じて、前記第１経路および前記第２経路のいずれか一方を外部装置へ配信する経路情報配信手段とを備えることを特徴とする経路案内システム。
【請求項２】
請求項１に記載の経路案内システムにおいて、
前記比較手段によって前記指標と前記基準とが比較された結果、前記比較手段によって前記現況交通情報と前記特定交通状況パターンとが互いに類似すると判定されたとき、前記経路情報配信手段は前記第１経路を配信し、前記比較手段によって前記現況交通情報と前記特定交通状況パターンとが互いに類似しないと判定されたとき、前記経路情報配信手段は前記第２経路を配信することを特徴とする経路案内システム。
【請求項３】
請求項２に記載の経路案内システムにおいて、
前記交通状況分類手段は、前記複数の交通状況をクラスタリングにより複数のクラスターに分類し、
前記複数の交通状況パターンの各々は、前記複数のクラスターの各クラスターに対応することを特徴とする経路案内システム。
【請求項４】
請求項３に記載の経路案内システムにおいて、
前記複数の交通状況の各々は、複数の区間道路のそれぞれに対応する複数の移動コストに関する複数の成分を含む交通情報ベクトルで表され、
前記複数の交通状況パターンの各々は前記各クラスターの重心に対応する前記交通情報ベクトルで表され、
前記交通状況照合手段は、前記複数のクラスターのそれぞれの重心に対応する複数の交通情報ベクトルのうち、前記現況交通情報に基づく交通状況を表す前記交通情報ベクトルから最も短い距離にある前記交通情報ベクトルで表される交通状況パターンを、前記特定交通状況パターンとして出力することを特徴とする経路案内システム。
【請求項５】
請求項４に記載の経路案内システムにおいて、
前記特定交通状況パターンは、前記複数のクラスターのうちの特定クラスターに対応し、
前記指標は、前記最も短い距離であり、
前記基準は、前記特定クラスターのクラスター半径であり、
前記比較手段は、前記指標と前記基準とを比較した結果、前記指標が前記基準以下のとき、前記現況交通情報と前記特定交通状況パターンとが互いに類似すると判定し、前記指標が前記基準よりも大きいとき、前記現況交通情報と前記特定交通状況パターンとが互いに類似しないと判定することを特徴とする経路案内システム。
【請求項６】
請求項１に記載の経路案内システムにおいて、
前記指標は、前記第２経路に対する前記第１経路の近似精度の低下を示し、
前記基準として予め所定値が設定され、
前記経路情報配信手段は前記第１経路を配信するとともに、
前記比較手段によって前記指標と前記基準とが比較された結果、前記指標が前記基準よりも大きいとき、前記経路情報配信手段は前記第２経路を配信することを特徴とする経路案内システム。
【請求項７】
請求項６に記載の経路案内システムにおいて、
前記交通状況分類手段は、前記複数の交通状況をクラスタリングにより複数のクラスターに分類し、
前記複数の交通状況パターンの各々は、前記複数のクラスターの各クラスターに対応することを特徴とする経路案内システム。
【請求項８】
請求項７に記載の経路案内システムにおいて、
前記複数の交通状況の各々は、複数の区間道路のそれぞれに対応する複数の移動コストに関する複数の成分を含む交通情報ベクトルで表され、
前記複数の交通状況パターンの各々は前記各クラスターの重心に対応する前記交通情報ベクトルで表され、
前記交通状況照合手段は、前記複数のクラスターのそれぞれの重心に対応する複数の交通情報ベクトルのうち、前記現況交通情報に基づく交通状況を表す前記交通情報ベクトルから最も短い距離にある前記交通情報ベクトルで表される交通状況パターンを、前記特定交通状況パターンとして出力することを特徴とする経路案内システム。
【請求項９】
請求項８に記載の経路案内システムにおいて、
前記第１経路が前記外部装置の画面に表示された後に前記第２経路が前記画面に表示されるように、前記経路情報配信手段は、前記第１経路を前記外部装置へ配信した後、前記第２経路を前記外部装置へ配信することを特徴とする経路案内システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は経路案内システムに関する。
【背景技術】
【０００２】
特許文献１には、交通管制センターが車両に対して目的地までの経路についての情報提供を行う際に、その時点での道路条件に応じた経路木を、過去に計算した経路木の中から見つけて車両に送信する技術が開示されている。
【０００３】
特許文献２には、交通情報ベクトルに対する主成分分析により得られる基底の線形合成により、交通情報を近似表現する技術が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平８−２６１７７３号公報
【特許文献２】特開２００６−２５１９４１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１に開示された技術によると、オフライン処理で計算されてデータベースに記憶される基準経路木は、平日／休日の別等の経路計算条件種別毎に計算される。そうした経路計算条件種別だけで道路条件が定まることはなく、実際には同一の経路計算条件種別に対して異なる道路条件が生じる場合がある。そのため、経路計算条件種別を考慮しても、必ずしも実際の道路条件とは一致しない道路条件に応じた基準経路木が計算されてしまう可能性がある。
【課題を解決するための手段】
【０００６】
請求項１に記載の経路案内システムは、時刻毎の交通情報に基づく複数の交通状況を複数の交通状況パターンに分類する交通状況分類手段と、複数の交通状況パターンの各々に対応して、複数の地点間のすべての組合せについての経路探索演算を行い、経路探索演算により得られるすべての経路を経路データベースに格納する経路データベース生成手段と、複数の交通状況パターンの中から、現況交通情報に基づく交通状況に類似した特定交通状況パターンを出力する交通状況照合手段と、交通状況照合手段により出力された特定交通状況パターンに基づき、経路データベースを参照して、出発地から目的地までの第１経路を検索する経路情報検索手段と、現況交通情報に基づく指標と特定交通状況パターンに基づく基準とを比較する比較手段と、現況交通情報に基づく経路探索演算により、出発地から目的地までの第２経路を探索する動的経路探索手段と、比較手段による指標と基準とを比較した結果に応じて、第１経路および第２経路のいずれか一方を外部装置へ配信する経路情報配信手段とを備えることを特徴とする。
【発明の効果】
【０００７】
本発明による経路案内システムは、現況交通情報に基づく動的経路に近似した近似経路を速やかに出力することができる。
【図面の簡単な説明】
【０００８】
【図１】第１の実施の形態における経路案内システムの構成図である。
【図２】経路データベースの内容を示す図である。
【図３】経路案内インターフェースの表示画面である。
【図４】交通情報ベクトルの特徴空間に射影した様子を示す模式図である。
【図５】交通情報ベクトルを特徴空間でクラスタリングした様子を示す模式図である。
【図６】特徴空間における交通状況照合を示す模式図である。
【図７】クラスター半径の算出方法を示す模式図である。
【図８】クラスター半径の算出方法を示す模式図である。
【図９】現況交通情報と交通状況パターンとの類似度判定を示す模式図である。
【図１０】経路案内システムの処理フローを示す図である。
【図１１】経路案内システムの処理フローを示す図である。
【図１２】第２の実施の形態における経路案内システムの構成図である。
【図１３】経路案内システムの処理フローを示す図である。
【発明を実施するための形態】
【０００９】
以下、図面を用いて本発明の実施の形態について説明する。
【００１０】
−−−第１の実施の形態−−−
図１は、第１の実施の形態における経路案内システム１００の構成例を表す図である。経路案内システム１００は、交通情報データベース１０１と、交通状況分類装置１０２と、交通状況パターン１０３と、経路データベース生成装置１０４と、経路データベース１０５と、現況交通情報１０６と、交通状況照合装置１０７と、経路情報検索装置１０８と、地図データベース１１０と、クラスター半径計算装置１１１と、クラスター距離判定装置１１２と、動的経路探索装置１１３とを有する。ナビゲーション装置１５０は、経路案内システム１００の外部装置であり、経路案内インターフェース１０９を有する。経路案内システム１００とナビゲーション装置１５０との間の入出力は、通信を介して行われる。
【００１１】
交通情報データベース１０１には、リンク旅行時間またはリンク代表速度などの数値データで表された過去の交通情報が格納されている。
【００１２】
交通状況分類装置１０２は、交通情報データベース１０１に格納された交通情報を読み出し、クラスタリングによって代表的な複数の交通状況パターンを生成する。クラスタリングの手法には様々な公知の手法がある。交通状況分類装置１０２は、例えばＫ−ｍｅａｎｓ法を用いて過去の交通状況のクラスタリングを行う。交通状況分類装置１０２が行う処理の詳細は後述する。
【００１３】
交通状況パターン１０３は交通状況分類装置によって生成される。交通状況パターン１０３は、クラスタリングによって生成されているため、過去に計測された交通状況そのものを表しているわけではない。過去の交通状況が複数の交通状況パターンに分類される。各交通状況パターンは、過去の交通状況のうちの互いに類似するいくつかのケースを代表する近似値により表される。交通状況パターンのそれぞれには固有のパターン番号が対応付けられている。
【００１４】
経路データベース生成装置１０４は、交通状況パターン１０３に対応する交通情報に基づく経路探索コストと、地図データベース１１０に格納された地図データとを用いて、ダイクストラ法などの経路探索アルゴリズムにより、交通状況パターン１０３のそれぞれに対応した全地点間のすべての組合せについての経路探索演算を行い、その経路探索演算により得られる全経路を経路データベース１０５に格納する。全地点間のすべての組合せについての経路探索演算とは、出発地および目的地となりうる全ノードのすべての組み合わせについて、経路探索演算を行うことをいう。経路データベース１０５には、交通状況パターン１０３のそれぞれに対応して、図２の表のように、出発地ノードと目的地ノードとを結ぶ経路を構成するリンク列が格納される。
【００１５】
交通状況照合装置１０７は、現況交通情報１０６と交通状況パターン１０３とを比較し、現況交通情報１０６に最も類似した交通状況パターン１０３のパターン番号を出力する。交通状況照合装置１０７が行う処理の詳細は後述する。
【００１６】
経路情報検索装置１０８は、交通状況照合装置１０７が出力したパターン番号の交通状況パターンに対応する全ノード間のすべての組合せについての経路探索結果を格納する経路データベース１０５を参照し、ナビゲーション装置１５０の経路案内インターフェース１０９から入力された出発地から目的地までの経路を検索して、その経路を構成するリンク列をナビゲーション装置１５０の経路案内インターフェース１０９へ出力する。
【００１７】
ナビゲーション装置１５０の経路案内インターフェース１０９は、ユーザからの出発地および目的地の入力を受け付けて経路案内システム１００の経路情報検索装置１０８へ出力するとともに、経路情報検索装置１０８が出力したリンク列で構成される経路３００を図３（ａ）のように画面に表示する。
【００１８】
交通状況分類装置１０２は、複数リンクの交通情報を要素とする多次元ベクトルをクラスタリングの対象とする。１リンクの交通情報を１つの座標軸上の値として考えると、例えば１０００本のリンクを含むエリアの交通状況は、１０００次元の交通情報空間上の交通情報ベクトルとして表される。この交通情報ベクトルが有する１０００個の成分は、それぞれ１０００本のリンクのリンク旅行時間またはリンク代表速度など、それぞれのリンクの移動コストに関する数値を表す。このリンク旅行時間またはリンク代表速度などの数値データは、上述したように交通情報データベース１０１に格納されており、過去の交通情報に基づいている。このような交通情報ベクトルが交通情報の更新周期毎に１本ずつ存在する。すなわち、１本の交通情報ベクトルは、ある時刻の交通情報に基づく１０００本のリンクの交通状況を表している。交通状況分類装置１０２は、複数回の交通情報更新で生成されたそれらの交通情報ベクトルをクラスタリングし、複数個の代表的なクラスターを得る。各クラスターには、複数の異なる時刻の交通情報に基づく複数の交通状況を表す複数の交通情報ベクトルが分類される。それらの複数の交通情報ベクトルの重心に対応する交通情報ベクトル、すなわち各クラスターの重心ベクトルで、交通状況パターン１０３が表される。
【００１９】
しかしリンク数が多い場合には、クラスタリングの演算量は膨大なものとなる。そのような場合には、特許文献２に開示されているように、交通情報ベクトルに対する主成分分析により得られる基底の線形合成により、交通情報を近似表現するのが好ましい。すなわち、まず交通情報ベクトルを主成分分析で低次元の特徴空間に特徴空間ベクトルとして射影し、次に特徴空間における特徴空間ベクトルを対象とするクラスタリングを行うと、演算量を大幅に減らすことができる。これを説明したものが図４である。図４は主成分分析で得られた複数の特徴空間ベクトルの射影点の座標４０１を、説明の便宜上、特徴空間から２つの基底Ｗ１およびＷ２を切り出した２次元の部分空間について示している。この特徴空間ベクトル（射影点）を対象とするクラスタリングを行うと、たとえば図５のようになる。複数のクラスター５０１のそれぞれの重心５０２を特徴空間からもとの交通情報空間に逆射影して得られる複数の重心ベクトルの各々は、交通情報空間でクラスタリングを行って得られる各クラスターの重心ベクトルの近似ベクトルである。この近似ベクトルを交通状況パターン１０３として用いることができる。
【００２０】
交通状況照合装置１０７は、現況交通情報１０６に基づく交通状況を表す交通情報ベクトルと、複数の交通状況パターン１０３を表す複数の交通情報ベクトルのそれぞれとの差分に基づいて得られる複数の差分ベクトルを相互比較し、ノルムが最も小さい差分ベクトルに対応する交通情報ベクトルで表される交通状況パターン１０３のパターン番号を出力する。また、前述のように交通状況分類装置１０２が複数の交通情報ベクトルを特徴空間に射影してクラスタリングを行う場合には、交通状況照合装置１０７も現況交通情報１０６に基づく交通状況を表す交通情報ベクトルを特徴空間に射影することにより、交通状況照合装置１０７は特徴空間において現況交通情報１０６と交通状況パターン１０３との照合を行うこともできる。これを図示したものが図６である。複数の重心６０１は、複数の交通状況パターン１０３のそれぞれに対応する特徴空間における座標に位置する。座標６０２は、現況交通情報１０６に基づく交通状況を表す交通情報ベクトルを特徴空間に射影した射影点の座標である。図６の例で交通状況照合装置１０７は、特徴空間における座標６０２に最も近い重心６０１ａに対応する特定の交通状況パターン１０３のパターン番号を出力する。
【００２１】
現況交通情報１０６によって表される交通状況が、過去の代表的な交通状況に類似している場合、すなわち現況交通情報１０６が特定の交通状況パターンに類似している場合には、上述したように、交通状況照合装置１０７により出力される特定の交通状況パターン１０３のパターン番号に基づき、経路情報検索装置１０８が経路データベース１０５を参照して経路を検索し、検索して読み出した経路を構成するリンク列をナビゲーション装置１５０へ出力する。経路情報検索装置１０８により読み出された経路が、現況交通情報１０６に対応した動的経路探索で得られる経路に精度良く近似する近似経路であり、こうして近似経路をナビゲーション装置１５０へ提供することができる。一方、現況交通情報１０６が特定の交通状況パターンから大きく逸脱した場合には、交通状況パターンを用いて事前探索した経路を格納した経路データベース１０５を検索して得られる近似経路は、現況交通情報１０６に対応した動的経路探索で得られる経路から大きく乖離したものとなる可能性がある。このような場合にも経路案内の品質を維持するには、現況交通情報と特定の交通状況パターンとの類似度が監視され、その類似度が低いときは、事前探索に基づく近似経路の経路情報ではなく、現況交通情報１０６を用いた動的経路探索で得られる動的経路の経路情報が配信されるように、経路情報配信処理が切り替えられることが好ましい。
【００２２】
クラスター距離判定装置１１２は、現況交通情報と特定の交通状況パターンとの類似度を判定する。動的経路探索装置１１３は、現況交通情報１０６を用いて、ナビゲーション装置１５０の経路案内インターフェース１０９を介してユーザにより指定された出発地から目的地までのダイクストラ法による動的経路探索を行い、得られた動的経路を構成するリンク列を経路案内インターフェース１０９に出力する。クラスター半径計算装置１１１は、現況交通情報１０６と特定の交通状況パターン１０３との類似度を評価する際の閾値であるクラスター半径を算出する。各交通状況パターン１０３に対応するクラスター半径の算出方法として、以下に２つの算出方法を示す。
【００２３】
図７はクラスター半径の第１の算出方法の解説図である。重心間距離７０２および７０３は、交通状況分類装置１０２によって生成された複数のクラスター重心７０１のうち、互いに隣接するクラスターのクラスター重心間の重心間距離を例示している。重心間距離の統計的代表値に基づいて、クラスター半径が定められる。重心間距離の統計的代表値は、例えば、互いに隣接する全てのクラスターの重心間距離の中で最も小さい距離である最近距離、互いに隣接する全てのクラスターの重心間距離の中で最も大きい距離である最遠距離、あるいは互いに隣接する全てのクラスターの重心間距離の平均距離である。例えば、隣接クラスター重心間の平均距離の０．５倍といった値をクラスター半径とする。このようにして、クラスター毎にクラスター半径が定められる。
【００２４】
図８はクラスター半径の第２の算出方法の解説図であり、クラスターのひとつに着目して描かれている。距離８０３は、このクラスターに含まれる１つの交通情報ベクトルの射影点８０２からクラスター重心８０１への距離である。このクラスターに含まれる各交通情報ベクトルの射影点からこのクラスター重心８０１への距離を、すべての交通情報ベクトルについて演算し、たとえばすべての交通情報ベクトルのうちの９０％が含まれる範囲８０４を決定する。範囲８０４は、図８ではハッチングされた領域として表されており、クラスター重心８０１を中心とする球の表面および内部である。図８においては、説明の便宜上、特徴空間から２つの基底Ｗ１およびＷ２を切り出した２次元の部分空間について示しているため、範囲８０４は、クラスター重心８０１を中心とする円の円周および内部として表されている。範囲８０４の半径をクラスター半径とする。このようにして、クラスター毎にクラスター半径が定められる。
【００２５】
図９はクラスター距離判定装置１１２による現況交通情報と特定の交通状況パターンとの類似度判定の方法を示した図である。クラスター距離判定装置１１２は、特定の交通状況パターン１０３に対応する特定のクラスターのクラスター重心９０１から現況交通情報１０６に基づく交通状況を表す交通情報ベクトルの射影点座標９０２までの距離９０３（現況交通情報１０６に基づく指標）と、クラスター半径計算装置１１１により特定の交通状況パターン１０３に対応する特定のクラスターについて算出されたクラスター半径９０４とを比較する。比較の結果、クラスター距離判定装置１１２は、クラスター半径９０４を閾値（特定交通状況パターン１０３に基づく基準）としたとき、距離９０３がこの閾値以下であるか否かを判定する。クラスター距離判定装置１１２は、距離９０３がクラスター半径９０４以下の場合は、現況交通情報１０６とクラスター重心９０１に対応する特定の交通状況パターン１０３との類似度が高いと判定する。すなわち、現況交通情報１０６と特定の交通状況パターン１０３とが互いに類似すると判定される。このように互いに類似すると判定されると、交通状況照合装置１０７による交通状況パターンのパターン番号の経路情報検索装置１０８への出力と、経路情報検索装置１０８による近似経路の検索および経路案内インターフェース１０９への近似経路の経路情報配信とが行われる。一方、距離９０３がクラスター半径９０４より大きい場合は、現況交通情報１０６と特定の交通状況パターン１０３との類似度が低いと判定する。すなわち、現況交通情報１０６と特定の交通状況パターン１０３とが互いに類似しないと判定される。このように互いに類似しないと判定されると、動的経路探索装置１１３による動的経路探索および経路案内インターフェース１０９への動的経路情報配信が行われる。すなわち、動的経路探索装置１１３は、現況交通情報１０６を用いて、ナビゲーション装置１５０の経路案内インターフェース１０９を介してユーザにより指定された出発地から目的地までの、ダイクストラ法による動的経路探索を行い、得られた動的経路を構成するリンク列を経路案内インターフェース１０９に出力する。
【００２６】
ナビゲーション装置１５０の経路案内インターフェース１０９は、ユーザからの出発地および目的地の入力を受け付けて経路案内システム１００の経路情報検索装置１０８および動的経路探索装置１１３へ出力する。経路案内インターフェース１０９は、経路情報検索装置１０８により配信された経路情報に基づく経路３００、すなわち経路情報検索装置１０８が出力したリンク列で構成される経路３００を図３（ａ）のように画面に表示するとともに、動的経路探索装置１１３により配信された経路情報に基づく経路３１０、すなわち動的経路探索装置１１３が出力したリンク列で構成される経路３１０を図３（ｂ）のように画面に表示する。
【００２７】
経路案内システム１００の動作をフローチャートで表すと図１０および図１１のようになる。図１０は、複数の交通状況パターン１０３の生成と、複数の交通状況パターン１０３のそれぞれに対応した全地点間のすべての組合せについての経路探索演算とを含む、経路案内システム１００によって予め行われる処理手順を示す。図１１は、出発地から目的地までの経路検索の際に経路案内システム１００によって行われる処理手順を示す。なお、ここではクラスタリングを前述のように特徴空間で行う場合について説明する。
【００２８】
図１０のステップＳ１００１では、交通状況分類装置１０２による交通情報データベース１０１からのデータ読み出しが行われる。交通状況分類装置１０２は経路探索の対象とする地域における過去の交通情報を取得する。ステップＳ１００２では、交通状況分類装置１０２による交通情報ベクトルの主成分分析の演算が行われる。交通状況分類装置１０２は、ステップＳ１００１で取得した交通情報に基づく交通状況を表す交通情報ベクトルに対する主成分分析により得られる基底に対応する特徴空間を生成する。ステップＳ１００３では、交通状況分類装置１０２は、該特徴空間に該交通情報ベクトルを射影する演算を行う。ステップＳ１００１で取得された交通情報に対応する特徴空間への射影により、特徴空間ベクトル（射影点）が得られる。ステップＳ１００４では、交通状況分類装置１０２によるクラスタリングの演算が行われる。該射影点が分類されたクラスターが形成される。クラスタリングには様々な手法があるが、たとえばＫ−ｍｅａｎｓ法を用いれば、複数の球状クラスターが形成され、各クラスターに分類された射影点から該クラスターのクラスター重心への距離が最短であることが保証される。ステップＳ１００５では、交通状況分類装置１０２による射影点およびクラスター重心の交通情報空間への逆射影演算が行われる。クラスター重心が逆射影されて得られる重心ベクトルから、交通状況パターン１０３が得られる。
【００２９】
ステップＳ１００６は経路データベース生成装置１０４内のループ処理である。経路データベース生成装置１０４は、交通状況パターン１０３のそれぞれに対応する交通情報に基づく経路探索コストを用いて、ステップＳ１００７における全ノードに関するループ処理を通じたステップＳ１００８における経路探索演算を行い、探索結果を経路データベース１０５に格納する。以上により、交通状況パターン１０３のそれぞれに対応する全ノード間の経路に関する経路情報が得られる。
【００３０】
図１１のステップＳ１１０１において、経路情報検索装置１０８は、ナビゲーション装置１５０の経路案内インターフェース１０９を介してユーザにより入力された出発地および目的地を含む経路案内リクエストを受信する。さらに、本実施の形態においては、動的経路探索装置１１３も、その経路案内リクエストを受信する。ステップＳ１１０２では、交通状況照合装置１０７への現況交通情報１０６の入力処理が行われる。ステップＳ１１０３では、交通状況照合装置１０７は、現況交通情報１０６に基づく交通状況を表す交通情報ベクトルの特徴空間への射影の演算を行う。交通状況照合装置１０７が該交通情報ベクトルを射影する特徴空間は、ステップＳ１００２で得られた特徴空間である。ステップＳ１１０４は交通状況照合装置１０７におけるループ処理である。ステップＳ１１０５において、交通状況照合装置１０７は、ステップＳ１１０３で得られた現況交通情報１０６に基づく交通状況を表す交通情報ベクトルの特徴空間における射影点と、交通状況パターン１０３のそれぞれに対応するクラスター重心との距離を算出する。交通状況照合装置１０７は、現況交通情報１０６に対応する該射影点からの距離のうちで最も短い距離にある特定のクラスター重心に対応する特定の交通状況パターン１０３のパターン番号を特定する。
【００３１】
ステップＳ１１０６では、クラスター距離判定装置１１２が、現況交通情報と特定の交通状況パターンとの類似度判定を行う。具体的には、上述した距離９０３がクラスター半径９０４以下であるか否かが判定される。ステップＳ１１０６で肯定判定がなされた場合は、ステップＳ１１０７からＳ１１０９までの処理が行われる。
【００３２】
ステップＳ１１０７において、交通状況照合装置１０７は、ステップＳ１１０５で特定した特定の交通状況パターン１０３のパターン番号を、現況交通情報に基づく交通状況に最も類似した特定の交通状況パターンのパターン番号として、経路情報検索装置１０８に出力する。ステップＳ１１０８では、経路情報検索装置１０８は、経路データベース１０５を参照して経路検索を行い、ナビゲーション装置１５０の経路案内インターフェース１０９を介してユーザにより指定された出発地および目的地と、ステップＳ１１０７で交通状況照合装置１０７から入力された特定の交通状況パターン１０３のパターン番号とに基づき、該パターン番号に対応した該出発地から該目的地までの経路に関する経路情報を読み出す。読み出された経路情報に対応する経路は、現況交通情報１０６に基づく交通状況に最も類似した特定の交通状況パターン１０３において検索された経路なので、現況交通情報１０６に対応した動的経路探索で得られる経路に近似した近似経路である。ステップＳ１１０９において、経路情報検索装置１０８は、ステップＳ１１０８で読み出した該経路情報を、ナビゲーション装置１５０の経路案内インターフェース１０９に配信する。ナビゲーション装置１５０の経路案内インターフェース１０９は、経路情報検索装置１０８により出力された近似経路を、図３（ａ）に示すように経路３００として画面に表示する。
【００３３】
ステップＳ１１０６で否定判定がなされた場合は、ステップＳ１１１０およびＳ１１１１が行われる。ステップＳ１１１０では、動的経路探索装置１１３が、ステップＳ１１０１で受信した経路案内リクエストに含まれる出発地から目的地までの、現況交通情報を用いた動的経路探索演算を行う。ステップＳ１１１１では、動的経路探索装置１１３は、ステップＳ１１１０で探索した動的経路の経路情報を、ナビゲーション装置１５０の経路案内インターフェース１０９に配信する。ナビゲーション装置１５０の経路案内インターフェース１０９は、動的経路探索装置１１３により出力された動的経路を、図３（ｂ）に示すように経路３１０として画面に表示する。
【００３４】
図１０に示すステップＳ１００１〜Ｓ１００８で行われる処理と、図１１に示すステップＳ１１０１〜Ｓ１１１１で行われる処理とは互いに独立した処理である。ステップＳ１００１〜Ｓ１００８は予めオフラインで実行される。ステップＳ１１０１〜Ｓ１１１１は、経路案内リクエストの受信に応じてリアルタイムに実行される。
【００３５】
本実施形態における経路案内システム１００は、ナビゲーション装置１５０の経路案内インターフェース１０９から入力された出発地から目的地までの上述した近似経路の近似精度が高い場合に、該出発地から該目的地までの近似経路を速やかに提供するので、利便性が高い。この近似経路は、現況交通情報１０６に突発的な交通規制等の情報が含まれている場合であっても、その情報を含んだ現況交通情報１０６に基づく交通状況に最も類似した特定の交通状況パターン１０３において検索された経路である。したがって、ほぼ実際の道路条件に応じた経路が、速やかに近似経路として得られるということになる。その一方で、実際の道路条件は変化しうるため、この近似経路の近似精度が常に高いとは限らない。近似精度が低い場合には、本実施形態における経路案内システム１００は動的経路探索に基づく経路を提供するので、経路案内の確実性が高い。
【００３６】
なお、ステップＳ１１０６における処理の分岐により、肯定判定時のステップＳ１１０７以降の処理が実行された場合に比べて、否定判定時のステップＳ１１１０で演算量の多い動的経路探索演算処理が実行された場合の方が、処理時間が長くなる。この処理時間の違いは、ナビゲーション装置１５０の経路案内インターフェース１０９の入出力に関わるユーザに対しては、ステップＳ１１０１における経路案内リクエスト受信の契機となる出発地および目的地の入力から、ステップＳ１１０９およびＳ１１１１における経路情報配信を契機として画面上に経路が描画されるまでの応答時間の差異となって現れる。
【００３７】
−−−第２の実施の形態−−−
第１の実施の形態における経路案内システム１００では、現況交通情報と交通状況パターンとの類似度が監視されることで、動的経路探索によって得られる動的経路に対する事前探索に基づく近似経路の近似精度の低下が間接的に検出される。第２の実施の形態における経路案内システム１００では、動的経路探索によって得られる動的経路に対する事前探索に基づく近似経路の近似精度が直接的に監視される。近似経路の近似精度は、経路案内システム１００からナビゲーション装置１５０への近似経路の提供後に検査される。近似経路の近似精度の低下が直接的に検出されると、動的経路探索によって得られる動的経路が提供される。
【００３８】
図１２は第２の実施の形態における経路案内システム１００の構成図である。本実施の形態における経路案内システム１００が有する交通情報データベース１０１、交通状況分類装置１０２、交通状況パターン１０３、経路データベース生成装置１０４、経路データベース１０５、現況交通情報１０６、交通状況照合装置１０７、経路情報検索装置１０８、および地図データベース１１０は第１の実施の形態における経路案内システム１００と同様であるため、詳細説明を省略する。ナビゲーション装置１５０は、経路案内システム１００の外部装置であり、経路案内インターフェース１０９を有する。経路案内システム１００とナビゲーション装置１５０との間の入出力は、通信を介して行われる。
【００３９】
本実施の形態における経路案内システム１００は、さらに、差替用動的経路探索装置１２０１と経路精度評価装置１２０２とを有する。差替用動的経路探索装置１２０１は、交通状況照合装置１０７と経路情報検索装置１０８とによって近似経路の検索および経路情報の出力が完了した後で、近似経路検索の時と同じ出発地から目的地までの、現況交通情報１０６を用いた動的経路探索演算を行う。
【００４０】
経路精度評価装置１２０２は、経路情報検索装置１０８から入力された近似経路と、差替用動的経路探索装置１２０１から入力された動的経路とを比較し、その動的経路に対するその近似経路の近似精度を、近似精度の低下を示す指標に基づいて評価する。すなわち、経路精度評価装置１２０２は、近似精度の低下を示す指標と、予め所定値が設定された基準値（基準）とを比較する。近似精度の低下を示す指標は、例えば動的経路の移動所要時間に対する、近似経路の移動所要時間と動的経路の移動所要時間との差の割合である。動的経路の移動所要時間が１００分、近似経路の移動所要時間が１１０分であるとき、近似経路の移動所要時間と動的経路の移動所要時間との差は１０分であるから、近似精度の低下を示す指標は１０％である。近似精度の低下を示す指標は、例えば、動的経路を構成するリンク列のうち、近似経路には含まれないリンク列の本数または長さの割合であってもよい。この近似精度の低下を示す指標の指標値が判明するタイミングは、経路情報検索装置１０８による近似経路の経路検索よりも多くの処理時間を要する差替用動的経路探索装置１２０１による動的経路探索演算の後であるから、経路情報検索装置１０８により既に近似経路の経路情報がナビゲーション装置１５０の経路案内インターフェース１０９に配信された後である。
【００４１】
近似精度の低下を示す指標が、例えば１０％を超えるなどのように、近似経路の近似精度が低下した場合（近似精度の低下を示す指標が基準値を超えた場合）には、経路精度評価装置１２０２は、動的経路の経路情報をナビゲーション装置１５０の経路案内インターフェース１０９に配信する。この時点で、ナビゲーション装置１５０の経路案内インターフェース１０９は、図３（ａ）に示すように、経路情報検索装置１０８により既に提供済みの近似経路情報に基づいて経路３００を画面に既に表示している。経路案内インターフェース１０９は、経路精度評価装置１２０２からの動的経路情報を受信したことを契機として、図３（ａ）に示す画面表示を上書きする形で、図３（ｂ）に示すように動的経路情報に基づく経路３１０を画面に表示する。近似経路の近似精度低下指標が基準値を超えない範囲内であれば、経路精度評価装置１２０２は、経路案内インターフェース１０９への動的経路情報配信を行わない。
【００４２】
差替用動的経路探索装置１２０１による動的経路探索演算処理、および経路精度評価装置１２０２による経路精度評価処理は、ともに経路情報検索装置１０８による近似経路の提供後に行われる。差替用の動的経路情報配信が行われる場合は、ナビゲーション装置１５０の経路案内インターフェース１０９の入出力に関わるユーザにとっては、いったん画面に描画された近似経路が消去された後、動的経路が再描画されるように感じられる。ナビゲーション装置１５０のユーザを待たせないために、先に得られる近似経路の経路情報が配信されるが、その後に行われる近似経路の近似精度の評価においてその近似精度が低いことが判明したときは、ユーザに動的経路を参照してもらうために、差替用の動的経路の経路情報が配信される。こうした差替用動的経路の再描画と合わせて、ユーザへの便宜のため、過去に生じたことの無いような何らかの異常事象が現在の交通状況に生じたために経路の再計算が行われた旨を明示することとしても良い。
【００４３】
図１３は、ナビゲーション装置１５０の経路案内インターフェース１０９から経路案内リクエストを受信してからの経路案内システム１００で行われる処理を表したフローチャートである。本実施の形態では、図１３に示すステップＳ１１０１からＳ１１０９において、図１１に示す第１の実施の形態におけるステップＳ１１０１からＳ１１０９までで行われる処理と同様の処理が行われるため、そうした処理に引き続いてステップＳ１３０１以降で行われる処理について説明する。なお、図１３には、図１１に示すステップＳ１１０６、Ｓ１１１０およびＳ１１１１が含まれておらず、ステップＳ１１０５における処理が完了するとステップＳ１１０７へ進む。
【００４４】
ステップＳ１１０９において、経路情報検索装置１０８は、ステップＳ１１０８で検索した近似経路の経路情報を、ナビゲーション装置１５０の経路案内インターフェース１０９に配信する。ナビゲーション装置１５０の経路案内インターフェース１０９は、経路情報検索装置１０８により出力された近似経路を、図３（ａ）に示すように経路３００として画面に表示する。
【００４５】
ステップＳ１３０１では、差替用動的経路探索装置１２０１は、現況交通情報１０６を用いた動的経路探索演算により動的経路を算出する。ステップＳ１３０２では、経路精度評価装置１２０２は、ステップＳ１１０８で検索された近似経路とステップＳ１３０１で算出された動的経路とを比較する。この比較結果によりステップＳ１３０２で処理が分岐する。この比較の結果、動的経路に対する近似経路の近似精度の低下を示す指標が上述した基準値を超えない範囲内ならば、ステップＳ１３０２で否定判定がなされ、本処理は終了となる。一方、動的経路に対する近似経路の近似精度の低下を示す指標が基準値を超えない範囲から逸脱している場合、すなわち近似精度低下指標が基準値を超過した場合は、ステップＳ１３０２で肯定判定がなされ、ステップＳ１３０３が実行される。ステップＳ１３０３において、経路精度評価装置１２０２は、ステップＳ１３０１で探索した動的経路の経路情報を、ナビゲーション装置１５０の経路案内インターフェース１０９に配信する。ナビゲーション装置１５０の経路案内インターフェース１０９は、図３（ａ）に示す画面を消去し、経路精度評価装置１２０２により出力された差替用動的経路の再描画を行い、その差替用動的経路を、図３（ｂ）に示すように経路３１０として画面に表示する。
【００４６】
第２の実施の形態における経路案内システム１００は、ナビゲーション装置１５０の経路案内インターフェース１０９から入力された出発地から目的地までの上述した近似経路の近似精度を評価する。上述したように、本実施の形態における経路案内システム１００では、第１の実施の形態における経路案内システム１００と異なり、近似経路の近似精度が、動的経路探索によって得られる動的経路に対する直接的な比較に基づいて評価される。したがって、近似経路の近似精度の評価を高精度に行うことができる。本実施の形態における経路案内システム１００は、その近似精度が低い場合には、その近似経路に差し替えて現況交通情報を反映した動的経路がナビゲーション装置１５０で表示されるように、その動的経路を提供するので、利便性が高い。
【符号の説明】
【００４７】
１００  経路案内システム
１０１  交通情報データベース
１０２  交通状況分類装置
１０３  交通状況パターン
１０４  経路データベース生成装置
１０５  経路データベース
１０６  現況交通情報
１０７  交通状況照合装置
１０８  経路情報検索装置
１０９  経路案内インターフェース
１１０  地図データベース
１１１  クラスター半径計算装置
１１２  クラスター距離判定装置
１１３  動的経路探索装置
１５０  ナビゲーション装置
４０１  特徴空間ベクトルの射影点の座標
５０１  クラスター
５０２  重心
６０１  重心
６０２  座標
７０１  クラスター重心
７０２  重心間距離
７０３  重心間距離
８０１  クラスター重心
８０２  交通情報ベクトルの射影点
８０３  距離
８０４  範囲
９０１  クラスター重心
９０２  交通情報ベクトルの射影点座標
９０３  距離
９０４  クラスター半径
１２０１  差替用動的経路探索装置
１２０２  経路精度評価装置
【図１】
0005586570.tif 000002
【図２】
0005586570.tif 000003
【図３】
0005586570.tif 000004
【図４】
0005586570.tif 000005
【図５】
0005586570.tif 000006
【図６】
0005586570.tif 000007
【図７】
0005586570.tif 000008
【図８】
0005586570.tif 000009
【図９】
0005586570.tif 000010
【図１０】
0005586570.tif 000011
【図１１】
0005586570.tif 000012
【図１２】
0005586570.tif 000013
【図１３】
0005586570.tif 000014