時刻毎の交通情報に基づく複数の交通状況を複数の交通状況パターンに分類する交通状況分類手段と、前記複数の交通状況パターンの各々に対応して、複数の地点間のすべての組み合わせについての経路探索演算を行い、前記経路探索演算により得られる全ての経路を経路データベースに格納する経路データベース生成手段と、前記複数の交通状況パターンの中から、現況交通情報に類似した交通状況パターンを出力する交通状況照合手段と、前記交通状況照合手段により出力された前記交通状況パターンに基づき、前記経路データベースを参照して、出発地から目的地までの経路を検索して出力する経路情報検索手段とを備えることを特徴とする経路案内システム。請求項1に記載の経路案内システムにおいて、前記交通状況分類手段は、前記複数の交通状況をクラスタリングにより複数のクラスタに分類し、前記複数の交通状況パターンの各々は、前記複数のクラスタの各クラスタに対応することを特徴とする経路案内システム。請求項2に記載の経路案内システムにおいて、前記複数の交通状況の各々は、複数の区間道路のそれぞれに対応する複数の移動コストに関する複数の成分を含む交通情報ベクトルで表され、前記複数の交通状況パターンの各々は前記各クラスタの重心に対応する前記交通情報ベクトルで表され、前記交通状況照合手段は、前記複数のクラスタのそれぞれの重心に対応する複数の交通情報ベクトルの内、前記現況交通情報に基づく交通状況を表す前記交通情報ベクトルから最も短い距離にある前記交通情報ベクトルで表される交通状況パターンを、前記現況交通情報に類似した交通状況パターンとして出力することを特徴とする経路案内システム。請求項3に記載の経路案内システムにおいて、前記交通状況照合手段は、前記最も短い距離が所定閾値以下のとき、前記現況交通情報に類似した前記交通状況パターンを出力し、前記複数のクラスタの内の、前記現況交通情報に基づく交通状況を表す前記交通情報ベクトルから前記最も短い距離にある前記交通情報ベクトルで表される前記交通状況パターンに対応するクラスタに応じて、前記所定閾値が定められることを特徴とする経路案内システム。交通情報を用いれば、その時々の交通状況に応じた動的な最適経路案内ができる。ただし、経路案内のリクエストがあるたびに最新の交通情報を用いて経路探索を実行する必要があるので、演算処理に時間が掛かる。一方、経路探索の実行時間を短縮するため、出発地、目的地として設定可能な全ての地点をそれぞれ出発地、目的地とする全ての組み合わせについて、事前に全出発地から全目的地までの間の経路を探索全探索をした結果をデータベースに格納しておくならば、経路案内リクエストを受けた際には、指定された出発地及び目的地に該当する出発地-目的地間の経路をデータベースから読み出すことにより、経路案内リクエストの度に経路探索演算処理が不要となり、データベースの探索処理により経路が求まる分、経路案内リクエストへの応答性が高まる。しかし、事前に可能な出発地目的地間の経路を全探索しておく方法では、時々刻々と変化する交通状況に応じた最適経路を提供することはできない。また、事前に想定しうる全ての交通状況の組み合わせを反映させた上で、前述の全探索を実行しておけば交通状況を反映させることが可能であるが、交通状況の状態数が無数に存在するため、全ての交通状況に対して事前に全探索を実行しておくことは現実的な手段とは言えない。上記課題を解決するため、本発明による経路案内システムは、時刻毎の交通情報に基づく複数の交通状況を複数の交通状況パターンに分類する交通状況分類手段と、複数の交通状況パターンの各々に対応して、複数の地点間のすべての組み合わせについての経路探索演算を行い、経路探索演算により得られる全ての経路を経路データベースに格納する経路データベース生成手段と、複数の交通状況パターンの中から、現況交通情報に類似した交通状況パターンを出力する交通状況照合手段と、交通状況照合手段により出力された交通状況パターンに基づき、経路データベースを参照して、出発地から目的地までの経路を検索し出力する経路情報検索手段とを備えることを特徴とする。本発明による経路案内システムは、現況交通情報に基づく経路の近似経路を事前探索により応答性を良く提供することを可能とする。以下、本発明を用いた経路探索システムの実施例について図面を用いて説明する。第1の実施例図1は、本実施例の経路案内システム100の構成図である。経路案内システム100は、交通情報データベース101と、交通状況分類装置102と、交通状況パターン103と、経路データベース生成装置104と、経路データベース105と、現況交通情報106と、交通状況照合装置107と、経路情報検索装置108と、地図データベース110とを有する。ナビゲーション装置150は、経路案内システム100の外部装置であり、経路案内インターフェース109を有する。経路案内システム100とナビゲーション装置150との間の入出力は、通信を介して行われる。経路案内システム100では、更新周期毎に各時点での交通情報を現況交通情報106として外部から収集している。この現況交通情報106は、路側に設置された感知機から得られる交通情報の他、プローブカーフローティングカーにより計測された走行データがアップロードされてきたプローブデータによる交通情報などがある。更新周期毎に収集された現況交通情報106は、過去の交通情報を蓄積する交通情報データベース101に記憶される。交通情報データベース101には、リンク旅行時間またはリンク代表速度などの数値データで表された過去の交通情報が格納されている。交通状況分類装置102では、交通情報データベース101に格納された交通情報を読み出し、クラスタリングによって代表的な複数の交通状況パターン103を生成する。クラスタリングの手法には様々な公知の手法がある。交通状況分類装置102は、例えばK-means法を用いて過去の交通状況のクラスタリングを行う。交通状況分類装置102が行う処理の詳細は後述する。交通状況パターン103は交通状況分類装置102によって生成される。交通状況パターン103は、クラスタリングによって生成されているため、過去に計測された交通状況そのものを表しているわけではない。過去の交通状況を複数の交通状況パターン103に分類し、各交通状況パターンは、過去の交通状況の内の互いに類似するいくつかのケースを代表する近似値として表される。交通状況パターン103のそれぞれには固有のパターン番号が付されている。経路データベース生成装置104では、交通状況パターン103に対応する交通情報に基づいた経路探索コストと、地図データベース110に格納された地図データとを用いて、ダイクストラ法などの経路探索アルゴリズムにより、交通状況パターン103のそれぞれに対応した全地点間の全ての組み合わせについての経路探索演算を行い、その経路探索演算により得られる全経路を、経路データベース105に格納する。ここで全地点間の全ての組み合わせについての経路探索演算とは、出発地と目的地となりうるノードの全ての組み合わせについて、経路探索を行うことである。即ち、地図データベース110から経路探索の対象エリア内の全てのノードを取得し、それを出発地または目的地とした全ての組み合わせ但し、同一ノード同士は除くについて、それぞれの交通状況パターン103に対応する交通情報に基づいた経路探索コストにより予め経路探索を行っておく。経路データベース105には、交通状況パターン103のそれぞれに対応して、図2に示す表のように、出発地ノードと目的地ノードを結ぶ経路を構成するリンク列が格納される。このリンク列は、出発地となるノードから目的地となるノードまでの経路を構成する道路リンクのリンク番号を、出発地から目的地まで並べたものである。交通状況照合装置107では、現況交通情報106と交通状況パターン103を比較し、現況交通情報106に最も類似した交通状況パターン103のパターン番号を出力する。この処理の詳細は後述する。経路情報検索装置108では、交通状況照合装置107が出力したパターン番号の交通状況パターンに対応する全ノード間の全ての組み合わせについての経路探索結果を格納する経路データベース105を参照し、ナビゲーション装置150の経路案内インターフェース109から入力される出発地から目的地までの経路を検索して、その経路を構成するリンク列をナビゲーション装置150の経路案内インターフェース109へ出力する。ナビゲーション装置150の経路案内インターフェース109では、利用者から出発地と目的地の入力を受け付けて、経路案内システム100の経路情報検索装置108に送り、経路情報検索装置108が出力したその出発地と目的地を結ぶ経路300の経路情報を受け取る。そして経路案内インターフェース109では、経路情報検索装置108からリンク列を受け取ると、図3の画面のように、出発地と目的地を表示した地図の上に、リンク列に該当する経路を強調表示する。次に、交通状況分類装置102の詳細を説明する。交通状況分類装置102は、複数リンクの交通情報を要素とする多次元ベクトルをクラスタリングの対象とする。1リンクの交通情報を1つの座標軸上の値として考えると、例えば1000本のリンクを含むエリアの交通状況は、1000次元の交通情報空間上の交通情報ベクトルとして表される。この交通情報ベクトルが有する1000個の成分は、それぞれ1000本のリンクのリンク旅行時間またはリンク代表速度など、それぞれのリンクの移動コストに関する数値を表す。このリンク旅行時間またはリンク代表速度などの数値データは、上述したように交通情報データベース101に格納されており、過去の交通情報に基づいている。このような交通情報ベクトルが交通情報の更新周期毎に1本ずつ存在する。即ち、1本の交通情報ベクトルは、ある時刻の交通情報に基づく1000本のリンクの交通状況を表している。交通状況分類装置102は、複数回の交通情報更新で生成されたそれらの交通情報ベクトルをクラスタリングし、複数個の代表的なクラスタを得る。各クラスタには、複数の異なる時刻の交通情報に基づく複数の交通状況を表す複数の交通情報ベクトルが分類される。それらの複数の交通情報ベクトルの重心に対応する交通情報ベクトル、即ち各クラスタの重心ベクトルで、交通状況パターン103が表される。しかしリンク数が多い場合には、クラスタリングの演算量は膨大なものとなる。そのような場合には、特許文献2に開示されているように、交通情報ベクトルに対する主成分分析により得られる基底の線形合成により、交通情報を近似表現するのが好ましい。即ち、まず交通情報ベクトルを主成分分析で得られる低次元の特徴空間に特徴空間ベクトルとして射影し、次に特徴空間における特徴空間ベクトルを対象とするクラスタリングを行うと、演算量を大幅に減らすことができる。これを説明したものが図4である。図4は主成分分析で得られた複数の特徴空間ベクトルの射影点の座標401を、説明の便宜上、特徴空間から2つの基底W1およびW2を切り出した2次元の部分空間について示している。実際の特徴空間の次数は、例えば主成分分析における累積寄与率を指標として用いて、元の交通情報ベクトルの持つ90の情報を近似して保持するように設定することができる。この特徴空間ベクトル射影点を対象とするクラスタリングを行うと、複数のクラスタ501が求まる。複数のクラスタ501のそれぞれの重心502を、特徴空間から元の交通情報空間に逆射影して得られる複数の重心ベクトルの各々は、交通情報空間でクラスタリングを行って得られる各クラスタの重心ベクトルの近似ベクトルである。この近似ベクトルを交通状況パターン103として用いることができる。次に、交通状況照合装置107の詳細を説明する。交通状況照合装置107は現況交通情報106に基づく交通状況を表す交通情報ベクトルと複数の交通状況パターン103を表す複数の交通情報ベクトルをそれぞれ比較して、その差分に基づいて得られる複数の差分ベクトルを相互比較し、ノルムが最も小さい差分ベクトルに対応する交通情報ベクトルで表される交通状況パターン103のパターン番号を出力する。前述のように交通状況分類装置102が複数の交通情報ベクトルを特徴空間に射影してクラスタリングを行う場合には、交通状況照合装置107も現況交通情報106に基づく交通状況を表す交通情報ベクトルを特徴空間に射影することにより、交通状況照合装置107は特徴空間において現況交通情報106と交通状況パターン103との照合を行うことになる。複数の重心502、503等は複数の交通状況パターン103のそれぞれに対応する特徴空間上の座標に位置する。現況交通情報106に基づく交通状況を表す交通情報ベクトルを特徴空間に射影した座標が座標601である。この例で交通状況照合装置107は、特徴空間上における座標601に最も近い重心を探し、その重心に対応する交通状況パターン103のパターン番号を出力する。図4の例では、座標601に最も近い重心503に対応する交通状況パターン103のパターン番号が出力されることになる。経路案内システム100の動作をフローチャートで表すと図5、図6のようになる。図5は、複数の交通状況パターン103の生成と、複数の交通状況パターン103のそれぞれに対応した全地点間の全ての組み合わせについての経路探索演算とを含む、経路案内システム100によって予め経路データベース804が準備される処理手順を示す。図6は、指定された出発地と目的地について出発地から目的地まで経路検索を行う際に経路案内システム100によって行われる処理手順を示す。なお、ここではクラスタリングを前述のように特徴空間で行う場合について説明する。図5のステップS701では、交通状況分類装置102による交通情報データベース101からのデータ読み出しが行われる。交通状況分類装置102は経路探索の対象とするエリアにおける過去の交通情報を取得する。ステップS702では、交通状況分類装置102による交通情報ベクトルの主成分分析の演算が行われる。交通状況分類装置102は、ステップS701で取得した交通情報に基づく交通状況を表す交通情報ベクトルに対する主成分分析により得られる基底に対応する特徴空間を生成する。なお、この時得られた基底は、後述するステップ705やステップ712でも使用されるため、別途記憶装置図示せずに格納されているものとする。ステップS703では、交通状況分類装置102は、当該特徴空間に該交通情報ベクトルを射影する演算を行う。ステップS701で取得した交通情報に対応する特徴空間への射影により、特徴空間ベクトル射影点が得られる。ステップS704では、交通状況分類装置102によるクラスタリングの演算が行われ、当該射影点が分類されたクラスタが形成される。クラスタリングには様々な手法があるが、例えばK-means法を用いれば、複数の球状クラスタが形成され、各クラスタに分類された射影点から該クラスタのクラスタ重心への距離が最短であることが保証される。ステップS705では、交通状況分類装置102による射影点およびクラスタ重心の交通情報空間への逆射影演算が行われる。クラスタ重心が逆射影されて得られる重心ベクトルから、交通状況パターン103が得られる。S706は経路データベース生成装置104内のループ処理である。経路データベース生成装置104では、交通状況パターンのそれぞれに対応する交通情報に基づく経路探索コストを用いて、ステップS707からの全ノードに関するループ処理において経路探索演算708を行い、探索結果を経路データベース105に格納する。具体的には、交通状況パターンに対応する交通情報は各リンクにおける旅行時間情報であるため、これを経路探索に用いられるリンクコストとして用いる、あるいはリンクコストに反映させるなどして経路探索を行う。以上により、交通状況パターン103のそれぞれに対応する全ノード間の経路に関する経路情報が得られる。図6のステップS709において、経路情報検索装置108は、ナビゲーション装置150の経路案内インターフェース109を介してユーザにより入力された出発地および目的地を含む経路案内リクエストを受信する。ステップS710では、交通状況照合装置107への現況交通情報106の入力処理が行われる。ステップS711では、交通状況照合装置107により、現況交通情報106に基づく交通状況を表す交通情報ベクトルの特徴空間への射影の演算を行う。交通状況照合装置107では当該交通情報ベクトルをステップS702で得られた特徴空間に射影する。この時用いる基底は、前述の通り、予めステップS702で求められていた基底を用いる。ステップS712は交通状況照合装置107におけるループ処理である。ステップS713において、交通状況照合装置107は、ステップS711で得られた現況交通情報106に基づく交通状況を表す交通情報ベクトルの特徴空間における射影点と、交通状況パターン103のそれぞれに対応するクラスタ重心との距離を算出する。ステップS714において、交通状況照合装置107は、ステップS713で算出した射影点からの距離の内で最も短い距離にあるクラスタ重心に対応する交通状況パターン103のパターン番号を、現況交通情報に最も類似した交通状況パターンのパターン番号として、経路情報検索装置108に出力する。ステップS715では、経路情報検索装置108は、経路データベース105に検索リクエストを発行し、図5の処理で予め作成しておいた経路データベース804の経路を参照することで経路検索を行う。即ち、ナビゲーション装置150の経路案内インターフェース109を介して利用者により指定された出発地および目的地と、ステップS714で交通状況照合装置107から入力された交通状況パターン103のパターン番号とに基づき、該パターン番号に対応した該出発地から該目的地までの経路に関する経路情報を読み出す。読み出された経路情報に対応する経路は、現況交通情報106に最も類似した交通状況パターン103において検索された経路なので、現況交通情報106に基づいて実際に経路探索することで得られる経路に近似した近似経路である。ステップS716において、経路情報検索装置108は、ステップS715で読み出した該経路情報を、ナビゲーション装置150の経路案内インターフェース109に配信する。ナビゲーション装置150の経路案内インターフェース109は、経路情報検索装置108により出力された近似経路を、図3に示すように経路300として画面に表示する。図5に示すステップS701~S708で行われる処理と、図6に示すステップS709~S716で行われる処理とは互いに独立した処理である。ステップS701~S708は予めオフラインで実行される。例えばこの処理は、1ヶ月に1回などのように定期的に実施するようにしても良い。これに対しステップS709~S716は、ナビゲーション装置150からの経路案内リクエストに応じて、交通情報の更新周期、即ち現況交通情報の取得と同期してリアルタイムに実行される。こうすることで、経路案内システム100は、ナビゲーション装置150の経路案内インターフェース109から入力された出発地から目的地までの上述した近似経路を速やかに提供することができる。この近似経路は、現況交通情報106に突発的な交通規制等の情報が含まれている場合であっても、その情報を含んだ現況交通情報106に最も類似した交通状況パターン103において検索された経路である。したがって、実際の道路条件に応じた経路に準じる近似経路が得られることになる。ステップS712として表した交通状況照合装置107におけるループ処理の中で、ステップS713において、交通状況照合装置107は、ステップS711で得られた現況交通情報106に基づく交通状況を表す交通情報ベクトルの特徴空間における射影点と、交通状況パターン103のそれぞれに対応するクラスタ重心との距離を算出する。しかし、ステップS703において、交通状況分類装置102により、交通状況パターン103のそれぞれに対応する交通情報ベクトルを特徴空間に射影する演算が行われない場合は、ステップS711においても、交通状況照合装置107により、現況交通情報106に基づく交通状況を表す交通情報ベクトルの特徴空間への射影の演算を行わないこととしてもよい。この場合、ステップS713において、交通状況照合装置107は、ステップS711で得られた現況交通情報106に基づく交通状況を表す交通情報ベクトルから、交通状況パターン103のそれぞれに対応するクラスタの重心に対応する交通情報ベクトル重心ベクトルまでの距離を算出することとしてもよい。第2の実施例経路案内の精度を上げる手段としては、特開2007-192727号公報特許文献1のように、出発地近傍では経路探索のコストに現況交通情報を用い、出発地遠方において、現況交通情報の誤差が統計交通情報の誤差を上回る範囲では経路探索コストに統計交通情報を用いる手法が知られている。本実施例においては、その手法を応用して実施例1の経路案内システムの精度を向上する方法を示す。図7は本実施例の経路案内システム800の構成図である。経路案内システム800の基本的な構成は図1の経路案内システム100と同様であるため、ここでは経路案内システム100と異なる構成要素について述べる。801は統計交通情報生成装置であり、交通情報データベース101に格納された過去の交通情報を用いて、統計交通情報を生成する。ここで言う統計交通情報とは、曜日祝祭日時間帯等で過去の交通情報の統計的代表値をとったものであり、例えば、日曜日10:00のリンク旅行時間やリンク代表速度といった情報が、統計交通情報データベース802に格納される。続いて経路データベース生成装置803の処理について述べる。経路案内システム100における経路データベース生成装置104は交通状況パターン103の交通情報のみを探索コストとして経路探索を行うが、経路データベース生成装置803は、交通状況パターン103と統計交通情報データベース802双方の交通情報を探索コストとして経路探索を行う。特許文献1にも言われているように、ある時点を起点としたとき、その時点での現況交通情報と統計交通情報の誤差は時間の経過とともに図8のように反転する。両者の誤差が反転し、現況交通情報の誤差が統計交通情報の誤差を上回る経過時間を閾値901とする。交通状況パターン103は交通状況照合装置107において現況交通情報106と比較照合の対象となる情報であるため、経路データベース生成装置803においては、閾値901を交通状況パターン103と統計交通情報データベース802を使い分ける閾値として用いる。すなわち、経路データベース生成装置803においてダイクストラ法を用いて探索を行う場合、探索開始時点では交通状況パターン103を探索コストとして計算を行い、新たなノードへの最短時間経路が確定するたびに、当該ノードへの到達時間と閾値901との比較を行い、到達時間が閾値901を上回った時点で、探索コストを交通状況パターン103から統計交通情報データベース802に切り替える。以上に述べた経路データベース生成装置803の処理をフローチャートで表すと図9のようになる。S1001は全ノードに関するループであり、各ノードを出発ノードとしてS1002~S1006の探索処理を行う。S1002は探索の初期化であり、交通状況パターン103の交通情報を探索コストとして各リンクに設定する。S1003は出発点近傍のノードから最短時間経路を順次確定する処理である。S1004は終了判定であり、当該出発ノードに対して、全ノードへの最短時間経路が確定した場合は探索処理を終了し、確定していない場合は探索処理を継続する。S1005はS1003で最短時間経路が確定したノードへの到達時間と閾値901の比較であり、到達時間が閾値を上回ったときは、S1006において統計交通情報データベース802の交通情報を、確定済みの最短経路に含まれていない各リンクの探索コストとして設定する。以上の処理により、経路データベース生成装置803は交通状況パターン103と統計交通情報データベース802を使い分けて全探索を行う。また、このようにして生成された経路データベース804を参照することで、経路情報検索装置108は、交通状況照合装置107による現況交通情報106と交通状況パターン103の照合結果に基づいて、交通状況パターン103と統計交通情報データベース802双方を加味した経路情報を配信することができる。