(57)【要約】  【課題】  推定又は予測を伴った複数の経路を探索することが可能な経路探索装置及び経路探索方法を提供すること。  【解決手段】  類似時点抽出手段９は、起終点を含む領域内の道路区間の交通流データ分布パターンと類似するパターンを所有する過去の複数時点をパターンマッチングにより探索し抽出する。複数経路探索提示手段１０は、抽出した各時点を出発時点として、各道路区間の走行コストを算出しながら、起終点間の各過去時点における最小コストの経路を探索し、当起終点間の複数の経路を提示する。【選択図】  図１
2005337984.tif 000002
【特許請求の範囲】
【請求項１】
任意時点における起終点間の経路を探索する経路探索装置であって、
交差点および道路区間の位置、区間距離、接続関係を含む道路網データと、各道路区間における交通流データとを蓄積するデータベースからデータを取得し、起終点を含む領域内に存在する道路区間の、任意時点から所定時間分過去の時点における交通流データの分布パターンと類似する分布パターンを所有する過去の複数時点をパターンマッチングにより探索して、その類似度と共に抽出する類似時点抽出手段と、
前記抽出された複数時点において、前記起終点間の前記道路網データ及び前記交通流データに基づいて最適経路を探索する経路探索手段と、
を備える経路探索装置。
【請求項２】
前記経路探索手段は、前記抽出した各時点を出発時点として、道路区間の距離と通過する時刻の速度又は通過に要する時間に基づいて各道路区間の走行コストを算出しながら、起終点間の各過去時点における最小コストの経路を探索する請求項１記載の経路探索装置。
【請求項３】
任意時点における起終点間の経路を探索する経路探索方法であって、
交差点および道路区間の位置、区間距離、接続関係を含む道路網データと、各道路区間における交通流データとを蓄積するデータベースからデータを取得するステップと、
起終点を含む領域内に存在する道路区間の、任意時点から所定時間分過去の時点における交通流データの分布パターンと類似する分布パターンを所有する過去の複数時点をパターンマッチングにより探索して、その類似度と共に抽出するステップと、
前記抽出された複数時点において、前記起終点間の前記道路網データ及び前記交通流データに基づいて最適経路を探索するステップと、
を有する経路探索方法。
【請求項４】
前記最適経路を探索するステップは、前記抽出した各時点を出発時点として、道路区間の距離と通過する時刻の速度又は通過に要する時間に基づいて各道路区間の走行コストを算出しながら、起終点間の各過去時点における最小コストの経路を探索する請求項３記載の経路探索方法。
【請求項５】
コンピュータに、請求項３または４記載の経路探索方法の各ステップを実行させる経路探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道路交通分野に係り、道路交通情報提供や交通管制における管理または運用等に利用するための経路探索装置および経路探索方法に関する。
【背景技術】
【０００２】
任意データ内の最適経路を探索する代表的な方法としては、ダイクストラ（またはダイキストラ）法が用いられている。このうち、複数の経路を探索する方法としては、特許文献１および非特許文献１に示すとおり、複数経路探索のためのデュアルダイキストラ法が存在する。この方法では、起点と終点の両方からダイクストラ法を適用し、起終点間の複数の経路を探索している。
【特許文献１】特願２００２−３４０４９号公報
【非特許文献１】藤田悠介、中村仁彦、Zvi Shiller 著  「トポロジの異なる経路を計算するデュアルダイキストラ法」、第２０回日本ロボット学会学術講演会、ｐ．１Ｄ２２
【発明の開示】
【発明が解決しようとする課題】
【０００３】
デュアルダイクキストラ法の適用では、ある時点データに基づく起終点両方からの探索による。このとき、経路上の車両の進行とともに時刻は経過するが、道路区間の交通状況は時々刻々と変化するため、同一時刻のデータや固定的な値を用いては、走行経路や時刻に応じた状況との相違を生じ、実際に見合ったコストの経路は得られない。同じ道路区間といえども、そこに到達するまでの経路が違えば、コストも相違する。よって、その地点や区間を通過又は探索する時刻でのコストから経路を求めなければならない。
【０００４】
現時点や過去における実際の最小コストの経路は、当データに基づく確定的な経路探索によって得られるものの、将来における経路に対しては推定予測する必要が発生する。特に将来の経路に関しては、推定又は予測を伴うため、可能性のある複数の経路を探索しておく必要が発生する。
【０００５】
本発明は、上記従来の事情に鑑みてなされたものであって、推定又は予測を伴った複数の経路を探索することが可能な経路探索装置及び経路探索方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の経路探索装置は、任意時点における起終点間の経路を探索する経路探索装置であって、
交差点および道路区間の位置、区間距離、接続関係を含む道路網データと、各道路区間における交通流データとを蓄積するデータベースからデータを取得し、起終点を含む領域内に存在する道路区間の、任意時点から所定時間分過去の時点における交通流データの分布パターンと類似する分布パターンを所有する過去の複数時点をパターンマッチングにより探索して、その類似度と共に抽出する類似時点抽出手段と、
前記抽出された複数時点において、前記起終点間の前記道路網データ及び前記交通流データに基づいて最適経路を探索する経路探索手段と、
を備える。
【０００７】
この構成により、起終点間とその周辺の領域において経路探索する時点に類似の複数の状況を得て、これらの複数の時点の各々について最適経路を探索することで、より実態に近い複数の経路の探索を行うことができる。
【０００８】
また、本発明の経路探索装置において、前記経路探索手段は、前記抽出した各時点を出発時点として、道路区間の距離と通過する時刻の速度又は通過に要する時間に基づいて各道路区間の走行コストを算出しながら、起終点間の各過去時点における最小コストの経路を探索する。
【０００９】
この構成により、交通状況の変化に応じた経路の探索を行うことができる。
【００１０】
本発明の経路探索方法は、任意時点における起終点間の経路を探索する経路探索方法であって、
交差点および道路区間の位置、区間距離、接続関係を含む道路網データと、各道路区間における交通流データとを蓄積するデータベースからデータを取得するステップと、
起終点を含む領域内に存在する道路区間の、任意時点から所定時間分過去の時点における交通流データの分布パターンと類似する分布パターンを所有する過去の複数時点をパターンマッチングにより探索して、その類似度と共に抽出するステップと、
前記抽出された複数時点において、前記起終点間の前記道路網データ及び前記交通流データに基づいて最適経路を探索するステップと、
を有する。
【００１１】
この方法により、起終点間とその周辺の領域において経路探索する時点に類似の複数の状況を得て、これらの複数の時点の各々について最適経路を探索することで、複数の経路の探索を行うことができる。
【００１２】
また、本発明の経路探索方法において、前記最適経路を探索するステップは、前記抽出した各時点を出発時点として、道路区間の距離と通過する時刻の速度又は通過に要する時間に基づいて各道路区間の走行コストを算出しながら、起終点間の各過去時点における最小コストの経路を探索する。
【００１３】
この方法により、交通状況の変化に応じた経路の探索を行うことができる。
【００１４】
また、本発明は、コンピュータに、上記の経路探索方法の各ステップを実行させるためのプログラムを提供するものである。
【発明の効果】
【００１５】
本発明によれば、推定又は予測を伴った複数の経路を探索することが可能な経路探索装置及び経路探索方法を提供することができる。
【発明を実施するための最良の形態】
【００１６】
以下、図１から図４を用いて本発明の実施形態について説明する。図１は、本発明の実施形態の経路探索装置全体の概略構成を示す図である。なお、本発明の実施形態において用いられる交通流データには、交通量、占有率又は占有時間、速度、旅行時間、渋滞度等が存在するが、本実施形態では、交通流データして、速度を用いた場合を説明する。
【００１７】
図１に実施形態の経路探索装置の全体構成を示し、大まかな動作を説明する。交差点１と道路区間２とを有する道路網３内を走行車両４が走行し、交通流データの計測手段である車両感知器５によって走行車両が感知される。処理部６では車両感知器５から送信された車両データに基づいて、感知された道路区間Ｌの速度を、５分間毎例えば２３：５５〜２４：００に集計し、０：００からの５分毎の時刻すなわち各時点、この場合は時点ｔ＝２４：００の５分間平均速度Ｖ（Ｌ，ｔ）として、処理部６が備える交通流データベース７に蓄積しているものとする。この交通流データベース７には、広域の道路区間の過去所定期間、例えば１年分のデータが蓄積されているものとする。
【００１８】
地図データベース８には、緯度・経度を含む道路網上の交差点位置や交差点間の接続道路によって構成される道路区間Ｌのデータが蓄積されているものとする。なお、車両感知器５は道路区間の各進行方向に設置されているものとする。
【００１９】
処理部６は、例えば、マイクロコンピュータ等によって構成され、所定のプログラムによって動作するプロセッサを主体に構成される。各時点において５分間交通流データここでは速度の集計後に引き続いて、類似時点抽出手段９、複数経路探索提示手段１０を順に実行し、入出力装置１１に表示する。
【００２０】
本実施形態では、現時点ｔにおいて、これから出発する場合すなわち現時点から先つまり未来の、任意の起点Ｏから終点Ｄに到着するまでの、起終点間の複数経路を探索して提示する場合について説明する。
【００２１】
図２は、類似時点抽出手段の処理フローを示す図である。類似時点抽出手段９は、交通流データベース７および地図データベース８からデータを取得し、起終点を含む領域内に存在する道路区間の、任意時点から所定時間分過去の時点における交通流データの分布パターンと類似する分布パターンを所有する過去の複数時点をパターンマッチングにより探索して、その類似度と共に抽出する。
【００２２】
本実施形態での類似時点抽出は、交通流データの分布パターンとして、ある時点の交通流データのベクトルを用い、類似度として、現時点でのベクトルと、過去の時点の交通流データのベクトルとの間の距離を用いる。
【００２３】
まず、入出力装置から起終点を入力し指定する（Ｓ２０１）。ここでは、起点Ｏと終点Ｄの交差点位置を緯度と経度による座標で指定する。次に、指定された位置の緯度Ｘ、経度Ｙから、起終点を含んで一定分拡張した領域を決定する（Ｓ２０２）。
【００２４】
本実施形態では、起終点の位置を点として含み緯度と経度方向に平行する直線で囲まれた矩形領域を、さらに東西および南北方向に一定の幅Δｄだけ拡大して構成する矩形領域Ｒとする。この矩形領域Ｒは、例えば、起点の座標がＯ＝（Ｘ（Ｏ），Ｙ（Ｏ））、終点の座標がＤ＝（Ｘ（Ｄ），Ｙ（Ｄ））、Ｘ（Ｏ）＜Ｘ（Ｄ）、Ｙ（Ｏ）＜Ｙ（Ｄ）であるとき、
Ｏ’＝（Ｘ（Ｏ）−Δｄ，Ｙ（Ｏ）−Δｄ）
Ｄ’＝（Ｘ（Ｄ）＋Δｄ，Ｙ（Ｄ）＋Δｄ）
Ｏ’Ｄ’＝（Ｘ（Ｏ）−Δｄ，Ｙ（Ｄ）＋Δｄ）
Ｄ’Ｏ’＝（Ｘ（Ｄ）＋Δｄ，Ｙ（Ｏ）−Δｄ）
の４点で構成される領域Ｒである。
【００２５】
処理部６の地図データベース８からこの領域Ｒに存在する道路区間を読み込む（Ｓ２０３）。ここでは、矩形領域Ｒ内にその両端の位置座標が存在している道路区間を読み込むものとし、該当する道路区間をＬｉ（ｉ＝１、２、３、．．．、ｒ）とする。次に、交通流データベース７から該当する道路区間の全交通流データを読み込む（Ｓ２０４）。
【００２６】
以降、該当する道路区間の交通流データここでは速度データの分布をベクトルとして、過去のデータを対象に距離算出処理を行う。ベクトルは、現時点から過去一定時点数Δｔ遡った時点、つまりｔ〜ｔ−Δｔまでの交通流データ分布をその次元として構成するが、以下では単純化してその一定時点数Δｔを０とし、現時点のデータのみとする。
【００２７】
この場合、矩形領域Ｒ内に存在する道路区間数ｒによるｒ次元のベクトルを構成して距離を算出する。具体的には、現時点での当領域内の道路区間Ｌｉの速度データｖからなるベクトルＶ（ｔ）＝（ｖ（Ｌ１，ｔ）、ｖ（Ｌ２，ｔ）、．．．、ｖ（Ｌｒ，ｔ））を構成し、このベクトルを基準ベクトルとして、過去時点ｔ−ｊの同ベクトルとの間のユークリッド距離Ｄの算出をＤ（ｔ−ｊ）＝‖Ｖ（ｔ）−Ｖ（ｔ−ｊ）‖として行なう（Ｓ２０５）。以上の距離算出を、読み込んだ全ての過去データについて行なう（Ｓ２０６）。
【００２８】
次に、算出された距離に基づいて、現時点の交通流データ分布に類似する過去時点を抽出する。ここでは、新しく（現在に近く）、距離が小さい程、類似とみなして、そのようなデータを抽出する。このため、時刻上近くかつ距離が小さい順にソートする（Ｓ２０７）。ソート後、必要な経路数分だけ、上位の任意個数ｐ個、例えばｐ＝１０個の該当する過去時点を抽出し、それらの過去時点のデータと類似度として算出した距離を処理部に格納する（Ｓ２０８）。以上の形態では速度を用いたが、他の交通流データ、例えば交通量や占有率といったデータの場合にも同様に適用できる。
【００２９】
この後、経路の探索と提示を行う。図３は、経路探索提示手段の処理フローを示す図である。まず、地図データベース８から地図データを読み込む（Ｓ３０１）。次に、類似時点抽出手段９によって類似として抽出されたｐ個（ここでは１０個）の過去時点データと類似度である距離を経路探索提示手段１０に読み込む（Ｓ３０２）。続いて、交通流データベース７から過去の全交通流データつまり速度データを読み込む（Ｓ３０３）。
【００３０】
本実施形態では、現時点に類似として抽出されたｐ個の過去時点ｐ（ｋ）（ここでｋ＝１、２、３、．．．、１０）について、処理に要する時間を考慮し次の時点ｐ（ｋ）＋ｌに起点を出発するものとおいて、ダイクストラ法を適用し最小コストの経路を探索していく（Ｓ３０４、Ｓ３０５）。
【００３１】
このとき、各到達道路区間のコストは、類似として抽出した過去における出発時点からその到達道路区間の終端への到達までに要した旅行時間分経過した時点以降の速度を用い、当道路区間の走行を模擬し算出される。その概念を図４に示す。図４は、道路区間におけるコスト算出の模式図である。起点から当区間までの探索の結果による到達時刻がｐ（ｋ）＋ｌ（ｌはここまでの旅行時間に等しい）までとして、当時刻以降に走行する場合の速度データに基づいてコストを算出している。このときのコストは当区間の走行に要した旅行時間である。蓄積データに応じて、右左折の待ち時間といった通過時間に関するコストを加えてもよい。抽出した各時点に対してこのような探索を実施し、経路を決定する。
【００３２】
探索されたｐ個の最小コストの経路は処理部に格納・保存され（Ｓ３０６）、地図上に各経路とその類似度とコストを重ね、入出力装置１１に表示される（Ｓ３０７）。
【００３３】
以上によって、指定された起終点間において、現時点ｔの次の時点ｔ＋１に起点を出発し終点に到達するとして探索された複数の経路と類似度、コストが得られる。
【００３４】
このような本発明の実施形態の経路探索装置及び経路探索方法によれば、類似した過去の複数の時点を抽出してこれらの時点における経路探索を行うことにより、より実態に近い経路探索を行うことができる。また、通過時の交通流データに基づいて走行コストを産出しながら最小コストの経路を探索するので、交通状況の変化に応じた経路探索を行うことができる。
【００３５】
従って、複数地図データと交通流データを蓄積しておくだけで、データを有効に活用し、容易に実態に近い経路を探索することができる。また、順次蓄積する交通流データによるため、交通環境の経年変化にも追従することができ、当データやシステム等の更新は低減され、維持や管理等の低コスト化に貢献できる。
【産業上の利用可能性】
【００３６】
本発明の経路探索装置及び経路探索方法は、推定又は予測を伴った複数の経路を探索することが可能な効果を有し、ルートガイダンス装置等に有用である。
【図面の簡単な説明】
【００３７】
【図１】本発明の実施形態の経路探索装置全体の概略構成を示す図
【図２】類似時点抽出手段の処理フローを示す図
【図３】経路探索提示手段の処理フローを示す図
【図４】道路区間におけるコスト算出の模式図
【符号の説明】
【００３８】
１  交差点
２  道路区間
３  道路網
４  走行車両
５  車両感知器
６  処理部
７  交通流データベース
８  地図データベース
９  類似時点抽出手段
１０  複数経路探索提示手段
１１  入出力装置
【図１】
2005337984.tif 000003
【図２】
2005337984.tif 000004
【図３】
2005337984.tif 000005
【図４】
2005337984.tif 000006