(57)【要約】      （修正有）【課題】より好適な移動経路を生成するナビゲーション方法を提供する。【解決手段】車両の第一の位置および目的地を取得し、車両の通過が予想される複数の道路合流点を決定する。複数の道路合流点を、第一の位置からの距離が閾値を下回るローカル道路合流点と、閾値を上回る遠隔道路合流点に分類し、ローカル道路合流点を通過するのに必要な所要時間であるローカル道路合流点走行時間を、ローカル道路合流点に対応するリアルタイムの交通データを利用して計算する。一つ以上の遠隔道路合流点を通過するのに必要な所要時間である遠隔道路合流点走行時間を、遠隔道路合流点に対応する過去の交通データを利用して計算する。通過が予想される複数の道路セグメントについて走行時間を計算し、道路セグメントの走行時間と、ローカル道路合流点走行時間と、遠隔道路合流点走行時間と、に基づいて、第一の位置と前記目的地とを結ぶ経路を生成する。【選択図】図３
2019184600.tif 000002
【特許請求の範囲】
【請求項１】
車両の走行経路を生成する方法であって、
前記車両の第一の位置および目的地を取得する取得ステップと、
前記第一の位置と前記目的地に基づいて、前記車両の通過が予想される複数の道路合流点を決定する決定ステップと、
前記複数の道路合流点を、前記第一の位置からの距離が閾値を下回るローカル道路合流点と、前記距離が前記閾値を上回る遠隔道路合流点に分類する分類ステップと、
一つ以上の前記ローカル道路合流点を通過するのに必要な所要時間であるローカル道路合流点走行時間を、前記ローカル道路合流点に対応するリアルタイムの交通データを利用して計算する第一の計算ステップと、
一つ以上の前記遠隔道路合流点を通過するのに必要な所要時間である遠隔道路合流点走行時間を、前記遠隔道路合流点に対応する過去の交通データを利用して計算する第二の計算ステップと、
前記車両の通過が予想される複数の道路セグメントについて走行時間を計算する第三の計算ステップと、
前記道路セグメントの走行時間と、前記ローカル道路合流点走行時間と、前記遠隔道路合流点走行時間と、に基づいて、前記第一の位置と前記目的地とを結ぶ経路を生成する生成ステップと、
を含む、方法。
【請求項２】
前記第一の計算ステップでは、
前記リアルタイムの交通データとして、前記ローカル道路合流点におけるリアルタイムの通過所要時間と、前記ローカル道路合流点における交通信号に関するデータを取得する、
請求項１に記載の方法。
【請求項３】
前記第二の計算ステップでは、
前記過去の交通データとして、前記遠隔道路合流点における過去の通過所要時間を取得する、
請求項１または２に記載の方法。
【請求項４】
前記道路合流点は、交差点、高速道路入口、高速道路出口のうちの少なくともいずれかを含む、
請求項１から３のいずれかに記載の方法。
【請求項５】
前記複数の道路セグメントは、前記第一の位置からの距離が第二の閾値を下回るローカル道路セグメントと、前記距離が前記第二の閾値を上回る遠隔道路セグメントを含み、
前記第三の計算ステップでは、
前記ローカル道路セグメントの走行時間を、前記ローカル道路セグメントに対応するリアルタイムの交通データを利用して計算し、
前記遠隔道路セグメントの走行時間を、前記遠隔道路セグメントに対応する過去の交通データを利用して計算する、
請求項１から４のいずれかに記載の方法。
【請求項６】
前記ローカル道路合流点走行時間と、前記ローカル道路合流点の通過に実際に要した時間との差、および、前記遠隔道路合流点走行時間と、前記遠隔道路合流点の通過に実際に要した時間との差に基づいて、前記閾値を較正する較正ステップをさらに含む、
請求項１から５のいずれかに記載の方法。
【請求項７】
前記較正ステップでは、算出した前記ローカル道路合流点走行時間の合計と、前記ローカル道路合流点の通過に実際に要した時間の合計の差が最も小さくなり、かつ、算出した前記遠隔道路合流点走行時間の合計と、前記遠隔道路合流点の通過に実際に要した時間の合計の差が最も小さくなる前記閾値を決定する、
請求項６に記載の方法。
【請求項８】
車両の走行経路を生成するシステムであって、
前記車両の第一の位置および目的地を取得する取得手段と、
前記第一の位置と前記目的地に基づいて、前記車両の通過が予想される複数の道路合流点を決定する決定手段と、
前記複数の道路合流点を、前記第一の位置からの距離が閾値を下回るローカル道路合流点と、前記距離が前記閾値を上回る遠隔道路合流点に分類する分類手段と、
一つ以上の前記ローカル道路合流点を通過するのに必要な所要時間であるローカル道路合流点走行時間を、前記ローカル道路合流点に対応するリアルタイムの交通データを利用して計算する第一の計算手段と、
一つ以上の前記遠隔道路合流点を通過するのに必要な所要時間である遠隔道路合流点走行時間を、前記遠隔道路合流点に対応する過去の交通データを利用して計算する第二の計算手段と、
前記車両の通過が予想される複数の道路セグメントについて走行時間を計算する第三の計算手段と、
前記道路セグメントの走行時間と、前記ローカル道路合流点走行時間と、前記遠隔道路合流点走行時間と、に基づいて、前記第一の位置と前記目的地とを結ぶ経路を生成する生成手段と、
を含む、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願への相互参照）
本出願は、「DYNAMIC VEHICLE NAVIGATION SYSTEM WITH ROADWAY JUNCTION IMPACT」と題し、２０１８年４月１０日に出願された米国特許出願第１５／９５０，０５７号の優先権を主張する。これらの特許出願は、その全体が参照によって本願明細書に援用される。
【０００２】
本開示は、旅程ルートの走行時間を推定するためのナビゲーションシステムに関する。特に、本明細書は、道路合流点が走行時間に与える影響を利用して推定走行時間の精度を高めるナビゲーションシステムに関する。
【背景技術】
【０００３】
ユーザは、走行中に有用な情報を提供するためにコンピューティング装置上のナビゲーションシステムに頼ることが多くなってきている。しかし、既存のシステムは、一般にルートまたは道路の平均を考慮に入れるだけであり、交差点、高速道路オンランプ、および他の道路合流点における遅延の影響を考慮に入れていない。
【０００４】
輸送ネットワークでは、道路の形状および様々な出発地−目的地のペアにより、同じ道路上を走行する車両は、他の道路に接続するための異なる移動をすることがある。そのような移動の結果、交差点のような道路合流点において種々の遅延をもたらし、これがルート計算およびナビゲーションの結果に影響を及ぼし得る。
【０００５】
いくつかの既存のナビゲーションシステムは、総距離または道路走行時間の平均に基づいて個々の車両についての最短ルートを検索する。いくつかのナビゲーションシステムは、右左折に関する制限、ならびに距離および速度に基づいて曲がるのに必要な時間を考慮に入れる。しかし、道路合流点における車両待ち行列の結果、個々の車両について予期せぬ遅れおよび走行時間の高い不確実性をもたらし、これらの既存のシステムによっては対処されていない。
【０００６】
車両ナビゲーションを説明する１つの特許公報は、米国特許第６，０３４，６２６号明細書（特許文献１）である。特許文献１は、ユーザの好みに基づいて優先ルートおよび非優先ルートから各個々の車両についての最適なルートを検索するナビゲーションシステムを説明している。特許文献１では右左折時間が考慮されるが、これらはより良好に推定されておらず、その理由は、特許文献１は、交通状況、信号、および他の動的要因に関係なく、道路速度制限および右左折曲率に基づいて交差点遅延を一定の条件で考慮するためである。しかし、車両待ち行列、交通信号などは、推定走行時間の精度に著しい影響を与える可能性がある。さらに、特許文献１は、例えば高速道路と幹線道路との間または交差点を通る接続を考慮していないため、システムが都市道路ネットワークに一般化されることを妨げている。
【０００７】
他のナビゲーションシステムが、非特許文献１ならびに非特許文献２に説明されている。非特許文献１および非特許文献２では、ルート選択アルゴリズムの右左折時間を考慮して、エッジベースのグラフおよびノード収縮法それぞれに基づいて個々の車両についての最短ルートを検索する。どちらの調査においても、交差点での右左折速度および右左折距離によって右左折負荷が決定される。これらの調査では、右左折の通過速度に関する交通の負荷を考慮しているが、道路合流点までの待ち行列および待機時間などの交通の影響は考慮に入れていない。さらに、非特許文献１および非特許文献２では、例えば、車両が実質的に直線で走行する可能性があるような他の合流点タイプについてではなく、特定の角
度を通る右左折運動の負荷のみを推定する。
【０００８】
別のナビゲーションシステムが、非特許文献３に説明されている。非特許文献３は、市内の交通センターから定期的に受信したリアルタイムの交通データにしたがって、車両の動的な最適ルートを計画するために簡易化されたリアルタイム道路ネットワークモデルを考慮する。非特許文献３は、限られた交差点の種類におけるリアルタイムの遅延を使用する。ただし、交差点での車両待ち行列はすばやく変化し、そのため車両がこれらの交差点に到着する前に待ち行列が変わる可能性があるため、ルート全体の待ち行列による影響の計算は、多くの場合、遠く離れた交差点では不正確になる。したがって、単にリアルタイムの遅延を使用することは、特により長い旅行を伴う車両にとって最適なルート推定には不十分であり、リアルタイムの遅延の初期計算はかなりの帯域幅および計算リソースを消費し、これは、リアルタイムの遅延が更新されるたびに度を増す。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国特許第６，０３４，６２６号明細書
【特許文献２】特開２００３−０２１５２４号公報
【非特許文献】
【００１０】
【非特許文献１】Volker L.，"Route Planning in Road Networks with Tum Costs"，Tech Report，University Karlsruhe，2008(Volker)
【非特許文献２】Geisberger R.，Vetter C，"Efficient Routing in Road Networks with Turn Costs"，International Symposium on Experimental Algorithms，vol.11，pp.100-111，2011(Geisberger)
【非特許文献３】Zhu Z.，Liu W.，Liu L.，Cui M.，Li J.，"A Simplified Real-Time Road Network Model Considering Intersection Delay and Its Application on Vehicle Navigation"，Applied Mechanics and Materials，vol.58，pp.1959-1965，2011(Zhu)
【発明の概要】
【００１１】
前述のアプローチの制限に対処することが望ましい。
【００１２】
システムは、道路合流点の影響を使用して車両ナビゲーションを提供する技術によって従来技術の欠点を克服する。一実装形態では、システムは、作動中に、例えばプロセッサ、非一時的記憶装置、およびプロセッサによって実行される命令を使用してシステムに工程を実行させる、システムにインストールされたソフトウェア、ファームウェア、ハードウェア、またはそれらの組み合わせを含む。
いくつかの実装形態によれば、工程は、プロセッサによって、クライアント装置の第１の位置および目的地を識別するステップと、プロセッサによって、クライアント装置の第１の位置、目的地、および地図データに基づいて複数の道路セグメントおよび複数の道路合流点を決定するステップであって、複数の道路合流点は、閾値を下回る１つ以上のローカル道路合流点と、閾値を上回る１つ以上の遠隔道路合流点とを含むステップと、プロセッサによって、複数の道路セグメントの各道路セグメントについての道路セグメント走行時間を計算するステップと、プロセッサによって、１つ以上のローカル道路合流点それぞれについてのローカル道路合流点走行時間に対する交通のローカル影響、および１つ以上の遠隔道路合流点のそれぞれについての遠隔道路合流点走行時間に対する交通の遠隔影響を計算するステップと、地図データ、複数の道路セグメントについての道路セグメント走行時間、１つ以上のローカル道路合流点のローカル道路合流点走行時間および１つ以上の遠隔道路合流点の遠隔道路合流点走行時間を使用して、クライアント装置の第１の位置と目的地との間のルートのセットを決定するステップ、プロセッサによって、道路セグメン
ト走行時間、ローカル道路合流点走行時間、および遠隔道路合流点走行時間に基づいて、ルートのセット内の各ルートについての総走行時間を計算するステップと、プロセッサによって、ルートのセットから選択された特定のルートについてのルート案内データを決定するステップと、プロセッサによって、ルート案内データに基づいて特定のルートについてのルート案内データをクライアント装置に提供するステップとを含む。
【００１３】
実装形態は、以下の特徴のうちの１つ以上を含む。
ローカル道路合流点走行時間に対する交通のローカル影響を計算するステップが、プロセッサによって、ローカル道路合流点におけるリアルタイムの遅延を含むローカル道路合流点のローカル道路合流点情報を受信するステップであって、ローカル道路合流点は、信号機、交差点、高速道路オンランプ、および高速道路オフランプのうちの１つ以上を含むステップと、プロセッサによって、リアルタイムの遅延に基づいて交通のローカル影響を計算するステップとを含む、コンピュータ実装方法。
遠隔道路合流点走行時間に対する交通の遠隔影響を計算するステップが、プロセッサによって、遠隔道路合流点における過去の時間遅延を含む遠隔道路合流点の遠隔道路合流点情報を受信するステップであって、遠隔道路合流点は、信号機、交差点、高速道路オンランプ、および高速道路オフランプのうちの１つ以上を含むステップと、プロセッサによって、過去の時間遅延に基づいて交通の遠隔影響を計算するステップとを含む、コンピュータ実装方法。
複数の道路セグメントが閾値内のローカル道路セグメントと、閾値を超える遠隔道路セグメントとを含むコンピュータ実装方法。
複数の道路セグメントの各道路セグメントについての道路セグメント走行時間を決定するステップが、プロセッサによって、閾値に基づいてローカル道路セグメントおよび遠隔道路セグメントを識別するステップをであって、道路セグメント走行時間は、ローカル道路セグメント走行時間および遠隔道路セグメント走行時間のうちの１つ以上を含み、ローカル道路セグメント走行時間は、ローカル道路セグメントを通るリアルタイム走行時間に基づいており、遠隔道路セグメント走行時間は、遠隔道路セグメントを通る過去の走行時間に基づくステップとを含む、コンピュータ実装方法。
総走行時間を計算するステップが、ルート内の道路セグメントのローカル道路セグメント走行時間および遠隔道路セグメント走行時間に基づいて、ルートのセット内の各ルートにおける道路セグメントのついての平均道路セグメント走行時間を決定するステップを含む、コンピュータ実装方法。
複数の道路合流点が少なくとも１つの高速道路オンランプを含む、コンピュータ実装方法。
ルート案内データに基づいて特定のルートについてのルート案内をクライアント装置に提供するステップが、クライアント装置による特定のルートの通過中のクライアント装置の第２の位置に基づいて特定のルートについての走行時間を再計算するステップを含む、コンピュータ実装方法。
プロセッサによって、ローカル道路合流点走行時間、遠隔道路合流点走行時間、および測定された走行時間の中の偏差を使用して、閾値を較正するステップを含む、コンピュータ実装方法。
特定のルートについてのルート案内データを決定するステップが、プロセッサによって、総走行時間および特定のルート属性についての記憶されたユーザの好みに基づいてルートのセットから特定のルートを選択するステップを含む、コンピュータ実装方法。
【００１４】
本発明に係る方法は、
車両の走行経路を生成する方法であって、前記車両の第一の位置および目的地を取得する取得ステップと、前記第一の位置と前記目的地に基づいて、前記車両の通過が予想される複数の道路合流点を決定する決定ステップと、前記複数の道路合流点を、前記第一の位置からの距離が閾値を下回るローカル道路合流点と、前記距離が前記閾値を上回る遠隔道
路合流点に分類する分類ステップと、一つ以上の前記ローカル道路合流点を通過するのに必要な所要時間であるローカル道路合流点走行時間を、前記ローカル道路合流点に対応するリアルタイムの交通データを利用して計算する第一の計算ステップと、一つ以上の前記遠隔道路合流点を通過するのに必要な所要時間である遠隔道路合流点走行時間を、前記遠隔道路合流点に対応する過去の交通データを利用して計算する第二の計算ステップと、前記車両の通過が予想される複数の道路セグメントについて走行時間を計算する第三の計算ステップと、前記道路セグメントの走行時間と、前記ローカル道路合流点走行時間と、前記遠隔道路合流点走行時間と、に基づいて、前記第一の位置と前記目的地とを結ぶ経路を生成する生成ステップと、を含む。
【００１５】
なお、前記第一の計算ステップでは、前記リアルタイムの交通データとして、前記ローカル道路合流点におけるリアルタイムの通過所要時間と、前記ローカル道路合流点における交通信号に関するデータを取得することを特徴としてもよい。
また、前記第二の計算ステップでは、前記過去の交通データとして、前記遠隔道路合流点における過去の通過所要時間を取得することを特徴としてもよい。
また、前記道路合流点は、交差点、高速道路入口、高速道路出口のうちの少なくともいずれかを含むことを特徴としてもよい。
また、前記複数の道路セグメントは、前記第一の位置からの距離が第二の閾値を下回るローカル道路セグメントと、前記距離が前記第二の閾値を上回る遠隔道路セグメントを含み、前記第三の計算ステップでは、前記ローカル道路セグメントの走行時間を、前記ローカル道路セグメントに対応するリアルタイムの交通データを利用して計算し、前記遠隔道路セグメントの走行時間を、前記遠隔道路セグメントに対応する過去の交通データを利用して計算することを特徴としてもよい。
また、前記ローカル道路合流点走行時間と、前記ローカル道路合流点の通過に実際に要した時間との差、および、前記遠隔道路合流点走行時間と、前記遠隔道路合流点の通過に実際に要した時間との差に基づいて、前記閾値を較正する較正ステップをさらに含むことを特徴としてもよい。
また、前記較正ステップでは、算出した前記ローカル道路合流点走行時間の合計と、前記ローカル道路合流点の通過に実際に要した時間の合計の差が最も小さくなり、かつ、算出した前記遠隔道路合流点走行時間の合計と、前記遠隔道路合流点の通過に実際に要した時間の合計の差が最も小さくなる前記閾値を決定することを特徴としてもよい。
【００１６】
本発明に係るシステムは、
車両の走行経路を生成するシステムであって、前記車両の第一の位置および目的地を取得する取得手段と、前記第一の位置と前記目的地に基づいて、前記車両の通過が予想される複数の道路合流点を決定する決定手段と、前記複数の道路合流点を、前記第一の位置からの距離が閾値を下回るローカル道路合流点と、前記距離が前記閾値を上回る遠隔道路合流点に分類する分類手段と、一つ以上の前記ローカル道路合流点を通過するのに必要な所要時間であるローカル道路合流点走行時間を、前記ローカル道路合流点に対応するリアルタイムの交通データを利用して計算する第一の計算手段と、一つ以上の前記遠隔道路合流点を通過するのに必要な所要時間である遠隔道路合流点走行時間を、前記遠隔道路合流点に対応する過去の交通データを利用して計算する第二の計算手段と、前記車両の通過が予想される複数の道路セグメントについて走行時間を計算する第三の計算手段と、前記道路セグメントの走行時間と、前記ローカル道路合流点走行時間と、前記遠隔道路合流点走行時間と、に基づいて、前記第一の位置と前記目的地とを結ぶ経路を生成する生成手段と、を含む。
【００１７】
本文献は、背景技術における問題に対処するための革新的な技術を開示している。この技術は、道路セグメントとは別に道路合流点における遅延を考慮することによって精度の向上を可能にすることができる。いくつかの実装形態はまた、ルートが計算または再計算
されるときに取り出し、処理される情報の量を低減することによってコンピュータ性能を向上させることもできる。これらおよび他の利点は以下にさらに詳細に記載される。
【００１８】
本発明は、例として説明されるものであり、添付の図面の図に限定されるものではない。図面では、同様の要素を指すために同様の参照番号が使用されている。
【図面の簡単な説明】
【００１９】
【図１】道路合流点の影響を用いた例示的な動的車両ナビゲーションシステムを示すブロック図である。
【図２】ナビゲーションアプリケーションを含む例示的なコンピューティング装置を示すブロック図である。
【図３】道路合流点の影響を使用してナビゲーションルートを生成するための例示的な方法の流れ図である。
【図４Ａ】遠隔道路合流点の影響を計算するための例示的な方法の流れ図である。
【図４Ｂ】ローカル道路合流点の影響を計算するための例示的な方法の流れ図である。
【図４Ｃ】道路セグメント走行時間を計算し、ルートを生成するための例示的な方法の流れ図である。
【図５Ａ】例示的な道路セグメントおよび道路合流点の図である。
【図５Ｂ】オンランプ、オフランプ、および道路セグメントを有する例示的な高速道路の図である。
【発明を実施するための形態】
【００２０】
道路合流点の影響を使用してナビゲーションルートを生成するための技術を以下に説明する。この技術は、旅行前または旅行中の道路合流点の影響を考慮して、最短走行時間で個々の車両の最適なルートを検索する動的車両ナビゲーションシステムを含む。システムは、交差点、高速道路オンランプ、およびオフランプへの高速道路出口車線などの道路合流点の影響をリアルタイムで更新し、それによって（例えば走行時間における）最短ルートを計算して、道路合流点の遅延および車両の走行時間の不確実性を低減すると共に、都市道路ネットワーク全体のパフォーマンスを向上させる。いくつかの実装形態では、道路セグメントは、道路セグメントを接続するローカル道路合流点および遠隔道路合流点を伴って、例えば、過去の交通状況およびリアルタイムの交通状況に基づいてそれらの走行時間とともに決定される。本明細書に説明する技術は、走行時間を短縮し、走行時間を予測する際の精度、したがって到着予定時刻および選択されたルートの推定時間の確実性を向上させ、帯域幅全体の使用量を低減させ、消費される計算リソースを低減する。
【００２１】
道路セグメントは、道路セグメントを１つ以上の他の道路セグメントに接続する１つ、２つ、またはいくつかの道路合流点を有する道路の区間または延長として定義される。場合によっては、道路セグメントは、２つの交差点間の道路の区間、１つ以上の接続道路合流点を有する、ある長さの高速道路または公道、または別の道路である。
【００２２】
道路合流点は、２つ以上の道路セグメントの接続点として定義される。いくつかの実装形態では、道路合流点は、道路セグメントを接続するためのゼロ距離を有する仮想リンクであり得るが、他の実装形態では、道路合流点は物理的サイズを含むものとして定義され得る。車両（または他のモバイルコンピューティングシステム１０８またはクライアント装置１１０）は、ルート案内を通じて、現在の道路セグメントを出て、一定時間道路合流点に留まり、次の道路セグメントに入って走行を続けることができる。道路合流点を通過する際の遅延、影響、ペナルティ、または負荷は、（例えば、実装形態に応じて、長さ、形状、および右左折の速度によって定義される基本の道路合流点走行時間に加えて）、道路合流点で費やされる時間または道路合流点で費やされる追加時間として定義され得る。
例えば、影響または負荷は、道路合流点を通過するための（例えば、右左折を行うのに費やされた遅延または時間による）待ち行列の待機時間および遅延の合計として推定され得る。
【００２３】
以下の図５Ａおよび図５Ｂを参照して、道路セグメントおよび道路合流点の例示的な実装形態をさらに詳細に図示および説明する。
【００２４】
いくつかの実装形態では、道路合流点の影響または遅延は、道路セグメント上のある車両が次の道路セグメントに入るのに費やすことに対して、同じ道路セグメント上の他の車両が異なる目標道路セグメントに入るのと比較した余分な時間を含む。ローカル道路合流点走行時間に対する交通の影響を使用することにより、システム１００は、所与のルートの総走行時間のより正確な評価をすることができる。
【００２５】
いくつかの実装形態では、道路合流点は、交差点、高速道路オンランプ、高速道路メータ（信号機）、高速道路オフランプ、高速道路上の出口車線、および同様の道路特徴などの道路特徴を含む。いくつかの実装形態では、道路合流点は、車線に基づいて、またはこれが接続する道路セグメントに基づいて区別することができ、例えば、システム１００は、左折用の第１の道路合流点、交差点を通過するための第２の道路合流点、および右折用の第３の道路合流点を含むものとして交差点を知覚することができる。したがって、１つの道路セグメントから他の様々な道路セグメントへ向かう車両、交通、およびルートを区別して精度をさらに向上させることができる。
【００２６】
図を参照すると、参照番号は、それらの参照番号が説明されている図面に示されているかどうかに関わらず、図のいずれにも見られる構成要素を指すために使用され得る。さらに、参照番号が複数の類似の構成要素（例えば、構成要素０００ａ、０００ｂ、および０００ｎ）のうちの１つを参照する文字を含む場合、参照番号は、文字なしでも類似の構成要素の１つまたはすべてを指すために使用される。
【００２７】
図１は、道路合流点の影響を使用する動的車両ナビゲーションシステム１００の１つの例示的な実装形態を示すブロック図である。図示するシステム１００は、ナビゲーションサーバ１０４と、データサーバ１０６と、モバイルコンピューティングシステム１０８と、ネットワーク１０２を介して通信可能に結合されたクライアント装置１１０を含むが、追加のまたはより少ない構成要素を使用できることに留意されたい。
【００２８】
ナビゲーションアプリケーション１１２は、システム１００の構成要素１０４、１０６、１０８、および１１０のうちの１つ以上によって動作可能である。例えば、ナビゲーションアプリケーション１１２ａのインスタンスは、モバイルコンピューティングシステム１０８上のクライアント装置１１０ａ…１１０ｎ、１１２ｃ上のナビゲーションサーバ１０４、１１２ｂ上で動作可能であり得るか、または場合によっては、ナビゲーションアプリケーション１１２は、システム１００の２つ以上の構成要素間に分散され得る。
【００２９】
ナビゲーションアプリケーション１１２は、本明細書に説明するルートを決定し工程を実行するために実行するロジックを含む。いくつかの実装形態では、ナビゲーションアプリケーション１１２は、モバイルコンピューティングシステム１０８、クライアント装置１１０、またはユーザに関連する位置データを取得する。ナビゲーションアプリケーション１１２は、ナビゲーションサーバ１０４やデータサーバ１０６（例えば、マッピングアプリケーション１１６、リアルタイム交通モジュール１１８など）から情報から取得して、本明細書で説明するようにその工程を実行することができる。例えば、位置データは地図上の地理的位置を説明する。ナビゲーションアプリケーション１１２の構成要素例は、図２を参照してさらに詳細に説明される。
【００３０】
ナビゲーションアプリケーション１１２は、道路合流点のペナルティまたは影響を道路セグメント走行時間に統合して、最小の遅延で走行時間の不確実性を少なくしてルートを検索する装置用の動的ナビゲーションシステムを提供する。例えば、この技術は、単に平均道路走行時間を適用するのではなく、道路合流点における遅延に対して適切な重みを設定することができる。例えば、システム１００は、右左折、信号機、オンランプ、または他の道路合流点の前の、車両またはモバイルコンピューティングシステム１０８の待機時間または待ち行列を考慮することができる。
【００３１】
いくつかの実装形態では、システム１００、またはその構成要素（例えば、ナビゲーションアプリケーション１１２）は、道路合流点を道路セグメントから分離した個別のナビゲーション要素として扱うことができる。背景技術で説明したものなどの既存のナビゲーションシステムと比較して、システム１００は、例えば、車両の待ち行列、交通信号、および制限された道路セグメント（例えば、高速道路のオンランプおよびオフランプ）における混雑に起因する、道路合流点に入る、または出るのに要する時間または遅延を推定し、車両ルートの推定値における遅延を統合することによって、数多くの利点を提供する。これらの要因を考慮に入れることによって、システム１００は、特に複数の交差点、信号、オンランプ、または他の道路合流点を有するルートを介したナビゲーションについての予測精度を向上させる。
【００３２】
いくつかの実装形態では、計算上の複雑性、消費される帯域幅、データ通信の量、および消費される計算リソースを低減しながら走行時間推定の精度をさらに向上させるために、本明細書に説明する技術は、ローカル道路合流点および遠隔道路合流点や区間との間を区別する。以前の車線レベルのナビゲーションシステムと比較して、この技術は、交通状況を推定および予測するための処理サイクルの消費を少なくし、それによって車両ルートのより効率的なリアルタイム更新を可能にする。例えば、本明細書に説明する技術は、定義された閾値距離または時間内のリアルタイム交通、および閾値を超える道路セグメントまたは道路合流点の過去の交通を使用することができる。したがって、リアルタイムの交通は急速に変化する可能性があるので、近くの（例えばローカルの）遅延はリアルタイムの交通を使用して計算することができる一方で、より遠い区間または合流点についての遅延は、過去のデータ、したがって場合によっては、より長い更新間隔を使用することができ、それによって帯域幅および処理の消費を低減する。例えば、過去の交通データは、リアルタイムの交通データよりも少ない頻度でキャッシュおよび更新できる。
【００３３】
ナビゲーションアプリケーション１１２のいくつかの実装形態では、混雑した地域を回避し、ネットワークが道路セグメントをよりよく利用するのを支援するために、ネットワーク内で車両を動的に再ルーティングする。例えば、システム１００は、交通状況の変化に適応するために、ルート案内中にルートおよび推定走行時間／推定到着時間を再計算することができる。これらの再計算中、上記で説明した計算上の利点はさらに増す。さらに、リアルタイム交通データの精度は過去の交通データの精度を超える可能性があるので、ルートが再計算されるとき、モバイルコンピューティングシステム１０８またはクライアント装置１１０からの閾値範囲内にある（例えば閾値内に元からなかった可能性がある）これらの道路セグメントまたは道路合流点は、リアルタイムデータを使用して再計算することができ、それによって精度を向上させる。
【００３４】
ネットワーク１０２は、有線や無線の従来型のものとすることができ、スター構成、トークンリング構成、または他の構成を含む多数の異なる構成を有することができる。例えば、ネットワーク１０２は、１つ以上のローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）（例えばインターネット）、パーソナルエリアネットワーク（ＰＡＮ）、パブリックネットワーク、プライベートネットワーク、仮想ネットワーク
、仮想プライベートネットワーク、ピアツーピアネットワーク、近距離無線ネットワーク（例えば、ブルートゥース（登録商標）、ＮＦＣなど）、車両ネットワーク、および／または複数の装置が通信することができる他の相互接続されたデータパスを含む。
【００３５】
ネットワーク１０２はまた、様々な異なる通信プロトコルでデータを送信するために電気通信ネットワークの一部に結合されるかまたはその一部を含むこともできる。プロトコルの例は、それだけに限定されないが、伝送制御プロトコル／インターネットプロトコル（ＴＣＰ／ＩＰ）、ユーザデータグラムプロトコル（ＵＤＰ）、伝送制御プロトコル（ＴＣＰ）、ハイパーテキスト転送プロトコル（ＨＴＴＰ）、セキュアハイパーテキスト転送プロトコル（ＨＴＴＰＳ）、ＨＴＴＰを介する（ＤＡＳＨ）動的適合ストリーミングおよびリアルタイムストリーミングプロトコル（ＲＴＳＰ）、リアルタイムトランスポートプロトコル（ＲＴＰ）およびリアルタイムトランスポート制御プロトコル（ＲＴＣＰ）、ボイスオーバーインターネットプロトコル（ＶＯＩＰ）、ファイル転送プロトコル（ＦＴＰ）、Ｗｅｂソケット（ＷＳ）、無線アクセスプロトコル（ＷＡＰ）、様々なメッセージングプロトコル（ＳＭＳ、ＭＭＳ、ＸＭＳ、ＩＭＡＰ、ＳＭＴＰ、ＰＯＰ、ＷｅｂＤＡＶなど）、または他の適切なプロトコルを含む。いくつかの実施形態では、ネットワーク１０２は、ＤＳＲＣ（専用短距離通信）、ＷＡＶＥ、８０２．１１ｐ、３Ｇ、４Ｇ、５Ｇ＋ネットワーク、ＷｉＦｉ（登録商標）、衛星ネットワーク、車車間（Ｖ２Ｖ）ネットワーク、車両からインフラストラクチャへ／インフラストラクチャから車両への（Ｖ２Ｉ／Ｉ２Ｖ）ネットワークまたは他の任意の無線ネットワークなどの接続を使用する無線ネットワークである。図１は、ナビゲーションサーバ１０４、クライアント装置１１０、モバイルコンピューティングシステム１０８、およびデータサーバ１０６に結合された１つのネットワーク１０２を示しているが、実際には１つ以上のネットワーク１０２をこれらおよび他のエンティティに接続することができる。
【００３６】
ナビゲーションサーバ１０４は、プロセッサ、メモリ、およびネットワーク通信機能を含むハードウェアまたは仮想サーバとすることができる。いくつかの実装形態では、ナビゲーションサーバ１０４は、データサーバ１０６、クライアント装置１１０ａ…１１０ｎ、およびモバイルコンピューティングシステム１０８のうちの１つ以上との間でデータを送受信する。ナビゲーションサーバ１０４はまた、ユーザのための登録データ、ルート（例えば、新しいルートおよび過去のルート）、交差点、地図などを含むことができる記憶装置１３２を含む。
【００３７】
いくつかの実装形態では、クライアント装置１１０ａ…１１０ｎは、ナビゲーションサーバ１０４、データサーバ１０６、またはモバイルコンピューティングシステム１０８のうちの１つ以上との間でデータを送受信する。クライアント装置１１０は、メモリおよびプロセッサを含む計算装置、例えばラップトップコンピュータ、デスクトップコンピュータ、タブレットコンピュータ、携帯電話、携帯情報端末、スマートウォッチ、または他の計算装置である、コンピューティング装置である。いくつかの実装形態では、クライアント装置１１０ａは、オンラインサービスにアクセスするためのブラウザ（例えば、ナビゲーションサーバ１０４）、およびユーザの登録データ、ルート、交差点、地図、位置情報などを記憶するための記憶装置１４４を含む。いくつかの実装形態では、図２を参照して説明したように、クライアント装置１１０は、全地球測位システム（ＧＰＳ）受信機、Ｗｉ−Ｆｉ無線装置、セルラー無線装置、またはその位置を決定するための他の装置などの位置特定機能を含む。
【００３８】
いくつかの例では、ナビゲーションアプリケーション１１２は、部分的にクライアント装置１１０に記憶されるシンクライアントアプリケーションとして、また部分的にはナビゲーションサーバ１０４に記憶され得る構成要素として作用する。例えば、ナビゲーションサーバ１０４は、ユーザデータを記憶装置１３２に記憶し、ユーザに合わせたルートを
推定することができる。
【００３９】
いくつかの実装形態では、モバイルコンピューティングシステム１０８は、ナビゲーションサーバ１０４、データサーバ１０６、およびクライアント装置１１０のうちの１つ以上との間でデータを送受信する。モバイルコンピューティングシステム１０８は、メモリおよびプロセッサを含む任意のコンピューティング装置である。一実装形態では、モバイルコンピューティングシステム１０８は、非一時的コンピュータ電子機器（例えば、プロセッサ、メモリ、または非一時的コンピュータ電子機器の任意の組み合わせ）を有する任意の車両または任意の他のモバイルシステムを含む。例としては、自動車、飛行機、ボート、トラック、バイオニックインプラント、ロボット、個人輸送装置、商業輸送装置などが挙げられる。いくつかの実装形態では、モバイルコンピューティングシステム１０８は、ユーザ、ルート、交差点、地図などの登録データを記憶するための記憶装置１４２を含む。いくつかの実装形態では、図２を参照して説明したように、モバイルコンピューティングシステム１０８は、ＧＰＳ受信機、Ｗｉ−Ｆｉ無線、セルラー無線、またはその位置を判断するための他の装置などの位置機能を含む。
【００４０】
データサーバ１０６は、例えば、マッピングアプリケーション１１６、リアルタイム交通モジュール１１８、地図記憶装置１２７、過去の道路交通データ１３６、道路形状データ１３８、および交通信号データ１４０を含む。図示する実施形態では、データサーバ１０６はネットワーク１０２に接続されており、このネットワークを介してデータサーバはシステム１００の他の構成要素と通信することができる。いくつかの実装形態では、マッピングアプリケーション１１６は、ナビゲーションアプリケーション１１２から地図の要求を受信する。例えば、ナビゲーションアプリケーション１１２は、複数の交差点間の１つ以上の高速道路または高速道路の一部を説明する地図を要求する。いくつかの実装形態では、マッピングアプリケーション１１６は、地図記憶装置１２７から地図を説明する地図データを呼び出し、その地図データをナビゲーションアプリケーション１１２に送信する。いくつかの他の実装形態では、マッピングアプリケーション１１６は、ナビゲーションに関する追加のまたは異なる情報を生成する。例えば、ナビゲーションに関する情報は、リアルタイムの交通情報、それだけに限定されないが、建設情報などを含む。
【００４１】
リアルタイム交通モジュール１１８は、リアルタイム交通データを集約し、場合によっては、リアルタイム交通データについての要求を処理するためのソフトウェアおよびルーチンを含む。例えば、リアルタイム交通モジュール１１８は、モバイルコンピューティングシステム１０８、クライアント装置１１０、交通カメラ、交通センサ、または他のリアルタイムデータ収集装置からデータを収集することができ、また、例えば、ナビゲーションアプリケーション１１２による要求に応答して、リアルタイムデータをナビゲーションアプリケーション１１２に提供することができる。リアルタイムデータは、待ち時間、処理、転送時間などによる一定の遅延を含み得ることに留意されたい。
【００４２】
いくつかの実装形態では、地図記憶装置１３４は、道路の位置（例えばＧＰＳ）、相互接続、形状などの地図データを含む。地図データは、道路セグメント、道路合流点、車線、交通信号の位置などを含む。
【００４３】
いくつかの実装形態では、過去の道路交通データ１３６は、時間に依存し、経時的に平均化される交通データ、旅行者、または車両のデータを含む。過去の道路交通データ１３６は、モバイルコンピューティングシステム１０８、クライアント装置１１０、交通カメラ、または他の交通監視装置からのデータを集約することによって収集することができる。
【００４４】
いくつかの実装形態では、道路形状データ１３８は、例えば、道路の形状、幅、長さな
どを表すデータを含む。例えば、道路形状データ１３８は、道路または車線が合流するか、分岐するか、交差点で合流するか、またはカーブであるかどうかおよびその様子を含む。場合によっては、道路形状データ１３８は、道路セグメントと道路セグメントに接続された道路合流点との間のマッピング、道路合流点への道路セグメントの車線のマッピング、または他の形状データなどの、道路セグメントと道路合流点との間のリンクの識別を含む。
【００４５】
いくつかの実装形態では、交通信号データ１４０は、交通信号の属性、例えば交差点の位置、信号に関連付けられた車線、サイズなど、ランプメータ（優先道路への流入タイミングを指示するための信号機）、および他の交通信号を含む。いくつかの事例では、交通信号データ１４０は、交通信号のタイミング、周期、またはトリガ情報などのタイミングデータも含むこともできる。
【００４６】
次に図２を参照すると、ナビゲーションアプリケーション１１２の一例がより詳細に示されている。図２は、いくつかの実施形態によるナビゲーションアプリケーション１１２、プロセッサ２３２、メモリ２３４、入出力装置２３６、記憶装置２３８、および通信ユニット２４０を含むコンピューティング装置２００のブロック図である。コンピューティング装置２００の構成要素は、バス２２０によって通信可能に結合されている。コンピューティング装置２００は、実装形態に応じて、ナビゲーションサーバ１０４、クライアント装置１１０、またはモバイルコンピューティングシステム１０８とすることができる。
【００４７】
プロセッサ２３２は、計算を実行し、場合によっては電子表示信号を表示装置に提供するために、算術論理装置、マイクロプロセッサ、汎用コントローラ、または他の何らかのプロセッサアレイを含む。プロセッサ２３２は、他の構成要素と通信するためにバス２２０に結合されている。プロセッサ２３２はデータ信号を処理し、複合命令セットコンピュータ（ＣＩＳＣ）アーキテクチャ、縮小命令セットコンピュータ（ＲＩＳＣ）アーキテクチャ、または命令セットの組み合わせを実装するアーキテクチャを含む様々なコンピューティングアーキテクチャを含む。図２は単一のプロセッサ２３２を示しているが、複数のプロセッサ２３２が含まれていてもよい。他のプロセッサ、オペレーティングシステム、センサ、ディスプレイおよび物理的構成も可能である。
【００４８】
メモリ２３４は、プロセッサ２３２によって実行することができる命令やデータを記憶する。メモリ２３４は、他の構成要素と通信するためにバス２２０に結合することができる。命令やデータは、本明細書に説明する技術を実行するためのコードを含む。メモリ２３４は、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）装置、スタティックランダムアクセスメモリ（ＳＲＡＭ）装置、フラッシュメモリ、または他の何らかのメモリ装置とすることができる。いくつかの実装形態では、メモリ２３４はまた、不揮発性メモリまたは類似の永久記憶装置と、ハードディスクドライブ、フロッピーディスクドライブ、ＣＤ−ＲＯＭ装置、ＤＶＤ−ＲＯＭ装置、ＤＶＤ−ＲＡＭ装置，ＤＶＤ−ＲＷ装置、フラッシュメモリ装置、またはより恒久的に情報を記憶するための他の何らかの大容量記憶装置を含む媒体を含む。
【００４９】
通信ユニット２４０は、ナビゲーションアプリケーション１１２との間でデータを送受信する。通信ユニット２４０はバス２２０に結合することができる。いくつかの実装形態では、通信ユニット２４０は、ＩＥＥＥ８０２．１１、ＩＥＥＥ８０２．１６、ＢＬＵＥＴＯＯＴＨ（登録商標）または別の適切な無線通信法を含む１つ以上の無線通信方法を使用してコンピューティング装置２００または他の通信チャネル内の他の構成要素とデータを交換するための無線トランシーバを含む。
【００５０】
いくつかの実装形態では、通信ユニット２４０は、ショートメッセージングサービス（
ＳＭＳ）、マルチメディアメッセージングサービス（ＭＭＳ）、ハイパーテキスト転送プロトコル（ＨＴＴＰ）、直接データ接続、ＷＡＰ、電子メール、または別の適切な種類の電子通信を含む、セルラー通信ネットワークを介してデータを送受信するためのセルラー通信トランシーバを含む。いくつかの実装形態では、通信ユニット２４０は、有線ポートおよび無線トランシーバを含む。通信ユニット２４０はまた、ＴＣＰ／ＩＰ、ＨＴＴＰ、ＨＴＴＰＳおよびＳＭＴＰなどを含む標準ネットワークプロトコルを使用してファイルや媒体オブジェクトを配信するためにネットワーク１０２への他の従来の接続を提供する。
【００５１】
記憶装置２３８は、本明細書に説明する機能を提供するためのデータを記憶する非一時的メモリとすることができる。記憶装置２３８は、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）装置、スタティックランダムアクセスメモリ（ＳＲＡＭ）装置、フラッシュメモリ、または他の何らかのメモリ装置とすることができる。いくつかの実装形態では、記憶装置２３８はまた、不揮発性メモリまたは類似の永久記憶装置と、ハードディスクドライブ、フロッピーディスクドライブ、ＣＤ−ＲＯＭ装置、ＤＶＤ−ＲＯＭ装置、ＤＶＤ−ＲＡＭ装置、ＤＶＤ−ＲＷ装置、フラッシュメモリ装置、またはより恒久的に情報を記憶するための他の何らかの大容量記憶装置を含む媒体とを含む。
【００５２】
図示する実装形態では、記憶装置２３８は、バス２２０に通信可能に結合されている。一実装形態では、記憶装置２３８は、ルートデータ、地図データ、または例えば符号１３２、１４２、１４４を参照して説明する他のデータを含む。例えば、記憶装置２３８は、本明細書に説明する機能を提供するための他のデータを記憶する。
【００５３】
入出力装置２３６は、入力を受信し出力を提供するためのハードウェアである。例えば、入出力装置２３６は、音（例えばルートに対応する音声命令）を生成するためのスピーカ、音（例えばユーザからのフィードバック）を記録するためのマイクロホン、および加速度計のような他のセンサまたはフィードバック装置を含む。任意選択により、入出力装置２３６は、音声処理を容易にするために、１つ以上のアナログデジタル変換器またはデジタルアナログ変換器、１つ以上のデジタル信号プロセッサを含む。これらの入出力装置２３６は、プロセッサ２３２およびメモリ２３４と通信するためにバス２２０に結合されている。任意選択により、マイクロコントローラを入出力装置２３６の一部として追加して、電力システムの制御を容易にすると共に、より低速の重要度の低いタスクからメインプロセッサ２３２をオフロードすることができる。
【００５４】
図示していないが、コンピューティング装置２００は、その位置を決定するための１つ以上の装置を含む。例えば、コンピューティング装置２００は、ＧＰＳ受信機、Ｗｉ−Ｆｉ無線装置、セルラー無線装置、またはコンピューティング装置２００の現在位置を決定することができるかまたは決定するように構成された他の装置を含む。
【００５５】
図２に示す実施形態では、ナビゲーションアプリケーション１１２は、ルートエンジン２０２、道路セグメントエンジン２０４、道路合流点エンジン２０６、ローカル−遠隔閾値エンジン２０８、ユーザインターフェースモジュール２１０を含む。いくつかの実装形態では、ナビゲーションアプリケーション１１２の構成要素は、バス２２０を介して通信可能に結合される。いくつかの実施形態では、ナビゲーションアプリケーション１１２、ルートエンジン２０２、道路セグメントエンジン２０４、道路合流点エンジン２０６、ローカル−遠隔閾値エンジン２０８、ユーザインターフェースモジュール２１０は、１つ以上のプロセッサやコンピューティング装置によって実行可能なソフトウェアを使用して、それだけ限定されないが、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）などのハードウェアを使用して、またはハードウェアおよびソフトウェアの組み合わせなどによって実装される。
【００５６】
ルートエンジン２０２は、データサーバ１０６から地図データおよびルートデータを要求するのに実行可能なソフトウェアやハードウェアロジックを含む。一実装形態では、ルートエンジン２０２は、通過時間などを推定し、ルートを生成し、データサーバ１０６から地図データおよびルートデータを要求するなど、後述する機能を提供するためにプロセッサ２３２によって実行可能な命令のセットとすることができる。
【００５７】
いくつかの実装形態では、ルートエンジン２０２は、地図についての要求を生成し、その地図についての要求をデータサーバ１０６に送信する。例えば、ルートエンジン２０２は、カリフォルニアのサンノゼ地域をカバーする地図についての要求を生成する。地図データは、例えば、サンノゼにおける複数の高速道路および交差点、ユーザが走行した過去のルート、地図を記述する地理的位置（例えばＧＰＳ）データ、道路セグメントおよび道路合流点、ならびにデータサーバ１０６からの他のデータを含む。
【００５８】
いくつかの実装形態では、ルートエンジン２０２は、地図およびルートデータを記述する地図データをナビゲーションアプリケーション１１２の他の構成要素のうちの１つ以上に送信する。いくつかの実装形態では、ルートエンジン２０２は、地図データ、ルート、またはルートエンジン２０２によって受信または処理された他のデータを記憶装置２３８に記憶する。
【００５９】
道路セグメントエンジン２０４は、例えば以下でさらに詳細に説明するように、道路セグメントを識別し、それらの走行時間を計算するのに実行可能なソフトウェアやハードウェアロジックを含む。いくつかの実装形態では、道路セグメントエンジン２０４は、例えば、ローカル−遠隔閾値エンジン２０８によって決定された閾値に基づいて、道路セグメントをローカルと遠隔とに区別することができる。
【００６０】
道路合流点エンジン２０６は、例えば以下でさらに詳細に説明するように、道路合流点を識別し、それらの走行時間を計算するのに実行可能なソフトウェアやハードウェアロジックを含む。いくつかの実装形態では、道路セグメントエンジン２０４は、例えば、ローカル−遠隔閾値エンジン２０８によって決定された閾値に基づいて、道路合流点をローカルと遠隔とに区別することができる。
【００６１】
道路合流点エンジン２０６は、道路合流点を通過する時間、または例えば、ルート内の道路合流点でルートに追加された時間に対する交通の影響を決定することができる。いくつかの実装形態では、道路合流点エンジン２０６は左折、通過、および右折の移動における遅延を区別し、それによってそれらを車両ルート走行時間の推定において別々に考慮し、場合によってはそのルートからの移動にかかる特定の時間を解消することができる。
【００６２】
ローカル−遠隔閾値エンジン２０８は、ローカルと遠隔の道路セグメントおよび道路合流点とを区別するための閾値を決定するのに実行可能なソフトウェアやハードウェアロジックを含む。例えば、道路セグメントエンジン２０４、道路合流点エンジン２０６、またはナビゲーションアプリケーション１１２の別の構成要素によって、本明細書に説明する技術の目的で、特定の道路セグメントまたは道路合流点を、ローカルまたは遠隔として分類するかどうかを決定するために閾値が使用される。例えば、閾値より近い区間または道路合流点は「ローカル」として分類され、閾値よりも遠い区間または道路合流点は、「遠隔」として分類されてもよい。閾値に正確に当てはまる区間または道路合流点は、設計上の選択としてローカルまたは遠隔のいずれかとして定義することができ、すなわち閾値は厳密な値を含むかまたは含まないことがあることに留意されたい。
本明細書では、ローカルとは、ユーザの現在位置から所定の範囲内に存在することを意味し、遠隔とは、ユーザの現在位置から所定の範囲外に存在することを意味する。
【００６３】
閾値は、（モバイルコンピューティングシステム１０８、クライアント装置１１０、またはこれらの装置のうちの１つと対話して位置を手動で入力するユーザの）位置からの半径として定義することができ、またはその位置からの道路に沿った距離として定義することができる。追加的または代替的に、ローカル−遠隔閾値エンジン２０８は、その位置からの車両の推定走行時間などの追加の要因に基づいて動的に定義された閾値を定義することができる。例えば、ルートが高速道路などによる高速走行を含む場合、閾値はその位置からのより遠い距離として定義され得る。
【００６４】
いくつかの実装形態では、例えば、道路セグメントにおける走行時間／遅延を予測する様々な方法の精度は、道路合流点についてのものより経時的に異なって変化し得るため、道路セグメントについて第１の閾値を定義し、道路合流点について別個の閾値を定義できることに留意されたい。さらに、特定の種類の道路セグメントや道路合流点について、特定の閾値を定義することができることに留意されたい。例えば、「高速道路オンランプでの遅延が交差点での遅延よりも変動性が小さい」という決定に応答して、閾値を高速道路オンランプと小さい交差点とでは異なるように定義または重み付けすることができる。
【００６５】
いくつかの実装形態では、閾値はシステム管理者によって提供された手動入力値であり得るが、いくつかの実装形態では、閾値は機械較正値であってもよい。ローカル−遠隔閾値エンジン２０８は、コンピュータ学習アルゴリズムを使用して、ローカル道路合流点走行時間、遠隔道路合流点走行時間、および測定走行時間の間の偏差に基づいて、固定または動的閾値を決定または較正することができる。いくつかの実装形態では、閾値は、実世界の観察結果と、本明細書で説明するように影響／遅延を決定する方法の予測との間の比較に基づいて、自動的に調整または重み付けされる。
例えば、算出したローカル道路合流点走行時間の合計と、ローカル道路合流点の通過に実際に要した時間の合計と、算出した遠隔道路合流点走行時間の合計と、遠隔道路合流点の通過に実際に要した時間の合計を取得したうえで、予測値と実測値の偏差に基づいて、閾値を補正してもよい。例えば、算出したローカル道路合流点走行時間の合計と、ローカル道路合流点の通過に実際に要した時間の合計の差が最も小さくなり、かつ、算出した遠隔道路合流点走行時間の合計と、遠隔道路合流点の通過に実際に要した時間の合計の差が最も小さくなるように閾値を動的に再計算してもよい。
いくつかの実装形態では、ローカル−遠隔閾値エンジン２０８は、道路合流点のリアルタイム交通、遅延、待ち行列などにおける偏差または変動性を追跡し、その変動性に基づいて閾値を調整することができる。例えば、高速道路オンランプの交通に起因する遅延が、「１０分間にわたって比較的一定であるが、１０分よりも長い期間中に大きく変動し得る」と判定された場合、ローカル−遠隔閾値エンジン２０８は、閾値を１０分、または１０分以内に走行すると予測される距離に設定することができる。
【００６６】
ユーザインターフェースモジュール２１０は、ユーザに合わせたルートの有用な情報を表示するためのユーザインターフェースを生成するのに実行可能なソフトウェアやハードウェアロジックを含む。一実装形態では、ユーザインターフェースモジュール２１０は、ユーザに合わせたルートの有用な情報を表示するためのユーザインターフェースを生成するために以下に説明する機能を提供するためにプロセッサ２３２によって実行可能な命令のセットとすることができる。別の実装形態では、ユーザインターフェースモジュール２１０は、コンピューティング装置２００のメモリ２３４に記憶することができ、プロセッサ２３２によってアクセス可能で実行可能とすることができる。いずれの実装形態においても、ユーザインターフェースモジュール２１０は、プロセッサ２３２およびコンピューティング装置２００の他の構成要素との協調および通信に適合することができる。
【００６７】
いくつかの実装形態では、ユーザインターフェースモジュール２１０は、ルートエンジン２０２から命令を受信し、計算されたルート、走行時間、到着予定時刻などに関する情
報を表示するためのユーザインターフェースを生成する。情報には、ルート沿いのアトラクションおよび文化的な設備を含むこともできる。別の例では、情報はまた、ルートに関連する交通遅延情報および道路閉鎖情報を含む。いくつかの実装形態では、ユーザインターフェースモジュール２１０は、有用な情報を含むユーザインターフェースデータをクライアント装置１１０またはモバイルコンピューティングシステム１０８に送信し、クライアント装置１１０またはモバイルコンピューティングシステム１０８に、有用な情報を含むユーザインターフェースをユーザに対して表示させる。
【００６８】
図３は、道路合流点の影響を使用してナビゲーションルートを生成するための方法３００の実施の流れ図である。例えば、システム１００は、過去の交通状況およびリアルタイムの交通状況を使用して、道路ネットワーク内の道路セグメントおよび道路合流点の走行時間を計算することができる。
【００６９】
ステップ３０２で、ナビゲーションアプリケーション１１２は、クライアント装置１１０（クライアント装置１１０は図３〜４Ｃを参照して参照されるが、モバイルコンピューティングシステム１０８もさらに、または代替的に使用され得ることに留意されたい）の位置および目的地を識別する。例えば、ナビゲーションアプリケーション１１２は、ＧＰＳ、セルラーネットワーク三角測量などに基づいてクライアント装置１１０の位置を受信することができる。同様に、ナビゲーションアプリケーション１１２は、実装形態に応じて、目的地をユーザからの入力として受信することができる。
【００７０】
ステップ３０４で、ナビゲーションアプリケーション１１２は、クライアント装置の第１の位置、目的地、および地図データに基づいて、複数の道路セグメントおよび複数の道路合流点を決定する。例えば、ナビゲーションアプリケーション１１２は、ナビゲーションネットワーク内の道路セグメントおよび道路合流点を決定する。これは、例えば、実装形態に応じて、クライアント装置１１０の位置の近く（例えば、定義された距離内、同じ都市内など）の道路、地図データに基づいてクライアント装置１１０の位置と目的地との間で計算されたルート候補に沿った道路を含む。例えば、いくつかの実装形態では、ナビゲーションアプリケーション１１２は、計算が行われるデータの全セットを低減するために、クライアント装置１１０の位置と目的地との間のルート候補のセットを計算することができる。いくつかの例では、複数の道路セグメントおよび複数の道路合流点は、ローカル道路セグメント、ローカル道路合流点、遠隔道路セグメント、遠隔道路合流点を含む。
【００７１】
ステップ３０６で、ナビゲーションアプリケーション１１２は、複数の道路セグメントのうちの各道路セグメントについて、道路セグメント走行時間を計算する。例えば、道路セグメント走行時間は、リアルタイム交通モジュール１１８、過去の道路交通データ１３６、記憶装置、またはシステム１００の他の構成要素から受信された、リアルタイム交通データ、特定の道路セグメント上の過去の走行時間、または他のデータに基づいて決定される。いくつかの実装形態では、本明細書の他の場所で説明するように、例えばリアルタイムおよび過去の交通データまたは走行時間データに基づいて、ローカルおよび遠隔の道路セグメントを区別することができ、それらの走行時間を決定することができる。例えば、道路セグメント走行時間の決定は、図４Ｃの実施例に説明するように実行することができる。
【００７２】
ステップ３０８で、ナビゲーションアプリケーション１１２は、ローカル道路合流点についてのローカル道路合流点走行時間に対する交通のローカル影響、および遠隔道路合流点についての遠隔道路合流点走行時間に対する交通の遠隔影響を計算する。いくつかの例では、データサーバ１０６などのシステムは、ローカルおよび遠隔の道路合流点について計算されたリアルタイムまたは過去の走行時間データ（例えば、遅延、影響、平均走行時間など）を有し、ナビゲーションアプリケーション１１２は、ローカル／遠隔を問わず、
道路合流点に適したデータセットを取得する。例えば、ナビゲーションアプリケーション１１２（例えば、道路合流点エンジン２０６による）は、上記でさらに詳細に論じたように、閾値に基づいてローカルと遠隔の道路合流点を区別することができる。遠隔道路合流点についての遠隔道路合流点走行時間に対する交通の遠隔影響を計算するための例示的な工程は、例えば、図４Ａを参照してさらに詳細に説明される。例えば、図４Ｂを参照して、ローカル道路合流点についてのローカル道路合流点走行時間に対する交通のローカル影響を計算するための例示的な工程が、さらに詳細に説明される。
【００７３】
ステップ３１０で、ナビゲーションアプリケーション１１２は、道路セグメント、ローカル道路合流点、および遠隔道路合流点の地図データ、道路セグメント走行時間、ローカル道路合流点走行時間、および遠隔道路合流点走行時間のうちの１つ以上を使用して、クライアント装置の位置と目的地との間のルートのセットを決定する。例えば、ナビゲーションアプリケーション１１２は、クライアント装置１１０の位置および目的地を接続するために、道路セグメントおよび道路合流点の中から選択することができ、例えば、最短距離／最短総走行時間を有するルートを選択することができる。
【００７４】
ステップ３１２で、ナビゲーションアプリケーション１１２は、例えば、道路セグメント走行時間、ローカル道路合流点走行時間、および遠隔道路合流点走行時間に基づいて、計算されたルートのセットのそれぞれの総走行時間を計算する。例えば、本ステップは、所与のルートにおける道路セグメントおよび道路合流点の各々を決定すること、および道路セグメントおよび道路合流点の各々についての走行時間を一緒に加算することを含む。
【００７５】
いくつかの実装形態では、ナビゲーションアプリケーション１１２は、総走行時間を使用してルートのセットから選択された特定のルートについて、ターンバイターン指示などのルート案内データを決定することができる。いくつかの実装形態では、ナビゲーションアプリケーション１１２は、ルート候補およびそれらの総走行時間または到着予定時刻を示すためのインターフェースをユーザに提供することができる。ナビゲーションアプリケーション１１２は、特定のルートを選択しているユーザからの入力を受信することができる。
【００７６】
いくつかの実装形態では、ナビゲーションアプリケーション１１２は、総走行時間および特定のルート機能について記憶されたユーザの好みに基づいて、ルートのセットから特定のルートを選択することができる。例えば、ナビゲーションアプリケーション１１２は、総走行時間やユーザの好みに基づいて、特定のルートを自動的に選択するか、またはルートのセットをランク付けすることができる。例えば、ナビゲーションアプリケーション１１２は、ユーザが最短の総走行時間でルートをとる（例えば、ユーザによって明示的に提供されるか、またはナビゲーションアプリケーション１１２によって以前のユーザインタラクションから学習された）好みを有すると決定することができ、この状況で、ナビゲーションアプリケーション１１２は、最短総走行時間のルートを自動的に選択することができる。いくつかの実装形態では、ユーザの好みは、例えば有料道路を回避する好みなどの他の条件を示すことができ、その状況では、ナビゲーションアプリケーション１１２は、有料道路を含むルートを自動的に除外することができる（または有料道路を使用してルートを計算しない）。
【００７７】
いくつかの実装形態では、ナビゲーションアプリケーション１１２は、ルート案内データに基づいて、選択された特定のルートについてのルート案内をクライアント装置１１０に提供することができる。いくつかの実装形態では、ルート案内は、走行中にクライアント装置１１０にリアルタイムで提供されるターンバイターン指示を含む。
【００７８】
いくつかの実装形態では、ナビゲーションアプリケーション１１２は、ルート案内中に
ルートや走行時間を再計算することができる。例えば、ルート案内データに基づいて特定のルートについてのルート案内をクライアント装置に提供することは、クライアント装置による特定のルートの通過中のクライアント装置の第２の位置に基づいて特定のルートを周期的に修正することを含む。例えば、運転者またはシステムの指定周期に基づいて、ナビゲーションアプリケーション１１２は、現在のクライアント装置１１０を決定し、走行時間を再計算し、そして通過中のルートを再計算することができる。いくつかの実装形態では、道路セグメントまたは道路合流点がローカルまたは遠隔として分類される閾値範囲は、更新されたクライアント装置１１０の位置に基づいて再計算され得る。
【００７９】
図４Ａは、遠隔道路合流点の影響を計算するための方法４００の実施の流れ図である。図４Ａを参照して説明された工程は、遠隔道路合流点走行時間に対する交通の遠隔（例えば、閾値によって定義され上記で論じたような）影響を計算することができる。遠隔の影響は、履歴情報によって取り込まれた繰り返し発生する時間依存の遅延を含む。
【００８０】
ステップ４０２で、道路合流点エンジン２０６は、道路形状情報（すべての関連する道路合流点についてか、または遠隔だけのものかに関わらず）を決定することができる。道路合流点エンジン２０６は、地図記憶装置１３４からの道路形状データやデータサーバ１０６上の道路形状データ１３８を取得することができる。例えば、道路形状データは、実装形態に応じて、位置、接続道路セグメント、サイズ、形状、交通信号情報、または道路合流点に関する他のデータを含む。場合によっては、道路形状データは、基本的な道路セグメント、合流区間および分岐区間、ならびに交差点に関連する道路合流点を含むことができ、これらを使用して、道路合流点エンジン２０６は、一方の道路セグメントから他の道路セグメントへの可能な道路合流点とともに、いくつかの実装形態では、道路合流点に関連する車線を識別することができる。
【００８１】
ステップ４０４で、道路合流点エンジン２０６は、１つ以上の遠隔道路合流点における過去の時間遅延を決定することができる。例えば、道路合流点エンジン２０６は、データサーバ１０６上の過去の道路交通データ１３６から、ルート内または潜在的ルートのセット内の道路合流点（例えば、「遠隔」または閾値を超える道路合流点）における過去の遅延を取得することができる。上記で論じたように、交通の遅延または影響は、車両が次の道路セグメントに進む前に道路合流点で待機する時間を含む。いくつかの例では、交通の遅延または影響は、交通信号における待機時間、車両待ち行列、事故、または道路合流点を通る車両の走行時間に影響を及ぼし得る他の要因のうちの１つ以上を考慮に入れることができる。
【００８２】
ステップ４０６で、道路合流点エンジン２０６は、時間依存の道路合流点遅延を推定することができる。例えば、道路合流点エンジン２０６は、過去の時間遅延、およびいくつかの実装形態では、道路合流点の他の属性に基づいて、交通の遠隔影響を計算することができる。例えば、道路合流点エンジン２０６は、交差点における過去の車両の過去の待機時間（例えば、平均または他の統計的尺度として採用される）に基づいて、所与の道路合流点が第１の道路セグメントから第２の道路セグメントまで現在の遅延を有すると決定することができる。いくつかの実装形態では、このデータは、データ要求時に計算され得るか、または迅速なアクセスのために、事前に計算され、クライアント装置１１０にキャッシュとして、またはデータサーバ１０６上の過去の道路交通データ１３６内に記憶され得る。
【００８３】
ステップ４０８で、道路合流点エンジン２０６は、例えばクライアント装置１１０からクライアント装置１１０の位置を受信し、ステップ４１０で、道路合流点エンジン２０６は、クライアント装置１１０の位置、またはクライアント装置１１０の位置と目的地との間のルート候補に対する道路合流点についての時間依存の道路合流点遅延または交通影響
を推定する。いくつかの実装形態では、道路合流点エンジン２０６は、最初にクライアント装置１１０の現在位置を識別し、（例えば、４０２〜４０６で情報を取得する前に）道路合流点をローカルおよび遠距離道路合流点として区別することができることに留意されたい。
【００８４】
図４Ｂは、ローカル道路合流点の影響を計算するための方法４００の実施の流れ図である。例えば、図４Ｂは、ローカル道路合流点走行時間に対する交通のローカル影響に関する工程を示す。ローカル影響は、道路合流点における短期間（例えば、上記で論じた閾値時間または距離内）の予測遅延として定義することができる。いくつかの実装形態では、図４Ｂを参照して説明する工程の一部または全部は、図４Ａを参照して説明したものと並行してまたはそれに続いて実行することができる。
【００８５】
ステップ４１２〜４１６で、道路合流点エンジン２０６は、ローカル道路合流点の属性を含むローカル道路合流点のローカル道路合流点情報を受信する。
【００８６】
ステップ４１２で、道路合流点エンジン２０６は、例えばデータサーバ１０６上の交通信号データ１４０記憶装置から交通信号データを受信する。例えば、上述のように、交通信号データは、交差点信号、ランプメータなどに関するデータを含む。
【００８７】
ステップ４１４で、道路合流点エンジン２０６は、例えば、上記で４０２を参照して説明したように、道路形状データを取得する。いくつかの場合、このステップで、道路合流点エンジン２０６は、すべての道路合流点についてローカルとして分類された道路合流点のみについて道路形状データを取得することができ、またはローカル道路合流点について取り出された道路形状データを、４０２における遠隔道路合流点についてのデータと一緒にまとめて取得することができる。
【００８８】
ステップ４１６で、道路合流点エンジン２０６は、例えば、リアルタイム交通モジュール１１８からのリアルタイム遅延（または走行時間）データの受信に基づいて、ローカル道路合流点でのリアルタイム遅延を決定する。いくつかの実装形態では、帯域幅を維持し、システム性能を向上させるために、道路合流点エンジン２０６は、ローカル道路合流点についてのリアルタイム情報を受信または取得することができるが、遠隔道路合流点については取得することはできない。
【００８９】
ステップ４１８で、道路合流点エンジン２０６は、短期間（例えば、閾値内）における道路合流点遅延を予測することができる。例えば、車両待ち行列の長さ、次の２つか３つの下流の交差点の交通信号、および道路形状情報などの、道路合流点において観察されるリアルタイム遅延を適用して、道路合流点における車両待ち行列および遅延について短期間の予測を行うことができ、したがって、道路合流点エンジン２０６は、道路合流点のリアルタイム遅延および属性に基づいて、交通のローカル影響を計算することができる。
【００９０】
ステップ４２０で、道路合流点エンジン２０６は、クライアント装置の位置を受信する。これは、ステップ４０８で受信されたのと同じデータであってもよいし、またはステップ４２０で再び取得してもよい。
ステップ４２２で、道路合流点エンジン２０６は、例えば、予測された短期間の遅延およびクライアント装置１１０の位置に基づいて、ローカル道路合流点についてのローカル道路合流点の影響を推定することができる。
【００９１】
図４Ｃは、道路セグメントの影響を計算し、ルートを生成するための方法４００の実施の流れ図である。例えば、ナビゲーションアプリケーション１１２は、道路セグメント走行時間および道路合流点走行時間を用いてルートを計算することができる。いくつかの実
装形態では、道路セグメントエンジン２０４は、図４Ｃを参照して説明した工程のいくつかまたはすべてを使用して、複数の道路セグメントについての道路セグメント走行時間を決定することができる。
【００９２】
ステップ４２４で、道路セグメントエンジン２０４は、過去における道路セグメント走行時間を取得する。例えば、道路セグメントエンジン２０４は、データサーバ１０６上の過去の道路交通データ１３６記憶装置からデータを取得する。過去の道路セグメント走行時間は、道路セグメントを通って走行する車両の過去の走行時間を示す。
【００９３】
ステップ４２６で、道路セグメントエンジン２０４は、リアルタイムの道路セグメント走行時間を受信する。例えば、道路セグメントエンジン２０４は、データサーバ１０６上のリアルタイム交通モジュール１１８と通信してリアルタイムデータを受信する。過去の道路セグメント走行時間は、上記で説明したように、例えば、交通監視、制限速度、道路セグメント形状などに基づいて、道路セグメントを走行する車両の過去の走行時間を示す。
【００９４】
いくつかの実装形態では、道路セグメントエンジン２０４は、閾値に基づいて１つ以上のローカル道路セグメントや、１つ以上の遠隔道路セグメントを識別することができ、各区間についての走行時間を決定することができる。例えば、ローカル道路セグメントは閾値距離内にあり、遠隔道路セグメントは、閾値距離を超える。そのような例では、道路セグメントエンジン２０４は、例えば、上記のローカルおよび遠隔の道路合流点を参照して説明したように、遠隔道路セグメントについての過去の道路セグメント走行時間およびローカル道路セグメントについてのリアルタイムの道路セグメント走行時間を使用することができる。
【００９５】
例えば、道路セグメントエンジン２０４は、道路セグメントを通って走行する対象物（例えば、１つ以上のモバイルコンピューティングシステム１０８、クライアント装置１１０、または他の車両）のリアルタイムの走行時間に基づいて、ローカル道路セグメント走行時間を決定する。また、道路セグメントエンジン２０４は、遠隔道路セグメントを通る対象物の過去の走行時間に基づいて遠隔道路セグメント走行時間を決定する。
【００９６】
いくつかの実装形態では、ステップ４２８で、道路セグメントエンジン２０４は、例えば、過去の道路セグメント走行時間やリアルタイムの道路セグメント走行時間に基づいて、平均の道路セグメント走行時間を推定する。いくつかの実装形態では、道路セグメントエンジン２０４は、実装形態に応じて、１つのルートまたはルートのセット内の道路セグメントについての平均走行時間を推定する。
【００９７】
ステップ４３２で、ルートエンジン２０２は、例えば、（例えば、ステップ４３０、４０８、４２０で受信された）ローカル道路合流点走行時間、遠隔道路合流点走行時間、道路セグメント走行時間、およびクライアント装置１１０の位置の１つ以上に基づいて、道路合流点の影響を使用してルートを計算する。いくつかの実装形態では、ルートエンジン２０２はさらに、上記で説明したように、（例えば、高速道路、有料道路などを回避する）ユーザの好みをそのルートの決定において考慮に入れる。いくつかの実装形態では、ルートエンジン２０２は、出発地から目的地までの道路をたどる１つのルートまたはルートのセットを生成し、上記で説明した区間および道路合流点走行時間を最も効果的なルートを選択する際に考慮に入れる。
【００９８】
ステップ４３４で、ルートエンジン２０２は、例えば、図３を参照して説明したように、計算されたルートのうちの選択されたルートについてのルート案内を生成し、モバイルコンピューティングシステム１０８またはクライアント装置１１０にそのルート案内を提
供する。
【００９９】
図５Ａは、道路セグメント５０２および道路合流点５０４の例の図５００を示す。図示するように、道路セグメント５０２ａ、５０２ｂ、５０２ｃ、５０２ｄ、５０２ｅは、交差点または他の道路合流点の間の道路のセクションを含む。図示するように、道路合流点５０４ａ、５０４ｂ、５０４ｃは、道路セグメント５０２を結ぶ接続部である。
【０１００】
矢印５０６ａ、５０６ｂ、および５０６ｃは、複数の道路セグメント５０２間のルート候補を示す。いくつかの実装形態では、矢印５０６は、右左折または車線レベルに対して定義された個々の道路合流点を表すが、いくつかの実装形態では、道路合流点は、（例えば、５０４ｃのように２つ以上の区間を接続する）交差点レベルに対して定義され得ることに留意されたい。
【０１０１】
例えば、矢印５０６ａは、道路セグメント５０２ｂを道路セグメント５０２ｃに（例えば、左折方向として）接続し、矢印５０６ｂは、道路セグメント５０２ｂを道路セグメント５０２ｅに（例えば、直進または直線移動として）接続し、そして矢印５０６ｃは、道路セグメント５０２ｂを道路セグメント５０２ｄに（例えば、右折方向として）接続する。
【０１０２】
図５Ｂは、オンランプ５５４、オフランプ５５６、および道路セグメント５５８を有する例示的な高速道路５５２の図５５０を示す。オンランプ５５４およびオフランプ５５６は、上記で説明したように、ランプメータなどを含む。いくつかの実装形態では、オンランプ５５４およびオフランプ５５６の自明でない長さのために、ナビゲーションアプリケーション１１２は、長さおよび平均移動速度を、例えば、道路合流点走行時間を決定する際に考慮に入れることができ、他の実施形態では、この考慮事項を、上記で説明した道路合流点走行時間／遅延に組み込むことができる。同様に、高速道路セグメント５５８は、オンランプ５５４とオフランプ５５６との間の距離として定義されるが、道路セグメントは、単にその終点ではなく、その長さに沿って道路合流点を有することができ、したがって実装に応じて、より長いまたは継続的な道路として定義することができることに留意されたい。
【０１０３】
以上の説明では、本発明を十分に理解できるように、多くの詳細について説明した。しかしながら、各実装形態はこれらの具体的な詳細無しでも実施できることは当業者にとって明らかであろう。また、発明が不明瞭になることを避けるために、構造や装置をブロック図の形式で表すこともある。たとえば、本発明は、クライアント装置および特定のソフトウェア／ハードウェアとともに実装される。しかし、明細書の記載は、データおよびコマンドを受信する任意のタイプの計算装置、および、サービスを提供する任意の周辺機器について適用できる。
【０１０４】
本明細書における「一実装形態」または「ある実装形態」等という用語は、その実装形態と関連づけて説明される特定の特徴・構造・性質が、少なくとも一つの実装形態に含まれることを意味する。「一実装形態における」等という用語は本明細書内で複数用いられるが、これらは必ずしも同一の実装形態を示すものとは限らない。
【０１０５】
以上の詳細な説明の一部は、コンピュータ可読記憶媒体に記憶されたデータビットに対する動作のアルゴリズムおよび記号的表現として提供される。これらのアルゴリズム的な説明および表現は、データ処理技術分野の当業者によって、他の当業者に対して自らの成果の本質を最も効果的に説明するために用いられるものである。なお、本明細書において（また一般に）アルゴリズムとは、所望の結果を得るための論理的な手順を意味する。処理のステップは、物理量を物理的に操作するものである。必ずしも必須ではないが、通常
は、これらの量は記憶・伝送・結合・比較およびその他の処理が可能な電気的または磁気的信号の形式を取る。通例にしたがって、これらの信号をビット・値・要素・エレメント・シンボル・キャラクタ・項・数値などとして称することが簡便である。
【０１０６】
なお、これらの用語および類似する用語はいずれも、適切な物理量と関連付いているものであり、これら物理量に対する簡易的なラベルに過ぎないということに留意する必要がある。以下の説明から明らかなように、特に断らない限りは、本明細書において「処理」「計算」「コンピュータ計算（処理）」「判断」「表示」といった用語を用いた説明は、コンピュータシステムや類似の電子的計算装置の動作および処理であって、コンピュータシステムのレジスタやメモリ内の物理的（電子的）量を、他のメモリやレジスタまたは同様の情報ストレージや通信装置、表示装置内の物理量として表される他のデータへ操作および変形する動作および処理を意味する。
【０１０７】
本発明は、本明細書で説明される動作を実行する装置にも関する。この装置は要求される目的のために特別に製造されるものであっても良いし、汎用コンピュータを用いて構成しコンピュータ内に格納されるプログラムによって選択的に実行されたり再構成されたりするものであっても良い。このようなコンピュータプログラムは、コンピュータのシステムバスに接続可能な、例えばフロッピー（登録商標）ディスク・光ディスク・ＣＤ−ＲＯＭ・磁気ディスクなど任意のタイプのディスク、読み込み専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気または光学式カード、ＵＳＢキーを含む不揮発性フラッシュメモリ、電子的命令を格納するために適した任意のタイプの媒体などの、非一時的なコンピュータ可読記憶媒体に記憶される。
【０１０８】
発明の具体的な実装形態は、完全にハードウェアによって実現されるものでも良いし、完全にソフトウェアによって実現されるものでも良いし、ハードウェアとソフトウェアの両方によって実現されるものでも良い。実装形態は、ソフトウェアによって実現されてもよい。ここでソフトウェアとは、ファームウェア、常駐ソフトウェア、マイクロコードやその他のソフトウェアを含むものである。
【０１０９】
さらに、ある実装形態は、コンピュータが利用あるいは読み込み可能な記憶媒体からアクセス可能なコンピュータプログラムプロダクトの形態を取る。この記憶媒体は、コンピュータや任意の命令実行システムによってあるいはそれらと共に利用されるプログラムコードを提供する。コンピュータが利用あるいは読み込み可能な記憶媒体とは、命令実行システムや装置によってあるいはそれらと共に利用されるプログラムを、保持、格納、通信、伝搬および転送可能な任意の装置を指す。
【０１１０】
プログラムコードを格納・実行するために適したデータ処理システムは、システムバスを介して記憶素子に直接または間接的に接続された少なくとも１つのプロセッサを有する。記憶素子は、プログラムコードの実際の実行に際して使われるローカルメモリや、大容量記憶装置や、実行中に大容量記憶装置からデータを取得する回数を減らすためにいくつかのプログラムコードを一時的に記憶するキャッシュメモリなどを含む。
入力／出力（Ｉ／Ｏ）装置は、例えばキーボード、ディスプレイ、ポインティング装置などであるが、これらはＩ／Ｏコントローラを介して直接あるいは間接的にシステムに接続される。
【０１１１】
データ処理システムが、介在するプライベートネットワークおよび／またはパブリックネットワークを介して、他のデータ処理システム、ストレージデバイス、リモートプリンタなどに結合されるようになることを可能にするために、ネットワークアダプタもシステムに結合されうる。ワイヤレス（たとえば、Ｗｉ−Ｆｉ（登録商標））トランシーバ、イーサネット（登録商標）アダプタ、およびモデムは、ネットワークアダプタのほんの数例
に過ぎない。
【０１１２】
本明細書において提示されるアルゴリズムおよび表示は特定のコンピュータや他の装置と本来的に関連するものではない。本明細書における説明にしたがったプログラムを有する種々の汎用システムを用いることができるし、また要求された処理ステップを実行するための特定用途の装置を製作することが適した場合もある。これら種々のシステムに要求される構成は、以上の説明において明らかにされる。さらに、本発明は、特定のプログラミング言語と関連づけられるものではない。様々な実装形態で説明される本発明の内容を実装するために種々のプログラミング言語を利用できることは明らかであろう。
【０１１３】
実装形態の前述の説明は、例示と説明を目的として行われたものである。したがって、明細書を、網羅的または開示された正確な形式に限定することを意図するものではない。本発明は、上記の開示にしたがって、種々の変形が可能である。本発明の範囲は上述の実装形態に限定解釈されるべきではなく、特許請求の範囲にしたがって解釈されるべきである。本発明の技術に詳しい者であれば、本発明はその思想や本質的特徴から離れることなくその他の種々の形態で実現できることを理解できるであろう。同様に、モジュール・処理・特徴・属性・方法およびその他の本発明の態様に関する名前付けや分割方法は必須なものでものないし重要でもない。また、本発明やその特徴を実装する機構は異なる名前や分割方法や構成を備えていても構わない。
さらに、モジュール・処理・特徴・属性・方法およびその他の本発明の態様は、ソフトウェア、ハードウェア、ファームウェアもしくはこれらの組合せとして実装できる。また、本発明をソフトウェアとして実装する場合には、モジュールなどの各要素は、どのような様式で実装されても良い。例えば、スタンドアローンのプログラム、大きなプログラムの一部、異なる複数のプログラム、静的あるいは動的なリンクライブラリー、カーネルローダブルモジュール、デバイスドライバー、その他コンピュータプログラミングの当業者にとって既知な方式として実装することができる。さらに、本発明の実装は特定のプログラミング言語に限定されるものではないし、特定のオペレーティングシステムや環境に限定されるものでもない。以上のように、上記の本発明の説明は限定的なものではなく例示的なものであり、本発明の範囲は添付の特許請求の範囲にしたがって定められる。
【符号の説明】
【０１１４】
１００  動的車両ナビゲーションシステム
１０２  ネットワーク
１０４  ナビゲーションサーバ
１０６  データサーバ
１０８  モバイルコンピューティングシステム
１１０  クライアント装置
１１２  ナビゲーションアプリケーション
１１６  マッピングアプリケーション
１１８  リアルタイム交通モジュール
１３４  地図記憶装置
１３２，１４２，１４４  記憶装置
１３６  過去の道路交通データ
１３８  道路形状データ
１４０  交通信号データ
【図１】
2019184600.tif 000003
【図２】
2019184600.tif 000004
【図３】
2019184600.tif 000005
【図４Ａ】
2019184600.tif 000006
【図４Ｂ】
2019184600.tif 000007
【図４Ｃ】
2019184600.tif 000008
【図５Ａ】
2019184600.tif 000009
【図５Ｂ】
2019184600.tif 000010