経路案内システム
【課題】現況交通情報に基づく経路に準じた近似経路を速やかに出力する。
【解決手段】経路案内システムは、時刻毎の交通情報に基づく複数の交通状況を複数の交通状況パターンに分類する交通状況分類手段と、複数の交通状況パターンの各々に対応して、複数の地点間のすべての組み合わせについての経路探索演算を行い、経路探索演算により得られる全ての経路を経路データベースに格納する経路データベース生成手段と、複数の交通状況パターンの中から、現況交通情報に類似した交通状況パターンを出力する交通状況照合手段と、交通状況照合手段により出力された交通状況パターンに基づき、経路データベースを参照して、出発地から目的地までの経路を検索し出力する経路情報検索手段とを備える。
【解決手段】経路案内システムは、時刻毎の交通情報に基づく複数の交通状況を複数の交通状況パターンに分類する交通状況分類手段と、複数の交通状況パターンの各々に対応して、複数の地点間のすべての組み合わせについての経路探索演算を行い、経路探索演算により得られる全ての経路を経路データベースに格納する経路データベース生成手段と、複数の交通状況パターンの中から、現況交通情報に類似した交通状況パターンを出力する交通状況照合手段と、交通状況照合手段により出力された交通状況パターンに基づき、経路データベースを参照して、出発地から目的地までの経路を検索し出力する経路情報検索手段とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は経路案内サービスに関わる。
【背景技術】
【０００２】
本技術分野の背景技術として、特開２００７−１９２７２７号公報（特許文献１）がある。この特許文献１には、精度の高い交通情報を利用して、目的地までの推奨経路を探索する技術が開示されている。
【０００３】
また、特許文献２には、交通情報ベクトルに対する主成分分析により得られる基底の線形合成により、交通情報を近似表現する技術が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００７−１９２７２７号公報
【特許文献２】特開２００６−２５１９４１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
交通情報を用いれば、その時々の交通状況に応じた動的な最適経路案内ができる。ただし、経路案内のリクエストがあるたびに最新の交通情報を用いて経路探索を実行する必要があるので、演算処理に時間が掛かる。
【０００６】
一方、経路探索の実行時間を短縮するため、出発地、目的地として設定可能な全ての地点をそれぞれ出発地、目的地とする全ての組み合わせについて、事前に全出発地から全目的地までの間の経路を探索（全探索）をした結果をデータベースに格納しておくならば、経路案内リクエストを受けた際には、指定された出発地及び目的地に該当する出発地−目的地間の経路をデータベースから読み出すことにより、経路案内リクエストの度に経路探索演算処理が不要となり、データベースの探索処理により経路が求まる分、経路案内リクエストへの応答性が高まる。
【０００７】
しかし、事前に可能な出発地目的地間の経路を全探索しておく方法では、時々刻々と変化する交通状況に応じた最適経路を提供することはできない。また、事前に想定しうる全ての交通状況の組み合わせを反映させた上で、前述の全探索を実行しておけば交通状況を反映させることが可能であるが、交通状況の状態数が無数に存在するため、全ての交通状況に対して事前に全探索を実行しておくことは現実的な手段とは言えない。
【課題を解決するための手段】
【０００８】
上記課題を解決するため、本発明による経路案内システムは、時刻毎の交通情報に基づく複数の交通状況を複数の交通状況パターンに分類する交通状況分類手段と、複数の交通状況パターンの各々に対応して、複数の地点間のすべての組み合わせについての経路探索演算を行い、経路探索演算により得られる全ての経路を経路データベースに格納する経路データベース生成手段と、複数の交通状況パターンの中から、現況交通情報に類似した交通状況パターンを出力する交通状況照合手段と、交通状況照合手段により出力された交通状況パターンに基づき、経路データベースを参照して、出発地から目的地までの経路を検索し出力する経路情報検索手段とを備えることを特徴とする。
【発明の効果】
【０００９】
本発明による経路案内システムは、現況交通情報に基づく経路の近似経路を事前探索により応答性を良く提供することを可能とする。
【図面の簡単な説明】
【００１０】
【図１】第１の実施例における経路案内システムの構成図である。
【図２】経路データベースのデータ構成を示す図である。
【図３】経路案内インターフェースの表示画面である。
【図４】交通情報を特徴空間に射影しクラスタリングした重心により交通状況照合を行う模式図である。
【図５】経路案内システムにおける経路データベースの作成処理フローである。
【図６】経路案内システムにおける経路探索の処理フローである。
【図７】第２の実施例における経路案内システムの構成図である。
【図８】現況交通情報と統計交通情報の時間経過による誤差変化傾向のグラフである。
【図９】経路案内システムの処理フローである。
【発明を実施するための形態】
【００１１】
以下、本発明を用いた経路探索システムの実施例について図面を用いて説明する。
【００１２】
（第１の実施例）
図１は、本実施例の経路案内システム１００の構成図である。経路案内システム１００は、交通情報データベース１０１と、交通状況分類装置１０２と、交通状況パターン１０３と、経路データベース生成装置１０４と、経路データベース１０５と、現況交通情報１０６と、交通状況照合装置１０７と、経路情報検索装置１０８と、地図データベース１１０とを有する。ナビゲーション装置１５０は、経路案内システム１００の外部装置であり、経路案内インターフェース１０９を有する。経路案内システム１００とナビゲーション装置１５０との間の入出力は、通信を介して行われる。
【００１３】
経路案内システム１００では、更新周期毎に各時点での交通情報を現況交通情報１０６として外部から収集している。この現況交通情報１０６は、路側に設置された感知機から得られる交通情報の他、プローブカー（フローティングカー）により計測された走行データがアップロードされてきたプローブデータによる交通情報などがある。更新周期毎に収集された現況交通情報１０６は、過去の交通情報を蓄積する交通情報データベース１０１に記憶される。
【００１４】
交通情報データベース１０１には、リンク旅行時間またはリンク代表速度などの数値データで表された過去の交通情報が格納されている。
【００１５】
交通状況分類装置１０２では、交通情報データベース１０１に格納された交通情報を読み出し、クラスタリングによって代表的な複数の交通状況パターン１０３を生成する。クラスタリングの手法には様々な公知の手法がある。交通状況分類装置１０２は、例えばＫ−ｍｅａｎｓ法を用いて過去の交通状況のクラスタリングを行う。交通状況分類装置１０２が行う処理の詳細は後述する。
【００１６】
交通状況パターン１０３は交通状況分類装置１０２によって生成される。交通状況パターン１０３は、クラスタリングによって生成されているため、過去に計測された交通状況そのものを表しているわけではない。過去の交通状況を複数の交通状況パターン１０３に分類し、各交通状況パターンは、過去の交通状況の内の互いに類似するいくつかのケースを代表する近似値として表される。交通状況パターン１０３のそれぞれには固有のパターン番号が付されている。
【００１７】
経路データベース生成装置１０４では、交通状況パターン１０３に対応する交通情報に基づいた経路探索コストと、地図データベース１１０に格納された地図データとを用いて、ダイクストラ法などの経路探索アルゴリズムにより、交通状況パターン１０３のそれぞれに対応した全地点間の全ての組み合わせについての経路探索演算を行い、その経路探索演算により得られる全経路を、経路データベース１０５に格納する。ここで全地点間の全ての組み合わせについての経路探索演算とは、出発地と目的地となりうるノードの全ての組み合わせについて、経路探索を行うことである。即ち、地図データベース１１０から経路探索の対象エリア内の全てのノードを取得し、それを出発地または目的地とした全ての組み合わせ（但し、同一ノード同士は除く）について、それぞれの交通状況パターン１０３に対応する交通情報に基づいた経路探索コストにより予め経路探索を行っておく。
【００１８】
経路データベース１０５には、交通状況パターン１０３のそれぞれに対応して、図２に示す表のように、出発地ノードと目的地ノードを結ぶ経路を構成するリンク列が格納される。このリンク列は、出発地となるノードから目的地となるノードまでの経路を構成する道路リンクのリンク番号を、出発地から目的地まで並べたものである。
【００１９】
交通状況照合装置１０７では、現況交通情報１０６と交通状況パターン１０３を比較し、現況交通情報１０６に最も類似した交通状況パターン１０３のパターン番号を出力する。この処理の詳細は後述する。
【００２０】
経路情報検索装置１０８では、交通状況照合装置１０７が出力したパターン番号の交通状況パターンに対応する全ノード間の全ての組み合わせについての経路探索結果を格納する経路データベース１０５を参照し、ナビゲーション装置１５０の経路案内インターフェース１０９から入力される出発地から目的地までの経路を検索して、その経路を構成するリンク列をナビゲーション装置１５０の経路案内インターフェース１０９へ出力する。
【００２１】
ナビゲーション装置１５０の経路案内インターフェース１０９では、利用者から出発地と目的地の入力を受け付けて、経路案内システム１００の経路情報検索装置１０８に送り、経路情報検索装置１０８が出力したその出発地と目的地を結ぶ経路３００の経路情報を受け取る。そして経路案内インターフェース１０９では、経路情報検索装置１０８からリンク列を受け取ると、図３の画面のように、出発地と目的地を表示した地図の上に、リンク列に該当する経路を強調表示する。
【００２２】
次に、交通状況分類装置１０２の詳細を説明する。交通状況分類装置１０２は、複数リンクの交通情報を要素とする多次元ベクトルをクラスタリングの対象とする。１リンクの交通情報を１つの座標軸上の値として考えると、例えば１０００本のリンクを含むエリアの交通状況は、１０００次元の交通情報空間上の交通情報ベクトルとして表される。この交通情報ベクトルが有する１０００個の成分は、それぞれ１０００本のリンクのリンク旅行時間またはリンク代表速度など、それぞれのリンクの移動コストに関する数値を表す。このリンク旅行時間またはリンク代表速度などの数値データは、上述したように交通情報データベース１０１に格納されており、過去の交通情報に基づいている。このような交通情報ベクトルが交通情報の更新周期毎に１本ずつ存在する。即ち、１本の交通情報ベクトルは、ある時刻の交通情報に基づく１０００本のリンクの交通状況を表している。交通状況分類装置１０２は、複数回の交通情報更新で生成されたそれらの交通情報ベクトルをクラスタリングし、複数個の代表的なクラスタを得る。各クラスタには、複数の異なる時刻の交通情報に基づく複数の交通状況を表す複数の交通情報ベクトルが分類される。それらの複数の交通情報ベクトルの重心に対応する交通情報ベクトル、即ち各クラスタの重心ベクトルで、交通状況パターン１０３が表される。
【００２３】
しかしリンク数が多い場合には、クラスタリングの演算量は膨大なものとなる。そのような場合には、特許文献２に開示されているように、交通情報ベクトルに対する主成分分析により得られる基底の線形合成により、交通情報を近似表現するのが好ましい。即ち、まず交通情報ベクトルを主成分分析で得られる低次元の特徴空間に特徴空間ベクトルとして射影し、次に特徴空間における特徴空間ベクトルを対象とするクラスタリングを行うと、演算量を大幅に減らすことができる。これを説明したものが図４である。図４は主成分分析で得られた複数の特徴空間ベクトルの射影点の座標４０１を、説明の便宜上、特徴空間から２つの基底Ｗ１およびＷ２を切り出した２次元の部分空間について示している。実際の特徴空間の次数は、例えば主成分分析における累積寄与率を指標として用いて、元の交通情報ベクトルの持つ９０％の情報を近似して保持するように設定することができる。この特徴空間ベクトル（射影点）を対象とするクラスタリングを行うと、複数のクラスタ５０１が求まる。複数のクラスタ５０１のそれぞれの重心５０２を、特徴空間から元の交通情報空間に逆射影して得られる複数の重心ベクトルの各々は、交通情報空間でクラスタリングを行って得られる各クラスタの重心ベクトルの近似ベクトルである。この近似ベクトルを交通状況パターン１０３として用いることができる。
【００２４】
次に、交通状況照合装置１０７の詳細を説明する。交通状況照合装置１０７は現況交通情報１０６に基づく交通状況を表す交通情報ベクトルと複数の交通状況パターン１０３を表す複数の交通情報ベクトルをそれぞれ比較して、その差分に基づいて得られる複数の差分ベクトルを相互比較し、ノルムが最も小さい差分ベクトルに対応する交通情報ベクトルで表される交通状況パターン１０３のパターン番号を出力する。
【００２５】
前述のように交通状況分類装置１０２が複数の交通情報ベクトルを特徴空間に射影してクラスタリングを行う場合には、交通状況照合装置１０７も現況交通情報１０６に基づく交通状況を表す交通情報ベクトルを特徴空間に射影することにより、交通状況照合装置１０７は特徴空間において現況交通情報１０６と交通状況パターン１０３との照合を行うことになる。複数の重心５０２、５０３等は複数の交通状況パターン１０３のそれぞれに対応する特徴空間上の座標に位置する。現況交通情報１０６に基づく交通状況を表す交通情報ベクトルを特徴空間に射影した座標が座標６０１である。この例で交通状況照合装置１０７は、特徴空間上における座標６０１に最も近い重心を探し、その重心に対応する交通状況パターン１０３のパターン番号を出力する。図４の例では、座標６０１に最も近い重心５０３に対応する交通状況パターン１０３のパターン番号が出力されることになる。
【００２６】
経路案内システム１００の動作をフローチャートで表すと図５、図６のようになる。図５は、複数の交通状況パターン１０３の生成と、複数の交通状況パターン１０３のそれぞれに対応した全地点間の全ての組み合わせについての経路探索演算とを含む、経路案内システム１００によって予め経路データベース８０４が準備される処理手順を示す。図６は、指定された出発地と目的地について出発地から目的地まで経路検索を行う際に経路案内システム１００によって行われる処理手順を示す。なお、ここではクラスタリングを前述のように特徴空間で行う場合について説明する。
【００２７】
図５のステップＳ７０１では、交通状況分類装置１０２による交通情報データベース１０１からのデータ読み出しが行われる。交通状況分類装置１０２は経路探索の対象とするエリアにおける過去の交通情報を取得する。ステップＳ７０２では、交通状況分類装置１０２による交通情報ベクトルの主成分分析の演算が行われる。交通状況分類装置１０２は、ステップＳ７０１で取得した交通情報に基づく交通状況を表す交通情報ベクトルに対する主成分分析により得られる基底に対応する特徴空間を生成する。なお、この時得られた基底は、後述するステップ７０５やステップ７１２でも使用されるため、別途記憶装置（図示せず）に格納されているものとする。ステップＳ７０３では、交通状況分類装置１０２は、当該特徴空間に該交通情報ベクトルを射影する演算を行う。ステップＳ７０１で取得した交通情報に対応する特徴空間への射影により、特徴空間ベクトル（射影点）が得られる。ステップＳ７０４では、交通状況分類装置１０２によるクラスタリングの演算が行われ、当該射影点が分類されたクラスタが形成される。クラスタリングには様々な手法があるが、例えばＫ−ｍｅａｎｓ法を用いれば、複数の球状クラスタが形成され、各クラスタに分類された射影点から該クラスタのクラスタ重心への距離が最短であることが保証される。ステップＳ７０５では、交通状況分類装置１０２による射影点およびクラスタ重心の交通情報空間への逆射影演算が行われる。クラスタ重心が逆射影されて得られる重心ベクトルから、交通状況パターン１０３が得られる。
【００２８】
Ｓ７０６は経路データベース生成装置１０４内のループ処理である。経路データベース生成装置１０４では、交通状況パターンのそれぞれに対応する交通情報に基づく経路探索コストを用いて、ステップＳ７０７からの全ノードに関するループ処理において経路探索演算７０８を行い、探索結果を経路データベース１０５に格納する。具体的には、交通状況パターンに対応する交通情報は各リンクにおける旅行時間情報であるため、これを経路探索に用いられるリンクコストとして用いる、あるいはリンクコストに反映させるなどして経路探索を行う。以上により、交通状況パターン１０３のそれぞれに対応する全ノード間の経路に関する経路情報が得られる。
【００２９】
図６のステップＳ７０９において、経路情報検索装置１０８は、ナビゲーション装置１５０の経路案内インターフェース１０９を介してユーザにより入力された出発地および目的地を含む経路案内リクエストを受信する。ステップＳ７１０では、交通状況照合装置１０７への現況交通情報１０６の入力処理が行われる。ステップＳ７１１では、交通状況照合装置１０７により、現況交通情報１０６に基づく交通状況を表す交通情報ベクトルの特徴空間への射影の演算を行う。交通状況照合装置１０７では当該交通情報ベクトルをステップＳ７０２で得られた特徴空間に射影する。この時用いる基底は、前述の通り、予めステップＳ７０２で求められていた基底を用いる。
【００３０】
ステップＳ７１２は交通状況照合装置１０７におけるループ処理である。ステップＳ７１３において、交通状況照合装置１０７は、ステップＳ７１１で得られた現況交通情報１０６に基づく交通状況を表す交通情報ベクトルの特徴空間における射影点と、交通状況パターン１０３のそれぞれに対応するクラスタ重心との距離を算出する。
【００３１】
ステップＳ７１４において、交通状況照合装置１０７は、ステップＳ７１３で算出した射影点からの距離の内で最も短い距離にあるクラスタ重心に対応する交通状況パターン１０３のパターン番号を、現況交通情報に最も類似した交通状況パターンのパターン番号として、経路情報検索装置１０８に出力する。ステップＳ７１５では、経路情報検索装置１０８は、経路データベース１０５に検索リクエストを発行し、図５の処理で予め作成しておいた経路データベース８０４の経路を参照することで経路検索を行う。即ち、ナビゲーション装置１５０の経路案内インターフェース１０９を介して利用者により指定された出発地および目的地と、ステップＳ７１４で交通状況照合装置１０７から入力された交通状況パターン１０３のパターン番号とに基づき、該パターン番号に対応した該出発地から該目的地までの経路に関する経路情報を読み出す。読み出された経路情報に対応する経路は、現況交通情報１０６に最も類似した交通状況パターン１０３において検索された経路なので、現況交通情報１０６に基づいて実際に経路探索することで得られる経路に近似した近似経路である。
【００３２】
ステップＳ７１６において、経路情報検索装置１０８は、ステップＳ７１５で読み出した該経路情報を、ナビゲーション装置１５０の経路案内インターフェース１０９に配信する。ナビゲーション装置１５０の経路案内インターフェース１０９は、経路情報検索装置１０８により出力された近似経路を、図３に示すように経路３００として画面に表示する。
【００３３】
図５に示すステップＳ７０１〜Ｓ７０８で行われる処理と、図６に示すステップＳ７０９〜Ｓ７１６で行われる処理とは互いに独立した処理である。ステップＳ７０１〜Ｓ７０８は予めオフラインで実行される。例えばこの処理は、１ヶ月に１回などのように定期的に実施するようにしても良い。これに対しステップＳ７０９〜Ｓ７１６は、ナビゲーション装置１５０からの経路案内リクエストに応じて、交通情報の更新周期、即ち現況交通情報の取得と同期してリアルタイムに実行される。こうすることで、経路案内システム１００は、ナビゲーション装置１５０の経路案内インターフェース１０９から入力された出発地から目的地までの上述した近似経路を速やかに提供することができる。この近似経路は、現況交通情報１０６に突発的な交通規制等の情報が含まれている場合であっても、その情報を含んだ現況交通情報１０６に最も類似した交通状況パターン１０３において検索された経路である。したがって、実際の道路条件に応じた経路に準じる近似経路が得られることになる。
【００３４】
ステップＳ７１２として表した交通状況照合装置１０７におけるループ処理の中で、ステップＳ７１３において、交通状況照合装置１０７は、ステップＳ７１１で得られた現況交通情報１０６に基づく交通状況を表す交通情報ベクトルの特徴空間における射影点と、交通状況パターン１０３のそれぞれに対応するクラスタ重心との距離を算出する。しかし、ステップＳ７０３において、交通状況分類装置１０２により、交通状況パターン１０３のそれぞれに対応する交通情報ベクトルを特徴空間に射影する演算が行われない場合は、ステップＳ７１１においても、交通状況照合装置１０７により、現況交通情報１０６に基づく交通状況を表す交通情報ベクトルの特徴空間への射影の演算を行わないこととしてもよい。この場合、ステップＳ７１３において、交通状況照合装置１０７は、ステップＳ７１１で得られた現況交通情報１０６に基づく交通状況を表す交通情報ベクトルから、交通状況パターン１０３のそれぞれに対応するクラスタの重心に対応する交通情報ベクトル（重心ベクトル）までの距離を算出することとしてもよい。
【００３５】
（第２の実施例）
経路案内の精度を上げる手段としては、特開２００７−１９２７２７号公報（特許文献１）のように、出発地近傍では経路探索のコストに現況交通情報を用い、出発地遠方において、現況交通情報の誤差が統計交通情報の誤差を上回る範囲では経路探索コストに統計交通情報を用いる手法が知られている。本実施例においては、その手法を応用して実施例１の経路案内システムの精度を向上する方法を示す。
【００３６】
図７は本実施例の経路案内システム８００の構成図である。経路案内システム８００の基本的な構成は図１の経路案内システム１００と同様であるため、ここでは経路案内システム１００と異なる構成要素について述べる。
【００３７】
８０１は統計交通情報生成装置であり、交通情報データベース１０１に格納された過去の交通情報を用いて、統計交通情報を生成する。ここで言う統計交通情報とは、曜日・祝祭日・時間帯等で過去の交通情報の統計的代表値をとったものであり、例えば、日曜日１０：００のリンク旅行時間やリンク代表速度といった情報が、統計交通情報データベース８０２に格納される。
【００３８】
続いて経路データベース生成装置８０３の処理について述べる。経路案内システム１００における経路データベース生成装置１０４は交通状況パターン１０３の交通情報のみを探索コストとして経路探索を行うが、経路データベース生成装置８０３は、交通状況パターン１０３と統計交通情報データベース８０２双方の交通情報を探索コストとして経路探索を行う。特許文献１にも言われているように、ある時点を起点としたとき、その時点での現況交通情報と統計交通情報の誤差は時間の経過とともに図８のように反転する。両者の誤差が反転し、現況交通情報の誤差が統計交通情報の誤差を上回る経過時間を閾値９０１とする。交通状況パターン１０３は交通状況照合装置１０７において現況交通情報１０６と比較照合の対象となる情報であるため、経路データベース生成装置８０３においては、閾値９０１を交通状況パターン１０３と統計交通情報データベース８０２を使い分ける閾値として用いる。すなわち、経路データベース生成装置８０３においてダイクストラ法を用いて探索を行う場合、探索開始時点では交通状況パターン１０３を探索コストとして計算を行い、新たなノードへの最短時間経路が確定するたびに、当該ノードへの到達時間と閾値９０１との比較を行い、到達時間が閾値９０１を上回った時点で、探索コストを交通状況パターン１０３から統計交通情報データベース８０２に切り替える。
【００３９】
以上に述べた経路データベース生成装置８０３の処理をフローチャートで表すと図９のようになる。Ｓ１００１は全ノードに関するループであり、各ノードを出発ノードとしてＳ１００２〜Ｓ１００６の探索処理を行う。Ｓ１００２は探索の初期化であり、交通状況パターン１０３の交通情報を探索コストとして各リンクに設定する。Ｓ１００３は出発点近傍のノードから最短時間経路を順次確定する処理である。Ｓ１００４は終了判定であり、当該出発ノードに対して、全ノードへの最短時間経路が確定した場合は探索処理を終了し、確定していない場合は探索処理を継続する。Ｓ１００５はＳ１００３で最短時間経路が確定したノードへの到達時間と閾値９０１の比較であり、到達時間が閾値を上回ったときは、Ｓ１００６において統計交通情報データベース８０２の交通情報を、確定済みの最短経路に含まれていない各リンクの探索コストとして設定する。以上の処理により、経路データベース生成装置８０３は交通状況パターン１０３と統計交通情報データベース８０２を使い分けて全探索を行う。また、このようにして生成された経路データベース８０４を参照することで、経路情報検索装置１０８は、交通状況照合装置１０７による現況交通情報１０６と交通状況パターン１０３の照合結果に基づいて、交通状況パターン１０３と統計交通情報データベース８０２双方を加味した経路情報を配信することができる。
【符号の説明】
【００４０】
１００ 経路案内システム
１０１ 交通情報データベース
１０２ 交通状況分類装置
１０３ 交通状況パターン
１０４、８０３ 経路データベース生成装置
１０５、８０４ 経路データベース
１０６ 現況交通情報
１０７ 交通状況照合装置
１０８ 経路情報検索装置
１０９ 経路案内インターフェース
１１０ 地図データベース
１５０ ナビゲーション装置
４０１ 特徴空間ベクトルの座標
５０１ クラスタ
５０２ クラスタ重心の座標
５０３ 現況交通情報の特徴空間射影点の座標に最も近いクラスタ重心の座標
６０１ 現況交通情報の特徴空間射影点の座標
８０１ 統計交通情報生成装置
８０２ 統計交通情報データベース
【技術分野】
【０００１】
本発明は経路案内サービスに関わる。
【背景技術】
【０００２】
本技術分野の背景技術として、特開２００７−１９２７２７号公報（特許文献１）がある。この特許文献１には、精度の高い交通情報を利用して、目的地までの推奨経路を探索する技術が開示されている。
【０００３】
また、特許文献２には、交通情報ベクトルに対する主成分分析により得られる基底の線形合成により、交通情報を近似表現する技術が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００７−１９２７２７号公報
【特許文献２】特開２００６−２５１９４１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
交通情報を用いれば、その時々の交通状況に応じた動的な最適経路案内ができる。ただし、経路案内のリクエストがあるたびに最新の交通情報を用いて経路探索を実行する必要があるので、演算処理に時間が掛かる。
【０００６】
一方、経路探索の実行時間を短縮するため、出発地、目的地として設定可能な全ての地点をそれぞれ出発地、目的地とする全ての組み合わせについて、事前に全出発地から全目的地までの間の経路を探索（全探索）をした結果をデータベースに格納しておくならば、経路案内リクエストを受けた際には、指定された出発地及び目的地に該当する出発地−目的地間の経路をデータベースから読み出すことにより、経路案内リクエストの度に経路探索演算処理が不要となり、データベースの探索処理により経路が求まる分、経路案内リクエストへの応答性が高まる。
【０００７】
しかし、事前に可能な出発地目的地間の経路を全探索しておく方法では、時々刻々と変化する交通状況に応じた最適経路を提供することはできない。また、事前に想定しうる全ての交通状況の組み合わせを反映させた上で、前述の全探索を実行しておけば交通状況を反映させることが可能であるが、交通状況の状態数が無数に存在するため、全ての交通状況に対して事前に全探索を実行しておくことは現実的な手段とは言えない。
【課題を解決するための手段】
【０００８】
上記課題を解決するため、本発明による経路案内システムは、時刻毎の交通情報に基づく複数の交通状況を複数の交通状況パターンに分類する交通状況分類手段と、複数の交通状況パターンの各々に対応して、複数の地点間のすべての組み合わせについての経路探索演算を行い、経路探索演算により得られる全ての経路を経路データベースに格納する経路データベース生成手段と、複数の交通状況パターンの中から、現況交通情報に類似した交通状況パターンを出力する交通状況照合手段と、交通状況照合手段により出力された交通状況パターンに基づき、経路データベースを参照して、出発地から目的地までの経路を検索し出力する経路情報検索手段とを備えることを特徴とする。
【発明の効果】
【０００９】
本発明による経路案内システムは、現況交通情報に基づく経路の近似経路を事前探索により応答性を良く提供することを可能とする。
【図面の簡単な説明】
【００１０】
【図１】第１の実施例における経路案内システムの構成図である。
【図２】経路データベースのデータ構成を示す図である。
【図３】経路案内インターフェースの表示画面である。
【図４】交通情報を特徴空間に射影しクラスタリングした重心により交通状況照合を行う模式図である。
【図５】経路案内システムにおける経路データベースの作成処理フローである。
【図６】経路案内システムにおける経路探索の処理フローである。
【図７】第２の実施例における経路案内システムの構成図である。
【図８】現況交通情報と統計交通情報の時間経過による誤差変化傾向のグラフである。
【図９】経路案内システムの処理フローである。
【発明を実施するための形態】
【００１１】
以下、本発明を用いた経路探索システムの実施例について図面を用いて説明する。
【００１２】
（第１の実施例）
図１は、本実施例の経路案内システム１００の構成図である。経路案内システム１００は、交通情報データベース１０１と、交通状況分類装置１０２と、交通状況パターン１０３と、経路データベース生成装置１０４と、経路データベース１０５と、現況交通情報１０６と、交通状況照合装置１０７と、経路情報検索装置１０８と、地図データベース１１０とを有する。ナビゲーション装置１５０は、経路案内システム１００の外部装置であり、経路案内インターフェース１０９を有する。経路案内システム１００とナビゲーション装置１５０との間の入出力は、通信を介して行われる。
【００１３】
経路案内システム１００では、更新周期毎に各時点での交通情報を現況交通情報１０６として外部から収集している。この現況交通情報１０６は、路側に設置された感知機から得られる交通情報の他、プローブカー（フローティングカー）により計測された走行データがアップロードされてきたプローブデータによる交通情報などがある。更新周期毎に収集された現況交通情報１０６は、過去の交通情報を蓄積する交通情報データベース１０１に記憶される。
【００１４】
交通情報データベース１０１には、リンク旅行時間またはリンク代表速度などの数値データで表された過去の交通情報が格納されている。
【００１５】
交通状況分類装置１０２では、交通情報データベース１０１に格納された交通情報を読み出し、クラスタリングによって代表的な複数の交通状況パターン１０３を生成する。クラスタリングの手法には様々な公知の手法がある。交通状況分類装置１０２は、例えばＫ−ｍｅａｎｓ法を用いて過去の交通状況のクラスタリングを行う。交通状況分類装置１０２が行う処理の詳細は後述する。
【００１６】
交通状況パターン１０３は交通状況分類装置１０２によって生成される。交通状況パターン１０３は、クラスタリングによって生成されているため、過去に計測された交通状況そのものを表しているわけではない。過去の交通状況を複数の交通状況パターン１０３に分類し、各交通状況パターンは、過去の交通状況の内の互いに類似するいくつかのケースを代表する近似値として表される。交通状況パターン１０３のそれぞれには固有のパターン番号が付されている。
【００１７】
経路データベース生成装置１０４では、交通状況パターン１０３に対応する交通情報に基づいた経路探索コストと、地図データベース１１０に格納された地図データとを用いて、ダイクストラ法などの経路探索アルゴリズムにより、交通状況パターン１０３のそれぞれに対応した全地点間の全ての組み合わせについての経路探索演算を行い、その経路探索演算により得られる全経路を、経路データベース１０５に格納する。ここで全地点間の全ての組み合わせについての経路探索演算とは、出発地と目的地となりうるノードの全ての組み合わせについて、経路探索を行うことである。即ち、地図データベース１１０から経路探索の対象エリア内の全てのノードを取得し、それを出発地または目的地とした全ての組み合わせ（但し、同一ノード同士は除く）について、それぞれの交通状況パターン１０３に対応する交通情報に基づいた経路探索コストにより予め経路探索を行っておく。
【００１８】
経路データベース１０５には、交通状況パターン１０３のそれぞれに対応して、図２に示す表のように、出発地ノードと目的地ノードを結ぶ経路を構成するリンク列が格納される。このリンク列は、出発地となるノードから目的地となるノードまでの経路を構成する道路リンクのリンク番号を、出発地から目的地まで並べたものである。
【００１９】
交通状況照合装置１０７では、現況交通情報１０６と交通状況パターン１０３を比較し、現況交通情報１０６に最も類似した交通状況パターン１０３のパターン番号を出力する。この処理の詳細は後述する。
【００２０】
経路情報検索装置１０８では、交通状況照合装置１０７が出力したパターン番号の交通状況パターンに対応する全ノード間の全ての組み合わせについての経路探索結果を格納する経路データベース１０５を参照し、ナビゲーション装置１５０の経路案内インターフェース１０９から入力される出発地から目的地までの経路を検索して、その経路を構成するリンク列をナビゲーション装置１５０の経路案内インターフェース１０９へ出力する。
【００２１】
ナビゲーション装置１５０の経路案内インターフェース１０９では、利用者から出発地と目的地の入力を受け付けて、経路案内システム１００の経路情報検索装置１０８に送り、経路情報検索装置１０８が出力したその出発地と目的地を結ぶ経路３００の経路情報を受け取る。そして経路案内インターフェース１０９では、経路情報検索装置１０８からリンク列を受け取ると、図３の画面のように、出発地と目的地を表示した地図の上に、リンク列に該当する経路を強調表示する。
【００２２】
次に、交通状況分類装置１０２の詳細を説明する。交通状況分類装置１０２は、複数リンクの交通情報を要素とする多次元ベクトルをクラスタリングの対象とする。１リンクの交通情報を１つの座標軸上の値として考えると、例えば１０００本のリンクを含むエリアの交通状況は、１０００次元の交通情報空間上の交通情報ベクトルとして表される。この交通情報ベクトルが有する１０００個の成分は、それぞれ１０００本のリンクのリンク旅行時間またはリンク代表速度など、それぞれのリンクの移動コストに関する数値を表す。このリンク旅行時間またはリンク代表速度などの数値データは、上述したように交通情報データベース１０１に格納されており、過去の交通情報に基づいている。このような交通情報ベクトルが交通情報の更新周期毎に１本ずつ存在する。即ち、１本の交通情報ベクトルは、ある時刻の交通情報に基づく１０００本のリンクの交通状況を表している。交通状況分類装置１０２は、複数回の交通情報更新で生成されたそれらの交通情報ベクトルをクラスタリングし、複数個の代表的なクラスタを得る。各クラスタには、複数の異なる時刻の交通情報に基づく複数の交通状況を表す複数の交通情報ベクトルが分類される。それらの複数の交通情報ベクトルの重心に対応する交通情報ベクトル、即ち各クラスタの重心ベクトルで、交通状況パターン１０３が表される。
【００２３】
しかしリンク数が多い場合には、クラスタリングの演算量は膨大なものとなる。そのような場合には、特許文献２に開示されているように、交通情報ベクトルに対する主成分分析により得られる基底の線形合成により、交通情報を近似表現するのが好ましい。即ち、まず交通情報ベクトルを主成分分析で得られる低次元の特徴空間に特徴空間ベクトルとして射影し、次に特徴空間における特徴空間ベクトルを対象とするクラスタリングを行うと、演算量を大幅に減らすことができる。これを説明したものが図４である。図４は主成分分析で得られた複数の特徴空間ベクトルの射影点の座標４０１を、説明の便宜上、特徴空間から２つの基底Ｗ１およびＷ２を切り出した２次元の部分空間について示している。実際の特徴空間の次数は、例えば主成分分析における累積寄与率を指標として用いて、元の交通情報ベクトルの持つ９０％の情報を近似して保持するように設定することができる。この特徴空間ベクトル（射影点）を対象とするクラスタリングを行うと、複数のクラスタ５０１が求まる。複数のクラスタ５０１のそれぞれの重心５０２を、特徴空間から元の交通情報空間に逆射影して得られる複数の重心ベクトルの各々は、交通情報空間でクラスタリングを行って得られる各クラスタの重心ベクトルの近似ベクトルである。この近似ベクトルを交通状況パターン１０３として用いることができる。
【００２４】
次に、交通状況照合装置１０７の詳細を説明する。交通状況照合装置１０７は現況交通情報１０６に基づく交通状況を表す交通情報ベクトルと複数の交通状況パターン１０３を表す複数の交通情報ベクトルをそれぞれ比較して、その差分に基づいて得られる複数の差分ベクトルを相互比較し、ノルムが最も小さい差分ベクトルに対応する交通情報ベクトルで表される交通状況パターン１０３のパターン番号を出力する。
【００２５】
前述のように交通状況分類装置１０２が複数の交通情報ベクトルを特徴空間に射影してクラスタリングを行う場合には、交通状況照合装置１０７も現況交通情報１０６に基づく交通状況を表す交通情報ベクトルを特徴空間に射影することにより、交通状況照合装置１０７は特徴空間において現況交通情報１０６と交通状況パターン１０３との照合を行うことになる。複数の重心５０２、５０３等は複数の交通状況パターン１０３のそれぞれに対応する特徴空間上の座標に位置する。現況交通情報１０６に基づく交通状況を表す交通情報ベクトルを特徴空間に射影した座標が座標６０１である。この例で交通状況照合装置１０７は、特徴空間上における座標６０１に最も近い重心を探し、その重心に対応する交通状況パターン１０３のパターン番号を出力する。図４の例では、座標６０１に最も近い重心５０３に対応する交通状況パターン１０３のパターン番号が出力されることになる。
【００２６】
経路案内システム１００の動作をフローチャートで表すと図５、図６のようになる。図５は、複数の交通状況パターン１０３の生成と、複数の交通状況パターン１０３のそれぞれに対応した全地点間の全ての組み合わせについての経路探索演算とを含む、経路案内システム１００によって予め経路データベース８０４が準備される処理手順を示す。図６は、指定された出発地と目的地について出発地から目的地まで経路検索を行う際に経路案内システム１００によって行われる処理手順を示す。なお、ここではクラスタリングを前述のように特徴空間で行う場合について説明する。
【００２７】
図５のステップＳ７０１では、交通状況分類装置１０２による交通情報データベース１０１からのデータ読み出しが行われる。交通状況分類装置１０２は経路探索の対象とするエリアにおける過去の交通情報を取得する。ステップＳ７０２では、交通状況分類装置１０２による交通情報ベクトルの主成分分析の演算が行われる。交通状況分類装置１０２は、ステップＳ７０１で取得した交通情報に基づく交通状況を表す交通情報ベクトルに対する主成分分析により得られる基底に対応する特徴空間を生成する。なお、この時得られた基底は、後述するステップ７０５やステップ７１２でも使用されるため、別途記憶装置（図示せず）に格納されているものとする。ステップＳ７０３では、交通状況分類装置１０２は、当該特徴空間に該交通情報ベクトルを射影する演算を行う。ステップＳ７０１で取得した交通情報に対応する特徴空間への射影により、特徴空間ベクトル（射影点）が得られる。ステップＳ７０４では、交通状況分類装置１０２によるクラスタリングの演算が行われ、当該射影点が分類されたクラスタが形成される。クラスタリングには様々な手法があるが、例えばＫ−ｍｅａｎｓ法を用いれば、複数の球状クラスタが形成され、各クラスタに分類された射影点から該クラスタのクラスタ重心への距離が最短であることが保証される。ステップＳ７０５では、交通状況分類装置１０２による射影点およびクラスタ重心の交通情報空間への逆射影演算が行われる。クラスタ重心が逆射影されて得られる重心ベクトルから、交通状況パターン１０３が得られる。
【００２８】
Ｓ７０６は経路データベース生成装置１０４内のループ処理である。経路データベース生成装置１０４では、交通状況パターンのそれぞれに対応する交通情報に基づく経路探索コストを用いて、ステップＳ７０７からの全ノードに関するループ処理において経路探索演算７０８を行い、探索結果を経路データベース１０５に格納する。具体的には、交通状況パターンに対応する交通情報は各リンクにおける旅行時間情報であるため、これを経路探索に用いられるリンクコストとして用いる、あるいはリンクコストに反映させるなどして経路探索を行う。以上により、交通状況パターン１０３のそれぞれに対応する全ノード間の経路に関する経路情報が得られる。
【００２９】
図６のステップＳ７０９において、経路情報検索装置１０８は、ナビゲーション装置１５０の経路案内インターフェース１０９を介してユーザにより入力された出発地および目的地を含む経路案内リクエストを受信する。ステップＳ７１０では、交通状況照合装置１０７への現況交通情報１０６の入力処理が行われる。ステップＳ７１１では、交通状況照合装置１０７により、現況交通情報１０６に基づく交通状況を表す交通情報ベクトルの特徴空間への射影の演算を行う。交通状況照合装置１０７では当該交通情報ベクトルをステップＳ７０２で得られた特徴空間に射影する。この時用いる基底は、前述の通り、予めステップＳ７０２で求められていた基底を用いる。
【００３０】
ステップＳ７１２は交通状況照合装置１０７におけるループ処理である。ステップＳ７１３において、交通状況照合装置１０７は、ステップＳ７１１で得られた現況交通情報１０６に基づく交通状況を表す交通情報ベクトルの特徴空間における射影点と、交通状況パターン１０３のそれぞれに対応するクラスタ重心との距離を算出する。
【００３１】
ステップＳ７１４において、交通状況照合装置１０７は、ステップＳ７１３で算出した射影点からの距離の内で最も短い距離にあるクラスタ重心に対応する交通状況パターン１０３のパターン番号を、現況交通情報に最も類似した交通状況パターンのパターン番号として、経路情報検索装置１０８に出力する。ステップＳ７１５では、経路情報検索装置１０８は、経路データベース１０５に検索リクエストを発行し、図５の処理で予め作成しておいた経路データベース８０４の経路を参照することで経路検索を行う。即ち、ナビゲーション装置１５０の経路案内インターフェース１０９を介して利用者により指定された出発地および目的地と、ステップＳ７１４で交通状況照合装置１０７から入力された交通状況パターン１０３のパターン番号とに基づき、該パターン番号に対応した該出発地から該目的地までの経路に関する経路情報を読み出す。読み出された経路情報に対応する経路は、現況交通情報１０６に最も類似した交通状況パターン１０３において検索された経路なので、現況交通情報１０６に基づいて実際に経路探索することで得られる経路に近似した近似経路である。
【００３２】
ステップＳ７１６において、経路情報検索装置１０８は、ステップＳ７１５で読み出した該経路情報を、ナビゲーション装置１５０の経路案内インターフェース１０９に配信する。ナビゲーション装置１５０の経路案内インターフェース１０９は、経路情報検索装置１０８により出力された近似経路を、図３に示すように経路３００として画面に表示する。
【００３３】
図５に示すステップＳ７０１〜Ｓ７０８で行われる処理と、図６に示すステップＳ７０９〜Ｓ７１６で行われる処理とは互いに独立した処理である。ステップＳ７０１〜Ｓ７０８は予めオフラインで実行される。例えばこの処理は、１ヶ月に１回などのように定期的に実施するようにしても良い。これに対しステップＳ７０９〜Ｓ７１６は、ナビゲーション装置１５０からの経路案内リクエストに応じて、交通情報の更新周期、即ち現況交通情報の取得と同期してリアルタイムに実行される。こうすることで、経路案内システム１００は、ナビゲーション装置１５０の経路案内インターフェース１０９から入力された出発地から目的地までの上述した近似経路を速やかに提供することができる。この近似経路は、現況交通情報１０６に突発的な交通規制等の情報が含まれている場合であっても、その情報を含んだ現況交通情報１０６に最も類似した交通状況パターン１０３において検索された経路である。したがって、実際の道路条件に応じた経路に準じる近似経路が得られることになる。
【００３４】
ステップＳ７１２として表した交通状況照合装置１０７におけるループ処理の中で、ステップＳ７１３において、交通状況照合装置１０７は、ステップＳ７１１で得られた現況交通情報１０６に基づく交通状況を表す交通情報ベクトルの特徴空間における射影点と、交通状況パターン１０３のそれぞれに対応するクラスタ重心との距離を算出する。しかし、ステップＳ７０３において、交通状況分類装置１０２により、交通状況パターン１０３のそれぞれに対応する交通情報ベクトルを特徴空間に射影する演算が行われない場合は、ステップＳ７１１においても、交通状況照合装置１０７により、現況交通情報１０６に基づく交通状況を表す交通情報ベクトルの特徴空間への射影の演算を行わないこととしてもよい。この場合、ステップＳ７１３において、交通状況照合装置１０７は、ステップＳ７１１で得られた現況交通情報１０６に基づく交通状況を表す交通情報ベクトルから、交通状況パターン１０３のそれぞれに対応するクラスタの重心に対応する交通情報ベクトル（重心ベクトル）までの距離を算出することとしてもよい。
【００３５】
（第２の実施例）
経路案内の精度を上げる手段としては、特開２００７−１９２７２７号公報（特許文献１）のように、出発地近傍では経路探索のコストに現況交通情報を用い、出発地遠方において、現況交通情報の誤差が統計交通情報の誤差を上回る範囲では経路探索コストに統計交通情報を用いる手法が知られている。本実施例においては、その手法を応用して実施例１の経路案内システムの精度を向上する方法を示す。
【００３６】
図７は本実施例の経路案内システム８００の構成図である。経路案内システム８００の基本的な構成は図１の経路案内システム１００と同様であるため、ここでは経路案内システム１００と異なる構成要素について述べる。
【００３７】
８０１は統計交通情報生成装置であり、交通情報データベース１０１に格納された過去の交通情報を用いて、統計交通情報を生成する。ここで言う統計交通情報とは、曜日・祝祭日・時間帯等で過去の交通情報の統計的代表値をとったものであり、例えば、日曜日１０：００のリンク旅行時間やリンク代表速度といった情報が、統計交通情報データベース８０２に格納される。
【００３８】
続いて経路データベース生成装置８０３の処理について述べる。経路案内システム１００における経路データベース生成装置１０４は交通状況パターン１０３の交通情報のみを探索コストとして経路探索を行うが、経路データベース生成装置８０３は、交通状況パターン１０３と統計交通情報データベース８０２双方の交通情報を探索コストとして経路探索を行う。特許文献１にも言われているように、ある時点を起点としたとき、その時点での現況交通情報と統計交通情報の誤差は時間の経過とともに図８のように反転する。両者の誤差が反転し、現況交通情報の誤差が統計交通情報の誤差を上回る経過時間を閾値９０１とする。交通状況パターン１０３は交通状況照合装置１０７において現況交通情報１０６と比較照合の対象となる情報であるため、経路データベース生成装置８０３においては、閾値９０１を交通状況パターン１０３と統計交通情報データベース８０２を使い分ける閾値として用いる。すなわち、経路データベース生成装置８０３においてダイクストラ法を用いて探索を行う場合、探索開始時点では交通状況パターン１０３を探索コストとして計算を行い、新たなノードへの最短時間経路が確定するたびに、当該ノードへの到達時間と閾値９０１との比較を行い、到達時間が閾値９０１を上回った時点で、探索コストを交通状況パターン１０３から統計交通情報データベース８０２に切り替える。
【００３９】
以上に述べた経路データベース生成装置８０３の処理をフローチャートで表すと図９のようになる。Ｓ１００１は全ノードに関するループであり、各ノードを出発ノードとしてＳ１００２〜Ｓ１００６の探索処理を行う。Ｓ１００２は探索の初期化であり、交通状況パターン１０３の交通情報を探索コストとして各リンクに設定する。Ｓ１００３は出発点近傍のノードから最短時間経路を順次確定する処理である。Ｓ１００４は終了判定であり、当該出発ノードに対して、全ノードへの最短時間経路が確定した場合は探索処理を終了し、確定していない場合は探索処理を継続する。Ｓ１００５はＳ１００３で最短時間経路が確定したノードへの到達時間と閾値９０１の比較であり、到達時間が閾値を上回ったときは、Ｓ１００６において統計交通情報データベース８０２の交通情報を、確定済みの最短経路に含まれていない各リンクの探索コストとして設定する。以上の処理により、経路データベース生成装置８０３は交通状況パターン１０３と統計交通情報データベース８０２を使い分けて全探索を行う。また、このようにして生成された経路データベース８０４を参照することで、経路情報検索装置１０８は、交通状況照合装置１０７による現況交通情報１０６と交通状況パターン１０３の照合結果に基づいて、交通状況パターン１０３と統計交通情報データベース８０２双方を加味した経路情報を配信することができる。
【符号の説明】
【００４０】
１００ 経路案内システム
１０１ 交通情報データベース
１０２ 交通状況分類装置
１０３ 交通状況パターン
１０４、８０３ 経路データベース生成装置
１０５、８０４ 経路データベース
１０６ 現況交通情報
１０７ 交通状況照合装置
１０８ 経路情報検索装置
１０９ 経路案内インターフェース
１１０ 地図データベース
１５０ ナビゲーション装置
４０１ 特徴空間ベクトルの座標
５０１ クラスタ
５０２ クラスタ重心の座標
５０３ 現況交通情報の特徴空間射影点の座標に最も近いクラスタ重心の座標
６０１ 現況交通情報の特徴空間射影点の座標
８０１ 統計交通情報生成装置
８０２ 統計交通情報データベース
【特許請求の範囲】
【請求項１】
時刻毎の交通情報に基づく複数の交通状況を複数の交通状況パターンに分類する交通状況分類手段と、
前記複数の交通状況パターンの各々に対応して、複数の地点間のすべての組み合わせについての経路探索演算を行い、前記経路探索演算により得られる全ての経路を経路データベースに格納する経路データベース生成手段と、
前記複数の交通状況パターンの中から、現況交通情報に類似した交通状況パターンを出力する交通状況照合手段と、
前記交通状況照合手段により出力された前記交通状況パターンに基づき、前記経路データベースを参照して、出発地から目的地までの経路を検索して出力する経路情報検索手段とを備えることを特徴とする経路案内システム。
【請求項２】
請求項１に記載の経路案内システムにおいて、
前記交通状況分類手段は、前記複数の交通状況をクラスタリングにより複数のクラスタに分類し、
前記複数の交通状況パターンの各々は、前記複数のクラスタの各クラスタに対応することを特徴とする経路案内システム。
【請求項３】
請求項２に記載の経路案内システムにおいて、
前記複数の交通状況の各々は、複数の区間道路のそれぞれに対応する複数の移動コストに関する複数の成分を含む交通情報ベクトルで表され、
前記複数の交通状況パターンの各々は前記各クラスタの重心に対応する前記交通情報ベクトルで表され、
前記交通状況照合手段は、前記複数のクラスタのそれぞれの重心に対応する複数の交通情報ベクトルの内、前記現況交通情報に基づく交通状況を表す前記交通情報ベクトルから最も短い距離にある前記交通情報ベクトルで表される交通状況パターンを、前記現況交通情報に類似した交通状況パターンとして出力することを特徴とする経路案内システム。
【請求項４】
請求項３に記載の経路案内システムにおいて、
前記交通状況照合手段は、前記最も短い距離が所定閾値以下のとき、前記現況交通情報に類似した前記交通状況パターンを出力し、
前記複数のクラスタの内の、前記現況交通情報に基づく交通状況を表す前記交通情報ベクトルから前記最も短い距離にある前記交通情報ベクトルで表される前記交通状況パターンに対応するクラスタに応じて、前記所定閾値が定められることを特徴とする経路案内システム。
【請求項１】
時刻毎の交通情報に基づく複数の交通状況を複数の交通状況パターンに分類する交通状況分類手段と、
前記複数の交通状況パターンの各々に対応して、複数の地点間のすべての組み合わせについての経路探索演算を行い、前記経路探索演算により得られる全ての経路を経路データベースに格納する経路データベース生成手段と、
前記複数の交通状況パターンの中から、現況交通情報に類似した交通状況パターンを出力する交通状況照合手段と、
前記交通状況照合手段により出力された前記交通状況パターンに基づき、前記経路データベースを参照して、出発地から目的地までの経路を検索して出力する経路情報検索手段とを備えることを特徴とする経路案内システム。
【請求項２】
請求項１に記載の経路案内システムにおいて、
前記交通状況分類手段は、前記複数の交通状況をクラスタリングにより複数のクラスタに分類し、
前記複数の交通状況パターンの各々は、前記複数のクラスタの各クラスタに対応することを特徴とする経路案内システム。
【請求項３】
請求項２に記載の経路案内システムにおいて、
前記複数の交通状況の各々は、複数の区間道路のそれぞれに対応する複数の移動コストに関する複数の成分を含む交通情報ベクトルで表され、
前記複数の交通状況パターンの各々は前記各クラスタの重心に対応する前記交通情報ベクトルで表され、
前記交通状況照合手段は、前記複数のクラスタのそれぞれの重心に対応する複数の交通情報ベクトルの内、前記現況交通情報に基づく交通状況を表す前記交通情報ベクトルから最も短い距離にある前記交通情報ベクトルで表される交通状況パターンを、前記現況交通情報に類似した交通状況パターンとして出力することを特徴とする経路案内システム。
【請求項４】
請求項３に記載の経路案内システムにおいて、
前記交通状況照合手段は、前記最も短い距離が所定閾値以下のとき、前記現況交通情報に類似した前記交通状況パターンを出力し、
前記複数のクラスタの内の、前記現況交通情報に基づく交通状況を表す前記交通情報ベクトルから前記最も短い距離にある前記交通情報ベクトルで表される前記交通状況パターンに対応するクラスタに応じて、前記所定閾値が定められることを特徴とする経路案内システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１３−７２７４３（Ｐ２０１３−７２７４３Ａ）
【公開日】平成２５年４月２２日（２０１３．４．２２）
【国際特許分類】
【出願番号】特願２０１１−２１１７９２（Ｐ２０１１−２１１７９２）
【出願日】平成２３年９月２８日（２０１１．９．２８）
【出願人】（５０９１８６５７９）日立オートモティブシステムズ株式会社 (2,205)
【Ｆターム（参考）】
【公開日】平成２５年４月２２日（２０１３．４．２２）
【国際特許分類】
【出願日】平成２３年９月２８日（２０１１．９．２８）
【出願人】（５０９１８６５７９）日立オートモティブシステムズ株式会社 (2,205)
【Ｆターム（参考）】
[ Back to top ]