時刻毎の交通情報に基づく複数の交通状況を複数の交通状況パターンに分類する交通状況分類手段と、前記複数の交通状況パターンの各々に対応して、複数の地点間のすべての組合せについての経路探索演算を行い、前記経路探索演算により得られるすべての経路を経路データベースに格納する経路データベース生成手段と、前記複数の交通状況パターンの中から、現況交通情報に基づく交通状況に類似した特定交通状況パターンを出力する交通状況照合手段と、前記交通状況照合手段により出力された前記特定交通状況パターンに基づき、前記経路データベースを参照して、出発地から目的地までの第1経路を検索する経路情報検索手段と、前記現況交通情報に基づく指標と前記特定交通状況パターンに基づく基準とを比較する比較手段と、前記現況交通情報に基づく経路探索演算により、前記出発地から前記目的地までの第2経路を探索する動的経路探索手段と、前記比較手段による前記指標と前記基準とを比較した結果に応じて、前記第1経路および前記第2経路のいずれか一方を外部装置へ配信する経路情報配信手段とを備えることを特徴とする経路案内システム。請求項1に記載の経路案内システムにおいて、前記比較手段によって前記指標と前記基準とが比較された結果、前記比較手段によって前記現況交通情報と前記特定交通状況パターンとが互いに類似すると判定されたとき、前記経路情報配信手段は前記第1経路を配信し、前記比較手段によって前記現況交通情報と前記特定交通状況パターンとが互いに類似しないと判定されたとき、前記経路情報配信手段は前記第2経路を配信することを特徴とする経路案内システム。請求項2に記載の経路案内システムにおいて、前記交通状況分類手段は、前記複数の交通状況をクラスタリングにより複数のクラスターに分類し、前記複数の交通状況パターンの各々は、前記複数のクラスターの各クラスターに対応することを特徴とする経路案内システム。請求項3に記載の経路案内システムにおいて、前記複数の交通状況の各々は、複数の区間道路のそれぞれに対応する複数の移動コストに関する複数の成分を含む交通情報ベクトルで表され、前記複数の交通状況パターンの各々は前記各クラスターの重心に対応する前記交通情報ベクトルで表され、前記交通状況照合手段は、前記複数のクラスターのそれぞれの重心に対応する複数の交通情報ベクトルのうち、前記現況交通情報に基づく交通状況を表す前記交通情報ベクトルから最も短い距離にある前記交通情報ベクトルで表される交通状況パターンを、前記特定交通状況パターンとして出力することを特徴とする経路案内システム。請求項4に記載の経路案内システムにおいて、前記特定交通状況パターンは、前記複数のクラスターのうちの特定クラスターに対応し、前記指標は、前記最も短い距離であり、前記基準は、前記特定クラスターのクラスター半径であり、前記比較手段は、前記指標と前記基準とを比較した結果、前記指標が前記基準以下のとき、前記現況交通情報と前記特定交通状況パターンとが互いに類似すると判定し、前記指標が前記基準よりも大きいとき、前記現況交通情報と前記特定交通状況パターンとが互いに類似しないと判定することを特徴とする経路案内システム。請求項1に記載の経路案内システムにおいて、前記指標は、前記第2経路に対する前記第1経路の近似精度の低下を示し、前記基準として予め所定値が設定され、前記経路情報配信手段は前記第1経路を配信するとともに、前記比較手段によって前記指標と前記基準とが比較された結果、前記指標が前記基準よりも大きいとき、前記経路情報配信手段は前記第2経路を配信することを特徴とする経路案内システム。請求項6に記載の経路案内システムにおいて、前記交通状況分類手段は、前記複数の交通状況をクラスタリングにより複数のクラスターに分類し、前記複数の交通状況パターンの各々は、前記複数のクラスターの各クラスターに対応することを特徴とする経路案内システム。請求項7に記載の経路案内システムにおいて、前記複数の交通状況の各々は、複数の区間道路のそれぞれに対応する複数の移動コストに関する複数の成分を含む交通情報ベクトルで表され、前記複数の交通状況パターンの各々は前記各クラスターの重心に対応する前記交通情報ベクトルで表され、前記交通状況照合手段は、前記複数のクラスターのそれぞれの重心に対応する複数の交通情報ベクトルのうち、前記現況交通情報に基づく交通状況を表す前記交通情報ベクトルから最も短い距離にある前記交通情報ベクトルで表される交通状況パターンを、前記特定交通状況パターンとして出力することを特徴とする経路案内システム。請求項8に記載の経路案内システムにおいて、前記第1経路が前記外部装置の画面に表示された後に前記第2経路が前記画面に表示されるように、前記経路情報配信手段は、前記第1経路を前記外部装置へ配信した後、前記第2経路を前記外部装置へ配信することを特徴とする経路案内システム。特許文献1に開示された技術によると、オフライン処理で計算されてデータベースに記憶される基準経路木は、平日/休日の別等の経路計算条件種別毎に計算される。そうした経路計算条件種別だけで道路条件が定まることはなく、実際には同一の経路計算条件種別に対して異なる道路条件が生じる場合がある。そのため、経路計算条件種別を考慮しても、必ずしも実際の道路条件とは一致しない道路条件に応じた基準経路木が計算されてしまう可能性がある。請求項1に記載の経路案内システムは、時刻毎の交通情報に基づく複数の交通状況を複数の交通状況パターンに分類する交通状況分類手段と、複数の交通状況パターンの各々に対応して、複数の地点間のすべての組合せについての経路探索演算を行い、経路探索演算により得られるすべての経路を経路データベースに格納する経路データベース生成手段と、複数の交通状況パターンの中から、現況交通情報に基づく交通状況に類似した特定交通状況パターンを出力する交通状況照合手段と、交通状況照合手段により出力された特定交通状況パターンに基づき、経路データベースを参照して、出発地から目的地までの第1経路を検索する経路情報検索手段と、現況交通情報に基づく指標と特定交通状況パターンに基づく基準とを比較する比較手段と、現況交通情報に基づく経路探索演算により、出発地から目的地までの第2経路を探索する動的経路探索手段と、比較手段による指標と基準とを比較した結果に応じて、第1経路および第2経路のいずれか一方を外部装置へ配信する経路情報配信手段とを備えることを特徴とする。本発明による経路案内システムは、現況交通情報に基づく動的経路に近似した近似経路を速やかに出力することができる。以下、図面を用いて本発明の実施の形態について説明する。---第1の実施の形態---図1は、第1の実施の形態における経路案内システム100の構成例を表す図である。経路案内システム100は、交通情報データベース101と、交通状況分類装置102と、交通状況パターン103と、経路データベース生成装置104と、経路データベース105と、現況交通情報106と、交通状況照合装置107と、経路情報検索装置108と、地図データベース110と、クラスター半径計算装置111と、クラスター距離判定装置112と、動的経路探索装置113とを有する。ナビゲーション装置150は、経路案内システム100の外部装置であり、経路案内インターフェース109を有する。経路案内システム100とナビゲーション装置150との間の入出力は、通信を介して行われる。交通情報データベース101には、リンク旅行時間またはリンク代表速度などの数値データで表された過去の交通情報が格納されている。交通状況分類装置102は、交通情報データベース101に格納された交通情報を読み出し、クラスタリングによって代表的な複数の交通状況パターンを生成する。クラスタリングの手法には様々な公知の手法がある。交通状況分類装置102は、例えばK-means法を用いて過去の交通状況のクラスタリングを行う。交通状況分類装置102が行う処理の詳細は後述する。交通状況パターン103は交通状況分類装置によって生成される。交通状況パターン103は、クラスタリングによって生成されているため、過去に計測された交通状況そのものを表しているわけではない。過去の交通状況が複数の交通状況パターンに分類される。各交通状況パターンは、過去の交通状況のうちの互いに類似するいくつかのケースを代表する近似値により表される。交通状況パターンのそれぞれには固有のパターン番号が対応付けられている。経路データベース生成装置104は、交通状況パターン103に対応する交通情報に基づく経路探索コストと、地図データベース110に格納された地図データとを用いて、ダイクストラ法などの経路探索アルゴリズムにより、交通状況パターン103のそれぞれに対応した全地点間のすべての組合せについての経路探索演算を行い、その経路探索演算により得られる全経路を経路データベース105に格納する。全地点間のすべての組合せについての経路探索演算とは、出発地および目的地となりうる全ノードのすべての組み合わせについて、経路探索演算を行うことをいう。経路データベース105には、交通状況パターン103のそれぞれに対応して、図2の表のように、出発地ノードと目的地ノードとを結ぶ経路を構成するリンク列が格納される。交通状況照合装置107は、現況交通情報106と交通状況パターン103とを比較し、現況交通情報106に最も類似した交通状況パターン103のパターン番号を出力する。交通状況照合装置107が行う処理の詳細は後述する。経路情報検索装置108は、交通状況照合装置107が出力したパターン番号の交通状況パターンに対応する全ノード間のすべての組合せについての経路探索結果を格納する経路データベース105を参照し、ナビゲーション装置150の経路案内インターフェース109から入力された出発地から目的地までの経路を検索して、その経路を構成するリンク列をナビゲーション装置150の経路案内インターフェース109へ出力する。ナビゲーション装置150の経路案内インターフェース109は、ユーザからの出発地および目的地の入力を受け付けて経路案内システム100の経路情報検索装置108へ出力するとともに、経路情報検索装置108が出力したリンク列で構成される経路300を図3aのように画面に表示する。交通状況分類装置102は、複数リンクの交通情報を要素とする多次元ベクトルをクラスタリングの対象とする。1リンクの交通情報を1つの座標軸上の値として考えると、例えば1000本のリンクを含むエリアの交通状況は、1000次元の交通情報空間上の交通情報ベクトルとして表される。この交通情報ベクトルが有する1000個の成分は、それぞれ1000本のリンクのリンク旅行時間またはリンク代表速度など、それぞれのリンクの移動コストに関する数値を表す。このリンク旅行時間またはリンク代表速度などの数値データは、上述したように交通情報データベース101に格納されており、過去の交通情報に基づいている。このような交通情報ベクトルが交通情報の更新周期毎に1本ずつ存在する。すなわち、1本の交通情報ベクトルは、ある時刻の交通情報に基づく1000本のリンクの交通状況を表している。交通状況分類装置102は、複数回の交通情報更新で生成されたそれらの交通情報ベクトルをクラスタリングし、複数個の代表的なクラスターを得る。各クラスターには、複数の異なる時刻の交通情報に基づく複数の交通状況を表す複数の交通情報ベクトルが分類される。それらの複数の交通情報ベクトルの重心に対応する交通情報ベクトル、すなわち各クラスターの重心ベクトルで、交通状況パターン103が表される。しかしリンク数が多い場合には、クラスタリングの演算量は膨大なものとなる。そのような場合には、特許文献2に開示されているように、交通情報ベクトルに対する主成分分析により得られる基底の線形合成により、交通情報を近似表現するのが好ましい。すなわち、まず交通情報ベクトルを主成分分析で低次元の特徴空間に特徴空間ベクトルとして射影し、次に特徴空間における特徴空間ベクトルを対象とするクラスタリングを行うと、演算量を大幅に減らすことができる。これを説明したものが図4である。図4は主成分分析で得られた複数の特徴空間ベクトルの射影点の座標401を、説明の便宜上、特徴空間から2つの基底W1およびW2を切り出した2次元の部分空間について示している。この特徴空間ベクトル射影点を対象とするクラスタリングを行うと、たとえば図5のようになる。複数のクラスター501のそれぞれの重心502を特徴空間からもとの交通情報空間に逆射影して得られる複数の重心ベクトルの各々は、交通情報空間でクラスタリングを行って得られる各クラスターの重心ベクトルの近似ベクトルである。この近似ベクトルを交通状況パターン103として用いることができる。交通状況照合装置107は、現況交通情報106に基づく交通状況を表す交通情報ベクトルと、複数の交通状況パターン103を表す複数の交通情報ベクトルのそれぞれとの差分に基づいて得られる複数の差分ベクトルを相互比較し、ノルムが最も小さい差分ベクトルに対応する交通情報ベクトルで表される交通状況パターン103のパターン番号を出力する。また、前述のように交通状況分類装置102が複数の交通情報ベクトルを特徴空間に射影してクラスタリングを行う場合には、交通状況照合装置107も現況交通情報106に基づく交通状況を表す交通情報ベクトルを特徴空間に射影することにより、交通状況照合装置107は特徴空間において現況交通情報106と交通状況パターン103との照合を行うこともできる。これを図示したものが図6である。複数の重心601は、複数の交通状況パターン103のそれぞれに対応する特徴空間における座標に位置する。座標602は、現況交通情報106に基づく交通状況を表す交通情報ベクトルを特徴空間に射影した射影点の座標である。図6の例で交通状況照合装置107は、特徴空間における座標602に最も近い重心601aに対応する特定の交通状況パターン103のパターン番号を出力する。現況交通情報106によって表される交通状況が、過去の代表的な交通状況に類似している場合、すなわち現況交通情報106が特定の交通状況パターンに類似している場合には、上述したように、交通状況照合装置107により出力される特定の交通状況パターン103のパターン番号に基づき、経路情報検索装置108が経路データベース105を参照して経路を検索し、検索して読み出した経路を構成するリンク列をナビゲーション装置150へ出力する。経路情報検索装置108により読み出された経路が、現況交通情報106に対応した動的経路探索で得られる経路に精度良く近似する近似経路であり、こうして近似経路をナビゲーション装置150へ提供することができる。一方、現況交通情報106が特定の交通状況パターンから大きく逸脱した場合には、交通状況パターンを用いて事前探索した経路を格納した経路データベース105を検索して得られる近似経路は、現況交通情報106に対応した動的経路探索で得られる経路から大きく乖離したものとなる可能性がある。このような場合にも経路案内の品質を維持するには、現況交通情報と特定の交通状況パターンとの類似度が監視され、その類似度が低いときは、事前探索に基づく近似経路の経路情報ではなく、現況交通情報106を用いた動的経路探索で得られる動的経路の経路情報が配信されるように、経路情報配信処理が切り替えられることが好ましい。クラスター距離判定装置112は、現況交通情報と特定の交通状況パターンとの類似度を判定する。動的経路探索装置113は、現況交通情報106を用いて、ナビゲーション装置150の経路案内インターフェース109を介してユーザにより指定された出発地から目的地までのダイクストラ法による動的経路探索を行い、得られた動的経路を構成するリンク列を経路案内インターフェース109に出力する。クラスター半径計算装置111は、現況交通情報106と特定の交通状況パターン103との類似度を評価する際の閾値であるクラスター半径を算出する。各交通状況パターン103に対応するクラスター半径の算出方法として、以下に2つの算出方法を示す。図7はクラスター半径の第1の算出方法の解説図である。重心間距離702および703は、交通状況分類装置102によって生成された複数のクラスター重心701のうち、互いに隣接するクラスターのクラスター重心間の重心間距離を例示している。重心間距離の統計的代表値に基づいて、クラスター半径が定められる。重心間距離の統計的代表値は、例えば、互いに隣接する全てのクラスターの重心間距離の中で最も小さい距離である最近距離、互いに隣接する全てのクラスターの重心間距離の中で最も大きい距離である最遠距離、あるいは互いに隣接する全てのクラスターの重心間距離の平均距離である。例えば、隣接クラスター重心間の平均距離の0.5倍といった値をクラスター半径とする。このようにして、クラスター毎にクラスター半径が定められる。図8はクラスター半径の第2の算出方法の解説図であり、クラスターのひとつに着目して描かれている。距離803は、このクラスターに含まれる1つの交通情報ベクトルの射影点802からクラスター重心801への距離である。このクラスターに含まれる各交通情報ベクトルの射影点からこのクラスター重心801への距離を、すべての交通情報ベクトルについて演算し、たとえばすべての交通情報ベクトルのうちの90が含まれる範囲804を決定する。範囲804は、図8ではハッチングされた領域として表されており、クラスター重心801を中心とする球の表面および内部である。図8においては、説明の便宜上、特徴空間から2つの基底W1およびW2を切り出した2次元の部分空間について示しているため、範囲804は、クラスター重心801を中心とする円の円周および内部として表されている。範囲804の半径をクラスター半径とする。このようにして、クラスター毎にクラスター半径が定められる。図9はクラスター距離判定装置112による現況交通情報と特定の交通状況パターンとの類似度判定の方法を示した図である。クラスター距離判定装置112は、特定の交通状況パターン103に対応する特定のクラスターのクラスター重心901から現況交通情報106に基づく交通状況を表す交通情報ベクトルの射影点座標902までの距離903現況交通情報106に基づく指標と、クラスター半径計算装置111により特定の交通状況パターン103に対応する特定のクラスターについて算出されたクラスター半径904とを比較する。比較の結果、クラスター距離判定装置112は、クラスター半径904を閾値特定交通状況パターン103に基づく基準としたとき、距離903がこの閾値以下であるか否かを判定する。クラスター距離判定装置112は、距離903がクラスター半径904以下の場合は、現況交通情報106とクラスター重心901に対応する特定の交通状況パターン103との類似度が高いと判定する。すなわち、現況交通情報106と特定の交通状況パターン103とが互いに類似すると判定される。このように互いに類似すると判定されると、交通状況照合装置107による交通状況パターンのパターン番号の経路情報検索装置108への出力と、経路情報検索装置108による近似経路の検索および経路案内インターフェース109への近似経路の経路情報配信とが行われる。一方、距離903がクラスター半径904より大きい場合は、現況交通情報106と特定の交通状況パターン103との類似度が低いと判定する。すなわち、現況交通情報106と特定の交通状況パターン103とが互いに類似しないと判定される。このように互いに類似しないと判定されると、動的経路探索装置113による動的経路探索および経路案内インターフェース109への動的経路情報配信が行われる。すなわち、動的経路探索装置113は、現況交通情報106を用いて、ナビゲーション装置150の経路案内インターフェース109を介してユーザにより指定された出発地から目的地までの、ダイクストラ法による動的経路探索を行い、得られた動的経路を構成するリンク列を経路案内インターフェース109に出力する。ナビゲーション装置150の経路案内インターフェース109は、ユーザからの出発地および目的地の入力を受け付けて経路案内システム100の経路情報検索装置108および動的経路探索装置113へ出力する。経路案内インターフェース109は、経路情報検索装置108により配信された経路情報に基づく経路300、すなわち経路情報検索装置108が出力したリンク列で構成される経路300を図3aのように画面に表示するとともに、動的経路探索装置113により配信された経路情報に基づく経路310、すなわち動的経路探索装置113が出力したリンク列で構成される経路310を図3bのように画面に表示する。経路案内システム100の動作をフローチャートで表すと図10および図11のようになる。図10は、複数の交通状況パターン103の生成と、複数の交通状況パターン103のそれぞれに対応した全地点間のすべての組合せについての経路探索演算とを含む、経路案内システム100によって予め行われる処理手順を示す。図11は、出発地から目的地までの経路検索の際に経路案内システム100によって行われる処理手順を示す。なお、ここではクラスタリングを前述のように特徴空間で行う場合について説明する。図10のステップS1001では、交通状況分類装置102による交通情報データベース101からのデータ読み出しが行われる。交通状況分類装置102は経路探索の対象とする地域における過去の交通情報を取得する。ステップS1002では、交通状況分類装置102による交通情報ベクトルの主成分分析の演算が行われる。交通状況分類装置102は、ステップS1001で取得した交通情報に基づく交通状況を表す交通情報ベクトルに対する主成分分析により得られる基底に対応する特徴空間を生成する。ステップS1003では、交通状況分類装置102は、該特徴空間に該交通情報ベクトルを射影する演算を行う。ステップS1001で取得された交通情報に対応する特徴空間への射影により、特徴空間ベクトル射影点が得られる。ステップS1004では、交通状況分類装置102によるクラスタリングの演算が行われる。該射影点が分類されたクラスターが形成される。クラスタリングには様々な手法があるが、たとえばK-means法を用いれば、複数の球状クラスターが形成され、各クラスターに分類された射影点から該クラスターのクラスター重心への距離が最短であることが保証される。ステップS1005では、交通状況分類装置102による射影点およびクラスター重心の交通情報空間への逆射影演算が行われる。クラスター重心が逆射影されて得られる重心ベクトルから、交通状況パターン103が得られる。ステップS1006は経路データベース生成装置104内のループ処理である。経路データベース生成装置104は、交通状況パターン103のそれぞれに対応する交通情報に基づく経路探索コストを用いて、ステップS1007における全ノードに関するループ処理を通じたステップS1008における経路探索演算を行い、探索結果を経路データベース105に格納する。以上により、交通状況パターン103のそれぞれに対応する全ノード間の経路に関する経路情報が得られる。図11のステップS1101において、経路情報検索装置108は、ナビゲーション装置150の経路案内インターフェース109を介してユーザにより入力された出発地および目的地を含む経路案内リクエストを受信する。さらに、本実施の形態においては、動的経路探索装置113も、その経路案内リクエストを受信する。ステップS1102では、交通状況照合装置107への現況交通情報106の入力処理が行われる。ステップS1103では、交通状況照合装置107は、現況交通情報106に基づく交通状況を表す交通情報ベクトルの特徴空間への射影の演算を行う。交通状況照合装置107が該交通情報ベクトルを射影する特徴空間は、ステップS1002で得られた特徴空間である。ステップS1104は交通状況照合装置107におけるループ処理である。ステップS1105において、交通状況照合装置107は、ステップS1103で得られた現況交通情報106に基づく交通状況を表す交通情報ベクトルの特徴空間における射影点と、交通状況パターン103のそれぞれに対応するクラスター重心との距離を算出する。交通状況照合装置107は、現況交通情報106に対応する該射影点からの距離のうちで最も短い距離にある特定のクラスター重心に対応する特定の交通状況パターン103のパターン番号を特定する。ステップS1106では、クラスター距離判定装置112が、現況交通情報と特定の交通状況パターンとの類似度判定を行う。具体的には、上述した距離903がクラスター半径904以下であるか否かが判定される。ステップS1106で肯定判定がなされた場合は、ステップS1107からS1109までの処理が行われる。ステップS1107において、交通状況照合装置107は、ステップS1105で特定した特定の交通状況パターン103のパターン番号を、現況交通情報に基づく交通状況に最も類似した特定の交通状況パターンのパターン番号として、経路情報検索装置108に出力する。ステップS1108では、経路情報検索装置108は、経路データベース105を参照して経路検索を行い、ナビゲーション装置150の経路案内インターフェース109を介してユーザにより指定された出発地および目的地と、ステップS1107で交通状況照合装置107から入力された特定の交通状況パターン103のパターン番号とに基づき、該パターン番号に対応した該出発地から該目的地までの経路に関する経路情報を読み出す。読み出された経路情報に対応する経路は、現況交通情報106に基づく交通状況に最も類似した特定の交通状況パターン103において検索された経路なので、現況交通情報106に対応した動的経路探索で得られる経路に近似した近似経路である。ステップS1109において、経路情報検索装置108は、ステップS1108で読み出した該経路情報を、ナビゲーション装置150の経路案内インターフェース109に配信する。ナビゲーション装置150の経路案内インターフェース109は、経路情報検索装置108により出力された近似経路を、図3aに示すように経路300として画面に表示する。ステップS1106で否定判定がなされた場合は、ステップS1110およびS1111が行われる。ステップS1110では、動的経路探索装置113が、ステップS1101で受信した経路案内リクエストに含まれる出発地から目的地までの、現況交通情報を用いた動的経路探索演算を行う。ステップS1111では、動的経路探索装置113は、ステップS1110で探索した動的経路の経路情報を、ナビゲーション装置150の経路案内インターフェース109に配信する。ナビゲーション装置150の経路案内インターフェース109は、動的経路探索装置113により出力された動的経路を、図3bに示すように経路310として画面に表示する。図10に示すステップS1001~S1008で行われる処理と、図11に示すステップS1101~S1111で行われる処理とは互いに独立した処理である。ステップS1001~S1008は予めオフラインで実行される。ステップS1101~S1111は、経路案内リクエストの受信に応じてリアルタイムに実行される。本実施形態における経路案内システム100は、ナビゲーション装置150の経路案内インターフェース109から入力された出発地から目的地までの上述した近似経路の近似精度が高い場合に、該出発地から該目的地までの近似経路を速やかに提供するので、利便性が高い。この近似経路は、現況交通情報106に突発的な交通規制等の情報が含まれている場合であっても、その情報を含んだ現況交通情報106に基づく交通状況に最も類似した特定の交通状況パターン103において検索された経路である。したがって、ほぼ実際の道路条件に応じた経路が、速やかに近似経路として得られるということになる。その一方で、実際の道路条件は変化しうるため、この近似経路の近似精度が常に高いとは限らない。近似精度が低い場合には、本実施形態における経路案内システム100は動的経路探索に基づく経路を提供するので、経路案内の確実性が高い。なお、ステップS1106における処理の分岐により、肯定判定時のステップS1107以降の処理が実行された場合に比べて、否定判定時のステップS1110で演算量の多い動的経路探索演算処理が実行された場合の方が、処理時間が長くなる。この処理時間の違いは、ナビゲーション装置150の経路案内インターフェース109の入出力に関わるユーザに対しては、ステップS1101における経路案内リクエスト受信の契機となる出発地および目的地の入力から、ステップS1109およびS1111における経路情報配信を契機として画面上に経路が描画されるまでの応答時間の差異となって現れる。---第2の実施の形態---第1の実施の形態における経路案内システム100では、現況交通情報と交通状況パターンとの類似度が監視されることで、動的経路探索によって得られる動的経路に対する事前探索に基づく近似経路の近似精度の低下が間接的に検出される。第2の実施の形態における経路案内システム100では、動的経路探索によって得られる動的経路に対する事前探索に基づく近似経路の近似精度が直接的に監視される。近似経路の近似精度は、経路案内システム100からナビゲーション装置150への近似経路の提供後に検査される。近似経路の近似精度の低下が直接的に検出されると、動的経路探索によって得られる動的経路が提供される。図12は第2の実施の形態における経路案内システム100の構成図である。本実施の形態における経路案内システム100が有する交通情報データベース101、交通状況分類装置102、交通状況パターン103、経路データベース生成装置104、経路データベース105、現況交通情報106、交通状況照合装置107、経路情報検索装置108、および地図データベース110は第1の実施の形態における経路案内システム100と同様であるため、詳細説明を省略する。ナビゲーション装置150は、経路案内システム100の外部装置であり、経路案内インターフェース109を有する。経路案内システム100とナビゲーション装置150との間の入出力は、通信を介して行われる。本実施の形態における経路案内システム100は、さらに、差替用動的経路探索装置1201と経路精度評価装置1202とを有する。差替用動的経路探索装置1201は、交通状況照合装置107と経路情報検索装置108とによって近似経路の検索および経路情報の出力が完了した後で、近似経路検索の時と同じ出発地から目的地までの、現況交通情報106を用いた動的経路探索演算を行う。経路精度評価装置1202は、経路情報検索装置108から入力された近似経路と、差替用動的経路探索装置1201から入力された動的経路とを比較し、その動的経路に対するその近似経路の近似精度を、近似精度の低下を示す指標に基づいて評価する。すなわち、経路精度評価装置1202は、近似精度の低下を示す指標と、予め所定値が設定された基準値基準とを比較する。近似精度の低下を示す指標は、例えば動的経路の移動所要時間に対する、近似経路の移動所要時間と動的経路の移動所要時間との差の割合である。動的経路の移動所要時間が100分、近似経路の移動所要時間が110分であるとき、近似経路の移動所要時間と動的経路の移動所要時間との差は10分であるから、近似精度の低下を示す指標は10である。近似精度の低下を示す指標は、例えば、動的経路を構成するリンク列のうち、近似経路には含まれないリンク列の本数または長さの割合であってもよい。この近似精度の低下を示す指標の指標値が判明するタイミングは、経路情報検索装置108による近似経路の経路検索よりも多くの処理時間を要する差替用動的経路探索装置1201による動的経路探索演算の後であるから、経路情報検索装置108により既に近似経路の経路情報がナビゲーション装置150の経路案内インターフェース109に配信された後である。近似精度の低下を示す指標が、例えば10を超えるなどのように、近似経路の近似精度が低下した場合近似精度の低下を示す指標が基準値を超えた場合には、経路精度評価装置1202は、動的経路の経路情報をナビゲーション装置150の経路案内インターフェース109に配信する。この時点で、ナビゲーション装置150の経路案内インターフェース109は、図3aに示すように、経路情報検索装置108により既に提供済みの近似経路情報に基づいて経路300を画面に既に表示している。経路案内インターフェース109は、経路精度評価装置1202からの動的経路情報を受信したことを契機として、図3aに示す画面表示を上書きする形で、図3bに示すように動的経路情報に基づく経路310を画面に表示する。近似経路の近似精度低下指標が基準値を超えない範囲内であれば、経路精度評価装置1202は、経路案内インターフェース109への動的経路情報配信を行わない。差替用動的経路探索装置1201による動的経路探索演算処理、および経路精度評価装置1202による経路精度評価処理は、ともに経路情報検索装置108による近似経路の提供後に行われる。差替用の動的経路情報配信が行われる場合は、ナビゲーション装置150の経路案内インターフェース109の入出力に関わるユーザにとっては、いったん画面に描画された近似経路が消去された後、動的経路が再描画されるように感じられる。ナビゲーション装置150のユーザを待たせないために、先に得られる近似経路の経路情報が配信されるが、その後に行われる近似経路の近似精度の評価においてその近似精度が低いことが判明したときは、ユーザに動的経路を参照してもらうために、差替用の動的経路の経路情報が配信される。こうした差替用動的経路の再描画と合わせて、ユーザへの便宜のため、過去に生じたことの無いような何らかの異常事象が現在の交通状況に生じたために経路の再計算が行われた旨を明示することとしても良い。図13は、ナビゲーション装置150の経路案内インターフェース109から経路案内リクエストを受信してからの経路案内システム100で行われる処理を表したフローチャートである。本実施の形態では、図13に示すステップS1101からS1109において、図11に示す第1の実施の形態におけるステップS1101からS1109までで行われる処理と同様の処理が行われるため、そうした処理に引き続いてステップS1301以降で行われる処理について説明する。なお、図13には、図11に示すステップS1106、S1110およびS1111が含まれておらず、ステップS1105における処理が完了するとステップS1107へ進む。ステップS1109において、経路情報検索装置108は、ステップS1108で検索した近似経路の経路情報を、ナビゲーション装置150の経路案内インターフェース109に配信する。ナビゲーション装置150の経路案内インターフェース109は、経路情報検索装置108により出力された近似経路を、図3aに示すように経路300として画面に表示する。ステップS1301では、差替用動的経路探索装置1201は、現況交通情報106を用いた動的経路探索演算により動的経路を算出する。ステップS1302では、経路精度評価装置1202は、ステップS1108で検索された近似経路とステップS1301で算出された動的経路とを比較する。この比較結果によりステップS1302で処理が分岐する。この比較の結果、動的経路に対する近似経路の近似精度の低下を示す指標が上述した基準値を超えない範囲内ならば、ステップS1302で否定判定がなされ、本処理は終了となる。一方、動的経路に対する近似経路の近似精度の低下を示す指標が基準値を超えない範囲から逸脱している場合、すなわち近似精度低下指標が基準値を超過した場合は、ステップS1302で肯定判定がなされ、ステップS1303が実行される。ステップS1303において、経路精度評価装置1202は、ステップS1301で探索した動的経路の経路情報を、ナビゲーション装置150の経路案内インターフェース109に配信する。ナビゲーション装置150の経路案内インターフェース109は、図3aに示す画面を消去し、経路精度評価装置1202により出力された差替用動的経路の再描画を行い、その差替用動的経路を、図3bに示すように経路310として画面に表示する。第2の実施の形態における経路案内システム100は、ナビゲーション装置150の経路案内インターフェース109から入力された出発地から目的地までの上述した近似経路の近似精度を評価する。上述したように、本実施の形態における経路案内システム100では、第1の実施の形態における経路案内システム100と異なり、近似経路の近似精度が、動的経路探索によって得られる動的経路に対する直接的な比較に基づいて評価される。したがって、近似経路の近似精度の評価を高精度に行うことができる。本実施の形態における経路案内システム100は、その近似精度が低い場合には、その近似経路に差し替えて現況交通情報を反映した動的経路がナビゲーション装置150で表示されるように、その動的経路を提供するので、利便性が高い。