(57)【要約】【課題】ユーザが過去に通ったことがあり、かつ、同じ地点に向かう複数の経路がある場合に、それらの経路に対して所要時間情報を提供する所要時間情報提供装置を提供する。【解決手段】所要時間情報提供装置は、所定の間隔で取得された時刻と、各時刻に移動体が位置していた地点との組で表される移動履歴を蓄積する履歴蓄積部１０３と、履歴蓄積部１０３に蓄積されている地点を時刻の順に結んで表される複数の移動経路のうちから、２以上の移動経路に共通する２地点を結ぶ複数の異なる移動経路を抽出する経路抽出部１０５と、経路抽出部１０５によって抽出された移動経路ごとに、２地点間の移動に要する所要時間情報を算出する情報算出部１０８と、算出された所要時間情報を移動体の現在位置に関連付けて利用者に提供する情報提供部１１０とを備える。【選択図】図１
2008261714.tif 000002
【特許請求の範囲】
【請求項１】
２地点間を結ぶ複数の異なる移動経路があった場合、各移動経路を通って移動体が２地点間を移動するために必要な所要時間に関する情報である所要時間情報を、所定の移動経路について提供する所要時間情報提供装置であって、
所定の間隔で取得された時刻と、前記各時刻に移動体が位置していた地点との組で表される移動履歴を蓄積する履歴蓄積手段と、
前記履歴蓄積手段に蓄積されている地点を時刻の順に結んで表される複数の移動経路のうちから、２以上の前記移動経路に共通する２地点を結ぶ複数の異なる移動経路を抽出する経路抽出手段と、
前記経路抽出手段によって抽出された前記移動経路ごとに、前記２地点間の移動に要する所要時間情報を算出する情報算出手段と、
算出された前記所要時間情報を前記移動体の現在位置に関連付けて利用者に提供する情報提供手段と
を備えることを特徴とする所要時間情報提供装置。
【請求項２】
前記経路抽出手段は、前記２地点のうち、複数の移動経路に分岐する地点を分岐点とし、複数の前記移動経路が合流する地点を合流点として、共通の分岐点と合流点とを結ぶ複数の移動経路のうち、移動経路同士で互いに一致する部分を含まない複数の移動経路を抽出する
ことを特徴とする請求項１に記載の所要時間情報提供装置。
【請求項３】
前記経路抽出手段は、共通の分岐点と合流点とを結ぶ複数の移動経路のうち、いずれの１つも同じ経路を２度以上含まない移動経路を抽出する
ことを特徴とする請求項２に記載の所要時間情報提供装置。
【請求項４】
前記経路抽出手段は、移動体が前記分岐点を通過する前の移動方向と前記合流点を通過する後の移動方向とのいずれもが、互いに一致する移動経路を抽出する
ことを特徴とする請求項３に記載の所要時間情報提供装置。
【請求項５】
前記所要時間情報提供装置は、さらに、
前記履歴蓄積手段に蓄積されている前記移動履歴から、前記移動体の移動先（目的地）を予測する移動先予測手段を備え、
前記移動先予測手段によって予測された移動先までの移動経路上に、前記経路抽出手段によって抽出された複数の移動経路がある場合、前記情報提供手段は、前記分岐点と前記合流点とを結ぶ異なる移動経路についての所要時間情報を提供する
ことを特徴とする請求項４に記載の所要時間情報提供装置。
【請求項６】
前記所要時間情報提供装置は、さらに、
現在時刻と前記移動体の現在位置との組を取得する現在位置取得手段を備え、
前記履歴蓄積手段は、所定時間以上エンジンが停止していた地点を移動経路の出発地または移動先として、前記エンジン停止地点で移動履歴を区切って蓄積し、
前記移動先予測手段は、前記履歴蓄積手段に蓄積されている地点を時刻の順に結んで表される複数の移動経路のうち、出発地から現在位置までの移動経路が一致する移動経路のいずれかを、現在の移動先に至る移動経路と予測する
ことを特徴とする請求項５に記載の所要時間情報提供装置。
【請求項７】
前記情報提供手段は、前記移動体の現在位置が、抽出された分岐点から所定の閾値以内の距離に近づいたとき算出された所要時間情報を提供する
ことを特徴とする請求項６に記載の所要時間情報提供装置。
【請求項８】
前記情報算出手段は、分岐点と合流点との間の異なる複数の前記移動経路について、移動経路同士の所要時間の大小関係を表す所要時間情報を算出する
ことを特徴とする請求項１に記載の所要時間情報提供装置。
【請求項９】
前記情報算出手段は、前記２地点のうち、複数の移動経路に分岐する地点を分岐点とし、複数の前記移動経路が合流する地点を合流点として、分岐点と合流点との間の異なる複数の前記移動経路のそれぞれについて、前記履歴蓄積手段に蓄積されている時刻と地点との組から、分岐点と合流点との間の移動に要する所要時間を算出し、
前記所要時間情報提供装置は、さらに、
前記分岐点と前記合流点とを結ぶ移動経路ごとに算出された所要時間を、移動経路同士で比較し、比較された所要時間の差が所定の閾値以内である移動経路について所要時間が類似すると判断する類似判断手段を備え、
前記情報提供手段は、前記類似判断手段により所要時間が類似すると判断された移動経路について前記所要時間情報を提供する
ことを特徴とする請求項１に記載の所要時間情報提供装置。
【請求項１０】
前記情報算出手段は、分岐点と合流点との間の異なる複数の前記移動経路のそれぞれについて、分岐点と合流点との間の移動に要する所要時間の平均を算出し、
前記類似判断手段は、前記分岐点と前記合流点とを結ぶ異なる移動経路ごとに算出された所要時間の平均を、前記移動経路同士で比較し、比較された所要時間の平均の差が閾値以内である移動経路について所要時間が類似すると判定する
ことを特徴とする請求項９に記載の所要時間情報提供装置。
【請求項１１】
前記情報算出手段は、前記２地点のうち、複数の移動経路に分岐する地点を分岐点とし、複数の前記移動経路が合流する地点を合流点として、分岐点と合流点との間の異なる複数の前記移動経路のそれぞれについて、前記履歴蓄積手段に蓄積されている時刻と地点との組から、分岐点と合流点との間の移動に要する所要時間の平均を算出し、
前記所要時間情報提供装置は、さらに、
前記分岐点と合流点を結ぶ異なる移動経路ごとに、前記情報算出手段が算出した所要時間の平均を比較し、所要時間の平均の大小関係を算出する比較手段と、
前記比較手段によって算出された前記大小関係に反する移動履歴の数を算出し、前記比較手段によって算出された前記大小関係に反する前記移動履歴の数が多い場合に、反事例が多いと判定する反事例判定手段とを備え、
前記情報提供手段は、前記反事例判定手段により反事例が多いと判断された移動経路について前記所要時間情報を提供する
ことを特徴とする請求項１に記載の所要時間情報提供装置。
【請求項１２】
前記類似判断手段は、前記履歴蓄積手段に蓄積されている移動履歴から、前記分岐点と合流点を結ぶ異なる移動経路のそれぞれの通過回数を算出し、
前記情報提供手段は、前記類似判断手段により算出された通過回数が閾値以下である移動経路について前記所要時間情報を提供する
ことを特徴とする請求項９に記載の所要時間情報提供装置。
【請求項１３】
前記類似判断手段は、前記履歴蓄積手段に蓄積されている移動履歴から、前記分岐点と合流点を結ぶ異なる移動経路のそれぞれの通過回数を算出し、
前記情報提供手段は、前記類似判断手段により算出された通過回数が類似する移動経路について前記所要時間情報を提供する
ことを特徴とする請求項９に記載の所要時間情報提供装置。
【請求項１４】
前記情報算出手段は、前記２地点のうち、複数の移動経路に分岐する地点を分岐点とし、複数の前記移動経路が合流する地点を合流点として、分岐点と合流点との間の異なる複数の前記移動経路のそれぞれについて、前記履歴蓄積手段に蓄積されている時刻と地点との組から、分岐点と合流点との間の移動に要する所要時間を算出し、
前記所要時間情報提供装置は、さらに、
前記履歴蓄積手段に蓄積されている時刻から、前記複数の移動経路を最も新しい時刻で通過したときの現在所要時間を算出する現在時間算出手段と、
前記履歴蓄積手段に蓄積されている時刻から、最も新しい時刻で通過したときを除く、前記移動経路の過去所要時間を算出する過去時間算出手段と、
前記現在所要時間と前記過去所要時間とが類似するか否かを判定する第２類似判断手段とを備え、
前記情報提供手段は、前記第２類似判断手段が類似しないと判定したときに、前記所要時間情報を提供する
ことを特徴とする請求項１に記載の所要時間情報提供装置。
【請求項１５】
前記情報算出手段は、前記２地点のうち、複数の移動経路に分岐する地点を分岐点とし、複数の前記移動経路が合流する地点を合流点として、分岐点と合流点との間の異なる複数の前記移動経路のそれぞれについて、前記履歴蓄積手段に蓄積されている時刻と地点との組から、分岐点と合流点との間の移動に要する所要時間を算出し、
前記所要時間情報提供装置は、さらに、
前記分岐点と合流点を結ぶ異なる移動経路ごとに、前記情報算出手段が算出した所要時間を比較し、前記所要時間の大小関係を算出する比較手段と、
外部から提供される道路情報を取得し、取得された前記道路情報から前記分岐点と前記合流点とを結ぶ異なる移動経路ごとに、所要時間を算出する第２時間算出手段と、
前記分岐点と合流点を結ぶ異なる移動経路ごとに、前記第２時間算出手段が算出した所要時間を比較し、前記所要時間の大小関係を算出する第２比較手段とを備え、
前記情報提供手段は、前記比較手段が算出した大小関係と前記第２比較手段が算出した大小関係とが異なる移動経路について、第２時間算出手段によって算出された所要時間に基づく所要時間情報を提供する
ことを特徴とする請求項１に記載の所要時間情報提供装置。
【請求項１６】
２地点間を結ぶ複数の異なる移動経路があった場合、各移動経路を通って移動体が２地点間を移動するために必要な所要時間に関する情報である所要時間情報を、所定の移動経路について提供する所要時間情報提供方法であって、
所定の間隔で取得された時刻と、前記各時刻に移動体が位置していた地点との組で表される移動履歴を蓄積する履歴蓄積ステップと、
前記履歴蓄積ステップで蓄積された地点を時刻の順に結んで表される複数の移動経路のうちから、２以上の前記移動経路に共通する２地点を結ぶ複数の異なる移動経路を抽出する経路抽出ステップと、
前記経路抽出ステップによって抽出された前記移動経路ごとに、前記２地点間の移動に要する所要時間情報を算出する情報算出ステップと、
算出された前記所要時間情報を前記移動体の現在位置に関連付けて利用者に提供する情報提供ステップと
を含むことを特徴とする所要時間情報提供方法。
【請求項１７】
２地点間を結ぶ複数の異なる移動経路があった場合、各移動経路を通って移動体が２地点間を移動するために必要な所要時間に関する情報である所要時間情報を、所定の移動経路について提供する所要時間情報提供装置のためのプログラムであって、
コンピュータに所定の間隔で取得された時刻と、前記各時刻に移動体が位置していた地点との組で表される移動履歴を蓄積する履歴蓄積ステップと、前記履歴蓄積ステップで蓄積された地点を時刻の順に結んで表される複数の移動経路のうちから、２以上の前記移動経路に共通する２地点を結ぶ複数の異なる移動経路を抽出する経路抽出ステップと、前記経路抽出ステップによって抽出された前記移動経路ごとに、前記２地点間の移動に要する所要時間情報を算出する情報算出ステップと、算出された前記所要時間情報を前記移動体の現在位置に関連付けて利用者に提供する情報提供ステップとを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動体の所定の経路に関する所要時間情報を提供する技術、特に、カーナビゲーション装置などの所要時間情報提供装置及びその方法に関するものである。
【背景技術】
【０００２】
現在、カーナビゲーション装置や携帯電話などのモバイル端末において、ユーザの移動経路の渋滞情報、通過時刻、到着時刻といった所要時間に関連する情報が提供されている。目的地に向かう移動時間をできるだけ小さくしたいというニーズがあるからである。図４２は、２地点間を結ぶ複数経路の例を示す図である。例えば、図４２のように所定の地点αから所定の地点βに向かう経路が、ＡルートとＢルートのように複数存在する場合、各経路を通って地点βに至るまでの所要時間に関連する情報は、ユーザがどちらの経路を通るかを決定する判断材料として有用である。どちらの経路を通ると所要時間が小さいのかをユーザが容易に比較できるからである。例えば特許文献１では、ユーザによって設定された目的地について、端末によって設定された経路とユーザの走行履歴から抽出した経路（すなわち、以前にユーザが走行したことがある経路）との間の所要時間比較情報を提供する。
【特許文献１】特開２００２−９０１６８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、特許文献１では、ユーザが目的地を設定しないと、所要時間情報が表示されないという問題があった。ユーザが目的地を設定しないと、ユーザがどの経路とどの経路の所要時間を比較したいのかがわからない。また、ユーザが目的地を設定したとしても、ユーザは本当に端末によって設定された経路を通るかどうか迷っているとは限らない。ユーザにとって端末によって設定された経路が、ユーザが通ったことがない経路であったとき、ユーザは設定された経路を通ろうとは思っていない場合があり、設定された経路と他の経路を比較したいとは考えていない可能性がある。モバイル端末において、ユーザに要らない情報を提供することは、運転、仕事などのユーザのタスクの妨げになることやユーザに必要な他の情報の提供の妨げになることがある。このため、情報はできるだけフィルタリングして効率よく提供する必要がある。
【０００４】
そこで本発明では、どちらの経路を通ると所要時間が小さいかを比較したいとユーザが考えている経路を抽出し、その経路に関する所要時間情報を提供することを目的とする。すなわち、ユーザが目的地を設定しなくても、現在位置の前途に、同じ地点に移動するための複数の異なる経路がある場合には、それぞれの経路について所要時間情報を提供することを目的とする。所要時間情報とは、渋滞情報、通過、到着時刻、所要時間、どちらの経路を通ると早いかを示すような所要時間の大小関係や差の情報である。
【課題を解決するための手段】
【０００５】
上記課題を解決するために、本発明の所要時間情報提供装置は、２地点間を結ぶ複数の異なる移動経路があった場合、各移動経路を通って移動体が２地点間を移動するために必要な所要時間に関する情報である所要時間情報を、所定の移動経路について提供する所要時間情報提供装置であって、所定の間隔で取得された時刻と、前記各時刻に移動体が位置していた地点との組で表される移動履歴を蓄積する履歴蓄積手段と、前記履歴蓄積手段に蓄積されている地点を時刻の順に結んで表される複数の移動経路のうちから、２以上の前記移動経路に共通する２地点を結ぶ複数の異なる移動経路を抽出する経路抽出手段と、前記経路抽出手段によって抽出された前記移動経路ごとに、前記２地点間の移動に要する所要時間情報を算出する情報算出手段と、算出された前記所要時間情報を前記移動体の現在位置に関連付けて利用者に提供する情報提供手段とを備えることを特徴とする。
【発明の効果】
【０００６】
以上のように本発明によれば、ユーザが過去に通ったことがある経路は、ユーザがその経路について知っているため、ユーザが通る経路を決めるときの候補の一つとなりうる。そのため本発明では、車両の存在地点と時刻からなる走行履歴から、ユーザが所定の地点から所定の地点に向かうときに異なる経路を通ったことがあるもの、具体的には分岐点と合流点、それらを結ぶ複数の経路を抽出することで、同じ場所に向かうときでも異なる経路を通る可能性があるものを抽出する。そして車両の位置から、車両が分岐点と合流点を通る可能性があるときに、抽出した経路の所要時間情報を通知する。これにより、ユーザがどちらの経路を通ると所要時間が小さいかを比較したいとユーザが考えている経路の所要時間情報を提供することができる。このため、ユーザはどちらの経路を通るとより早く目的地に到着できるかがわかり、通る経路を決定することができる。
【発明を実施するための最良の形態】
【０００７】
（実施の形態１）
図１は本実施の形態の所要時間情報提供装置の構成を示すブロック図である。図１の所要時間情報提供装置は、蓄積した走行履歴から、２地点間を結ぶ異なる経路を抽出し、それぞれの経路に関する所要時間情報を通知する所要時間情報提供装置であって、地点取得部１０１、時刻取得部１０２、履歴蓄積部１０３、地図蓄積部１０４、ノード抽出部１１１、経路抽出部１０５、仮定部１１２、分割部１１３、判定部１１４、情報取得部１０７、情報算出部１０８、通知部１０９及び情報提供部１１０を備えている。以下、まず各構成要素について図を用いて説明し、後に本所要時間情報提供装置の動作について説明する。
【０００８】
地点取得部１０１は、ＧＰＳアンテナまたはＩＣタグ、基地局通信、画像認識等により、車両の現在の存在地点を検知する。例えば、東経「１３４．５．５９．９」、北緯「３４．５．１５．６」のように車両の経度、緯度の情報を検知する。
【０００９】
時刻取得部１０２は、装置内の時計や、ＧＰＳアンテナにより現在時刻を取得する。例えば「２００６年４月２０日１１時１３分２０秒」のように年月日時分秒を取得する。
【００１０】
ここで、地点取得部１０１と時刻取得部１０２とは、現在時刻と前記移動体の現在位置との組を取得する現在位置取得手段の一例である。
【００１１】
履歴蓄積部１０３は、所定の間隔で取得された時刻と、前記各時刻に移動体が位置していた地点との組で表される移動履歴を蓄積する履歴蓄積手段の一例であり、本実施の形態では地点取得部１０１が取得した車両の存在地点と時刻取得部１０２が取得した時刻の履歴を走行履歴として蓄積する。図２は、履歴蓄積部に蓄積された走行履歴の例を示す図である。例えば、図２のように１秒ごとに地点情報を時系列順に蓄積する。例えば、図２のＩＤ「００１」は時刻「９月２０日７時０分０秒」に車両が東経「１３４．５．２８．９」、北緯「３４．５．１５．７」の地点に存在していたことを示す。
【００１２】
地図蓄積部１０４は、道路のノードＩＤ、ノード存在位置や接続ノード、リンクＩＤといった地図情報を蓄積する。図３は、地図情報蓄積部に蓄積された地図情報の例を示す図である。例えば、図３のように、ノードＩＤ、ノード位置、接続ノード、ノード間を結ぶリンクＩＤが蓄積されている。図３のノードＩＤ「００１」はノード位置が経度「１３４．３．０．９」であり、緯度が「３４．６．３．６」であり、ノードＩＤ「００２」「００３」「００４」「００５」と接続している。また、リンクＩＤ「００１」は始点ノードＩＤ「００１」と終点ノードＩＤ「００２」を結ぶリンクであることを示す。
【００１３】
ノード抽出部１１１は、地図蓄積部１０４に蓄積された地図情報を参照し、履歴蓄積部１０３に蓄積された走行履歴から、時系列順に並べられたノードＩＤの系列を抽出する。つまり、走行履歴中の車両の存在地点と場所が一致する地図情報中のノードＩＤを時系列順に抽出する。具体的には、走行履歴中の地点から距離が閾値以内にある地図情報のノードＩＤを探索し、存在すれば抽出する。閾値は例えば、予め既定した道路幅、車両が１秒間に進む最大距離、ＧＰＳ誤差から決定する。ただし、直前に抽出したノードと同じノードＩＤは抽出しない。閾値の決定方法は、例えば、道路幅を２５ｍ、車両が１秒間に進む最大距離を、一般道の最高時速である時速６０ｋｍの車が１秒間に進む距離である６００００／３６００（＝約１７）ｍとし、ＧＰＳ誤差を１０ｍとすると、それらの和である５０（＝約５２）ｍとする。図４は、ノード抽出部がノード系列を抽出する例を示す図である。図４を例として説明する。簡易的に、経度２．２５秒を５０ｍ、緯度１．５秒を５０ｍとすると、図４の地図蓄積部１０４に蓄積されたノードのうち、ＩＤ００１の走行履歴（経度１３４．３．０．９、緯度３４．６．２．６）から閾値５０ｍ以内に存在するノードは、ノードＩＤ００１（緯度差１秒＜１．５秒）である。よってノードＩＤ００１を抽出する。ＩＤ００２の走行履歴について閾値５０ｍ以内に存在するノードは、ノードＩＤ００１であるが、直前に抽出したノードＩＤ００１と同一であるため、抽出しない。ＩＤ００３〜００６の走行履歴については閾値５０ｍ以内にノードが存在しないため抽出しない。ＩＤ００７の走行履歴（経度１３４．３．０．９、緯度３４．６．９．６）については閾値５０ｍ以内に存在するノードはノードＩＤ００３（経度１３４．３．０．９、緯度３４．６．１０．６）であるため、ノードＩＤ００３を抽出する。抽出したノードＩＤを走行履歴の時刻順に並べたノードＩＤ系列、図４の場合「００１→００３」を抽出する。
【００１４】
なお、地図蓄積部１０４の接続ノード情報から、接続されているノードＩＤのみを抽出するとなおよい。例えば、図３のように地図情報が蓄積されていたとき、ノードＩＤ００１から接続されているノードＩＤは、００２、００３、００４、００５である。よってノードＩＤ００１の直後は、００２、００３、００４、００５のうちいずれか一つしか抽出しない。
【００１５】
なお、ノードＩＤ系列の代わりにリンクＩＤ系列を抽出しても良い。
経路抽出部１０５は、前記履歴蓄積手段に蓄積されている地点を時刻の順に結んで表される複数の移動経路のうちから、２以上の前記移動経路に共通する２地点を結ぶ複数の異なる移動経路を抽出する経路抽出手段の一例であり、本実施の形態では、ノード抽出部１１１により抽出されたノードＩＤ系列、地図蓄積部１０４に蓄積された地図情報から、分岐点と合流点を示すノードＩＤ、及び分岐点と合流点を結ぶ複数の経路を示すノードＩＤ系列群を抽出する。図５は、分岐点、合流点、抽出経路の例を示す図である。例えば、ノード抽出部１１１が図５のような走行履歴のノードＩＤ系列（・・・→００１→００２→００３→００４→００７→・・・→００１→００２→００３→００５→００６→００４→００７→・・・）を抽出していた場合、分岐点（ノードＩＤ００３）、と合流点（ノードＩＤ００４）」、それらを結ぶ複数の経路を表すノード系列（Ａルート００３→００４）（Ｂルート００３→００５→００６→００４）を抽出する。経路抽出部１０５は仮定部１１２、分割部１１３、判定部１１４により構成される。
【００１６】
仮定部１１２は、抽出したノードＩＤ系列中に存在する任意のノードＩＤ二つを仮想分岐点ＩＤ、仮想合流点ＩＤとしてそれぞれ仮定する。これは抽出したノードＩＤ系列に存在する全てのノードＩＤについて行う。例えば、ノードＩＤ系列として「・・・→００１→００２→００３→００４→００７→・・・→００１→００２→００３→００５→００６→００７→・・・」が抽出されていたとき、仮想分岐点ＩＤを００１と合流点ＩＤを００２、仮想分岐点００１と仮想合流点ＩＤ００３、仮想分岐点００１と仮想合流点ＩＤ００４、・・・のように全ての組み合わせについて仮定する。
【００１７】
分割部１１３は、ノード抽出部１１１が抽出したノードＩＤ系列を分割し、仮定部１１２が仮定した仮想分岐点ＩＤと仮想合流点ＩＤを結ぶノードＩＤ系列を抽出する。具体的には、ノードＩＤ系列を前方から順に仮想分岐点ＩＤと一致するノードＩＤを探索する。見つかった場合、そのノードＩＤの直後から仮想合流点ＩＤと一致するノードＩＤを探索する。見つかった場合、仮想分岐点ＩＤと一致するノードＩＤから仮想合流点ＩＤと一致するノードＩＤまでの一連の系列を仮想分岐点ＩＤと仮想合流点ＩＤを結ぶノードＩＤ系列として抽出する。同様に、残りのノードＩＤ系列について抽出を繰り返し、仮想分岐点ＩＤと仮想合流点ＩＤを結ぶノードＩＤ系列を全て抽出する。
【００１８】
しかし、経路の中には同一の交差点ノードを二回以上通るような明らかに遠回りとなる余分な経路が存在する。図６は、遠回りとなる例を示す図である。例えば、図６のように仮想分岐点ＩＤ００３、仮想合流点ＩＤ００４を仮定したときに、それらを結ぶルートとしてＣルート（００３→００８→００９→００８→０１０→００４）が抽出できたとする。しかし、これはノード００９近傍に目的地が存在した、迷ったなどの理由でノード００８を二回通ったと考えられ、仮想分岐点ＩＤ００３、仮想合流点ＩＤ００４を結ぶ所要時間が最短の経路とは明らかに言えない。そこで、抽出するノードＩＤ系列は、同一のＩＤが二つ以上存在しない経路のみ抽出する。言い換えれば分岐点と合流点を一筆書きで結ぶような経路のみ抽出する。これにより、たとえ走行履歴に存在したとしても、ユーザが合流点に向かうときには一般的に通らない、同じノードを二度以上通る経路における所要時間情報をフィルタリングすることができるため、ユーザに余分な情報を与えて混乱させることがないという利点がある。
【００１９】
判定部１１４は、前記２地点のうち、複数の移動経路に分岐する地点を分岐点とし、複数の前記移動経路が合流する地点を合流点として、共通の分岐点と合流点とを結ぶ複数の移動経路のうち、移動経路同士で互いに一致する部分を含まない複数の移動経路を抽出する前記経路抽出手段の一例である。判定部１１４は、仮定部１１２が仮定した仮想分岐点と仮想合流点の真偽を判定し、分割部１１３が抽出したノードＩＤ系列群に対して、真に分岐点、合流点となっている分岐点、合流点、及びそれらを結ぶ複数の経路を示すノードＩＤ系列群を抽出する。具体的には、仮想分岐点から仮想合流点までの複数のノードＩＤ系列のうち、分岐点及び合流点以外のノードＩＤが一つも一致しないノードＩＤ系列の組み合わせが存在するときに真とする。組み合わせが存在しないときは別のノードＩＤが分岐点、合流点と考えられるため偽とする。また、判定部１１４は、共通の分岐点と合流点とを結ぶ複数の移動経路のうち、いずれの１つも同じ経路を２度以上含まない移動経路を抽出する前記経路抽出手段の一例である。図７は、判定部が偽と判定する分岐点、合流点の例を示す図である。例えば、図７のように、仮想分岐点ＩＤ００２、仮想合流点ＩＤ００４を仮定したときに、それらを一筆書きで結ぶ経路として、Ｄルート（００２→００３→００４）、Ｅルート（００２→００３→００５→００６→００４）の２種類が存在したとする。このとき、ノードＩＤ００３は、Ｄルート、Ｅルート共に存在する。よって、仮想分岐点ＩＤ００２は分岐点ではないため、偽と判定する。図８は、判定部が真と判定する分岐点、合流点の例を示す図である。しかし、図８のように、仮想分岐点ＩＤ００２、仮想分岐点ＩＤ００４を仮定したときに、それらを一筆書きで結ぶ経路として、Ｄルート（００２→００３→００４）、Ｅルート（００２→００３→００５→００６→００４）、Ｆルート（００２→０１１→００８→０１０→００４）の３種類が存在したとする。このとき、ノードＩＤ００３は、Ｄルート、Ｅルート共に存在するが、Ｆルートでは存在しない。このため仮想分岐点、仮想合流点を真と判定し、真と判定された仮想分岐点、仮想合流点を分岐点、合流点として、Ｄ，Ｅ，ＦルートのノードＩＤ系列と共に出力する。
【００２０】
情報取得部１０７は、ＶＩＣＳなどの外部ネットワーク媒体１０６から、道路リンクの所要時間情報を取得する。図９は、情報取得部が取得する所要時間情報の例を示す図である。例えば、図９のようにリンクＩＤ００１に対して所要時間９０秒といった所要時間情報を取得する。
【００２１】
情報算出部１０８は、前記経路抽出手段によって抽出された前記移動経路ごとに、前記２地点間の移動に要する所要時間情報を算出する情報算出手段の一例であり、本実施の形態では、情報取得部１０７が取得したリンクＩＤに対する所要時間情報、地図蓄積部１０４に蓄積されたリンクＩＤ情報を用いて、経路抽出部１０５が抽出した分岐点、合流点、分岐点と合流点を結ぶ複数の経路（ノードＩＤ系列）中の所要時間情報を算出する。算出する所要時間情報は、抽出した複数の経路のうち、どれか一つの経路の所要時間でもよいし、経路中の渋滞情報でもよい。また、抽出した複数の経路の所要時間の大小関係情報でも良い。算出した所要時間情報は抽出した分岐点と組にして出力する。また、情報算出部１０８は、分岐点と合流点との間の異なる複数の前記移動経路について、移動経路同士の所要時間の大小関係を表す所要時間情報を算出する前記情報算出手段の一例である。
【００２２】
図１０は、情報算出部が抽出した経路中の所要時間情報を算出する例を示す図である。例えば、図１０のように、分岐点ＩＤ００３、合流点ＩＤ００４について、Ａルート（００３→００４）、Ｂルート（００３→００５→００６→００４）のノードＩＤ系列が抽出されたとする。このとき、Ａルートの所要時間を算出すると、地図情報からノードＩＤ００３とノードＩＤ００４を結ぶリンクＩＤが０２０であり、情報取得部１０７が取得した情報からリンクＩＤ０２０の所要時間は６００秒である。よってＡルートの所要時間は６００秒である。次にＢルートの所要時間を算出すると、地図情報からノードＩＤ系列（００３→００５→００６→００４）に対応するリンクＩＤ系列は（０２１→０２２→０２３）である。取得情報からリンクＩＤ系列（０２１→０２２→０２３）の所要時間は、４８０秒（＝６０＋３６０＋６０）である。よって、Ｂルートの所要時間は４８０秒である。このことから、分岐点ＩＤ００３について、Ｂルートの方がＡルートよりも１２０秒（＝６００−４８０）早いという所要時間情報が算出される。
【００２３】
また、渋滞情報の取得手法について例により説明する。地図蓄積部にリンクＩＤに対してリンク距離と道路リンク種別を予め蓄積する。リンク距離はリンクの長さであり、道路リンク種別は一般道路、都市内高速道路、都市間高速道路を示す。例えば経路抽出部１０５が抽出したノードＩＤ系列に対応するリンクＩＤ系列のそれぞれのリンクＩＤについて、所要時間とリンク距離から時速を算出し、時速とリンク種別に対する渋滞の一般的な定義に従い、例えばリンクが一般道路であり、時速１０ｋｍ以下であれば渋滞と判別することで、経路中の渋滞情報を取得できる。
【００２４】
通知部１０９は、前記移動体の現在位置が、抽出された分岐点から所定の閾値以内の距離に近づいたとき算出された所要時間情報を提供する前記情報提供手段の一例であり、本実施の形態でば、地点取得部１０１が取得した車両の現在地点から閾値以内の距離に、経路抽出部が抽出した分岐点が存在するときに、その分岐点に関連する情報を通知可とする。具体的には通知可能となった分岐点ＩＤ（及び合流点ＩＤ）を出力する、閾値は、例えば情報通知後ユーザがどちらの経路を進むか考えるだけの余裕がある距離として、５ｋｍとする。
【００２５】
情報提供部１１０は、算出された前記所要時間情報を前記移動体の現在位置に関連付けて利用者に提供する情報提供手段の一例であり、本実施の形態では、通知部１０９が通知可能と判断した分岐点ＩＤに対して、情報算出部１０８が算出した所要時間情報のうち、分岐点ＩＤが一致する情報をユーザに提供する。図１１は、情報提供部が所要時間情報を提供する例を示す図である。例えば、図１１のように通知部１０９が通知可能と判断した分岐点がノードＩＤ００３であり、情報算出部１０８が算出した所要時間情報が分岐点ＩＤ００３に対して「Ｂルート（００３→００５→００６→００４）がＡルート（００３→００４）より１２０秒早い」、分岐点ＩＤ０２２に対して「Ｃルート（０２２→０２３→０２４）がＤルート（０２２→０２５→０２４）より２４０秒早い」であったとする。このとき、通知可能分岐点ＩＤ００３に対応する所要時間情報「Ｂルート（００３→００５→００６→００４）がＡルート（００３→００４）より１２０秒早い」を情報提供装置の画面に表示する。
【００２６】
本実施の形態のように、所要時間情報提供装置では、ノードに対する仮想分岐点及び仮想合流点の仮定と真偽判定により、分岐点、合流点を抽出する。これにより、走行履歴に存在し、ユーザが通る可能性のある全ての経路から、二地点間の異なる経路を全て抽出することができる。比較のために簡易的に異なる経路を算出する手法を説明する。経路抽出部１０５は、所定時間以上エンジンが停止していた地点を移動経路の出発地または移動先として、前記エンジン停止地点で移動履歴を区切って蓄積する前記履歴蓄積手段の一例であり、本実施の形態では、経路抽出部１０５が、ノード抽出部１１１が抽出した走行履歴を表すノードＩＤ系列を所定の始点と終点により分割したとする。例えば車両が駐車した地点、つまりエンジンをＯＮ、ＯＦＦした地点を始点、終点とする。そして、始点と終点が一致するノードＩＤ系列のうち、異なるノードＩＤが存在する系列を抽出することでも、異なる経路は抽出できる。しかし、分岐点、合流点は所定の始点、終点と一致するとは限らないため、別の始点、終点を持つノードＩＤ系列も用いないと、全ての異なる経路を抽出することはできない。図１２は、始点、終点が一致しないノードＩＤ系列からでも２地点間を結ぶ異なる経路を抽出できる例を示す図である。例えば、図１２のように、エンジンをＯＮ、ＯＦＦした地点がノードＩＤ０３０、０３３、０３１、００８であり、それを始点、終点としてノードＩＤ系列を分割したところ、Ａ''ルート（０３０→００１→００２→００３→００４→００７→０３３）とＢ''ルート（０３１→００１→００２→００３→００５→００６→００４→００７→０３２）に分割されたとする。このとき、Ａ''ルートにおける始点（０３０）、終点（０３３）と、Ｂ''ルートにおける始点（０３１）、終点（０３２）は一致しないため、異なる経路が抽出できない。しかし、本実施の形態のように分岐点と合流点を抽出することで、Ａルート（００３→００４）とＢルート（００３→００５→００６→００４）という分岐点（００３）と合流点（００４）を結ぶ異なるルートを抽出することができる。これにより、履歴に存在し、ユーザが通る可能性のある全てのルートを抽出できるため、ユーザが所要時間を比較したい経路を、より忠実に抽出し、情報を提供することができる。
【００２７】
また、本実施の形態のようにノードに対する分岐点合流点の仮定と真偽判定により、分岐点、合流点を抽出することで、実際に異なる経路の情報のみを提供することができる。これは特にルートの渋滞情報の提供に有効である。図１３は、異なる経路以外の渋滞情報も提供する例を示す図である。例えば、分岐点合流点の抽出を行わなかったとして、図１３のように走行履歴から二地点間の異なる経路Ａ'ルート（００１→００２→００３→００４→００７）とＢ'ルート（００１→００２→００３→００５→００６→００４→００７）が抽出できたとする。このとき、ノードＩＤ００１とノードＩＤ００３を結ぶルートはＡ'ルート、Ｂ'ルートの共通部分である。ユーザはノードＩＤ００７に向かう場合は、このルート（００１→００２→００３）以外のルートを通ろうとは通常考えていないため、このルート（００１→００２→００３）の渋滞情報を提供するより、共通しない部分（例えば００３→００４）のルートの渋滞情報を提供する方がユーザにとって好ましい。本実施の形態では、共通しないＡルート（００３→００４）とＢルート（００３→００５→００６→００４）の渋滞情報のみを提供することができる。もしくは、他の渋滞情報に比べて強調することができる。つまり本実施の形態ではユーザへの情報をフィルタリングできるため、ユーザが欲しいと思っている情報のみを提供することができる。
【００２８】
また、分岐点が算出できるため、車両の現在地点と分岐点の距離に応じて情報の提供タイミングを調整することができる。このため、現在位置が分岐点に近づいたときにユーザに警告し、ユーザに注意を促すこともできる。これにより、ユーザが欲するタイミングで情報を提供することができる。
【００２９】
図１４は、本発明の実施の形態における所要時間情報提供装置の動作の例を示すフローチャートである。以下、本実施の形態１の所要時間情報提供装置における各部の動作を、図１４のフローチャートを用いて説明する。
【００３０】
時刻取得部１０２は、現在時刻を取得する（ステップＳ１２０１）。地点取得部１０１は、車両の現在地点を取得する（ステップＳ１２０２）。履歴蓄積部１０３は、時刻取得部１０２が取得した現在時刻と、地点取得部１０１が取得した車両の現在地点を走行履歴として蓄積する（ステップＳ１２０３）。ノード抽出部１１１は、地図蓄積部１０４に蓄積された地図情報を参照し、履歴蓄積部１０３に蓄積された走行履歴から、時系列順に並べられたノードＩＤの系列を抽出する（ステップＳ１２０４）。仮定部１１２は、抽出したノードＩＤ系列中に存在する任意のノードＩＤ二つを仮想分岐点ＩＤ、仮想合流点ＩＤとしてそれぞれ仮定する（ステップＳ１２０５）。分割部１１３は、ノード抽出部１１１が抽出したノードＩＤ系列を分割し、仮定部１１２が仮定した仮想分岐点ＩＤと仮想合流点ＩＤを結ぶノードＩＤ系列群を抽出する（ステップＳ１２０６）。分割部１１３は、抽出したノードＩＤ系列群の中から、同一ノードを含まないノードＩＤ系列のみ抽出する（ステップＳ１２０７）。判定部１１４は、仮定部１１２が仮定した仮想分岐点と仮想合流点について、対応する分割部１１３が抽出したノードＩＤ系列群の中に、分岐点、合流点以外にノードＩＤが全て異なるノードＩＤ系列の組み合わせが存在するものについて、分岐点、合流点、及び分岐点と合流点を結ぶノードＩＤ系列群を抽出する（ステップＳ１２０８）。情報取得部１０７は、ＶＩＣＳなどの外部ネットワーク媒体１０６から、道路リンクの所要時間情報を取得する（ステップＳ１２０９）。情報算出部１０８は、情報取得部１０７が取得したリンクＩＤに対する所要時間情報、地図蓄積部１０４に蓄積されたリンクＩＤ情報を用いて、判定部１１４が抽出した分岐点と合流点を結ぶノードＩＤ系列中の所要時間情報を算出する（ステップＳ１２１０）。通知部１０９は、地点取得部１０１が取得した車両の現在地点から閾値以内の距離に、判定部１１４が抽出した分岐点が存在するかどうかの判定を行い（ステップＳ１２１１）、存在したときは、ステップＳ１２１２に進む（ステップＳ１２１１のＹｅｓ）。存在しなかったときは、ステップＳ１２０１に戻る（ステップＳ１２１１のＮｏ）。現在地点の近傍に分岐点が存在したとき、情報提供部１１０は、通知部１０９が現在地点の近傍に存在すると判定した分岐点に対して、情報算出部１０８が算出した所要時間情報のうち、分岐点が一致する情報をユーザに提供する（ステップＳ１２１２）。終了するか判定を行い（ステップＳ１２１３）、終了するならば、処理を終了する（ステップＳ１２１３のＹｅｓ）。終了しないならば、ステップＳ１２０１に戻る（ステップＳ１２１３のＮｏ）。
【００３１】
（実施の形態１の変形例１）
なお、実施の形態１では、経路抽出部１０５は、分岐点と合流点を結ぶ複数種類のノードＩＤ系列を抽出し、それらのノードＩＤ系列がユーザにとって所要時間を比較したい経路としていた。しかし、分岐点と合流点が一致するノードＩＤ系列でもユーザが比較したいと思っていない経路も存在する。信号が少ない地域など、右折、左折が困難ではない地域であれば実施の形態１の手法でも有効である。しかし特に右折、左折が困難である地域など、走行履歴中に分岐点と合流点を結ぶ複数の経路があったとしても、分岐点への進入方向もしくは合流点からの脱出方向が異なる場合、進入方向、脱出方向によって通る経路がユーザにとって決まっており、ユーザは比較したいと思っていない可能性が高い。図１５は、分岐点への進入方向、合流点からの脱出方向が異なる例を示す図である。例えば図１５のように、走行履歴中に、Ｇルート（・・・→０１１→００８→０１０→００４→００６→・・・）とＨルート（・・・０１２→００８→００３→００４→００７→・・・）が存在したとする。このとき、分岐点００８、合流点００４に対して、００８→０１０→００４（Ｇルートの一部）、００８→００３→００４（Ｈルートの一部）という２種類の異なるノードＩＤ系列が存在する。しかし、ユーザは右折、左折をできるだけ避けるという傾向があるため、分岐点００８に０１１方向から進入したときは００３を通ろうとは考えていない可能性がある。同様に、合流点００４から００７方向に脱出する場合は、０１０を通ろうとは考えていない可能性がある。つまり、走行履歴に存在しない進入方向、脱出方向に関しては、通る可能性が低い。そこで、走行履歴から分岐点に対する進入方向、合流点に対する脱出方向が一致する経路（ノードＩＤ系列群）のみ抽出する。これにより、ユーザが通る可能性があり、所要時間を比較したいと考えている経路の情報のみ提供することができる。
【００３２】
以下本実施の形態の手法について説明する。
図１６は、本実施の形態１の変形例１における所要時間情報提供装置の構成を示すブロック図である。同図に示すように、実施の形態１の変形例１における所要時間情報提供装置は、走行履歴中に分岐点と合流点を結ぶ複数の経路があったとしても、分岐点への進入方向もしくは合流点からの脱出方向が異なる経路を除外して所要時間情報を提供する所要時間情報提供装置である。前記実施の形態１で示した構成要素には同様の符号を付与し、説明を省略する。以下、まず各構成要素について図を用いて説明し、後に本装置の動作について説明する。
【００３３】
経路抽出部１４０５は、移動体が前記分岐点を通過する前の移動方向と前記合流点を通過する後の移動方向とのいずれもが、互いに一致する移動経路を抽出する前記経路抽出手段の一例であり、本実施の形態では、ノード抽出部１１１により抽出されたノードＩＤ系列、地図蓄積部１０４に蓄積された地図情報から、ユーザが通過する可能性の高い分岐点と合流点を示すノードＩＤ、及び分岐点と合流点を結ぶ複数の経路を示すノードＩＤ系列群を抽出する。経路抽出部１４０５は現在ノード抽出部１４１５、仮定部１４１２、分割部１４１３、判定部１４１４により構成される。
【００３４】
現在ノード抽出部１４１５は、ノード抽出部１１１が抽出したノードＩＤ系列から車両の現在地点に対応するノードＩＤ、つまりノードＩＤ系列のうち最後尾のノードＩＤを現在ノードとして抽出する。例えば、ノードＩＤ系列（・・・→０３０→０３１→０３２→０１１）が抽出されていたときは、現在ノードとして０１１を抽出する。
【００３５】
仮定部１４１２は、ノード抽出部１１１により抽出されたノードＩＤ系列において、現在ノード抽出部１４１５が抽出したノードＩＤの直後のノードＩＤを仮想分岐点として抽出する。これは分岐点への進入方向を考慮するためである。例えば、ノードＩＤ系列（・・・→０３２→０１１→００８→０１０→００４→００６→・・・）が抽出され、現在ノードが０１１であったときは００８を仮想分岐点として抽出する。また、ノードＩＤ系列において仮想分岐点の後に存在する任意のノードＩＤを仮想合流点として仮定する。例えば、現在ノードが０１１であり、ノードＩＤ系列（・・・→０３２→０１１→００８→０１０→００４→００６→・・・）が抽出されていたときは、００８や０１０、００４、００６、・・・を仮想合流点として抽出する。
【００３６】
分割部１４１３は、ノード抽出部１１１が抽出したノードＩＤ系列を分割し、仮定部１４１２が仮定した仮想分岐点ＩＤと仮想合流点ＩＤを結ぶノードＩＤ系列を抽出する。ただし、ノードＩＤ系列における仮想分岐点ＩＤの直前のノードＩＤが、現在ノード抽出部１４１５が抽出した現在ノードと一致するノードＩＤ系列のみ抽出する。また、ノードＩＤ系列における仮想合流点ＩＤの直後のノードＩＤについても合流点後ノードＩＤ抽出する。具体的には、ノードＩＤ系列を前方から順に仮想分岐点ＩＤと一致するノードＩＤを探索する。見つかった場合、そのノードＩＤの直後から仮想合流点ＩＤと一致するノードＩＤを探索する。見つかった場合、仮想分岐点ＩＤと一致するノードの直前のノードＩＤから仮想合流点ＩＤと一致するノードの直後のノードＩＤまでの一連の系列を仮想分岐点ＩＤと仮想合流点ＩＤを結ぶノードＩＤ系列として抽出する。ただし、分岐点への進入方向を考慮するため、仮想分岐点ＩＤと一致するノードの直前のノードＩＤが、現在ノード抽出部１４１５が抽出した現在ノードＩＤと一致するノードＩＤ系列のみ抽出する。例えば、現在ノードが０１１であり、仮想分岐点ＩＤが００８、仮想合流点ＩＤが００４、ノードＩＤ系列（・・・→０３２→０１１→００８→０１０→００４→００６→・・・）が抽出されていたときは、ノードＩＤ系列における仮想合流点ＩＤ００８の直前のノードＩＤが０１１であり、現在ノードＩＤ０１１と一致するため、ノードＩＤ系列「００８→０１０→００４」と合流点後ノードＩＤ００６を抽出する。同様に、残りのノードＩＤ系列について抽出を繰り返し、仮想分岐点ＩＤと仮想合流点ＩＤを結ぶノードＩＤ系列群、合流点ノードＩＤを全て抽出する。また、抽出するノードＩＤ系列は、同一のＩＤが二つ以上存在しない経路のみ抽出する。言い換えれば分岐点と合流点を一筆書きで結ぶような経路のみ抽出する。
【００３７】
判定部１４１４は、仮定部１４１２が仮定した仮想分岐点と仮想合流点の真偽を判定し、分割部１４１３が抽出したノードＩＤ系列群に対して、真に分岐点、合流点となっている分岐点、合流点、及びそれらを結ぶ複数の経路を示すノードＩＤ系列群を抽出する。具体的には、仮想分岐点から仮想合流点までの複数のノードＩＤ系列のうち、分岐点及び合流点以外のノードＩＤが一つも一致しないノードＩＤ系列の組み合わせが存在し、しかもそのノードＩＤ系列において合流点後ノードＩＤが一致するときに真とし、その組み合わせのノードＩＤ系列群のみ出力する。組み合わせが存在しないときは別のノードＩＤが分岐点、合流点と考えられるため偽とする。図１７は、判定部が同じ合流点後ＩＤの組み合わせを出力する例を示す図である。例えば図１７のように、仮想分岐点ＩＤ００８、仮想合流点ＩＤ００４を仮定したときに、それらを一筆書きで結ぶ経路として、Ｇルート（００８→０１０→００４）合流点後ＩＤ００６、Ｈルート（００８→００３→００４）合流点後ＩＤ００７、Ｉルート（００８→００４）合流点後ＩＤ００６の３種類が存在したとする。このとき、分岐点、合流点以外に一致するノードは存在しない。しかし、合流点後ＩＤが一致する組み合わせはＧルート（合流点後ＩＤ００６）とＩルート（合流点後ＩＤ００６）のみであるため、分岐点ＩＤ００８、合流点ＩＤ００４及びＧルートノードＩＤ系列（００８→０１０→００４）、ＩルートノードＩＤ系列（００８→００４）のみを出力する。これは、もしノードＩＤ００７に向かっている場合は、ユーザはＨルート（００８→００３→００４）を通ると決まっていて、所要時間を比較したいとは考えていない可能性が高いためである。しかしノードＩＤ００６に向かっている場合は、ユーザはＧルート（００８→０１０→００４）とＩルート（００８→００４）の双方を通る可能性があり、所要時間を比較したいとは考えている可能性が高い。
【００３８】
通知部１４０９は、判定部１４１４が現在ノードの直後にある分岐点を出力したときに、その分岐点に関連する情報を通知可とする。
【００３９】
図１８は、本発明の実施の形態１の変形例１における所要時間情報提供装置の動作の例を示すフローチャートである。以下、本実施の形態１の変形例１の所要時間情報提供装置の動作を、図１８のフローチャートを用いて説明する。実施の形態１で説明した処理については説明を省略する。
【００４０】
実施の形態１と同様に、ノード抽出部１１１がノードＩＤ系列を抽出した後（ステップＳ１２０４）、現在ノード抽出部１４１５は、ノード抽出部１１１が抽出したノードＩＤ系列から車両の現在地点のノードＩＤを抽出する（ステップＳ１６０５）。仮定部１４１２は、ノード抽出部１１１により抽出されたノードＩＤ系列において、現在ノード抽出部１４１５が抽出したノードＩＤの直後のノードＩＤを仮想分岐点として仮定する（ステップＳ１６０６）。仮定部１４１２は、ノードＩＤ系列において仮想分岐点の後に存在する任意のノードＩＤを仮想合流点として仮定する（ステップＳ１６０７）。分割部１４１３は、ノード抽出部１１１により抽出されたノードＩＤ系列について、前方から順に仮定部１４１２が仮定した仮想分岐点ＩＤと一致するノードＩＤを探索する（ステップＳ１６０８）。分割部１４１３は、ノードＩＤ系列において仮想分岐点ＩＤと一致するノードＩＤの直前のノードＩＤが、現在ノード抽出部１４１５が抽出した現在ノードＩＤと一致するかどうか判定を行い（ステップＳ１６０９）、一致したときは、ステップＳ１６１０に進む（ステップＳ１６０９のＹｅｓ）。現在ノードＩＤと一致しなかったときは、ステップＳ１６０８に戻る（ステップＳ１６０９のＮｏ）。分割部１４１３は、ノードＩＤ系列において、仮想分岐点ＩＤと一致するノードから仮想合流点ＩＤと一致するノードまでにＩＤが同一であるノードが含まれるかを判定し（ステップＳ１６１０）、含まれる場合は、ステップＳ１６０８に戻る（ステップＳ１６１０のＹｅｓ）。同一ノードが含まれない場合は、ステップＳ１６１１に進む（ステップＳ１６１０のＮｏ）。分割部１４１３は、ノード抽出部１１１により抽出されたノードＩＤ系列において仮想分岐点ＩＤと一致するノードから仮想合流点ＩＤと一致するノードまでのノードＩＤ系列及び仮想合流点ＩＤと一致するノードの直後のＩＤを合流点後ＩＤとして抽出する（ステップＳ１６１１）。分割部１４１３は、仮想分岐点ＩＤと一致するノードの探索が、ノード抽出部１１１により抽出されたノードＩＤ系列の終端まで行われたかどうかの判定を行い（ステップＳ１６１２）、探索が終端まで行われた場合は、ステップＳ１６１３に進む（ステップＳ１６１２のＹｅｓ）。探索が終端まで行われていない場合は、ステップＳ１６０８に戻る（ステップＳ１６１２のＮｏ）。判定部１４１４は、仮定部１４１２が仮定した仮想分岐点と仮想合流点について、対応する分割部１１３が抽出したノードＩＤ系列群の中に、分岐点、合流点以外にノードＩＤが全て異なるノードＩＤ系列の組み合わせが存在するものについて、分岐点、合流点、及ぶそれらを結ぶノードＩＤ系列群を抽出する（ステップＳ１６１３）。判定部１４１４は、抽出したノードＩＤ系列のうち、合流点後ノードＩＤが一致する組み合わせがあるノードＩＤ系列群のみを抽出する（ステップＳ１６１４）。情報取得部１０７は、ＶＩＣＳなどの外部ネットワーク媒体１０６から、道路リンクの所要時間情報を取得する（ステップＳ１６１５）。情報算出部１０８は、情報取得部１０７が取得したリンクＩＤに対する所要時間情報、地図蓄積部１０４に蓄積されたリンクＩＤ情報を用いて、判定部１４１４が抽出した分岐点と合流点を結ぶノードＩＤ系列中の所要時間情報を算出する（ステップＳ１６１６）。通知部１４０９は、判定部１４１４が抽出した分岐点が存在するかどうかの判定を行い（ステップＳ１６１７）、存在したときは、ステップＳ１６１８に進む（ステップＳ１６１７のＹｅｓ）。存在しなかったときは、ステップＳ１２０１に戻る（ステップＳ１６１７のＮｏ）。分岐点が存在したとき、情報提供部１１０は、情報算出部１０８が算出した所要時間情報をユーザに提供する（ステップＳ１６１８）。終了するか判定を行い（ステップＳ１６１９）、終了するならば、処理を終了する（ステップＳ１６１９のＹｅｓ）。終了しないならば、ステップＳ１２０１に戻る（ステップＳ１６１９のＮｏ）。
【００４１】
（実施の形態１の変形例２）
なお、実施の形態１では、走行履歴中に、分岐点から合流点までの異なるノードＩＤ系列が存在したときにユーザにとって所要時間を比較したい経路が存在するとしていた。寄り道を行わず、自宅と目的地の往復ばかり行うユーザに対しては、実施の形態１は有効である。しかし、自宅と目的地の間に別の目的地（経由地）に立ち寄るユーザもいる。このようなユーザは同じ地点に対して向かうときにも店舗や自宅、会社といった目的地（経由地）ランドマークを訪問するために、異なるノードＩＤ系列を通ることもある。図１９は、ランドマークを訪問するために異なる経路を通る例を示す図である。例えば図１９のように、分岐点００３と合流点００４を結ぶ経路は、Ｊルート（００３→００４）とＫルート（００３→００８→０１２→０１３→０１０→００４）の二つの経路が走行履歴として存在したとする。しかし、この場合、ノードＩＤ系列（Ｋルート）はランドマークを訪問するために通っているのであり、そのノードＩＤ系列（Ｋルート）がユーザにとって所要時間を比較したい経路ではない可能性が高い。そこで、ランドマークに駐車したかどうかを判定し、ランドマークに駐車するごとに走行履歴を分割する。これにより、ランドマークを訪問するために通過したノードＩＤ系列を削除することができる。例えばノードＩＤ系列が・・・→００３→００８→０１２→（駐車）→０１３→０１０→００４→・・・の場合、・・・→００３→００８→０１２と０１３→０１０→００４→・・・に分割する。これにより、一般的に所定の地点に向かう場合にユーザが欲する、どこも経由せずに所定の地点に対して直接向かう経路の情報のみ提供することができる。
【００４２】
（実施の形態１の変形例３）
なお、実施の形態１では、道路の交差点を表すノードＩＤのみを分岐点、合流点として扱っていた。しかし、ユーザが出発、到着したランドマーク、具体的に駐車したランドマークも分岐点、合流点となりうる。図２０は、ランドマークが分岐点となる例を示す図である。例えば、図２０の場合、ランドマーク「Ｌ００１」を出発し、合流点００４に向かう場合でも、Ｌルート（Ｌ００１→００２→００３→００４）、Ｍルート（Ｌ００１→０１４→００８→００４）の二種類の走行履歴が存在したとする。このとき、ユーザは分岐点Ｌ００１を出発したときは、ＬルートとＭルートの双方とも通る可能性があり、所要時間を比較したい経路である可能性が高い。合流点がランドマークである場合も同様である。よってこのような経路においても情報を提供するために、ランドマークに駐車したかどうかを判定し、ランドマークに駐車したときは駐車したランドマークに対して「Ｌ００１」などのノードＩＤを付与する。これにより、ランドマークが分岐点、合流点となる場合も情報を提供することができるため、ユーザがどちらを通るか迷っている、より多くの経路について情報を提供することができる。
【００４３】
なお、実施の形態１の変形例１では分岐点への進入方向、合流点からの脱出方向も考慮していた。しかし、分岐点、合流点がランドマークの場合は、駐車によって一旦走行が途絶えるため、方向を考慮する必要がない。よって分岐点、合流点がランドマークであった場合は、分岐点前ノード、合流点後ノードＩＤの一致判定を行わない。逆にランドマーク以外のノードＩＤであった場合は、分岐点前ノード、合流点後ノードＩＤの一致判定を行う。これにより、ユーザがどちらの経路を通るか迷っている経路の情報をより正確に提供することができる。
【００４４】
（実施の形態１の変形例４）
なお、実施の形態１においては車両の現在地点の近傍に分岐点があったときに所要時間情報を提供していた。しかし、現在地点の近傍に分岐点があったとしても、車両が分岐点を通るとは限らない。また、分岐点を通ったとしても車両は合流点に向かっていない可能性もある。つまりユーザが求めていない情報を提供する可能性がある。また、実施の形態１の変形例１においては、車両の現在ノード（交差点）の直後に分岐点を通る履歴があったときに、所要時間情報を提供していた。しかし、分岐点の直前の交差点で異なる経路に関する情報を提供されたとしても、運転に慣れていない人や交差点が密集した道路などでは、どちらの経路を通るか考える時間の余裕がない場合もある。そこで、車両の移動経路を幾つか予測することによって、実際に車両が分岐点の直前ノードを通るより前に、車両が分岐点、合流点を通る可能性が高いことを判断し、分岐点と合流点を通る異なる経路の所要時間情報を提供することができる。このためユーザは提供された情報を判断材料とし、余裕をもってどちらの経路を通るかを判断できる。また、実際にユーザが通る分岐点、合流点の情報のみをより正確に提供することができる。
【００４５】
以下本実施の形態の手法について説明する。
図２１は、本実施の形態における所要時間情報提供装置の構成を示すブロック図である。前記実施の形態１で示した構成要素には同様の符号を付与し、説明を省略する。以下、まず各構成要素について図を用いて説明し、後に本装置の動作について説明する。
【００４６】
駐車検知部１９１６は、車両が駐車状態にあることを検知する。駐車状態とは、車両の位置が閾値以上の時間固定されているということである。特に、車両は車の場合、車のエンジンが切られているときに駐車状態と検知する。ただし、アイドリングストップを行っている可能性もあるため、車のエンジンが一定時間以上切られていたときに、駐車状態であると検知する。実施の形態１の変形例２における駐車状態検知も同様である。
【００４７】
履歴蓄積部１９０３は、地点取得部１０１が取得した車両の存在地点と時刻取得部１０２が取得した時刻の履歴を走行履歴として蓄積する。ただし、駐車検知部１９１６が駐車状態を検知するごとに履歴を分割して蓄積する。つまり、車両の出発地からの出発地から目的地への到着までの走行履歴を蓄積する。ただし、最新の履歴については出発地から車両の現在地までの走行履歴が蓄積される。
【００４８】
図２２は、履歴蓄積部に蓄積された走行履歴の例を示す図である。例えば、図２２のように１秒ごとに地点情報を時系列順に出発から到着までを一組として蓄積する。例えば、図２のＩＤ「０００１」は時刻「９月２０日７時０分０秒」に車両が東経「１３４．５．２８．９」、北緯「３４．５．１５．７」の地点を出発したことを示す。
【００４９】
ランドマーク蓄積部１９１７は、店舗や自宅、会社といったランドマークのＩＤとランドマークの位置といったランドマーク情報を蓄積する。図２３は、ランドマーク蓄積部に蓄積されたランドマーク情報の例を示す図である。例えば、図２３のランドマークＩＤ「Ｌ００１」は位置が経度「１３４．３．０．９」であり、緯度が「３４．６．２．５」であることを示す。実施の形態１の変形例２、３における駐車状態による履歴分割、ランドマークノード取得も同様である。
【００５０】
ノード抽出部１９１１は、地図蓄積部１０４に蓄積された地図情報、ランドマーク蓄積部１９１７に蓄積されたランドマーク情報を参照し、履歴蓄積部１９０３に蓄積された走行履歴から、時系列順に並べられたノードＩＤの系列を抽出する。ノードＩＤには道路の交差点だけではなく、ランドマークＩＤも含まれる。履歴蓄積部１９０３には、出発地から目的地もしくは現在地までの走行履歴が複数蓄積されている。よって、蓄積された走行履歴全てについてノードＩＤ系列に変換を行い、出発地から目的地までのノードＩＤ系列を複数出力する。具体的に変換手法を説明する。駐車状態を検知するごとに分割して蓄積された走行履歴における始点と終点、つまり出発地と目的地については、走行履歴における地点から、最も近い位置に存在するランドマークＩＤを抽出する。ただし、最新の履歴の終点は現在地を表すため、ランドマークは抽出しない。出発地、目的地以外の走行履歴に関しては、走行履歴の地点から距離が閾値以内にある地図情報のノードＩＤを探索し、存在すれば抽出する。ただし、直前に抽出したノードと同じノードＩＤは抽出しない。図２４は、ノード抽出部がノード系列を抽出する例を示す図である。図２４を例として説明する。簡易的に、経度２．２５秒を５０ｍ、緯度１．５秒を５０ｍとすると、図２４の出発地を表すＩＤ００１の走行履歴（経度１３４．３．０．９、緯度３４．６．２．６）から最も近い位置にあるランドマークは、Ｌ００１（経度１３４．３．０．９、緯度３４．６．２．５）である。よってノードＩＤＬ００１を抽出する。また、ＩＤ００２の走行履歴について閾値５０ｍ以内に存在するノードは、ノードＩＤ００１である。よってノードＩＤ００１を抽出する。ＩＤ００３〜００６の走行履歴については閾値５０ｍ以内にノードが存在しないため抽出しない。ＩＤ００７の走行履歴（経度１３４．３．０．９、緯度３４．６．９．６）については閾値５０ｍ以内に存在するノードはノードＩＤ００３（経度１３４．３．０．９、緯度３４．６．１０．６）であるため、ノードＩＤ００３を抽出する。目的地を表すＩＤ０１０の走行履歴（経度１３４．３．０．９、緯度３４．６．１２．６）から最も近い位置にあるランドマークは、Ｌ００３（経度１３４．３．０．９、緯度３４．６．１２．９）である。よってＬ００３を抽出する。抽出したノードＩＤを走行履歴の時刻順に並べたノードＩＤ系列、図２４の場合「Ｌ００１→００１→００３→Ｌ００３」を抽出する。同様に、全ての出発地から目的地までの走行履歴に着いてノード系列変換を行う。実施の形態１の変形例２、３における分割された履歴、駐車ランドマークに対するノードＩＤ系列変換も同様である。
【００５１】
移動先ノード予測部１９１８は、前記履歴蓄積手段に蓄積されている前記移動履歴から、前記移動体の移動先（目的地）を予測する移動先予測手段の一例であり、前記履歴蓄積手段に蓄積されている地点を時刻の順に結んで表される複数の移動経路のうち、出発地から現在位置までの移動経路が一致する移動経路のいずれかを、現在の移動先に至る移動経路と予測する前記移動先予測手段の一例である。移動先ノード予測部１９１８は、本実施の形態では、ノード抽出部１９１１により抽出されたノードＩＤ系列を用いて、移動先の経路を表すノードＩＤ系列を予測する。具体的には最新の走行履歴から変換されたノードＩＤ系列、つまり出発地から現在地までのノードＩＤ系列を抽出する。出発地から現在地までのノードＩＤ系列が完全に含まれる過去のノードＩＤ系列を抽出し、同一のノードＩＤ系列が最も多い系列における現在地以降の系列を移動先の経路を表すノードＩＤ系列とする。図２５は、移動先ノードＩＤ系列を予測する例を示す図である。図２５の場合、最新のノードＩＤ系列、つまり出発地から現在地までのノードＩＤ系列は「Ｌ００１→００１」である。このノードＩＤ系列が完全に含まれるノードＩＤ系列を抽出し、同一のノード系列を集計すると、系列「Ｌ００１→００１→００２→００３→００５→００６→００４→Ｌ００７」が１つ、「Ｌ００１→００１→００２→００３→００４→Ｌ００７」が３つ、「Ｌ００１→００１→００２→００８→００９→Ｌ０１０」が１つ存在する。よって、最も履歴数の多い「Ｌ００１→００１→００２→００３→００４→Ｌ００７」の系列を用いる。この系列のうち、最新のノードＩＤ系列「Ｌ００１→００１」に含まれない部分、つまり、「００２→００３→００４→Ｌ００７」が現在以降、車両が通過すると予測される経路であるため、「００２→００３→００４→Ｌ００７」を予測ノードＩＤ系列として出力する。
【００５２】
経路抽出部１９０５は、移動先ノード予測部１９１８によって予測された予測ノードＩＤ系列、ノード抽出部１９１１により抽出されたノードＩＤ系列から、分岐点と合流点を示すノードＩＤ、及び分岐点と合流点を結ぶ複数の経路を示すノードＩＤ系列群を抽出する。経路抽出部１９０５は仮定部１９１２、分割部１９１３、判定部１９１４により構成される。
【００５３】
仮定部１９１２は、移動先ノード予測部１９１８によって予測された予測ノードＩＤ系列中に存在する任意のノードＩＤ二つを仮想分岐点ＩＤ、仮想合流点ＩＤとしてそれぞれ仮定する。ただし仮想合流点ＩＤはノードＩＤ系列において仮想分岐点ＩＤの後に位置する。また、分岐、合流の方向も考慮するため、予測ノードＩＤ系列における仮想分岐点の直前のノードＩＤを分岐前ＩＤとして、仮想合流点の直後のノードＩＤを合流後ＩＤとして抽出する。しかし、仮想分岐点ＩＤ、仮想合流点ＩＤがランドマークＩＤであったとき、つまり出発地、目的地であった場合には、方向性は考慮しないため、分岐前ＩＤ、合流後ＩＤは抽出しない。また、分岐前ＩＤ、合流後ＩＤがランドマークＩＤであったときは方向性の検出が困難であるため抽出しない。また、予測ノードＩＤ系列のうち、最も手前のノードＩＤつまり、次に通過すると予測されるノードＩＤを分岐点として仮定するときは、分岐前ＩＤは現在ノードＩＤつまり、ノード抽出部１９１１により抽出されたノードＩＤ系列のうち最新のノードＩＤとなる。
【００５４】
これは抽出したノードＩＤ系列に存在する全てのノードＩＤについて行う。例えば、現在地を表す最新のノードＩＤが００１であり、予測ノードＩＤ系列として「００２→００３→００４→Ｌ００７」が抽出されていたとき、仮想分岐点ＩＤ００２と分岐前ＩＤ００１と仮想合流点ＩＤ００３と合流後ＩＤ００４、仮想分岐点ＩＤ００２と分岐前ＩＤ００１と仮想合流点ＩＤ００４、仮想分岐点ＩＤ００２と仮想合流点ＩＤＬ００７、仮想分岐点ＩＤ００３と分岐前ＩＤ００２と仮想合流点ＩＤ００４、仮想分岐点ＩＤ００３と分岐前ＩＤ００２と仮想合流点ＩＤＬ００７、仮想分岐点ＩＤ００４と分岐前ＩＤ００３と仮想合流点ＩＤＬ００７を仮定する。
【００５５】
分割部１９１３は、ノード抽出部１９１１が抽出した出発地から目的地までの複数のノードＩＤ系列から、仮定部１９１２が仮定した仮想分岐点ＩＤと仮想合流点ＩＤを結ぶノードＩＤ系列を抽出する。ただし、分岐前ＩＤ、分岐後ＩＤが仮定されているときは、ノードＩＤ系列における仮想分岐点ＩＤの直前のノードＩＤが、分岐前ＩＤと一致し、ノードＩＤ系列における仮想分岐点ＩＤの直後のノードＩＤが、分岐後ＩＤと一致するノードＩＤ系列のみ抽出する。具体的には、ノードＩＤ系列を前方から順に分岐点前ＩＤと仮想分岐点ＩＤが連続で一致するノードＩＤを探索する。見つかった場合、そのノードＩＤの直後から分岐点後ＩＤと仮想合流点ＩＤが連続で一致するノードＩＤを探索する。見つかった場合、仮想分岐点ＩＤと一致するノードＩＤから仮想合流点ＩＤと一致するノードＩＤまでの一連の系列を仮想分岐点ＩＤと仮想合流点ＩＤを結ぶノードＩＤ系列として抽出する。見つからなかった場合は別のノードＩＤ系列について再び初めから探索を行う。ただし抽出するノードＩＤ系列は、同一のＩＤが二つ以上存在しない経路のみ抽出する。言い換えれば分岐点と合流点を一筆書きで結ぶような経路のみ抽出する。
【００５６】
判定部１９１４は、仮定部１９１２が仮定した仮想分岐点と仮想合流点の真偽を判定し、分割部１９１３が抽出したノードＩＤ系列群に対して、真に分岐点、合流点となっている分岐点、合流点、及びそれらを結ぶ複数の経路を示すノードＩＤ系列群を抽出する。具体的には、仮想分岐点から仮想合流点までの複数のノードＩＤ系列のうち、分岐点及び合流点以外のノードＩＤが一つも一致しないノードＩＤ系列の組み合わせが存在するときに真とし、その組み合わせのノードＩＤ系列群のみ出力する。組み合わせが存在しないときは別のノードＩＤが分岐点、合流点と考えられるため偽とする。
【００５７】
通知部１９０９は、判定部１９１４が分岐点を出力したときに、その分岐点に関連する情報を通知可とする。
【００５８】
ここで、情報提供部１１０は、前記移動先予測手段によって予測された移動先までの移動経路上に、前記経路抽出手段によって抽出された複数の移動経路がある場合、前記分岐点と前記合流点とを結ぶ異なる移動経路についての所要時間情報を提供する前記情報提供手段の一例である。
【００５９】
図２６は、本発明の実施の形態１の変形例４における所要時間情報提供装置の動作の例を示すフローチャートである。以下、本実施の形態１の変形例４のフローチャートを、図２６を用いて説明する。実施の形態１で説明した処理については説明を省略する
実施の形態１と同様に、履歴蓄積部１９０３は、地点取得部１０１が取得した車両の存在地点と時刻取得部１０２が取得した時刻の履歴を走行履歴として蓄積した後（ステップＳ１２０３）、駐車検知部１９１６が駐車状態であるか否かを検知する（ステップＳ２４０４）。駐車状態を検知したときは、ステップＳ２４０５に進む（ステップＳ２４０４のＹｅｓ）。駐車状態を検知しなかったときは、ステップＳ２４０６に進む（ステップＳ２４０４のＮｏ）。駐車状態を検知したとき、履歴蓄積部１９０３は、走行履歴を分割し（ステップＳ２４０５）、ステップＳ１２０１に戻る。駐車状態を検知しなかったとき、ノード抽出部１９１１は、地図蓄積部１０４に蓄積された地図情報、ランドマーク蓄積部１９１７に蓄積されたランドマーク情報を参照し、履歴蓄積部１９０３に蓄積された走行履歴から、時系列順に並べられたノードＩＤの系列を抽出する（ステップＳ２４０６）。移動先ノード予測部１９１８は、ノード抽出部１９１１により抽出されたノードＩＤ系列のうち、最新のノードＩＤ系列、つまり出発地から現在地までのノードＩＤ系列を抽出する（ステップＳ２４０７）。移動先ノード予測部１９１８は、ノード抽出部１９１１により抽出されたノードＩＤ系列の中から、最新のノードＩＤ系列を含むノード系列を抽出し、同一ノード系列を集計する（ステップＳ２４０８）。移動先ノード予測部１９１８は、抽出したノードＩＤ系列のうち、最も履歴数の多いノード系列について、最新のノードＩＤ系列に含まれない部分を予測ノード系列として出力する（ステップＳ２４０９）。仮定部１９１２は、移動先ノード予測部１９１８によって予測された予測ノードＩＤ系列中に存在する任意のノードＩＤ二つを仮想分岐点ＩＤ、仮想合流点ＩＤとしてそれぞれ仮定し、仮想分岐点ＩＤの直前に存在するノードＩＤを分岐点前ＩＤ、仮想合流点ＩＤの直後に存在するノードＩＤを合流点後ＩＤとして仮定する（ステップＳ２４１０）。分割部１９１３は、ノード抽出部１９１１により抽出されたノードＩＤ系列について、前方から順に仮定部１９１２が仮定した仮想分岐点ＩＤと一致するノードＩＤを探索する（ステップＳ２４１１）。分割部１９１３は、ノード抽出部１９１１により抽出されたノードＩＤ系列において仮想分岐点ＩＤと一致するノードＩＤの直前のノードＩＤが、仮定部１９１２が仮定した分岐点前ＩＤと一致するかどうか判定を行い（ステップＳ２４１２）、一致したときは、ステップＳ２４１３に進む（ステップＳ２４１２のＹｅｓ）。一致しなかったときは、ステップＳ２４１１に戻る（ステップＳ２４１２のＮｏ）。分割部１９１３は、ノードＩＤ系列において、仮想分岐点ＩＤと一致するノードから仮想合流点ＩＤと一致するノードまでにＩＤが同一であるノードが含まれるかを判定し（ステップＳ２４１３）、含まれる場合は、ステップＳ２４１１に戻る（ステップＳ２４１３のＹｅｓ）。同一ノードが含まれない場合は、ステップＳ２４１４に進む（ステップＳ２４１３のＮｏ）。分割部１９１３は、ノード抽出部１９１１により抽出されたノードＩＤ系列において仮想合流点ＩＤと一致するノードＩＤの直後のノードＩＤが、仮定部１９１２が仮定した合流点後ＩＤと一致するかどうか判定を行い（ステップＳ２４１４）、一致したときは、ステップＳ２４１５に進む（ステップＳ２４１４のＹｅｓ）。一致しなかったときは、ステップＳ２４１１に戻る（ステップＳ２４１４のＮｏ）。分割部１９１３は、ノード抽出部１９１１により抽出されたノードＩＤ系列において仮想分岐点ＩＤと一致するノードから仮想合流点ＩＤと一致するノードまでのノードＩＤ系列を抽出する（ステップＳ２４１５）。分割部１９１３は、仮想分岐点ＩＤと一致するノードの探索が、ノード抽出部１９１１により抽出された全てのノードＩＤ系列で行われたかどうかの判定を行い（ステップＳ２４１６）、探索が全てのノードＩＤ系列まで行われた場合は、ステップＳ２４１７に進む（ステップＳ２４１６のＹｅｓ）。探索が全てのノードＩＤ系列まで行われていない場合は、ステップＳ２４１１に戻る（ステップＳ２４１６のＮｏ）。判定部１９１４は、仮定部１９１２が仮定した仮想分岐点と仮想合流点について、対応する分割部１９１３が抽出したノードＩＤ系列群の中に、分岐点、合流点以外にノードＩＤが全て異なるノードＩＤ系列の組み合わせが存在するものについて、分岐点、合流点、及ぶそれらを結ぶノードＩＤ系列群を抽出する（ステップＳ２４１７）。情報取得部１０７は、ＶＩＣＳなどの外部ネットワーク媒体１０６から、道路リンクの所要時間情報を取得する（ステップＳ２４１８）。情報算出部１０８は、情報取得部１０７が取得したリンクＩＤに対する所要時間情報、地図蓄積部１０４に蓄積されたリンクＩＤ情報を用いて、判定部１９１４が抽出した分岐点と合流点を結ぶノードＩＤ系列中の所要時間情報を算出する（ステップＳ２４１９）。通知部１９０９は、判定部１９１４が抽出した分岐点が存在するかどうかの判定を行い（ステップＳ２４２０）、存在したときは、ステップＳ２４２１に進む（ステップＳ２４２０のＹｅｓ）。存在しなかったときは、ステップＳ１２０１に戻る（ステップＳ２４２０のＮｏ）。分岐点が存在したとき、情報提供部１１０は、情報算出部１０８が算出した所要時間情報をユーザに提供する（ステップＳ２４２１）。終了するか判定を行い（ステップＳ２４２２）、終了するならば、処理を終了する（ステップＳ２４２２のＹｅｓ）。終了しないならば、ステップＳ１２０１に戻る（ステップＳ２４２２のＮｏ）。
【００６０】
なお、上記実施の形態では、一組の分岐点と合流点との間の移動経路についてだけ所要時間情報を通知していた。例えば、実施の形態１では、通知部１０９は、地点取得部１０１が取得した車両の現在地点から閾値以内の距離に、経路抽出部が抽出した分岐点が存在するときに、その分岐点に関連する情報を通知可とした。しかし、本発明はこれに限定されず、予測された経路上にある何組かの分岐点と合流点とについて所要時間情報を提供するとしてもよい。図２７は、予測された移動経路上に２組以上の分岐点と合流点との組（ａ、ｂ）、（ｃ、ｄ）がある場合について所要時間情報を提供する多様な表示例を模式的に示す図である。上記実施の形態１では、現在位置の近傍に分岐点ａが存在したとき、例えば、領域２７１に示されるような分岐点ａ及び合流点ｂとの間の経路に対してのみ所要時間情報を提供した。これに対し、予測した移動経路上に複数の分岐点と合流点との組が存在した場合には、例えば、領域２７２に示されるような、現在位置により近い２組の分岐点と合流点との組とについて、所要時間情報を提供するとしてもよい。
【００６１】
また、表示画面内で煩雑にならなければ、３組以上の分岐点と合流点との組について、所要時間情報を提供するとしてもよい。また、複数組の分岐点と合流点との組を表示画面に表示する場合には、現在位置により近い組についてだけ所要時間情報を提供し、現在位置から遠い方の組（例えば、分岐点ｃと合流点ｄとの組）については分岐点及び合流点とそれらを結ぶ複数の経路とだけを表示するようにしてもよい。また、移動経路上に領域２７２に示されるような、複数組の分岐点と合流点との組がある場合、まず、領域２７２に示されるように、全部の組について点滅表示などで分岐点と合流点とその間の経路だけを表示し、次いで、現在位置に最も近い分岐点を含む組について、経路と所要時間情報とを提供するようにしてもよい。
【００６２】
さらに、分岐点と合流点とを結ぶ複数の移動経路のうち、所要時間情報を提供しない経路については、その経路を破線などで表示してもよいし、経路自体を地図上の表示と同様の表示とし、線で示すなどの特別な表示をしないとしてもよい。
【００６３】
またさらに、所要時間情報提供装置は、一旦、予測した移動経路上のすべての分岐点と合流点との組について異なる移動経路を解析しておいてもよい。そして、現在位置に直近の分岐点を含む移動経路についてのみ、当該分岐点が所定の閾値以内の距離に近づいたときに所要時間情報を提供するとしてもよい。
【００６４】
また、一組の分岐点と合流点とを結ぶ複数の経路がすべて履歴に記憶されているものであるということは、ユーザがすでに一回はその経路を通過しているということである。従って、ユーザは、各経路を移動する場合の所要時間についてある程度は知識があるはずなので、例えば、ＶＩＣＳがある経路についてだけ所要時間情報を提供するとしてもよい。
【００６５】
（実施の形態２）
なお、実施の形態１では、車両の走行履歴中に分岐点と合流点を結ぶ複数種類の経路が存在したときに、その経路がユーザにとって所要時間を比較したい経路であるとし、所要時間関連情報を通知していた。しかし、走行履歴中に分岐点と合流点を結ぶ複数種類の経路が存在したとしても、ユーザはどちらの経路が早いか知っている可能性がある。具体的には、車両の過去の走行履歴において経路の所要時間が類似していないときには、ユーザはどちらの経路が早いか知っている可能性が高い。このようなときには、所要時間情報を通知すると、通知情報が無意味であるだけではなく、ユーザの運転等のタスクや別の有効な情報の提供を妨げることにもなる。特に音声による情報提供の場合やユーザが運転操作を行っている場合など、タスクを妨げる可能性が高いため、より情報をフィルタリングする必要がある。そこで、過去の走行履歴において経路の所要時間が類似して、どちらの経路が早いかユーザにとって判別がつきにくいときのみ所要時間情報を通知する。これにより、ユーザにとって、所要時間を比較したいと考えている可能性が、より高い経路の情報を通知することができる。つまり、ユーザにとって当たり前の所要時間情報をフィルタリングし、どちらの経路を通るほうが早いかがわからない経路の情報のみ通知することができる。
【００６６】
以下、本実施の形態の手法について説明する。
図２８は、本実施の形態における所要時間情報提供装置の構成を示すブロック図である。前記実施の形態１で示した構成要素には同様の符号を付与し、説明を省略する。以下、まず各構成要素について図を用いて説明し、後に本装置の動作について説明する。
【００６７】
ノード抽出部２５１１は、地図蓄積部１０４に蓄積された地図情報を参照し、履歴蓄積部１０３に蓄積された走行履歴から、時系列順に並べられたノードＩＤの系列およびそれぞれのノードＩＤの通過時刻を抽出する。つまり、走行履歴中の車両の存在地点と場所が一致する地図情報中のノードＩＤを時系列順に通過時刻と共に抽出する。具体的には、走行履歴中の地点から距離が閾値以内にある地図情報のノードＩＤを探索し、存在すれば時刻と共に抽出する。閾値は例えば、道路幅、車両が１秒間に進む最大距離、ＧＰＳ誤差から決定する。ただし、直前に抽出したノードと同じノードＩＤは抽出しない。例えば、道路幅２５ｍ、車両が１秒間に進む最大距離６００００／３６００ｍ、ＧＰＳ誤差１０ｍとすると、それらの和である５０ｍとする。図２９は、ノード抽出部がノード系列と通過時刻を抽出する例を示す図である。図２９を例として説明する。簡易的に、経度２．２５秒を５０ｍ、緯度１．５秒を５０ｍとすると、図２９のＩＤ００１の走行履歴（経度１３４．３．０．９、緯度３４．６．２．６）から閾値５０ｍ以内に存在するノードは、ノードＩＤ００１（緯度差１秒＜１．５秒）である。よってノードＩＤ００１を走行履歴ＩＤ００１の時刻（９／２０  ７：００：００）と共に抽出する。ＩＤ００２の走行履歴について閾値５０ｍ以内に存在するノードは、ノードＩＤ００１であるが、直前に抽出したノードＩＤ００１と同一であるため、抽出しない。ＩＤ００３〜００６の走行履歴については閾値５０ｍ以内にノードが存在しないため抽出しない。ＩＤ００７の走行履歴（経度１３４．３．０．９、緯度３４．６．９．６）については閾値５０ｍ以内に存在するノードはノードＩＤ００３（経度１３４．３．０．９、緯度３４．６．１０．６）であるため、ノードＩＤ００３を走行履歴ＩＤ００７の時刻（９／２０  ７：００：０６）と共に抽出する。抽出したノードＩＤを走行履歴の時刻順に並べたノードＩＤ系列、図２９の場合「００１（９／２０  ７：００：００）→００３（９／２０  ７：００：０６）」を抽出する。
【００６８】
時間算出部２５２１は、前記２地点のうち、複数の移動経路に分岐する地点を分岐点とし、複数の前記移動経路が合流する地点を合流点として、分岐点と合流点との間の異なる複数の前記移動経路のそれぞれについて、前記履歴蓄積手段に蓄積されている時刻と地点との組から、分岐点と合流点との間の移動に要する所要時間を算出する前記情報算出手段の一例であり、分岐点と合流点との間の異なる複数の前記移動経路のそれぞれについて、分岐点と合流点との間の移動に要する所要時間の平均を算出する前記情報算出手段の一例である。本実施の形態では、時間算出部２５２１は、通知部１０９が通知可能とした分岐点ＩＤ、合流点ＩＤに対して対応する判定部１１４が算出した分岐点ＩＤ、合流点ＩＤを結ぶ複数の経路を示す複数のノードＩＤ系列に対して、ノード抽出部２５１１が抽出したノードＩＤ系列の通過時刻から、経路に対する所要時間を算出する。具体的には、通知可能とした分岐点ＩＤ、合流点ＩＤに対する判定部１１４が算出した複数ノードＩＤ系列に対して、一致する系列をノード抽出部２５１１が抽出したノードＩＤ系列から選択し、選択したノードＩＤ系列の終点（合流点ＩＤ）の通過時刻と、選択したノードＩＤ系列の始点（分岐点ＩＤ）の通過時刻の差を、判定部１１４が算出したノードＩＤ系列に対する所要時間とする。図３０は、時間算出部が分岐点合流点間のノードＩＤ系列に対する所要時間を算出する例を示す図である。図３０を例として説明する。図３０のように通知部１０９が通知可能とした分岐点ＩＤが００３、合流点ＩＤが００４であり、それに分岐点、合流点が一致する判定部１１４が算出したノードＩＤ系列が「００３→００４」、「００３→００５→００６→００４」であったとする。このとき、ノード抽出部２５１１が抽出したノードＩＤ系列中に一致する部分を選択し、選択した部分における始点と終点の時刻の差を所要時間として求める。図３０の場合、ノード抽出部２５１１が抽出したノードＩＤ系列中の「００３（９／２０  ７：００：０６）→００４（９／２０  ７：１５：３６）」に対して、時刻の差である所要時間１５分３０秒（＝９／２０  ７：１５：３６  −  ９／２０  ７：００：０６）が算出される。また、ノードＩＤ系列中の「００３（９／２２  ７：２０：３０）→００５→００６→００４（９／２２  ７：３３：３０」」に対して、所要時間１３分、「００３（９／２４  ７：１１：２０）→００４（９／２４  ７：１６：２０）」に対して、所要時間１４分が算出される。
【００６９】
類似部２５２２は、前記分岐点と前記合流点とを結ぶ移動経路ごとに算出された所要時間を、移動経路同士で比較し、比較された所要時間の差が所定の閾値以内である移動経路について所要時間が類似すると判断する類似判断手段の一例であり、前記分岐点と前記合流点とを結ぶ異なる移動経路ごとに算出された所要時間の平均を、前記移動経路同士で比較し、比較された所要時間の平均の差が閾値以内である移動経路について所要時間が類似すると判定する前記類似判断手段の一例である。類似部２５２２は、本実施の形態では、時間算出部２５２１が算出した分岐点合流点間の複数の経路を示すノードＩＤ系列に対する所要時間情報を用いて、分岐点、合流点が一致する複数の経路の所要時間が類似しているか否かを判定し、類似していた場合は類似した経路を示すノードＩＤ系列を出力する。具体的には、それぞれの経路ごとに、所要時間の平均を算出し、経路間の所要時間平均の差が閾値以内であった場合、類似しているとする。図３１は、類似部が経路の所要時間の類似を判定する例を示す図である。図３１を例として説明する。時間算出部２５２１が算出した所要時間が、「００３→００４」に対して１５分３０秒、「００３→００５→００６→００４」に対して１３分、「００３→００４」に対して１４分、「００３→００５→００６→００４」に対して１４分、「００３→００４」に対して１２分であったとする。このとき、経路ごとの所要時間の平均を算出すると、ノードＩＤ系列「００３→００４」に対して１３分５０秒（＝（１５分３０秒＋１４分＋１２分）／３）、ノードＩＤ系列「００３→００５→００６→００４」に対して１３分３０秒（＝（１３分＋１４分）／２）、である。「００３→００４」、「００３→００５→００６→００４」の分岐点、合流点は一致し、所要時間の差は２０秒（１３分５０秒―１３分３０秒）である。閾値を５分とすると、２０秒は閾値以内であるため、ノードＩＤ系列「００３→００４」と「００３→００５→００６→００４」の所要時間は類似していると判定する。
【００７０】
分岐点合流点間を結ぶ経路（ノードＩＤ系列）が３個以上あった場合は、２個の組み合わせごとに類似しているか否かを判定する。例えば、分岐点合流点間を結ぶ経路としてＡルート、Ｂルート、Ｃルートが存在したときは、ＡルートとＢルート、ＢルートとＣルート、ＣルートとＡルートの組み合わせでそれぞれ類似判定を行う。なお、ユーザが欲する情報は最も所要時間が小さいルートである場合が多いため、最も所要時間平均が小さい２つの経路についてのみ類似判定を行ってもよい。これにより、同じ合流点に向かう経路が３つ以上あったとしても、ユーザがどちらの経路を通るか迷っている可能性が最も高い２つの経路における、ユーザの知っている所要時間情報が異なるときのみ、所要時間情報を提供することができる。
【００７１】
なお、各経路に対する所要時間の平均ではなく、所要時間の中央値を用いてもよい。中央値を用いることで、まれに渋滞が発生する場所などにおいて、外れ値を除去することができる。よって、所要時間が類似しているため所要時間の大小関係がわからないとユーザが思っている経路の情報のみ提供することができる。
【００７２】
第２通知部２５２３は、類似部２５２２が類似していると判定したノードＩＤ系列が存在した場合、そのノードＩＤ系列に対して通知可能であると決定する。
【００７３】
情報算出部２５０８は、情報取得部１０７が取得したリンクＩＤに対する所要時間情報、地図蓄積部１０４に蓄積されたリンクＩＤ情報を用いて、第２通知部２５２３が通知可能と決定した、分岐点と合流点を結ぶ複数の経路（ノードＩＤ系列）中の所要時間情報を算出する。
【００７４】
情報提供部２５１０は、前記類似判断手段により所要時間が類似すると判断された移動経路について前記所要時間情報を提供する前記情報提供手段の一例であり、第２通知部２５２３が通知可能と決定したとき、情報算出部１０８が算出した第２通知部２５２３が通知可能と決定した経路に関する所要時間情報をユーザに提供する。
【００７５】
図３２は、本発明の実施の形態２における所要時間情報提供装置の動作の例を示すフローチャートである。以下、本実施の形態２のフローチャートを、図３２を用いて説明する。実施の形態１で説明した処理については説明を省略する。
【００７６】
実施の形態１と同様に、履歴蓄積部１９０３は、地点取得部１０１が取得した車両の存在地点と時刻取得部１０２が取得した時刻の履歴を走行履歴として蓄積した後（ステップＳ１２０３）、ノード抽出部２５１１は、地図蓄積部１０４に蓄積された地図情報を参照し、履歴蓄積部１０３に蓄積された走行履歴から、時系列順に並べられたノードＩＤの系列とノードＩＤの通過時刻を抽出する（ステップＳ２９０４）。仮定部１１２は、抽出したノードＩＤ系列中に存在する任意のノードＩＤ二つを仮想分岐点ＩＤ、仮想合流点ＩＤとしてそれぞれ仮定する（ステップＳ２９０５）。分割部１１３は、ノード抽出部１１１が抽出したノードＩＤ系列を分割し、仮定部１１２が仮定した仮想分岐点ＩＤと仮想合流点ＩＤを結ぶノードＩＤ系列群を抽出する（ステップＳ２９０６）。分割部１１３は、抽出したノードＩＤ系列群の中から、同一ノードを含まないノードＩＤ系列のみ抽出する（ステップＳ２９０７）。判定部１１４は、仮定部１１２が仮定した仮想分岐点と仮想合流点について、対応する分割部１１３が抽出したノードＩＤ系列群の中に、分岐点、合流点以外にノードＩＤが全て異なるノードＩＤ系列の組み合わせが存在するものについて、分岐点、合流点、及ぶそれらを結ぶノードＩＤ系列群を抽出する（ステップＳ２９０８）。通知部１０９は、地点取得部１０１が取得した車両の現在地点から閾値以内の距離に、判定部１１４が抽出した分岐点が存在するかどうかの判定を行い（ステップＳ２９０９）、存在したときは、通知部１０９はその分岐点及び対応する合流点について通知可能とし、ステップＳ２９１０に進む（ステップＳ２９０９のＹｅｓ）。存在しなかったときは、ステップＳ１２０１に戻る（ステップＳ２９０９のＮｏ）。現在地点の近傍に分岐点が存在したとき、時間算出部２５２１は、通知部１０９が通知可能とした分岐点ＩＤ、合流点ＩＤを結ぶ判定部１１４が算出した複数のノードＩＤ系列に対して、ノード抽出部２５１１が抽出したノードＩＤの通過時刻から、ノードＩＤ系列に対する所要時間を算出する（ステップＳ２９１０）。類似部２５２２は、時間算出部２５２１が算出したノードＩＤ系列に対する所要時間情報を用いて、分岐点、合流点間の経路ごとの所要時間平均の差が閾値以内であるかどうかを判定し（ステップＳ２９１１）、閾値以内であったときはそれらのノードＩＤ系列を類似していると判定し、第２通知部２５２３が通知可能と決定し、ステップＳ２９１２に進む（ステップＳ２９１１のＹｅｓ）。閾値以内であるノードＩＤ系列が存在しなかった場合は、類似していないと判定し、ステップＳ１２０１に戻る（ステップＳ２９１１のＮｏ）。類似部２５２２が類似していると判定したノードＩＤ系列が存在した場合、情報取得部１０７は、ＶＩＣＳなどの外部ネットワーク媒体１０６から、道路リンクの所要時間情報を取得する（ステップＳ２９１２）。情報算出部２５０８は、情報取得部１０７が取得したリンクＩＤに対する所要時間情報、地図蓄積部１０４に蓄積されたリンクＩＤ情報を用いて、第２通知部２５２３が通知可能と決定した、分岐点と合流点を結ぶ複数のノードＩＤ系列中の所要時間情報を算出する（ステップＳ２９１３）。情報提供部２５１０は、情報算出部２５０８が算出した第２通知部２５２３が通知可能と決定した経路に関する所要時間情報をユーザに提供する（ステップＳ２９１４）。終了するか判定を行い（ステップＳ２９１５）、終了するならば、処理を終了する（ステップＳ２９１５のＹｅｓ）。終了しないならば、ステップＳ１２０１に戻る（ステップＳ２９１５のＮｏ）。
【００７７】
（実施の形態２の変形例１）
なお、本実施の形態２において、類似部２５２２が類似判定に用いる閾値は一定であった。渋滞の度合いが日時によりあまり変化しない地域であればよいが、都心部、国道などにより渋滞の度合いの変化が激しい地域など、過去それぞれの経路を通るときの通過時刻にばらつきがあったときは、経路同士の所要時間の違い、どちらの経路を通るのが早いかはユーザにとってわかりにくくなる。例えば、過去Ａ経路を通った場合、７時１２分に分岐点を通過し、合流点を７時２４分に通過したとする。このとき、過去Ｂ経路を通った場合、７時１３分に分岐点を通過し、合流点を７時３０分に通過したとすると、Ａ経路がＢ経路に対して早いことがわかる。しかし同じＡ経路がＢ経路に対して５分早い場合でも、過去Ｂ経路を通った場合、７時１３分ではなく、７時３５分に分岐点を通過し、合流点を７時５２分に通過したとすると、７時１３分に分岐点を通過したときに比べて、どちらの経路が早いのかがわかりにくい。そこで、類似部２５２２が類似判定に用いる閾値を、分岐点の通過時刻のばらつきによって変動させる。具体的には、ノード抽出部２５１１が抽出したノードＩＤの通過時刻から、分岐点ＩＤの通過時刻の分散値を算出する。分散値が小さいほど閾値を小さくする。例えば、分散値を閾値とする。これにより、ある程度所要時間の平均が異なっていたとしても、経路の所要時間にばらつきがあるため、結果的にユーザがどちらの経路が早いかわからない経路についての所要時間情報も提供することができる。
【００７８】
なお、分岐点から合流点までの経路の長さや所要時間が大きくなるほど類似判定に用いる閾値を大きくしても良い。特に、走行距離が長いユーザなど、分岐点から合流点までの距離や所要時間が長い場合がある。このときは、そもそもそこに到るまでの車の走行時間が長いため、所要時間が異なっていても、走行時間に比べてスケールが小さいとユーザが違いを認識できない場合が多い。よって、分岐点から合流点までの経路の長さ、もしくは所要時間に応じて、類似判定に用いる閾値を大きくする。これにより、走行時間が長いため、少々の所要時間の違いを認識できない経路に対しても所要時間情報を通知することができる。
【００７９】
（実施の形態２の変形例２）
なお、本実施の形態２において、分岐点合流点間の経路（ノードＥＩＤ系列）を通過した全ての履歴を用いて所要時間平均を算出していた。しかし、同じ経路でも、平日に通過する場合と、休日に通過する場合では所要時間が異なる場合は多い。同様に朝に通過する場合と夜に通過する場合など、時間帯が異なるときも所要時間が異なる場合が多い。このようなとき、ユーザは時間帯、平休日ごとに、所要時間を覚え、複数経路中のどちらが早いかを覚えている場合が多い。そこで、平休日もしくは、時間帯が現在走行と一致する履歴のみを用いて所要時間平均を算出しても良い。具体的には、時間算出部２５２１が、各ノード系列に対する所要時間を算出する際、時刻取得部１０２が取得した現在時刻（時：分；秒）から通過時刻（時：分；秒）が閾値以内である履歴のみを抽出し、所要時間を算出する。または、時刻取得部１０２が取得した現在日付の平休日から、通過時刻（日付）の平休日が一致する履歴のみを抽出し、所要時間を算出する。これにより、同じ地点に向かう場合でも、朝通る場合はＡルート、夜通る場合はＢルートが早いとユーザは記憶しているような経路に対して、ユーザにとって当たり前の所要時間比較情報を提供してユーザのタスクを妨げることを防ぐことができる。特にいろんな時間帯に車両を使うなど車両を使う頻度が多いユーザは時間帯、平休日ごとに所要時間を覚えている可能性が高いため有効である。
【００８０】
（実施の形態２の変形例３）
なお、本実施の形態２において、分岐点合流点を結ぶ複数経路について、走行履歴中の所要時間平均が類似していたときに所要時間情報を通知していた。しかし、所要時間平均が類似していなかったときにも、ユーザはどちらの経路を通ると早いかがわからない場合がある。例えば、分岐点合流点を結ぶ複数経路についてＡルートとＢルートがあったとする。Ａルートの所要時間平均よりもＢルートの所要時間平均が充分小さかったとする（Ａ＞Ｂ）。しかし、平均ではそうであったとしても、Ａルートの所要時間よりもＢルートの所要時間が大きい履歴が存在する可能性がある（Ａ＜Ｂ）。このような所要時間平均から得た大小関係に反する事例の割合が多い場合は、ユーザはたとえ平均の差が大きかったとしても、どちらの経路が早いのかがわからない可能性が高い。そこで、こういった場合にも所要時間情報を通知することで、たとえ所要時間平均が類似していなかったとしても、ユーザがどちらの経路を通る方が早いかわからないときに、経路の所要時間情報を通知することができる。
【００８１】
以下本実施の形態の手法について説明する。
図３３は、本実施の形態における所要時間情報提供装置の構成を示すブロック図である。前記実施の形態２で示した構成要素には同様の符号を付与し、説明を省略する。以下、まず各構成要素について図を用いて説明し、後に本装置の動作について説明する。
【００８２】
比較部３０２４は、前記分岐点と合流点を結ぶ異なる移動経路ごとに、前記情報算出手段が算出した所要時間の平均を比較し、所要時間の平均の大小関係を算出する比較手段の一例であり、本実施の形態では、類似部２５２２が所要時間は類似していないと判定したときに、類似部２５２２が算出した分岐点合流点間の複数の経路に対する所要時間平均を用いて、経路の所要時間平均の大小関係を判定する。例えば、分岐点合流点を結ぶ複数経路「００３→００４」、「００３→００５→００６→００４」について、ノードＩＤ系列「００３→００４」に対して所要時間平均１３分５０秒、ノードＩＤ系列「００３→００５→００６→００４」に対して所要時間平均２０分０秒であったとする。このとき、ノードＩＤ系列「００３→００４」の所要時間がノードＩＤ系列「００３→００５→００６→００４」の所要時間に比べて小さいと判定する（１３分５０秒＜２０分０秒）。
【００８３】
反事例部３０２５は、前記比較手段によって算出された前記大小関係に反する移動履歴の数を算出し、前記比較手段によって算出された前記大小関係に反する前記移動履歴の数が多い場合に、反事例が多いと判定する反事例判定手段の一例である。反事例部３０２５は、比較部３０２４が判定した分岐点合流点を結ぶ複数経路の所要時間の大小関係について、その大小関係に反する事例の割合を時間算出部２５２１が算出した経路に対する所要時間履歴から算出し、割合が閾値以上であった場合、大小関係は判定できないと判断する。具体的には、比較部３０２４が判定した分岐点合流点を結ぶ経路がＡルートとＢルートであり、時間算出部２５２１が算出した経路に対する所要時間履歴について、Ａルートに関しては履歴数α個、Ｂルートに関してはβ個であったとする。このとき、Ａルートの履歴から１つ、Ｂルートの履歴から１つ履歴を取ってきたときの組み合わせの数はα×βである。また、所要時間履歴からＡルートの履歴から１つ、Ｂルートの履歴から１つ履歴を取ってきたときに、比較部３０２４が判定した所要時間の大小関係とは反する事例数を算出する。事例数がｘ個であったとするとｘ／（α×β）が反事例の割合であるためｘ／（α×β）が閾値以上であれば、大小関係は判定できないとする。図３４は、反事例部が反事例数から経路の所要時間の大小関係の判定可否を判断する例を示す図である。図３４を例として説明する。図３４のように時間算出部２５２１によって経路に対する所要時間履歴が算出され、比較部３０２４によって所要時間平均大小関係が「００３→００４」（１３分５０秒）＜「００３→００４→００５→００６」（２０分）と算出されたとする。このとき、「００３→００４」経路の履歴（履歴数３）と「００３→００４→００５→００６」経路の履歴（履歴数２）による組み合わせの事例数は６（＝３×２）である。また、反事例の履歴数つまり、所要時間の大小関係が「００３→００４」＜「００３→００４→００５→００６」とならない組み合わせの事例は、「００３→００４」（１５分３０秒）＞「００３→００４→００５→００６」（１０分）、「００３→００４」（１４分）＞「００３→００４→００５→００６」（１０分）、「００３→００４」（１２秒）＞「００３→００４→００５→００６」（１０分）の３通りである。よって反事例の割合は０．５（＝３／６）である。閾値を０．１と既定していたとすると、反事例の割合０．５は閾値以上であるため、大小関係はユーザにとって判定できないと判断する。
【００８４】
なお、反事例の割合により大小関係の判定の可否を判断すると、正規化されるため、履歴の数が多く、ノイズとなるような例外データが存在したとしても適切に判断できる。しかし、用いる履歴の数が少ない場合は、反事例の割合ではなく、反事例数を用いても良い。これにより、履歴の数が少ない場合は、大小関係の判定の可否が適切に判断できる。
【００８５】
第２通知部２５２３は、類似部２５２２が類似していると判定したノードＩＤ系列が存在するか、反事例部３０２５が大小関係は判定できないと判断したノードＩＤ系列が存在した場合、そのノードＩＤ系列に対して通知可能であると決定する。
【００８６】
図３５は、本発明の実施の形態２の変形例３における所要時間情報提供装置の動作の例を示すフローチャートである。以下、本実施の形態２の変形例３のフローチャートを、図３５を用いて説明する。実施の形態２で説明した処理については説明を省略する。
【００８７】
実施の形態２と同様に、時間算出部２５２１は、通知部１０９が通知可能とした分岐点ＩＤ、合流点ＩＤを結ぶ判定部１１４が算出した複数のノードＩＤ系列に対して、ノード抽出部２５１１が抽出したノードＩＤの通過時刻から、ノードＩＤ系列に対する所要時間を算出した後（ステップＳ２９１０）、類似部２５２２は、時間算出部２５２１が算出したノードＩＤ系列に対する所要時間情報を用いて、分岐点、合流点間の経路ごとの所要時間平均の差が閾値以内であるかどうかを判定し（ステップＳ３２１１）、閾値以内であったときはそれらのノードＩＤ系列を類似していると判定し、第２通知部３０２３が通知可能と決定し、ステップＳ３２１５に進む（ステップＳ３２１１のＹｅｓ）。閾値以内であるノードＩＤ系列が存在しなかった場合は、類似していないと判定し、ステップＳ３２１２に進む（ステップＳ３２１１のＮｏ）。類似部２５２２が類似していないと判定したノードＩＤ系列に対して、比較部３０２４は類似部２５２２が算出した分岐点合流点間の複数の経路に対する所要時間平均を用いて、経路の所要時間平均の大小関係を判定する（ステップＳ３２１２）。反事例部３０２５は、比較部３０２４が判定した分岐点合流点を結ぶ複数経路の所要時間の大小関係について、その大小関係に反する事例数の割合を時間算出部２５２１が算出した経路に対する所要時間履歴から算出する（ステップＳ３２１３）。反事例部３０２５は、大小関係に反する事例数の割合が閾値以上であるかどうかを判定し（ステップＳ３２１４）、閾値以上であった場合、反事例部３０２５は、それの経路について大小関係は判定できないと判断し、第２通知部３０２３が通知可能と決定し、ステップＳ３２１５に進む（ステップＳ３２１４のＹｅｓ）。閾値以上でなかった場合、反事例部３０２５は、それの経路について判定できると判断し、ステップＳ１２０１に戻る（ステップＳ３２１４のＮｏ）。第２通知部３０２３が通知可能と決定した経路が存在したとき、情報取得部１０７は、ＶＩＣＳなどの外部ネットワーク媒体１０６から、道路リンクの所要時間情報を取得する（ステップＳ３２１５）。情報算出部２５０８は、情報取得部１０７が取得したリンクＩＤに対する所要時間情報、地図蓄積部１０４に蓄積されたリンクＩＤ情報を用いて、第２通知部３０２３が通知可能と決定した、分岐点と合流点を結ぶ複数のノードＩＤ系列中の所要時間情報を算出する（ステップＳ３２１６）。情報提供部２５１０は、情報算出部２５０８が算出した第２通知部３０２３が通知可能と決定した経路に関する所要時間情報をユーザに提供する（ステップＳ３２１７）。終了するか判定を行い（ステップＳ３２１８）、終了するならば、処理を終了する（ステップＳ３２１８のＹｅｓ）。終了しないならば、ステップＳ１２０１に戻る（ステップＳ３２１８のＮｏ）。
【００８８】
（実施の形態２の変形例４）
なお、本実施の形態２において、分岐点合流点間の経路について所要時間平均が類似しているときに所要時間情報を通知していた。しかし、特にあまり同じ経路を通らないユーザなど、ユーザが現在までに経路を通った回数が少ないときは、その経路に関する所要時間を覚えていない可能性がある。覚えていないときは、ユーザは分岐点合流点間の複数経路に関する所要時間の大小関係もわからない。そこで、経路に関する所要時間の履歴数が閾値以下のときは、大小関係が判定不能として、所要時間情報を通知してもよい。第２通知部３０２３は、前記履歴蓄積手段に蓄積されている移動履歴から、前記分岐点と合流点を結ぶ異なる移動経路のそれぞれの通過回数を算出する前記類似判断手段と、前記類似判断手段により算出された通過回数が閾値以下である移動経路について前記所要時間情報を提供する前記情報提供手段との一例である。具体的には、比較部３０２４が判定した分岐点合流点を結ぶ経路がＡルートとＢルートであり、時間算出部２５２１が算出した経路に対する所要時間履歴について、Ａルートに関しては履歴数α個、Ｂルートに関してはβ個であったとする。このとき、αもしくはβが閾値以下であれば、第２通知部はそれらの経路に関して通知可能とする。これにより、所要時間は類似せず大小関係が明白であったとしても、ユーザがその大小関係を覚えていないため、どちらの経路が早いかわからないような経路についても所要時間情報を提供することができる。
【００８９】
（実施の形態２の変形例５）
なお、本実施の形態２において、分岐点合流点間の経路について所要時間平均が類似しているときに所要時間情報を通知していた。しかし、ユーザは所要時間のみによって、通る経路を選ぶわけではない。複数の経路が存在したとき、道路幅や右左折数、経路コストといった通りやすさを重視するユーザも存在する。よって、所要時間が類似していたとしても、経路の通過回数が類似していない場合、ユーザは所要時間以外の要因により経路を選択しており、所要時間情報を欲していない可能性が高い。そこで、分岐点合流点間の複数経路について履歴から算出した所要時間が類似し、履歴から算出した通過回数も類似するときにのみ所要時間情報を提供する。これにより、通りやすさを重視するユーザに対しても、より所要時間情報を欲する状況で通知することができる。
【００９０】
類似部２５２２は、前記履歴蓄積手段に蓄積されている移動履歴から、前記分岐点と合流点を結ぶ異なる移動経路のそれぞれの通過回数を算出する前記類似判断手段と、前記類似判断手段により算出された通過回数が類似する移動経路について前記所要時間情報を提供する前記情報提供手段の一例である。具体的には類似部２５２２は、時間算出部２５２１が算出した分岐点合流点間の複数の経路を示すノードＩＤ系列に対する所要時間情報を用いて、分岐点、合流点が一致する複数の経路の所要時間及び通過回数が類似しているか否かを判定し、類似していた場合は類似した経路を示すノードＩＤ系列を出力する。図３１を例として説明する。時間算出部２５２１が算出した所要時間が、「００３→００４」に対して１５分３０秒、「００３→００５→００６→００４」に対して１３分、「００３→００４」に対して１４分、「００３→００５→００６→００４」に対して１４分、「００３→００４」に対して１２分であったとする。このとき、「００３→００４」に対する履歴数（通過回数）は３、「００３→００５→００６→００４」に対する履歴数（通過回数）が２である。履歴数の差が閾値以内であれば類似しているとする。閾値を５とすると、履歴数の差が１（＝３−２）で閾値以内であるため、通過回数は類似しているとする。
【００９１】
なお、履歴数は増加しつづけるため、履歴数を限定するための履歴の削除を行わない場合は、ユーザはどちらの経路も同じように通過していたとしても、履歴が増加していくと履歴数の差が大きくなってしまう可能性がある。そこで履歴数の差ではなく、履歴数の比と１の差が閾値以内のときに、通過回数は類似していると判定しても良い。
【００９２】
（実施の形態３）
なお、実施の形態１では、車両の走行履歴中に分岐点と合流点を結ぶ複数種類の経路が存在したときに、その経路がユーザにとって所要時間を比較したい経路であるとし、所要時間関連情報を通知していた。しかし、走行履歴中に分岐点と合流点を結ぶ複数種類の経路が存在したとしても、ユーザはどちらの経路が早いか知っている可能性がある。このようなときには、所要時間情報を通知すると、通知情報が無意味であるだけではなく、ユーザの運転等のタスクや別の有効な情報の提供を妨げることにもなる。しかし、たとえユーザはどちらの経路が早いか知っていたとしても、自分の所要時間知識と現実の所要時間知識が乖離しているのではないかと不安になる場合はある。そういったユーザが自分の知識とは異なる状況ではないかと不安になっている状況では、確認のために情報を提供すると、たとえ情報がユーザの知っているものであっても、ユーザは安心し、安全に運転することができる。つまり、ユーザがどちらの経路が早いか知っている、知っていないに関わらず、経路に関する所要時間関連情報を通知する。これにより、ユーザがどちらの経路が早いか迷っている経路について、いわば確認のための情報を提供することができる。ユーザが不安になる場合とは、ユーザの過去の走行と道路交通状況が異なる場合である。具体的には、現在の走行において、出発地などのある地点から現在地までの実際の所要時間が、過去の履歴における所要時間と異なることを検出することでユーザの知っている普段の交通状況と異なることを検出することができる。よって、現在までの所要時間が普段と異なるときに所要時間情報を通知し、そうでないときに所要時間情報を通知しないことで、ユーザの知っている普段の交通状況と異なり、ユーザが不安になる状況で、経路の情報を提供することができる。つまり、ユーザにとって所要時間を比較したいと考えている可能性が、より高いタイミングで、経路の情報を通知することができる。
【００９３】
以下本実施の形態の手法について説明する。
図３６は、本実施の形態における所要時間情報提供装置の構成を示すブロック図である。前記実施の形態１、実施の形態１の変形例４で示した構成要素には同様の符号を付与し、説明を省略する。以下、まず各構成要素について図を用いて説明し、後に本装置の動作について説明する。
【００９４】
ノード抽出部３３１１は、地図蓄積部１０４に蓄積された地図情報、ランドマーク蓄積部１９１７に蓄積されたランドマーク情報を参照し、履歴蓄積部１９０３に蓄積された走行履歴から、時系列順に並べられたノードＩＤの系列およびそれぞれのノードＩＤの通過時刻を抽出する。ノードＩＤには道路の交差点だけではなく、ランドマークＩＤも含まれる。履歴蓄積部１９０３には、出発地から目的地もしくは現在地までの走行履歴が複数蓄積されている。よって、蓄積された走行履歴全てについてノードＩＤ系列、およびそのノードＩＤの通過時刻に変換を行い、出発地から目的地までのノードＩＤ系列および時刻を複数出力する。具体的に変換手法を説明する。駐車状態を検知するごとに分割して蓄積された走行履歴における始点と終点、つまり出発地と目的地については、走行履歴における地点から、最も近い位置に存在するランドマークＩＤを抽出し、通過時刻は走行履歴の始点の時刻とする。ただし、最新の履歴の終点は現在地を表すため、ランドマークは抽出しない。出発地、目的地以外の走行履歴に関しては、走行履歴の地点から距離が閾値以内にある地図情報のノードＩＤを探索し、存在すれば時刻と共に抽出する。ただし、直前に抽出したノードと同じノードＩＤは抽出しない。同様に、全ての出発地から目的地までの走行履歴についてノードＩＤ系列、通過時刻変換を行う。
【００９５】
現在経路部３３３０は、ノード抽出部３３１１が抽出したノードＩＤ系列から、現在の走行における出発地から現在地までの経路に相当するノードＩＤ系列を抽出する。具体的には、最新の走行履歴から抽出したノードＩＤ系列である。図３７は、現在時間部が現在の走行における出発地から現在地までの所要時間を算出する例を示す図である。例えば、図３７の場合、出発地から現在地までのノードＩＤ系列は「Ｌ００１→１０１→００１」である。
【００９６】
現在時間部３３３１は、前記履歴蓄積手段に蓄積されている時刻から、前記複数の移動経路を最も新しい時刻で通過したときの現在所要時間を算出する現在時間算出手段の一例であり、本実施の形態では、ノード抽出部３３１１が抽出したノードＩＤ系列から、現在の走行における出発地から現在地までの経路に対する所要時間を抽出する。具体的には、最新の走行履歴から抽出した最新の出発地ランドマークＩＤに対応する通過時刻から最新のノードＩＤに対応する通過時刻までの時刻の差である。例えば、図３７の場合、現在の走行における出発地から現在地までの所要時間は、最新の出発地ＩＤの通過時刻が「１０／２  ７：１０：００」であり、最新のノードＩＤ（現在ノードＩＤ）の通過時刻が「１０／２  ７：２５：００」であることから、現在の走行における出発地から現在地までの所要時間は１５分（＝１０／２  ７：２５：００  −  １０／２  ７：１０：００）となる。
【００９７】
過去時間部３３３２は、前記履歴蓄積手段に蓄積されている時刻から、最も新しい時刻で通過したときを除く、前記移動経路の過去所要時間を算出する過去時間算出手段の一例であり、本実施の形態では、ノード抽出部３３１１が抽出したノードＩＤ系列から、最新のノードＩＤ系列以外で、現在経路部３３３０が抽出した現在の走行における出発地から現在地までのノードＩＤ系列と一致するノードＩＤ系列を抽出し、それらのノードＩＤ系列の所要時間の平均を算出する。図３８は、過去時間部が出発地から現在地までのノードＩＤ系列における過去の所要時間を算出する例を示す図である。図３８を例として説明する。現在経路部３３３０が現在走行における出発地から現在地までの経路を示すノードＩＤ系列として「Ｌ００１→１０１→００１」を抽出していたとする。ノード抽出部３３１１が抽出したノードＩＤ系列中、現在走行を示す最新のノードＩＤ系列を除いて、「Ｌ００１→１０１→００１」と一致するノードＩＤ系列を抽出する。抽出したそれぞれの履歴における始点から終点までつまり、「Ｌ００１」から「００１」までの所要時間を算出すると、８分（  ９／２５  ７：２０：００  −  ９／２５  ７：１２：００  ）、１０分（  ９／２６  ７：２１：００  −  ９／２６  ７：１１：００  ）、１１分（  ９／２７  ７：２１：００  −  ９／２７  ７：１０：００  ）、７分（  ９／２９  ７：１７：００  −  ９／２７  ７：１０：００  ）、９分（  １０／１  ７：１９：５０  −  １０／１  ７：１０：５０  ）となる。よって過去の履歴における所要時間の平均は９分（＝８分＋１０分＋１１分＋７分＋９分）となる。
【００９８】
第２類似部３３３３は、前記現在所要時間と前記過去所要時間とが類似するか否かを判定する第２類似判断手段の一例であり、本実施の形態では、現在時間部３３３１が算出した現在の走行における出発地から現在地までのノードＩＤ系列の所要時間と、過去時間部３３３２が算出した過去の走行における前記ノードＩＤ系列の所要時間を比較し、類似しているか否かを判定する。具体的には、現在時間部が算出した所要時間と過去時間部３３３２が算出した所要時間との差が閾値以下であれば類似しているとする。例えば、閾値を５分としたとき、現在時間部３３３１が算出した所要時間が１５分、過去時間部３３３２が算出した所要時間が９分であったとする。差は６分（＝１５分―９分）であり、閾値より大きいため類似していないと判定する。
【００９９】
通知部３３０９は、地点取得部１０１が取得した車両の現在地点から閾値以内の距離に、経路抽出部１０５が抽出した分岐点が存在するときに、その分岐点と合流点を結ぶ複数の経路を示すノードＩＤ系列群をと通知可能として出力する。
【０１００】
第３通知部３３３４は、通知部３３０９が通知可能と判定したノードＩＤ系列が存在し、第２類似部３３３３が類似していないと判定した場合、通知部３３０９が通知可能と判定したノードＩＤ系列に対して通知可能であると決定する。
【０１０１】
情報算出部３３０８は、情報取得部１０７が取得したリンクＩＤに対する所要時間情報、地図蓄積部１０４に蓄積されたリンクＩＤ情報を用いて、第３通知部３３３４が通知可能と決定した、分岐点と合流点を結ぶ複数の経路（ノードＩＤ系列）中の所要時間情報を算出する。
【０１０２】
情報提供部３３１０は、前記第２類似判断手段が類似しないと判定したときに、前記所要時間情報を提供する前記情報提供手段の一例であり、本実施の形態では、第３通知部３３３４が通知可能と決定したとき、情報算出部３３０８が算出した第３通知部３３３４が通知可能と決定した経路に関する所要時間情報をユーザに提供する。
【０１０３】
図３９は、本発明の実施の形態３における所要時間情報提供装置の動作の例を示すフローチャートである。以下、本実施の形態３のフローチャートを、図３９を用いて説明する。実施の形態１の変形例４で説明した処理については説明を省略する。
【０１０４】
実施の形態１の変形例４と同様に、履歴蓄積部１９０３は、地点取得部１０１が取得した車両の存在地点と時刻取得部１０２が取得した時刻の履歴を走行履歴として蓄積した後（ステップＳ１２０３）、駐車検知部１９１６が駐車状態であるか否かを検知する（ステップＳ３６０４）。駐車状態を検知したときは、ステップＳ２４０５に進む（ステップＳ３６０４のＹｅｓ）。駐車状態を検知しなかったときは、ステップＳ３６０６に進む（ステップＳ３６０４のＮｏ）。ノード抽出部３３１１は、地図蓄積部１０４に蓄積された地図情報を参照し、履歴蓄積部１０３に蓄積された走行履歴から、時系列順に並べられたノードＩＤの系列とノードＩＤの通過時刻を抽出する（ステップＳ３６０６）。仮定部１１２は、抽出したノードＩＤ系列中に存在する任意のノードＩＤ二つを仮想分岐点ＩＤ、仮想合流点ＩＤとしてそれぞれ仮定する（ステップＳ３６０７）。分割部１１３は、ノード抽出部３３１１が抽出したノードＩＤ系列を分割し、仮定部１１２が仮定した仮想分岐点ＩＤと仮想合流点ＩＤを結ぶノードＩＤ系列群を抽出する（ステップＳ３６０８）。分割部１１３は、抽出したノードＩＤ系列群の中から、同一ノードを含まないノードＩＤ系列のみ抽出する（ステップＳ３６０９）。判定部１１４は、仮定部１１２が仮定した仮想分岐点と仮想合流点について、対応する分割部１１３が抽出したノードＩＤ系列群の中に、分岐点、合流点以外にノードＩＤが全て異なるノードＩＤ系列の組み合わせが存在するものについて、分岐点、合流点、及ぶそれらを結ぶノードＩＤ系列群を抽出する（ステップＳ３６１０）。通知部３３０９は、地点取得部１０１が取得した車両の現在地点から閾値以内の距離に、判定部１１４が抽出した分岐点が存在するかどうかの判定を行い（ステップＳ３６１１）、存在したときは、その分岐点に対応する判定部１１４が抽出したノードＩＤ系列群を通知可能とし、ステップＳ３６１２に進む（ステップＳ３６１１のＹｅｓ）。存在しなかったときは、ステップＳ１２０１に戻る（ステップＳ３６１１のＮｏ）。近傍に分岐点が存在したとき、現在経路部３３３０は、ノード抽出部３３１１が抽出したノードＩＤ系列から、現在の走行における出発地から現在地までの経路に相当する最新ノードＩＤ系列を抽出する（ステップＳ３６１２）。現在時間部３３３１は、ノード抽出部３３１１が抽出したノードＩＤ系列から、現在の走行における出発地から現在地までの経路（最新ノードＩＤ系列）に対する所要時間を抽出する（ステップＳ３６１３）。過去時間部３３３２は、ノード抽出部３３１１が抽出したノードＩＤ系列から、最新のノードＩＤ系列以外で、現在経路部３３３０が抽出した現在の走行における出発地から現在地までのノードＩＤ系列と一致するノードＩＤ系列を全て抽出する（ステップＳ３６１４）。過去時間部３３３２は抽出したノードＩＤ系列の所要時間の平均を過去走行の所要時間として算出する（ステップＳ３６１５）。第２類似部３３３３は、現在時間部３３３１が算出した現在の走行における出発地から現在地までのノードＩＤ系列の所要時間と、過去時間部３３３２が算出した過去の走行における前記ノードＩＤ系列の所要時間の差が閾値以下であるか否かを判定し（ステップＳ３６１６）、閾値以下であったときは類似していると判定し、ステップＳ１２０１に戻る（ステップＳ３６１６のＹｅｓ）。閾値以下でなかったときは、類似していないと判定し、ステップＳ３６１７に進む（ステップＳ３６１６のＮｏ）。第２類似部３３３３が類似していないと判定した場合、情報取得部１０７は、ＶＩＣＳなどの外部ネットワーク媒体１０６から、道路リンクの所要時間情報を取得する（ステップＳ３６１７）。情報算出部３３０８は、情報取得部１０７が取得したリンクＩＤに対する所要時間情報、地図蓄積部１０４に蓄積されたリンクＩＤ情報を用いて、通知部３３０９が通知可能と決定した、分岐点と合流点を結ぶ複数のノードＩＤ系列中の所要時間情報を算出する（ステップＳ３６１８）。情報提供部３３１０は、情報算出部３３０８が算出した通知部３３０９が通知可能と決定した経路に関する所要時間情報をユーザに提供する（ステップＳ３６１９）。終了するか判定を行い（ステップＳ３６２０）、終了するならば、処理を終了する（ステップＳ３６２０のＹｅｓ）。終了しないならば、ステップＳ１２０１に戻る（ステップＳ３６２０のＮｏ）。
【０１０５】
なお、実施の形態３において現在経路部３３３０は、現在の走行における出発地から現在地までの経路を抽出していた。しかし、特に出発地から現在地までの距離が長い場合、出発地から現在地までの所要時間では同じでも、局所的に現在地付近で所要時間がユーザの知っている所要時間と異なる場合がある。こういった場合でもユーザは自分の知っている所要時間が正しいかどうか不安になる。よって、現在の走行の所要時間が普段と異なるとユーザが認識していることを検知するためには、現在の走行における、所定の通過地点から現在地までの所要時間と過去走行における同経路の所要時間を比較しても良い。つまり、現在経路部３３３０は出発地から現在地ではなく、現在地から既定数前のノードから現在ノードまでの経路を示すノードＩＤ系列を抽出してもよい。このとき、現在時間部３３３１も同様に、現在の走行における現在地から既定数前のノードから現在ノードまでの経路の所要時間を算出する。これにより、局所的に現在地付近の所要時間が異なり、ユーザが自分の所要時間知識に不安になったときにも、所要時間情報を通知することができる。
【０１０６】
（実施の形態４）
なお、実施の形態１では、車両の走行履歴中に分岐点と合流点を結ぶ複数種類の経路が存在したときに、その経路がユーザにとって所要時間を比較したい経路であるとし、所要時間関連情報を通知していた。しかし、走行履歴中に分岐点と合流点を結ぶ複数種類の経路が存在したとしても、ユーザはどちらの経路が早いか予測できるときには、ユーザには情報を通知するべきではない。しかし、ユーザが所定の経路の方が早いと予測したとしても、実際には異なる可能性がある。ユーザの予測する複数経路の所要時間の大小関係と実際の所要時間の大小関係が異なるときは所要時間情報を通知したほうがユーザにとって好ましい。そこで、走行履歴からユーザの予測する複数の経路における所要時間の大小関係を算出し、ＶＩＣＳなどの外部ネットワークから入手した道路交通情報から算出した所要時間の大小関係と比較し、異なる場合にユーザに所要時間情報を通知する。これにより、経路の所要時間の大小関係について、ユーザが知っている大小関係と同じときには、情報が通知されないため、ユーザは当たり前の情報を受け取ることでタスクを妨げられることなく、所要時間が小さい経路を通ることができる。逆に経路の所要時間の大小関係について、ユーザが知っている大小関係と異なるときには、情報が通知されないと、ユーザは自分の知識に従って行動するため、所要時間が大きい経路を通ってしまう。しかし本実施の形態では、情報が通知されるため、所要時間が大きい経路ではなく、真に所要時間が小さい経路を通ることができる。つまり、ユーザにとって所要時間の比較を欲する可能性が、より高い経路の情報を通知することができる。
【０１０７】
以下本実施の形態の手法について説明する。
図４０は、本実施の形態における所要時間情報提供装置の構成を示すブロック図である。前記実施の形態１、２で示した構成要素には同様の符号を付与し、説明を省略する。以下、まず各構成要素について図を用いて説明し、後に本装置の動作について説明する。
【０１０８】
比較部３７２４は、前記分岐点と合流点を結ぶ異なる移動経路ごとに、前記情報算出手段が算出した所要時間を比較し、前記所要時間の大小関係を算出する比較手段の一例であり、本実施の形態では、時間算出部２５２１が算出した分岐点合流点間の複数の経路を示すノードＩＤ系列に対する所要時間情報を用いて、分岐点、合流点が一致する複数の経路の所要時間を比較し、大小関係を算出する。具体的には、それぞれの経路ごとに、所要時間の平均を算出し、平均の大小関係を算出する。例えば、分岐点合流点を結ぶ複数経路Ａルート「００３→００４」、Ｂルート「００３→００５→００６→００４」について、ノードＩＤ系列「００３→００４」に対して所要時間平均１３分５０秒、ノードＩＤ系列「００３→００５→００６→００４」に対して所要時間平均２０分０秒であったとする。このとき、ＡルートノードＩＤ系列「００３→００４」の所要時間がＢルートノードＩＤ系列「００３→００５→００６→００４」の所要時間に比べて小さいと判定する（１３分５０秒＜２０分０秒）。
【０１０９】
情報算出部３７０８は、情報取得部１０７が取得したリンクＩＤに対する所要時間情報、地図蓄積部１０４に蓄積されたリンクＩＤ情報を用いて、判定部１１４が抽出し、通知部１０９が通知可能とした分岐点、合流点、分岐点と合流点を結ぶ複数の経路（ノードＩＤ系列）における所要時間の大小関係を算出する。情報算出部３７０８は、第２時間算出部３７４０と第２比較部３７４１により構成される。
【０１１０】
第２時間算出部３７４０は、外部から提供される道路情報を取得し、取得された前記道路情報から前記分岐点と前記合流点とを結ぶ異なる移動経路ごとに、所要時間を算出する第２時間算出手段の一例である。第２時間算出部３７４０は、本実施の形態では、情報取得部１０７が取得したリンクＩＤに対する所要時間情報、地図蓄積部１０４に蓄積されたリンクＩＤ情報を用いて、判定部１１４が抽出し、通知部１０９が通知可能とした分岐点、合流点、分岐点と合流点を結ぶ複数の経路（ノードＩＤ系列）における所要時間を算出する。例えば、図１０のように、分岐点ＩＤ００３、合流点ＩＤ００４について、Ａルート（００３→００４）、Ｂルート（００３→００５→００６→００４）のノードＩＤ系列が抽出されたとする。このとき、Ａルートの所要時間を算出すると、地図情報からノードＩＤ００３とノードＩＤ００４を結ぶリンクＩＤが０２０であり、情報取得部１０７が取得した情報からリンクＩＤ０２０の所要時間は６００秒である。よってＡルートの所要時間は６００秒である。次にＢルートの所要時間を算出すると、地図情報からノードＩＤ系列（００３→００５→００６→００４）に対応するリンクＩＤ系列は（０２１→０２２→０２３）である。取得情報からリンクＩＤ系列（０２１→０２２→０２３）の所要時間は、４８０秒（＝６０＋３６０＋６０）である。よって、Ｂルートの所要時間は４８０秒である。
【０１１１】
第２比較部３７４１は、前記分岐点と合流点を結ぶ異なる移動経路ごとに、前記第２時間算出手段が算出した所要時間を比較し、前記所要時間の大小関係を算出する第２比較手段の一例であり、本実施の形態では、第２時間算出部３７４０が算出した分岐点と合流点を結ぶ複数のノードＩＤ系列に対する所要時間から、所要時間の大小関係を算出する。例えば図１０のように、分岐点ＩＤ００３、合流点ＩＤ００４を結ぶ複数の経路、Ａルート（００３→００４）の所要時間が６００秒（１０分）であり、Ｂルート（００３→００５→００６→００４）の所要時間が４８０秒（８分）であったとする。このとき、Ａルートの方がＢルートの所要時間に比べて大きいという大小関係が算出される（１０分＞８分）。
【０１１２】
第４通知部３７４２は、分岐点と合流点を結ぶ複数のノードＩＤ系列について、比較部３７２４が算出した所要時間大小関係と第２比較部３７４１が算出した所要時間大小関係の相違を算出し、大小関係が異なるときに、それらのノードＩＤ系列に関する所要時間情報を通知可能とする。例えば、Ａルート「００３→００４」とＢルート「００３→００５→００６→００４」について、比較部３７２４が「Ａルートの所要時間＜Ｂルートの所要時間」と算出し、第２比較部３７４１が「Ａルートの所要時間＞Ｂルートの所要時間」と算出したとする。このとき大小関係が異なるため（＜≠＞）、Ａルート「００３→００４」とＢルート「００３→００５→００６→００４」について通知可能とする。
【０１１３】
情報提供部３７１０は、前記比較手段が算出した大小関係と前記第２比較手段が算出した大小関係とが異なる移動経路について、第２時間算出手段によって算出された所要時間に基づく所要時間情報を提供する前記情報提供手段の一例であり、本実施の形態では、第４通知部３７４２が通知可能と判断した分岐点ＩＤ、合流点ＩＤを結ぶ複数のノードＩＤ系列に対して第２比較部３７４１が算出した所要時間の大小関係情報をユーザに提供する。例えば、第４通知部３７４２が通知可能と判断したノード系列がＡルート「００３→００４」とＢルート「００３→００５→００６→００４」であり、第２比較部３７４１が算出した所要時間の大小関係がＡルート「００３→００４」の方がＢルート「００３→００５→００６→００４」の所要時間に比べて大きいという情報であった場合、例えば所要時間情報「Ｂルート（００３→００５→００６→００４）がＡルート（００３→００４）より早い」を情報提供装置の画面に表示する。
【０１１４】
図４１は、本発明の実施の形態４における所要時間情報提供装置の動作の例を示すフローチャートである。以下、本実施の形態４のフローチャートを、図４１を用いて説明する。実施の形態２で説明した処理については説明を省略する。
【０１１５】
実施の形態２と同様に、時間算出部２５２１が、通知部１０９が通知可能とした分岐点ＩＤ、合流点ＩＤを結ぶ判定部１１４が算出した複数のノードＩＤ系列に対して、ノード抽出部２５１１が抽出したノードＩＤの通過時刻から、ノードＩＤ系列に対する所要時間を算出した後（ステップＳ２９１０）、比較部３０２４は、時間算出部２５２１が算出した分岐点合流点間の複数の経路を示すノードＩＤ系列に対する所要時間情報を用いて、分岐点、合流点が一致する複数の経路の所要時間平均を比較し、大小関係を算出する（ステップＳ３８１１）。情報取得部１０７は、ＶＩＣＳなどの外部ネットワーク媒体１０６から、道路リンクの所要時間情報を取得する（ステップＳ３８１２）。第２時間算出部３７４０は、情報取得部１０７が取得したリンクＩＤに対する所要時間情報、地図蓄積部１０４に蓄積されたリンクＩＤ情報を用いて、判定部１１４が抽出し、通知部１０９が通知可能とした分岐点、合流点、分岐点と合流点を結ぶ複数の経路（ノードＩＤ系列）における所要時間を算出する（ステップＳ３８１３）。第２比較部３７４１は、第２時間算出部３７４０が算出した分岐点と合流点を結ぶ複数のノードＩＤ系列に対する所要時間から、所要時間の大小関係を算出する（ステップＳ３８１４）。第４通知部３７４２は、分岐点と合流点を結ぶ複数のノードＩＤ系列について、比較部３７２４が算出した所要時間大小関係と第２比較部３７４１が算出した所要時間大小関係の相違を算出し（ステップＳ３８１５）、大小関係が異なるときはステップＳ３８１６に進む（ステップＳ３８１５のＹｅｓ）。大小関係が一致するときはステップＳ１２０１に戻る（ステップＳ３８１５のＮｏ）。大小関係が異なるとき、情報提供部３７１０は、第４通知部３７４２が通知可能と判断した分岐点ＩＤ、合流点ＩＤを結ぶ複数のノードＩＤ系列に対して第２比較部３７４１が算出した所要時間の大小関係情報をユーザに提供する（ステップＳ３８１６）。終了するか判定を行い（ステップＳ３８１７）、終了するならば、処理を終了する（ステップＳ３８１７のＹｅｓ）。終了しないならば、ステップＳ１２０１に戻る（ステップＳ３８１７のＮｏ）。
【０１１６】
以上、実施の形態および変形例について説明したが、本発明の所要時間情報提供装置は、これらに限定されるものではない。以上の実施の形態および変形例で説明した所要時間情報提供装置が備える各機能を、矛盾しない限りにおいて、任意に組み合わせて構成される装置であってもよい。
【産業上の利用可能性】
【０１１７】
以上のように、本発明の所要時間情報提供装置は、カーナビゲーション装置やＧＰＳ、地図付き携帯電話等の車両の位置情報を取得し、所要時間情報を提供する装置に適用できる。
【図面の簡単な説明】
【０１１８】
【図１】本発明の実施の形態１における所要時間情報提供装置の構成を示すブロック図である。
【図２】履歴蓄積部に蓄積された走行履歴の例を示す図である。
【図３】地図情報蓄積部に蓄積された地図情報の例を示す図である。
【図４】ノード抽出部がノード系列を抽出する例を示す図である。
【図５】分岐点、合流点、抽出経路の例を示す図である。
【図６】遠回りとなる例を示す図である。
【図７】判定部が偽と判定する分岐点、合流点の例を示す図である。
【図８】判定部が真と判定する分岐点、合流点の例を示す図である。
【図９】情報取得部が取得する所要時間情報の例を示す図である。
【図１０】情報算出部が抽出した経路中の所要時間情報を算出する例を示す図である。
【図１１】情報提供部が所要時間情報を提供する例を示す図である。
【図１２】始点、終点が一致しないノードＩＤ系列からでも２地点間を結ぶ異なる経路を抽出できる例を示す図である。
【図１３】異なる経路以外の渋滞情報も提供する例を示す図である。
【図１４】本発明の実施の形態１における所要時間情報提供装置の動作の例を示すフローチャートである。
【図１５】分岐点への進入方向、合流点からの脱出方向が異なる例を示す図である。
【図１６】本発明の実施の形態１の変形例１における所要時間情報提供装置の構成を示すブロック図である。
【図１７】判定部が同じ合流点後ＩＤの組み合わせを出力する例を示す図である。
【図１８】本発明の実施の形態１の変形例１における所要時間情報提供装置の動作の例を示すフローチャートである。
【図１９】ランドマークを訪問するために異なる経路を通る例を示す図である。
【図２０】ランドマークが分岐点となる例を示す図である。
【図２１】本発明の実施の形態１の変形例４における所要時間情報提供装置の構成を示すブロック図である。
【図２２】履歴蓄積部に蓄積された走行履歴の例を示す図である。
【図２３】ランドマーク蓄積部に蓄積されたランドマーク情報の例を示す図である。
【図２４】ノード抽出部がノード系列を抽出する例を示す図である。
【図２５】移動先ノードＩＤ系列を予測する例を示す図である。
【図２６】本発明の実施の形態１の変形例４における所要時間情報提供装置の動作の例を示すフローチャートである。
【図２７】予測された移動経路上に２組以上の分岐点と合流点との組（ａ、ｂ）、（ｃ、ｄ）がある場合について所要時間情報を提供する多様な表示例を模式的に示す図である。
【図２８】本発明の実施の形態２における所要時間情報提供装置の構成を示すブロック図である。
【図２９】ノード抽出部がノード系列と通過時刻を抽出する例を示す図である。
【図３０】時間算出部が分岐点合流点間のノードＩＤ系列に対する所要時間を算出する例を示す図である。
【図３１】類似部が経路の所要時間の類似を判定する例を示す図である。
【図３２】本発明の実施の形態２における所要時間情報提供装置の動作の例を示すフローチャートである。
【図３３】本発明の実施の形態２の変形例３における所要時間情報提供装置の構成を示すブロック図である。
【図３４】反事例部が反事例数から経路の所要時間の大小関係の判定可否を判断する例を示す図である。
【図３５】本発明の実施の形態２の変形例３における所要時間情報提供装置の動作の例を示すフローチャートである。
【図３６】本発明の実施の形態３における所要時間情報提供装置の構成を示すブロック図である。
【図３７】現在時間部が現在の走行における出発地から現在地までの所要時間を算出する例を示す図である。
【図３８】過去時間部が出発地から現在地までのノードＩＤ系列における過去の所要時間を算出する例を示す図である。
【図３９】本発明の実施の形態３における所要時間情報提供装置の動作の例を示すフローチャートである。
【図４０】本発明の実施の形態４における所要時間情報提供装置の構成を示すブロック図である。
【図４１】本発明の実施の形態４における所要時間情報提供装置の動作の例を示すフローチャートである。
【図４２】２地点間を結ぶ複数経路の例を示す図である。
【符号の説明】
【０１１９】
１０１  地点取得部
１０２  時刻取得部
１０３  履歴蓄積部
１０４  地図蓄積部
１０５  経路抽出部
１０６  外部ネットワーク媒体
１０７  情報取得部
１０８  情報算出部
１０９  通知部
１１０  情報提供部
１１１  ノード抽出部
１１２  仮定部
１１３  分割部
１１４  判定部
１４０５  経路抽出部
１４０９  通知部
１４１２  仮定部
１４１３  分割部
１４１４  判定部
１４１５  現在ノード抽出部
１９０３  履歴蓄積部
１９０９  通知部
１９１１  ノード抽出部
１９１２  仮定部
１９１３  分割部
１９１４  判定部
１９１６  駐車検知部
１９１７  ランドマーク蓄積部
１９１８  移動先ノード予測部
２５０８  情報算出部
２５１０  情報提供部
２５１１  ノード抽出部
２５２１  時間算出部
２５２２  類似部
２５２３  第２通知部
３０２４  比較部
３０２５  反事例部
３３１１  ノード抽出部
３３０８  情報算出部
３３０９  通知部
３３１０  情報提供部
３３１１  ノード抽出部
３３３０  現在経路部
３３３１  現在時間部
３３３２  過去時間部
３３３３  第２類似部
３３３４  第３通知部
３７０８  情報算出部
３７１０  情報提供部
３７４０  第２時間算出部
３７４１  第２比較部
３７４２  第４通知部
【図１】
2008261714.tif 000003
【図２】
2008261714.tif 000004
【図３】
2008261714.tif 000005
【図４】
2008261714.tif 000006
【図５】
2008261714.tif 000007
【図６】
2008261714.tif 000008
【図７】
2008261714.tif 000009
【図８】
2008261714.tif 000010
【図９】
2008261714.tif 000011
【図１０】
2008261714.tif 000012
【図１１】
2008261714.tif 000013
【図１２】
2008261714.tif 000014
【図１３】
2008261714.tif 000015
【図１４】
2008261714.tif 000016
【図１５】
2008261714.tif 000017
【図１６】
2008261714.tif 000018
【図１７】
2008261714.tif 000019
【図１８】
2008261714.tif 000020
【図１９】
2008261714.tif 000021
【図２０】
2008261714.tif 000022
【図２１】
2008261714.tif 000023
【図２２】
2008261714.tif 000024
【図２３】
2008261714.tif 000025
【図２４】
2008261714.tif 000026
【図２５】
2008261714.tif 000027
【図２６】
2008261714.tif 000028
【図２７】
2008261714.tif 000029
【図２８】
2008261714.tif 000030
【図２９】
2008261714.tif 000031
【図３０】
2008261714.tif 000032
【図３１】
2008261714.tif 000033
【図３２】
2008261714.tif 000034
【図３３】
2008261714.tif 000035
【図３４】
2008261714.tif 000036
【図３５】
2008261714.tif 000037
【図３６】
2008261714.tif 000038
【図３７】
2008261714.tif 000039
【図３８】
2008261714.tif 000040
【図３９】
2008261714.tif 000041
【図４０】
2008261714.tif 000042
【図４１】
2008261714.tif 000043
【図４２】
2008261714.tif 000044
【手続補正書】
【提出日】平成20年2月25日(2008.2.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
２地点間を結ぶ複数の異なる移動経路があった場合、各移動経路を通って移動体が２地点間を移動するために必要な所要時間に関する情報である所要時間情報を、所定の移動経路について提供する所要時間情報提供装置であって、
所定の間隔で取得された時刻情報と、前記各時刻に移動体が位置していた地点情報との組で表される移動履歴情報を蓄積する履歴蓄積手段に蓄積されている地点情報を時刻の順に結んで表される複数の移動経路のうちから、２以上の前記移動経路に共通する２地点を結ぶ複数の異なる移動経路を抽出する経路抽出手段と、
前記経路抽出手段によって抽出された前記移動経路ごとに、前記２地点間の移動に要する所要時間情報を算出する情報算出手段と、
算出された前記所要時間情報を前記移動体の現在位置に関連付けて利用者に提供する情報提供手段と
を備えることを特徴とする所要時間情報提供装置。
【請求項２】
前記経路抽出手段は、前記２地点のうち、複数の移動経路に分岐する地点を分岐点とし、複数の前記移動経路が合流する地点を合流点として、共通の分岐点と合流点とを結ぶ複数の移動経路のうち、移動経路同士で互いに一致する部分を含まない複数の移動経路を抽出する
ことを特徴とする請求項１に記載の所要時間情報提供装置。
【請求項３】
前記経路抽出手段は、共通の分岐点と合流点とを結ぶ複数の移動経路のうち、いずれの１つも同じ経路を２度以上含まない移動経路を抽出する
ことを特徴とする請求項２に記載の所要時間情報提供装置。
【請求項４】
前記経路抽出手段は、移動体が前記分岐点を通過する前の移動方向と前記合流点を通過する後の移動方向とのいずれもが、互いに一致する移動経路を抽出する
ことを特徴とする請求項３に記載の所要時間情報提供装置。
【請求項５】
前記所要時間情報提供装置は、さらに、
前記履歴蓄積手段に蓄積されている前記移動履歴から、前記移動体の移動先を予測する移動先予測手段を備え、
前記移動先予測手段によって予測された移動先までの移動経路上に、前記経路抽出手段によって抽出された複数の移動経路がある場合、前記情報提供手段は、前記分岐点と前記合流点とを結ぶ異なる移動経路についての所要時間情報を提供する
ことを特徴とする請求項４に記載の所要時間情報提供装置。
【請求項６】
前記所要時間情報提供装置は、さらに、
現在時刻と前記移動体の現在位置との組を取得する現在位置取得手段を備え、
前記履歴蓄積手段は、所定時間以上エンジンが停止していた地点を移動経路の出発地または移動先として、前記エンジン停止地点で移動履歴を区切って蓄積し、
前記移動先予測手段は、前記履歴蓄積手段に蓄積されている地点を時刻の順に結んで表される複数の移動経路のうち、出発地から現在位置までの移動経路が一致する移動経路のいずれかを、現在の移動先に至る移動経路と予測する
ことを特徴とする請求項５に記載の所要時間情報提供装置。
【請求項７】
前記情報提供手段は、前記移動体の現在位置が、抽出された分岐点から所定の閾値以内の距離に近づいたとき算出された所要時間情報を提供する
ことを特徴とする請求項６に記載の所要時間情報提供装置。
【請求項８】
前記情報算出手段は、分岐点と合流点との間の異なる複数の前記移動経路について、移動経路同士の所要時間の大小関係を表す所要時間情報を算出する
ことを特徴とする請求項１に記載の所要時間情報提供装置。
【請求項９】
前記情報算出手段は、前記２地点のうち、複数の移動経路に分岐する地点を分岐点とし、複数の前記移動経路が合流する地点を合流点として、分岐点と合流点との間の異なる複数の前記移動経路のそれぞれについて、前記履歴蓄積手段に蓄積されている時刻と地点との組から、分岐点と合流点との間の移動に要する所要時間を算出し、
前記所要時間情報提供装置は、さらに、
前記分岐点と前記合流点とを結ぶ移動経路ごとに算出された所要時間を、移動経路同士で比較し、比較された所要時間の差が所定の閾値以内である移動経路について所要時間が類似すると判断する類似判断手段を備え、
前記情報提供手段は、前記類似判断手段により所要時間が類似すると判断された移動経路について前記所要時間情報を提供する
ことを特徴とする請求項１に記載の所要時間情報提供装置。
【請求項１０】
前記情報算出手段は、分岐点と合流点との間の異なる複数の前記移動経路のそれぞれについて、分岐点と合流点との間の移動に要する所要時間の平均を算出し、
前記類似判断手段は、前記分岐点と前記合流点とを結ぶ異なる移動経路ごとに算出された所要時間の平均を、前記移動経路同士で比較し、比較された所要時間の平均の差が閾値以内である移動経路について所要時間が類似すると判定する
ことを特徴とする請求項９に記載の所要時間情報提供装置。
【請求項１１】
前記情報算出手段は、前記２地点のうち、複数の移動経路に分岐する地点を分岐点とし、複数の前記移動経路が合流する地点を合流点として、分岐点と合流点との間の異なる複数の前記移動経路のそれぞれについて、前記履歴蓄積手段に蓄積されている時刻と地点との組から、分岐点と合流点との間の移動に要する所要時間の平均を算出し、
前記所要時間情報提供装置は、さらに、
前記分岐点と合流点を結ぶ異なる移動経路ごとに、前記情報算出手段が算出した所要時間の平均を比較し、所要時間の平均の大小関係を算出する比較手段と、
前記比較手段によって算出された前記大小関係に反する移動履歴の数を算出し、前記比較手段によって算出された前記大小関係に反する前記移動履歴の数が多い場合に、反事例が多いと判定する反事例判定手段とを備え、
前記情報提供手段は、前記反事例判定手段により反事例が多いと判断された移動経路について前記所要時間情報を提供する
ことを特徴とする請求項１に記載の所要時間情報提供装置。
【請求項１２】
前記類似判断手段は、前記履歴蓄積手段に蓄積されている移動履歴から、前記分岐点と合流点を結ぶ異なる移動経路のそれぞれの通過回数を算出し、
前記情報提供手段は、前記類似判断手段により算出された通過回数が閾値以下である移動経路について前記所要時間情報を提供する
ことを特徴とする請求項９に記載の所要時間情報提供装置。
【請求項１３】
前記類似判断手段は、前記履歴蓄積手段に蓄積されている移動履歴から、前記分岐点と合流点を結ぶ異なる移動経路のそれぞれの通過回数を算出し、
前記情報提供手段は、前記類似判断手段により算出された通過回数が類似する移動経路について前記所要時間情報を提供する
ことを特徴とする請求項９に記載の所要時間情報提供装置。
【請求項１４】
前記情報算出手段は、前記２地点のうち、複数の移動経路に分岐する地点を分岐点とし、複数の前記移動経路が合流する地点を合流点として、分岐点と合流点との間の異なる複数の前記移動経路のそれぞれについて、前記履歴蓄積手段に蓄積されている時刻と地点との組から、分岐点と合流点との間の移動に要する所要時間を算出し、
前記所要時間情報提供装置は、さらに、
前記履歴蓄積手段に蓄積されている時刻から、前記複数の移動経路を最も新しい時刻で通過したときの現在所要時間を算出する現在時間算出手段と、
前記履歴蓄積手段に蓄積されている時刻から、最も新しい時刻で通過したときを除く、前記移動経路の過去所要時間を算出する過去時間算出手段と、
前記現在所要時間と前記過去所要時間とが類似するか否かを判定する第２類似判断手段とを備え、
前記情報提供手段は、前記第２類似判断手段が類似しないと判定したときに、前記所要時間情報を提供する
ことを特徴とする請求項１に記載の所要時間情報提供装置。
【請求項１５】
前記情報算出手段は、前記２地点のうち、複数の移動経路に分岐する地点を分岐点とし、複数の前記移動経路が合流する地点を合流点として、分岐点と合流点との間の異なる複数の前記移動経路のそれぞれについて、前記履歴蓄積手段に蓄積されている時刻と地点との組から、分岐点と合流点との間の移動に要する所要時間を算出し、
前記所要時間情報提供装置は、さらに、
前記分岐点と合流点を結ぶ異なる移動経路ごとに、前記情報算出手段が算出した所要時間を比較し、前記所要時間の大小関係を算出する比較手段と、
外部から提供される道路情報を取得し、取得された前記道路情報から前記分岐点と前記合流点とを結ぶ異なる移動経路ごとに、所要時間を算出する第２時間算出手段と、
前記分岐点と合流点を結ぶ異なる移動経路ごとに、前記第２時間算出手段が算出した所要時間を比較し、前記所要時間の大小関係を算出する第２比較手段とを備え、
前記情報提供手段は、前記比較手段が算出した大小関係と前記第２比較手段が算出した大小関係とが異なる移動経路について、第２時間算出手段によって算出された所要時間に基づく所要時間情報を提供する
ことを特徴とする請求項１に記載の所要時間情報提供装置。
【請求項１６】
２地点間を結ぶ複数の異なる移動経路があった場合、各移動経路を通って移動体が２地点間を移動するために必要な所要時間に関する情報である所要時間情報を、所定の移動経路について提供する所要時間情報提供方法であって、
所定の間隔で取得された時刻情報と、前記各時刻に移動体が位置していた地点情報との組で表される移動履歴情報を蓄積する履歴蓄積手段から取得した地点情報を時刻の順に結んで表される複数の移動経路のうちから、２以上の前記移動経路に共通する２地点を結ぶ複数の異なる移動経路を抽出する経路抽出ステップと、
前記経路抽出ステップによって抽出された前記移動経路ごとに、前記２地点間の移動に要する所要時間情報を算出する情報算出ステップと、
算出された前記所要時間情報を前記移動体の現在位置に関連付けて利用者に提供する情報提供ステップと
を含むことを特徴とする所要時間情報提供方法。
【請求項１７】
２地点間を結ぶ複数の異なる移動経路があった場合、各移動経路を通って移動体が２地点間を移動するために必要な所要時間に関する情報である所要時間情報を、所定の移動経路について提供する所要時間情報提供装置のためのプログラムであって、
コンピュータに所定の間隔で取得された時刻情報と、前記各時刻に移動体が位置していた地点情報との組で表される移動履歴情報を蓄積する履歴蓄積手段から取得した地点情報を時刻の順に結んで表される複数の移動経路のうちから、２以上の前記移動経路に共通する２地点を結ぶ複数の異なる移動経路を抽出する経路抽出ステップと、前記経路抽出ステップによって抽出された前記移動経路ごとに、前記２地点間の移動に要する所要時間情報を算出する情報算出ステップと、算出された前記所要時間情報を前記移動体の現在位置に関連付けて利用者に提供する情報提供ステップとを実行させるためのプログラム。