"予め定められている区間であるリンクを車両が通過するために要する第1の通過予測時間を前記車両の移動速度に基づき算出し、算出した前記第1の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第2の通過予測時間を算出し、算出した前記第2の通過予測時間に基づき、前記経路を選択することを特徴とする経路案内装置。前記車両の移動速度を含む交通情報を取得する交通情報収集部と、前記経路上のリンクを抽出し、前記車両の移動速度に基づき前記車両が目的位置に到着する時刻までに渋滞が起きているリンクを抽出し、前記車両の移動速度に基づき前記渋滞が起きているリンクを前記車両が通過するのに要する第1の通過予測時間を生成する予測時間情報生成部と、を備えることを特徴とする請求項1に記載の経路案内装置。前記車両の現在の走行位置から目的位置までの経路候補を示す経路候補情報を生成する経路候補情報生成部と、前記経路候補で前記車両が目的位置に到着する時刻までに渋滞が起きているリンクに対する前記第1の通過予測時間に基づき第1の動的限界費用を算出する動的限界費用情報生成部と、前記経路候補において前記渋滞が起きていないリンクを前記車両が通過するために要する通過予測時間に基づき第2の動的限界費用を算出し、前記経路候補の全てのリンクについて、前記第2の動的限界費用と前記動的限界費用情報生成部が算出した第1の動的限界費用とを前記経路候補毎に合計し、前記合計した動的限界費用を比較し、比較の結果、前記合計した動的限界費用が最小になる前記経路候補を探索するパレート改善経路案内部と、を備えることを特徴とする請求項1または請求項2に記載の経路案内装置。前記予測時間情報生成部は、前記経路候補上の全てのリンクから1つのリンクを抽出し、前記抽出したリンクにおける前記車両が前記目的位置に到着する時刻までの移動速度が予め定められている第1の速度未満であると判定した場合、前記抽出したリンクを前記車両が前記目的位置に到着する時刻までに渋滞が起きているリンクであると予測することを特徴とする請求項1から請求項3のいずれか1項に記載の経路案内装置。前記予測時間情報生成部は、前記渋滞が起きるリンクを示す情報に基づき、前記渋滞が終了するリンクをボトルネックリンクとして抽出し、抽出した前記ボトルネックリンクにおいて、前記経路候補上の前記ボトルネックリンクの渋滞が終了する時刻を、前記リンク毎の前記車両の移動速度と前記経路候補情報を用いて推定することを特徴とする請求項1から請求項4のいずれか1項に記載の経路案内装置。前記予測時間情報生成部は、前記渋滞が起きるリンクの下流に接続されている全てのリンクにおいて、前記接続されているリンクに到達する時刻の前記車両の移動速度が予め定められている第2の速度以上であると判定した場合、前記渋滞が起きているリンクに重み付けを行い、前記渋滞が起きているリンクの重みを示す値が、予め定められている値より大きい場合、前記渋滞が起きているリンクをボトルネックリンクとして抽出することを特徴とする請求項1から請求項5のいずれか1項に記載の経路案内装置。前記予測時間情報生成部は、前記渋滞が起きているリンクを示す情報及び前記車両の移動速度に基づき、予め定められている時速未満の前記リンクが連続している場合、1つの連続した渋滞が起きているリンクと判定することを特徴とする請求項1から請求項6のいずれか1項に記載の経路案内装置。前記パレート改善経路案内部は、前記ボトルネックリンクの上流側に従属しているリンクのグラフ構造における末端数に基づき、前記ボトルネックリンクの影響度を算出し、算出した前記影響度を用いて前記動的限界費用を算出することを特徴とする請求項3から請求項7のいずれか1項に記載の経路案内装置。前記パレート改善経路案内部は、前記車両が現在選択している前記現在位置から前記目標位置までの経路である現在経路における前記リンク費用の合計を算出し、前記選択した経路候補の前記リンク費用の合計と比較し、前記選択した経路候補の前記リンク費用の合計が前記現在経路における前記リンク費用の合計より小さい場合、前記選択した経路候補を前記経路として決定することを特徴とする請求項3から請求項8のいずれか1項に経路案内装置。経路案内装置における経路案内方法であって、予め定められている区間であるリンクを車両が通過するために要する第1の通過予測時間を前記車両の移動速度に基づき算出する手段と、算出した前記第1の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第2の通過予測時間を算出する手段と、算出した前記第2の通過予測時間に基づき、前記経路を選択する手段と、を含むことを特徴とする経路案内方法。経路案内装置における経路案内方法の処理をコンピューターに実行させるための経路案内プログラムであって、予め定められている区間であるリンクを車両が通過するために要する第1の通過予測時間を前記車両の移動速度に基づき算出する手順と、算出した前記第1の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第2の通過予測時間を算出する手段と、算出した前記第2の通過予測時間に基づき、前記経路を選択する手段と、をコンピューターに実行させるための経路案内プログラム。しかしながら、プローブ交通情報を提供する車両や、プローブ交通情報を利用する車両が増えた場合、従来のカーナビゲーションシステムと同様に最適なルートを車両に提供してしまうと、最適ルートに車両が集中してしまい交通渋滞を緩和できないという問題点があった。本発明は、上記の問題点に鑑みてなされたものであって、交通渋滞を緩和できる交通状況の経路案内装置、経路案内方法及び経路案内プログラムを提供することを目的としている。上記目的を達成するため、本発明に係る経路案内装置は、予め定められている区間であるリンクを車両が通過するために要する第1の通過予測時間を前記車両の移動速度に基づき算出し、算出した前記第1の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第2の通過予測時間を算出し、算出した前記第2の通過予測時間に基づき、前記経路を選択することを特徴としている。なお、本発明において、第1の通過予測時間とは、車両がリンクを通過するために要すると予測される時間である。また、第2の通過予測時間とは、現在の走行位置から目標位置までの経路を車両が通過するために要すると予測される時間である。すなわち、本発明は、経路案内装置が、経路ではなく、リンクの第1の通過予測時間を用いて、経路候補を探索することに特徴がある。また、本発明の経路案内装置において、前記車両の移動速度を含む交通情報を取得する交通情報収集部と、前記経路上のリンクを抽出し、前記車両の移動速度に基づき前記車両が目的位置に到着する時刻までに渋滞が起きているリンクを抽出し、前記車両の移動速度に基づき前記渋滞が起きているリンクを前記車両が通過するのに要する第1の通過予測時間を生成する予測時間情報生成部と、を備えるようにしてもよい。また、本発明の経路案内装置において、前記車両の現在の走行位置から目的位置までの経路候補を示す経路候補情報を生成する経路候補情報生成部と、前記経路候補で前記車両が目的位置に到着する時刻までに渋滞が起きているリンクに対する前記第1の通過予測時間に基づき第1の動的限界費用を算出する動的限界費用情報生成部と、前記経路候補において前記渋滞が起きていないリンクを前記車両が通過するために要する通過予測時間に基づき第2の動的限界費用を算出し、前記経路候補の全てのリンクについて、前記第2の動的限界費用と前記動的限界費用情報生成部が算出した第1の動的限界費用とを前記経路候補毎に合計し、前記合計した動的限界費用を比較し、比較の結果、前記合計した動的限界費用が最小になる前記経路候補を探索するパレート改善経路案内部と、を備えるようにしてもよい。なお、本発明において、リンクの動的限界費用とは、あるリンクを1台の車両が選択したこともしくはしなかったことによる総費用の増加分減少分を意味している。また、第1の動的限界費用とは、経路候補で車両が目的位置に到着する時刻までに渋滞が起きているリンクに対する動的限界費用である。また、第2の動的限界費用とは、渋滞が起きていないリンクに対する動的限界費用である。また、限界費用とは、一般的に生産1単位あたりにかかる費用であり、本発明では、経路間の移動にかかる1単位毎の費用である。すなわち、本発明は、パレート改善経路案内部が、経路ではなく、リンクの動的限界費用を用いて、経路候補を探索することに特徴がある。また、本発明の経路案内装置において、前記予測時間情報生成部は、前記経路候補上の全てのリンクから1つのリンクを抽出し、前記抽出したリンクにおける前記車両が前記目的位置に到着する時刻までの移動速度が予め定められている第1の速度未満であると判定した場合、前記抽出したリンクを前記車両が前記目的位置に到着する時刻までに渋滞が起きているリンクであると予測するようにしてもよい。また、本発明の経路案内装置において、前記予測時間情報生成部は、前記渋滞が起きるリンクを示す情報に基づき、前記渋滞が終了するリンクをボトルネックリンクとして抽出し、抽出した前記ボトルネックリンクにおいて、前記経路候補上の前記ボトルネックリンクの渋滞が終了する時刻を、前記リンク毎の前記車両の移動速度と前記経路候補情報を用いて推定するようにしてもよい。また、本発明の経路案内装置において、前記予測時間情報生成部は、前記渋滞が起きるリンクの下流に従属されている全てのリンクにおいて、前記従属されているリンクに到達する時刻の車両の移動速度が予め定められている第2の速度以上であると判定した場合、前記渋滞が起きているリンクに重み付けを行い、前記渋滞が起きているリンクの重みを示す値が、予め定められている値より大きい場合、前記渋滞が起きているリンクをボトルネックリンクとして抽出するようにしてもよい。また、本発明の経路案内装置において、前記予測時間情報生成部は、前記渋滞が起きているリンクを示す情報及び前記車両の移動速度に基づき、予め定められている時速未満の前記リンクが連続している場合、1つの連続した渋滞が起きているリンクと判定するようにしてもよい。また、本発明の経路案内装置において、前記パレート改善経路案内部は、前記ボトルネックリンクの上流側に従属しているリンクのグラフ構造における末端数に基づき、前記ボトルネックリンクの影響度を算出し、算出した前記影響度を用いて前記動的限界費用を算出するようにしてもよい。また、本発明の経路案内装置において、前記パレート改善経路案内部は、車両が現在選択している前記現在位置から前記目標位置までの経路である現在経路における前記リンク費用の合計を算出し、前記選択した経路候補の前記リンク費用の合計と比較し、前記選択した経路候補の前記リンク費用の合計が前記現在経路における前記リンク費用の合計より小さい場合、前記選択した経路候補を前記経路として決定するようにしてもよい。上記目的を達成するため、本発明は、経路案内装置における経路案内方法であって、予め定められている区間であるリンクを車両が通過するために要する第1の通過予測時間を前記車両の移動速度に基づき算出する手段と、算出した前記第1の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第2の通過予測時間を算出する手段と、算出した前記第2の通過予測時間に基づき、前記経路を選択する手段と、を含むことを特徴としている。上記目的を達成するため、本発明は、経路案内装置における経路案内方法の処理をコンピューターに実行させるための経路案内プログラムであって、予め定められている区間であるリンクを車両が通過するために要する第1の通過予測時間を前記車両の移動速度に基づき算出する手順と、算出した前記第1の通過予測時間に基づき現在の走行位置から目標位置までの経路を前記車両が通過するために要する第2の通過予測時間を算出する手段と、算出した前記第2の通過予測時間に基づき、前記経路を選択する手段と、をコンピューターに実行させることを特徴としている。本発明に係る経路案内装置は、車両がリンクを通過するために要すると予測される時間第1の通過予測時間を算出する。次に、本発明に係る経路案内装置は、算出した第1の通過予測時間に基づいて、現在の走行位置から目標位置までの経路を車両が通過するために要すると予測される時間第2の通過予測時間を算出し、算出した第2の通過予測時間に基づいて経路を選択するようにした。この結果、本発明に係る経路案内装置は、利用者にとって経路が最短の利用者最適状態における移動時間より移動時間を軽減し、さらに経路案内装置を利用している利用者の合計移動時間が最も少ないシステム最適状態において生じる利用者の旅行時間の増加を軽減できるパレート最適状態の交通渋滞緩和することができる。最初に、本発明の概要を説明する。本発明に係る経路案内システムは、後述するパレート最適状態における限界費用を算出する。また、本発明に係る経路案内システムは、経路の限界費用を算出するのではなく、後述するリンクの限界費用を算出するようにしたことに特徴がある。なお、限界費用とは、一般的に生産1単位あたりにかかる費用であり、本発明では、経路間の移動にかかる1単位毎の費用である。そして、本発明に係る経路案内システムは、このリンクの限界費用に基づき、パレート最適状態となる各車両の経路を生成して、各車両に提供する。以下、図面を用いて、本発明の実施形態について説明する。まず、本発明の概要について説明する。図1は、本実施形態に係る経路案内システムのフレームワークを説明する図である。図1において、符号terは、経路案内システム1を利用している車両の集まりを表している。車両M1-1からM1-4は、プローブProbe車両を表している。なお、プローブ車両とは、車両の走行データ速度情報、位置情報、時間情報などを取得して送信する装置を搭載している車両である。この装置が取得したデータをプローブ交通情報といい、プローブ車両は、取得したプローブ交通情報をプローブ交通情報システムSys1プローブ送信センターともいうに送信する。車両M10-1からM10-16は、プローブ車両以外の経路案内システム1を利用している車両を表している。車両M20-1からM20-4は、経路案内システム1を利用していない車両を表している。情報i1からi4は、各プローブ車両M1-1からM1-4からプローブ交通情報システムSys1に送信される情報を表している。情報i5は、情報i1からi4を模式的に表している。情報i6は、プローブ交通情報システムSys1からリアルタイム渋滞予測システムSys2に送信される情報を表している。情報i7は、リアルタイム渋滞予測システムSys2から環境改善パレート経路案内システムSys3に送信される情報を表している。情報i8は、環境改善パレート経路案内システムSys3から経路案内システム1を利用している車両に送信される情報を表している。プローブ車両M1-1からM1-4及びプローブ交通情報システムSys1は、交通状況の変化を即時かつ詳細に捉える、センサーの役割を果たす。リアルタイム渋滞予測システムSys2は、現在の状況から予測しうる将来の状況情報予測旅行時間情報と称するを生成する。リアルタイム渋滞予測システムSys2は、生成した予測旅行時間情報に基づき、環境改善パレート経路案内システムSys3が行う演算に必要な動的限界費用DMC情報を求める。環境改善パレート経路案内システムSys3は、リアルタイム渋滞予測システムSys2が生成した予測旅行時間情報と動的限界費用情報に基づき、パレート最適状態の経路案内情報を生成し、生成した経路案内情報を車両M1-1~M1-4、M10-1~M10-16に送信する。このプローブ交通情報システムSys1、リアルタイム渋滞予測システムSys2、環境改善パレート経路案内システムSys3、車両M1-1~M1-4、M10-1~M10-16は、オープンループ系を構成している。なお、本実施形態における経路の動的な限界費用とは、ある経路を1台の車両が選択したこともしくはしなかったことによる総費用の増加分減少分を意味している。ここでパレート最適状態の概念について、図2を用いて説明する。図2は、パラドックスがある静的配分問題での利用者均衡状態、パレート最適状態、システム最適状態を説明する図である。なお、パレート最適状態とは、他車の旅行時間を増加させることなく、自車の旅行時間をこれ以上短縮することが出来ない状態である。このような状態は、ある条件下で、経路間の等費用原則が成立している利用者均衡状態よりも社会的に小さい費用が達成されることが知られている。また、システム最適状態とは、経路上の総費用が最小になる、システムから見た場合に最適な状態である。また、利用者均衡状態とは、全てのネットワーク利用者に対して、費用が均等になるような状態である。図2では、経路をネットワークとして表している。符号p1からp4は、各々、点を表している。また、符号l12、l13、l23、l24及びl34は、各々、リンクを表している。符号l12は、点1から点2へのリンク12を表し、符号l24は、点2から点4へのリンク24を表している。符号l13は、点1から点3へのリンク13を表し、符号l34は、点3から点4へのリンク34を表している。符号l23は、点2から点3へのリンク23を表している。図2aから図2dに示した例では、点p1からp4に移動する場合、経路は以下の3つある。第1の経路は、最初にリンク12l12を通り、次にリンク24l24を経る経路124である。第2の経路は、最初にリンク13l13を通り、次にリンク34l34を経る経路134である。第3の経路は、最初にリンク12l12を通り、次にリンク23l23を経て、最後にリンク34l34を経る経路1234である。図2aは、サービス水準と限界費用を説明する図である。図2aにおいて、リンク12l12とリンク34l34は、サービス水準が高く、限界費用が大きいリンクである。リンク13l13とリンク24l24は、サービス水準が低く、限界費用が小さいリンクである。リンク23l23は、限界費用が大きいリンク12l12とリンク34l34をつなぐ限界費用の小さなリンクである。なお、限界費用とは、図2のようなネットワークにおいて経路間の移動にかかる1単位毎の費用である。また、図2aにおいて、符号x12は、リンク12l12の費用を表し、符号x24は、リンク24l24の費用を表している。符号x13は、リンク13l13の費用を表し、符号x34は、リンク34l34の費用を表している。符号x23は、リンク23l23の費用を表している。リンク12l12の費用10x12のうちx12に乗じられている10は、限界費用の大きさを表している。リンク23l23の費用x1350のうちx13に加算されている50は、サービス水準の大きさを表している。また、図2aにおいて、各リンクの費用は、リンク12の費用が10x12であり、リンク13の費用がx1350であり、リンク23の費用がx2310であり、リンク24の費用がx2450であり、リンク34の費用が10x34である。図2bは、利用者均衡状態の例を説明する図である。図2bの状態は、経路124の経路の費用以下、経路費用という10x12=4x24=250=92と、経路134の経路費用x13=25010x34=4=92と、経路1234の経路費用10x12=4x23=21010x34=4=92とが均衡、すなわち一致している状態である。このため、図2bにおける総費用は、92×3=276である。図2cは、システム最適状態の例を説明する図である。図2cの状態の各費用は、経路124の経路費用10x12=3x24=350=83、経路134の経路費用x13=35010x34=3=83、経路1234の経路費用10x12=3x23=01010x34=3=70である。従って、図2cのシステム最適状態の総費用236=838370は、図2bの利用者均衡状態の総費用276より安い。図2dは、パレート最適状態の例を説明する図である。図2dの状態の各費用は、経路124の経路の費用の合計10x12=3.5x24=2.550=87.5、経路134の経路の費用の合計x13=2.55010x34=3.5=83、経路1234の経路の費用の合計10x12=3.5x23=1.01010x34=3.5である。従って、図2dのパレート最適状態の総費用256は、図2cのシステム最適状態の総費用236より高く、図2bの利用者均衡状態の総費用276より安い。一般的な経路案内システムでは、経路案内システムを利用している全ての車両に対して、図2bに示したような利用者均衡状態である最適なルートを提供していた。このような利用者均衡状態の場合、最適ルートに車両が集中してしまい交通渋滞緩和できないという課題があった。利用者均衡状態は、図2bで説明したように、経路費用、及び総費用は、パレート最適状態、及びシステム最適状態より大きい。交通渋滞を緩和するため、仮に経路案内システムにとっての最適なシステム最適状態である経路以下、システム最適経路というを導入した場合について説明する。システム最適状態において、経路案内システムは、全ての車両を最適なルートに誘導するのではなく、最適なルートに車両が集中するのを防ぐために、一部の車両に対して迂回を強いるルートに誘導する。この場合、迂回を強いられた車両のドライバーは、不利益を被ることになるので、このようなルートの経路案内を受け入れ難い。しかしながら、図2dで説明したように、経路費用、及び総費用は、利用者均衡状態のものより小さくなる。一方、図2cで説明したように、パレート最適状態は、経路費用、及び総費用=81が利用者均衡状態のものより安くなり、一部の利用者経路1234の経路費用が、システム最適状態の経路124及び経路134の経路費用=83より安くなっている。このため、本実施形態に係る経路案内システムは、最適ルートに車両が集中しないようにして交通渋滞緩和の効率を悪化させず、且つドライバーに不利にならない経路案内であるパレート最適状態の経路案内を行う。次に、経路案内システム1の構成を、図3を用いて説明する。図3は、本実施形態に係る経路案内システム1の概略構成図である。図3に示したように、経路案内システム1は、プローブ交通情報収集装置101、交通情報蓄積装置102、外部情報記憶部103、統計情報処理装置104、予測旅行時間情報生成装置105、動的限界費用情報生成装置106、及びパレート改善経路案内装置107を備えている。プローブ交通情報収集装置101交通情報収集部は、プローブ車両M30が送信するプローブ交通情報i10を取得する。プローブ交通情報収集装置101は、受信したプローブ交通情報i10、道路に設置されているセンサーからの交通量情報、過去の交通量情報等を用いて、公知の手法により現在の交通量や車両の旅行速度等を示すリアルタイム交通情報i11を生成する。交通量情報とは、車両の位置、移動速度、現在時刻などの情報である。プローブ交通情報収集装置101は、生成したリアルタイム交通情報i11を予測旅行時間情報生成装置105に出力し、さらに生成したリアルタイム交通情報i11を交通情報蓄積装置102に記憶させる。交通情報蓄積装置102には、各時刻のリアルタイム交通情報i11が記憶されている。外部情報記憶部103には、センサーから取得した交通量情報、過去の統計的な交通量情報、及び道路に設置されているセンサーから送信された情報に基づいて生成された交通情報が記憶されている。統計情報処理装置104は、交通情報蓄積装置102に記憶されているリアルタイム交通情報i12を読み出す。統計情報処理装置104は、外部情報記憶部103に記憶されている交通情報i13を読み出す。統計情報処理装置104は、読み出したリアルタイム交通情報i12と交通情報i13とに基づき、予測モデルを生成する。なお、予測モデルとは、現在時間を基準とした直前の旅行時間の変動データを入力として、現在時間を基準とした将来の旅行時間の変動情報を出力する予測モデルである。予測モデルは、読み出したリアルタイム交通情報i12と交通情報i13の統計データから学習させた旅行時間情報の変動特性を示すものである。なお、変動特性とは、例えば、直前に入力されたデータとその後の出力とを回帰分析することで、入力に対する出力の関係を示す特性である。そして、この生成された予測モデルは、予測旅行時間情報生成装置105がリアルタイム交通情報を入力現在時間を基準とした過去の情報として、予測旅行時間情報を出力現在時間を基準とした将来の情報として生成する際に使用される。なお、交通情報蓄積装置102及び外部情報記憶部103には、例えば、各々1週間分の情報が蓄積されている。そして、統計情報処理装置104は、例えば、一週間に一回の周期で、交通情報蓄積装置102及び外部情報記憶部103に蓄積されている各情報を読み出して、上述した予測モデルを生成し、生成した予測モデルを示す情報i14を予測旅行時間情報生成装置105に出力する。予測旅行時間情報生成装置105経路候補情報生成部、予測時間情報生成部は、プローブ交通情報収集装置101が生成したリアルタイム交通情報i11を、統計情報処理装置104が生成した予測モデルを用いて、リンク毎の予測旅行時間情報第1の通過予測時間を生成する。予測旅行時間情報生成装置105は、図示しない交通情報端末を搭載している車両M40が送信する車両が、現在、走行している経路情報以下、現在経路情報というと、車両が走行している目的地情報とを含む情報i15を取得する。予測旅行時間情報生成装置105は、取得した現在経路情報と目的地情報に基づき、車両M40の現在位置から目的位置までの経路候補情報を公知の手法を用いて生成する。予測旅行時間情報生成装置105は、生成した予測旅行時間情報と、生成した目的地までの経路候補情報と、プローブ交通情報収集装置101が出力するリアルタイム交通情報i11と、統計情報処理装置104が生成した予測モデルとを用いて、後述するように経路候補情報の経路からボトルネックリンクを抽出する。なお、ボトルネックリンクについては、後述する。予測旅行時間情報生成装置105は、抽出したボトルネックリンクにおいて、経路上のボトルネックリンクの渋滞が終了する時刻以下、渋滞終了予想時刻というを、予測旅行時間情報と経路候補情報とを用いて推定する。予測旅行時間情報生成装置105は、生成した予測旅行時間情報及び推定した経路候補情報を動的限界費用情報生成装置106に出力する。なお、予測旅行時間情報生成装置105は、プローブ交通情報収集装置101が出力するリアルタイム交通情報i11を、統計情報処理装置104が生成した予測モデルを用いて、例えば、5分周期でリンク毎の予測旅行時間情報を生成する。予測旅行時間情報生成装置105が予測旅行時間情報を生成する周期は、例えば、予測する時間帯、季節、場所などに応じて選択するようにしてもよい。動的限界費用情報生成装置106動的限界費用情報生成部は、リンク毎の予測旅行時間情報と、経路候補情報、渋滞終了予想時刻、ボトルネックリンクを用いて、後述するように各経路の動的限界費用を算出する。動的限界費用情報生成装置106は、入力された経路候補情報、動的限界費用を示す情報及び予測旅行時間情報i16、算出した各経路の動的限界費用に基づき、各経路候補の予測旅行時間第2の通過予測時間及び動的限界費用を算出する。動的限界費用情報生成装置106は、算出した各経路候補の予測旅行時間及び動的限界費用を含む情報i17をパレート改善経路案内装置107に出力する。パレート改善経路案内装置107パレート改善経路案内部は、動的限界費用情報生成装置106が出力する各経路候補の予測旅行時間及び動的限界費用に基づき、後述するように各ボトルネックリンクの経路候補への影響度を算出する。パレート改善経路案内装置107は、動的限界費用情報生成装置106が出力する各経路候補の予測旅行時間及び動的限界費用に基づき、現在、車両M40が通行している経路と、生成した各経路候補の各予測旅行時間と各動的限界費用について、順次比較する。パレート改善経路案内装置107は、後述するように動的限界費用が最小になる経路候補を探索する。パレート改善経路案内装置107は、算出した経路候補の中から、予測旅行時間が現在経路以下であり、且つ動的限界費用が現在経路以下である動的限界費用が最小になる経路候補を探索する。パレート改善経路案内装置107は、予測旅行時間が現在経路以下であり、且つ動的限界費用が現在経路以下である動的限界費用が最小になる推奨経路候補があるか否かを判定する。推奨経路候補があると判定した場合、パレート改善経路案内装置107は、探索結果である推奨経路情報i18を、交通情報端末を搭載している車両M40に送信する。推奨経路候補がない判定した場合、パレート改善経路案内装置107は、探索結果を、交通情報端末を搭載している車両M40に送信しない。次に、経路探索アルゴリズムにおける動的限界費用について説明する。一般的なカーナビゲーションシステムや交通情報センターで使われている経路探索アルゴリズムは、リンクの費用をベースに計算している。しかしながら、動的限界費用はリンク単位に定義されるのではなく、走行経路単位で定義される概念である。このため、リンクの費用をベースに計算し、経路探索した結果を使わないと、動的限界費用が計算できないことになる。さらに、一般的な道路における車両は、信号機による制御の影響を受けているため、非渋滞時でも移動時間旅行時間ともいうにある程度の遅れを伴っている。従って、ほとんどの経路は、シミュレーション開始時間から終了時間まで、常に遅れを伴う旅行時間を有することになる。この結果、一般的な経路探索アルゴリズムでは、厳密に限界費用を算出することが困難である。このため、本実施形態では、図2で説明したリンク単位で動的限界費用を近似的に算出する。近似的に算出できる根拠は、動的限界費用は、ある車両が渋滞区間を抜けるまでに要する所要時間と、その車両が渋滞末尾に到着した時刻から、その渋滞が解消するまでの時間の合計に等しいことが本発明の発明者らの研究により示されている桑原雅夫,吉井稔雄,熊谷香太郎:動的システム最適配分とランプ流入制御に関する研究-簡略ネットワークにおける基礎的分析-,土木学会論文集,No667IV50,pp5971,土木学会,200101.参照。なお、本実施形態における経路の動的限界費用は、その車両が経路上の渋滞区間に到着した時刻と、その後に渋滞が解消するまでの時刻との差、すなわち渋滞区間を通過するために要する時間に等しい。図4は、リンクへの流入車両数とリンクからの流出車両数を説明する図である。なお、図4では、説明を簡単にするために、1つのリンクについて説明する。図4において、横軸は時間を表し、縦軸は累積交通量を表している。曲線g101は、リンクへの流入量車両台数の時間に対する変化を表している。符号g102は、リンクからの流出量車両台数の時間に対する変化を表している。また、時刻taからtbの期間の曲線g111は、時刻taにおける動的限界費用を表している。破線g131は、N台目を表している。図4に示したように、リンクへの流入量曲線g101は、リンクからの流出量曲線g102に対して隔たりがある場合、このリンクで流出が滞る、すなわち渋滞が発生することを意味している。この場合、破線g131のように、時刻taに流入したN台目の車両は、N台目にこのリンクを流出する。このため、図4において時間tabは、N台目の車両が渋滞に入ってきてから、渋滞から抜け出すまでの旅行時間を表している。また曲線g111は、このリンクで起きている渋滞が、時刻taから先の時刻において、どの車両まで渋滞が継続しているかを表している。次に、経路の限界費用について図5を用いて説明する。図5は、本実施形態に係る経路の限界費用を説明する図である。図5aは、経路を説明する図である。図5bは、経路の交通量経路フローにおける限界費用を説明する図である。図5cは、リンク単位の交通量リンクフローにおける限界費用を説明する図である。図5bにおいて、横軸は時間を表し、縦軸は経路kの累積交通量を表している。また、図5cにおいて、横軸は時間を表し、縦軸はリンク交通量を表している。図5aにおいて、符号p201からp205は、経路k及び経路jの各位置を表している。また、符号l201からl206は、経路k及び経路jの各リンクを表している。また、図5aにおいて、車両の移動方向は、位置p201上流からp204下流に向かう方向である。また、リンクl201を経路kのi番目のリンク、リンクl202とl205を経路kのi1番目のリンク、リンクl203とl206を経路kのi2番目のリンクとする。図5aに示したように、経路kは、位置p201から車両が流入し、リンクl201を通り、リンクl202、及びl203を経て位置204から流出する。また、経路jは、位置p205から車両が流入し、リンクl205を通り、リンクl206を経て位置204から流出する。この場合、位置p203において、経路kのリンク202と、経路jのリンクl205とが合流している。すなわち、リンクl203とl206は、同じ道路である。ここで、単純なネットワークの場合、経路の動的限界費用は,図5bに示したように、ある経路の交通量経路フローについて、到着累積曲線とボトルネックリンクにおける通過の累積曲線を描き、図式的に求めることで得られる。図5bにおいて、曲線Akiは、リンクl201における上流の位置p201から流入到着交通量ともいうする交通量車両台数の時間に対する変化を表している。曲線Aki1は、リンクl202における上流の位置p202から流入する交通量の時間に対する変化を表している。曲線Aki2は、リンクl203における上流の位置p203から流入する交通量の時間に対する変化を表している。曲線Dki2は、リンクl203における下流の位置p204ボトルネックリンクから流出する交通量の時間に対する変化を表している。また、破線g201とg202は、リンクl203へのリンクl201と同等の流入量を模式的に表している。すなわち、リンクl201には、破線g201で示した車両台数が流入している。しかしながら、リンクl203では、実線で示した曲線Aki2のみ流入し、差分の車両が渋滞していることを示している。また、流出量を示す曲線Dki2においても、破線g202に示した流入量より低い台数のみの車両しか通過できていず、差分の車両が渋滞していることを示している。また、曲線d201は、図4で説明したのと同様に、時刻t1における経路kの限界費用を表している。本実施形態では、図5cに示すように、経路毎ではなくリンク単位で交通量リンクフローの累積図を描き、ある経路上の渋滞区間の最後に位置するボトルネックリンクの累積図から、簡易的に動的限界費用を求める。図5cの曲線Aiは、リンクl201における上流の位置p201から流入する交通量の時間に対する変化を表している。曲線Ai1は、リンクl202における上流の位置p202から流入する交通量と、リンクl205における上流の位置p205から流入する交通量とを加算した交通量の時間に対する変化を表している。曲線Ai2は、リンクl203及びリンク206における上流の位置p203から流入する交通量の時間に対する変化を表している。曲線Di2は、リンクl203における下流の位置p204から流出する交通量の時間に対する変化を表している。また、破線g211は、リンクl203へのリンクl201と同等の流入量を模式的に表している。また、曲線d202は、遅れを伴うリンクl203及びl206における経路kの限界費用を表している。さらに、図5a及び図5cで示したように、リンクl203で渋滞が終了しているため、このリンクl203をボトルネックリンクと定義する。図5cにおいて、曲線Ai~Ai2、Di2の傾きが大きい方が、交通量が多いことを表している。また、曲線Aiの傾きより、曲線Di2の傾きが小さいのは、到着した交通量が多くても、その経路で通過させることができる交通量が到着した交通量より少ないことを表している。ここで、曲線Di2の傾きを、ボトルネックの容量と定義する。なお、ボトルネックの容量とは、単位時間当たりに通過できる交通量である。このため、曲線Aiの傾きと曲線Ai1の傾きとの乖離量は、流入した交通量と実際に流れた交通量の乖離を表し、すなわち、区間iから区間i1に溜まっている交通量を表している。同様に、曲線Ai1の傾きと曲線Ai2の傾きとの乖離量は、流入した交通量と実際に流れた交通量の乖離を表し、すなわち、区間i1から区間i2に溜まっている交通量を表している。図5を用いて説明した経路の場合、単純に、リンク単位で、上述したある車両が渋滞区間を抜けるまでに要する所要時間と、その車両が渋滞末尾に到着した時刻から、その渋滞が解消するまでの時間の合計に等しいに基づき、動的限界費用を求めようとすると、例えばあるボトルネックリンクの渋滞が、そのリンクを越えて上流のリンクにまで及んでいると、限界費用が重複して算出されてしまう。このため、本実施形態において、遅れを伴うリンクが連続する区間については、その区間の最下流のリンクでのみ限界費用、すなわちそのリンクの流入時刻から、渋滞の予測解消時刻までの時間を算出し、その他の渋滞リンクでは、通過所要時間を算出する。この結果、重複をなくし、リンク単位での計算で動的限界費用の近似値を得ることが出来る。次に、渋滞予測方法について、図6~図9を用いて説明する。図6は、本実施形態に係る動的限界費用を説明する図である。図6において、横軸は時間を表し、縦軸はリンク内の車両の移動速度であるリンク旅行速度を表している。破線g301は、渋滞判定の閾値を表している。実線g311は、時刻0からt301の期間における時間に対するリンク旅行速度の実測値の変化を表し、破線g312は、時刻t301以降における時間に対するリンク旅行速度の予測値の変化を表している。また、時刻t301は、現在時刻である。予測旅行時間情報生成装置105は、プローブ交通情報であるリアルタイム交通情報を入力として、予測モデルを用いて、現在時刻t301以降のリンク旅行速度を予測する。図6に示すように、予測旅行時間情報生成装置105は、リンク旅行速度g311が、予め定めた渋滞判定閾値g301より小さくなった場合を渋滞とみなす。図6において、予測旅行時間情報生成装置105は、現在時刻以降、時刻t301から時刻t302の期間、渋滞が発生していると判定する。このように、本実施形態では、リンク旅行速度の予測値g312が、渋滞判定閾値g301未満の場合の期間t301からt302を、動的限界費用と定義する。次に、渋滞しているリンクの判定について、図7を用いて説明する。図7は、本実施形態に係る渋滞区間を説明する図である。図7において、車両の進行方向をx方向、x方向と垂直な方向をy方向とする。図7において、符号r401は、x方向に延びている道路、符号c401からc404は、道路r401と垂直なy方向に延びている道路を表している。また、道路r401とc401の交点、道路r401とc402の交点、道路r401と道路c403の交点及び道路r401とc404の交点は、交差点を表している。また、図7において、x方向の0からx402の区間l401、x402からx404の区間l402及びx404からx405の区間l403は、各々、信号機と信号機との区間であり、リンクである。図7に示すように、符号g401は、x方向のx401からx402の区間、速度低下が発生している区間である。予測旅行時間情報生成装置105は、このように速度が低下する区間以下、速度低下区間というg401が、リンクl401より短いため、渋滞とはみなさない。また、図7に示すように、符号g402は、x方向のx403からx405の区間、速度低下が発生している区間である。予測旅行時間情報生成装置105は、このように速度が低下する速度低下区間g402が、リンクl403より長いため、渋滞とみなす。この場合、渋滞と見なされる区間は、リンクl403のみではなく、リンクl402も含んでいる。このため、予測旅行時間情報生成装置105は、速度低下区間が、複数のリンクを跨ぐ場合、連続している速度低下区間をつなげて1つの速度低下区間とみなす。なお、旅行速度を予測する単位区間以下、旅行速度予測の単位区間というは、信号交差点程度の距離とする。信号交差点程度の距離は、数百m程度であるので、旅行速度予測の単位区間は、信号の1サイクルで滞留している車両量を捌ける滞留長長くても200m程度よりも長い方が望ましい。例えば、300m以上の区間が、時速20km未満と予測される場合、予測旅行時間情報生成装置105は、渋滞が生じると予測する。区間の長さを300m以上の場合、車両は、信号の2サイクル以上要して通過できた状態に相当するためであり、信号待ちによる速度低下ではないためである。次に、ボトルネックリンクを特定する方法について、図8を用いて説明する。渋滞の終了位置であるボトルネックリンクが、どこであるかを特定することは単純ではない。このため、本実施形態では、過去の交通量や渋滞データを蓄積しておき、渋滞が起きている箇所を予め抽出しておく。図8は、本実施形態に係るボトルネックリンクの特定方法の一例を説明する図である。図8aは、図7のx軸方向x403からx405の区間を示した図である。図8bは、図8aの区間をリンクで示した図である。図8aにおいて、車両の進行方向をx方向、x方向と垂直な方向をy方向とする。図8bにおいて、符号p402は、図8aの道路r401とc403との交点であり、符号p403は、図8aの道路r401とc404との交点である。図8bに示したように、点p402には、リンクl402、l402-1及びl402-2の各入力が接続されている。また、点p402の出力は、リンクl403に接続されている。同様に、点p403には、リンクl403、l403-1及びl403-2の各入力が接続されている。また、点p403の出力は、リンクl404に接続されている。経路案内システム1の予測旅行時間情報生成装置105は、例えば、過去一ヶ月から数ヶ月程度の交通量のデータのうち、5分間のリンク旅行速度に関するデータの統計情報処理装置104を介して外部情報記憶部103から読み出す。なお、5分間のリンク旅行速度データとは、リンク毎に測定された5分間の車両の移動速度データである。図8aに示したように、区間g401のリンク旅行速度は、10km/h第1の速度未満である。このため、予測旅行時間情報生成装置105は、道路r401においてリンクl402とl403の区間では、渋滞が起きていると判別する。一方、道路r401のx方向のc404以降の区間g402リンクl404において、リンク旅行速度は30km/h第1の速度以上である。このため、予測旅行時間情報生成装置105は、道路r401においてリンクl404では、渋滞が起きていないと判別する。渋滞がリンクl402とl403で起きていてリンクl404では起きていないため、予測旅行時間情報生成装置105は、渋滞が起きているリンクをボトルネックリンクとし、このリンクに対して1ポイントを加算する。予測旅行時間情報生成装置105は、このようにして、解析したい全てのリンクについて、近接するリンク間の旅行速度データを比較していく。予測旅行時間情報生成装置105は、このようにして、与えたポイントを加算していき、1日あたりのポイントの平均値が、6から12ポイント程度のリンクを、ボトルネックリンクとして抽出する。すなわち、予測旅行時間情報生成装置105は、このようにして、ボトルネックになっている下流地点を決める。次に、ボトルネックリンクの経路への影響度について、図9を用いて説明する。一般的な道路では、図9のように、複数の道路が従属して接続されている。このため、本実施形態では、1つのボトルネックが、どれくらいの経路に影響するかポイントを与えるかについても重み付けを行う。本実施形態では、過去の統計データに基づき、平均的な渋滞情報を使って、そのボトルネックに接続されている道路がいくつあるのか、接続されている道路の数を数えることで、影響度を以下のように算出する。図9のような数本の道路が互いに交差している状態について説明する。図9は、本実施形態に係るボトルネックリンクの経路への影響度を説明する図である。図9において、左右方向をx方向、x方向に垂直な方向をy方向とする。図9において、符号r501、r502及びr503は、x方向に各々平行な道路であり、符号c501は、道路r501、r502及びr503に垂直な道路である。また、符号c502は、道路r503と交差し、道路r502に合流する道路である。符号l501、l502、l503及びl504は、各々ボトルネックリンクを表している。また、符号p501、p502、p503、p504、p505、p506、p507及びp508は、道路上の点や交差点を表している。点p501は、道路r502のx軸の負方向の一方端であり、ボトルネックリンクl501の流入点である。点p502は、道路r503のx軸の負方向の一方端であり、ボトルネックリンクl502の流入点である。点p503は、道路c502のy軸の負方向の一方端であり、ボトルネックリンクl503の流入点である。点p504は、道路c501のy軸の負方向の一方端であり、ボトルネックリンクl502の流入点である。点p505は、道路r503と道路c502との交点であり、ボトルネックリンクl503上の通過点である。点p506は、道路r503と道路c501との交点であり、ボトルネックリンクl504上の通過点である。点p507は、道路r502と道路c502との交点であり、道路r502と道路c502との合流点であり、ボトルネックリンクl501、l502、l503及びl504上の通過点である。また、ボトルネックリンクl504において、y軸の負方向を下流、x軸の正方向を上流という。図9に示すように、ボトルネックリンクl501は、点p501と点p507との区間と、点p507と点p508との区間から構成されている。また、ボトルネックリンクl501は、点p501から渋滞が始まり、道路r502において点p501からx軸の正方向の点p507までのリンク、及び道路c501において位置p507からy軸の正方向の位置p508までのリンクで渋滞が継続している。ボトルネックリンクl502は、点p502と点p505との区間と、点p505と点p507との区間と、点p507と点p508との区間とから構成されている。また、ボトルネックリンクl502は、点p502から渋滞が始まり、道路r503において点p502からx軸の正方向の点p505までのリンク、道路c502において位置p505からx軸に対して角度αの方向の位置p507までのリンク、道路c501において位置p507からy軸の正方向の位置p508までのリンクで渋滞が継続している。ボトルネックリンクl503は、点p503と点p505との区間と、点p505と点p507との区間と、点p507と点p508との区間とから構成されている。また、ボトルネックリンクl503は、点p503から渋滞が始まり、道路c502において点p503からx軸に対して角度αの方向の点p505を介し位置p507までの2つのリンク、道路c501において位置p507からy軸の正方向の位置p508までのリンクで渋滞が継続している。ボトルネックリンクl504は、点p504と点p506との区間と、点p506と点p507との区間と、点p507と点p508との区間とから構成されている。また、ボトルネックリンクl504は、点p504から渋滞が始まり、道路c501において点p504からy軸の正方向の点p506を介し位置p507までの2つのリンク、道路c501において位置p507からy軸の正方向の位置p508までのリンクで渋滞が継続している。予測旅行時間情報生成装置105は、図8で説明したように、車両がそのリンクを通過する時点で、各リンクに渋滞が起きているか否かを判別する。具体的には、予測旅行時間情報生成装置105は、例えば、過去一ヶ月から数ヶ月程度の交通量のデータのうち、5分間のリンク旅行速度に関するデータを外部情報記憶部103から読み出す。予測旅行時間情報生成装置105は、リンク旅行速度が、10km/h第1の速度未満であるか否かを判定する。予測旅行時間情報生成装置105は、1つのリンクを抽出し、抽出したリンクのリンク旅行速度が10km/h未満であり、そのリンクに下流側で接続するいずれかのリンク旅行速度も10km/h未満の場合、抽出したリンクに1ポイント付与する。なお、ここで用いるポイントは、図8で説明したポイントとは異なる。予測旅行時間情報生成装置105は、このように算出したポイントが、1日あたりの平均で6から12ポイント程度あるリンクを、ボトルネックからの渋滞に従属しているリンク末端の道路と見なす。具体的には、図9において、点p507からp508が合流地点であり、上流側である。このリンクには、図9で示したように、点p501からp507のリンク、点p502から点p505を経て点p507に接続されるリンク、点p503から点p505を経て点p507に接続されるリンク、及び点p504から点p506を経て点p507に接続される4つのリンクが上流の点p507からp508の区間に接続されている。そして、パレート改善経路案内装置107は、ボトルネックリンクの上流で従属するリンクのグラフ構造が有している本数を算出する。図9において、ボトルネックリンクの上流である点p507からp508の区間で従属するリンクは4本であるので、パレート改善経路案内装置107は、リンク毎に影響度1を加算し、影響度4であると定義する。影響度が高いことの意味合いは、渋滞率が高いことを意味している。図9に示した影響度は、プローブから取得したデータに基づいて生成される。このようにして、全てのリンクについて重み付けを行った場合、予測旅行時間情報生成装置105は、例えば、1日あたりの平均で6~12ポイント程度の重み付けがされたリンクをボトルネックリンクとして抽出する。なお、車両の移動速度を測定できるセンサーが設置されている場合、パレート改善経路案内装置107は、このセンサーが取得した速度データを用いて、同様にボトルネックリンクを抽出するようにしてもよい。なお、6ポイントの重み付けがされているリンクは、30分5分×6間、渋滞が継続している道路である可能性がある。同様に、12ポイントの重み付けがされているリンクは、60分5分×12間、渋滞が継続している道路である可能性があることを表している。次に、経路案内システム1の処理手順について、図10を用いて説明する。図10は、本実施形態に係る経路案内システム1の処理手順のフローチャートである。まず、以下で行う処理の概略について説明する。経路案内システム1は、全車両が最適である経路を探索する。その後、各車両の経路について、経路の1つ1つのリンクについて、別のリンクに行った方がその車両にとってコスト旅行時間的にメリットがあり、システム的なコストから見てもメリットがあると判定された場合、その車両に対して推奨経路情報として提示する。ステップS101プローブ交通情報収集装置101は、プローブ車両M30が送信するプローブ交通情報i10を取得する。次に、プローブ交通情報収集装置101は、受信したプローブ交通情報、道路に設置されているセンサーからの交通量情報、過去の交通量情報等を用いて、公知の手法により現在の交通量や車両の旅行速度等を示すリアルタイム交通情報i11を生成する。プローブ交通情報収集装置101は、生成したリアルタイム交通情報i11を予測旅行時間情報生成装置105に出力し、さらに生成したリアルタイム交通情報i11を交通情報蓄積装置102に記憶させる。ステップS101終了後、ステップS102に進む。ステップS102統計情報処理装置104は、交通情報蓄積装置102にステップS101で記憶されたリアルタイム交通情報i11を含む過去に記憶されたリアルタイム交通情報i12を読み出す。次に、統計情報処理装置104は、外部情報記憶部103に記憶されている交通情報i13を読み出す。次に、統計情報処理装置104は、読み出したリアルタイム交通情報i12と交通情報i13とに基づき、予測モデルを生成する。ステップS102終了後、ステップS103に進む。ステップS103予測旅行時間情報生成装置105は、プローブ交通情報収集装置101が出力するリアルタイム交通情報i11を、統計情報処理装置104が生成した予測モデルを用いて、リンク毎の予測旅行時間情報を生成する。ステップS103終了後、ステップS104に進む。ステップS104予測旅行時間情報生成装置105は、図示しない交通情報端末を搭載している車両M40が送信する車両の現在経路情報と、車両が走行している目的地情報とを含む情報i15を取得する。ステップS104終了後、ステップS105に進む。ステップS105予測旅行時間情報生成装置105は、取得した現在経路情報と目的地情報に基づき、車両M40の現在位置から目的位置までの経路候補情報を公知の手法を用いて生成する。ステップS105終了後、ステップS106に進む。ステップS106予測旅行時間情報生成装置105は、ステップS105において生成した目的地までの経路候補情報と、ステップS103において生成した予測時間情報とを用いて、上述したように経路候補情報の経路からボトルネックリンクを抽出する。具体的には、予測旅行時間情報生成装置105は、車両が各リンクに到達する時刻において、図7を用いて説明したように生成した予測時間情報を用いて渋滞区間を抽出し、抽出した区間が300m以上であり、予め定められている旅行速度例えば、時速20km未満と予測される区間を渋滞していると判定する。なお、予測旅行時間情報生成装置105は、この判定を、例えば時刻毎に行う。次に、予測旅行時間情報生成装置105は、図8を用いて説明したように、1日あたりの平均の付与したポイントが予め定めた値より多いリンクまたは区間をボトルネックリンクとして抽出する。ステップS106終了後、ステップS107に進む。ステップS107予測旅行時間情報生成装置105は、抽出したボトルネックリンクにおいて、経路上のボトルネックリンクの渋滞終了予想時刻を、ステップS103で生成した予測旅行時間情報と、ステップS105で生成した経路候補情報とを用いて推定する。例えば図5を用いて説明したように、予測旅行時間情報生成装置105は、各リンクの経路の累積交通量に対する時間変化のグラフに基づき、ボトルネックリンクの渋滞終了予想時刻を推定する。予測旅行時間情報生成装置105は、推定したボトルネックリンクの渋滞終了予想時刻、予測旅行時間情報及び生成した経路候補情報を動的限界費用情報生成装置106に出力する。ステップS107終了後、ステップS108に進む。ステップS108動的限界費用情報生成装置106は、入力されたボトルネックリンクの渋滞終了予想時刻、予測旅行時間情報及び生成した経路候補情報に基づき、各経路候補における渋滞が発生しているリンクの動的限界費用を算出する。動的限界費用情報生成装置106は、算出した各経路候補における渋滞が発生しているリンクの動的限界費用を、パレート改善経路案内装置107に出力する。ステップS108終了後、ステップS109に進む。ステップS109パレート改善経路案内装置107は、動的限界費用情報生成装置106が出力する各経路候補における渋滞が発生しているリンクの動的限界費用及び予測旅行時間に基づき、図9を用いて説明したように、各ボトルネックリンクの経路候補への影響度を算出する。次に、パレート改善経路案内装置107は、動的限界費用情報生成装置106が出力する各経路候補における渋滞が発生しているリンクの動的限界費用及び予測旅行時間に基づき、現在、車両M40が通行している経路と、生成した各経路候補の各予測旅行時間と各動的限界費用について、順次算出する。ステップS109終了後、ステップS110に進む。ステップS110次に、パレート改善経路案内装置107は、ステップS109で算出された値を順次比較し、動的限界費用が最小になる経路候補を探索する。パレート改善経路案内装置107は、現在経路の予測旅行時間情報と各経路候補の予測旅行時間情報とを比較し、現在経路の予測旅行時間以下の経路候補を探索する第1探索。また、パレート改善経路案内装置107は、現在経路の動的限界費用と各経路候補の動的限界費用とを比較し、現在経路の動的限界費用以下の経路候補を探索する第2探索。パレート改善経路案内装置107は、第1探索及び第2探索を行った結果、最も動的限界費用が小さい経路を、次式1を用いて算出する。ckt=a1Tkta2Mkt1式1において、cktは、経路候補kにおける各時刻tのコストである。Tktは、例えば、プローブ交通情報や、センサーから得られた情報から生成したリンクの通過所要時間リンク旅行時間である。Mktは、次式2で算出されるボトルネックリンクにおける旅行時間である。Mkt=渋滞が解消するまでの時間×影響度2なお、式2のMktは、ボトルネックリンクについてのみ算出する。また、式1において、a1、a2は、予め定めておく定数である。式1において、定数a1=0及び定数a2=1の状態は、利用者最適状態である。また、式1において、定数a1=1及び定数a2=0の状態は、システム最適状態である。このため、定数a1及びa2のバランスを取れば、パレート最適状態にできる。定数a1及びa2のバランスは、例えば、このように生成された経路案内情報を使用している車両がどの位の割合かにより、シミュレーションにより数値計算して実情に応じた割合を算出する。ステップS110終了後、ステップS111に進む。ステップS111次に、パレート改善経路案内装置107は、ステップS110で算出した経路候補の中から、予測旅行時間が現在経路以下であり、且つ動的限界費用が現在経路以下である動的限界費用が最小になる経路候補である推奨経路があるか否かを判定する。推奨経路があると判定した場合ステップS111;Yes、ステップS112に進む。推奨経路がないと判定した場合ステップS111;No、ステップS113に進む。ステップS112推奨経路があると判定した場合ステップS111;Yes、パレート改善経路案内装置107は、探索結果である推奨経路情報を、交通情報端末を搭載している車両M40に送信する。この場合、車両M40の利用者は、例えば、従来技術のカーナビゲーションシステムで探索された利用者最適状態の経路から、経路案内システム1から送信された推奨経路に走行経路を変更する。ステップS113推奨経路がない判定した場合ステップS111;No、パレート改善経路案内装置107は、探索結果を、交通情報端末を搭載している車両M40に送信しない。この場合、車両M40の利用者は、例えば、従来技術のカーナビゲーションシステムで探索された利用者最適状態の経路の走行を継続する。従来技術のカーナビゲーションシステムによるコスト計算では、式1においてTktの項のみ算出していた。しかし、本実施形態では、式1において2項目Mktのボトルネックリンクに対する動的限界費用を追加して計算することに差異がある。また、本実施形態では、従来技術と同様に、旅行時間をベースに、ボトルリンクによる動的限界費用も加味している。すなわち、本実施形態では、自車両がこの経路を選択した場合に、他の車両に対してどの程度、影響があるかを加味していることになる。次に、本実施形態に係る経路案内システム1の効果の一例を、図11から図14を用いて説明する。図11は、本実施形態に係る経路案内システム1において、シミュレーションに用いた地図である。図11において、左右方向をx方向、x方向に垂直な方向をy方向とする。図11に示したエリアは、x方向が10kmの長さであり、y方向が20kmの長さであり、このエリア内における道路のリンク数は7600ある。また、車両の交通量は、3時間で27万台である。図12は、図11に示したエリアで本実施形態に係る経路案内システム1をシミュレーションした結果である。図12において、符号g601で示した行は、利用者最適状態DUO75の経路案内から、経路案内システム1が提示した推奨経路DPOに変更した車両数と、システム最適状態DSOにおける車両数を表している。符号g602で示した行は、DUO75の経路案内から、経路案内システム1が提示した推奨経路に変更した車両数の全台数に対する割合と、DSOにおける車両数の全台数に対する割合を表している。符号g603で示した行は、DUO75、DPO及びDSOの各状態における総旅行時間=台数×走行時間を表している。符号g604で示した行は、DUO75における総旅行時間とDPOにおける総旅行時間との差及びDUO75における総旅行時間とDSOにおける総旅行時間との差が、DUO75における総旅行時間の何であるかを表している。符号g605で示した行は、DUO75の経路案内から、経路案内システム1が提示したDPOに変更した車両において1台あたりの削減された総旅行時間と、DUO75の経路案内から、DSOに変更した車両において1台あたりの削減された総旅行時間とを表している。符号g606で示した行は、DUO75、DPO及びDSOの各状態における3時間あたりのCO2の総排出量を表している。符号g607で示した行は、DUO75のCO2排出量に対するDPOのCO2排出量の削減率、DUO75のCO2排出量に対するDSOのCO2排出量の削減率を表している。DUO75を比較対象としている理由は、利用者最適状態において、カーナビゲーションを搭載している車両が、例えば100DUO100に設定した場合、全ての車両がカーナビゲーションによって提示された最適気経路に向かってしまう。カーナビゲーションを搭載している車両が、例えば100DUO100に設定した場合についてシミュレーションを行った結果、効率は悪化した。シミュレーションの結果、DUO75の状態が、本実施形態の経路案内システム1や、DSOを用いない場合に一番効率がよかったため、DUO75の状態を比較値に設定した。図12に示したように、DUO75の状態から、経路を変更した車両はDPO本実施形態の場合、1.7、DSOの場合、2.4であった行g601、g602。台数ではDSOの方が、DUO75から経路変更している車両数が多い。しかしながら、総旅行時間について比較すると、変更した車両あたりの削減された旅行時間は、DPOの方が多い行g603~g605。さらに、DUO75に対するDPOのCO2削減量は、0.98である。以上のように、本実施形態に係る経路案内システム1では、利用者最適状態から経路を変更した場合、旅行時間も削減でき、これによりCO2の排気量も削減できることを示唆している。図13は、システム最適状態における経路変更有り場合の車両台数と旅行時間変化を表す図である。なお、経路変更なしの場合の車両では、カーナビゲーションシステムが設定した利用者最適状態の経路が選択されている。図13において、横軸は旅行時間の変化時間を表し、横軸の真ん中0秒が、旅行時間が変化しなかったことを意味している。また、図13において、縦軸は車両台数を表している。図13に示すように、経路変更有りの場合、旅行時間0秒に対して、ほぼ左右対称かつ正規分布状に旅行時間の変化が分散している。この場合、図13に示すように、利用者最適状態の場合と比較して、300秒も旅行時間が短縮された利用者がいる反面、300秒も旅行時間が増加した利用者がいる。さらに、破線長丸g701で示したように、旅行時間が増加した利用者は、1000人以上いることを表している。図14は、本実施形態に係るパレート最適状態における経路変更有り場合の車両台数と旅行時間変化を表す図である。なお、経路変更なしの場合の車両では、カーナビゲーションシステムが設定した利用者最適状態の経路が選択されている。図14において、横軸は旅行時間の変化時間を表し、横軸の真ん中0秒が、旅行時間が変化しなかったことを意味している。また、図14において、縦軸は車両台数を表している。図14の破線長丸g702に示すように、図13とは大きく異なり、旅行時間が増加している利用者は、数百人程度であることを表している。一方、旅行時間が短縮された利用者は、システム最適状態と同等である。すなわち、本実施形態の経路案内システム1によれば、経路変更した利用者にとって、旅行時間が現状のままであるか、短縮する場合がほとんどであり、旅行時間が増加する場合は少ないことを表している。以上のように、本実施形態の経路案内システム1において、動的限界費用情報生成装置106は、渋滞が起きるリンク区間を示す情報と渋滞が終了する時刻を示す情報とに基づき、現在経路及び経路候補の各動的限界費用を算出する。そして、パレート改善経路案内装置107は、各経路候補の各予測旅行時間及び各動的限界費用に基づき、現在経路及び各経路候補の各予測旅行時間及び各動的限界費用について比較し、比較の結果、動的限界費用が最小になる経路候補を探索する。この結果、利用者にとって経路が最短の利用者最適状態よりコストを軽減し、さらに経路案内システム1にとってコストが最も安いシステム最適状態より利用者の旅行時間の増加を軽減できる交通渋滞緩和の効率を向上することができる。また、本実施形態では、動的限界費用の算出において、以下のような処理を行うようにした。予測旅行時間情報生成装置105は、現在経路上及び前記経路候補上の全てのリンクから1つのリンクを抽出し、抽出したリンクにおける車両の目的地までの到着時間までの将来における移動速度が予め定められている第1の速度未満であると判定した場合、抽出したリンクを渋滞が起きるリンクであると予測するようにした。また、予測旅行時間情報生成装置105は、渋滞が起きるリンクを示す情報に基づき、渋滞が終了するボトルネックリンクを抽出し、抽出したボトルネックリンクにおいて、現在経路上及び経路候補上のボトルネックリンクの渋滞が終了する時刻を、リンク毎の予測旅行時間情報及び現在経路情報及び経路候補情報を用いて推定するようにした。また、予測旅行時間情報生成装置105は、渋滞が起きるリンクの下流に接続されている全てのリンクにおける車両の目的地までの到着時間までの将来における移動速度が予め定められている第2の速度以上であると判定した場合、渋滞が起きるリンクに重み付けを行い、渋滞が起きるリンクの重みを示す値が、予め定められている値より大きい場合、渋滞が起きるリンクをボトルネックリンクとして抽出するようにした。また、パレート改善経路案内装置107は、ボトルネックリンクの上流側に従属しているリンクのグラフ構造における末端数に基づき、ボトルネックリンクの影響度を算出し、算出した前記影響度を用いて動的限界費用を算出するようにした。この結果、本実施形態では、渋滞が終了するリンクであるボトルネックリンクを特定でき、さらにボトルネックリンクの経路への影響度を算出して動的限界費用の算出を行うようにしたので、利用者最適状態やシステム最適状態よりコスト的に利用者に好適な交通渋滞緩和の効率を向上することができる。なお、本実施形態では、プローブ車両から送信される交通情報を用いる例を説明したが、例えば、図示しないセンサーが車両の移動速度情報も収集して、プローブ交通情報収集装置101に送信するようにしてもよい。"