(57)【要約】【課題】交通渋滞を緩和できる交通状況の経路案内装置、経路案内方法及び経路案内プログラムを提供することを目的としている。【解決手段】経路案内装置が、予め定められている区間であるリンクを車両が通過するために要する第１の通過予測時間を前記車両の移動速度に基づき算出し、算出した前記第１の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第２の通過予測時間を算出し、算出した前記第２の通過予測時間に基づき、前記経路を選択する。【選択図】図３
2013057544.tif 000002
【特許請求の範囲】
【請求項１】
予め定められている区間であるリンクを車両が通過するために要する第１の通過予測時間を前記車両の移動速度に基づき算出し、
算出した前記第１の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第２の通過予測時間を算出し、
算出した前記第２の通過予測時間に基づき、前記経路を選択する
ことを特徴とする経路案内装置。
【請求項２】
前記車両の移動速度を含む交通情報を取得する交通情報収集部と、
前記経路上のリンクを抽出し、前記車両の移動速度に基づき前記車両が目的位置に到着する時刻までに渋滞が起きているリンクを抽出し、前記車両の移動速度に基づき前記渋滞が起きているリンクを前記車両が通過するのに要する第１の通過予測時間を生成する予測時間情報生成部と、
を備えることを特徴とする請求項１に記載の経路案内装置。
【請求項３】
前記車両の現在の走行位置から目的位置までの経路候補を示す経路候補情報を生成する経路候補情報生成部と、
前記経路候補で前記車両が目的位置に到着する時刻までに渋滞が起きているリンクに対する前記第１の通過予測時間に基づき第１の動的限界費用を算出する動的限界費用情報生成部と、
前記経路候補において前記渋滞が起きていないリンクを前記車両が通過するために要する通過予測時間に基づき第２の動的限界費用を算出し、前記経路候補の全てのリンクについて、前記第２の動的限界費用と前記動的限界費用情報生成部が算出した第１の動的限界費用とを前記経路候補毎に合計し、前記合計した動的限界費用を比較し、比較の結果、前記合計した動的限界費用が最小になる前記経路候補を探索するパレート改善経路案内部と、
を備えることを特徴とする請求項１または請求項２に記載の経路案内装置。
【請求項４】
前記予測時間情報生成部は、
前記経路候補上の全てのリンクから１つのリンクを抽出し、前記抽出したリンクにおける前記車両が前記目的位置に到着する時刻までの移動速度が予め定められている第１の速度未満であると判定した場合、前記抽出したリンクを前記車両が前記目的位置に到着する時刻までに渋滞が起きているリンクであると予測する
ことを特徴とする請求項１から請求項３のいずれか１項に記載の経路案内装置。
【請求項５】
前記予測時間情報生成部は、
前記渋滞が起きるリンクを示す情報に基づき、前記渋滞が終了するリンクをボトルネック・リンクとして抽出し、抽出した前記ボトルネック・リンクにおいて、前記経路候補上の前記ボトルネック・リンクの渋滞が終了する時刻を、前記リンク毎の前記車両の移動速度と前記経路候補情報を用いて推定する
ことを特徴とする請求項１から請求項４のいずれか１項に記載の経路案内装置。
【請求項６】
前記予測時間情報生成部は、
前記渋滞が起きるリンクの下流に接続されている全てのリンクにおいて、前記接続されているリンクに到達する時刻の前記車両の移動速度が予め定められている第２の速度以上であると判定した場合、前記渋滞が起きているリンクに重み付けを行い、前記渋滞が起きているリンクの重みを示す値が、予め定められている値より大きい場合、前記渋滞が起きているリンクをボトルネック・リンクとして抽出する
ことを特徴とする請求項１から請求項５のいずれか１項に記載の経路案内装置。
【請求項７】
前記予測時間情報生成部は、
前記渋滞が起きているリンクを示す情報及び前記車両の移動速度に基づき、予め定められている時速未満の前記リンクが連続している場合、１つの連続した渋滞が起きているリンクと判定する
ことを特徴とする請求項１から請求項６のいずれか１項に記載の経路案内装置。
【請求項８】
前記パレート改善経路案内部は、
前記ボトルネック・リンクの上流側に従属しているリンクのグラフ構造における末端数に基づき、前記ボトルネック・リンクの影響度を算出し、算出した前記影響度を用いて前記動的限界費用を算出する
ことを特徴とする請求項３から請求項７のいずれか１項に記載の経路案内装置。
【請求項９】
前記パレート改善経路案内部は、
前記車両が現在選択している前記現在位置から前記目標位置までの経路である現在経路における前記リンク費用の合計を算出し、前記選択した経路候補の前記リンク費用の合計と比較し、前記選択した経路候補の前記リンク費用の合計が前記現在経路における前記リンク費用の合計より小さい場合、前記選択した経路候補を前記経路として決定する
ことを特徴とする請求項３から請求項８のいずれか１項に経路案内装置。
【請求項１０】
経路案内装置における経路案内方法であって、
予め定められている区間であるリンクを車両が通過するために要する第１の通過予測時間を前記車両の移動速度に基づき算出する手段と、
算出した前記第１の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第２の通過予測時間を算出する手段と、
算出した前記第２の通過予測時間に基づき、前記経路を選択する手段と、
を含むことを特徴とする経路案内方法。
【請求項１１】
経路案内装置における経路案内方法の処理をコンピューターに実行させるための経路案内プログラムであって、
予め定められている区間であるリンクを車両が通過するために要する第１の通過予測時間を前記車両の移動速度に基づき算出する手順と、
算出した前記第１の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第２の通過予測時間を算出する手段と、
算出した前記第２の通過予測時間に基づき、前記経路を選択する手段と、
をコンピューターに実行させるための経路案内プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、車両の通行状況に係る情報から、道路の交通状況の予測を行う交通状況の経路案内装置、経路案内方法及び経路案内プログラムに関する。
【背景技術】
【０００２】
交通状況の予測演算装置は、車両の通行状況に係る道路情報データを収集して、その道路情報データに基づいて発生する渋滞状況などを予測し、予測した渋滞状況の情報などを提供する。ここで、道路情報データは、交通情報システムで定期的に収集される。このように定期的に収集される道路情報データに基づいて、刻々と状況が変化する渋滞情報などの交通状況を予測するシステムが知られている（例えば、非特許文献１から３参照）。
予測された交通状況の情報は、路側に設けられた道路情報表示板や、道路交通情報通信システム（ＶＩＣＳ（ビックス）；Ｖｅｈｉｃｌｅ  Ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｙｓｔｅｍ）や、放送メディアなどを介して提供される。
【０００３】
例えば、道路交通情報通信システムにおいて、集計センターは、道路に設置されている固定センサーを介して車両の交通量データを収集している。集計センターは、収集したデータを処理して渋滞状況などの道路交通情報を生成して、生成した道路交通情報をＦＭ放送に多重して送信している。このため、従来の道路交通情報通信システムでは、固定センサーが設置されている道路しか道路交通情報が提供できなかった。従って、ＶＩＣＳ交通情報は、日本全国の幅が５．５［ｍ］以上の道路の全長約８３万［ｋｍ］のうち、固定センサーが設置されている主要道路約７万［ｋｍ］しかカバーできていなかった。
【０００４】
このため、以下のような道路交通情報を提供するシステム（以下、道路交通情報システムという）が、提供され始めている。道路交通情報システムでは、車両が、自車の位置及び走行状態を示す走行情報に時刻情報を付加したプローブ交通情報を発信する。そして、道路交通情報システムは、受信したプローブ交通情報を用いて、道路交通情報の提供を行う。このようなサービスは、現在、各自動車メーカーまたはカーナビゲーション・メーカーのカーナビゲーションシステムの利用車両からの情報に基づいて行われている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】白石、桑原、堀口、「リアルタイム予測交通流シミュレーションの開発」、第30回土木計画学研究発表会、2004年11月21〜23日。
【非特許文献２】白石、堀口、「リアルタイムシミュレーションを用いた交通流予測システムの開発」、第54回理論応用力学講演会（NCTAM2005）日本学術会議、2005年1月27日。
【非特許文献３】Shiraishi, Kuwahara, Horiguchi，「A Development of Traffic Prediction System Based on Real-time Simulation」、第12回ITS世界会議サンフランシスコ2005、2005年11月6〜10日。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、プローブ交通情報を提供する車両や、プローブ交通情報を利用する車両が増えた場合、従来のカーナビゲーションシステムと同様に最適なルートを車両に提供してしまうと、最適ルートに車両が集中してしまい交通渋滞を緩和できないという問題点があった。
【０００７】
本発明は、上記の問題点に鑑みてなされたものであって、交通渋滞を緩和できる交通状況の経路案内装置、経路案内方法及び経路案内プログラムを提供することを目的としている。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明に係る経路案内装置は、予め定められている区間であるリンクを車両が通過するために要する第１の通過予測時間を前記車両の移動速度に基づき算出し、算出した前記第１の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第２の通過予測時間を算出し、算出した前記第２の通過予測時間に基づき、前記経路を選択することを特徴としている。
【０００９】
なお、本発明において、第１の通過予測時間とは、車両がリンクを通過するために要すると予測される時間である。また、第２の通過予測時間とは、現在の走行位置から目標位置までの経路を車両が通過するために要すると予測される時間である。すなわち、本発明は、経路案内装置が、経路ではなく、リンクの第１の通過予測時間を用いて、経路候補を探索することに特徴がある。
【００１０】
また、本発明の経路案内装置において、前記車両の移動速度を含む交通情報を取得する交通情報収集部と、前記経路上のリンクを抽出し、前記車両の移動速度に基づき前記車両が目的位置に到着する時刻までに渋滞が起きているリンクを抽出し、前記車両の移動速度に基づき前記渋滞が起きているリンクを前記車両が通過するのに要する第１の通過予測時間を生成する予測時間情報生成部と、を備えるようにしてもよい。
【００１１】
また、本発明の経路案内装置において、前記車両の現在の走行位置から目的位置までの経路候補を示す経路候補情報を生成する経路候補情報生成部と、前記経路候補で前記車両が目的位置に到着する時刻までに渋滞が起きているリンクに対する前記第１の通過予測時間に基づき第１の動的限界費用を算出する動的限界費用情報生成部と、前記経路候補において前記渋滞が起きていないリンクを前記車両が通過するために要する通過予測時間に基づき第２の動的限界費用を算出し、前記経路候補の全てのリンクについて、前記第２の動的限界費用と前記動的限界費用情報生成部が算出した第１の動的限界費用とを前記経路候補毎に合計し、前記合計した動的限界費用を比較し、比較の結果、前記合計した動的限界費用が最小になる前記経路候補を探索するパレート改善経路案内部と、を備えるようにしてもよい。
【００１２】
なお、本発明において、リンクの動的限界費用とは、あるリンクを１台の車両が選択したこと（もしくはしなかったこと）による総費用の増加分（減少分）を意味している。また、第１の動的限界費用とは、経路候補で車両が目的位置に到着する時刻までに渋滞が起きているリンクに対する動的限界費用である。また、第２の動的限界費用とは、渋滞が起きていないリンクに対する動的限界費用である。また、限界費用とは、一般的に生産１単位あたりにかかる費用であり、本発明では、経路間の移動にかかる１単位毎の費用である。すなわち、本発明は、パレート改善経路案内部が、経路ではなく、リンクの動的限界費用を用いて、経路候補を探索することに特徴がある。
【００１３】
また、本発明の経路案内装置において、前記予測時間情報生成部は、前記経路候補上の全てのリンクから１つのリンクを抽出し、前記抽出したリンクにおける前記車両が前記目的位置に到着する時刻までの移動速度が予め定められている第１の速度未満であると判定した場合、前記抽出したリンクを前記車両が前記目的位置に到着する時刻までに渋滞が起きているリンクであると予測するようにしてもよい。
【００１４】
また、本発明の経路案内装置において、前記予測時間情報生成部は、前記渋滞が起きるリンクを示す情報に基づき、前記渋滞が終了するリンクをボトルネック・リンクとして抽出し、抽出した前記ボトルネック・リンクにおいて、前記経路候補上の前記ボトルネック・リンクの渋滞が終了する時刻を、前記リンク毎の前記車両の移動速度と前記経路候補情報を用いて推定するようにしてもよい。
【００１５】
また、本発明の経路案内装置において、前記予測時間情報生成部は、前記渋滞が起きるリンクの下流に従属されている全てのリンクにおいて、前記従属されているリンクに到達する時刻の車両の移動速度が予め定められている第２の速度以上であると判定した場合、前記渋滞が起きているリンクに重み付けを行い、前記渋滞が起きているリンクの重みを示す値が、予め定められている値より大きい場合、前記渋滞が起きているリンクをボトルネック・リンクとして抽出するようにしてもよい。
【００１６】
また、本発明の経路案内装置において、前記予測時間情報生成部は、前記渋滞が起きているリンクを示す情報及び前記車両の移動速度に基づき、予め定められている時速未満の前記リンクが連続している場合、１つの連続した渋滞が起きているリンクと判定するようにしてもよい。
【００１７】
また、本発明の経路案内装置において、前記パレート改善経路案内部は、前記ボトルネック・リンクの上流側に従属しているリンクのグラフ構造における末端数に基づき、前記ボトルネック・リンクの影響度を算出し、算出した前記影響度を用いて前記動的限界費用を算出するようにしてもよい。
【００１８】
また、本発明の経路案内装置において、前記パレート改善経路案内部は、車両が現在選択している前記現在位置から前記目標位置までの経路である現在経路における前記リンク費用の合計を算出し、前記選択した経路候補の前記リンク費用の合計と比較し、前記選択した経路候補の前記リンク費用の合計が前記現在経路における前記リンク費用の合計より小さい場合、前記選択した経路候補を前記経路として決定するようにしてもよい。
【００１９】
上記目的を達成するため、本発明は、経路案内装置における経路案内方法であって、予め定められている区間であるリンクを車両が通過するために要する第１の通過予測時間を前記車両の移動速度に基づき算出する手段と、算出した前記第１の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第２の通過予測時間を算出する手段と、算出した前記第２の通過予測時間に基づき、前記経路を選択する手段と、を含むことを特徴としている。
【００２０】
上記目的を達成するため、本発明は、経路案内装置における経路案内方法の処理をコンピューターに実行させるための経路案内プログラムであって、予め定められている区間であるリンクを車両が通過するために要する第１の通過予測時間を前記車両の移動速度に基づき算出する手順と、算出した前記第１の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第２の通過予測時間を算出する手段と、算出した前記第２の通過予測時間に基づき、前記経路を選択する手段と、をコンピューターに実行させることを特徴としている。
【発明の効果】
【００２１】
本発明に係る経路案内装置は、車両がリンクを通過するために要すると予測される時間（第１の通過予測時間）を算出する。次に、本発明に係る経路案内装置は、算出した第１の通過予測時間に基づいて、現在の走行位置から目標位置までの経路を車両が通過するために要すると予測される時間（第２の通過予測時間）を算出し、算出した第２の通過予測時間に基づいて経路を選択するようにした。
この結果、本発明に係る経路案内装置は、利用者にとって経路が最短の利用者最適状態における移動時間より移動時間を軽減し、さらに経路案内装置を利用している利用者の合計移動時間が最も少ないシステム最適状態において生じる利用者の旅行時間の増加を軽減できるパレート最適状態の交通渋滞緩和することができる。
【図面の簡単な説明】
【００２２】
【図１】本実施形態に係る経路案内システムのフレームワークを説明する図である。
【図２】パラドックスがある静的配分問題での利用者均衡状態、パレート最適状態、システム最適状態を説明する図である。
【図３】本実施形態に係る経路案内システム１の概略構成図である。
【図４】リンクへの流入車両数とリンクからの流出車両数を説明する図である。
【図５】本実施形態に係る経路の限界費用を説明する図である。
【図６】本実施形態に係る動的限界費用を説明する図である。
【図７】本実施形態に係る渋滞区間を説明する図である。
【図８】本実施形態に係るボトルネック・リンクの特定方法の一例を説明する図である。
【図９】本実施形態に係るボトルネック・リンクの影響度を説明する図である。
【図１０】本実施形態に係る経路案内システム１の処理手順のフローチャートである。
【図１１】本実施形態に係る経路案内システム１において、シミュレーションに用いた地図である。
【図１２】図１１に示したエリアで本実施形態に係る経路案内システム１をシミュレーションした結果である。
【図１３】システム最適状態における経路変更有り場合の車両台数と旅行時間変化を表す図である。
【図１４】本実施形態に係るパレート最適状態における経路変更有り場合の車両台数と旅行時間変化を表す図である。
【発明を実施するための形態】
【００２３】
最初に、本発明の概要を説明する。
本発明に係る経路案内システムは、後述するパレート最適状態における限界費用を算出する。また、本発明に係る経路案内システムは、経路の限界費用を算出するのではなく、後述するリンクの限界費用を算出するようにしたことに特徴がある。なお、限界費用とは、一般的に生産１単位あたりにかかる費用であり、本発明では、経路間の移動にかかる１単位毎の費用である。そして、本発明に係る経路案内システムは、このリンクの限界費用に基づき、パレート最適状態となる各車両の経路を生成して、各車両に提供する。
【００２４】
以下、図面を用いて、本発明の実施形態について説明する。
まず、本発明の概要について説明する。図１は、本実施形態に係る経路案内システムのフレームワークを説明する図である。
図１において、符号ｔｅｒは、経路案内システム１を利用している車両の集まりを表している。車両Ｍ１−１からＭ１−４は、プローブ（Ｐｒｏｂｅ）車両を表している。なお、プローブ車両とは、車両の走行データ（速度情報、位置情報、時間情報など）を取得して送信する装置を搭載している車両である。この装置が取得したデータをプローブ交通情報といい、プローブ車両は、取得したプローブ交通情報をプローブ交通情報システムＳｙｓ１（プローブ送信センターともいう）に送信する。
車両Ｍ１０−１からＭ１０−１６は、プローブ車両以外の経路案内システム１を利用している車両を表している。
車両Ｍ２０−１からＭ２０−４は、経路案内システム１を利用していない車両を表している。
【００２５】
情報ｉ１からｉ４は、各プローブ車両Ｍ１−１からＭ１−４からプローブ交通情報システムＳｙｓ１に送信される情報を表している。情報ｉ５は、情報ｉ１からｉ４を模式的に表している。情報ｉ６は、プローブ交通情報システムＳｙｓ１からリアルタイム渋滞予測システムＳｙｓ２に送信される情報を表している。情報ｉ７は、リアルタイム渋滞予測システムＳｙｓ２から環境改善パレート経路案内システムＳｙｓ３に送信される情報を表している。情報ｉ８は、環境改善パレート経路案内システムＳｙｓ３から経路案内システム１を利用している車両に送信される情報を表している。
【００２６】
プローブ車両Ｍ１−１からＭ１−４及びプローブ交通情報システムＳｙｓ１は、交通状況の変化を即時かつ詳細に捉える、センサーの役割を果たす。
リアルタイム渋滞予測システムＳｙｓ２は、現在の状況から予測しうる将来の状況情報（予測旅行時間情報と称する）を生成する。リアルタイム渋滞予測システムＳｙｓ２は、生成した予測旅行時間情報に基づき、環境改善パレート経路案内システムＳｙｓ３が行う演算に必要な動的限界費用（ＤＭＣ）情報を求める。
環境改善パレート経路案内システムＳｙｓ３は、リアルタイム渋滞予測システムＳｙｓ２が生成した予測旅行時間情報と動的限界費用情報に基づき、パレート最適状態の経路案内情報を生成し、生成した経路案内情報を車両（Ｍ１−１〜Ｍ１−４、Ｍ１０−１〜Ｍ１０−１６）に送信する。
このプローブ交通情報システムＳｙｓ１、リアルタイム渋滞予測システムＳｙｓ２、環境改善パレート経路案内システムＳｙｓ３、車両（Ｍ１−１〜Ｍ１−４、Ｍ１０−１〜Ｍ１０−１６）は、オープンループ系を構成している。
なお、本実施形態における経路の動的な限界費用とは、ある経路を１台の車両が選択したこと（もしくはしなかったこと）による総費用の増加分（減少分）を意味している。
【００２７】
ここでパレート最適状態の概念について、図２を用いて説明する。
図２は、パラドックスがある静的配分問題での利用者均衡状態、パレート最適状態、システム最適状態を説明する図である。なお、パレート最適状態とは、他車の旅行時間を増加させることなく、自車の旅行時間をこれ以上短縮することが出来ない状態である。このような状態は、ある条件下で、経路間の等費用原則が成立している利用者均衡状態よりも社会的に小さい費用が達成されることが知られている。また、システム最適状態とは、経路上の総費用が最小になる、システムから見た場合に最適な状態である。また、利用者均衡状態とは、全てのネットワーク利用者に対して、費用が均等になるような状態である。
【００２８】
図２では、経路をネットワークとして表している。符号ｐ１からｐ４は、各々、点を表している。また、符号ｌ１２、ｌ１３、ｌ２３、ｌ２４及びｌ３４は、各々、リンクを表している。符号ｌ１２は、点１から点２へのリンク（１２）を表し、符号ｌ２４は、点２から点４へのリンク（２４）を表している。符号ｌ１３は、点１から点３へのリンク（１３）を表し、符号ｌ３４は、点３から点４へのリンク（３４）を表している。符号ｌ２３は、点２から点３へのリンク（２３）を表している。
【００２９】
図２（ａ）から図２（ｄ）に示した例では、点ｐ１からｐ４に移動する場合、経路は以下の３つある。第１の経路は、最初にリンク（１２）ｌ１２を通り、次にリンク（２４）ｌ２４を経る経路（１２４）である。第２の経路は、最初にリンク（１３）ｌ１３を通り、次にリンク（３４）ｌ３４を経る経路（１３４）である。第３の経路は、最初にリンク（１２）ｌ１２を通り、次にリンク（２３）ｌ２３を経て、最後にリンク（３４）ｌ３４を経る経路（１２３４）である。
【００３０】
図２（ａ）は、サービス水準と限界費用を説明する図である。
図２（ａ）において、リンク（１２）ｌ１２とリンク（３４）ｌ３４は、サービス水準が高く、限界費用が大きいリンクである。リンク（１３）ｌ１３とリンク（２４）ｌ２４は、サービス水準が低く、限界費用が小さいリンクである。リンク（２３）ｌ２３は、限界費用が大きいリンク（１２）ｌ１２とリンク（３４）ｌ３４をつなぐ限界費用の小さなリンクである。なお、限界費用とは、図２のようなネットワークにおいて経路間の移動にかかる１単位毎の費用である。
また、図２（ａ）において、符号ｘ１２は、リンク（１２）ｌ１２の費用を表し、符号ｘ２４は、リンク（２４）ｌ２４の費用を表している。符号ｘ１３は、リンク（１３）ｌ１３の費用を表し、符号ｘ３４は、リンク（３４）ｌ３４の費用を表している。符号ｘ２３は、リンク（２３）ｌ２３の費用を表している。
リンク（１２）ｌ１２の費用「１０ｘ１２」のうち「ｘ１２」に乗じられている「１０」は、限界費用の大きさを表している。リンク（２３）ｌ２３の費用「ｘ１３＋５０」のうち「ｘ１３」に加算されている「５０」は、サービス水準の大きさを表している。
また、図２（ａ）において、各リンクの費用は、リンク１２の費用が１０ｘ１２であり、リンク１３の費用がｘ１３＋５０であり、リンク２３の費用がｘ２３＋１０であり、リンク２４の費用がｘ２４＋５０であり、リンク３４の費用が１０ｘ３４である。
【００３１】
図２（ｂ）は、利用者均衡状態の例を説明する図である。
図２（ｂ）の状態は、経路１２４の経路の費用（以下、経路費用という）（１０ｘ１２（＝４）＋（ｘ２４（＝２）＋５０）＝９２）と、経路（１３４）の経路費用（（ｘ１３（＝２）＋５０）＋１０ｘ３４（＝４）＝９２）と、経路（１２３４）の経路費用（１０ｘ１２（＝４）＋（ｘ２３（＝２）＋１０）＋１０ｘ３４（＝４）＝９２）とが均衡、すなわち一致している状態である。このため、図２（ｂ）における総費用は、９２×３＝２７６である。
【００３２】
図２（ｃ）は、システム最適状態の例を説明する図である。
図２（ｃ）の状態の各費用は、経路（１２４）の経路費用（１０ｘ１２（＝３）＋（ｘ２４（＝３）＋５０）＝８３）、経路（１３４）の経路費用（（ｘ１３（＝３）＋５０）＋１０ｘ３４（＝３）＝８３）、経路（１２３４）の経路費用（１０ｘ１２（＝３）＋（ｘ２３（＝０）＋１０）＋１０ｘ３４（＝３）＝７０）である。従って、図２（ｃ）のシステム最適状態の総費用２３６（＝８３＋８３＋７０）は、図２（ｂ）の利用者均衡状態の総費用２７６より安い。
【００３３】
図２（ｄ）は、パレート最適状態の例を説明する図である。
図２（ｄ）の状態の各費用は、経路（１２４）の経路の費用の合計（１０ｘ１２（＝３．５）＋（ｘ２４（＝２．５）＋５０）＝８７．５）、経路（１３４）の経路の費用の合計（（ｘ１３（＝２．５）＋５０）＋１０ｘ３４（＝３．５）＝８３）、経路（１２３４）の経路の費用の合計（１０ｘ１２（＝３．５）＋（ｘ２３（＝１．０）＋１０）＋１０ｘ３４（＝３．５）である。従って、図２（ｄ）のパレート最適状態の総費用２５６は、図２（ｃ）のシステム最適状態の総費用２３６より高く、図２（ｂ）の利用者均衡状態の総費用２７６より安い。
【００３４】
一般的な経路案内システムでは、経路案内システムを利用している全ての車両に対して、図２（ｂ）に示したような利用者均衡状態である最適なルートを提供していた。このような利用者均衡状態の場合、最適ルートに車両が集中してしまい交通渋滞緩和できないという課題があった。利用者均衡状態は、図２（ｂ）で説明したように、経路費用、及び総費用は、パレート最適状態、及びシステム最適状態より大きい。
交通渋滞を緩和するため、仮に経路案内システムにとっての最適なシステム最適状態である経路（以下、システム最適経路という）を導入した場合について説明する。システム最適状態において、経路案内システムは、全ての車両を最適なルートに誘導するのではなく、最適なルートに車両が集中するのを防ぐために、一部の車両に対して迂回を強いるルートに誘導する。この場合、迂回を強いられた車両のドライバーは、不利益を被ることになるので、このようなルートの経路案内を受け入れ難い。しかしながら、図２（ｄ）で説明したように、経路費用、及び総費用は、利用者均衡状態のものより小さくなる。
一方、図２（ｃ）で説明したように、パレート最適状態は、経路費用、及び総費用（＝８１）が利用者均衡状態のものより安くなり、一部の利用者（経路１２３４）の経路費用が、システム最適状態の経路（１２４）及び経路（１３４）の経路費用（＝８３）より安くなっている。
このため、本実施形態に係る経路案内システムは、最適ルートに車両が集中しないようにして交通渋滞緩和の効率を悪化させず、且つドライバーに不利にならない経路案内であるパレート最適状態の経路案内を行う。
【００３５】
次に、経路案内システム１の構成を、図３を用いて説明する。
図３は、本実施形態に係る経路案内システム１の概略構成図である。図３に示したように、経路案内システム１は、プローブ交通情報収集装置１０１、交通情報蓄積装置１０２、外部情報記憶部１０３、統計情報処理装置１０４、予測旅行時間情報生成装置１０５、動的限界費用情報生成装置１０６、及びパレート改善経路案内装置１０７を備えている。
【００３６】
プローブ交通情報収集装置１０１（交通情報収集部）は、プローブ車両Ｍ３０が送信するプローブ交通情報ｉ１０を取得する。プローブ交通情報収集装置１０１は、受信したプローブ交通情報ｉ１０、道路に設置されているセンサーからの交通量情報、過去の交通量情報等を用いて、公知の手法により現在の交通量や車両の旅行速度等を示すリアルタイム交通情報ｉ１１を生成する。交通量情報とは、車両の位置、移動速度、現在時刻などの情報である。プローブ交通情報収集装置１０１は、生成したリアルタイム交通情報ｉ１１を予測旅行時間情報生成装置１０５に出力し、さらに生成したリアルタイム交通情報ｉ１１を交通情報蓄積装置１０２に記憶させる。
【００３７】
交通情報蓄積装置１０２には、各時刻のリアルタイム交通情報ｉ１１が記憶されている。
外部情報記憶部１０３には、センサーから取得した交通量情報、過去の統計的な交通量情報、及び道路に設置されているセンサーから送信された情報に基づいて生成された交通情報が記憶されている。
【００３８】
統計情報処理装置１０４は、交通情報蓄積装置１０２に記憶されているリアルタイム交通情報ｉ１２を読み出す。統計情報処理装置１０４は、外部情報記憶部１０３に記憶されている交通情報ｉ１３を読み出す。統計情報処理装置１０４は、読み出したリアルタイム交通情報ｉ１２と交通情報ｉ１３とに基づき、予測モデルを生成する。
なお、予測モデルとは、現在時間を基準とした直前の旅行時間の変動データを入力として、現在時間を基準とした将来の旅行時間の変動情報を出力する予測モデルである。
予測モデルは、読み出したリアルタイム交通情報ｉ１２と交通情報ｉ１３の統計データから学習させた旅行時間情報の変動特性を示すものである。なお、変動特性とは、例えば、直前に入力されたデータとその後の出力とを回帰分析することで、入力に対する出力の関係を示す特性である。
そして、この生成された予測モデルは、予測旅行時間情報生成装置１０５がリアルタイム交通情報を入力（現在時間を基準とした過去の情報）として、予測旅行時間情報を出力（現在時間を基準とした将来の情報）として生成する際に使用される。
なお、交通情報蓄積装置１０２及び外部情報記憶部１０３には、例えば、各々１週間分の情報が蓄積されている。そして、統計情報処理装置１０４は、例えば、一週間に一回の周期で、交通情報蓄積装置１０２及び外部情報記憶部１０３に蓄積されている各情報を読み出して、上述した予測モデルを生成し、生成した予測モデルを示す情報ｉ１４を予測旅行時間情報生成装置１０５に出力する。
【００３９】
予測旅行時間情報生成装置１０５（経路候補情報生成部、予測時間情報生成部）は、プローブ交通情報収集装置１０１が生成したリアルタイム交通情報ｉ１１を、統計情報処理装置１０４が生成した予測モデルを用いて、リンク毎の予測旅行時間情報（第１の通過予測時間）を生成する。予測旅行時間情報生成装置１０５は、図示しない交通情報端末を搭載している車両Ｍ４０が送信する車両が、現在、走行している経路情報（以下、現在経路情報という）と、車両が走行している目的地情報とを含む情報ｉ１５を取得する。
予測旅行時間情報生成装置１０５は、取得した現在経路情報と目的地情報に基づき、車両Ｍ４０の現在位置から目的位置までの経路候補情報を公知の手法を用いて生成する。予測旅行時間情報生成装置１０５は、生成した予測旅行時間情報と、生成した目的地までの経路候補情報と、プローブ交通情報収集装置１０１が出力するリアルタイム交通情報ｉ１１と、統計情報処理装置１０４が生成した予測モデルとを用いて、後述するように経路候補情報の経路からボトルネック・リンクを抽出する。なお、ボトルネック・リンクについては、後述する。
予測旅行時間情報生成装置１０５は、抽出したボトルネック・リンクにおいて、経路上のボトルネック・リンクの渋滞が終了する時刻（以下、渋滞終了予想時刻という）を、予測旅行時間情報と経路候補情報とを用いて推定する。予測旅行時間情報生成装置１０５は、生成した予測旅行時間情報及び推定した経路候補情報を動的限界費用情報生成装置１０６に出力する。
なお、予測旅行時間情報生成装置１０５は、プローブ交通情報収集装置１０１が出力するリアルタイム交通情報ｉ１１を、統計情報処理装置１０４が生成した予測モデルを用いて、例えば、５分周期でリンク毎の予測旅行時間情報を生成する。予測旅行時間情報生成装置１０５が予測旅行時間情報を生成する周期は、例えば、予測する時間帯、季節、場所などに応じて選択するようにしてもよい。
【００４０】
動的限界費用情報生成装置１０６（動的限界費用情報生成部）は、リンク毎の予測旅行時間情報と、経路候補情報、渋滞終了予想時刻、ボトルネック・リンクを用いて、後述するように各経路の動的限界費用を算出する。動的限界費用情報生成装置１０６は、入力された経路候補情報、動的限界費用を示す情報及び予測旅行時間情報ｉ１６、算出した各経路の動的限界費用に基づき、各経路候補の予測旅行時間（第２の通過予測時間）及び動的限界費用を算出する。動的限界費用情報生成装置１０６は、算出した各経路候補の予測旅行時間及び動的限界費用を含む情報ｉ１７をパレート改善経路案内装置１０７に出力する。
【００４１】
パレート改善経路案内装置１０７（パレート改善経路案内部）は、動的限界費用情報生成装置１０６が出力する各経路候補の予測旅行時間及び動的限界費用に基づき、後述するように各ボトルネック・リンクの経路候補への影響度を算出する。パレート改善経路案内装置１０７は、動的限界費用情報生成装置１０６が出力する各経路候補の予測旅行時間及び動的限界費用に基づき、現在、車両Ｍ４０が通行している経路と、生成した各経路候補の各予測旅行時間と各動的限界費用について、順次比較する。パレート改善経路案内装置１０７は、後述するように動的限界費用が最小になる経路候補を探索する。
パレート改善経路案内装置１０７は、算出した経路候補の中から、予測旅行時間が現在経路以下であり、且つ動的限界費用が現在経路以下である動的限界費用が最小になる経路候補を探索する。パレート改善経路案内装置１０７は、予測旅行時間が現在経路以下であり、且つ動的限界費用が現在経路以下である動的限界費用が最小になる推奨経路候補があるか否かを判定する。推奨経路候補があると判定した場合、パレート改善経路案内装置１０７は、探索結果である推奨経路情報ｉ１８を、交通情報端末を搭載している車両Ｍ４０に送信する。推奨経路候補がない判定した場合、パレート改善経路案内装置１０７は、探索結果を、交通情報端末を搭載している車両Ｍ４０に送信しない。
【００４２】
次に、経路探索アルゴリズムにおける動的限界費用について説明する。
一般的なカーナビゲーションシステムや交通情報センターで使われている経路探索アルゴリズムは、リンクの費用をベースに計算している。しかしながら、動的限界費用はリンク単位に定義されるのではなく、走行経路単位で定義される概念である。このため、リンクの費用をベースに計算し、経路探索した結果を使わないと、動的限界費用が計算できないことになる。さらに、一般的な道路における車両は、信号機による制御の影響を受けているため、非渋滞時でも移動時間（旅行時間ともいう）にある程度の遅れを伴っている。従って、ほとんどの経路は、シミュレーション開始時間から終了時間まで、常に遅れを伴う旅行時間を有することになる。この結果、一般的な経路探索アルゴリズムでは、厳密に限界費用を算出することが困難である。
このため、本実施形態では、図２で説明したリンク単位で動的限界費用を近似的に算出する。近似的に算出できる根拠は、「動的限界費用は、ある車両が渋滞区間を抜けるまでに要する所要時間と、その車両が渋滞末尾に到着した時刻から、その渋滞が解消するまでの時間の合計に等しい」ことが本発明の発明者らの研究により示されている（桑原雅夫，吉井稔雄，熊谷香太郎：動的システム最適配分とランプ流入制御に関する研究−簡略ネットワークにおける基礎的分析−，土木学会論文集，No.667/IV-50，pp.59-71，土木学会，2001.01．参照）。
なお、本実施形態における経路の動的限界費用は、その車両が経路上の渋滞区間に到着した時刻と、その後に渋滞が解消するまでの時刻との差、すなわち渋滞区間を通過するために要する時間に等しい。
【００４３】
図４は、リンクへの流入車両数とリンクからの流出車両数を説明する図である。なお、図４では、説明を簡単にするために、１つのリンクについて説明する。
図４において、横軸は時間を表し、縦軸は累積交通量を表している。曲線ｇ１０１は、リンクへの流入量（車両台数）の時間に対する変化を表している。符号ｇ１０２は、リンクからの流出量（車両台数）の時間に対する変化を表している。また、時刻ｔａからｔｂの期間の曲線ｇ１１１は、時刻ｔａにおける動的限界費用を表している。破線ｇ１３１は、Ｎ台目を表している。
図４に示したように、リンクへの流入量（曲線ｇ１０１）は、リンクからの流出量（曲線ｇ１０２）に対して隔たりがある場合、このリンクで流出が滞る、すなわち渋滞が発生することを意味している。
この場合、破線ｇ１３１のように、時刻ｔａに流入したＮ台目の車両は、Ｎ台目にこのリンクを流出する。このため、図４において時間ｔａｂは、Ｎ台目の車両が渋滞に入ってきてから、渋滞から抜け出すまでの旅行時間を表している。
また曲線ｇ１１１は、このリンクで起きている渋滞が、時刻ｔａから先の時刻において、どの車両まで渋滞が継続しているかを表している。
【００４４】
次に、経路の限界費用について図５を用いて説明する。
図５は、本実施形態に係る経路の限界費用を説明する図である。図５（ａ）は、経路を説明する図である。図５（ｂ）は、経路の交通量（経路フロー）における限界費用を説明する図である。図５（ｃ）は、リンク単位の交通量（リンクフロー）における限界費用を説明する図である。図５（ｂ）において、横軸は時間を表し、縦軸は経路ｋの累積交通量を表している。また、図５（ｃ）において、横軸は時間を表し、縦軸はリンク交通量を表している。
図５（ａ）において、符号ｐ２０１からｐ２０５は、経路ｋ及び経路ｊの各位置を表している。また、符号ｌ２０１からｌ２０６は、経路ｋ及び経路ｊの各リンクを表している。また、図５（ａ）において、車両の移動方向は、位置ｐ２０１（上流）からｐ２０４（下流）に向かう方向である。また、リンクｌ２０１を経路ｋのｉ番目のリンク、リンクｌ２０２とｌ２０５を経路ｋのｉ＋１番目のリンク、リンクｌ２０３とｌ２０６を経路ｋのｉ＋２番目のリンクとする。
図５（ａ）に示したように、経路ｋは、位置ｐ２０１から車両が流入し、リンクｌ２０１を通り、リンクｌ２０２、及びｌ２０３を経て位置２０４から流出する。また、経路ｊは、位置ｐ２０５から車両が流入し、リンクｌ２０５を通り、リンクｌ２０６を経て位置２０４から流出する。この場合、位置ｐ２０３において、経路ｋのリンク２０２と、経路ｊのリンクｌ２０５とが合流している。すなわち、リンクｌ２０３とｌ２０６は、同じ道路である。
【００４５】
ここで、単純なネットワークの場合、経路の動的限界費用は，図５（ｂ）に示したように、ある経路の交通量（経路フロー）について、到着累積曲線とボトルネック・リンクにおける通過の累積曲線を描き、図式的に求めることで得られる。図５（ｂ）において、曲線Ａｋｉは、リンクｌ２０１における上流の位置ｐ２０１から流入（到着交通量ともいう）する交通量（車両台数）の時間に対する変化を表している。曲線Ａｋｉ＋１は、リンクｌ２０２における上流の位置ｐ２０２から流入する交通量の時間に対する変化を表している。曲線Ａｋｉ＋２は、リンクｌ２０３における上流の位置ｐ２０３から流入する交通量の時間に対する変化を表している。曲線Ｄｋｉ＋２は、リンクｌ２０３における下流の位置ｐ２０４（ボトルネック・リンク）から流出する交通量の時間に対する変化を表している。
また、破線ｇ２０１とｇ２０２は、リンクｌ２０３へのリンクｌ２０１と同等の流入量を模式的に表している。すなわち、リンクｌ２０１には、破線ｇ２０１で示した車両台数が流入している。しかしながら、リンクｌ２０３では、実線で示した曲線Ａｋｉ＋２のみ流入し、差分の車両が渋滞していることを示している。また、流出量を示す曲線Ｄｋｉ＋２においても、破線ｇ２０２に示した流入量より低い台数のみの車両しか通過できていず、差分の車両が渋滞していることを示している。
また、曲線ｄ２０１は、図４で説明したのと同様に、時刻ｔ１における経路ｋの限界費用を表している。
【００４６】
本実施形態では、図５（ｃ）に示すように、経路毎ではなくリンク単位で交通量（リンクフロー）の累積図を描き、ある経路上の渋滞区間の最後に位置するボトルネック・リンクの累積図から、簡易的に動的限界費用を求める。
図５（ｃ）の曲線Ａｉは、リンクｌ２０１における上流の位置ｐ２０１から流入する交通量の時間に対する変化を表している。
曲線Ａｉ＋１は、リンクｌ２０２における上流の位置ｐ２０２から流入する交通量と、リンクｌ２０５における上流の位置ｐ２０５から流入する交通量とを加算した交通量の時間に対する変化を表している。曲線Ａｉ＋２は、リンクｌ２０３及びリンク２０６における上流の位置ｐ２０３から流入する交通量の時間に対する変化を表している。曲線Ｄｉ＋２は、リンクｌ２０３における下流の位置ｐ２０４から流出する交通量の時間に対する変化を表している。
また、破線ｇ２１１は、リンクｌ２０３へのリンクｌ２０１と同等の流入量を模式的に表している。
また、曲線ｄ２０２は、遅れを伴うリンクｌ２０３及びｌ２０６における経路ｋの限界費用を表している。
さらに、図５（ａ）及び図５（ｃ）で示したように、リンクｌ２０３で渋滞が終了しているため、このリンクｌ２０３をボトルネック・リンクと定義する。
【００４７】
図５（ｃ）において、曲線Ａｉ〜Ａｉ＋２、Ｄｉ＋２の傾きが大きい方が、交通量が多いことを表している。また、曲線Ａｉの傾きより、曲線Ｄｉ＋２の傾きが小さいのは、到着した交通量が多くても、その経路で通過させることができる交通量が到着した交通量より少ないことを表している。ここで、曲線Ｄｉ＋２の傾きを、ボトルネックの容量と定義する。なお、ボトルネックの容量とは、単位時間当たりに通過できる交通量である。
このため、曲線Ａｉの傾きと曲線Ａｉ＋１の傾きとの乖離量は、流入した交通量と実際に流れた交通量の乖離を表し、すなわち、区間ｉから区間ｉ＋１に溜まっている交通量を表している。
同様に、曲線Ａｉ＋１の傾きと曲線Ａｉ＋２の傾きとの乖離量は、流入した交通量と実際に流れた交通量の乖離を表し、すなわち、区間ｉ＋１から区間ｉ＋２に溜まっている交通量を表している。
【００４８】
図５を用いて説明した経路の場合、単純に、リンク単位で、上述した「ある車両が渋滞区間を抜けるまでに要する所要時間と、その車両が渋滞末尾に到着した時刻から、その渋滞が解消するまでの時間の合計に等しい」に基づき、動的限界費用を求めようとすると、例えばあるボトルネック・リンクの渋滞が、そのリンクを越えて上流のリンクにまで及んでいると、限界費用が重複して算出されてしまう。
このため、本実施形態において、遅れを伴うリンクが連続する区間については、その区間の最下流のリンクでのみ限界費用、すなわちそのリンクの流入時刻から、渋滞の予測解消時刻までの時間を算出し、その他の渋滞リンクでは、通過所要時間を算出する。この結果、重複をなくし、リンク単位での計算で動的限界費用の近似値を得ることが出来る。
【００４９】
次に、渋滞予測方法について、図６〜図９を用いて説明する。
図６は、本実施形態に係る動的限界費用を説明する図である。図６において、横軸は時間を表し、縦軸はリンク内の車両の移動速度であるリンク旅行速度を表している。破線ｇ３０１は、渋滞判定の閾値を表している。実線ｇ３１１は、時刻０からｔ３０１の期間における時間に対するリンク旅行速度の実測値の変化を表し、破線ｇ３１２は、時刻ｔ３０１以降における時間に対するリンク旅行速度の予測値の変化を表している。また、時刻ｔ３０１は、現在時刻である。
予測旅行時間情報生成装置１０５は、プローブ交通情報であるリアルタイム交通情報を入力として、予測モデルを用いて、現在時刻ｔ３０１以降のリンク旅行速度を予測する。
【００５０】
図６に示すように、予測旅行時間情報生成装置１０５は、リンク旅行速度ｇ３１１が、予め定めた渋滞判定閾値ｇ３０１より小さくなった場合を渋滞とみなす。図６において、予測旅行時間情報生成装置１０５は、現在時刻以降、時刻ｔ３０１から時刻ｔ３０２の期間、渋滞が発生していると判定する。このように、本実施形態では、リンク旅行速度の予測値ｇ３１２が、渋滞判定閾値ｇ３０１未満の場合の期間（ｔ３０１からｔ３０２）を、動的限界費用と定義する。
【００５１】
次に、渋滞しているリンクの判定について、図７を用いて説明する。
図７は、本実施形態に係る渋滞区間を説明する図である。図７において、車両の進行方向をｘ方向、ｘ方向と垂直な方向をｙ方向とする。図７において、符号ｒ４０１は、ｘ方向に延びている道路、符号ｃ４０１からｃ４０４は、道路ｒ４０１と垂直なｙ方向に延びている道路を表している。また、道路ｒ４０１とｃ４０１の交点、道路ｒ４０１とｃ４０２の交点、道路ｒ４０１と道路ｃ４０３の交点及び道路ｒ４０１とｃ４０４の交点は、交差点を表している。
また、図７において、ｘ方向の０からｘ４０２の区間ｌ４０１、ｘ４０２からｘ４０４の区間ｌ４０２及びｘ４０４からｘ４０５の区間ｌ４０３は、各々、信号機と信号機との区間であり、リンクである。
【００５２】
図７に示すように、符号ｇ４０１は、ｘ方向のｘ４０１からｘ４０２の区間、速度低下が発生している区間である。予測旅行時間情報生成装置１０５は、このように速度が低下する区間（以下、速度低下区間という）ｇ４０１が、リンクｌ４０１より短いため、渋滞とはみなさない。
また、図７に示すように、符号ｇ４０２は、ｘ方向のｘ４０３からｘ４０５の区間、速度低下が発生している区間である。予測旅行時間情報生成装置１０５は、このように速度が低下する速度低下区間ｇ４０２が、リンクｌ４０３より長いため、渋滞とみなす。この場合、渋滞と見なされる区間は、リンクｌ４０３のみではなく、リンクｌ４０２も含んでいる。このため、予測旅行時間情報生成装置１０５は、速度低下区間が、複数のリンクを跨ぐ場合、連続している速度低下区間をつなげて１つの速度低下区間とみなす。
なお、旅行速度を予測する単位区間（以下、旅行速度予測の単位区間という）は、信号交差点程度の距離とする。信号交差点程度の距離は、数百ｍ程度であるので、旅行速度予測の単位区間は、信号の１サイクルで滞留している車両量を捌ける滞留長（長くても２００ｍ程度）よりも長い方が望ましい。
例えば、３００ｍ以上の区間が、時速２０ｋｍ未満と予測される場合、予測旅行時間情報生成装置１０５は、渋滞が生じると予測する。区間の長さを３００ｍ以上の場合、車両は、信号の２サイクル以上要して通過できた状態に相当するためであり、信号待ちによる速度低下ではないためである。
【００５３】
次に、ボトルネック・リンクを特定する方法について、図８を用いて説明する。渋滞の終了位置であるボトルネック・リンクが、どこであるかを特定することは単純ではない。このため、本実施形態では、過去の交通量や渋滞データを蓄積しておき、渋滞が起きている箇所を予め抽出しておく。
図８は、本実施形態に係るボトルネック・リンクの特定方法の一例を説明する図である。図８（ａ）は、図７のｘ軸方向ｘ４０３からｘ４０５の区間を示した図である。図８（ｂ）は、図８（ａ）の区間をリンクで示した図である。図８（ａ）において、車両の進行方向をｘ方向、ｘ方向と垂直な方向をｙ方向とする。
図８（ｂ）において、符号ｐ４０２は、図８（ａ）の道路ｒ４０１とｃ４０３との交点であり、符号ｐ４０３は、図８（ａ）の道路ｒ４０１とｃ４０４との交点である。
図８（ｂ）に示したように、点ｐ４０２には、リンクｌ４０２、ｌ４０２−１及びｌ４０２−２の各入力が接続されている。また、点ｐ４０２の出力は、リンクｌ４０３に接続されている。同様に、点ｐ４０３には、リンクｌ４０３、ｌ４０３−１及びｌ４０３−２の各入力が接続されている。また、点ｐ４０３の出力は、リンクｌ４０４に接続されている。
【００５４】
経路案内システム１の予測旅行時間情報生成装置１０５は、例えば、過去一ヶ月から数ヶ月程度の交通量のデータのうち、５分間のリンク旅行速度に関するデータの統計情報処理装置１０４を介して外部情報記憶部１０３から読み出す。なお、５分間のリンク旅行速度データとは、リンク毎に測定された５分間の車両の移動速度データである。
図８（ａ）に示したように、区間ｇ４０１のリンク旅行速度は、１０ｋｍ／ｈ（第１の速度）未満である。このため、予測旅行時間情報生成装置１０５は、道路ｒ４０１においてリンクｌ４０２とｌ４０３の区間では、渋滞が起きていると判別する。一方、道路ｒ４０１のｘ方向のｃ４０４以降の区間ｇ４０２（リンクｌ４０４）において、リンク旅行速度は３０ｋｍ／ｈ（第１の速度）以上である。このため、予測旅行時間情報生成装置１０５は、道路ｒ４０１においてリンクｌ４０４では、渋滞が起きていないと判別する。渋滞がリンクｌ４０２とｌ４０３で起きていてリンクｌ４０４では起きていないため、予測旅行時間情報生成装置１０５は、渋滞が起きているリンクをボトルネック・リンクとし、このリンクに対して１ポイントを加算する。
予測旅行時間情報生成装置１０５は、このようにして、解析したい全てのリンクについて、近接するリンク間の旅行速度データを比較していく。
予測旅行時間情報生成装置１０５は、このようにして、与えたポイントを加算していき、１日あたりのポイントの平均値が、６から１２ポイント程度のリンクを、ボトルネック・リンクとして抽出する。すなわち、予測旅行時間情報生成装置１０５は、このようにして、ボトルネックになっている下流地点を決める。
【００５５】
次に、ボトルネック・リンクの経路への影響度について、図９を用いて説明する。
一般的な道路では、図９のように、複数の道路が従属して接続されている。このため、本実施形態では、１つのボトルネックが、どれくらいの経路に影響するかポイントを与えるかについても重み付けを行う。
本実施形態では、過去の統計データに基づき、平均的な渋滞情報を使って、そのボトルネックに接続されている道路がいくつあるのか、接続されている道路の数を数えることで、影響度を以下のように算出する。
【００５６】
図９のような数本の道路が互いに交差している状態について説明する。
図９は、本実施形態に係るボトルネック・リンクの経路への影響度を説明する図である。
図９において、左右方向をｘ方向、ｘ方向に垂直な方向をｙ方向とする。図９において、符号ｒ５０１、ｒ５０２及びｒ５０３は、ｘ方向に各々平行な道路であり、符号ｃ５０１は、道路ｒ５０１、ｒ５０２及びｒ５０３に垂直な道路である。また、符号ｃ５０２は、道路ｒ５０３と交差し、道路ｒ５０２に合流する道路である。
符号ｌ５０１、ｌ５０２、ｌ５０３及びｌ５０４は、各々ボトルネック・リンクを表している。また、符号ｐ５０１、ｐ５０２、ｐ５０３、ｐ５０４、ｐ５０５、ｐ５０６、ｐ５０７及びｐ５０８は、道路上の点や交差点を表している。
点ｐ５０１は、道路ｒ５０２のｘ軸の負方向の一方端であり、ボトルネック・リンクｌ５０１の流入点である。点ｐ５０２は、道路ｒ５０３のｘ軸の負方向の一方端であり、ボトルネック・リンクｌ５０２の流入点である。点ｐ５０３は、道路ｃ５０２のｙ軸の負方向の一方端であり、ボトルネック・リンクｌ５０３の流入点である。点ｐ５０４は、道路ｃ５０１のｙ軸の負方向の一方端であり、ボトルネック・リンクｌ５０２の流入点である。点ｐ５０５は、道路ｒ５０３と道路ｃ５０２との交点であり、ボトルネック・リンクｌ５０３上の通過点である。点ｐ５０６は、道路ｒ５０３と道路ｃ５０１との交点であり、ボトルネック・リンクｌ５０４上の通過点である。点ｐ５０７は、道路ｒ５０２と道路ｃ５０２との交点であり、道路ｒ５０２と道路ｃ５０２との合流点であり、ボトルネック・リンクｌ５０１、ｌ５０２、ｌ５０３及びｌ５０４上の通過点である。
また、ボトルネック・リンクｌ５０４において、ｙ軸の負方向を下流、ｘ軸の正方向を上流という。
【００５７】
図９に示すように、ボトルネック・リンクｌ５０１は、点ｐ５０１と点ｐ５０７との区間と、点ｐ５０７と点ｐ５０８との区間から構成されている。また、ボトルネック・リンクｌ５０１は、点ｐ５０１から渋滞が始まり、道路ｒ５０２において点ｐ５０１からｘ軸の正方向の点ｐ５０７までのリンク、及び道路ｃ５０１において位置ｐ５０７からｙ軸の正方向の位置ｐ５０８までのリンクで渋滞が継続している。
ボトルネック・リンクｌ５０２は、点ｐ５０２と点ｐ５０５との区間と、点ｐ５０５と点ｐ５０７との区間と、点ｐ５０７と点ｐ５０８との区間とから構成されている。また、ボトルネック・リンクｌ５０２は、点ｐ５０２から渋滞が始まり、道路ｒ５０３において点ｐ５０２からｘ軸の正方向の点ｐ５０５までのリンク、道路ｃ５０２において位置ｐ５０５からｘ軸に対して角度αの方向の位置ｐ５０７までのリンク、道路ｃ５０１において位置ｐ５０７からｙ軸の正方向の位置ｐ５０８までのリンクで渋滞が継続している。
ボトルネック・リンクｌ５０３は、点ｐ５０３と点ｐ５０５との区間と、点ｐ５０５と点ｐ５０７との区間と、点ｐ５０７と点ｐ５０８との区間とから構成されている。また、ボトルネック・リンクｌ５０３は、点ｐ５０３から渋滞が始まり、道路ｃ５０２において点ｐ５０３からｘ軸に対して角度αの方向の点ｐ５０５を介し位置ｐ５０７までの２つのリンク、道路ｃ５０１において位置ｐ５０７からｙ軸の正方向の位置ｐ５０８までのリンクで渋滞が継続している。
ボトルネック・リンクｌ５０４は、点ｐ５０４と点ｐ５０６との区間と、点ｐ５０６と点ｐ５０７との区間と、点ｐ５０７と点ｐ５０８との区間とから構成されている。また、ボトルネック・リンクｌ５０４は、点ｐ５０４から渋滞が始まり、道路ｃ５０１において点ｐ５０４からｙ軸の正方向の点ｐ５０６を介し位置ｐ５０７までの２つのリンク、道路ｃ５０１において位置ｐ５０７からｙ軸の正方向の位置ｐ５０８までのリンクで渋滞が継続している。
【００５８】
予測旅行時間情報生成装置１０５は、図８で説明したように、車両がそのリンクを通過する時点で、各リンクに渋滞が起きているか否かを判別する。具体的には、予測旅行時間情報生成装置１０５は、例えば、過去一ヶ月から数ヶ月程度の交通量のデータのうち、５分間のリンク旅行速度に関するデータを外部情報記憶部１０３から読み出す。予測旅行時間情報生成装置１０５は、リンク旅行速度が、１０ｋｍ／ｈ（第１の速度）未満であるか否かを判定する。
予測旅行時間情報生成装置１０５は、１つのリンクを抽出し、抽出したリンクのリンク旅行速度が１０ｋｍ／ｈ未満であり、そのリンクに下流側で接続するいずれかのリンク旅行速度も１０ｋｍ／ｈ未満の場合、抽出したリンクに１ポイント付与する。なお、ここで用いるポイントは、図８で説明したポイントとは異なる。
予測旅行時間情報生成装置１０５は、このように算出したポイントが、１日あたりの平均で６から１２ポイント程度あるリンクを、ボトルネックからの渋滞に従属しているリンク（末端の道路）と見なす。
【００５９】
具体的には、図９において、点ｐ５０７からｐ５０８が合流地点であり、上流側である。このリンクには、図９で示したように、点ｐ５０１からｐ５０７のリンク、点ｐ５０２から点ｐ５０５を経て点ｐ５０７に接続されるリンク、点ｐ５０３から点ｐ５０５を経て点ｐ５０７に接続されるリンク、及び点ｐ５０４から点ｐ５０６を経て点ｐ５０７に接続される４つのリンクが上流の点ｐ５０７からｐ５０８の区間に接続されている。
そして、パレート改善経路案内装置１０７は、ボトルネック・リンクの上流で従属するリンクのグラフ構造が有している本数を算出する。図９において、ボトルネック・リンクの上流である点ｐ５０７からｐ５０８の区間で従属するリンクは４本であるので、パレート改善経路案内装置１０７は、リンク毎に影響度１を加算し、影響度４であると定義する。影響度が高いことの意味合いは、渋滞率が高いことを意味している。
図９に示した影響度は、プローブから取得したデータに基づいて生成される。このようにして、全てのリンクについて重み付けを行った場合、予測旅行時間情報生成装置１０５は、例えば、１日あたりの平均で６〜１２ポイント程度の重み付けがされたリンクをボトルネック・リンクとして抽出する。なお、車両の移動速度を測定できるセンサーが設置されている場合、パレート改善経路案内装置１０７は、このセンサーが取得した速度データを用いて、同様にボトルネック・リンクを抽出するようにしてもよい。
なお、６ポイントの重み付けがされているリンクは、３０分（５分×６）間、渋滞が継続している道路である可能性がある。同様に、１２ポイントの重み付けがされているリンクは、６０分（５分×１２）間、渋滞が継続している道路である可能性があることを表している。
【００６０】
次に、経路案内システム１の処理手順について、図１０を用いて説明する。図１０は、本実施形態に係る経路案内システム１の処理手順のフローチャートである。
まず、以下で行う処理の概略について説明する。
経路案内システム１は、全車両が最適である経路を探索する。その後、各車両の経路について、経路の１つ１つのリンクについて、別のリンクに行った方がその車両にとってコスト（旅行時間）的にメリットがあり、システム的なコストから見てもメリットがあると判定された場合、その車両に対して推奨経路情報として提示する。
【００６１】
（ステップＳ１０１）プローブ交通情報収集装置１０１は、プローブ車両Ｍ３０が送信するプローブ交通情報ｉ１０を取得する。
次に、プローブ交通情報収集装置１０１は、受信したプローブ交通情報、道路に設置されているセンサーからの交通量情報、過去の交通量情報等を用いて、公知の手法により現在の交通量や車両の旅行速度等を示すリアルタイム交通情報ｉ１１を生成する。プローブ交通情報収集装置１０１は、生成したリアルタイム交通情報ｉ１１を予測旅行時間情報生成装置１０５に出力し、さらに生成したリアルタイム交通情報ｉ１１を交通情報蓄積装置１０２に記憶させる。ステップＳ１０１終了後、ステップＳ１０２に進む。
【００６２】
（ステップＳ１０２）統計情報処理装置１０４は、交通情報蓄積装置１０２にステップＳ１０１で記憶されたリアルタイム交通情報ｉ１１を含む過去に記憶されたリアルタイム交通情報ｉ１２を読み出す。
次に、統計情報処理装置１０４は、外部情報記憶部１０３に記憶されている交通情報ｉ１３を読み出す。
次に、統計情報処理装置１０４は、読み出したリアルタイム交通情報ｉ１２と交通情報ｉ１３とに基づき、予測モデルを生成する。ステップＳ１０２終了後、ステップＳ１０３に進む。
【００６３】
（ステップＳ１０３）予測旅行時間情報生成装置１０５は、プローブ交通情報収集装置１０１が出力するリアルタイム交通情報ｉ１１を、統計情報処理装置１０４が生成した予測モデルを用いて、リンク毎の予測旅行時間情報を生成する。ステップＳ１０３終了後、ステップＳ１０４に進む。
【００６４】
（ステップＳ１０４）予測旅行時間情報生成装置１０５は、図示しない交通情報端末を搭載している車両Ｍ４０が送信する車両の現在経路情報と、車両が走行している目的地情報とを含む情報ｉ１５を取得する。ステップＳ１０４終了後、ステップＳ１０５に進む。
【００６５】
（ステップＳ１０５）予測旅行時間情報生成装置１０５は、取得した現在経路情報と目的地情報に基づき、車両Ｍ４０の現在位置から目的位置までの経路候補情報を公知の手法を用いて生成する。ステップＳ１０５終了後、ステップＳ１０６に進む。
【００６６】
（ステップＳ１０６）予測旅行時間情報生成装置１０５は、ステップＳ１０５において生成した目的地までの経路候補情報と、ステップＳ１０３において生成した予測時間情報とを用いて、上述したように経路候補情報の経路からボトルネック・リンクを抽出する。
具体的には、予測旅行時間情報生成装置１０５は、車両が各リンクに到達する時刻において、図７を用いて説明したように生成した予測時間情報を用いて渋滞区間を抽出し、抽出した区間が３００ｍ以上であり、予め定められている旅行速度（例えば、時速２０ｋｍ）未満と予測される区間を渋滞していると判定する。なお、予測旅行時間情報生成装置１０５は、この判定を、例えば時刻毎に行う。次に、予測旅行時間情報生成装置１０５は、図８を用いて説明したように、１日あたりの平均の付与したポイントが予め定めた値より多いリンク（または区間）をボトルネック・リンクとして抽出する。ステップＳ１０６終了後、ステップＳ１０７に進む。
【００６７】
（ステップＳ１０７）予測旅行時間情報生成装置１０５は、抽出したボトルネック・リンクにおいて、経路上のボトルネック・リンクの渋滞終了予想時刻を、ステップＳ１０３で生成した予測旅行時間情報と、ステップＳ１０５で生成した経路候補情報とを用いて推定する。例えば図５を用いて説明したように、予測旅行時間情報生成装置１０５は、各リンクの経路の累積交通量に対する時間変化のグラフに基づき、ボトルネック・リンクの渋滞終了予想時刻を推定する。予測旅行時間情報生成装置１０５は、推定したボトルネック・リンクの渋滞終了予想時刻、予測旅行時間情報及び生成した経路候補情報を動的限界費用情報生成装置１０６に出力する。ステップＳ１０７終了後、ステップＳ１０８に進む。
【００６８】
（ステップＳ１０８）動的限界費用情報生成装置１０６は、入力されたボトルネック・リンクの渋滞終了予想時刻、予測旅行時間情報及び生成した経路候補情報に基づき、各経路候補における渋滞が発生しているリンクの動的限界費用を算出する。動的限界費用情報生成装置１０６は、算出した各経路候補における渋滞が発生しているリンクの動的限界費用を、パレート改善経路案内装置１０７に出力する。ステップＳ１０８終了後、ステップＳ１０９に進む。
【００６９】
（ステップＳ１０９）パレート改善経路案内装置１０７は、動的限界費用情報生成装置１０６が出力する各経路候補における渋滞が発生しているリンクの動的限界費用及び予測旅行時間に基づき、図９を用いて説明したように、各ボトルネック・リンクの経路候補への影響度を算出する。
次に、パレート改善経路案内装置１０７は、動的限界費用情報生成装置１０６が出力する各経路候補における渋滞が発生しているリンクの動的限界費用及び予測旅行時間に基づき、現在、車両Ｍ４０が通行している経路と、生成した各経路候補の各予測旅行時間と各動的限界費用について、順次算出する。ステップＳ１０９終了後、ステップＳ１１０に進む。
【００７０】
（ステップＳ１１０）次に、パレート改善経路案内装置１０７は、ステップＳ１０９で算出された値を順次比較し、動的限界費用が最小になる経路候補を探索する。
パレート改善経路案内装置１０７は、現在経路の予測旅行時間情報と各経路候補の予測旅行時間情報とを比較し、現在経路の予測旅行時間以下の経路候補を探索する（第１探索）。また、パレート改善経路案内装置１０７は、現在経路の動的限界費用と各経路候補の動的限界費用とを比較し、現在経路の動的限界費用以下の経路候補を探索する（第２探索）。パレート改善経路案内装置１０７は、第１探索及び第２探索を行った結果、最も動的限界費用が小さい経路を、次式（１）を用いて算出する。
【００７１】
ｃｋ（ｔ）＝ａ１Ｔｋ（ｔ）＋ａ２Ｍｋ（ｔ）  ・・・（１）
【００７２】
式（１）において、ｃｋ（ｔ）は、経路候補ｋにおける各時刻ｔのコストである。Ｔｋ（ｔ）は、例えば、プローブ交通情報や、センサーから得られた情報から生成したリンクの通過所要時間（リンク旅行時間）である。Ｍｋ（ｔ）は、次式（２）で算出されるボトルネック・リンクにおける旅行時間である。
【００７３】
Ｍｋ（ｔ）＝（渋滞が解消するまでの時間）×影響度  ・・・（２）
【００７４】
なお、式（２）のＭｋ（ｔ）は、ボトルネック・リンクについてのみ算出する。
また、式（１）において、ａ１、ａ２は、予め定めておく定数である。式（１）において、定数ａ１＝０及び定数ａ２＝１の状態は、利用者最適状態である。また、式（１）において、定数ａ１＝１及び定数ａ２＝０の状態は、システム最適状態である。このため、定数ａ１及びａ２のバランスを取れば、パレート最適状態にできる。
定数ａ１及びａ２のバランスは、例えば、このように生成された経路案内情報を使用している車両がどの位の割合かにより、シミュレーションにより数値計算して実情に応じた割合を算出する。ステップＳ１１０終了後、ステップＳ１１１に進む。
【００７５】
（ステップＳ１１１）次に、パレート改善経路案内装置１０７は、ステップＳ１１０で算出した経路候補の中から、予測旅行時間が現在経路以下であり、且つ動的限界費用が現在経路以下である動的限界費用が最小になる経路候補である推奨経路があるか否かを判定する。推奨経路があると判定した場合（ステップＳ１１１；Ｙｅｓ）、ステップＳ１１２に進む。推奨経路がないと判定した場合（ステップＳ１１１；Ｎｏ）、ステップＳ１１３に進む。
【００７６】
（ステップＳ１１２）推奨経路があると判定した場合（ステップＳ１１１；Ｙｅｓ）、パレート改善経路案内装置１０７は、探索結果である推奨経路情報を、交通情報端末を搭載している車両Ｍ４０に送信する。この場合、車両Ｍ４０の利用者は、例えば、従来技術のカーナビゲーションシステムで探索された利用者最適状態の経路から、経路案内システム１から送信された推奨経路に走行経路を変更する。
【００７７】
（ステップＳ１１３）推奨経路がない判定した場合（ステップＳ１１１；Ｎｏ）、パレート改善経路案内装置１０７は、探索結果を、交通情報端末を搭載している車両Ｍ４０に送信しない。この場合、車両Ｍ４０の利用者は、例えば、従来技術のカーナビゲーションシステムで探索された利用者最適状態の経路の走行を継続する。
【００７８】
従来技術のカーナビゲーションシステムによるコスト計算では、式（１）においてＴｋ（ｔ）の項のみ算出していた。しかし、本実施形態では、式（１）において２項目Ｍｋ（ｔ）のボトルネック・リンクに対する動的限界費用を追加して計算することに差異がある。また、本実施形態では、従来技術と同様に、旅行時間をベースに、ボトルリンクによる動的限界費用も加味している。
すなわち、本実施形態では、自車両がこの経路を選択した場合に、他の車両に対してどの程度、影響があるかを加味していることになる。
【００７９】
次に、本実施形態に係る経路案内システム１の効果の一例を、図１１から図１４を用いて説明する。
図１１は、本実施形態に係る経路案内システム１において、シミュレーションに用いた地図である。図１１において、左右方向をｘ方向、ｘ方向に垂直な方向をｙ方向とする。図１１に示したエリアは、ｘ方向が１０ｋｍの長さであり、ｙ方向が２０ｋｍの長さであり、このエリア内における道路のリンク数は７６００ある。また、車両の交通量は、３時間で２７万台である。
【００８０】
図１２は、図１１に示したエリアで本実施形態に係る経路案内システム１をシミュレーションした結果である。
図１２において、符号ｇ６０１で示した行は、利用者最適状態（ＤＵＯ）７５％の経路案内から、経路案内システム１が提示した推奨経路（ＤＰＯ）に変更した車両数と、システム最適状態（ＤＳＯ）における車両数を表している。符号ｇ６０２で示した行は、ＤＵＯ７５％の経路案内から、経路案内システム１が提示した推奨経路に変更した車両数の全台数に対する割合と、ＤＳＯにおける車両数の全台数に対する割合を表している。
符号ｇ６０３で示した行は、ＤＵＯ７５％、ＤＰＯ及びＤＳＯの各状態における総旅行時間（＝台数×走行時間）を表している。
【００８１】
符号ｇ６０４で示した行は、ＤＵＯ７５％における総旅行時間とＤＰＯにおける総旅行時間との差及びＤＵＯ７５％における総旅行時間とＤＳＯにおける総旅行時間との差が、ＤＵＯ７５％における総旅行時間の何％であるかを表している。
符号ｇ６０５で示した行は、ＤＵＯ７５％の経路案内から、経路案内システム１が提示したＤＰＯに変更した車両において１台あたりの削減された総旅行時間と、ＤＵＯ７５％の経路案内から、ＤＳＯに変更した車両において１台あたりの削減された総旅行時間とを表している。
符号ｇ６０６で示した行は、ＤＵＯ７５％、ＤＰＯ及びＤＳＯの各状態における３時間あたりのＣＯ２の総排出量を表している。
符号ｇ６０７で示した行は、ＤＵＯ７５％のＣＯ２排出量に対するＤＰＯのＣＯ２排出量の削減率、ＤＵＯ７５％のＣＯ２排出量に対するＤＳＯのＣＯ２排出量の削減率を表している。
【００８２】
ＤＵＯ７５％を比較対象としている理由は、利用者最適状態において、カーナビゲーションを搭載している車両が、例えば１００％（ＤＵＯ１００％）に設定した場合、全ての車両がカーナビゲーションによって提示された最適気経路に向かってしまう。カーナビゲーションを搭載している車両が、例えば１００％（ＤＵＯ１００％）に設定した場合についてシミュレーションを行った結果、効率は悪化した。シミュレーションの結果、ＤＵＯ７５％の状態が、本実施形態の経路案内システム１や、ＤＳＯを用いない場合に一番効率がよかったため、ＤＵＯ７５％の状態を比較値に設定した。
【００８３】
図１２に示したように、ＤＵＯ７５％の状態から、経路を変更した車両はＤＰＯ（本実施形態）の場合、１．７％、ＤＳＯの場合、２．４％であった（行ｇ６０１、ｇ６０２）。台数ではＤＳＯの方が、ＤＵＯ７５％から経路変更している車両数が多い。
しかしながら、総旅行時間について比較すると、変更した車両あたりの削減された旅行時間は、ＤＰＯの方が多い（行ｇ６０３〜ｇ６０５）。
さらに、ＤＵＯ７５％に対するＤＰＯのＣＯ２削減量は、０．９８％である。
以上のように、本実施形態に係る経路案内システム１では、利用者最適状態から経路を変更した場合、旅行時間も削減でき、これによりＣＯ２の排気量も削減できることを示唆している。
【００８４】
図１３は、システム最適状態における経路変更有り場合の車両台数と旅行時間変化を表す図である。なお、経路変更なしの場合の車両では、カーナビゲーションシステムが設定した利用者最適状態の経路が選択されている。
図１３において、横軸は旅行時間の変化時間を表し、横軸の真ん中０秒が、旅行時間が変化しなかったことを意味している。また、図１３において、縦軸は車両台数を表している。
図１３に示すように、経路変更有りの場合、旅行時間０秒に対して、ほぼ左右対称かつ正規分布状に旅行時間の変化が分散している。この場合、図１３に示すように、利用者最適状態の場合と比較して、３００秒も旅行時間が短縮された利用者がいる反面、３００秒も旅行時間が増加した利用者がいる。さらに、破線長丸ｇ７０１で示したように、旅行時間が増加した利用者は、１０００人以上いることを表している。
【００８５】
図１４は、本実施形態に係るパレート最適状態における経路変更有り場合の車両台数と旅行時間変化を表す図である。なお、経路変更なしの場合の車両では、カーナビゲーションシステムが設定した利用者最適状態の経路が選択されている。
図１４において、横軸は旅行時間の変化時間を表し、横軸の真ん中０秒が、旅行時間が変化しなかったことを意味している。また、図１４において、縦軸は車両台数を表している。
図１４の破線長丸ｇ７０２に示すように、図１３とは大きく異なり、旅行時間が増加している利用者は、数百人程度であることを表している。一方、旅行時間が短縮された利用者は、システム最適状態と同等である。すなわち、本実施形態の経路案内システム１によれば、経路変更した利用者にとって、旅行時間が現状のままであるか、短縮する場合がほとんどであり、旅行時間が増加する場合は少ないことを表している。
【００８６】
以上のように、本実施形態の経路案内システム１において、動的限界費用情報生成装置１０６は、渋滞が起きるリンク区間を示す情報と渋滞が終了する時刻を示す情報とに基づき、現在経路及び経路候補の各動的限界費用を算出する。そして、パレート改善経路案内装置１０７は、各経路候補の各予測旅行時間及び各動的限界費用に基づき、現在経路及び各経路候補の各予測旅行時間及び各動的限界費用について比較し、比較の結果、動的限界費用が最小になる経路候補を探索する。
この結果、利用者にとって経路が最短の利用者最適状態よりコストを軽減し、さらに経路案内システム１にとってコストが最も安いシステム最適状態より利用者の旅行時間の増加を軽減できる交通渋滞緩和の効率を向上することができる。
【００８７】
また、本実施形態では、動的限界費用の算出において、以下のような処理を行うようにした。
予測旅行時間情報生成装置１０５は、現在経路上及び前記経路候補上の全てのリンクから１つのリンクを抽出し、抽出したリンクにおける車両の目的地までの到着時間までの将来における移動速度が予め定められている第１の速度未満であると判定した場合、抽出したリンクを渋滞が起きるリンクであると予測するようにした。
また、予測旅行時間情報生成装置１０５は、渋滞が起きるリンクを示す情報に基づき、渋滞が終了するボトルネック・リンクを抽出し、抽出したボトルネック・リンクにおいて、現在経路上及び経路候補上のボトルネック・リンクの渋滞が終了する時刻を、リンク毎の予測旅行時間情報及び現在経路情報及び経路候補情報を用いて推定するようにした。
また、予測旅行時間情報生成装置１０５は、渋滞が起きるリンクの下流に接続されている全てのリンクにおける車両の目的地までの到着時間までの将来における移動速度が予め定められている第２の速度以上であると判定した場合、渋滞が起きるリンクに重み付けを行い、渋滞が起きるリンクの重みを示す値が、予め定められている値より大きい場合、渋滞が起きるリンクをボトルネック・リンクとして抽出するようにした。
また、パレート改善経路案内装置１０７は、ボトルネック・リンクの上流側に従属しているリンクのグラフ構造における末端数に基づき、ボトルネック・リンクの影響度を算出し、算出した前記影響度を用いて動的限界費用を算出するようにした。
この結果、本実施形態では、渋滞が終了するリンクであるボトルネック・リンクを特定でき、さらにボトルネック・リンクの経路への影響度を算出して動的限界費用の算出を行うようにしたので、利用者最適状態やシステム最適状態よりコスト的に利用者に好適な交通渋滞緩和の効率を向上することができる。
【００８８】
なお、本実施形態では、プローブ車両から送信される交通情報を用いる例を説明したが、例えば、図示しないセンサーが車両の移動速度情報も収集して、プローブ交通情報収集装置１０１に送信するようにしてもよい。
【符号の説明】
【００８９】
１・・・経路案内システム、１０１・・・プローブ交通情報収集装置、１０２・・・交通情報蓄積装置、１０３・・・外部情報記憶部、１０４・・・統計情報処理装置、１０５・・・予測旅行時間情報生成装置、１０６・・・動的限界費用情報生成装置、１０７・・・パレート改善経路案内装置、ｌ２０１〜ｌ２０６、ｌ４０１〜ｌ４０４、ｌ５０１〜ｌ５０４・・・リンク、Ｍ３０・・・プローブ車両
【図１】
2013057544.tif 000003
【図２】
2013057544.tif 000004
【図３】
2013057544.tif 000005
【図４】
2013057544.tif 000006
【図５】
2013057544.tif 000007
【図６】
2013057544.tif 000008
【図７】
2013057544.tif 000009
【図８】
2013057544.tif 000010
【図９】
2013057544.tif 000011
【図１０】
2013057544.tif 000012
【図１１】
2013057544.tif 000013
【図１２】
2013057544.tif 000014
【図１３】
2013057544.tif 000015
【図１４】
2013057544.tif 000016