(57)【要約】【課題】適度な到達時間を確保しつつ、プローブカーとしての観測頻度や観測範囲を広げる経路指示を各車両に行うことができる経路探索装置などを提供する。【解決手段】目的地までの予定経路情報を受信する受信手段と、予定経路を複数の区間に区分けしたリンクそれぞれのリンク旅行時間を第１のコストとして、リンクにおける各車両のリンク通過時間ごとに算出する第１の算出手段と、前記リンクにおける前記各車両のリンク通過時刻において最大値を有し、時間の経過に伴って減少する値を与える関数によって算出される第２のコストを算出する第２の算出手段と、第１のコストと、第２のコストとに、それぞれ所定の比率を掛けて加算した統合コストを所定の時刻ごとに算出する加算手段と、合コストに基づいて、各車両の最短経路を求める最短経路取得手段とを備える。【選択図】図２
2014190920.tif 000002
【特許請求の範囲】
【請求項１】
経路探索の対象領域内に存在する複数の車両からの情報に基づいて前記複数の車両の各車両の経路探索を行う経路探索装置であって、
前記各車両が目的地へ向けて出発した出発時刻を含む前記目的地までの予定経路情報を前記各車両から受信する受信手段と、
受信した前記予定経路情報に基づいて、前記目的地までの予定経路を複数の区間に区分けしたリンクそれぞれのリンク旅行時間を第１のコストとして、前記リンクにおける前記各車両の通過時刻であるリンク通過時間ごとに算出する第１の算出手段と、
前記リンクにおける前記各車両のリンク通過時刻において最大値を有し、時間の経過に伴って減少する値を与える関数によって算出される第２のコストを所定の時刻ごとに算出する第２の算出手段と、
前記第１の算出手段によって算出された前記第１のコストと、前記第２の算出手段によって算出された前記第２のコストとに、それぞれ所定の比率を掛けて加算した統合コストを前記所定の時刻ごとに算出する加算手段と、
算出された前記統合コストに基づいて、前記各車両の最短経路を求める最短経路取得手段とを、
備える経路探索装置。
【請求項２】
前記第１の算出手段は、前記リンクのうち所定のリンクにおける前記各車両の通過時刻である前記リンク通過時刻を算出し、算出された前記リンク通過時刻における前記所定のリンクを通過する予定の車両数である通過予定数を算出し、算出された前記通過予定数と所定のデータとに基づいて前記所定のリンクにおける推定速度を算出し、算出された前記推定速度に基づいて前記所定のリンクのリンク旅行時間を前記第１のコストとして前記リンク通過時刻ごとに算出する一連の処理を行うとともに、前記所定のリンク以降のリンクに対しても前記一連の処理を行い、すべてのリンクについて前記第１のコストを前記リンク通過時刻ごとに算出する請求項１に記載の経路探索装置。
【請求項３】
前記最短経路取得手段は、求められた前記最短経路が所定の条件を満たしていないと判断した場合、前記第１の算出手段によって算出された前記第１のコストを更新させた更新後の第１のコストを利用して最短経路を求める請求項１又は２に記載の経路探索装置。
【請求項４】
前記加算手段は、現時点での各リンクにおけるリンク旅行時間を第３のコストとし、前記統合コストを算出する際に前記第３のコストを含めて算出する請求項１から３のいずれか１つに記載の経路探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の車両から送信される情報に基づいて経路探索などを行う経路探索装置に関する。
【背景技術】
【０００２】
従来からネットワーク（特に、道路ネットワーク）上において最短距離（又は時間、コストなど）で目的地までの経路を求める経路探索技術がある。その代表的なものとしてDijkstra法などが挙げられる。上記技術は下記の特許文献１や非特許文献１などに開示されている。また、道路の状況（渋滞、路面状況など）を把握するために、対象車両（プローブカー）にＧＰＳ（Global Positioning System）情報やセンサー情報をセンターに送信させるプローブカーシステム（フローティングカーシステムとも言う）が存在する（下記の非特許文献２を参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特表平１１−５０８７５４号公報（要約）
【非特許文献】
【０００４】
【非特許文献１】http://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
【非特許文献２】http://ja.wikipedia.org/wiki/%E3%83%95%E3%83%AD%E3%83%BC%E3%83%86%E3%82%A3%E3%83%B3%E3%82%B0%E3%82%AB%E3%83%BC%E3%83%87%E3%83%BC%E3%82%BF
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来の経路探索技術やプローブカーシステムを用いて経路探索を行うと、各車両が最短の経路を通ることにより徐々にその経路が混んできてしまうという問題がある。また、各車両が最短の経路を通ることにより車両が通らない道路が多くなってしまい、それらの道路に関する情報（例えば、混雑具合や路面状況などの情報）が得られなくなってしまうという問題がある。また、プローブカーによる道路の観測を行う場合に、観測範囲や観測時間帯を増やそうとすると最短経路でない経路を通ることになり、かえって各車両の経路長が長くなるという問題もある。
【０００６】
本発明は、上記の問題点に鑑み、適度（リーズナブル）な到達時間を確保しつつ、プローブカーとしての観測頻度や観測範囲を広げる経路指示を各車両に行うことができ、またプローブカーとしての必要なデータ品質を確保しつつ、各車両の便益（最短経路に近い経路での走行など）の低下を最小限にすることができる経路探索装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明によれば、経路探索の対象領域内に存在する複数の車両からの情報に基づいて前記複数の車両の各車両の経路探索を行う経路探索装置であって、前記各車両が目的地へ向けて出発した出発時刻を含む前記目的地までの予定経路情報を前記各車両から受信する受信手段と、受信した前記予定経路情報に基づいて、前記目的地までの予定経路を複数の区間に区分けしたリンクそれぞれのリンク旅行時間を第１のコストとして、前記リンクにおける前記各車両の通過時刻であるリンク通過時間ごとに算出する第１の算出手段と、前記リンクにおける前記各車両のリンク通過時刻において最大値を有し、時間の経過に伴って減少する値を与える関数によって算出される第２のコストを所定の時刻ごとに算出する第２の算出手段と、前記第１の算出手段によって算出された前記第１のコストと、前記第２の算出手段によって算出された前記第２のコストとに、それぞれ所定の比率を掛けて加算した統合コストを前記所定の時刻ごとに算出する加算手段と、算出された前記統合コストに基づいて、前記各車両の最短経路を求める最短経路取得手段とを備える経路探索装置が提供される。この構成により、適度（リーズナブル）な到達時間を確保しつつ、プローブカーとしての観測頻度や観測範囲を広げる経路指示を各車両に行うことができ、またプローブカーとしての必要なデータ品質を確保しつつ、各車両の便益（最短経路に近い経路での走行など）の低下を最小限にすることができる。なお、ここでのリンクとは、例えば後述するリンク１〜３を言う。また、ここでのリンク通過とは、リンクに車両が入った時点を通過としてもよく、リンクを車両が通り抜けた時点を通過としてもよく、リンク中の所定の地点を車両が通り抜けた時点を通過としてもよい。
【０００８】
また、本発明の経路探索装置において、前記第１の算出手段が、前記リンクのうち所定のリンクにおける前記各車両の通過時刻である前記リンク通過時刻を算出し、算出された前記リンク通過時刻における前記所定のリンクを通過する予定の車両数である通過予定数を算出し、算出された前記通過予定数と所定のデータとに基づいて前記所定のリンクにおける推定速度を算出し、算出された前記推定速度に基づいて前記所定のリンクのリンク旅行時間を前記第１のコストとして前記リンク通過時刻ごとに算出する一連の処理を行うとともに、前記所定のリンク以降のリンクに対しても前記一連の処理を行い、すべてのリンクについて前記第１のコストを前記リンク通過時刻ごとに算出することは、本発明の好ましい態様である。この構成により、より精度の高い経路探索を行うことができる。なお、所定のリンクにおける前記各車両の通過時刻であるリンク通過時刻を算出する際、各車両から別途受信した走行速度を利用してもよく、法定速度を利用してもよい。また、前記所定のリンク以降のリンクとは、例えば所定のリンクに続く目的地までのそれぞれのリンクを言う。
【０００９】
また、本発明の経路探索装置において、前記最短経路取得手段が、求められた前記最短経路が所定の条件を満たしていないと判断した場合、前記第１の算出手段によって算出された前記第１のコストを更新させた更新後の第１のコストを利用して最短経路を求めることは、本発明の好ましい態様である。この構成により、より精度の高い経路探索を行うことができる。ここでの所定の条件とは、例えば後述するステップＳ８０４における経路が変化したか否かという条件を言う。
【００１０】
また、本発明の経路探索装置において、前記加算手段が、現時点での各リンクにおけるリンク旅行時間を第３のコストとし、前記統合コストを算出する際に前記第３のコストを含めて算出することは、本発明の好ましい態様である。この構成により、より精度の高い経路探索を行うことができる。
【発明の効果】
【００１１】
本発明の経路探索装置は、上記構成を有し、適度（リーズナブル）な到達時間を確保しつつ、プローブカーとしての観測頻度や観測範囲を広げる経路指示を各車両に行うことができ、またプローブカーとしての必要なデータ品質を確保しつつ、各車両の便益（最短経路に近い経路での走行など）の低下を最小限にすることができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施の形態に係る経路探索装置を含むプローブカーシステムの一例を示す図である。
【図２】本発明の実施の形態に係る経路探索装置の一例を示す構成図である。
【図３】本発明の実施の形態におけるＱ−Ｖ曲線の一例を示す図である。
【図４】本発明の実施の形態における通過予定によるリンクコスト計算の結果の一例を示す図である。
【図５】本発明の実施の形態における観測頻度によるコスト計算の結果の一例を示す図である。
【図６】本発明の実施の形態における統合リンクコストを説明するための図である。
【図７】本発明の実施の形態における統合リンクコストの計算結果の一例を示す図である。
【図８】本発明の実施の形態に係る経路探索装置の処理フローの一例を示すフローチャートである。
【図９】本発明の実施の形態における総旅行時間と観測カバレッジとの関係の一例を示す図である。
【発明を実施するための形態】
【００１３】
まず、本発明の実施の形態に係る経路探索装置を含むプローブカーシステムについて図１を用いて説明する。図１に示すように、プローブカーシステム１１０は、経路探索装置１００と、複数のプローブカー１０１ａ〜１０１ｃとから構成されている。図１ではプローブカー（単に車両とも言う）の数が３台となっているが、３台に限られるものではなく、それ以上の数であってもよい。各車両は、それぞれが予定している目的地までの予定経路情報を経路探索装置１００に送信する。すなわち、経路探索装置１００に対して各車両から予定経路情報が送信される。なお、各車両は予定経路情報を経路探索装置１００へ送信するのではなく、自車両の出発地、目的地、出発時刻などの情報を経路探索装置１００へ送信するようにしてもよい。この場合、経路探索装置１００は、受信した出発地及び目的地の情報などを用いて各車両の予定経路を算出する。
【００１４】
ここで、本発明の実施の形態に係る経路探索装置の一例について図２を用いて説明する。図２に示すように、経路探索装置１００は、送受信部２００、算出部２０１（第１の算出手段、第２の算出手段に相当）、合成部２０２（加算手段に相当）、最短経路取得部２０３、格納部２０４から構成されている。送受信部２００は、各車両との間でやりとりされる情報などを送受信するものであり、例えば通信インターフェースなどによって実現可能である。また、格納部２０４は、送受信部２００によって送受信される情報を格納したり、算出部２０１によって算出された情報を格納したり、経路探索に必要な情報を格納したりするものであり、例えばＨＤＤ（Hard Disk Drive：ハードディスクドライブ）やＲＡＭ（Random Access Memory：ランダムアクセスメモリ）などによって実現可能である。
【００１５】
また、算出部２０１は、各車両から送信された予定経路情報に基づいて、あるリンク（例えば、後述する図４の場合にはリンク１）を通過する予定の車両の数（通過予定数）を所定の時刻ごとに算出するものである。なお、各車両から出発時刻、現在地、目的地などの情報を受信する場合には、算出部２０１は、所定のリンクを通過する予定の車両の数（通過予定数）を所定の時刻ごとに算出する前に各車両の予定経路を算出する。ここで、リンクとは、例えば目的地までの経路を複数の区間に区分けした各道路区間を言い、例えば交差点間の区間や信号間の区間などが考えられるが、これらに限られるものではない。
【００１６】
また、算出部２０１は、図３に示すＱ-Ｖ曲線（交通量と速度の関係）を用いて、算出された通過予定数から推定速度を算出し、算出された推定速度からリンクのリンク旅行時間であるコスト（通過予定によるリンクコストとも言い、第１のコストに相当）を求める。なお、この処理を特開２０１１−１９８１３２号公報などに示される手法で行ってもよく、通常の渋滞予測、シミュレーションを行って求めたコストであってもよい。そして、算出部２０１は、得られた推定速度を基に次のリンク（例えば、隣接するリンク）の各車両の通過時刻を算出する。そして、算出部２０１は、算出された通過時刻における通過予定数を算出し、算出された通過予定数から上述したようにＱ−Ｖ曲線を用いて推定速度を算出し、算出された推定速度から当該リンクのコストを求める。この処理を最後のリンク（後述する図４の場合にはリンク３）まで繰り返す。
【００１７】
ここで、算出部２０１による通過予定によるリンクコスト計算の結果を図４に示す。なお、図４に示される丸囲みの数字は上記コストを示している。リンク１においては、時刻０：００に車両Ａ、時刻０：１０に車両Ｂ、Ｃ、Ｄが通過する予定であり、リンク２においては、時刻０：００に車両Ａ、時刻０：１０に車両Ｄ、時刻０：１５に車両Ｂ、Ｃが通過する予定であり、リンク３においては、時刻０：０５に車両Ａ、時刻０：１５に車両Ｃ、Ｄ、時刻０：２０に車両Ｂが通過する予定である。
【００１８】
次に、算出部２０１は、図５に示すようなコスト（観測頻度によるコストとも言い、第２のコストに相当）計算を行う。具体的には、算出部２０１は、リンク（図５の場合、リンク１〜３）における各車両のリンク通過時刻において最大値を有し、時間の経過に伴って減少する値を与える関数（例えば、所定の時刻の経過に伴ってコストが１つずつ減るなど）によって算出されるコストを所定の時刻ごとに算出する。その結果が図５に示すものである。なお、このコスト計算は、車両数によらず、コストが重なっても加算はされない。
【００１９】
図５に示すように、リンク１では、時刻０：００に車両Ａ、時刻０：１０に車両Ｂ、Ｃ、Ｄが通過予定であり、それぞれの時刻においてコストの値を最大値（ここでは、５）とし、時間の経過に伴ってコストの値が減少する。リンク２では、時刻０：００に車両Ａ、時刻０：１０に車両Ｄ、時刻０：１５に車両Ｂ、Ｃが通過予定であり、それぞれの時刻においてコストの値を最大値（ここでは、５）とし、時間の経過に伴ってコストの値が減少する。リンク３では、時刻０：０５に車両Ａ、時刻０：１５に車両Ｃ、Ｄ、時刻０：２０に車両Ｂが通過予定であり、それぞれの時刻においてコストの値を最大値（ここでは、５）とし、時間の経過に伴ってコストの値が減少する。
【００２０】
合成部２０２は、例えば、算出部２０１によって算出された通過予定によるリンクコストと観測頻度によるコストとを合成してリンクコスト（統合リンクコスト又は統合コストとも言う）を求める。なお、統合リンクコストを求める際、後述するように統合リンクコストを定義し、現時点での各リンクにおけるリンク旅行時間であるコスト（第３のコストに相当）をも考慮して算出するようにしてもよい。図６は通過予定によるリンクコストと観測頻度によるコストとをまとめたものを示す図であり、図７は通過予定によるリンクコストに所定の比率ｒ＝０．５、観測頻度によるコストに所定の比率（１−ｒ）＝０．５をそれぞれ掛けて加算した場合の統合リンクコストの値を示す図である。
【００２１】
より具体的には、統合リンクコストは、例えば、現在（現時点）のリンク旅行時間、予定通過数（将来のリンク旅行時間）、観測頻度の項を有する関数により定義されてもよく、その場合、統合リンクコスト＝ｆ（現在のリンク旅行時間、予定通過数、観測頻度）として表される。合成の仕方としては、例えば後述するように線形和を用いる。すなわち、統合リンクコスト＝ｒ×リンク旅行時間＋（１−ｒ）×観測頻度によるコストとして求める。なお、所定の比率ｒは、例えばシミュレーションにて各車両の総旅行時間が最適値（観測頻度を考慮しない場合）からの悪化が平均して閾値以下になるような値を設定する。所定の比率ｒの設定については後述する。最短経路取得部２０３は、求められた統合リンクコストに基づいて最短経路を求める。その場合、特開平１１−３１６８８８号公報などに示される方法で求めてもよい。上記構成により、経路の重なりを排除する方向に働くため、求められた統合リンクコストにて、センシング範囲の増加と、渋滞の解消がある程度両立させることができる。
【００２２】
ここで、本発明の経路探索装置の処理フローの一例について図８を用いて説明する。まず、経路探索装置は、経路探索の対象領域内の各車両の出発時刻と目的地の情報を取得する（ステップＳ８０１）。ここで、送受信部２００は各車両から出発時刻を含む予定経路情報を受信するようにしてもよい。また、経路探索装置は、各車両から上記情報だけでなく、車両の走行速度などの情報も併せて受信するようにしてもよい。次に、経路探索装置は統合リンクコストをアップデートする（ステップＳ８０２）。ここでの統合リンクコストは、上述したように、例えば、現在のリンク旅行時間、予定通過数（将来のリンク旅行時間）、観測頻度の項を有する関数により定義され、統合リンクコスト＝ｆ（現在のリンク旅行時間、予定通過数、観測頻度）として表される。
【００２３】
ここでの統合リンクコストのアップデートは、具体的に、現在のリンク旅行時間、予定通過数（将来のリンク旅行時間）、観測頻度の３つの項の合成方法を変化させ、シミュレーションを行った場合の感度分析結果、全車両の総旅行時間と観測カバレッジ（観測範囲）がどのように変化するかによって、最適値を得る。合成は、例えば線形和を用いる。現在と将来のリンク旅行時間は同じく扱えるため、リンク旅行時間と観測頻度のコストにおいて、ｆ（リンク旅行時間、観測頻度）＝ｒ×（リンク旅行時間）＋（１−ｒ）×（観測頻度によるコスト）とし、パラメータｒを変化させて以下を行う。例えば、総旅行時間を、最適値のある割合以上悪化させない範囲で観測カバレッジを最大化したいなどの場合は、図９に示すような実験結果が得られたとすると、丸部分の時点のパラメータを採用する。
【００２４】
そして、経路探索装置は、アップデートされた統合リンクコストで最短経路をアップデートする（ステップＳ８０３）。経路探索装置は、最短経路をアップデートした後、経路が変化したか否かを判断する（ステップＳ８０４）。経路探索装置は、経路が変化しない場合には決定された経路を取得する（ステップＳ８０５）。一方、経路が変化する場合、経路探索装置は、各リンクの通過予定時刻を算出し（ステップＳ８０６）、各リンク、各時刻の車両の予定通過数を取得し（ステップＳ８０７）、各時刻のコスト（リンク旅行時間）の予測を取得する（ステップＳ８０８）。ここで、ステップＳ８０８において、リンクごとにＱ−Ｖ曲線（例えば、図３など）を求め、交通量Ｑが得られたときに速度Ｖを推定できるようにしておく。実際に行うには以下のような線形で近似する方法などを採る（http://nmdc.sakura.ne.jp/visitok/visitok_07/visitok_07_7.html）。
【００２５】
なお、上述した本発明の実施の形態では、模式的なブロック図を用いて説明を行ったが、これらのブロック図に記載されている各ブロックは、ハードウェア及び／又はソフトウェアによって実現可能である。また、フローチャートによって表されている動作は、ハードウェア及び／又は各処理を定めたプログラムをＣＰＵ（Central Processing Unit：中央演算処理装置）によって実行させることによって実現可能である。
【産業上の利用可能性】
【００２６】
本発明に係る経路探索装置は、適度（リーズナブル）な到達時間を確保しつつ、プローブカーとしての観測頻度や観測範囲を広げる経路指示を各車両に行うことができ、またプローブカーとしての必要なデータ品質を確保しつつ、各車両の便益（最短経路に近い経路での走行など）の低下を最小限にすることができるため、プローブカーによる情報に基づいて経路探索などを行う経路探索装置などに有用である。
【符号の説明】
【００２７】
１００  経路探索装置
１０１ａ、１０１ｂ、１０１ｃ  プローブカー
１１０  プローブカーシステム
２００  送受信部（受信手段）
２０１  算出部（第１の算出手段、第２の算出手段）
２０２  合成部（加算手段）
２０３  最短経路取得部（最短経路取得手段）
２０４  格納部
【図１】
2014190920.tif 000003
【図２】
2014190920.tif 000004
【図３】
2014190920.tif 000005
【図４】
2014190920.tif 000006
【図５】
2014190920.tif 000007
【図６】
2014190920.tif 000008
【図７】
2014190920.tif 000009
【図８】
2014190920.tif 000010
【図９】
2014190920.tif 000011