(57)【特許請求の範囲】
【請求項１】
コンピュータに、
複数の位置情報をそれぞれが含む複数の軌跡情報を記憶する第１の記憶部を参照して、前記複数の軌跡情報のうちの何れかの軌跡情報を取得し、
それぞれが位置を示す複数のノードと、それぞれが前記複数のノード間を連結する複数のエッジとをそれぞれが含む一又は複数の平面グラフを記憶する第２の記憶部を参照して、前記一又は複数の平面グラフのうちの何れかの平面グラフを取得し、
取得した前記何れかの平面グラフと、取得した前記何れかの軌跡情報に含まれる複数の位置情報とに基づき、前記何れかの平面グラフに対してエッジの追加及び消去を行った他の平面グラフを生成し、
前記第１の記憶部に記憶された前記複数の軌跡情報のうち、前記何れかの平面グラフと、前記他の平面グラフとの差分部分を通過する他の軌跡情報を抽出し、
前記他の平面グラフから該他の平面グラフに含まれる何れかのエッジを除外した候補グラフ毎に、取得した前記軌跡情報と、抽出した前記他の軌跡情報とのそれぞれを対応付けた際の該候補グラフの最適度を算出し、
算出した前記最適度に基づき、何れかの候補グラフを出力する
ことを含む処理を実行させる経路グラフ生成方法。
【請求項２】
前記最適度は、前記取得した軌跡情報及び前記抽出した他の軌跡情報の各々を、前記他の平面グラフに対応付けた際に通過するエッジ毎に、該エッジを通過禁止とした前記他の平面グラフに、前記取得した軌跡情報及び前記抽出した他の軌跡情報の各々を再度対応付けた際に通過しないエッジを、前記他の平面グラフから除外した候補グラフ毎に算出される請求項１記載の経路グラフ生成方法。
【請求項３】
前記他の平面グラフとして、前記何れかの平面グラフに含まれる複数のノード、及び前記取得した軌跡情報に含まれる複数の位置情報の各々をドロネー点とするドロネーグラフを生成する請求項１又は請求項２記載の経路グラフ生成方法。
【請求項４】
前記最適度は、前記候補グラフの複雑度と、前記取得した軌跡情報及び前記抽出した他の軌跡情報の各々と前記候補グラフとの非類似度とを用いて表される請求項１〜請求項３のいずれか１項記載の経路グラフ生成方法。
【請求項５】
前記最適度は、エッジを除外する前後における前記複雑度の差と、前記非類似度の差とを用いて表される請求項４記載の経路グラフ生成方法。
【請求項６】
前記候補グラフの最適度を算出する際、前記取得した軌跡情報及び前記抽出した他の軌跡情報のいずれか１つの軌跡情報を再度対応付ける毎に前記最適度を算出し、算出された最適度が、前記複雑度の差が前記非類似度の差より大きい場合には、残りの軌跡情報を再度対応付けることなく、該候補グラフを候補から除外する請求項５記載の経路グラフ生成方法。
【請求項７】
複数の位置情報をそれぞれが含む複数の軌跡情報を記憶する第１の記憶部を参照して、前記複数の軌跡情報のうちの何れかの軌跡情報を取得する軌跡情報取得部と、
それぞれが位置を示す複数のノードと、それぞれが前記複数のノード間を連結する複数のエッジとをそれぞれが含む一又は複数の平面グラフを記憶する第２の記憶部を参照して、前記一又は複数の平面グラフのうちの何れかの平面グラフを取得する平面グラフ取得部と、
取得した前記何れかの平面グラフと、取得した前記何れかの軌跡情報に含まれる複数の位置情報とに基づき、前記何れかの平面グラフに対してエッジの追加及び消去を行った他の平面グラフを生成する生成部と、
前記第１の記憶部に記憶された前記複数の軌跡情報のうち、前記何れかの平面グラフと、前記他の平面グラフとの差分部分を通過する他の軌跡情報を抽出する抽出部と、
前記他の平面グラフから該他の平面グラフに含まれる何れかのエッジを除外した候補グラフ毎に、取得した前記軌跡情報と、抽出した前記他の軌跡情報とのそれぞれを対応付けた際の該候補グラフの最適度を算出する算出部と、
算出した前記最適度に基づき、何れかの候補グラフを出力する出力部と、
を含む経路グラフ生成装置。
【請求項８】
コンピュータに、
複数の位置情報をそれぞれが含む複数の軌跡情報を記憶する第１の記憶部を参照して、前記複数の軌跡情報のうちの何れかの軌跡情報を取得し、
それぞれが位置を示す複数のノードと、それぞれが前記複数のノード間を連結する複数のエッジとをそれぞれが含む一又は複数の平面グラフを記憶する第２の記憶部を参照して、前記一又は複数の平面グラフのうちの何れかの平面グラフを取得し、
取得した前記何れかの平面グラフと、取得した前記何れかの軌跡情報に含まれる複数の位置情報とに基づき、前記何れかの平面グラフに対してエッジの追加及び消去を行った他の平面グラフを生成し、
前記第１の記憶部に記憶された前記複数の軌跡情報のうち、前記何れかの平面グラフと、前記他の平面グラフとの差分部分を通過する他の軌跡情報を抽出し、
前記他の平面グラフから該他の平面グラフに含まれる何れかのエッジを除外した候補グラフ毎に、取得した前記軌跡情報と、抽出した前記他の軌跡情報とのそれぞれを対応付けた際の該候補グラフの最適度を算出し、
算出した前記最適度に基づき、何れかの候補グラフを出力する
ことを含む処理を実行させる経路グラフ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路グラフ生成方法、経路グラフ生成装置、及び経路グラフ生成プログラムに関する。
【背景技術】
【０００２】
ＧＰＳ（Global Positioning System）等のセンサで収集した移動体の軌跡データの分析にあたり、軌跡データから経路グラフを生成する技術が開示されている。
【０００３】
例えば、ＧＰＳにより取得された軌跡データを、その軌跡データが示す移動体の移動の方向が近しい区間に分割してベクトルで代表させる方法が提案されている。この方法では、類似度を用いてベクトルを密度に基づきクラスタリングし、クラスタを代表するベクトルを接続することにより、グラフ構造を抽出している。
【０００４】
また、グラフと軌跡との非類似性と、グラフの複雑さとを考慮したコストを最小化するように、軌跡データをＦｒｅｃｈｅｔ距離などに基づいてグラフと対応付け、対応付かない部分をグラフに追加する方法が提案されている。この方法では、空のグラフからスタートし、全ての軌跡データについて１回ずつこの処理を行うことで、経路グラフを生成する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１５−７６０６９号公報
【非特許文献】
【０００６】
【非特許文献１】Jae-Gil Lee, Jiawei Han, Kyu-Young Whang, "Trajectory Clustering: A Partition-and-Group Framework", SIGMOD '07, ２００７年６月
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、軌跡データを分割したベクトルのクラスタリングによりグラフ構造を抽出する方法は、バッチ処理であるため、例えば、人や車などの流れを即時に反映するようなオンライン処理に適用することができない。
【０００８】
また、軌跡データを１本ずつ経路グラフに追加する方法では、コスト（最適度）を最適化するように、次に追加する軌跡データを選択している。したがって、この方法は、コストを十分に最適化するためには、追加する軌跡データの順番を考慮する必要があるため、追加する順番を考慮できないオンライン処理には適用することができない。
【０００９】
本発明は、一つの側面として、最適度が最適となる経路グラフをオンライン処理で生成することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、一つの態様として、複数の位置情報をそれぞれが含む複数の軌跡情報を記憶する第１の記憶部を参照して、前記複数の軌跡情報のうちの何れかの軌跡情報を取得する。それぞれが位置を示す複数のノードと、それぞれが前記複数のノード間を連結する複数のエッジとをそれぞれが含む一又は複数の平面グラフを記憶する第２の記憶部を参照して、前記一又は複数の平面グラフのうちの何れかの平面グラフを取得する。取得した前記何れかの平面グラフと、取得した前記何れかの軌跡情報に含まれる複数の位置情報とに基づき、前記何れかの平面グラフに対してエッジの追加及び消去を行った他の平面グラフを生成する。前記第１の記憶部に記憶された前記複数の軌跡情報のうち、前記何れかの平面グラフと、前記他の平面グラフとの差分部分を通過する他の軌跡情報を抽出する。前記他の平面グラフから該他の平面グラフに含まれる何れかのエッジを除外した候補グラフ毎に、取得した前記軌跡情報と、抽出した前記他の軌跡情報とのそれぞれを対応付けた際の該候補グラフの最適度を算出する。算出した前記最適度に基づき、何れかの候補グラフを出力する。
【発明の効果】
【００１１】
一つの側面として、最適度が最適となる経路グラフをオンライン処理で生成することができる、という効果を有する。
【図面の簡単な説明】
【００１２】
【図１】本実施形態に係る経路グラフ生成装置の概略構成を示す機能ブロック図である。
【図２】軌跡データのデータ構造の一例を示す図である。
【図３】経路グラフデータベースの一例を示す図である。
【図４】ΔＧの特定を説明するための図である。
【図５】ΔＧの特定を説明するための図である。
【図６】経路グラフ生成装置として機能するコンピュータの概略構成を示すブロック図である。
【図７】本実施形態における経路グラフ生成処理の一例を示すフローチャートである。
【図８】経路グラフ更新処理の一例を示すフローチャートである
【図９】ループ１における管理データベースの一例を示す図である。
【図１０】経路グラフＧ（０．５）の一例を示す図である。
【図１１】経路グラフＧ（１．５）の一例を示す図である。
【図１２】ループ２における管理データベースの一例を示す図である。
【図１３】経路グラフＧ（２．５）の一例を示す図である。
【図１４】ループ３における管理データベースの一例を示す図である。
【図１５】経路グラフＧ（３．５）の一例を示す図である。
【図１６】ループ４における管理データベースの一例を示す図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照して、本発明に関する実施形態の一例を詳細に説明する。
【００１４】
図１に示すように、本実施形態に係る経路グラフ生成装置１０は、入力として軌跡データ２１を受け付ける。経路グラフ生成装置１０は、経路グラフデータベース（ＤＢ）２２に記憶された経路グラフＧを、受け付けた軌跡データ２１を用いて更新することにより、新たな経路グラフＧを生成する。
【００１５】
軌跡データ２１は、所定時間間隔でＧＰＳ（Global Positioning System）等のセンサにより観測された移動体の位置を示す観測データの系列であり、移動体が移動した軌跡を表すデータである。
【００１６】
観測データには、センサを識別するセンサＩＤと、観測された位置毎の緯度及び経度で示される位置データ（ｘ座標及びｙ座標）と、観測時刻とが含まれる。軌跡データ２１は、複数の観測データをセンサＩＤ毎に抽出し、各観測データに含まれる観測点を、観測時刻に基づいて時系列に並べたものである。なお、センサＩＤが同一であっても、観測点間の観測時刻が所定時間以上離れている場合には、その箇所で軌跡データを分割する。この場合、センサＩＤに通し番号を付加するなどして、軌跡データを一意に識別可能な軌跡ＩＤを、軌跡データ毎に付与する。以下では、軌跡ＩＤがαｉの軌跡データ２１を、「軌跡データαｉ」、軌跡データαｉが表す軌跡を「軌跡αｉ」とも表記する。
【００１７】
例えば、軌跡データαｉに含まれる観測点が、Ｐｉ１、Ｐｉ２、・・・、Ｐｉｊ、・・・、ＰｉＪ（Ｊは軌跡データαｉに含まれる観測点の数）であるとする。この場合、軌跡データαｉは、αｉ＝｛Ｐｉ１，Ｐｉ２，・・・，Ｐｉｊ，・・・，ＰｉＪ｝と表すことができる。また、各観測点を示す観測データには、その観測点を含む軌跡データ２１の軌跡ＩＤと、観測点の識別情報である観測点ＩＤと、位置データ（ｘ座標及びｙ座標）と、観測時刻とが含まれる。例えば、軌跡データαｉに含まれる観測点Ｐｉｊの観測データは、Ｐｉｊ＝｛αｉ，Ｐｉｊ，（ｘｉｊ，ｙｉｊ），ｓｉｊ｝と表すことができる。なお、（ｘｉｊ，ｙｉｊ）は、観測点Ｐｉｊの位置データ、ｓｉｊは、観測点Ｐｉｊの観測時刻である。図２に、軌跡データ２１をテーブル形式のデータ構造で表現した一例を示す。
【００１８】
経路グラフＧは、それぞれが位置情報を表す複数のノードと、ノード間を連結するエッジとで表される。経路グラフＤＢ２２には、例えば、図３に示すように、経路グラフＧに含まれるノードを示すノード情報の集合と、エッジを示すエッジ情報の集合とが含まれる。ノード情報は、例えば、各ノードの識別情報（ノードＩＤ）と、各ノードの位置データ（ｘ座標及びｙ座標）とを含む。また、エッジ情報は、各エッジの識別情報（エッジＩＤ）と、そのエッジで連結されているノードのノードＩＤを「＿（アンダーバー）」で接続した表記で表される連結ノードの情報とを含む。以下では、エッジＩＤがｅｉのエッジを「エッジｅｉ」とも表記する。
【００１９】
ここで、本実施形態では、コストが最適となる経路グラフＧをオンライン処理で生成することを目的とする。そこで、まず、軌跡データ集合Ｔを追加することにより生成される経路グラフＧのコストとして、下記（１）式のコストｃｏｓｔＴ（Ｇ）を定義し、この（１）式のコストｃｏｓｔＴ（Ｇ）を最小化するように、経路グラフＧを生成することを考える。
【００２０】
ｃｏｓｔＴ（Ｇ）＝Σα∈Ｔδα（Ｇ）＋λ｜Ｇ｜                （１）
【００２１】
ただし、λは、λ＞０の定数、｜Ｇ｜は、経路グラフＧの複雑度、及びδα（Ｇ）は、経路グラフＧと軌跡αとの非類似度である。経路グラフＧの複雑度は、例えば、経路グラフＧに含まれるノード数、エッジ数、エッジ長の和などとすることができる。非類似度δα（Ｇ）は、例えば、Ｆｒｅｃｈｅｔ距離などとすることができる。
【００２２】
上述したように、軌跡データを１本ずつ経路グラフに追加する方法では、追加する軌跡データの順番を考慮しない場合に、コストを十分に最適化することができない。そこで、軌跡データを追加する毎に、生成済みの経路グラフを生成する際に利用した軌跡データも合わせて、全ての軌跡データを用いたバッチ処理により、コストを最適化するように経路グラフを生成することも考えられる。しかし、データ規模が大きな場合などには、最適解の候補となるグラフが多数存在するため、経路グラフの生成に要する計算量が増大する。
【００２３】
このような計算量の増大を抑制するために、局所最適解を求めるための手法である最急降下法を、経路グラフＧのコストの最適化に適用する。最急降下法では、下記（２）式を、解ｘ（ｉ）が収束するまで反復する。ただし、ηは定数とする。
【００２４】
ｘ（ｉ＋１）＝ｘ（ｉ）−η∇ｆ（ｘ（ｉ））                          （２）
【００２５】
（２）式を経路グラフＧのコストの最適化に適用した場合、ｘ＝Ｇ＝（Ｖ，Ｅ）である。Ｖは、経路グラフＧに含まれるノードｖの集合、Ｅは、経路グラフＧに含まれるエッジｅの集合である。また、（２）式を経路グラフＧのコストの最適化に適用した場合、ｆ（ｘ）＝ｃｏｓｔＴ（Ｇ）である。ところが、経路グラフＧは高次元の離散値ベクトルであるため、微分である∇ｃｏｓｔＴ（Ｇ）を定義することができない。
【００２６】
そこで、本実施形態では、微分の代わりに、下記（３）式で定義される差分ΔｃｏｓｔＴ，Ｇ（ΔＧ）に基づいてΔＧを選択し、Ｇ←Ｇ−ΔＧのように更新することで、局所最適解を得る。
【００２７】
ΔｃｏｓｔＴ，Ｇ（ΔＧ）＝
｛（Σα∈Ｔδα（Ｇ−ΔＧ）＋λ｜Ｇ−ΔＧ｜）−（Σα∈Ｔδα（Ｇ）＋λ｜Ｇ｜）｝
＝Σα∈Ｔ［δα（Ｇ−ΔＧ）−δα（Ｇ）］−λ［｜Ｇ｜−｜Ｇ−ΔＧ｜］
（３）
【００２８】
最急降下法を経路グラフＧのコストの最適化に適用する方法を具体的に説明する。まず、初期解となる経路グラフＧ（０）を設定する。例えば、経路グラフＧと軌跡との非類似度Σα∈Ｔδα（Ｇ）を最少にする経路グラフＧ（０）＝（Ｖ（０），Ｅ（０））を初期解とすることができる。
【００２９】
次に、経路グラフＧ（０）の部分グラフであるＧ（ｉ）＝（Ｖ（ｉ），Ｅ（ｉ））に含まれるエッジｅを通過する軌跡データα∈Ｔｅを、エッジｅを通過禁止にした経路グラフＧ（ｉ）＼｛ｅ｝にマップマッチングさせる。以下では、エッジｅを通過する軌跡データを、エッジｅを通過禁止に設定した経路グラフにマップマッチングさせることを、「リルート」ともいう。このリルートの結果、１本以上の軌跡が通過するエッジのみを残して得られた経路グラフをＧ−ΔＧとする。
【００３０】
例えば、図４に示すように、エッジｅ１、ｅ２、ｅ３、ｅ４、ｅ５、ｅ６、ｅ７、ｅ８、ｅ９を含む部分経路グラフＧ（ｉ）において、エッジｅ８を通過禁止に設定する。エッジｅ８を通過する軌跡は、軌跡α１及びα２であるとする。軌跡α１を経路グラフＧ（ｉ）にマップマッチングしたルートは、エッジｅ１→ｅ６→ｅ７→ｅ８→ｅ５、軌跡α２を経路グラフＧ（ｉ）にマップマッチングしたルートは、エッジｅ１→ｅ２→ｅ９→ｅ８→ｅ５であるとする。エッジｅ８を通過禁止に設定した経路グラフＧ（ｉ）＼｛ｅ８｝に軌跡α１及びα２をリルートすると、図５に示すように、両軌跡とも、エッジｅ１→ｅ２→ｅ３→ｅ４→ｅ５のようにリルートされたとする。この場合、経路グラフＧ（ｉ）に含まれるエッジのうち、リルートされた軌跡α１及びα２の１本以上の軌跡が通過するエッジのみを残して得られたグラフ（Ｇ（ｉ）−ΔＧ）は、｛ｅ１，ｅ２，ｅ３，ｅ４，ｅ５｝である。従って、ΔＧ＝｛ｅ６，ｅ７，ｅ８，ｅ９｝である。
【００３１】
このようにして、全てのｅ∈Ｅ（ｉ）についてΔＧが定まる。また、エッジｅを通過する軌跡を表す軌跡データの集合をＴｅとする。このようなΔＧの候補のうち、コストが所定の条件を満たすΔＧを選択する。所定の条件としては、例えば、以下のようなものを定めておくことができる。
【００３２】
（１）ΔｃｏｓｔＴ，Ｇ（ΔＧ）＜０、かつΔｃｏｓｔＴ，Ｇ（ΔＧ）が最少
（２）ΔｃｏｓｔＴ，Ｇ（ΔＧ）＜０、かつ｜ｅ｜が最大（又は最少）
（３）ΔｃｏｓｔＴ，Ｇ（ΔＧ）＜０、かつ｜Ｔｅ｜が最少（又は最大）
（４）ΔｃｏｓｔＴ，Ｇ（ΔＧ）＜０、かつ｜Ｔｅ｜−γ｜ｅ｜が最少
（ただしγ＞０は定数）
【００３３】
各条件の「ΔｃｏｓｔＴ，Ｇ（ΔＧ）＜０」は、｜ΔＧ｜に比べ、軌跡データとグラフ（Ｇ−ΔＧ）との非類似度が小さいことを示す。
【００３４】
なお、通過禁止に設定するエッジｅ∈Ｅ（ｉ）に対するΔＧ及びδα（Ｇ−ΔＧ）の算出にはマップマッチングが必要であり、マップマッチングの計算量は一般に大きい。本実施形態では、α∈Ｔ−Ｔｅに対してはδα（Ｇ−ΔＧ）＝δα（Ｇ）であるため、下記（４）式が得られる。
【００３５】
ΔｃｏｓｔＴ，Ｇ（ΔＧ）＝
Σα∈Ｔ［δα（Ｇ−ΔＧ）−δα（Ｇ）］−λ［｜Ｇ｜−｜Ｇ−ΔＧ｜］
＝Σα∈Ｔｅ［δα（Ｇ−ΔＧ）−δα（Ｇ）］
＋Σα∈Ｔ−Ｔｅ［δα（Ｇ−ΔＧ）−δα（Ｇ）］−λ［｜Ｇ｜−｜Ｇ−ΔＧ｜］
＝Σα∈Ｔｅ［δα（Ｇ−ΔＧ）−δα（Ｇ）］−λ［｜Ｇ｜−｜Ｇ−ΔＧ｜］
（４）
【００３６】
したがって、軌跡データα∈Ｔを全てマップマッチングすることなく、通過禁止に設定するエッジを通過する軌跡データα∈Ｔｅのマップマッチングのみで、ΔｃｏｓｔＴ，Ｇ（ΔＧ）を算出することができる。軌跡データの集合Ｔｅは、集合Ｔに比べてとても小さいため、大幅にマップマッチングの回数を減らすことができる。
【００３７】
ここまで説明してきた最急降下法を適用した経路グラフのコストの最適化を、オンライン処理へ拡張する。
【００３８】
生成済みの経路グラフに軌跡データを追加した場合、上記の初期解となる経路グラフＧ（０）は変更されるため、全ての軌跡データを対象に、上記の手順をやりなおす必要があるとも考えられる。しかし、生成済みの経路グラフと、軌跡データを追加した後のグラフとの差分に対して、上記の手順や適用することで、オンライン処理により、コストを最適化する経路グラフを生成することができる。
【００３９】
例えば、軌跡データの観測点をドロネー点とするドロネーグラフから経路グラフを生成する場合を考える。観測点を追加する前のドロネーグラフをＤ（ｉ）＝（Ｕ（ｉ），Ｆ（ｉ））、観測点を追加した後のドロネーグラフをＤ（ｉ＋１）＝（Ｕ（ｉ＋１），Ｆ（ｉ＋１））とする。なお、Ｕは、ドロネーグラフに含まれるノード（ドロネー点）の集合、Ｆは、ドロネーグラフに含まれるエッジ（ドロネー辺）の集合である。｜Ｆ（ｉ）∩Ｆ（ｉ＋１）｜／｜Ｆ（ｉ）｜は小さくないため、Ｄ（ｉ）とＤ（ｉ＋１）との差分に着目することで、バッチ処理のように計算量を増大させることなく、オンライン処理で経路グラフＧを生成することができる。
【００４０】
具体的には、Ｆ（−）＝Ｆ（ｉ）＼Ｆ（ｉ＋１）とすると、経路グラフＧ（ｉ）の生成に用いた軌跡データが表す軌跡のうち、Ｅ（−）＝Ｅ（ｉ）∩Ｆ（−）を通過する軌跡と、追加する軌跡データが表す軌跡とを、ドロネーグラフＤ（ｉ＋１）にリルートするだけでよい。Ｆ（−）は、ドロネーグラフＤ（ｉ）の双対となるボロノイ図における各ボロノイ領域において、追加する軌跡データの観測点が含まれるボロノイ領域の母点を端点とするエッジの部分集合となる。ドロネーグラフＤ（ｉ＋１）も、追加する軌跡データの観測点が含まれるボロノイ領域の母点数に比例する計算量で求めることができる。この母点数は、追加する観測点数を上回ることはないため、Ｄ（ｉ＋１）を、追加する観測点数に比例する計算量で求めることができる。
【００４１】
以上のことから、追加する観測点に比例した計算量で、コストを最適化する経路グラフを生成することができるため、オンライン処理での経路グラフの生成が可能になる。
【００４２】
本実施形態では、上述したように、最急降下法を定式化し、オンライン処理に拡張した手法により、経路グラフＧを生成する。以下、本実施形態に係る経路グラフ生成装置１０の各機能部について詳述する。
【００４３】
経路グラフ生成装置１０は、図１に示すように、取得部１１と、平面グラフ生成部１２と、抽出部１３と、算出部１４と、経路グラフ生成部１５とを含む。また、経路グラフ生成装置１０の所定の記憶領域には、経路グラフＤＢ２２と、ドロネーグラフＤＢ２３と、管理ＤＢ２４とが記憶される。
【００４４】
経路グラフＤＢ２２には、上述したような経路グラフＧの情報（例えば、図３）が記憶される。ドロネーグラフＤＢ２３には、平面グラフ生成部１２で生成されたドロネーグラフＤの情報が記憶される。ドロネーグラフＤのデータ構造は、経路グラフＧのデータ構造と同様に、複数のノード（ドロネー点）情報と複数のエッジ（ドロネー辺）情報とを含む。管理ＤＢ２４には、算出部１４におけるコストの計算、及び経路グラフ生成部１５における経路グラフＧの生成に必要な軌跡データの情報が記憶される。
【００４５】
取得部１１は、例えば、移動体から取得したＧＰＳなどの観測データから軌跡データを生成する軌跡データ生成装置３０から、軌跡データ２１を１つずつ取得する。取得部１１は、軌跡データ２１を軌跡データ生成装置３０から取得する場合に限らず、他の情報処理装置、外部の記憶装置、内部の記憶装置などから取得してもよい。また、移動体に搭載又は保持されるカーナビゲーションシステムやスマートフォン等の情報処理装置が、観測データから軌跡データを生成する機能を有する場合には、移動体に搭載又は保持される情報処理装置から直接軌跡データを取得してもよい。取得部１１は、取得した軌跡データ２１を、平面グラフ生成部１２へ受け渡す。
【００４６】
平面グラフ生成部１２は、ドロネーグラフＤＢ２３から、前回生成したドロネーグラフＤ（ｔ−１）を読み込み、ドロネーグラフＤ（ｔ−１）に、取得部１１から受け渡された軌跡データ２１に含まれる観測点を追加し、ドロネーグラフＤ（ｔ）を生成する。平面グラフ生成部１２は、生成したドロネーグラフＤ（ｔ）を、ドロネーグラフＤＢ２３に記憶すると共に、取得部１１から受け渡された軌跡データ２１を、抽出部１３に受け渡す。
【００４７】
抽出部１３は、ドロネーグラフＤＢ２３に記憶されたドロネーグラフＤ（ｔ−１）と、ドロネーグラフＤ（ｔ）との差分を、経路グラフＧ（ｔ−１）に反映した経路グラフＧ（ｔ−１／２）を生成する。この際、抽出部１３は、ドロネーグラフＤ（ｔ−１）に含まれるエッジ集合Ｆ（ｔ−１）のうち、ドロネーグラフＤ（ｔ）から消去されたエッジ集合Ｆ（−）を特定する。そして、抽出部１３は、管理ＤＢ２４に記憶された軌跡データから、エッジ集合Ｆ（−）のいずれかのエッジを通過する軌跡データを抽出する。抽出部１３は、抽出した軌跡データと、取得部１１から受け渡された軌跡データ２１と、生成した経路グラフＧ（ｔ−１／２）とを、算出部１４へ受け渡す。
【００４８】
算出部１４は、抽出部１３から受け渡された軌跡データの各々が表す軌跡の各々を経路グラフＧ（ｔ−１／２）にマップマッチングした際に通過するエッジｅの各々を通行禁止に設定した経路グラフＧ（ｔ−１／２）＼｛ｅ｝に、軌跡の各々をリルートする。そして、算出部１４は、リルートの結果、いずれの軌跡も通過しない部分をΔＧとし、経路グラフＧ（ｔ）の候補である経路グラフ（Ｇ（ｔ−１／２）−ΔＧ）についてのコストを、（４）式により算出する。
【００４９】
経路グラフ生成部１５は、算出部１４により算出されたコストが所定の条件を満たすΔＧを特定し、経路グラフＧ（ｔ−１／２）から、ΔＧに含まれるエッジを除外することで、経路グラフＧ（ｔ）を生成する。
【００５０】
経路グラフ生成装置１０は、例えば、図６に示すコンピュータ４０で実現することができる。コンピュータ４０はＣＰＵ４１、一時記憶領域としてのメモリ４２、及び不揮発性の記憶部４３を備える。また、コンピュータ４０は、表示装置及び入力装置等の入出力装置４４を備える。また、コンピュータ４０は、記録媒体４９に対するデータの読み込みと書き込みとを制御するｒｅａｄ／ｗｒｉｔｅ（Ｒ／Ｗ）部４５、及びインターネット等のネットワークに接続されるネットワークＩ／Ｆ４６を備える。ＣＰＵ４１、メモリ４２、記憶部４３、入出力装置４４、Ｒ／Ｗ部４５、及びネットワークＩ／Ｆ４６は、バス４７を介して互いに接続される。
【００５１】
記憶部４３は、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（solid state drive）、フラッシュメモリ等によって実現できる。記憶媒体としての記憶部４３には、コンピュータ４０を経路グラフ生成装置１０として機能させるための経路グラフ生成プログラム５０が記憶される。経路グラフ生成プログラム５０は、取得プロセス５１と、平面グラフ生成プロセス５２と、抽出プロセス５３と、算出プロセス５４と、経路グラフ生成プロセス５５とを有する。また、記憶部４３は、経路グラフＤＢ２２を構成する情報、ドロネーグラフＤＢ２３を構成する情報、管理ＤＢ２４を構成する情報等が記憶されるデータ記憶領域６０を有する。
【００５２】
ＣＰＵ４１は、経路グラフ生成プログラム５０を記憶部４３から読み出してメモリ４２に展開し、経路グラフ生成プログラム５０が有するプロセスを順次実行する。また、ＣＰＵ４１は、データ記憶領域６０に記憶された情報を読み出し、経路グラフＤＢ２２、ドロネーグラフＤＢ２３、及び管理ＤＢ２４の各々をメモリ４２に展開する。
【００５３】
ＣＰＵ４１は、取得プロセス５１を実行することで、図１に示す取得部１１として動作する。また、ＣＰＵ４１は、平面グラフ生成プロセス５２を実行することで、図１に示す平面グラフ生成部１２として動作する。また、ＣＰＵ４１は、抽出プロセス５３を実行することで、図１に示す抽出部１３として動作する。また、ＣＰＵ４１は、算出プロセス５４を実行することで、図１に示す算出部１４として動作する。また、ＣＰＵ４１は、経路グラフ生成プロセス５５を実行することで、図１に示す経路グラフ生成部１５として動作する。これにより、経路グラフ生成プログラム５０を実行したコンピュータ４０が、経路グラフ生成装置１０として機能することになる。
【００５４】
なお、経路グラフ生成プログラム５０により実現される機能は、例えば半導体集積回路、より詳しくはＡＳＩＣ（Application Specific Integrated Circuit）等で実現することも可能である。
【００５５】
次に、本実施形態に係る経路グラフ生成装置１０の作用について説明する。経路グラフ生成装置１０に軌跡データ２１が入力されると、経路グラフ生成装置１０において、図７に示す経路グラフ生成処理が実行される。なお、経路グラフ生成装置１０に入力された軌跡データ２１は、一旦所定の記憶領域に記憶されるものとする。
【００５６】
図７に示す経路グラフ生成処理のステップＳ１０で、取得部１１が、経路グラフＧを生成するために取得された何個目の軌跡データかを示す変数ｔを初期値の「１」に設定する。また、取得部１１が、平面グラフ生成部１２で生成するドロネーグラフの初期値として、空のグラフを設定する。このドロネーグラフをＤ（０）＝（Ｕ（０），Ｆ（０））＝（φ，φ）とする。上述した通り、Ｕは、ドロネーグラフに含まれるノード（ドロネー点）の集合、Ｆは、ドロネーグラフに含まれるエッジ（ドロネー辺）の集合である。さらに、取得部１１が、経路グラフ生成部１５で生成する経路グラフの初期値として、空のグラフを設定する。この経路グラフをＧ（０）＝（Ｖ（０），Ｅ（０））＝（φ，φ）とする。上述した通り、Ｖは、経路グラフに含まれるノードの集合、Ｅは、経路グラフに含まれるエッジの集合である。
【００５７】
次に、ステップＳ１５で、取得部１１が、所定の記憶領域から、経路グラフ生成装置１０に入力された軌跡データα（ｔ）を読み込む。取得部１１は、読み込んだ軌跡データ２１を、平面グラフ生成部１２へ受け渡す。
【００５８】
次に、ステップＳ２０で、平面グラフ生成部１２が、ドロネーグラフＤＢ２３から、前回生成したドロネーグラフＤ（ｔ−１）を読み込み、ドロネーグラフＤ（ｔ−１）に、取得部１１から受け渡された軌跡データα（ｔ）に含まれる観測点を追加し、ドロネーグラフＤ（ｔ）を生成する。具体的には、平面グラフ生成部１２は、ドロネーグラフＤ（ｔ−１）のノード集合Ｕ（ｔ−１）の各ノードを母点とするボロノイ領域であって、軌跡データα（ｔ）の観測点が追加されたボロノイ領域の母点を端点とするエッジを消去する。この消去されるエッジ集合をＦ（−）と表記する。すなわち、Ｆ（−）＝Ｆ（ｔ−１）−Ｆ（ｔ）である。
【００５９】
そして、平面グラフ生成部１２は、追加された軌跡データα（ｔ）の各観測点ｖｉ（ｉ＝１，２，・・・，Ｉ、Ｉは軌跡データα（ｔ）に含まれる観測点の総数）に基づいて、新たなノード集合Ｕ（＋）を生成する。なお、Ｕ（＋）＝Ｕ（ｔ）−Ｕ（ｔ−１）である。また、平面グラフ生成部１２は、新たなノード集合Ｕ（＋）及び消去したエッジ集合Ｆ（−）に基づいて、新たなエッジ集合Ｆ（＋）を生成する。なお、Ｆ（＋）＝Ｆ（ｔ）−Ｆ（ｔ−１）である。これにより、ドロネーグラフＤ（ｔ）＝（Ｕ（ｔ），Ｆ（ｔ））が生成される。
【００６０】
次に、ステップＳ２５で、平面グラフ生成部１２が、生成したドロネーグラフＤ（ｔ）を、ドロネーグラフＤＢ２３に記憶すると共に、取得部１１から受け渡された軌跡データ２１を、抽出部１３に受け渡す。抽出部１３は、ドロネーグラフＤＢ２３に記憶されたドロネーグラフＤ（ｔ−１）と、ドロネーグラフＤ（ｔ）との差分を、経路グラフＧ（ｔ−１）に反映した経路グラフＧ（ｔ−１／２）を生成する。具体的には、抽出部１３は、エッジ集合Ｅ（ｔ−１）からエッジ集合Ｆ（−）を除いたエッジ集合と、エッジ集合Ｆ（＋）との和集合をエッジ集合Ｅ（ｔ−１／２）とする経路グラフＧ（ｔ−１／２）＝（Ｖ（ｔ−１／２），Ｅ（ｔ−１／２））を生成する。
【００６１】
次に、ステップＳ３０で、抽出部１３が、管理ＤＢ２４に記憶された軌跡データ、すなわち経路グラフＧ（ｔ−１）の生成に用いられた軌跡データから、エッジ集合Ｆ（−）のいずれかのエッジｅを通過する軌跡データを抽出する。ここで抽出された軌跡データ集合をＴｅとする。
【００６２】
次に、ステップＳ３５で、抽出部１３が、軌跡データ集合Ｔｅに、軌跡データα（ｔ）を加えた軌跡データ集合Ｔと、生成した経路グラフＧ（ｔ−１／２）とを、算出部１４へ受け渡す。次に、ステップＳ４０で、経路グラフ更新処理が実行される。
【００６３】
ここで、図８を参照して、経路グラフ更新処理について説明する。
【００６４】
ステップＳ４１で、算出部１４が、経路グラフＧ（ｔ−１／２）を経路グラフＧに設定する。そして、算出部１４は、軌跡データ集合Ｔに含まれる軌跡データαの各々が表す軌跡αの各々を、経路グラフＧにマップマッチングしたルートπ＝＜ｅ（１），・・・，ｅ（Ｎ）＞を取得する。ｅ（１）は、軌跡αをマップマッチングした際の先頭のエッジであり、ｅ（Ｎ）は、末尾のエッジである。また、算出部１４は、軌跡αと経路グラフＧとの非類似度δα（Ｇ）を算出する。
【００６５】
次に、ステップＳ４２で、算出部１４が、軌跡αをマップマッチングした結果を、管理ＤＢ２４の軌跡管理表２４Ａ及びエッジ−軌跡テーブル２４Ｂに登録する。図９に軌跡管理表２４Ａ及びエッジ−軌跡テーブル２４Ｂの一例を示す。軌跡管理表２４Ａには、マップマッチングした軌跡αを表す軌跡データαの軌跡ＩＤと、マップマッチングにより得られたルートπと、非類似度δα（Ｇ）とが対応付けて記憶される。エッジ−軌跡テーブル２４Ｂは、経路グラフＧに含まれる各エッジと、そのエッジを通過する軌跡との対応関係を示すテーブルである。エッジ−軌跡テーブル２４Ｂには、各エッジｅのエッジＩＤと、そのエッジを通過する軌跡αを表す軌跡データαの軌跡ＩＤの集合（軌跡データ集合Ａ）とを対応付けた各エントリが記憶される。
【００６６】
次に、ステップＳ４３で、算出部１４が、エッジ−軌跡テーブル２４Ｂに、以降の処理が未処理のエントリが存在するか否かを判定する。未処理のエントリが存在する場合には、処理はステップＳ４４へ移行する。
【００６７】
ステップＳ４４では、算出部１４が、エッジ−軌跡テーブル２４Ｂ内の未処理のエントリのうち、軌跡データ集合のサイズが最小のエントリ（ｅ，Ａ）を抽出する。軌跡データ集合のサイズが最小とは、軌跡データ集合Ａに含まれる軌跡データの数、又は軌跡データの長さの和が最小の場合である。なお、本ステップの処理は、上述した、ΔＧを選択する際にコストが満たす所定の条件の「（３）ΔｃｏｓｔＴ，Ｇ（ΔＧ）＜０、かつ｜Ｔｅ｜が最少（又は最大）」に適応するための処理である。
【００６８】
次に、ステップＳ４５で、算出部１４が、抽出したエントリのエッジｅを通過する軌跡データ集合Ａに含まれる軌跡データの各々が表す軌跡が通過するエッジだけで構成された部分グラフを、ΔＧの初期値に設定する。
【００６９】
次に、ステップＳ４６で、算出部１４が、ワーク変数Δｅｒｒ及びΔｇｒａｐｈの各々を初期値に設定する。Δｅｒｒは、（４）式の第１項（Σα∈Ｔｅ［δα（Ｇ−ΔＧ）−δα（Ｇ）］）を求めるためのワーク変数であり、Δｇｒａｐｈは、（４）式の第２項（λ［｜Ｇ｜−｜Ｇ−ΔＧ｜］）を求めるためのワーク変数である。算出部１４は、Δｅｒｒ＝０、Δｇｒａｐｈ＝｜ΔＧ｜に設定する。｜ΔＧ｜は、ΔＧに含まれるエッジの長さの和である。
【００７０】
次に、ステップＳ４７で、算出部１４が、上記ステップＳ４４で抽出したエントリの軌跡データ集合Ａに、以降の処理が未処理の軌跡データが存在するか否かを判定する。未処理の軌跡データがある場合には、処理はステップＳ４８へ移行する。
【００７１】
ステップＳ４８では、算出部１４が、軌跡データ集合Ａから、未処理の軌跡データを１つ選択し、軌跡データαＡに設定する。
【００７２】
次に、ステップＳ４９で、算出部１４が、軌跡データαＡが表す軌跡αＡを、エッジｅを通過禁止に設定した経路グラフＧ＼｛ｅ｝にリルートしたルートπαＡ＝＜ｅ（１），・・・，ｅ（Ｍ）＞を取得する。また、算出部１４は、軌跡αＡとエッジｅを通過禁止に設定した経路グラフＧ＼｛ｅ｝との非類似度δαＡ（Ｇ＼｛ｅ｝）を算出する。
【００７３】
次に、ステップＳ５０で、算出部１４が、Δｅｒｒに、非類似度δαＡ（Ｇ＼｛ｅ｝）と、非類似度δαＡ（Ｇ）との差を加算する。算出部１４は、非類似度δαＡ（Ｇ）を、軌跡管理表２４Ａから取得する。また、算出部１４は、Δｇｒａｐｈから、ΔＧに含まれるエッジと、軌跡αＡをリルートしたルートπαＡに含まれるエッジとで共通するエッジの長さの和を減算する。さらに、算出部１４は、ΔＧから、ルートπαＡに含まれるエッジを除外する。
【００７４】
次に、ステップＳ５１で、算出部１４が、ΔｅｒｒがΔｇｒａｐｈより小さいか否かを判定する。Δｅｒｒ＜Δｇｒａｐｈの場合には、処理はステップＳ４７に戻り、Δｅｒｒ≧Δｇｒａｐｈの場合には、処理はステップＳ４３に戻る。
【００７５】
ここで、δα（Ｇ−ΔＧ）−δα（Ｇ）が常に非負となるようなマップマッチングを利用すれば、軌跡データ集合Ａに含まれる軌跡データが表す軌跡を順次リルートした場合、Δｅｒｒは単調増加する。なお、Ｆｒｅｃｈｅｔ距離最小とする方法をはじめ、適当なマップマッチングは、δα（Ｇ−ΔＧ）−δα（Ｇ）が常に非負となる。また、｜Ｇ｜−｜Ｇ−ΔＧ｜は、リルートによって軌跡が通過しなくなったエッジの長さの和であり、その上限値は｜ΔＧ｜である。また、軌跡を順次リルートする場合、先に設定されたΔＧ内を通過する軌跡があり得るため、Δｇｒａｐｈは単調減少する。すなわち、軌跡データ集合Ａに含まれるｋ番目の軌跡データαＡが表す軌跡αＡのリルートが完了したときに、Δｅｒｒ＜Δｇｒａｐｈが成り立たないならば、ｋ＋１番目以降の軌跡αＡをリルートしても、Δｅｒｒ＜Δｇｒａｐｈが成り立つことはない。
【００７６】
したがって、ステップＳ５１の判定により、軌跡データ集合Ａに含まれる残りの軌跡データαＡが表す軌跡αＡのリルートを継続するか否かを判定することで、計算量が多いリルート（マップマッチング）の処理回数を低減することができる。ステップＳ５１で否定判定された場合、処理中のエントリのエッジｅに対応する候補グラフ（Ｇ−ΔＧ）は、候補から除外されることになる。
【００７７】
ステップＳ４７で、軌跡データ集合Ａに、以降の処理が未処理の軌跡データが存在しないと判定された場合には、処理はステップＳ５２へ移行する。ステップＳ５２では、経路グラフ生成部１５が、経路グラフＧからΔＧを除外して経路グラフＧを更新すると共に、軌跡管理表２４Ａ及びエッジ−軌跡テーブル２４Ｂを更新して、処理はステップＳ４３に戻る。
【００７８】
ステップＳ４３で、エッジ−軌跡テーブル２４Ｂに未処理のエントリが存在しないと判定された場合には、処理はステップＳ５３へ移行する。ステップＳ５３では、経路グラフ生成部１５が、現在の経路グラフＧを、経路グラフＧ（ｔ）として、処理は、経路グラフ生成処理（図７）にリターンする。
【００７９】
次に、図７に示す経路グラフ生成処理のステップＳ６０で、取得部１１が、経路グラフ生成装置１０に入力されている次の軌跡データが存在するか否かを判定する。次の軌跡データが存在する場合には、処理はステップＳ６５へ移行し、取得部１１が、ｔを１インクリメントして、処理はステップＳ１５へ戻る。一方、次の軌跡データが存在しない場合には、経路グラフ生成処理は終了する。
【００８０】
上述した経路グラフ生成処理を、具体例を用いて説明する。
【００８１】
まず、ループ１（ｔ＝１）において、取得部１１が、軌跡データα（１）を読み込み（Ｓ１５）、平面グラフ生成部１２が、ドロネーグラフＤ（１）を生成し（Ｓ２０）、抽出部１３が、経路グラフＧ（０．５）を生成する（Ｓ２０）。図１０に、経路グラフＧ（０．５）の一例を示す。図１０において、実線のエッジ及び破線のエッジ（ただし、白丸のノードを一端とするエッジは除く）群が経路グラフＧ（０．５）を表している。また、図１０に示すエッジｅ１、ｅ９、ｅ１１、ｅ１３、ｅ１４、ｅ１５、及びｅ８が、Ｆ（＋）である。なお、図１０における黒丸で示すノードは、軌跡データα（１）の観測点により生成されたドロネーグラフＤ（１）のノードに基づいて生成されたノードである。また、図１０における白丸で示すノードは、軌跡データα（１）の観測点により生成されたドロネーグラフＤ（１）の煩雑さ回避し、説明を簡単にするために作図上設けたノードである。図１０、図１１、図１３、及び図１５においても同様である。
【００８２】
ここでは、Ｄ（０）＝φ（空）であるので、前回のドロネーグラフＤ（０）から消去されたエッジ集合Ｆ（−）は存在しないため、Ｆ（−）のいずれかを通過する軌跡データ集合Ｔｅは、Ｔｅ＝φである（Ｓ３０）。したがって、軌跡データ集合Ｔとして、Ｔ＝｛α（１）｝が算出部１４に渡され、経路グラフＧ（０．５）が経路グラフＧに設定され、経路グラフ更新処理が実行される（Ｓ４０）。
【００８３】
軌跡データα（１）を経路グラフＧにマップマッチングして、ルートπ＝＜ｅ１，ｅ９，ｅ１１，ｅ１３，ｅ１４，ｅ１５，ｅ８＞が得られ、非類似度δα（Ｇ）＝４が得られたとする（Ｓ４１）。この場合、軌跡管理表２４Ａ及びエッジ−軌跡テーブル２４Ｂは、図９に示すように更新される（Ｓ４２）。
【００８４】
そして、エッジ−軌跡テーブル２４Ｂから、エントリ（ｅ１５，｛α（１）｝）が抽出されたものとする（Ｓ４４）。この場合、ΔＧの初期値は、ΔＧ＝｛ｅ１，ｅ９，ｅ１１，ｅ１３，ｅ１４，ｅ１５，ｅ８｝に設定される（Ｓ４５）。また、ワーク変数は、Δｅｒｒ＝０、及びΔｇｒａｐｈ＝｜ΔＧ｜＝７に設定される（Ｓ４６）。なお、ここでは、各エッジ長を「１」と見做し、エッジ長の和＝エッジ数として説明する。
【００８５】
次に、算出部１４が、軌跡データ集合Ａ＝｛α（１）｝から、α（１）を軌跡データαＡに設定し（Ｓ４８）、軌跡α（１）を、エッジｅ１５を通過禁止に設定した経路グラフＧ＼｛ｅ１５｝にリルートしたルートπαＡを得る（Ｓ４９）。この場合、経路グラフＧ＼｛ｅ１５｝が連結ではなくなってしまうため、軌跡データαＡのリルートは不可能であり、非類似度δαＡ（Ｇ＼｛ｅ１５｝）は∞となる。
【００８６】
次に、算出部１４が、Δｅｒｒ＋（δαＡ（Ｇ＼｛ｅ１５｝）−δαＡ（Ｇ））＝０＋（∞−４）＝∞で、Δｅｒｒを更新し、Δｇｒａｐｈ−｜ΔＧ∩｛ｅ（ｍ）｜ｍ＝１，・・・，Ｍ｝｜＝７−０＝７で、Δｇｒａｐｈを更新する（Ｓ５０）。さらに、算出部１４が、ΔＧ＝｛ｅ１，ｅ９，ｅ１１，ｅ１３，ｅ１４，ｅ１５，ｅ８｝から、｛ｅ（ｍ）｜ｍ＝１，・・・，Ｍ｝を除外して、ΔＧ＝｛ｅ１，ｅ９，ｅ１１，ｅ１３，ｅ１４，ｅ１５，ｅ８｝と更新する。
【００８７】
上述のように、ここでは、δαＡ（Ｇ＼｛ｅ１５｝）が極めて大きな値となるため、Δｅｒｒ＞Δｇｒａｐｈとなり、ステップＳ５１で否定判定され、ステップＳ４３に戻る。エッジ−軌跡テーブル２４Ｂに含まれる他のエントリについても、エントリ（ｅ１５，｛α（１）｝）の場合と同様、Δｅｒｒ＞Δｇｒａｐｈとなるとする。この場合、経路グラフＧに設定した経路グラフＧ（０．５）から、いずれのエッジも除外されることなく、Ｇ（０．５）がそのまま経路グラフＧ（１）となる（Ｓ５３）。すなわち、図１０の実線のエッジ群が、経路グラフＧ（１）を表す。
【００８８】
次に、ループ２（ｔ＝２）において、取得部１１が、軌跡データα（２）を読み込み（Ｓ１５）、平面グラフ生成部１２が、ドロネーグラフＤ（２）を生成し（Ｓ２０）、抽出部１３が、経路グラフＧ（１．５）を生成する（Ｓ２０）。図１１に、経路グラフＧ（１．５）の一例を示す。図１１において、実線のエッジ、破線のエッジ、及び一点破線のエッジ（ただし、白丸のノードを一端とするエッジは除く）群が経路グラフＧ（１．５）を表している。また、図１１に示すエッジｅ２及びｅ１０が、Ｆ（＋）である。軌跡データα（２）を追加することにより、図１１に示すエッジｅ２、エッジｅ１０、及び一点破線で示すエッジが追加され、また、前回のドロネーグラフＤ（１）から消去されたエッジ集合Ｆ（−）はないとする。
【００８９】
Ｆ（−）=φであるため、Ｔｅ＝φであり（Ｓ３０）、軌跡データ集合Ｔとして、Ｔ＝｛α（２）｝が算出部１４に渡され、経路グラフＧ（１．５）が経路グラフＧに設定され、経路グラフ更新処理が実行される（Ｓ４０）。
【００９０】
軌跡データα（２）を経路グラフＧにマップマッチングして、ルートπ＝＜ｅ１，ｅ２，ｅ１０，ｅ１１，ｅ１３，ｅ１４，ｅ１５，ｅ８＞が得られ、非類似度δα（Ｇ）＝３が得られたとする（Ｓ４１）。この場合、軌跡管理表２４Ａ及びエッジ−軌跡テーブル２４Ｂは、図１２に示すように更新される（Ｓ４２）。
【００９１】
そして、エッジ−軌跡テーブル２４Ｂから、エントリ（ｅ９，｛α（１）｝）が抽出されたものとする（Ｓ４４）。この場合、ΔＧの初期値は、ΔＧ＝｛ｅ９｝に設定される（Ｓ４５）。また、ワーク変数は、Δｅｒｒ＝０、及びΔｇｒａｐｈ＝｜ΔＧ｜＝１に設定される（Ｓ４６）。
【００９２】
次に、算出部１４が、軌跡データ集合Ａ＝｛α（１）｝から、α（１）を軌跡データαＡに設定し（Ｓ４８）、軌跡α（１）を、エッジｅ９を通過禁止に設定した経路グラフＧ＼｛ｅ９｝にリルートしたルートπαＡを得る（Ｓ４９）。例えば、παＡ＝＜ｅ１，ｅ２，ｅ１０，ｅ１１，ｅ１３，ｅ１４，ｅ１５，ｅ８＞が得られたとする。また、非類似度δαＡ（Ｇ＼｛ｅ９｝）＝５．５が得られたとする。
【００９３】
次に、算出部１４が、Δｅｒｒ＋（δαＡ（Ｇ＼｛ｅ９｝）−δαＡ（Ｇ））＝０＋（５．５−４）＝１．５で、Δｅｒｒを更新し、Δｇｒａｐｈ−｜ΔＧ∩｛ｅ（ｍ）｜ｍ＝１，・・・，Ｍ｝｜＝１−０＝１で、Δｇｒａｐｈを更新する（Ｓ５０）。さらに、算出部１４が、ΔＧ＝｛ｅ９｝から、｛ｅ（ｍ）｜ｍ＝１，・・・，Ｍ｝＝｛ｅ１，ｅ２，ｅ１０，ｅ１１，ｅ１３，ｅ１４，ｅ１５，ｅ８｝を除外して、ΔＧ＝｛ｅ９｝と更新する。
【００９４】
Δｅｒｒ＝１．５＞Δｇｒａｐｈ＝１であるため、ステップＳ５１で否定判定され、ステップＳ４３に戻る。エッジ−軌跡テーブル２４Ｂに含まれる他のエントリについても、Δｅｒｒ＞Δｇｒａｐｈとなるとする。この場合、経路グラフＧ（１．５）から、いずれのエッジも除外されることなく、Ｇ（１．５）がそのまま経路グラフＧ（２）に更新される（Ｓ５３）。すなわち、図１１の実線のエッジ群が、経路グラフＧ（２）を表す。
【００９５】
次に、ループ３（ｔ＝３）において、取得部１１が、軌跡データα（３）を読み込み（Ｓ１５）、平面グラフ生成部１２が、ドロネーグラフＤ（３）を生成し（Ｓ２０）、抽出部１３が、経路グラフＧ（２．５）を生成する（Ｓ２０）。図１３に、経路グラフＧ（２．５）の一例を示す。図１３において、実線のエッジ、破線のエッジ、及び一点破線のエッジ（ただし、白丸のノードを一端とするエッジは除く）群が経路グラフＧ（２．５）を表している。また、図１３に示すエッジｅ３、ｅ１２、及び一点破線のエッジが、Ｆ（＋）である。軌跡データα（３）を追加することにより、図１３に示すエッジｅ３、エッジｅ１２、及び一点破線で示すエッジが追加され、また、白丸のノードを一端とするエッジ以外は、前回のドロネーグラフＤ（２）から消去されたエッジ集合Ｆ（−）はないとする。
【００９６】
Ｆ（−）＝φであるため、Ｔｅ＝φであり（Ｓ３０）、軌跡データ集合Ｔとして、Ｔ＝｛α（３）｝が算出部１４に渡され、経路グラフＧ（２．５）が経路グラフＧに設定され、経路グラフ更新処理が実行される（Ｓ４０）。
【００９７】
軌跡データα（３）を経路グラフＧにマップマッチングして、ルートπ＝＜ｅ１，ｅ２，ｅ３，ｅ１２，ｅ１３，ｅ１４，ｅ１５，ｅ８＞が得られ、非類似度δα（Ｇ）＝３が得られたとする（Ｓ４１）。この場合、軌跡管理表２４Ａ及びエッジ−軌跡テーブル２４Ｂは、図１４に示すように更新される（Ｓ４２）。
【００９８】
そして、エッジ−軌跡テーブル２４Ｂから、エントリ（ｅ９，｛α（１）｝）が抽出されたものとする（Ｓ４４）。この場合、ΔＧの初期値は、ΔＧ＝｛ｅ９｝に設定される（Ｓ４５）。また、ワーク変数は、Δｅｒｒ＝０、及びΔｇｒａｐｈ＝｜ΔＧ｜＝１に設定される（Ｓ４６）。
【００９９】
次に、算出部１４が、軌跡データ集合Ａ＝｛α（１）｝から、α（１）を軌跡データαＡに設定し（Ｓ４８）、軌跡α（１）を、エッジｅ９を通過禁止に設定した経路グラフＧ＼｛ｅ９｝にリルートしたルートπαＡを得る（Ｓ４９）。例えば、παＡ＝＜ｅ１，ｅ２，ｅ３，ｅ１２，ｅ１３，ｅ１４，ｅ１５，ｅ８＞が得られたとする。また、非類似度δαＡ（Ｇ＼｛ｅ９｝）＝５．８が得られたとする。
【０１００】
次に、算出部１４が、Δｅｒｒ＋（δαＡ（Ｇ＼｛ｅ９｝）−δαＡ（Ｇ））＝０＋（５．８−４）＝１．８で、Δｅｒｒを更新し、Δｇｒａｐｈ−｜ΔＧ∩｛ｅ（ｍ）｜ｍ＝１，・・・，Ｍ｝｜＝１−０＝１で、Δｇｒａｐｈを更新する（Ｓ５０）。さらに、算出部１４が、ΔＧ＝｛ｅ９｝から、｛ｅ（ｍ）｜ｍ＝１，・・・，Ｍ｝＝｛ｅ１，ｅ２，ｅ３，ｅ１２，ｅ１３，ｅ１４，ｅ１５，ｅ８｝を除外して、ΔＧ＝｛ｅ９｝と更新する。
【０１０１】
Δｅｒｒ＝１．８＞Δｇｒａｐｈ＝１であるため、ステップＳ５１で否定判定され、ステップＳ４３に戻る。エッジ−軌跡テーブル２４Ｂに含まれる他のエントリについても、エントリ（ｅ９，｛α（１）｝）の場合と同様、Δｅｒｒ＞Δｇｒａｐｈとなるとする。この場合、経路グラフＧに設定した経路グラフＧ（２．５）から、いずれのエッジも除外されることなく、Ｇ（２．５）がそのまま経路グラフＧ（３）に更新される（Ｓ５３）。すなわち、図１３の実線のエッジ群が、経路グラフＧ（３）を表す。
【０１０２】
次に、ループ４（ｔ＝４）において、取得部１１が、軌跡データα（４）を読み込み（Ｓ１５）、平面グラフ生成部１２が、ドロネーグラフＤ（４）を生成し（Ｓ２０）、抽出部１３が、経路グラフＧ（３．５）を生成する（Ｓ２０）。図１５に、経路グラフＧ（３．５）の一例を示す。図１５において、実線のエッジ、破線のエッジ、及び一点破線のエッジ（ただし、白丸のノードを一端とするエッジは除く）群が経路グラフＧ（３．５）を表している。また、図１５に示すエッジｅ４、ｅ５、ｅ６、ｅ７、及び一点破線のエッジが、Ｆ（＋）である。軌跡データα（４）を追加することにより、図１５に示すエッジｅ４、ｅ５、ｅ６、ｅ７、及び一点破線で示すエッジが追加され、また、白丸のノードを一端とするエッジ以外は、前回のドロネーグラフＤ（３）から消去されたエッジ集合Ｆ（−）はないとする（Ｓ３０）。
【０１０３】
軌跡データ集合Ｔとして、Ｔ＝｛α（４）｝が算出部１４に渡され、経路グラフＧ（３．５）が経路グラフＧに設定され、経路グラフ更新処理が実行される（Ｓ４０）。
【０１０４】
軌跡データα（４）を経路グラフＧにマップマッチングして、ルートπ＝＜ｅ１，ｅ２，ｅ３，ｅ４，ｅ５，ｅ６，ｅ７，ｅ８＞が得られ、非類似度δα（Ｇ）＝５が得られたとする（Ｓ４１）。この場合、軌跡管理表２４Ａ及びエッジ−軌跡テーブル２４Ｂは、図１６に示すように更新される（Ｓ４２）。
【０１０５】
そして、エッジ−軌跡テーブル２４Ｂから、エントリ（ｅ１５，｛α（１），α（２），α（３）｝）が抽出されたものとする（Ｓ４４）。この場合、ΔＧの初期値は、ΔＧ＝｛ｅ９，ｅ１０，ｅ１１，ｅ１２，ｅ１３，ｅ１４，ｅ１５｝に設定される（Ｓ４５）。また、ワーク変数は、Δｅｒｒ＝０、及びΔｇｒａｐｈ＝｜ΔＧ｜＝７に設定される（Ｓ４６）。
【０１０６】
次に、算出部１４が、軌跡データ集合Ａ＝｛α（１），α（２），α（３）｝から、α（１）を軌跡データαＡに設定し（Ｓ４８）、軌跡α（１）を、エッジｅ１５を通過禁止に設定した経路グラフＧ＼｛ｅ１５｝にリルートしたルートπαＡを得る（Ｓ４９）。例えば、παＡ＝＜ｅ１，ｅ２，ｅ３，ｅ４，ｅ５，ｅ６，ｅ７，ｅ８＞が得られたとする。また、非類似度δαＡ（Ｇ＼｛ｅ１５｝）＝５が得られたとする。
【０１０７】
次に、算出部１４が、Δｅｒｒ＋（δαＡ（Ｇ＼｛ｅ１５｝）−δαＡ（Ｇ））＝０＋（５−４）＝１で、Δｅｒｒを更新し、Δｇｒａｐｈ−｜ΔＧ∩｛ｅ（ｍ）｜ｍ＝１，・・・，Ｍ｝｜＝７−０＝７で、Δｇｒａｐｈを更新する（Ｓ５０）。さらに、算出部１４が、ΔＧ＝｛ｅ９，ｅ１０，ｅ１１，ｅ１２，ｅ１３，ｅ１４，ｅ１５｝から、｛ｅ（ｍ）｜ｍ＝１，・・・，Ｍ｝＝｛ｅ１，ｅ２，ｅ３，ｅ４，ｅ５，ｅ６，ｅ７，ｅ８｝を除外する。そして、ΔＧ＝｛ｅ９，ｅ１０，ｅ１１，ｅ１２，ｅ１３，ｅ１４，ｅ１５｝と更新する。
【０１０８】
Δｅｒｒ＝１＜Δｇｒａｐｈ＝７であるため、ステップＳ５１で肯定判定され、ステップＳ４７に戻る。
【０１０９】
次に、算出部１４が、軌跡データ集合Ａ＝｛α（１），α（２），α（３）｝から、α（２）を軌跡データαＡに設定し（Ｓ４８）、軌跡α（２）を、エッジｅ１５を通過禁止に設定した経路グラフＧ＼｛ｅ１５｝にリルートしたルートπαＡを得る（Ｓ４９）。例えば、παＡ＝＜ｅ１，ｅ２，ｅ３，ｅ４，ｅ５，ｅ６，ｅ７，ｅ８＞が得られたとする。また、非類似度δαＡ（Ｇ＼｛ｅ１５｝）＝５が得られたとする。
【０１１０】
次に、算出部１４が、Δｅｒｒ＋（δαＡ（Ｇ＼｛ｅ１５｝）−δαＡ（Ｇ））＝１＋（５−３）＝３で、Δｅｒｒを更新し、Δｇｒａｐｈ−｜ΔＧ∩｛ｅ（ｍ）｜ｍ＝１，・・・，Ｍ｝｜＝７−０＝７で、Δｇｒａｐｈを更新する（Ｓ５０）。さらに、算出部１４が、ΔＧ＝｛ｅ９，ｅ１０，ｅ１１，ｅ１２，ｅ１３，ｅ１４，ｅ１５｝から、｛ｅ（ｍ）｜ｍ＝１，・・・，Ｍ｝＝｛ｅ１，ｅ２，ｅ３，ｅ４，ｅ５，ｅ６，ｅ７，ｅ８｝を除外し、ΔＧ＝｛ｅ９，ｅ１０，ｅ１１，ｅ１２，ｅ１３，ｅ１４，ｅ１５｝と更新する。
【０１１１】
Δｅｒｒ＝３＜Δｇｒａｐｈ＝７であるため、ステップＳ５１で肯定判定され、ステップＳ４７に戻る。
【０１１２】
次に、算出部１４が、軌跡データ集合Ａ＝｛α（１），α（２），α（３）｝から、α（３）を軌跡データαＡに設定し（Ｓ４８）、軌跡α（３）を、エッジｅ１５を通過禁止に設定した経路グラフＧ＼｛ｅ１５｝にリルートしたルートπαＡを得る（Ｓ４９）。例えば、παＡ＝＜ｅ１，ｅ２，ｅ３，ｅ４，ｅ５，ｅ６，ｅ７，ｅ８＞が得られたとする。また、非類似度δαＡ（Ｇ＼｛ｅ１５｝）＝５が得られたとする。
【０１１３】
次に、算出部１４が、Δｅｒｒ＋（δαＡ（Ｇ＼｛ｅ１５｝）−δαＡ（Ｇ））＝３＋（５−３）＝５で、Δｅｒｒを更新し、Δｇｒａｐｈ−｜ΔＧ∩｛ｅ（ｍ）｜ｍ＝１，・・・，Ｍ｝｜＝７−０＝７で、Δｇｒａｐｈを更新する（Ｓ５０）。さらに、算出部１４が、ΔＧ＝｛ｅ９，ｅ１０，ｅ１１，ｅ１２，ｅ１３，ｅ１４，ｅ１５｝から、｛ｅ（ｍ）｜ｍ＝１，・・・，Ｍ｝＝｛ｅ１，ｅ２，ｅ３，ｅ４，ｅ５，ｅ６，ｅ７，ｅ８｝を除外し、ΔＧ＝｛ｅ９，ｅ１０，ｅ１１，ｅ１２，ｅ１３，ｅ１４，ｅ１５｝と更新する。
【０１１４】
Δｅｒｒ＝５＜Δｇｒａｐｈ＝７であるため、ステップＳ５１で肯定判定され、処理はステップＳ４７に戻る。軌跡データ集合Ａには、未処理の軌跡データは存在しないため、処理はステップＳ５２へ移行し、経路グラフ生成部１５が、経路グラフＧからΔＧ＝｛ｅ９，ｅ１０，ｅ１１，ｅ１２，ｅ１３，ｅ１４，ｅ１５｝を除外して、経路グラフＧを更新する。また、経路グラフ生成部１５は、軌跡管理表２４Ａ及びエッジ−軌跡テーブル２４Ｂを更新する。具体的には、まず、軌跡データ集合Ａ＝｛α（１），α（２），α（３）｝について、軌跡管理表２４Ａのルートπ及び非類似度δα（Ｇ）を、それぞれπαＡ及びδαＡ（Ｇ）に更新する。続けて、エッジ−軌跡テーブル２４ＢからΔＧ＝｛ｅ９，ｅ１０，ｅ１１，ｅ１２，ｅ１３，ｅ１４，ｅ１５｝のエントリを除外したのちに、軌跡データ集合Ａ＝｛α（１），α（２），α（３）｝について、ルートπαＡ＝＜ｅ（１），ｅ（２），…，ｅ（ｍ）＞のエントリを更新する。
【０１１５】
以上説明したように、本実施形態に係る経路グラフ生成装置によれば、生成済みの経路グラフと、その経路グラフに軌跡データを追加して得た平面グラフとの差分を通過する軌跡データのみをマップマッチングして、コスト最適となる経路グラフを生成する。これにより、コストを最適化するために、バッチ処理により全ての軌跡データから経路グラフを生成する場合に比べ、計算量の多いマップマッチングの回数を低減することができるため、コストが最適となる経路グラフをオンライン処理で生成することができる。マップマッチングの回数を低減することができることにより、大量の軌跡データを処理する場合にも対応することができる。
【０１１６】
また、本実施形態では、高次元、離散値の空間の元として定義される経路グラフに対し、経路グラフと軌跡データとの非類似性、及び経路グラフの複雑さを考慮したコストの差分を定義し、オンライン型のアルゴリズムである最急降下法を適用している。これにより、コストが最適となる経路グラフの局所最適解を得ることができるため、より効率的にオンライン処理を実現することができる。
【０１１７】
また、本実施形態では、軌跡データのみで経路グラフを生成することができる。すなわち、ＧＰＳなどのセンサを搭載した移動体の速度や観測データの観測間隔等の移動体の固有な性質に依らず、軌跡データは観測点の系列データであるという要件さえ満たしていれば、コストが最適となる経路グラフをオンライン処理で生成することができる。
【０１１８】
コストが最適となる経路グラフをオンライン処理により生成することができることにより、軌跡データの分析をリアルタイムで実施することができる。例えば、交通渋滞を予測したり、事故やトラブルの発生を即時に検知し、これに伴う人や車の流れの変化をリアルタイムに分析したりすることができる。
【０１１９】
なお、上記実施形態では、軌跡データのマップマッチングを１本ずつ行う場合について説明したが、これに限定されない。異なる軌跡データのマップマッチングの結果は相互に依存しないため、グラフＧ−ΔＧを共有するスレッドや子プロセスを使って、並列に実行してもよい。これにより、経路グラフの生成の処理時間をさらに短縮することができる。
【０１２０】
また、上記実施形態では、生成済みのドロネーグラフのノード及び追加する軌跡データの観測点の全てを用いて、ドロネーグラフを更新する場合について説明したが、これに限定されない。これらのノード及び観測点から、例えば、乱数を用いたサンプリングによって抽出したノード及び観測点を用いてドロネーグラフを更新してもよい。これにより、マップマッチングの計算量、及び最急降下法の反復回数を低減することができる。
【０１２１】
また、上記実施形態では、初期解となるグラフを空としているが、複数の軌跡データから既に生成されている経路グラフ、デジタル道路ネットワークデータ、三角格子グラフ、四角格子グラフ、任意の点をドロネー点とするドロネーグラフなどを用いてもよい。特に、デジタル道路ネットワークデータ、三角格子グラフ、四角格子グラフを用いる場合には、平面グラフ生成部を省略することができる。この場合、常にＤ（ｔ）＝Ｄ（ｔ−１）、Ｆ（−）＝φであり、上記ステップＳ３０において、Ｔｅ＝φとなる。そのかわり、Ｆ（＋）は、α（ｔ）をＤ（ｔ）にマップマッチングしたときのエッジが設定される。
【０１２２】
また、平面グラフ生成部で生成するグラフは、ドロネーグラフの場合に限定されず、平面グラフであればよい。
【０１２３】
また、上記では、経路グラフ生成プログラム５０が記憶部４３に予め記憶（インストール）されている態様を説明したが、これに限定されない。開示の技術に係るプログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ等の記録媒体に記録された形態で提供することも可能である。
【０１２４】
以上の実施形態に関し、更に以下の付記を開示する。
【０１２５】
（付記１）
コンピュータに、
複数の位置情報をそれぞれが含む複数の軌跡情報を記憶する第１の記憶部を参照して、前記複数の軌跡情報のうちの何れかの軌跡情報を取得し、
それぞれが位置を示す複数のノードと、それぞれが前記複数のノード間を連結する複数のエッジとをそれぞれが含む一又は複数の平面グラフを記憶する第２の記憶部を参照して、前記一又は複数の平面グラフのうちの何れかの平面グラフを取得し、
取得した前記何れかの平面グラフと、取得した前記何れかの軌跡情報に含まれる複数の位置情報とに基づき、他の平面グラフを生成し、
前記第１の記憶部に記憶された前記複数の軌跡情報のうち、前記何れかの平面グラフと、前記他の平面グラフとの差分部分を通過する他の軌跡情報を抽出し、
前記他の平面グラフから該他の平面グラフに含まれる何れかのエッジを除外した候補グラフ毎に、取得した前記軌跡情報と、抽出した前記他の軌跡情報とのそれぞれを対応付けた際の該候補グラフの最適度を算出し、
算出した前記最適度に基づき、何れかの候補グラフを出力する
ことを含む処理を実行させる経路グラフ生成方法。
【０１２６】
（付記２）
前記最適度は、前記取得した軌跡情報及び前記抽出した他の軌跡情報の各々を、前記他の平面グラフに対応付けた際に通過するエッジ毎に、該エッジを通過禁止とした前記他の平面グラフに、前記取得した軌跡情報及び前記抽出した他の軌跡情報の各々を再度対応付けた際に通過しないエッジを、前記他の平面グラフから除外した候補グラフ毎に算出される付記１記載の経路グラフ生成方法。
【０１２７】
（付記３）
前記他の平面グラフとして、前記何れかの平面グラフに含まれる複数のノード、及び前記取得した軌跡情報に含まれる複数の位置情報の各々をドロネー点とするドロネーグラフを生成する付記１又は付記２記載の経路グラフ生成方法。
【０１２８】
（付記４）
前記最適度は、前記候補グラフの複雑度と、前記取得した軌跡情報及び前記抽出した他の軌跡情報の各々と前記候補グラフとの非類似度とを用いて表される付記１〜付記３のいずれか１項記載の経路グラフ生成方法。
【０１２９】
（付記５）
前記最適度は、エッジを除外する前後における前記複雑度の差と、前記非類似度の差とを用いて表される付記４記載の経路グラフ生成方法。
【０１３０】
（付記６）
前記候補グラフの最適度を算出する際、前記取得した軌跡情報及び前記抽出した他の軌跡情報のいずれか１つの軌跡情報を再度対応付ける毎に前記最適度を算出し、算出された最適度が、前記複雑度の差が前記非類似度の差より大きい場合には、残りの軌跡情報を再度対応付けることなく、該候補グラフを候補から除外する付記５記載の経路グラフ生成方法。
【０１３１】
（付記７）
前記他の平面グラフを生成する際に、前記取得した軌跡情報に含まれる複数の位置情報と、前記何れかの平面グラフに含まれる複数のノードとからサンプリングした点を前記ドロネー点とする付記３記載の経路グラフ生成方法。
【０１３２】
（付記８）
前記何れかの平面グラフの初期値として、空のグラフ、複数の軌跡情報から生成された経路グラフ、デジタル道路ネットワークデータ、三角格子グラフ、四角格子グラフ、又は所定の点をドロネー点とするドロネーグラフを用いる付記１〜付記７のいずれか１項記載の経路グラフ生成方法。
【０１３３】
（付記９）
複数の位置情報をそれぞれが含む複数の軌跡情報を記憶する第１の記憶部を参照して、前記複数の軌跡情報のうちの何れかの軌跡情報を取得する軌跡情報取得部と、
それぞれが位置を示す複数のノードと、それぞれが前記複数のノード間を連結する複数のエッジとをそれぞれが含む一又は複数の平面グラフを記憶する第２の記憶部を参照して、前記一又は複数の平面グラフのうちの何れかの平面グラフを取得する平面グラフ取得部と、
取得した前記何れかの平面グラフと、取得した前記何れかの軌跡情報に含まれる複数の位置情報とに基づき、他の平面グラフを生成する生成部と、
前記第１の記憶部に記憶された前記複数の軌跡情報のうち、前記何れかの平面グラフと、前記他の平面グラフとの差分部分を通過する他の軌跡情報を抽出する抽出部と、
前記他の平面グラフから該他の平面グラフに含まれる何れかのエッジを除外した候補グラフ毎に、取得した前記軌跡情報と、抽出した前記他の軌跡情報とのそれぞれを対応付けた際の該候補グラフの最適度を算出する算出部と、
算出した前記最適度に基づき、何れかの候補グラフを出力する出力部と、
を含む経路グラフ生成装置。
【０１３４】
（付記１０）
前記算出部は、前記取得した軌跡情報及び前記抽出した他の軌跡情報の各々を、前記他の平面グラフに対応付けた際に通過するエッジ毎に、該エッジを通過禁止とした前記他の平面グラフに、前記取得した軌跡情報及び前記抽出した他の軌跡情報の各々を再度対応付けた際に通過しないエッジを、前記他の平面グラフから除外した候補グラフ毎に、前記最適度を算出する付記９記載の経路グラフ生成装置。
【０１３５】
（付記１１）
前記生成部は、前記他の平面グラフとして、前記何れかの平面グラフに含まれる複数のノード、及び前記第１の軌跡情報に含まれる複数の位置情報の各々をドロネー点とするドロネーグラフを生成する付記９又は付記１０記載の経路グラフ生成装置。
【０１３６】
（付記１２）
前記算出部は、前記候補グラフの複雑度と、前記取得した軌跡情報及び前記抽出した他の軌跡情報の各々と前記候補グラフとの非類似度とを用いて表される最適度を算出する付記９〜付記１１のいずれか１項記載の経路グラフ生成装置。
【０１３７】
（付記１３）
前記算出部は、エッジを除外する前後における前記複雑度の差と、前記非類似度の差とを用いて表される最適度を算出する付記１２記載の経路グラフ生成装置。
【０１３８】
（付記１４）
前記算出部は、各候補グラフの最適度を算出する際、前記取得した軌跡情報及び前記抽出した他の軌跡情報のいずれか１つの軌跡情報を再度対応付ける毎に前記最適度を算出し、算出された最適度が、前記複雑度の差が前記非類似度の差より大きい場合には、残りの軌跡情報を再度対応付けることなく、該候補グラフを候補から除外する付記１３記載の経路グラフ生成装置。
【０１３９】
（付記１５）
前記平面グラフ生成部は、前記他の平面グラフを生成する際に、前記取得した軌跡情報に含まれる複数の位置情報と、前記何れかの平面グラフに含まれる複数のノードとからサンプリングした点を前記ドロネー点とする付記１１記載の経路グラフ生成装置。
【０１４０】
（付記１６）
前記平面グラフ生成部は、前記何れかの平面グラフの初期値として、空のグラフ、複数の軌跡情報から生成された経路グラフ、デジタル道路ネットワークデータ、三角格子グラフ、四角格子グラフ、又は所定の点をドロネー点とするドロネーグラフを用いる付記９〜付記１５のいずれか１項記載の経路グラフ生成装置。
【０１４１】
（付記１７）
コンピュータに、
複数の位置情報をそれぞれが含む複数の軌跡情報を記憶する第１の記憶部を参照して、前記複数の軌跡情報のうちの何れかの軌跡情報を取得し、
それぞれが位置を示す複数のノードと、それぞれが前記複数のノード間を連結する複数のエッジとをそれぞれが含む一又は複数の平面グラフを記憶する第２の記憶部を参照して、前記一又は複数の平面グラフのうちの何れかの平面グラフを取得し、
取得した前記何れかの平面グラフと、取得した前記何れかの軌跡情報に含まれる複数の位置情報とに基づき、他の平面グラフを生成し、
前記第１の記憶部に記憶された前記複数の軌跡情報のうち、前記何れかの平面グラフと、前記他の平面グラフとの差分部分を通過する他の軌跡情報を抽出し、
前記他の平面グラフから該他の平面グラフに含まれる何れかのエッジを除外した候補グラフ毎に、取得した前記軌跡情報と、抽出した前記他の軌跡情報とのそれぞれを対応付けた際の該候補グラフの最適度を算出し、
算出した前記最適度に基づき、何れかの候補グラフを出力する
ことを含む処理を実行させる経路グラフ生成プログラム。
【０１４２】
（付記１８）
前記最適度は、前記取得した軌跡情報及び前記抽出した他の軌跡情報の各々を、前記他の平面グラフに対応付けた際に通過するエッジ毎に、該エッジを通過禁止とした前記他の平面グラフに、前記取得した軌跡情報及び前記抽出した他の軌跡情報の各々を再度対応付けた際に通過しないエッジを、前記他の平面グラフから除外した候補グラフ毎に算出される付記１７記載の経路グラフ生成プログラム。
【０１４３】
（付記１９）
前記他の平面グラフとして、前記何れかの平面グラフに含まれる複数のノード、及び前記取得した軌跡情報に含まれる複数の位置情報の各々をドロネー点とするドロネーグラフを生成する付記１７又は付記１８記載の経路グラフ生成プログラム。
【０１４４】
（付記２０）
前記最適度は、前記候補グラフの複雑度と、前記取得した軌跡情報及び前記抽出した他の軌跡情報の各々と前記候補グラフとの非類似度とを用いて表される付記１７〜付記１９のいずれか１項記載の経路グラフ生成プログラム。
【０１４５】
（付記２１）
前記最適度は、エッジを除外する前後における前記複雑度の差と、前記非類似度の差とを用いて表される付記２０記載の経路グラフ生成プログラム。
【０１４６】
（付記２２）
前記候補グラフの最適度を算出する際、前記取得した軌跡情報及び前記抽出した他の軌跡情報のいずれか１つの軌跡情報を再度対応付ける毎に前記最適度を算出し、算出された最適度が、前記複雑度の差が前記非類似度の差より大きい場合には、残りの軌跡情報を再度対応付けることなく、該候補グラフを候補から除外する付記２１記載の経路グラフ生成プログラム。
【０１４７】
（付記２３）
前記他の平面グラフを生成する際に、前記取得した軌跡情報に含まれる複数の位置情報と、前記何れかの平面グラフに含まれる複数のノードとからサンプリングした点を前記ドロネー点とする付記１９記載の経路グラフ生成プログラム。
【０１４８】
（付記２４）
前記何れかの平面グラフの初期値として、空のグラフ、複数の軌跡情報から生成された経路グラフ、デジタル道路ネットワークデータ、三角格子グラフ、四角格子グラフ、又は所定の点をドロネー点とするドロネーグラフを用いる付記１７〜付記２３のいずれか１項記載の経路グラフ生成プログラム。
【０１４９】
（付記２５）
コンピュータに、
複数の位置情報をそれぞれが含む複数の軌跡情報を記憶する第１の記憶部を参照して、前記複数の軌跡情報のうちの何れかの軌跡情報を取得し、
それぞれが位置を示す複数のノードと、それぞれが前記複数のノード間を連結する複数のエッジとをそれぞれが含む一又は複数の平面グラフを記憶する第２の記憶部を参照して、前記一又は複数の平面グラフのうちの何れかの平面グラフを取得し、
取得した前記何れかの平面グラフと、取得した前記何れかの軌跡情報に含まれる複数の位置情報とに基づき、他の平面グラフを生成し、
前記第１の記憶部に記憶された前記複数の軌跡情報のうち、前記何れかの平面グラフと、前記他の平面グラフとの差分部分を通過する他の軌跡情報を抽出し、
前記他の平面グラフから該他の平面グラフに含まれる何れかのエッジを除外した候補グラフ毎に、取得した前記軌跡情報と、抽出した前記他の軌跡情報とのそれぞれを対応付けた際の該候補グラフの最適度を算出し、
算出した前記最適度に基づき、何れかの候補グラフを出力する
ことを含む処理を実行させる経路グラフ生成プログラムを記憶した記憶媒体。
【符号の説明】
【０１５０】
１０   経路グラフ生成装置
１１   取得部
１２   平面グラフ生成部
１３   抽出部
１４   算出部
１５   経路グラフ生成部
２１   軌跡データ
２２   経路グラフデータベース
２３   ドロネーグラフデータベース
２４   管理データベース
２４Ａ 軌跡管理表
２４Ｂ 軌跡テーブル
４０   コンピュータ
４１   ＣＰＵ
４２   メモリ
４３   記憶部
４９   記録媒体
５０   経路グラフ生成プログラム
【図１】
0006672711.tif 000002
【図２】
0006672711.tif 000003
【図３】
0006672711.tif 000004
【図４】
0006672711.tif 000005
【図５】
0006672711.tif 000006
【図６】
0006672711.tif 000007
【図７】
0006672711.tif 000008
【図８】
0006672711.tif 000009
【図９】
0006672711.tif 000010
【図１０】
0006672711.tif 000011
【図１１】
0006672711.tif 000012
【図１２】
0006672711.tif 000013
【図１３】
0006672711.tif 000014
【図１４】
0006672711.tif 000015
【図１５】
0006672711.tif 000016
【図１６】
0006672711.tif 000017