(57)【要約】【課題】不確実性ベースの交通渋滞指標を生成するためのメカニズムを提供する。【解決手段】このメカニズムは、複数のＧＰＳデータ・ポイントを取得する。次に、複数のＧＰＳデータ・ポイントを複数の可変スライディング・ウィンドウ（可変スライディング・区間）に分割する。その際、分割が複数の可変スライディング・ウィンドウのそれぞれにおける形状情報の量を最大化するように分割する。次に、ＧＰＳデータ・ポイントが分割によって分割されたのに伴って複数のＧＰＳデータ・ポイントに対してマップ・マッチング・プロセスを実行する。次に、マップ・マッチング・プロセスの信頼度値を計算する。最後に、交通渋滞指標を生成することであって、交通渋滞指標が、マップ・マッチング・プロセスを示す計算された信頼度値を考慮に入れることによって生成される。【選択図】図２６
2017111813.tif 000002
【特許請求の範囲】
【請求項１】
交通渋滞指標を生成するためのコンピュータ実装方法であって、
プロセッサによって複数のＧＰＳデータ・ポイントを取得するステップと、
前記プロセッサによって前記複数のＧＰＳデータ・ポイントを複数の可変スライディング・ウィンドウに分割するステップであって、前記分割が前記複数の可変スライディング・ウィンドウのそれぞれにおける形状情報の量を最大化する、前記分割するステップと、
前記プロセッサによって、前記ＧＰＳデータ・ポイントが前記分割によって分割されたのに伴って前記複数のＧＰＳデータ・ポイントに対してマップ・マッチング・プロセスを実行するステップと、
前記プロセッサによって、前記マップ・マッチング・プロセスの信頼度値を計算するステップと、
前記プロセッサによって前記交通渋滞指標を生成するステップであって、前記交通渋滞指標が、前記マップ・マッチング・プロセスを示す前記計算された信頼度値を考慮に入れることによって生成される、前記生成するステップと
を含む方法。
【請求項２】
前記複数の可変スライディング・ウィンドウはそれぞれ、前記ＧＰＳデータ・ポイントを複数含み、
前記分割するステップにおいて、前記複数の可変スライディング・ウィンドウそれぞれが含む前記ＧＰＳデータ・ポイントの軌跡の形状情報の量を最大化するように分割する、請求項１に記載の方法。
【請求項３】
前記分割後に、前記可変スライディング・ウィンドウのウィンドウ長を、前記軌跡の形状情報の量の多寡に応じて可変させる、請求項２に記載の方法。
【請求項４】
前記複数の可変スライディング・ウィンドウはそれぞれ、前記ＧＰＳデータ・ポイントを複数含み、
前記マップ・マッチング・プロセスを実行するステップにおいて、前記可変スライディング・ウィンドウが含む前記複数のＧＰＳデータ・ポイントからなる軌跡が、デジタルマップ上の道路にマッチングされる、請求項１に記載の方法。
【請求項５】
前記プロセッサによって前記交通渋滞指標を出力するステップをさらに含む、請求項１に記載の方法。
【請求項６】
前記分割するステップにおいて、少なくとも、第１の可変ウィンドウを有する第１の可変スライディング・ウィンドウと、第２の可変ウィンドウを有する第２の可変スライディング・ウィンドウとを生成し、前記第１の可変ウィンドウが前記第２の可変ウィンドウと異なる、請求項１に記載の方法。
【請求項７】
前記マップ・マッチング・プロセスが前記複数の可変スライディング・ウィンドウのそれぞれについて実行される、請求項１に記載の方法。
【請求項８】
前記信頼度値を計算するステップにおいて、前記可変スライディング・ウィンドウのそれぞれについて、それに含まれる各形状に対し、前記複数のＧＰＳデータ・ポイントに関連する軌跡の連続性の量を評価することを含む、請求項１に記載の方法。
【請求項９】
前記信頼度値を計算するステップにおいて、前記可変スライディング・ウィンドウのそれぞれについて、それに含まれる各形状に対し、前記複数のＧＰＳデータ・ポイントに関連する軌跡の平滑性の量を評価することを含む、請求項１に記載の方法。
【請求項１０】
前記信頼度値を計算するステップにおいて、前記可変スライディング・ウィンドウのそれぞれについて、それに含まれる各形状に対し、前記複数のＧＰＳデータ・ポイントに関連する曲線類似性を評価することを含む、請求項１に記載の方法。
【請求項１１】
前記曲線類似性がディジタル・マップ上の道路に対して計算される、請求項１０に記載の方法。
【請求項１２】
前記曲線類似性が、フレシェ距離を決定することによって計算される、請求項１０に記載の方法。
【請求項１３】
前記複数のＧＰＳデータ・ポイントが複数のプローブ車両から取得される、請求項１に記載の方法。
【請求項１４】
交通渋滞指標を生成するためにコンピュータによって実行可能なプログラムであって、
前記コンピュータに、
複数のＧＰＳデータ・ポイントを取得するステップ、
前記複数のＧＰＳデータ・ポイントを複数の可変スライディング・ウィンドウに分割するステップであって、前記分割が前記複数の可変スライディング・ウィンドウのそれぞれにおける形状情報の量を最大化する、前記分割するステップ、
前記ＧＰＳデータ・ポイントが前記分割によって分割されたのに伴って前記複数のＧＰＳデータ・ポイントに対してマップ・マッチング・プロセスを実行するステップ、
前記マップ・マッチング・プロセスの信頼度値を計算するステップ、
前記交通渋滞指標を生成するステップであって、前記交通渋滞指標が、前記マップ・マッチング・プロセスを示す前記計算された信頼度値を考慮に入れることによって生成される、前記生成するステップ、
を実行させるためのプログラム。
【請求項１５】
前記コンピュータに、前記交通渋滞指標を出力するステップをさらに実行させる、請求項１４に記載のプログラム。
【請求項１６】
前記分割するステップにおいて、少なくとも、第１の可変ウィンドウを有する第１の可変スライディング・ウィンドウと、第２の可変ウィンドウを有する第２の可変スライディング・ウィンドウとを生成し、前記第１の可変ウィンドウが前記第２の可変ウィンドウと異なる、請求項１４に記載のプログラム。
【請求項１７】
前記マップ・マッチング・プロセスが前記複数の可変スライディング・ウィンドウのそれぞれについて実行される、請求項１４に記載のプログラム。
【請求項１８】
前記信頼度値を計算するステップにおいて、前記可変スライディング・ウィンドウのそれぞれについて、それに含まれる各形状に対し、前記複数のＧＰＳデータ・ポイントに関連する曲線類似性を評価することを含み、
前記曲線類似性がディジタル・マップ上の道路に対して計算され、
前記曲線類似性が、フレシェ距離を決定することによって計算される、請求項１４に記載のプログラム。
【請求項１９】
交通渋滞指標を生成するためのシステムであって、
プロセッサと、
コンピュータ可読命令を記憶したメモリとを備え、前記コンピュータ可読命令が、前記プロセッサによって実行されたとき、
複数のＧＰＳデータ・ポイントを取得するステップと、
前記複数のＧＰＳデータ・ポイントを複数の可変スライディング・ウィンドウに分割するステップであって、前記分割が前記複数の可変スライディング・ウィンドウのそれぞれにおける形状情報の量を最大化する、前記分割するステップと、
前記ＧＰＳデータ・ポイントが前記分割によって分割されたのに伴って前記複数のＧＰＳデータ・ポイントに対してマップ・マッチング・プロセスを実行するステップと、
前記マップ・マッチング・プロセスの信頼度値を計算するステップと、
前記交通渋滞指標を生成するステップであって、前記交通渋滞指標が、前記マップ・マッチング・プロセスを示す前記計算された信頼度値を考慮に入れることによって生成される、前記生成するステップと、
前記交通渋滞指標を出力するステップと
を実行する、システム。
【請求項２０】
前記出力するステップにおいて、前記交通渋滞指標をマップの形で出力する、請求項１９に記載のシステム。
【請求項２１】
前記分割するステップにおいて、少なくとも、第１の可変ウィンドウを有する第１の可変スライディング・ウィンドウと、第２の可変ウィンドウを有する第２の可変スライディング・ウィンドウとを生成し、前記第１の可変ウィンドウが前記第２の可変ウィンドウと異なる、請求項１９に記載のシステム。
【請求項２２】
前記マップ・マッチング・プロセスが前記複数の可変スライディング・ウィンドウのそれぞれについて実行される、請求項１９に記載のシステム。
【請求項２３】
前記出力するステップにおいて、（ａ）ディスプレイ、（ｂ）ハードコピー・プリンタ、（ｃ）データ・ストレージ・デバイス、および（ｄ）これらの任意の組合せ、のうちの少なくとも１つに前記交通渋滞指標を出力する、請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自動車両の交通条件を監視するためのメカニズムに関し、より詳細には、交通渋滞エリアを回避する際に運転手が使用するための改善された交通渋滞指標に関する。
【背景技術】
【０００２】
交通渋滞情報、例えば、交通渋滞指標（ＴＣＩ、traffic congestionindex）の形の情報が、旅行計画および運転誘導において広く応用されている（例えば、ＧＯＯＧＬＥマップやＢＡＩＤＵマップなどを参照されたい）。
【０００３】
テレマティクスならびにセンサおよびモビリティ技術の開発に伴い、近い将来、何百万台ものコネクテッド・ビークル（connected vehicle）が現実になるであろう。そして、「メガ・コネクテッド・ビークル」時代における交通渋滞指標計算のために、様々な車両から調達される全地球測位システム（ＧＰＳ）データが一般に使用されるであろう。
【０００４】
ここで図１を参照すると、ここには、マップ１０１上に描かれた交通渋滞指標の、従来の作成の例が示されている。交通渋滞指標は、専用ポータブル・ナビゲーション・デバイス（ここではその１つがナビゲーション・デバイス１０３として示されている）上で示されることがある。さらに、交通渋滞指標は、スマート・フォン（ここではその１つがスマート・フォン１０５として示されている）上で示されることもある。さらにまた、交通渋滞指標は、テレビジョン放送（ここではその１つがテレビジョン放送１０７として示されている）上で示されることもある。
【０００５】
引き続き図１を参照すると、交通渋滞指標は、（ａ）固定センサからの交通データ（この図１では要素１０９として示されている）、（ｂ）モバイル・センサからの交通データ（この図１では要素１１１として示されている）、（ｃ）公衆イベントからの交通データ（この図１では要素１１３として示されている）、または（ｄ）ＧＩＳ−Ｔアプリケーションからの交通データ（この図１では要素１１５として示されている）、あるいはそれらの組合せに基づいて作成される場合があることがわかる。
【０００６】
次に図２を参照すると、ここには、データ前処理（２０１）からデータ融合（２０３）へ、適用（２０５）へと移行する従来のプロセスの例が示されている。図でわかるように、道路センサから受け取られたデータは、（１）異常検出およびフィルタリングと、（２）時間的および空間的な相関および補償と、を使用して前処理される。また、図でわかるように、モバイル車両センサから受け取られたデータは、（１）異常検出およびフィルタリングと、（２）軌跡パターン分析と、（３）道路マッピングと、を使用して前処理される。留意すべきことに、この従来のワークフローは、データの精度（すなわちデータ不確実性）に関する尺度の欠如を含む。また、この従来のワークフローでは、データ処理とＴＣＩ計算とが、異なる組織によって扱われる。
【０００７】
ここで、特にＧＰＳに関しては、ＧＰＳセンサの測定値は測位エラーおよびサンプリング・エラーを有するので、ＧＰＳ追跡データが実際の軌跡から逸脱することがほとんど避けられない可能性があることに留意する。結果として、ＧＰＳデータ前処理のタスク（元のＧＰＳ追跡データをディジタル・マップにマッチングする（すなわち「マップ・マッチング」）とともに、例外、エラー補正、雑音および冗長の低減を扱うことを含む）は、ＴＣＩを計算するための必要条件である。このマップ・マッチングに関して、次に図３を参照するが、この図では、車Ａがいくつかの道路上で運転しているのがわかる。この例では、場所シーケンスＡ、Ｂ、Ｃの、元のＧＰＳ追跡データが受け取られた。マップ・マッチングのタスクは、実際の場所シーケンスを推定することであり、これは、Ａ２、Ｂ１、Ｃ３、または、Ａ１、Ｂ２、Ｃ３、または、Ａ３、Ｂ１、Ｃ２などである可能性がある。マップ・マッチングの出力は、最も可能性の高い場所シーケンスまたは軌跡（この例では、「１」の印の付いたより濃いポリラインで示されるように、Ａ１、Ｂ２、Ｃ３）である。
【０００８】
しかし、ＴＣＩ計算の従来の解決法は通常、このような不確実性に関係する尺度が欠如している。すなわち、ＴＣＩ計算の従来の解決法は通常、データ前処理、次いでＴＣＩ計算という、２つの独立したプロセスに分割される。従来のＴＣＩ計算段階の間、すべての入力は等しく確実であると見なされる。
【０００９】
したがって、様々な実施形態は、ＧＰＳデータ処理における不確実性を測定し、次いで第２の段階の間に交通渋滞指標計算の品質を改善するための、メカニズムを提供する。さらに、様々な実施形態で、このようなメカニズムは、システム、方法、またはコンピュータ・プログラム製品、あるいはそれらの組合せを介して実現されることが可能である。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
様々な実施形態は、自動車両の交通条件を監視するためのメカニズムに関し、より詳細には、交通渋滞エリアを回避する際に運転手が使用するための改善された交通渋滞指標に関する。
【課題を解決するための手段】
【００１１】
一実施形態では、交通渋滞指標を生成するためのコンピュータ実装方法が提供される。この方法は、プロセッサによって複数のＧＰＳデータ・ポイントを取得するステップと、プロセッサによって複数のＧＰＳデータ・ポイントを複数の可変スライディング・ウィンドウ（ウィンドウは区間とも呼ぶ）に分割するステップであって、分割が複数の可変スライディング・ウィンドウのそれぞれにおける形状情報の量を最大化する、分割するステップと、プロセッサによって、ＧＰＳデータ・ポイントが分割によって分割されたのに伴って複数のＧＰＳデータ・ポイントに対してマップ・マッチング・プロセスを実行するステップと、プロセッサによって、マップ・マッチング・プロセスの信頼度値を計算するステップと、プロセッサによって交通渋滞指標を生成するステップであって、交通渋滞指標が、マップ・マッチング・プロセスを示す計算された信頼度値を考慮に入れることによって生成される、生成するステップと、を含む。
【００１２】
別の実施形態では、交通渋滞指標を生成するためにコンピュータによって実行可能なプログラムが提供される。プログラムは、コンピュータに複数のＧＰＳデータ・ポイントを取得するステップ、複数のＧＰＳデータ・ポイントを複数の可変スライディング・ウィンドウに分割するステップであって、分割が複数の可変スライディング・ウィンドウのそれぞれにおける形状情報の量を最大化する、分割するステップ、ＧＰＳデータ・ポイントが分割によって分割されたのに伴って複数のＧＰＳデータ・ポイントに対してマップ・マッチング・プロセスを実行するステップ、マップ・マッチング・プロセスの信頼度値を計算するステップ、交通渋滞指標を生成するステップであって、交通渋滞指標が、マップ・マッチング・プロセスを示す計算された信頼度値を考慮に入れることによって生成される、生成するステップ、を実行させる。
【００１３】
別の実施形態では、交通渋滞指標を生成するためのシステムが提供される。このシステムは、プロセッサと、コンピュータ可読命令を記憶したメモリとを備え、コンピュータ可読命令が、プロセッサによって実行されたとき、複数のＧＰＳデータ・ポイントを取得するステップと、複数のＧＰＳデータ・ポイントを複数の可変スライディング・ウィンドウに分割するステップであって、分割が複数の可変スライディング・ウィンドウのそれぞれにおける形状情報の量を最大化する、分割するステップと、ＧＰＳデータ・ポイントが分割によって分割されたのに伴って複数のＧＰＳデータ・ポイントに対してマップ・マッチング・プロセスを実行するステップと、マップ・マッチング・プロセスの信頼度値を計算するステップと、交通渋滞指標を生成するステップであって、交通渋滞指標が、マップ・マッチング・プロセスを示す計算された信頼度値を考慮に入れることによって生成される、生成するステップと、交通渋滞指標を出力するステップと、を実行する。
【００１４】
一例では、出力するステップにおいて、交通渋滞指標をマップの形で出力する。
【００１５】
添付の図面と共に読まれる後続の詳細な記述を考慮すれば、本発明の様々な目的、特徴、および利点が当業者には明らかになるであろう。
【図面の簡単な説明】
【００１６】
【図１】マップ上に描かれた交通渋滞指標の、従来の作成の例を示す図である。
【図２】データ前処理からデータ融合へ、適用へと移行する従来のプロセスの例を示す図である。
【図３】従来のマップ・マッチング・プロセスの例を示す図である。
【図４】一実施形態による可変スライディング・ウィンドウ分割器およびマップ・マッチング器を示すブロック図である。
【図５】一実施形態による例示的なマップ・マッチング・プロセス（図４のマップ・マッチング器によって実行されるタイプの）のブロック図である。
【図６】一実施形態による、形状情報、スライディング・ウィンドウ、およびマップ・マッチング信頼度に関連する図である。
【図７】一実施形態による、形状情報、スライディング・ウィンドウ、およびマップ・マッチング信頼度に関連する図である。
【図８】一実施形態による、形状情報、スライディング・ウィンドウ、およびマップ・マッチング信頼度に関連する図である。
【図９】ＧＰＳデバイスによってもたらされる様々な不確実性がＴＣＩに影響を及ぼすことを示す例示的なマップ（一実施形態による）を描いた図であり、橋の上に信号がないことを示す図である。
【図１０】ＧＰＳデバイスによってもたらされる様々な不確実性がＴＣＩに影響を及ぼすことを示す例示的なマップ（一実施形態による）を描いた図であり、湖の下を横断するトンネルと、トンネルを離れた後の、街路を横断するための折返し路とを示す図である。
【図１１】ＧＰＳデバイスによってもたらされる様々な不確実性がＴＣＩに影響を及ぼすことを示す例示的なマップ（一実施形態による）を描いた図であり、リンク欠落を示す図である。
【図１２】ＧＰＳデバイスによってもたらされる様々な不確実性がＴＣＩに影響を及ぼすことを示す例示的なマップ（一実施形態による）を描いた図であり、ＧＰＳ「フローティング」を示す図である。
【図１３】可変スライディング・ウィンドウ中の様々な軌跡が問題となることを示す例示的なマップ（一実施形態による）を描いた図であり、軌跡６０１の長さおよび形状を示す図である。
【図１４】可変スライディング・ウィンドウ中の様々な軌跡が問題となることを示す例示的なマップ（一実施形態による）を描いた図であり、軌跡６０３の長さおよび形状を示す図である。
【図１５】可変スライディング・ウィンドウ中の様々な軌跡が問題となることを示す例示的なマップ（一実施形態による）を描いた図であり、軌跡６０５の長さおよび形状を示す図である。
【図１６】可変スライディング・ウィンドウ中の様々な軌跡が問題となることを示す例示的なマップ（一実施形態による）を描いた図であり、軌跡６０７の長さおよび形状を示す図である。
【図１７】形状の情報量に関する例示的な一実装形態（一実施形態による）を描いた図である。
【図１８】形状の情報量に関する例示的な一実装形態（一実施形態による）を描いた図である。
【図１９】形状の情報量に関する例示的な一実装形態（一実施形態による）を描いた図である。
【図２０】従来の曲線類似性決定方法についての記述を描いた図である。
【図２１】従来のフレシェ距離決定方法についての記述を描いた図である。
【図２２】例示的な交通渋滞指標計算に関係する図面を描いた図である。
【図２３】例示的な交通渋滞指標出力を示すマップを描いた図である。
【図２４】一実施形態による方法のフローチャートである。
【図２５】一実施形態による方法のフローチャートである。
【図２６】一実施形態によるシステムのブロック図である。
【図２７】一実施形態によるシステムのブロック図である。
【図２８】不確実性を管理することによって心理的ギャップを最小化できる一実施形態に関係する図である。
【図２９】不確実性を管理することによって心理的ギャップを最小化できる一実施形態に関係する図である。
【発明を実施するための形態】
【００１７】
本発明を記述および特許請求する目的で、「マップ・マッチング・プロセス」という言葉は、元のＧＰＳ追跡データをディジタル・マップに（例えば、ディジタル・マップ上の道路に）マッピングすることを指すものとする。
【００１８】
本発明を記述および特許請求する目的で、「マップ・マッチング・プロセスを示す信頼度値」という言葉は、元のＧＰＳデータがディジタル・マップ（例えば、ディジタル・マップ上の道路）に正しくマッチングされている可能性がどれくらい高いかを示す指示を指すものとする。
【００１９】
本明細書に記載のように、様々な実施形態の核となる考えは、ＧＰＳデータ前処理段階の新しい出力として不確実性測定値を追加することであり、ＧＰＳデータ前処理段階の新しい出力としての不確実性測定値はまた、交通渋滞指標計算のための新しい入力として追加される（これに関して、鍵となる問題および困難は、これらの不確実性がどのように起こるか、およびそれらをどのように測定するかを理解することである。本明細書では、これらの不確実性がどのように起こるかについてのいくつかの説明、ならびにそれらをどのように測定するかについてのいくつかの記述が記載される）。
【００２０】
次に図４を参照すると、一実施形態による可変スライディング・ウィンドウ分割器３０１およびマップ・マッチング器３０３が示されている。これに関して、前に言及したように、ＧＰＳデータ前処理の鍵となるステップは、マップ・マッチング（元のＧＰＳ追跡データをディジタル・マップにマッチングする）として知られる。結果として、各車両が運転された実際の道路を識別することができる。このステップは、ＴＣＩを計算するための必要条件である。しかし、ＴＣＩは、ある時間期間（普通は５分〜１５分）中に各道路セグメントを通って運転されたすべての車両の総計情報に基づく。
【００２１】
ＴＣＩ計算段階に入るために、最初に、生ＧＰＳデータの長いシーケンスが、マップ・マッチングのためにスライディング・ウィンドウに分割されなければならない。従来の解決法では、スライディング・ウィンドウの長さは普通、固定されている。対照的に、本明細書に記載の様々な実施形態では、特別に設計された可変スライディング・ウィンドウ分割器３０１が、この目的に使用される。さらに、「マップ・マッチング信頼度計算器」（マップ・マッチング器３０３の一部である）中で、マップ・マッチング・ウィンドウの各結果につき、信頼度値が計算される。したがって、各ウィンドウ内の軌跡の長さおよび形状が、信頼度計算にとってクリティカルである（例えば、直線は、固有の特徴を有しない（形状情報を保持しない）ことがあり、信頼度値の品質はほとんど保証されない可能性がある（おそらく多くの代替がある））。
【００２２】
本明細書に記載のように、この実施形態は、各スライディング・ウィンドウ内の軌跡の形状情報量を計算するための計算器３０１Ａを提供する。さらに、可変スライディング・ウィンドウ分割器３０１は、生ＧＰＳデータの長いシーケンスをいくつかのスライディング・ウィンドウに分割するための最適化エンジン（または最適化器）３０１Ｂを備える（この場合、すべてのウィンドウの形状情報量が最大化される）。
【００２３】
引き続き図４を参照すると、「マップ・マッチング信頼度計算器」（マップ・マッチング器３０３の一部である）は、次のようにマップ・マッチング信頼度計算を実行することができる。すなわち、（ａ）ＧＰＳデータの分析によって軌跡の形状の連続性および平滑性を評価する（これは「信号安定性」の評価である）か、または（ｂ）曲線類似性計算を実行して各スライディング・ウィンドウにつきマップ・マッチング信頼度を計算するか、あるいはその両方を行う。
【００２４】
上記のポイント（ｂ）に関して、特定の例示的な一実装形態では、フレシェ距離を使用することができる。数学において、フレシェ距離は、曲線に沿った点の場所および順序付けを考慮に入れる、曲線間の類似性の尺度である。他の例では、他の曲線類似性方法を使用してもよい。いずれの場合でも、前に言及したように、可変スライディング・ウィンドウ分割器３０１は、すべてのウィンドウの情報量を最大化することができる（例えば、したがって、曲線類似性計算品質を保証することができ、また定量化もすることができる）。
【００２５】
次に、なぜスライディング・ウィンドウが一般に必要かについて言及するが、典型的な移動は普通、１０００個を超えるＧＰＳサンプリング・ポイントを有するであろうことに留意する。これに関して、可能なすべての組合せは、非常に多数となり得る（例えば、８＊８＊１０＊．．．．＊１２＝１．２３＊１０１０００）。したがって、長い移動を多くの部分（スライディング・ウィンドウ）に分割する必要がある。
【００２６】
次に図５を参照すると、一実施形態による例示的なマップ・マッチング・プロセス（図４のマップ・マッチング器３０３によって実行されるタイプの）が示されている。図でわかるように、この例示的なマップ・マッチング・プロセスは、ポイント「１」、「２」、および「３」（マップ４０１中に示される）を使用し、次いで（各ポイントにつき）、４０３に示されるステップ、４０５に示されるステップ、および４０７に示されるステップへと移行する。
【００２７】
次に図６、７、および８を参照すると、一実施形態による、形状情報、スライディング・ウィンドウ、およびマップ・マッチング信頼度に関連する図が示されている。より詳細には、図６は、いくつかのＧＰＳサンプリング・ポイントと、走行されたかもしれない可能な２つの道路（道路Ａおよび道路Ｂ）とを示す。次に図７を参照すると、スライディング・ウィンドウ２中の軌跡が有する形状情報がより少なく、したがってマップ・マッチング結果に関する信頼度がない（または低い）ことがわかる（すなわち、車は実際には道路Ａ上で運転されたのかそれとも道路Ｂ上で運転されたのか？）。しかし、次に図８を参照すると、スライディング・ウィンドウ２中の軌跡が有する形状情報はより多く、したがってマップ・マッチング結果に関するより多くの信頼度がある（すなわち、車は実際には道路Ａ上で運転された）。
【００２８】
次に、データ収集／処理に関するいくつかの観察について言及する（これらの観察は、様々な実施形態の処理または利点あるいはその両方のいくらかに対する基礎を提供した）。すなわち、（ａ）プローブ車両は、時間次元と空間次元の両方で不均衡である。（ｂ）ＧＰＳデバイスによってもたらされる不確実性が、ＴＣＩに影響を及ぼす（例えば、図９（橋の上に信号がないことを示す）、図１０（湖の下を横断するトンネルと、トンネルを離れた後の、街路を横断するための折返し路とを示す）、図１１（リンク欠落を示す）、図１２（ＧＰＳ「フローティング」（すなわち、高精度の位置決定を得ることができない）ことを示す）を参照されたい）。（ｃ）ＧＰＳ信号は、しばしば不安定であり、多くの要因に影響される可能性がある（例えば、気象条件、高い建物、高架道路、トンネル、橋）。（ｄ）ＧＰＳ信号エラーおよび中断が偏在する。（ｄ）マップ・マッチングにおける不確実性を、信号安定性または平滑性によって測定することができる（これに関して、例えば、ＧＰＳ信号が（前に言及したように）「フローティング」することがあるか、または所与の経路でＧＰＳ信号が欠落していることがある（例えば、地下道の下もしくはトンネル中でＧＰＳ信号が失われることがある）か、あるいはその両方の場合があることに留意する）。（ｅ）マップ・マッチングにおける不確実性を、いくつかの種類の曲線類似性計算によって測定することができる。（ｆ）可変スライディング・ウィンドウ中の軌跡の長さおよび形状が問題となる（例えば、様々な軌跡６０１、６０３、６０５、および６０７の様々な長さおよび形状を示す図１３〜１６を参照されたい）。
【００２９】
次に図１７、１８、および１９を参照すると、一実施形態による、形状の情報量に関する例示的な一実装形態が示されている（すなわち、これらの図は、所与の曲線についてどのように形状情報を計算するかに関係する）。図でわかるように（図１７参照）、重さｍの仮想的な小さい球８０１が、所与の軌跡に沿って一定速度ｖで進んでいると仮定する。この場合、重さｍを速度ｖで動かすために消費される必要のある最小エネルギー量が、形状情報量としての働きをすることができる（すなわち、必要とされるエネルギー量が多いほど、形状情報量は増加する）。また、図１７に示される曲線の数学的表現を示す図１８も参照されたい。また、図１８の数学的表現に関連するいくつかの式を示す図１９も参照されたい。さらに、前に言及したように、図４の可変スライディング・ウィンドウ分割器１０１は、生ＧＰＳデータの長いシーケンスをいくつかのスライディング・ウィンドウに分割するための最適化エンジン（または最適化器）３０１Ｂを備える（この場合、すべてのウィンドウの形状情報量が最大化される）。これに関して（すなわち、可変スライディング・ウィンドウ分割器を用いて「どのように形状情報量を最大化するか？」について）、いくつかの種類の最適化器を使用してスライディング・ウィンドウの最良の切断プランを見つけることができることに留意する。例えば、すべてのスライディング・ウィンドウの形状情報量が最大化されるようにすることは、各ウィンドウの最小長さ、オンライン計算の遅延要件（長すぎるべきでない）、渋滞報告間隔（普通は５〜１０分）、などに関する制約を使用する。さらに（また図４を再び参照すると）、可変スライディング・ウィンドウ分割器（ＶＳＷＤ）とマップ・マッチング器（ＭＭ）との間にフィードバック・メカニズムがあってもよい。この場合、ＶＳＷＤは、スライディング・ウィンドウの切断プランをＭＭに出力し、次いでＭＭは、いくつかのスライディング・ウィンドウ内で激しく競合する代替軌跡をＭＭが見つけた場合に、切断プランを調整するようＶＳＷＤに要求することができる。
【００３０】
次に図２０を参照すると、従来の曲線類似性決定方法についての記述が提供されている。特定の一例では、この従来の曲線類似性決定方法を、本明細書に記載のマップ・マッチング・プロセスで利用することができる。
【００３１】
次に図２１を参照すると、従来のフレシェ距離決定方法についての記述が提供されている。特定の一例では、この従来のフレシェ距離決定方法を、本明細書に記載のマップ・マッチング・プロセスで利用することができる。
【００３２】
次に図２２および２３を参照すると、図２２は、例示的な交通渋滞指標計算に関係する図面を描いており、図２３は、例示的な交通渋滞指標出力を示すマップを描いている。より詳細には、図２２でわかるように、この例では、交通渋滞指標を、各道路セグメントにつき［０〜１０］の値として定義することができる（例えば、ＴＣＩ＝１のときは、望むだけ速く運転することができる。例えば、ＴＣＩ＝８のときは、２分の１に減速されることになる（ＴＣＩ＝０に対して相対的に））。さらに、図２３でわかるように、マップ１２００は、各道路についての関連するＴＣＩに合わせて色分けされた道路を有することができる。
【００３３】
次に図２４を参照すると、一実施形態による、交通渋滞指標を計算するための例示的なプロセスが示されている。図でわかるように、データ・クリーニング・ステップ１３０１で、生ＧＰＳデータが「クリーニング」される。次いで、ステップ１３０３で、クリーニングされたデータは可変スライディング・ウィンドウ分割器に提供されて、いくつかの可変スライディング・ウィンドウが生成される（このステップは、長さ、形状、および雑音を考慮して実行されてよい。さらに、このステップは、遅延要件に関して実行されてよい。さらにまた、このステップは、渋滞報告間隔（例えば５〜１５分）に関して実行されてよい）。次いで、ステップ１３０５で、ステップ１３０３からの出力がマップ・マッチングのために受け取られる（このステップ１３０５は、生ＧＰＳデータを様々な道路セグメントにマッチングするために実行されてよい）。ステップ１３０５では、各道路セグメントが、いくつかのマッチングされた軌跡に関係してもよい。さらに、データがステップ１３０５からステップ１３０３にフィードバックされてもよい。加えて、ステップ１３０５からのデータがステップ１３０７に提供されるが、ステップ１３０７は、マップ・マッチング信頼度を決定するためのプロセスである。ステップ１３０７ではまた、以下の情報も受け取られる。すなわち、（ａ）データ・ソース特有の不確実性に関係する、ステップ１３０９からの情報（例えば、空のタクシーが意図的に減速することがある（乗り手を拾うなどのために）。バスが多くの場所で停車する（乗客を拾うかもしくは降ろすかまたはその両方などのために））、または（ｂ）高速エビデンスに関係する、ステップ１３１１からの情報（例えば、いくつかの車は速く動くことがあるが他の車はゆっくり動くことがある）、あるいはその両方である。いずれの場合でも、ステップ１３０７におけるマップ・マッチング信頼度決定プロセスは、（ａ）生ＧＰＳ軌跡と、マッチングされた道路セグメント軌跡との間の類似性、または（ｂ）信号安定性（平滑性）、あるいはその両方を算出することができる。さらに、マップ・マッチング信頼度決定ステップ１３０７の出力は、複数のプローブ車両からのデータ融合に関係するステップ１３１３に（「新しい入力」として）提供されてよい。このステップ１３１３は、プローブ車両の数が少ないとき（低信頼度）に、ＴＣＩ結果を調整することができる。これに関して、関連するプローブ車両が多いほど、信頼度は高い。加えて、複数のプローブ車両間の矛盾を解決するためにソルバが使用されてもよい。最後に、ＴＣＩがステップ１３１３からスマート・フォン１３１５に提供されてよい（当然、ＴＣＩは、そのうえ（または代わりに）、他の任意の望まれるデバイスに提供されてもよい）。
【００３４】
引き続き図２４を参照するが、ステップ１３０１に関しては、ＧＰＳサンプリング・シーケンス中の自明なエラーが除去されることになる（例えば、他のほとんどのＧＰＳポイントから１０００ｋｍ離れていること、１９４９年や２０４６年からのデータなどのタイムスタンプ・エラー、等）。ステップ１３０９に関しては、交通渋滞の原理は、タクシー、バス、トラック、自家用車など、多くの異なる種類の車両からのサンプル・データ（ＧＰＳ、時間、速度、進行方向など）を使用することになることに留意する。これに関して、データ・ソース特有の不確実性がある（例えば、空のタクシーは普通、乗客を引き付けるために減速する）。したがって、これらのタクシーからのサンプリング・データは渋滞を表さない。同様に、バスもまた、道路渋滞時以外の時に、乗降する乗客のために停止する。ステップ１３１１（高速エビデンスに関する）に関しては、例えば、２つの車両が同じ道路セグメントを走行したばかりであることを示すサンプリング・データが、これらの車両から受け取られることがあることに留意する。しかし、このデータは、一方の車両は非常に高速で走ったが、他方の車両は非常に低速で走ったことを示す。このような状況で、この道路セグメントの交通渋滞の量はどのように決定されるべきか？すなわち、渋滞しているのか、それとも自由に流れているのか？このような種類の不確実性を高速エビデンスと呼ぶことができ、これは、車両がこの道路を高速で走ることができるというエビデンスを受け取ったことを意味する。高速エビデンスは正しいが、他の何らかの個人的理由（例えば電話対応中）によって低速結果が引き起こされる、と仮定することができる。
【００３５】
本明細書に記載のように、交通渋滞指標は、信頼度値を考慮に入れることができる。より詳細には、一例では、交通渋滞指標は、各道路セグメントの、最後の５〜１５分の平均的な交通渋滞レベルを表す。すなわち、最後の５〜１５分の間に道路セグメントを走行したすべての車両が、ＴＣＩへの寄与を有することができる。ＴＣＩについてのサンプル一実装形態は、すべての車両の、平均走行時間／速度である。マップ・マッチング信頼度値がなければ、一般に、各車両が等しく重要であると仮定することしかできない。しかし、様々な実施形態によれば、車両のいくつかが実際には特定の道路を走行しなかったという、信頼度の尺度が提供される（例えば、２０台の低信頼度車両からのデータに関して、これらのデータ（低信頼度）は、単に無視されてもよく、または、単に平均結果を得る以外に重み付き結果を得てもよい。
【００３６】
本明細書に記載のように、ＴＣＩは、信頼度（不確実性の尺度）に基づいて調整されることが可能である。前に言及したように、交通渋滞指標の原理は、タクシー、バス、トラック、自家用車など、多くの異なる種類の車両（プローブ）からのサンプル・データ（ＧＰＳ、時間、速度、進行方向など）を使用することになる。プローブ車両は、時間次元と空間次元の両方で不均衡である（例えば、一日中、郊外の道路を走行するプローブ車両がない。ある期間中は、都会の道路を走行するプローブ車両の数が少ない）。これに関して、以下のシナリオが考えられるであろう。すなわち、（ａ）道路上の１台の車両からサンプリング・データが受け取られただけの場合は、マップ・マッチング信頼度が低いならば交通をその道路上では不明として報告する。（ｂ）多くの車両からサンプリング・データが受け取られた場合は、この高信頼度データを信用する（また、高速エビデンス（前に論じた）を考慮する）。
【００３７】
次に図２５を参照すると、不確実性ベースの交通渋滞指標を生成する方法が示されている。この図２５でわかるように、この実施形態の方法は、１４０１で、プロセッサによって複数のＧＰＳデータ・ポイントを取得することと、１４０３で、プロセッサによって複数のＧＰＳデータ・ポイントを複数の可変スライディング・ウィンドウに分割することであって、分割が複数の可変スライディング・ウィンドウのそれぞれにおける形状情報の量を最大化する、分割することと、１４０５で、プロセッサによって、ＧＰＳデータ・ポイントが分割によって分割されたのに伴って複数のＧＰＳデータ・ポイントに対してマップ・マッチング・プロセスを実行することと、１４０７で、プロセッサによって、マップ・マッチング・プロセスを示す信頼度値を計算することと、１４０９で、プロセッサによって交通渋滞指標を生成することであって、交通渋滞指標が、マップ・マッチング・プロセスを示す計算された信頼度値を考慮に入れることによって生成される、生成することと、を含む。
【００３８】
次に図２６を参照すると、不確実性ベースの交通渋滞指標を生成するためのシステム１５００が提供される。このシステムは、プロセッサ（図示せず）と、コンピュータ可読命令を記憶したメモリ（図示せず）とを備えることができ、コンピュータ可読命令は、プロセッサによって実行されたとき、複数のＧＰＳデータ・ポイントを取得するように構成された取得要素１５０１と、複数のＧＰＳデータ・ポイントを複数の可変スライディング・ウィンドウに分割するように構成された分割要素１５０３であって、分割が複数の可変スライディング・ウィンドウのそれぞれにおける形状情報の量を最大化する、分割要素１５０３と、ＧＰＳデータ・ポイントが分割によって分割されたのに伴って複数のＧＰＳデータ・ポイントに対してマップ・マッチング・プロセスを実行するように構成された実施要素１５０５と、マップ・マッチング・プロセスを示す信頼度値を計算するように構成された計算要素１５０７と、交通渋滞指標を生成するように構成された生成要素１５０９であって、交通渋滞指標が、マップ・マッチング・プロセスを示す計算された信頼度値を考慮に入れることによって生成される、生成要素１５０９と、交通渋滞指標を出力するように構成された出力要素１５１１と、を実装する。
【００３９】
一例では、図２６の様々なコンポーネント間の通信は、双方向とすることができる。別の例では、通信は、インターネット、イントラネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、または他の任意の望まれる通信チャネル、あるいはそれらの組合せを介して実行されてよい。別の例では、各コンポーネントは、他の各コンポーネントに動作可能に接続されてよい。別の例では、これらのコンポーネントのいくつかまたはすべては、図２７に示されるタイプのコンピュータ・システム中で実装されてよい。
【００４０】
次に図２７を参照すると、この図は、本発明の一実施形態によるコンピューティング・システム１６００のハードウェア構成を示す。図でわかるように、このハードウェア構成は、少なくとも１つのプロセッサまたは中央処理装置（ＣＰＵ）１６１１を有する。ＣＰＵ１６１１は、システム・バス１６１２を介して、ランダム・アクセス・メモリ（ＲＡＭ）１６１４と、読取専用メモリ（ＲＯＭ）１６１６と、入出力（Ｉ／Ｏ）アダプタ１６１８（ディスク・ユニット１６２１やテープ・ドライブ１６４０などの周辺デバイスをバス１６１２に接続するための）と、ユーザ・インタフェース・アダプタ１６２２（キーボード１６２４、マウス１６２６、スピーカ１６２８、マイクロフォン１６３２、または他のユーザ・インタフェース・デバイス、あるいはそれらの組合せをバス１６１２に接続するための）と、システム１６００をデータ処理ネットワーク、インターネット、イントラネット、ローカル・エリア・ネットワーク（ＬＡＮ）などに接続するための通信アダプタ１６３４と、バス１６１２をディスプレイ・デバイス１６３８またはプリンタ１６３９（例えばディジタル・プリンタなど）あるいはその両方に接続するためのディスプレイ・アダプタ１６３６と、に相互接続される。
【００４１】
本明細書に記載のように、不確実性測定値を入力として利用して交通渋滞指標を計算するためのメカニズムが提供される。一例では、不確実性測定値は、ＧＰＳ前処理ステップの出力に含まれる。特定の一例では、不確実性測定値は、複数のスライディング・ウィンドウのそれぞれの内の軌跡について形状情報量を計算することに基づく（この場合、生ＧＰＳデータの長いシーケンスが、マップ・マッチングのために複数のスライディング・ウィンドウに分割されている）。別の特定の例では、不確実性測定値は、生ＧＰＳデータを利用して信号安定性を決定することによって、各軌跡の形状の連続性および平滑性を評価することに基づく。
【００４２】
本明細書に記載のように、交通渋滞指標を提供するのに十分なほど信号ソースが正確かどうかを評価するために、生データによって保持される不確実性を掘り出す（例えば、マップ・マッチング信頼度およびデータ融合に基づいて）ためのメカニズムが提供される。
【００４３】
本明細書に記載のように、プローブ車両から収集された交通データ（例えばＧＰＳデータの形の）の信頼度レベルを考慮することによって、交通渋滞指標評価の精度を改善するためのメカニズムが提供される。信頼度レベルは、ＧＰＳデータに基づくマップ・マッチング結果の信頼度評価によって決定することができる（交通渋滞指標推定がマップ・マッチング精度にかなり影響されるという独特の洞察を使用して）。この例では、不確実性は、ＧＰＳセンサの測定値からくる（ＧＰＳは測位エラーおよびサンプリング・エラーを有し、この場合、ＧＰＳ追跡データが実際の軌跡から逸脱することはほとんど避けられない）。
【００４４】
本明細書に記載のように、データ処理とＴＣＩ計算とが、同じ組織によって扱われるためのメカニズムが提供される。
【００４５】
本明細書に記載のように、マップ・マッチング・プロセスに新しい出力（不確実性測定値）を追加するためのメカニズムが提供される。したがって、ＴＣＩ計算段階の間に、低信頼度の状況でＴＣＩを調整することができる。加えて、異なるプローブ車両から複数のデータが受け取られたときに矛盾を解決することができる。
【００４６】
別の実施形態では、不確実性を管理することによって、例えば空のタクシーからのデータは、ＴＣＩ計算において有用である（従来の解決法では、空のタクシーからのデータは通常、完全に除去される）。
【００４７】
別の例では、マップを表示することができ、このマップ中では、交通渋滞が道路網にわたり徐々に広がることにより、交通渋滞指標結果において色が徐々に変更される。
【００４８】
本明細書に記載のように、ＧＰＳシーケンスのセグメント（スライディング・ウィンドウ中の）を道路網上の軌跡にマッチングする（多くの代替軌跡があるかもしれない場合に）ための様々なメカニズムが提供される。さらに、所与のＧＰＳシーケンスが有する形状情報の量が少ない場合は、低い信頼度尺度をマップ・マッチング結果に割り当てることができる。
【００４９】
次に図２８および２９を参照すると、不確実性を管理することによって心理的ギャップを最小化できる一実施形態に関係する図が示されている。より詳細には、前に言及したように、ＴＣＩは、信頼度（不確実性の尺度）に基づいて調整されることが可能である。例えば、本開示の様々な態様が「アプリ」（ＧＯＯＧＬＥマップのような）に適用された場合、ユーザ体験に関するユーザの心理的ギャップの定義を行うことができる。このような定義は、ユーザの期待と、アプリが提供する交通情報との間のギャップ（満足または失望）を表す。例えば、図２８（１台のプローブ車両１７００のみからのデータがある）に関しては、報告される交通渋滞指標に応じて様々なレベルの心理的ギャップ（１７０１Ａ〜１７０１Ｆ）が生み出される場合がある。さらに、図２９（多くのプローブ車両１７５０がある）に関しては、様々な要因１７６０Ａ〜１７６０Ｄを考慮に入れて、報告される交通渋滞指標を道路上の実際の交通レベルにより近くマッチングすることができる。
【００５０】
一実施形態では、交通渋滞指標を生成するためのコンピュータ実装方法が提供される。この方法は、プロセッサによって複数のＧＰＳデータ・ポイントを取得するステップと、プロセッサによって複数のＧＰＳデータ・ポイントを複数の可変スライディング・ウィンドウに分割するステップであって、分割が複数の可変スライディング・ウィンドウのそれぞれにおける形状情報の量を最大化する、分割するステップと、プロセッサによって、ＧＰＳデータ・ポイントが分割によって分割されたのに伴って複数のＧＰＳデータ・ポイントに対してマップ・マッチング・プロセスを実行するステップと、プロセッサによって、マップ・マッチング・プロセスの信頼度値を計算するステップと、プロセッサによって交通渋滞指標を生成するステップであって、交通渋滞指標が、マップ・マッチング・プロセスを示す計算された信頼度値を考慮に入れることによって生成される、生成するステップと、を含む。
【００５１】
一例では、この方法はさらに、前記複数の可変スライディング・ウィンドウはそれぞれ、前記ＧＰＳデータ・ポイントを複数含み、
前記分割するステップにおいて、前記複数の可変スライディング・ウィンドウそれぞれが含む前記ＧＰＳデータ・ポイントの軌跡の形状情報の量を最大化するように分割する。
一例では、この方法はさらに、前記分割後に、前記可変スライディング・ウィンドウのウィンドウ長を、前記軌跡の形状情報の量の多寡に応じて可変させる。
一例では、この方法はさらに、前記複数の可変スライディング・ウィンドウはそれぞれ、前記ＧＰＳデータ・ポイントを複数含み、
前記マップ・マッチング・プロセスを実行するステップにおいて、前記可変スライディング・ウィンドウが含む前記複数のＧＰＳデータ・ポイントからなる軌跡が、デジタルマップ上の道路にマッチングされる。
一例では、この方法はさらに、プロセッサによって交通渋滞指標を出力するステップを含む。
【００５２】
別の例では、分割するステップにおいて、少なくとも、第１の可変ウィンドウを有する第１の可変スライディング・ウィンドウと、第２の可変ウィンドウを有する第２の可変スライディング・ウィンドウとを生成し、第１の可変ウィンドウは第２の可変ウィンドウとは異なる。
【００５３】
別の例では、マップ・マッチング・プロセスは、複数の可変スライディング・ウィンドウのそれぞれについて実行される。
【００５４】
別の例では、信頼度値を計算するステップにおいて、可変スライディング・ウィンドウのそれぞれについて、それに含まれる各形状に対し、複数のＧＰＳデータ・ポイントに関連する軌跡の連続性の量を評価することを含む。
【００５５】
別の例では、信頼度値を計算するステップにおいて、可変スライディング・ウィンドウのそれぞれについて、それに含まれる各形状に対し、複数のＧＰＳデータ・ポイントに関連する軌跡の平滑性の量を評価することを含む。
【００５６】
別の例では、信頼度値を計算するステップにおいて、可変スライディング・ウィンドウのそれぞれについて、それに含まれる各形状に対し、複数のＧＰＳデータ・ポイントに関連する曲線類似性を評価することを含む。
【００５７】
別の例では、曲線類似性は、ディジタル・マップ上の道路に対して計算される。
【００５８】
別の例では、曲線類似性は、フレシェ距離を決定することによって計算される。
【００５９】
別の例では、複数のＧＰＳデータ・ポイントは、複数のプローブ車両から取得される。
【００６０】
別の実施形態では、交通渋滞指標を生成するためにコンピュータによって実行可能なプログラムが提供される。プログラムは、コンピュータに複数のＧＰＳデータ・ポイントを取得するステップ、複数のＧＰＳデータ・ポイントを複数の可変スライディング・ウィンドウに分割するステップであって、分割が複数の可変スライディング・ウィンドウのそれぞれにおける形状情報の量を最大化する、分割するステップ、ＧＰＳデータ・ポイントが分割によって分割されたのに伴って複数のＧＰＳデータ・ポイントに対してマップ・マッチング・プロセスを実行するステップ、マップ・マッチング・プロセスの信頼度値を計算するステップ、交通渋滞指標を生成するステップであって、交通渋滞指標が、マップ・マッチング・プロセスを示す計算された信頼度値を考慮に入れることによって生成される、生成するステップ、を実行させる。
【００６１】
一例では、プログラムは、交通渋滞指標を出力するステップをさらに実行させる。
【００６２】
別の例では、分割するステップにおいて、少なくとも、第１の可変ウィンドウを有する第１の可変スライディング・ウィンドウと、第２の可変ウィンドウを有する第２の可変スライディング・ウィンドウとを生成し、第１の可変ウィンドウは第２の可変ウィンドウとは異なる。
【００６３】
別の例では、マップ・マッチング・プロセスは、複数の可変スライディング・ウィンドウのそれぞれについて実行される。
【００６４】
別の例では、信頼度値を計算するステップにおいて、可変スライディング・ウィンドウのそれぞれについて、それに含まれる各形状に対し、複数のＧＰＳデータ・ポイントに関連する曲線類似性を評価することを含み、曲線類似性はディジタル・マップ上の道路に対して計算され、曲線類似性は、フレシェ距離を決定することによって計算される。
【００６５】
別の実施形態では、交通渋滞指標を生成するためのシステムが提供される。このシステムは、プロセッサと、コンピュータ可読命令を記憶したメモリとを備え、コンピュータ可読命令は、プロセッサによって実行されたとき、複数のＧＰＳデータ・ポイントを取得するステップと、複数のＧＰＳデータ・ポイントを複数の可変スライディング・ウィンドウに分割するステップであって、分割が複数の可変スライディング・ウィンドウのそれぞれにおける形状情報の量を最大化する、分割するステップと、ＧＰＳデータ・ポイントが分割によって分割されたのに伴って複数のＧＰＳデータ・ポイントに対してマップ・マッチング・プロセスを実行するステップと、マップ・マッチング・プロセスの信頼度値を計算するステップと、交通渋滞指標を生成するステップであって、交通渋滞指標が、マップ・マッチング・プロセスを示す計算された信頼度値を考慮に入れることによって生成される、生成するステップと、交通渋滞指標を出力するステップと、を実行する。
【００６６】
一例では、出力するステップにおいて、交通渋滞指標をマップの形で出力する。
【００６７】
別の例では、分割するステップにおいて、少なくとも、第１の可変ウィンドウを有する第１の可変スライディング・ウィンドウと、第２の可変ウィンドウを有する第２の可変スライディング・ウィンドウとを生成し、第１の可変ウィンドウは第２の可変ウィンドウとは異なる。
【００６８】
別の例では、マップ・マッチング・プロセスは、複数の可変スライディング・ウィンドウのそれぞれについて実行される。
【００６９】
別の例では、出力するステップにおいて、（ａ）ディスプレイ、（ｂ）ハードコピー・プリンタ、（ｃ）データ・ストレージ・デバイス、および（ｄ）これらの任意の組合せ、のうちの少なくとも１つに交通渋滞指標を出力する。
【００７０】
他の例では、本明細書に記載の任意のステップは、望まれる任意の適切な順序で実行されてよい。
【００７１】
本発明は、システム、方法、またはコンピュータ・プログラム製品、あるいはそれらの組合せとすることができる。コンピュータ・プログラム製品は、本発明の態様をプロセッサに実行させるためのコンピュータ可読プログラム命令を有するコンピュータ可読ストレージ媒体を含むことができる。
【００７２】
コンピュータ可読ストレージ媒体は、命令実行デバイスによって使用される命令を保持および記憶できる有形デバイスとすることができる。コンピュータ可読ストレージ媒体は、例えば、電子ストレージ・デバイス、磁気ストレージ・デバイス、光学ストレージ・デバイス、電磁ストレージ・デバイス、半導体ストレージ・デバイス、または上記の任意の適切な組合せとすることができるが、これらに限定されない。コンピュータ可読ストレージ媒体のより具体的な例の非網羅的なリストは、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読取専用メモリ（ＲＯＭ）、消去可能プログラム可能な読取専用メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、ポータブル・コンパクト・ディスク読取専用メモリ（ＣＤ−ＲＯＭ）、ディジタル多用途ディスク（ＤＶＤ）、メモリ・スティック、フロッピー（Ｒ）・ディスク、機械的にエンコードされたデバイス（命令が記録された、パンチカード、または溝の中の隆起構造など）、および上記の任意の適切な組合せを含む。本明細書におけるコンピュータ可読ストレージ媒体は、電波もしくは他の自由伝搬する電磁波、導波管もしくは他の伝送媒体を介して伝搬する電磁波（例えば、光ファイバ・ケーブルの中を通る光パルス）、またはワイヤを介して伝送される電気信号など、一時的な信号自体であると解釈されるべきではない。
【００７３】
本明細書に記載のコンピュータ可読プログラム命令は、コンピュータ可読ストレージ媒体からそれぞれのコンピューティング／処理デバイスにダウンロードされてよく、あるいは、ネットワーク（例えば、インターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、もしくはワイヤレス・ネットワーク、またはそれらの組合せ）を介して外部コンピュータまたは外部ストレージ・デバイスにダウンロードされてよい。ネットワークは、銅伝送ケーブル、光伝送ファイバ、ワイヤレス伝送、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータ、またはエッジ・サーバ、あるいはそれらの組合せを含むことができる。各コンピューティング／処理デバイス中の、ネットワーク・アダプタ・カードまたはネットワーク・インタフェースが、コンピュータ可読プログラム命令をネットワークから受け取り、これらのコンピュータ可読プログラム命令を、それぞれのコンピューティング／処理デバイス内のコンピュータ可読ストレージ媒体に記憶されるように転送する。
【００７４】
本発明の動作を実行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セット・アーキテクチャ（ＩＳＡ）命令、機械命令、機械依存命令、マイクロコード、ファームウェア命令、状態設定データであってよく、または、Ｓｍａｌｌｔａｌｋ（Ｒ）やＣ＋＋などのオブジェクト指向プログラミング言語、および、「Ｃ」プログラミング言語や類似のプログラミング言語などの従来の手続き型プログラミング言語を含めた、１つもしくは複数のプログラミング言語の任意の組合せで書かれたソース・コードとオブジェクト・コードとのいずれかであってよい。コンピュータ可読プログラム命令は、完全にユーザのコンピュータ上で実行されるか、スタンドアロンソフトウェアパッケージとして部分的にユーザのコンピュータ上で実行されるか、部分的にユーザのコンピュータ上で実行され部分的にリモート・コンピュータ上で実行されるか、または完全にリモート・コンピュータもしくはサーバ上で実行される場合がある。後者のシナリオでは、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）もしくはワイド・エリア・ネットワーク（ＷＡＮ）を含めた任意のタイプのネットワークを介してユーザのコンピュータに接続されてもよく、または、接続は、外部コンピュータに対して（例えば、インターネット・サービス・プロバイダを使用してインターネット経由で）行われてもよい。いくつかの実施形態では、プログラマブル・ロジック回路、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、またはプログラマブル・ロジック・アレイ（ＰＬＡ）を例えば含む、電子回路が、本発明の態様を実行するために、コンピュータ可読プログラム命令の状態情報を利用して電子回路を個人化することによって、コンピュータ可読プログラム命令を実行することができる。
【００７５】
本明細書では、本発明の態様を、本発明の実施形態による方法、装置（システム）、およびコンピュータ・プログラム製品の、フローチャート説明またはブロック図あるいはその両方に関して述べている。フローチャート説明またはブロック図あるいはその両方の各ブロック、および、フローチャート説明またはブロック図あるいはその両方の中のブロックの組合せを、コンピュータ可読プログラム命令によって実現できることは理解されるであろう。
【００７６】
これらのコンピュータ可読プログラム命令は、コンピュータまたは他のプログラム可能データ処理装置のプロセッサを介して実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロック中で指定される機能／行為を実現する手段をもたらすように、汎用コンピュータ、専用コンピュータ、または他のプログラム可能データ処理装置のプロセッサに提供されて、マシンを生み出すものであってよい。これらのコンピュータ可読プログラム命令はまた、命令が記憶されたコンピュータ可読ストレージ媒体が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロック中で指定される機能／行為の態様を実現する命令を含む製造品を含むように、コンピュータ可読ストレージ媒体に記憶され、コンピュータ、プログラム可能データ処理装置、または他のデバイス、あるいはそれらの組合せに、特定の方式で機能するよう指令するものであってもよい。
【００７７】
コンピュータ可読プログラム命令はまた、コンピュータ、他のプログラム可能装置、または他のデバイス上で実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロック中で指定される機能／行為を実現するように、コンピュータ実装プロセスを生み出すべく、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスにロードされ、コンピュータ、他のプログラム可能装置、または他のデバイス上で一連の動作ステップを実行させるものであってもよい。
【００７８】
図中のフローチャートおよびブロック図は、本発明の様々な実施形態によるシステム、方法、およびコンピュータ・プログラム製品の可能な実装形態の、アーキテクチャ、機能、および動作を示す。これに関して、フローチャートまたはブロック図の中の各ブロックは、モジュール、セグメント、または命令の一部を表すことができ、これは、指定される論理機能を実現するための１つまたは複数の実行可能命令を含む。いくつかの代替実装形態では、ブロック中で示される機能は、図中で示される順序とは異なる順序で生じる場合がある。例えば、関連する機能に応じて、連続して示される２つのブロックが実際にはほぼ同時に実行される場合もあり、またはこれらのブロックが逆の順序で実行されることもある。また、ブロック図またはフローチャート説明あるいはその両方の各ブロック、および、ブロック図またはフローチャート説明あるいはその両方の中のブロックの組合せは、指定される機能もしくは行為を実行するかまたは専用ハードウェアとコンピュータ命令との組合せを実行する、専用ハードウェアベースのシステムによって実現できることにも留意されるであろう。
【符号の説明】
【００７９】
３０１  可変スライディング・ウィンドウ分割器
３０１Ａ  計算器
３０１Ｂ  最適化エンジン、最適化器
３０３  マップ・マッチング器
６０１  軌跡
６０３  軌跡
６０５  軌跡
６０７  軌跡
１２００  マップ
１５００  不確実性ベースの交通渋滞指標を生成するためのシステム
１５０１  取得要素
１５０３  分割要素
１５０５  実行要素
１５０７  計算要素
１５０９  生成要素
１５１１  出力要素
１６００  コンピューティング・システム
１６１１  プロセッサ、中央処理装置（ＣＰＵ）
１６１２  システム・バス
１６１４  ランダム・アクセス・メモリ（ＲＡＭ）
１６１６  読取専用メモリ（ＲＯＭ）
１６１８  入出力（Ｉ／Ｏ）アダプタ
１６２１  ディスク・ユニット
１６２２  ユーザ・インタフェース・アダプタ
１６２４  キーボード
１６２６  マウス
１６２８  スピーカ
１６３２  マイクロフォン
１６３４  通信アダプタ
１６３６  ディスプレイ・アダプタ
１６３８  ディスプレイ・デバイス
１６３９  プリンタ
１６４０  テープ・ドライブ
１７００  １台のプローブ車両
１７０１Ａ  心理的ギャップ
１７０１Ｂ  心理的ギャップ
１７０１Ｃ  心理的ギャップ
１７０１Ｄ  心理的ギャップ
１７０１Ｅ  心理的ギャップ
１７０１Ｆ  心理的ギャップ
１７５０  多くのプローブ車両
１７６０Ａ  要因
１７６０Ｂ  要因
１７６０Ｃ  要因
１７６０Ｄ  要因
【図１】
2017111813.tif 000003
【図２】
2017111813.tif 000004
【図３】
2017111813.tif 000005
【図４】
2017111813.tif 000006
【図５】
2017111813.tif 000007
【図６】
2017111813.tif 000008
【図７】
2017111813.tif 000009
【図８】
2017111813.tif 000010
【図９】
2017111813.tif 000011
【図１０】
2017111813.tif 000012
【図１１】
2017111813.tif 000013
【図１２】
2017111813.tif 000014
【図１３】
2017111813.tif 000015
【図１４】
2017111813.tif 000016
【図１５】
2017111813.tif 000017
【図１６】
2017111813.tif 000018
【図１７】
2017111813.tif 000019
【図１８】
2017111813.tif 000020
【図１９】
2017111813.tif 000021
【図２０】
2017111813.tif 000022
【図２１】
2017111813.tif 000023
【図２２】
2017111813.tif 000024
【図２３】
2017111813.tif 000025
【図２４】
2017111813.tif 000026
【図２５】
2017111813.tif 000027
【図２６】
2017111813.tif 000028
【図２７】
2017111813.tif 000029
【図２８】
2017111813.tif 000030
【図２９】
2017111813.tif 000031