(57)【特許請求の範囲】
【請求項１】
記憶部に記憶された移動履歴情報に含まれる第１の移動に関する第１の移動経路及び該第１の移動経路における第１の移動速度と、第２の移動に関する第２の移動経路及び該第２の移動経路における第２の移動速度とを取得し、
取得した前記第１の移動経路と前記第２の移動経路との間の近さに関する評価値と、前記第１の移動速度と前記第２の移動速度との間の速度差に関する評価値と、に基づいて、前記第１の移動経路と前記第２の移動経路との間で移動経路の統合処理を実行するか否か判定し、
判定結果に応じて前記第１の移動経路と前記第２の移動経路との統合処理を実行する、
処理をコンピュータに実行させることを特徴とする移動経路統合方法。
【請求項２】
前記第１の移動経路と、前記第２の移動経路は、それぞれ、前記第１の移動、前記第２の移動において測定された２箇所の位置を結ぶパスである、ことを特徴とする請求項１に記載の移動経路統合方法。
【請求項３】
前記第１の移動経路に、前記第１の移動速度が異なる複数の区間が含まれる場合、前記第２の移動経路を前記複数の区間の各々に対応して分割した区間毎に、前記第１の移動経路と前記第２の移動経路との間で移動経路の統合処理を実行するか否か判定する、前記速度差を求める請求項１または請求項２に記載の移動経路統合方法。
【請求項４】
前記第１の移動経路に、前記第１の移動速度が同一の複数の区間が含まれる場合、前記第２の移動経路と、前記第１の移動経路の前記複数の区間との間で移動経路の統合処理を実行するか否か判定する、請求項１または請求項２に記載の移動経路統合方法。
【請求項５】
記憶部に記憶された移動履歴情報に含まれる第１の移動に関する第１の移動経路及び該第１の移動経路における第１の移動速度と、第２の移動に関する第２の移動経路及び該第２の移動経路における第２の移動速度とを取得し、
取得した前記第１の移動経路と前記第２の移動経路との間の近さに関する評価値と、前記第１の移動速度と前記第２の移動速度との間の速度差に関する評価値と、に基づいて、前記第１の移動経路と前記第２の移動経路との間で移動経路の統合処理を実行するか否か判定し、
判定結果に応じて前記第１の移動経路と前記第２の移動経路との統合処理を実行する、
処理をコンピュータに実行させることを特徴とする移動経路統合プログラム。
【請求項６】
記憶部に記憶された移動履歴情報に含まれる第１の移動に関する第１の移動経路及び該第１の移動経路における第１の移動速度と、第２の移動に関する第２の移動経路及び該第２の移動経路における第２の移動速度とを取得する取得部と、
取得した前記第１の移動経路と前記第２の移動経路との間の近さに関する評価値と、前記第１の移動速度と前記第２の移動速度との間の速度差に関する評価値と、に基づいて、前記第１の移動経路と前記第２の移動経路との間で移動経路の統合処理を実行するか否か判定する判定部と、
判定結果に応じて前記第１の移動経路と前記第２の移動経路との統合処理を実行する統合部と、
を含む移動経路統合装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動経路統合方法、移動経路統合装置、及び移動経路統合プログラムに関する。
【背景技術】
【０００２】
従来、空間情報分析として、移動体の経路に関する分析を行う技術が存在する。例えば、実際の観測データである複数の軌跡データから、指定された地点を出発地点または到着地点とする経路を検索するＯＤ（Ｏ＝“Origin”：出発地点、Ｄ＝“Destination”：到着地点）検索を行う技術が存在する。また、複数の軌跡データから、所定回数（例えば、１０回）以上出現する出発地点と到着地点との組み合わせ（例えば、（新宿駅−渋谷駅）、（品川駅−池袋駅）等）を示す頻出ＯＤを分析する技術が存在する。また、軌跡データの中から、例えば、品川駅→（山手線外回り）→池袋駅を通過する経路のように、部分経路を検索する技術が存在する。さらに、軌跡データの中に、所定回数（例えば、１０回）以上出現する部分経路を示す頻出部分経路を分析する技術が存在する。このような経路分析において、分析対象となる経路が、道路ネットワークや地図データなどで予め特定されている場合には、経路に軌跡データを対応させることで、適切な分析結果を得ることができる。
【０００３】
また、軌跡データ等の移動体の移動に関する情報に基づいて、移動体の状態等を分析する技術が提案されている。例えば、車両の状態を予測する装置において、所定の道路単位で走行場所を特定し、その道路単位を走行中の車両の状態を示す測定結果を取得する装置が提案されている。この装置では、同一の道路単位での測定結果を所定の条件に従いグループにまとめ、グループの属する測定結果に基づく測定データを有する走行データを生成する。そして、グループに対応する道路単位と対応させて記憶し、道路単位の距離に基づき車両の状態を予測している。
【０００４】
また、多数の車両が実際に走行した軌跡と速度の情報を含む走行履歴データを蓄積し、このデータを用いて最適な走行経路を検索するカーナビゲーションシステムなども提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００８−２８２２６３号公報
【特許文献２】特開２０１２−６３２６０号公報
【特許文献３】特開２０１３−１４８５７４号公報
【特許文献４】特開２０１２−２７５５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
軌跡データを用いた移動体の経路の分析において、軌跡データで表された移動体の移動経路を対応させるべき分析対象となる経路情報が、例えば道路ネットワークや地図データなどの予め特定された情報として存在しない場合がある。このような場合には、軌跡データから適切な分析結果が得られない。そこで、複数の移動体の移動経路を統合して、分析対象となる経路グラフを生成することが考えられる。
【０００７】
ところが、従来技術では、移動体の軌跡データの類似性に基づき、複数の移動体の移動経路を統合している。このため、生成される経路グラフは、移動体の移動を十分に反映できていない。
【０００８】
本発明は、一つの側面として、移動体の移動をより反映した経路グラフを生成できる移動経路統合方法、移動経路統合装置、及び移動経路統合プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
一つの態様として、記憶部に記憶された移動履歴情報に含まれる第１の移動に関する第１の移動経路及び該第１の移動経路における第１の移動速度と、第２の移動に関する第２の移動経路及び該第２の移動経路における第２の移動速度とを取得する。そして、前記第１の移動経路と前記第２の移動経路との間で移動経路の統合処理を実行するか否か判定する。この判定は、取得した前記第１の移動経路と前記第２の移動経路との間の近さに関する評価値と、前記第１の移動速度と前記第２の移動速度との間の速度差に関する評価値と、に基づいて行う。さらに、判定結果に応じて前記第１の移動経路と前記第２の移動経路との統合処理を実行する。
【発明の効果】
【００１０】
一つの側面として、移動体の移動をより反映した経路グラフを生成することができる、という効果を有する。
【図面の簡単な説明】
【００１１】
【図１】本実施形態の経路グラフ生成システムの概略構成を示すブロック図である。
【図２】軌跡データが示す軌跡の概略図である。
【図３】本実施形態の経路グラフ生成装置の機能ブロック図である。
【図４】節点間に付与された速度情報の一例を示す図である。
【図５】経路グラフの生成を説明するための図である。
【図６】最適な経路グラフを説明するための図である。
【図７】距離近似領域の一例を説明するための図である。
【図８】速度の異なる部分を説明するための図である。
【図９】節点の対応付けを説明するための図である。
【図１０】近似領域の一例を説明するための図である。
【図１１】本実施形態の経路グラフ生成装として機能するコンピュータの概略構成を示すブロック図である。
【図１２】経路グラフ生成処理の一例を示すフローチャートである。
【図１３】軌跡データ探索処理の一例を示すフローチャートである。
【図１４】軌跡データ追加処理の一例を示すフローチャートである。
【図１５】近似領域抽出処理の一例を示すフローチャートである。
【図１６】距離近似領域の抽出を説明するための図である。
【図１７】軌跡と経路との速度の比較を説明するための図である。
【図１８】軌跡と経路との速度の比較を説明するための図である。
【図１９】軌跡と経路との速度の比較を説明するための図である。
【図２０】軌跡と経路との速度の比較を説明するための図である。
【図２１】平面グラフへの軌跡データの追加を説明するための図である。
【図２２】軌跡データ集合追加処理の一例を示すフローチャートである。
【図２３】経路グラフ生成処理の最初のループにおいて生成された中間の平面グラフの一例を示す図である。
【図２４】経路グラフ生成処理の最初のループにおいて生成された中間の平面グラフに対する非近似性のコストの一例を示す図である。
【図２５】経路グラフ生成処理の２回目のループにおいて生成された中間の平面グラフの中間の平面グラフの一例を示す図である。
【図２６】経路グラフ生成処理の２回目のループにおいて生成された中間の平面グラフに対する非近似性のコストの一例を示す図である。
【図２７】中間の平面グラフに残りの軌跡データを追加して経路グラフを生成する様子を示す図である。
【図２８】速度を考慮しない経路グラフの生成を示す図である。
【図２９】本実施形態における経路グラフの生成を示す図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施形態の一例を詳細に説明する。
【００１３】
図１に示すように、本実施形態に係る経路グラフ生成装置１０は、軌跡データ生成装置２２と、軌跡データ記憶部２４と共に、経路グラフ生成システム２０に含まれる。なお、経路グラフ生成装置１０は、本発明の移動経路統合装置の一例である。
【００１４】
軌跡データ生成装置２２は、移動体の位置を観測するセンサ２６の各々で定期的に観測された移動体の位置を示す観測データを、ネットワーク２８を介して取得する。センサ２６は、移動体の一例である人が保持する携帯電話、スマートフォン等の端末や、移動体の一例である車両に搭載されたカーナビゲーションシステム等で利用されるＧＰＳ等とすることができる。観測データには、観測点毎の緯度及び経度で示される位置データと観測時刻、並びにセンサ２６を識別するセンサＩＤが含まれる。軌跡データ生成装置２２は、取得した複数の観測データを、センサＩＤ毎に抽出し、各観測データに含まれる位置データを、観測時刻に基づいて時系列に並べて軌跡データを生成する。
【００１５】
軌跡データにより、移動体がどのように移動したかを示す軌跡が特定される。例えば、センサＩＤ＝ｋの観測データに含まれる位置データが示す観測点をｐｉ（ｉ＝１，２，・・・，ｎ、ｎはセンサＩＤ＝ｋを含む観測データに含まれる位置データの総数）とする。この場合、軌跡αｋを示す軌跡データは、αｋ＝＜ｐ１，ｐ２，・・・，ｐｎ＞と表すことができる。なお、観測点ｐｉを示す位置データは、緯度ｘｉ及び経度ｙｉを用いて、ｐｉ＝（ｘｉ，ｙｉ）∈Ｒ２（Ｒ２は実数を要素とする二次元空間）で表される。
【００１６】
例えば、図２に概略的に示す複数の軌跡α１，α２，α３，α４を示す軌跡データα１，α２，α３，α４は下記のように表される。
軌跡データ集合Ｔ＝｛α１，α２，α３，α４｝
α１＝＜ｐ１，ｐ２，ｐ３，ｐ４＞
α２＝＜ｐ５，ｐ６，ｐ７，ｐ８，ｐ９＞
α３＝＜ｐ１０，ｐ１１，ｐ１２＞
α４＝＜ｐ１３，ｐ１４＞
【００１７】
また、本実施形態では、各軌跡を、観測点に対応する節点と、時系列順で連続する観測点間に対応する節点間を結ぶリンクとで表す。図２の例では、節点を丸で、リンクを矢印で表しており、節点を表す丸の中の記号は、節点の識別子を表している。
【００１８】
軌跡データ生成装置２２は、生成した複数の軌跡データを、軌跡データ記憶部２４に記憶する。軌跡データ記憶部２４は、軌跡データ生成装置２２に設けられた記憶装置であってもよいし、軌跡データ生成装置２２とは別の外部装置として設けられた記憶装置であってもよい。また、軌跡データ記憶部２４は、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ等の可搬型記憶媒体であってもよい。
【００１９】
図３に示すように、経路グラフ生成装置１０は、速度情報付与部１１と、軌跡データ探索部１２と、平面グラフ生成部１３と、コスト算出部１４とを備える。なお、速度情報付与部１１は、本発明の取得部の一例である。また、軌跡データ探索部１２及びコスト算出部１４は、本発明の判定部の一例である。また、平面グラフ生成部１３は、本発明の統合部の一例である。
【００２０】
速度情報付与部１１は、軌跡データ記憶部２４に記憶された軌跡データを取得し、各軌跡データにおいて連続する観測点間に速度情報を付与する。例えば、連続する観測点間の観測時刻から移動体が観測点間を移動するのに要した時間を計算し、各観測点の位置データから観測点間の距離を計算し、距離を時間で割った値を、観測点間の速度として観測点間に付与し、所定の記憶領域に記憶する。
【００２１】
速度情報付与部１１は、例えば、図４に示すように、観測点間に対応する軌跡のリンクの始点となる節点及び終点となる節点の識別子に、その観測点間の速度情報を対応付けたリストとして、観測点間の速度情報を記憶することができる。
【００２２】
なお、観測データの観測時に、移動体の速度も合わせて取得され、観測データが、観測点毎の速度情報も保持している場合には、連続する観測点の各々が保持する速度情報が示す速度の平均を、その観測点間の速度情報として付与してもよい。また、軌跡データに、予め観測点間の速度情報が付与されている場合は、付与されている速度情報をそのまま用いることができる。この場合、速度情報付与部１１を省略してもよい。
【００２３】
軌跡データ探索部１２は、速度情報が付与された軌跡データの集合の中から、次に平面グラフに統合する軌跡データを探索する。具体的には、軌跡データ探索部１２は、平面グラフ生成部１３により、現段階で生成されている平面グラフに統合して新たな平面グラフを生成した場合に、コスト算出部１４により算出されるコストが最小となる軌跡データを探索する。なお、以下では、コスト算出のために、現段階で生成されている平面グラフに軌跡データαを追加して生成される平面グラフを「中間の平面グラフ」という。
【００２４】
平面グラフ生成部１３は、軌跡データ探索部１２で探索された軌跡データを１つずつ順次統合していくことで、軌跡データから平面グラフを生成する。具体的には、平面グラフ生成部１３は、図５に示すように、各軌跡データが示す軌跡間の近似度が高い部分がまとまり、相互に近似しない部分経路しか持たない平面グラフを生成する。本実施形態では、軌跡間の近似度として、軌跡間の距離と軌跡を示す軌跡データに付与された速度情報が示す速度差とを用いる。なお、本実施形態では、平面グラフに軌跡データを順次統合していくため、軌跡間の距離及び速度差とは、軌跡と平面グラフ内の部分経路との距離及び速度差である。
【００２５】
平面グラフ生成部１３は、節点と、節点間を結ぶリンクとにより、複数の経路を表すグラフである。従って、平面グラフの一部は、平面グラフ全体で表される経路の一部であり、以下ではこれを「部分経路」という。平面グラフ生成部１３は、軌跡データの観測点に対応する節点を示す節点データの集合Ｖと、節点間を結ぶリンクを示すリンクデータの集合Ｅとを登録することにより、平面グラフを生成する。節点データとしては、節点の識別子を用いることができる。リンクデータとしては、リンクの両端の節点を特定したデータとして表すことができる。リンクは有向であっても無向であってもよい。リンクを有向とする場合には、例えば、リンクの始点となる節点の識別子＿終点となる節点の識別子、のような形式でリンクデータを表すことができる。
【００２６】
例えば、図５の右図に示す平面グラフでは、節点を丸、節点の識別子を丸内の記号、リンクを節点間の矢印で表している。この平面グラフをＧ＝（Ｖ，Ｅ）とすると、Ｖ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ｝、Ｅ＝｛Ａ＿Ｂ，Ｂ＿Ｃ，Ｄ＿Ｂ，Ｂ＿Ｅ，Ｂ＿Ｇ，Ｅ＿Ｆ，Ｇ＿Ｈ｝と表すことができる。
【００２７】
また、平面グラフ生成部１３は、平面グラフに付与された速度情報と、平面グラフに統合した軌跡データに付与された速度情報との平均、加重平均、最頻値等の統計値を、新たに生成した平面グラフの速度情報として、各リンクに付与する。なお、本実施形態では、統計値として平均を用いる場合について説明する。
【００２８】
コスト算出部１４は、平面グラフ生成部１３で生成された平面グラフに、ある軌跡データを統合することにより生成される平面グラフのコストを算出する。
【００２９】
詳細は後述するが、本実施形態では、軌跡データの集合を全て統合した段階で生成されている平面グラフが、最終的に出力する経路グラフとなる。経路グラフは、軌跡データ全体をよく表しつつ、できるだけ単純なグラフであることが、経路分析にとって都合がよい。例えば、図６に示すように、軌跡データそのものを表すような経路グラフ１０１は、元の軌跡データを最も忠実に再現しており、元の軌跡データに対する非近似性が最小である。しかし、経路グラフ１０１は複雑性が最大であり、経路分析に用いた際に、計算量の増大や分析精度の低下を招くおそれがある。一方、経路グラフ１０２は、元の軌跡データを最も簡潔な状態に統合しており、複雑性は最小である。しかし、経路グラフ１０２は、元の軌跡データを全く近似しておらず、経路分析に用いることはできない。
【００３０】
そこで、本実施形態では、コスト算出部１４において、複雑性及び非近似性の２つコストを勘案したコストを算出する。そして、平面グラフ生成部１３において、例えば、図６に示す平面グラフ１０３のように、複雑性と非近似性とが共に低くなり、経路分析に都合がよい平面グラフを生成する。
【００３１】
本実施形態では、コスト算出部１４は、非近似性のコストΣα∈Ｔδ（Ｇ，α）と、複雑性のコスト｜Ｇ｜とを加算したコストＣ、すなわち、コストＣ＝Σα∈Ｔδ（Ｇ，α）＋｜Ｇ｜を算出する。以下、非近似性のコストΣα∈Ｔδ（Ｇ，α）、及び複雑性のコスト｜Ｇ｜の各々について詳述する。
【００３２】
まず、非近似性のコストΣα∈Ｔδ（Ｇ，α）について説明する。上述したように、平面グラフＧは、現段階で生成されている平面グラフに軌跡データを１つずつ統合していくことで生成される。非近似性のコストΣα∈Ｔδ（Ｇ，α）におけるδ（Ｇ，α）は、ある平面グラフＧに含まれる部分経路と、軌跡データαが示す軌跡αとが近似しない程度を表す値であり、δ（Ｇ，α）の値が大きい程、近似しない程度が大きいことを表す。ある平面グラフＧに含まれる部分経路が軌跡αを完全に近似することができる場合には、δ（Ｇ，α）は０となる。
【００３３】
上述したように、本実施形態では、平面グラフＧに含まれる部分経路と軌跡αとが近似するか否かは、部分経路と軌跡との間の距離と、部分経路に付与された速度情報と軌跡αを示す軌跡データαに付与された速度情報との差とに基づいて判断する。
【００３４】
例えば、図７に示すような平面グラフＧに含まれる部分経路Πと軌跡αとのδ（Ｇ，α）について説明する。なお、部分経路Π及び軌跡αの各リンクに付与された数字は速度（ｋｍ／ｈ）を表す。
【００３５】
具体的な処理は後述するが、平面グラフ生成部１３は、まず、距離関数として、例えばフレッシェ距離等を用いて、部分経路Πと軌跡αとの距離が予め定めた閾値ε以下となる距離近似領域１０４を抽出する。
【００３６】
平面グラフ生成部１３は、さらに、距離近似領域１０４内において、部分経路Πと軌跡αとで、距離が近い節点同士を対応付ける。そして、平面グラフ生成部１３は、対応付けが行われた節点間で表される、部分経路Πと軌跡αとで対応する区間において、部分経路Πに付与された速度と、軌跡αに付与された速度とを比較する。そして、平面グラフ生成部１３は、部分経路Πに付与された速度と、軌跡αに付与された速度との速度差が予め定めた閾値ｖｔｈ以下となる近似領域を抽出する。
【００３７】
ここで、図７に示す距離近似領域１０４内では、軌跡データαの観測間隔が大きいために、軌跡αの節点と部分経路Πの節点とが１対１で対応しておらず、図８に示すように、対応する区間内で、部分経路Πに付与された速度が異なる部分が生じている。この場合において、対応する区間内の速度を単純に比較する場合、対応する区間内の速度の平均をとった上で、比較することが考えられる。図８の例では、軌跡αにおける対応する区間内の速度は、リンクｐ１３＿ｐ１４に付与された速度「５０」そのままである。一方、部分経路Πにおける対応する区間内の速度は、リンクｐ２＿ｐ３に付与された速度「４０」と、リンクｐ３＿ｐ４に付与された速度「８０」との平均で、「６０」となる。従って、対応する区間における部分経路Πと軌跡αとの速度差は「１０」であり、例えば、閾値ｖｔｈが１０の場合には、距離近似領域１０４と同じ領域が近似領域として抽出されることになる。
【００３８】
しかし、図８の例では、部分経路Πのリンクｐ３＿ｐ４に付与された速度「８０」と、軌跡αのリンクｐ１３＿ｐ１４に付与された速度「５０」との差は「３０」であり、閾値ｖｔｈを超えている。上記のように、対応する区間内の速度の平均をとる例では、この部分まで近似領域として抽出してしまい、速度情報も考慮した部分経路Πと軌跡αとの非近似性を精度良く算出できない。図８の例では、部分経路Πに速度が異なる部分が存在する例であるが、この問題は、軌跡αに速度が異なる部分が存在する場合にも同様に生じ得る。
【００３９】
そこで、本実施形態では、部分経路及び軌跡のいずれか一方の速度が異なる部分に対応して、他方のリンク上に節点を追加し、追加された節点により分割されたリンクに対して、元のリンクに付与されていた速度情報を付与する。例えば、図９に示すように、部分経路Πにおいて、速度が変化する箇所に相当する節点ｐ３に対応する節点ｑ３を、軌跡αのリンクｐ１３＿ｐ１４上に追加する。追加する節点の位置は、例えば、対応する節点との距離が最小となるリンク上の位置とすることができる。そして、リンクｐ１３＿ｑ３及びリンクｑ３＿ｐ１４の各々に、元のリンクｐ１３＿ｐ１４に付与された速度「５０」を付与する。
【００４０】
これにより、図１０に示すように、部分経路Πと軌跡αとの距離の近さに加え、速度差が小さい近似領域１０５を精度良く抽出することができる。
【００４１】
コスト算出部１４は、平面グラフＧに含まれる部分経路Πと軌跡αとの非近似性の程度を表す値δ（Ｇ，α）を、軌跡αのうち、平面グラフＧに含まれる部分経路Πに近似できなかった部分の要素に基づいて計算する。例えば、軌跡αのうち、近似領域１０５に含まれない節点の数、リンクの数、節点の数とリンクの数との和、近似領域１０５に含まれない部分のリンク長の和などとすることができる。また、近似領域１０５に含まれないに軌跡αの全ての節点に所定面積の円を想定し、リンクが存在する場合には各リンクを長手方向の中心軸とした長方形を想定し、これら想定した円や長方形の面積の合計をδ（Ｇ，α）としてもよい。さらに、近似領域１０５に含まれない軌跡αの節点の中で、近似領域１０５から最も離れている節点までの距離をδ（Ｇ，α）としてもよい。また、これらを組み合わせたものをδ（Ｇ，α）としてもよい。本実施形態では、近似領域１０５に含まれない節点の数をδ（Ｇ，α）とする場合について説明する。図１０の例では、軌跡αの節点ｐ１４が近似領域１０５に含まれないため、δ（Ｇ，α）＝１となる。
【００４２】
非近似性のコストΣα∈Ｔδ（Ｇ，α）は、平面グラフＧに対して、まだ統合されていない軌跡データの各々について算出したδ（Ｇ，α）の合計である。従って、非近似性のコストΣα∈Ｔδ（Ｇ，α）が小さいほど、ある平面グラフＧは、未統合の軌跡データの各々をよく近似したものとなる。
【００４３】
次に、複雑性のコスト｜Ｇ｜を説明する。複雑性のコスト｜Ｇ｜は、平面グラフＧの複雑さの度合いを示す値である。コスト算出部１４は、複雑性のコスト｜Ｇ｜として、平面グラフＧに含まれる節点の数、リンクの数、リンク長の和、またはこれらの組み合わせを算出することができる。本実施形態では、平面グラフＧに含まれる節点の数を、複雑性のコスト｜Ｇ｜とする場合について説明する。
【００４４】
本実施形態では、非近似性のコストΣα∈Ｔδ（Ｇ，α）と、複雑性のコスト｜Ｇ｜との和をコストＣとする場合について説明するが、非近似性のコストΣα∈Ｔδ（Ｇ，α）と、複雑性のコスト｜Ｇ｜との統合方法はこれに限定されない。例えば、下記に示すように、２つのコストの重みつき和として、コストＣを算出してもよい。
Ｃ＝Σα∈Ｔδ（Ｇ，α）＋λ｜Ｇ｜   （ただし、λ＞０：定数）
この場合、後述する軌跡データの探索がすぐに終わってしまう場合などの回避策としてλを微調整することができる。
【００４５】
また、２つのコストの積により、コストＣを算出してもよく、２つのコストの物理的な意味に応じて適切な統合方法を選択すればよい。本実施形態では、２つのコストが、節点やリンクなどの要素の数を用いており、２つのコストの各々が持つ物理的な意味が同じであるため、本実施形態で採用する和や、上記の重み付き和などによるコストの統合が適している。
【００４６】
経路グラフ生成装置１０は、例えば図１１に示すコンピュータ４０で実現することができる。コンピュータ４０はＣＰＵ４１、一時記憶領域としてのメモリ４２、及び不揮発性の記憶部４３を備える。また、コンピュータ４０は、入出力装置４８が接続される入出力インターフェース（Ｉ／Ｆ）４４を備える。また、コンピュータ４０は、記録媒体４９に対するデータの読み込み及び書き込みを制御するｒｅａｄ／ｗｒｉｔｅ（Ｒ／Ｗ）部４５、及びインターネット等のネットワークに接続されるネットワークＩ／Ｆ４６を備える。ＣＰＵ４１、メモリ４２、記憶部４３、入出力Ｉ／Ｆ４４、Ｒ／Ｗ部４５、及びネットワークＩ／Ｆ４６は、バス４７を介して互いに接続される。
【００４７】
記憶部４３はＨＤＤ（Hard Disk Drive）、ＳＳＤ（solid state drive）、フラッシュメモリ等によって実現できる。記憶媒体としての記憶部４３には、コンピュータ４０を経路グラフ生成装置１０として機能させるための経路グラフ生成プログラム５０が記憶される。なお、経路グラフ生成プログラム５０は、本発明の移動経路統合プログラムの一例である。
【００４８】
ＣＰＵ４１は、経路グラフ生成プログラム５０を記憶部４３から読み出してメモリ４２に展開し、経路グラフ生成プログラム５０が有するプロセスを順次実行する。経路グラフ生成プログラム５０は、速度情報付与プロセス５１と、軌跡データ探索プロセス５２と、平面グラフ生成プロセス５３と、コスト算出プロセス５４とを有する。
【００４９】
ＣＰＵ４１は、速度情報付与プロセス５１を実行することで、図３に示す速度情報付与部１１として動作する。また、ＣＰＵ４１は、軌跡データ探索プロセス５２を実行することで、図３に示す軌跡データ探索部１２として動作する。また、ＣＰＵ４１は、平面グラフ生成プロセス５３を実行することで、図３に示す平面グラフ生成部１３として動作する。また、ＣＰＵ４１は、コスト算出プロセス５４を実行することで、図３に示すコスト算出部１４として動作する。これにより、経路グラフ生成プログラム５０を実行したコンピュータ４０が、経路グラフ生成装置１０として機能することになる。
【００５０】
なお、経路グラフ生成装置１０は、例えば半導体集積回路、より詳しくはＡＳＩＣ（Application Specific Integrated Circuit）等で実現することも可能である。
【００５１】
次に、本実施形態に係る経路グラフ生成システム２０の作用について説明する。軌跡データ生成装置２２が、複数のセンサ２６の各々で観測された観測データを、ネットワーク２８を介して取得し、観測データから軌跡データを生成して、軌跡データ記憶部２４に記憶する。経路グラフ生成装置１０に、軌跡データ記憶部２４に記憶された軌跡データ集合Ｔが入力されると、経路グラフ生成装置１０において、図１２に示す経路グラフ生成処理が実行される。なお、経路グラフ生成装置１０において実行される経路グラフ生成処理は、本発明の移動経路統合方法の一例である。
【００５２】
図１２に示す経路グラフ生成処理のステップＳ１０で、速度情報付与部１１が、入力された軌跡データ集合Ｔを受け付ける。そして、速度情報付与部１１が、軌跡データ集合Ｔに含まれる各軌跡データについて、連続する観測点間の観測時刻から観測点間の移動に要した時間を計算し、各観測点の位置データから観測点間の距離を計算する。そして、速度情報付与部１１は、計算した距離を計算した時間で割った値を、観測点間の速度として観測点間に付与し、所定の記憶領域に記憶する。
【００５３】
次に、ステップＳ１５で、軌跡データ探索部１２が、経路グラフ生成処理で使用する作業変数の初期化として、平面グラフＧ＊を構成する節点の集合Ｖ＊と、リンクの集合Ｅ＊を空集合に設定する。なお、以下では、平面グラフＧ＊は、探索された軌跡データα＊を追加することにより生成される平面グラフを表す。また、「＊」を付していない平面グラフＧは、コストを算出するために生成される中間の平面グラフを表し、Ｇ＝（Ｖ，Ｅ）とする。また、軌跡データ探索部１２は、平面グラフＧのコストＣの最小値を示す最小コストｍｉｎＣに十分大きな値、例えば無限大を設定する。
【００５４】
次に、ステップＳ２０で、軌跡データ探索部１２が、軌跡データ集合Ｔが空集合か否かを判定する。空集合ではない場合には、処理はステップＳ３０へ移行し、図１３に詳細を示す軌跡データ探索処理が実行される。
【００５５】
図１３に示す軌跡データ探索処理のステップＳ３１で、軌跡データ探索部１２が、軌跡データ探索処理で使用する作業変数の初期化として、探索結果となる軌跡データを示すα＊に「Ｎｏｎｅ」を設定する。
【００５６】
次に、ステップＳ３２で、軌跡データ探索部１２が、軌跡データ集合Ｔの中に、探索が未処理の軌跡データが存在するか否かを判定する。未処理の軌跡データが存在する場合には、処理はステップＳ３３へ移行し、軌跡データ探索部１２が、軌跡データ集合Ｔから未処理の軌跡データを１つ選択して、軌跡データαに設定する。次に、ステップＳ３４で、図１４に詳細を後述する軌跡データ追加処理が実行される。
【００５７】
図１４に示す軌跡データ追加処理のステップＳ５１で、平面グラフ生成部１３が、処理対象を示す節点ｐにｎｉｌ（無）を設定すると共に、節点ｓに、上記ステップＳ３３で設定された軌跡データαが示す軌跡αの始点を設定する。なお、節点ｐは、軌跡αにおける節点ｓの１つ前の節点である。また、平面グラフ生成部１３は、平面グラフＧ＊を、コスト計算用の中間の平面グラフＧに設定する。次に、ステップＳ５２で、平面グラフＧに含まれる部分経路Πと軌跡αとの近似領域１０５を抽出するための、図１５に詳細を示す近似領域抽出処理が実行される。
【００５８】
図１５に示す近似領域抽出処理のステップＳ５２１で、平面グラフ生成部１３が、近似領域抽出処理で使用する作業変数を初期化する。具体的には、平面グラフ生成部１３は、部分経路Πの近似領域１０５に含まれる経路πを構成する節点の集合Ｖπを空集合に設定する。
【００５９】
次に、ステップＳ５２２で、平面グラフ生成部１３が、例えば、図７に示すように、平面グラフＧに含まれる部分経路Πと軌跡αとの距離が予め定めた閾値ε以下となる距離近似領域１０４を抽出する。軌跡αからの距離がε以内にある経路を効率よく探索するアルゴリズムとして、フレッシェ距離を用いたアルゴリズムが知られており、本実施形態ではこれを用いる。このアルゴリズムの計算量は，軌跡αの長さと平面グラフＧのサイズに比例する。
【００６０】
具体的な距離近似領域１０４の抽出方法を、図１６を参照して説明する。図１６において、丸で表した節点は平面グラフＧの節点、四角で表した節点は軌跡αの節点である。平面グラフ生成部１３は、図１６に示すように、軌跡αの始点である節点ｓを中心とする半径εの円内にある平面グラフＧの節点ｔ１が抽出される。続いて、この節点ｔ１とリンクによって接続された節点で、かつその節点を中心とした半径εの円が節点ｔ１を中心とする円及び軌跡αと交差する節点を探索し、節点ｔ２が抽出される。このように、軌跡αとの距離がε以内となる平面グラフＧの節点を、軌跡αの始点である節点ｓから幅優先探索で繰り返し探索することにより、節点ｔ３，ｔ４，ｔ５，ｔ６，ｔ７が抽出される。そして、軌跡αの終点である節点ｇを含む円の中心となる節点ｔ８が抽出された段階で、節点の探索を終了する。そして、抽出された節点のうち、節点ｓに対応する節点ｔ１から節点ｇに対応する節点ｔ８までを結ぶ経路ｔ１，ｔ２，ｔ３，ｔ５，ｔ７，ｔ８が得られ、この経路、及び軌跡αを含む領域が距離近似領域１０４として抽出される。
【００６１】
なお、軌跡αの始点である節点ｓとの距離がε以内の平面グラフの節点が存在しない場合には、節点ｓの次の節点を始点に置き換えて、同様の処理を行う。また、軌跡αの終点である節点ｇとの距離がε以内の平面グラフの節点が存在しない場合には、距離がε以内の平面グラフの節点が最後に探索できた軌跡αの節点を終点とすればよい。
【００６２】
次に、ステップＳ５２３で、平面グラフ生成部１３が、上記ステップＳ５２２で距離近似領域１０４が抽出できたか否かを判定する。抽出できた場合には、処理はステップＳ５２４へ移行し、抽出できなかった場合には、処理はステップＳ５３８へ移行する。
【００６３】
ステップＳ５２４では、平面グラフ生成部１３が、距離近似領域１０４において、軌跡αの節点と、その節点との距離がε以内で最も距離が近い部分経路Πの節点とを対応付ける。なお、この節点同士の対応付けは、フレッシェ距離を用いた距離近似領域１０４の抽出時に同時に行うことができ、高速な対応付けを実現することができる。軌跡αの節点との距離がε以内となる部分経路Πの節点が存在しない場合には、平面グラフ生成部１３は、例えば、軌跡αの節点との距離がε以内となる節点を、部分経路Π上に追加した上で、節点同士を対応付ける。平面グラフ生成部１３は、節点ｓから順に、軌跡αの節点を節点ｓ１，ｓ２，・・・ｓｎ（ｎは距離近似領域１０４に含まれる軌跡αの節点の数）とする。また、平面グラフ生成部１３は、節点ｓに対応する部分経路Πの節点から順に、経路の節点を節点ｔ１，ｔ２，・・・ｔｍ（ｍは距離近似領域１０４に含まれる部分経路Πの節点の数、追加された節点も含む）とする。
【００６４】
より具体的な例を挙げて説明する。図１７に示すように、軌跡αと部分経路Πとの距離近似領域１０４が抽出されたとする。軌跡αと部分経路Πとで、節点ｐ２とｐ９、節点ｐ３とｐ１０、節点ｐ４とｐ１２、節点ｐ５とｐ１３、節点ｐ７とｐ１４とがそれぞれ対応している。また、軌跡αの節点ｐ６には、距離がε以内となる部分経路Πの節点が存在しないとする。そこで、部分経路Π上に、節点ｐ６との距離がε以内となる節点ｕ６を追加する。節点ｕ６を追加する位置は、部分経路Πのリンク上で、節点ｐ６との距離が最も近い位置とすることができる。また、軌跡αの節点ｐ６の前後の節点ｐ５とｐ７とに対応する部分経路Πのリンクｐ１３＿ｐ１４上で、節点ｐ１３と節点ｕ６と、節点ｕ６と節点ｐ１４との距離の比が、リンクｐ５＿ｐ６とリンクｐ６＿ｐ７との長さの比と等しくなる内分点としてもよい。
【００６５】
次に、ステップＳ５２５で、平面グラフ生成部１３が、変数ｉに１を設定する。次に、ステップＳ５２６で、平面グラフ生成部１３が、軌跡αの節点ｓｉ及び節点ｓｉ＋１に対応する部分経路Πの節点ｔａ及びｔｂを抽出する。図１７の例では、ｉ＝１の場合、節点ｔａとして節点ｔ１（ｐ９）が、節点ｔｂとして節点ｔ２（ｐ１０）が抽出される。
【００６６】
次に、ステップＳ５２７で、平面グラフ生成部１３が、節点ｔａと節点ｔｂとの間に、部分経路Πの他の節点ｔｃが存在するか否かを判定する。節点ｔｃが存在しない場合には、処理はステップＳ５２８へ移行し、節点ｔｃが存在する場合には、処理はステップＳ５３３へ移行する。
【００６７】
ステップＳ５２８では、平面グラフ生成部１３が、図１８に示すように、リンクｓｉ＿ｓｉ＋１の速度ｖｓ、及びリンクｔａ＿ｔｂの速度ｖｔを、軌跡データα及び平面グラフＧに付与され、所定の記憶領域に記憶されている速度情報から取得する。次に、ステップＳ５２９で、平面グラフ生成部１３が、リンクｓｉ＿ｓｉ＋１の速度ｖｓとリンクｔａ＿ｔｂの速度ｖｔとの速度差が、予め定めた閾値ｖｔｈ以下か否かを判定する。速度差が閾値ｖｔｈ以下の場合には、処理はステップＳ５３０へ移行し、速度差が閾値ｖｔｈを超える場合には、処理はステップＳ５３１へ移行する。
【００６８】
ステップＳ５３０では、平面グラフ生成部１３が、節点ｓｉ、ｔａ、リンクｓｉ＿ｓｉ＋１、及びリンクｔａ＿ｔｂを含む範囲（図１８の破線１０６）を近似領域１０５の一部であると判定する。近似領域１０５に含まれる部分経路Πの部分が、経路πであるため、平面グラフ生成部１３が、節点ｔａを示す節点データを経路πの節点集合Ｖπに追加する。
【００６９】
次に、ステップＳ５３１で、ｉ＋１がｎか否かを判定することにより、節点ｓｉ＋１が距離近似領域１０４における軌跡αの終点である節点か否かを判定する。ｉ＋１がｎの場合には、処理はステップＳ５３８へ移行する。ｉ＋１がｎに到達していない場合には、処理はステップＳ５３２へ移行し、平面グラフ生成部１３が、変数ｉを１インクリメントして、処理はステップＳ５２６に戻る。
【００７０】
例えば、図１９に示すように、ｉ＝２の場合には、節点ｔａである節点ｔ２（ｐ１０）と節点ｔｂである節点ｔ４（ｐ１２）との間には、節点ｔｃとなる節点ｔ３（ｐ１１）が存在するため、上記ステップＳ５２７で肯定判定されて、処理はステップＳ５３３へ移行する。
【００７１】
ステップＳ５３３では、平面グラフ生成部１３が、節点ｔａと節点ｔｂとの間の全てのリンクの速度情報を取得する。例えば、図１９の例では、平面グラフ生成部１３は、リンクｔａ＿ｔｃの速度ｖｔ１、リンクｔｃ＿ｔｂの速度ｖｔ２を取得する。なお、節点ｔｃが複数存在する場合には、リンクｔｃｊ＿ｔｃｊ＋１（ｊ＝１，２，・・・，Ｊ−１、Ｊは節点ｔｃの数）の速度も取得する。そして、平面グラフ生成部１３は、節点ｔａと節点ｔｂとの間のリンクの速度が全て同じか否かを判定する。全て同じ場合には、処理はステップＳ５３４へ移行し、速度が異なるリンクが含まれる場合には、処理はステップＳ５３７へ移行する。
【００７２】
ステップＳ５３４では、平面グラフ生成部１３が、リンクｓｉ＿ｓｉ＋１の速度ｖｓ、及び節点ｔａとｔｂとの間に含まれるいずれかのリンクの速度ｖｔを取得する。次に、ステップＳ５３５で、平面グラフ生成部１３が、速度ｖｓと速度ｖｔとの速度差が、予め定めた閾値ｖｔｈ以下か否かを判定する。速度差が閾値ｖｔｈ以下の場合には、処理はステップＳ５３６へ移行し、速度差が閾値ｖｔｈを超える場合には、処理はステップＳ５３１へ移行する。
【００７３】
ステップＳ５３６では、平面グラフ生成部１３が、節点ｓｉ、ｔａ、ｔｃ、リンクｓｉ＿ｓｉ＋１、及び節点ｔａと節点ｔｂとの間の全てのリンク含む範囲（図１９の破線１０７）を近似領域１０５の一部であると判定する。そして、平面グラフ生成部１３が、節点ｔａ及び節点ｔｃを示す節点データを経路πの節点集合Ｖπに追加し、処理はステップＳ５３１へ移行する。
【００７４】
一方、節点ｔａと節点ｔｂとの間に、速度が異なるリンクが含まれると判定されて、処理がステップＳ５３７へ移行した場合には、平面グラフ生成部１３が、節点ｔｃに対応する節点を軌跡αのリンクｓｉ＿ｓｉ＋１上に追加する。さらに、平面グラフ生成部１３は、節点ｓ１から順に、軌跡αの節点を節点ｓ１，ｓ２，・・・，ｓｎ（ｎは距離近似領域１０４に含まれる軌跡αの節点の数、追加した節点を含む）と振り直す。節点の追加は、上記ステップＳ５２４において、軌跡αの節点に対応して、部分経路Π上に節点を追加した方法と同様に行うことができる。節点を追加すると、処理はステップＳ５２６に戻る。
【００７５】
例えば、図２０に示すように、部分経路Π上の節点ｔｃである節点ｔ３（ｐ１１）に対応する節点ｑ６を軌跡αのリンクｓｉ＿ｓｉ＋１上に追加し、ｓ１，ｓ２，・・・，ｓｎを振り直す。節点ｔｃが複数存在する場合には、節点ｔｃの各々に対応する節点の各々を軌跡αのリンクｓｉ＿ｓｉ＋１上に追加する。この後、処理がステップＳ５２６に戻ることにより、図２０に示すように、部分経路Πのリンクに付与された速度が異なる部分（図２０中の破線１０８Ａと１０８Ｂ）毎に、速度を比較して近似領域１０５を抽出する処理が行われる。
【００７６】
ステップＳ５３８では、平面グラフ生成部１３が、部分経路Πのうち近似領域１０５に含まれる経路πとして、節点集合Ｖπを出力する。上記ステップＳ５２３で距離近似領域１０４が抽出できなかった場合、またはステップＳ５２９もしくはＳ５３５で近似領域１０５の一部が抽出できなかった場合には、Ｖπとして空集合が出力され、近似領域１０５が抽出されなかったことを表す。そして、処理は図１４に示す軌跡データ追加処理に戻る。
【００７７】
次に、図１４に示す軌跡データ追加処理のステップＳ５４で、平面グラフ生成部１３が、節点ｓが近似領域１０５に含まれるか否かを判定する。具体的には、上記ステップＳ５２の処理で出力された経路πの節点集合Ｖπに、節点ｓに対応する部分経路Πの節点が含まれる場合には、節点ｓは近似領域１０５内に含まれると判定することができる。上記ステップＳ５２で出力された経路πの節点集合Ｖπが空集合の場合、すなわち近似領域１０５が抽出されていない場合や、節点ｓが近似領域１０５外に存在する場合には、否定判定されて、処理はステップＳ５６へ移行する。例えば、図２１に示すように近似領域１０５が抽出されている場合において、節点ｐがｎｉｌ、節点ｓがｐ１の場合には、節点ｓは近似領域１０５外と判定されて、ステップＳ５６へ移行する。
【００７８】
ステップＳ５６では、平面グラフ生成部１３が、節点ｐが「ｎｉｌ」ではないか否かを判定し、ｐがｎｉｌではない場合には、処理はステップＳ５７へ移行する。節点ｐがｎｉｌの場合には、処理はステップＳ５９へ移行する。上記の例では、節点ｐがｎｉｌであるため、否定判定されて、処理はステップＳ５９へ移行する。
【００７９】
ステップＳ５９では、平面グラフ生成部１３が、節点ｓを節点ｐに設定し、節点ｓの直後の節点を節点ｓに設定する。上記の図２１の例では、節点ｐ＝ｐ１、節点ｓ＝ｐ２に設定される。次に、ステップＳ６０で、平面グラフ生成部１３が、節点ｓが軌跡αの終点か否かを判定する。節点ｓが軌跡αの終点ではない場合には、処理はステップＳ５４に戻る。
【００８０】
節点ｐ２は近似領域１０５には含まれず、節点ｐ１はｎｉｌではないため、処理はステップＳ５７へ移行する。ステップＳ５７では、平面グラフ生成部１３が、節点ｐを節点集合Ｖに追加すると共に、リンクｐ＿ｓをリンク集合Ｅに追加し、コスト算出部１４が、コスト変数Ａに１加算する。ここでは、節点ｐ１が節点集合Ｖに追加され、リンクｐ１＿ｐ２がリンク集合Ｅに追加される。
【００８１】
次に、ステップＳ５８で、平面グラフ生成部１３が、リンク集合Ｅに追加したリンクｐ＿ｓに、軌跡αのリンクｐ＿ｓに付与されている速度情報を付与し、頻度１とする。なお、頻度とは、平面グラフの各リンクに対して軌跡データが統合された回数を表す。軌跡データが統合される都度、リンクに付与された速度を更新する際に用いる情報である。図２１では、平面グラフＧのリンクに付与した前の数字が速度、後ろの数字が頻度である。図２１の例では、リンク集合Ｅに追加されたリンクｐ１＿ｐ２に対して、「６０，１」という速度情報が付与される。
【００８２】
次のステップＳ５９で、平面グラフ生成部１３が、節点ｐ＝ｐ２、節点ｓ＝ｐ３に設定すると、節点ｐ３は近似領域１０５に含まれるため、上記ステップＳ５４で肯定判定されて、処理はステップＳ６１へ移行する。
【００８３】
ステップＳ６１では、平面グラフ生成部１３が、節点ｐが「ｎｉｌ」ではないか否かを判定し、ｐがｎｉｌではない場合には、処理はステップＳ６２へ移行する。節点ｐがｎｉｌの場合には、処理はステップＳ６８へ移行する。ここでは、節点ｐ＝ｐ２であるため、処理はステップＳ６２へ移行する。
【００８４】
ステップＳ６２では、平面グラフ生成部１３が、節点ｐを節点集合Ｖに追加し、コスト算出部１４が、コスト変数Ａに１加算する。ここでは、節点ｐ２が節点集合Ｖに追加される。
【００８５】
次に、ステップＳ６３で、平面グラフ生成部１３が、近似領域１０５に含まれる軌跡αの節点列をｓ１，ｓ２，・・・，ｓｎとし、経路πの節点列をｔ１，ｔ２，・・・，ｔｍとする。そして、平面グラフ生成部１３が、節点ｐを節点ｔ０に設定し、リンクｔ０＿ｔ１をリンク集合Ｅに追加すると共に、速度０及び頻度０をリンクｔ０＿ｔ１の速度情報として付与する。図２１の例で、節点ｐがｐ２の場合、平面グラフ生成部１３が、リンクｐ２＿ｐ１０をリンク集合Ｅに追加し、速度０及び頻度０の速度情報を付与する。この速度情報は、節点ｐ１０が節点集合Ｖに含まれる場合、後述の処理により、リンクｐ２＿ｐ３に付与された速度及び頻度１（８０，１）に更新される。
【００８６】
ステップＳ６４では、平面グラフ生成部１３が、節点ｔｉ＋１が平面グラフＧの節点集合Ｖに含まれるか否かを判定する。ここで、ｉは、０，１，・・・，ｍ−１であり、各ｉについて以下のステップＳ６６〜Ｓ６７、またはステップＳ６５の判定により、ステップＳ６９〜Ｓ７２及びＳ６６〜Ｓ６７の処理を実行する。節点ｔｉ＋１が平面グラフＧの節点集合Ｖに含まれる場合には、処理はステップＳ６６へ移行する。節点ｔｉ＋１が上述の近似領域抽出処理（図１５）のステップＳ５２４における節点同士の対応付けの際に追加された節点の場合には、節点集合Ｖには含まれないため、否定判定されて、処理はステップＳ６５へ移行する。
【００８７】
ステップＳ６６では、平面グラフ生成部１３が、節点ｔｉ及びｔｉ＋１を含むリンクをリンク集合Ｅから取得し、リンクｈ＿ｈ’に設定する。
【００８８】
次に、ステップＳ６７で、平面グラフ生成部１３が、節点ｔｉ及びｔｉ＋１に対応する軌跡αの節点ｓｉ’及びｓｉ＋１’を抽出する。ここで、図２１に示すように、例えば節点ｔ３（ｐ１２）には対応付けられた軌跡αの節点は存在しない。これは、リンクｐ１１＿ｐ１２と、リンクｐ１２＿ｐ１３とで速度が変化しないため、上記近似領域抽出処理（図１５）のステップＳ５３３及びＳ５３４で、軌跡αに節点を追加することなく対応付けが行われたものである。このような場合には、節点ｔｉに対応する軌跡αの節点ｓｉ’として、節点ｔｉの前で軌跡αの節点との対応付けが行われている、節点ｔｉに最も近い節点に対応する軌跡αの節点を抽出すればよい。同様に、節点ｔｉ＋１に対応する軌跡αの節点ｓｉ＋１’として、節点ｔｉ＋１の後で軌跡αの節点との対応付けが行われている、節点ｔｉ＋１に最も近い節点に対応する軌跡αの節点を抽出すればよい。図２１の例では、節点ｔｉが節点ｐ１１の場合、及び節点ｐ１２の場合は、いずれも節点ｓｉ’及びｓｉ＋１’として、節点ｐ４及びｐ５が抽出される。
【００８９】
そして、平面グラフ生成部１３は、リンクｓｉ’＿ｓｉ＋１’に付与された速度ｖ’と、リンクｈ＿ｈ’の速度ｖ及び頻度ｋとを取得し、リンクｈ＿ｈ’の速度を、（ｋ×ｖ＋ｖ’）／ｋ＋１で更新する。さらに、平面グラフ生成部１３は、リンクｈ＿ｈ’の頻度ｋに１加算し、処理はステップＳ６８へ移行する。
【００９０】
一方、ステップＳ６５では、平面グラフ生成部１３が、ｉ＋１が１またはｍのいずれかと等しいか否かを判定する。ｉ＋１が１またはｍのいずれかと等しい場合には、処理はステップＳ６９へ移行する。
【００９１】
ステップＳ６９では、平面グラフ生成部１３が、節点ｔｉ及びｔｉ＋１を含むリンクをリンク集合Ｅから取得し、リンクｈ＿ｈ’に設定する。図２１の例で、ｔｉ＋１である節点ｔ５（ｕ６）が節点集合Ｖに含まれないとすると、リンク集合Ｅから、リンクｐ１３＿ｐ１４を取得し、これをリンクｈ＿ｈ’とする。
【００９２】
次に、ステップＳ７０で、平面グラフ生成部１３が、節点ｔｉ＋１を節点集合Ｖに追加し、コスト算出部１４が、コスト変数Ａに１を加算する。次に、ステップＳ７１で、平面グラフ生成部１３が、節点ｈと追加した節点ｔｉ＋１とを結ぶリンクｈ＿ｔｉ＋１、及び節点ｔｉ＋１と節点ｈ’とを結ぶリンクｔｉ＋１＿ｈ’をリンク集合Ｅに追加すると共に、リンクｈ＿ｈ’をリンク集合Ｅから削除する。
【００９３】
次に、ステップＳ７２で、平面グラフ生成部１３が、リンクｈ＿ｈ’に付与された速度及び頻度を取得し、リンクｈ＿ｔｉ＋１及びｔｉ＋１＿ｈ’に取得した速度及び頻度を付与する。そして、ステップ６６へ移行する。
【００９４】
上記の節点ｔｉ＋１が節点ｕ６の例では、リンクｐ１３＿ｐ１４が削除され、リンクｐ１３＿ｕ６及びリンクｕ６＿ｐ１４が追加される。そして、リンクｐ１３＿ｕ６に対応する軌跡αのリンクｐ５＿ｐ６の速度６０と、元のリンクｐ１３＿ｐ１４の速度情報（速度５０、頻度１）とに基づいて、リンクｐ１３＿ｕ６の速度情報が、速度５５、頻度２と更新される。
【００９５】
次に、ステップＳ６８で、平面グラフ生成部１３が、節点ｔｍを節点ｐに、節点ｓｎの直後の節点を節点ｓに設定し、処理はステップＳ６０へ移行する。節点ｓが軌跡αの終点の場合には、ステップＳ６０で肯定判定されて、処理は図１３に示す軌跡データ探索処理に戻る。
【００９６】
なお、図１３のステップＳ３４で実行される軌跡データ追加処理では、コストの算出は不要であるため、上記ステップＳ５７、Ｓ６２、Ｓ６５、Ｓ７０においてコスト変数Ａに１加算する処理は省略してもよい。
【００９７】
次に、図１３に示す軌跡データ探索処理のステップＳ３５で、詳細を図２２に示す軌跡データ集合追加処理が実行される。
【００９８】
図２２に示す軌跡データ集合追加処理のステップＳ８１で、コスト算出部１４が、コスト変数Ａ及びコストＣを０に初期化する。
【００９９】
次に、ステップＳ８２で、軌跡データ探索部１２が、軌跡データ集合Ｔのうち、上記軌跡データ探索処理（図１３）のステップＳ３３で選択された軌跡データ以外で、平面グラフＧへの追加が未処理の軌跡データが存在するか否かを判定する。未処理の軌跡データが存在する場合には、処理はステップＳ８３へ移行する。
【０１００】
ステップＳ８３では、軌跡データ探索部１２が、軌跡データ集合Ｔから、上記ステップＳ３３で選択された軌跡データ以外で未処理の軌跡データを１つ選択して、軌跡データαに設定する。次に、ステップＳ８４で、図１４に示す軌跡データ追加処理が実行される。
【０１０１】
未処理の軌跡データがなくなると、ステップＳ８２で否定判定されて、処理はステップＳ８５へ移行する。ステップＳ８５では、コスト算出部１４が、平面グラフＧの複雑性のコスト｜Ｇ｜として、例えば平面グラフＧに含まれる節点の数を算出し、コスト変数Ａと加算して、コストＣを算出する。そして、処理は図１３に示す軌跡データ探索処理に戻る。
【０１０２】
次に、図１３に示す軌跡データ探索処理のステップＳ３６で、軌跡データ探索部１２が、コストＣが最小コストｍｉｎＣより小さいか否かを判定する。Ｃ＜ｍｉｎＣの場合には、処理はステップＳ３７へ移行し、平面グラフ生成部１３が、平面グラフＧ＊に追加する軌跡データα＊に、上記ステップＳ３３で選択したαを設定し、処理はステップＳ３２に戻る。Ｃ≧ｍｉｎＣの場合には、そのままステップＳ３２に戻る。
【０１０３】
未処理の軌跡データがなくなると、ステップＳ３２で否定判定されて、処理はステップＳ３８へ移行する。ステップＳ３８では、軌跡データ探索部１２が、軌跡データα＊及びその軌跡データα＊を追加した平面グラフＧ＊のコストＣ＊を出力して、図１２の経路グラフ生成処理に戻る。
【０１０４】
次に、図１２に示す経路グラフ生成処理のステップＳ４０で、平面グラフ生成部１３が、コストＣ＊が最小コストｍｉｎＣより小さいか否かを判定する。Ｃ＊＜ｍｉｎＣの場合には、処理はステップＳ５０へ移行し、平面グラフ生成部１３が、軌跡データα＊について、図１４に示す軌跡データ追加処理を実行する。なお、本ステップにおいて実行される軌跡データ追加処理のステップＳ５１において、平面グラフＧに平面グラフＧ＊を設定する処理は省略する。従って、図１４に示す軌跡データ追加処理の各ステップにおけるＶはＶ＊に、ＥはＥ＊に読み替える。
【０１０５】
ステップＳ６０で、軌跡データ探索部１２が、軌跡データ集合Ｔから、軌跡データα＊を削除し、最小コストｍｉｎＣにコストＣ-＊を設定し、処理はステップＳ２０に戻る。
【０１０６】
上記ステップＳ４０で、Ｃ＊≧ｍｉｎＣと判定された場合には、コストＣが前回ループ時の平面グラフＧ＊から下がっていないため、ループを停止し、処理はステップＳ８０へ移行する。ステップＳ８０では、平面グラフ生成部１３が、軌跡データ集合Ｔに残っている軌跡データを対象に、図２２に示す軌跡データ集合追加処理を実行する。なお、本ステップで実行される軌跡データ集合追加処理のステップＳ８４で実行される軌跡データ追加処理においても、各ステップにおけるＶはＶ＊に、ＥはＥ＊に読み替える。軌跡データ集合追加処理が終了すると、処理はステップＳ９０へ移行する。
【０１０７】
また、上記ステップＳ２０で肯定判定された場合も、処理はステップＳ９０へ移行する。
【０１０８】
ステップＳ９０では、現段階で生成されている平面グラフＧ＊を、最終的な経路グラフとして、平面グラフＧ＊について計算されたコストＣ＊と共に出力し、経路グラフ生成処理を終了する。
【０１０９】
以上の処理をより具体的な例を用いて説明する。
【０１１０】
例えば、図２に示すような複数の軌跡α１，α２，α３，α４を示す、下記の軌跡データ集合Ｔが経路グラフ生成装置１０に入力されたとする。
軌跡データ集合Ｔ＝｛α１，α２，α３，α４｝
α１＝＜ｐ１，ｐ２，ｐ３，ｐ４＞
α２＝＜ｐ５，ｐ６，ｐ７，ｐ８，ｐ９＞
α３＝＜ｐ１０，ｐ１１，ｐ１２＞
α４＝＜ｐ１３，ｐ１４＞
【０１１１】
そして、速度情報付与部１１により、図４に示すような速度情報が、軌跡の各節点間に付与されたとする（ステップＳ１０）。
【０１１２】
経路グラフ生成処理の最初のループでは、平面グラフＧ＊に対して、軌跡データα１，α２，α３，α４の各々を追加した平面グラフＧが生成される（ステップＳ３３、Ｓ３４）。最初は、平面グラフＧ＊は節点集合Ｖ＊及びリンク集合Ｅ＊が空集合であるため、図２３に示すように、平面グラフＧ＊に軌跡データα１を追加した平面グラフＧ１は、軌跡α１そのものとなる。同様に、平面グラフＧ＊に軌跡データα２を追加した平面グラフＧ２は軌跡α２、軌跡データα３を追加した平面グラフＧ３は軌跡α３、軌跡データα４を追加した平面グラフＧ４は軌跡α４そのものとなる。
【０１１３】
次に、各平面グラフＧ１、Ｇ２、Ｇ３、Ｇ４に対する、追加した軌跡データα以外の軌跡データの各々の非近似性のコストδ（Ｇ，α）が、例えば図２４に示すように算出される（ステップＳ３５）。図２４の表は、各行が各平面グラフＧに対応し、各列が軌跡データαに対応し、各マスの値が、そのマスに対応する行の平面グラフＧと、そのマスに対応する列の軌跡データαとの非近似性のコストδ（Ｇ，α）を表す。なお、ここでも、非近似性のコストδ（Ｇ，α）として、平面グラフＧに含まれる経路Πと軌跡αとの近似領域１０５に含まれない節点の数を採用している。図２４において、例えば、平面グラフＧ１（軌跡α１）と軌跡α２とでは、近似領域１０５が存在せず、軌跡α２の節点の数（５）がコストδ（Ｇ，α）となっていることを表す。これらのコストδ（Ｇ，α）に各平面グラフＧの複雑性のコスト｜Ｇ｜を加算し、各平面グラフＧのコストを算出すると、下記のようになる。
【０１１４】
Ｃ（Ｇ１，｛α２，α３，α４｝）
＝δ（Ｇ１，α２）＋δ（Ｇ１，α３）＋δ（Ｇ１，α４）＋｜Ｇ１｜
＝１２
Ｃ（Ｇ２，｛α１，α３，α４｝）
＝δ（Ｇ２，α１）＋δ（Ｇ２，α３）＋δ（Ｇ２，α４）＋｜Ｇ２｜
＝１２
Ｃ（Ｇ３，｛α１，α２，α４｝）
＝δ（Ｇ３，α１）＋δ（Ｇ３，α２）＋δ（Ｇ３，α４）＋｜Ｇ３｜
＝９
Ｃ（Ｇ４，｛α１，α２，α３｝）
＝δ（Ｇ４，α１）＋δ（Ｇ４，α２）＋δ（Ｇ４，α３）＋｜Ｇ４｜
＝１２
【０１１５】
従って、軌跡データα３を平面グラフＧ＊に統合した平面グラフＧのコストＣが最小となるため、平面グラフＧ＊に追加する軌跡データα＊として、軌跡データα３が選択される（ステップＳ３６、Ｓ３７、Ｓ３８）。これにより、新たな平面グラフＧ＊として、平面グラフＧ３（軌跡α３）が生成される（ステップＳ５０）。また、軌跡データ集合Ｔから軌跡データα３が削除される（ステップＳ６０）。
【０１１６】
次のループで、図２５に示すように、平面グラフＧ＊である平面グラフＧ３に対して、軌跡データα１，α２，α４の各々を追加した平面グラフＧ３１、Ｇ３２、Ｇ３４が生成される（ステップＳ３３、Ｓ３４）。なお、図２５では、生成された平面グラフを太線、追加した軌跡を細線で表している。
【０１１７】
次に、各平面グラフＧ３１、Ｇ３２、Ｇ３４に対する、追加した軌跡データα以外の軌跡データ各々の非近似性のコストδ（Ｇ，α）が、例えば図２６に示すように算出される（ステップＳ３５）。これらのコストδ（Ｇ，α）に各平面グラフＧの複雑性のコスト｜Ｇ｜を加算し、各平面グラフＧのコストを算出すると、下記のようになる。
【０１１８】
Ｃ（Ｇ３１，｛α２，α４｝）
＝δ（Ｇ３１，α２）＋δ（Ｇ３１，α４）＋｜Ｇ３１｜＝９
Ｃ（Ｇ３２，｛α１，α４｝）
＝δ（Ｇ３２，α１）＋δ（Ｇ３２，α４）＋｜Ｇ３２｜＝９
Ｃ（Ｇ３４，｛α１，α２｝）
＝δ（Ｇ３４，α１）＋δ（Ｇ３４，α２）＋｜Ｇ３４｜＝９
【０１１９】
ここで、前回のループで軌跡データα＊を選択した際のコストの最小値は「９」であり、今回のループではそれより小さいコストは算出されていない。従って、ここでループを停止する（ステップＳ４０）。そして、平面グラフＧ＊（Ｇ３）に、軌跡データ集合Ｔに残っている軌跡データα１，α２，α４を追加した平面グラフＧ＊を生成し（ステップＳ８０）、これを最終的な経路グラフとする（ステップＳ９０）。
【０１２０】
図２７に、平面グラフＧ３に、軌跡データα１，α２，α４を追加して、平面グラフＧ３１２４を生成する様子を示す。図２７中の破線１０９で示す箇所では、軌跡間の距離が閾値ε以内となる対応する区間において、速度の異なる部分が存在するが、その速度の異なる部分毎に速度を比較した結果に基づいて、統合が行われている。また、図２７中の破線１１０で示す箇所では、軌跡間の節点同士が１対１で対応していないが、対応する区間に含まれる複数のリンクに付与された全ての速度が同じであるため、節点を追加することなく、対応する区間の統合が行われている。
【０１２１】
以上説明したように、本実施形態に係る経路グラフ生成装置によれば、移動体の移動経路を表す軌跡を統合する際、軌跡間の距離だけでなく、軌跡に付与された速度の差も比較するため、移動体の速度の違いを考慮した経路の統合を行うことができる。
【０１２２】
例えば、図２８に示すように、速度を考慮しない経路グラフの生成では、単純に軌跡間の距離のみに基づいて軌跡間の統合を行った経路グラフが生成される。一方、本実施形態では、図２９に示すように、速度に差がある箇所は異なる経路となるような経路グラフが生成される。具体的には、図２８に示す経路グラフでは、節点Ｇからは節点Ｈへ向かう経路のみが示されている。一方、図２９に示す本実施形態による経路グラフでは、速度８０が付与されたリンクＧ＿Ｈと、速度５０が付与されたリンクＧ＿Ｉの経路が含まれ、速度を考慮した詳細な経路グラフとなっている。
【０１２３】
本実施形態により生成された経路グラフを用いて経路分析を行う場合には、生成された経路グラフに、元の軌跡データをマッピングする。マッピングの方法は、経路グラフを生成する際の軌跡間の統合判定と同様に、軌跡と経路グラフの経路との距離及び速度の近似度を用いて行うことができる。例えば、図２９の例では、軌跡データα１は、Ａ→Ｂ→Ｇ→Ｈ、軌跡データα２は、Ｄ→Ｂ→Ｅ→Ｆ、軌跡データα３は、Ｄ→Ｂ→Ｃ、軌跡データα４は、Ｂ→Ｇ→Ｉという経路にマッピングされる。
【０１２４】
上記のようにマッピングした後、例えば，２人以上が通った経路は下記の経路である、といった経路分析（頻出部分経路発見問題）を行うことができる。
Ｂ→Ｇ  （α１とα４）
Ｄ→Ｂ  （α２とα３）
このことから、節点Ｂは混雑していると考えられ、新たに交差点や道路を設置することで混雑の緩和が見込まれる、などの検討を行うことができる。
【０１２５】
また、例えば、リンクＧ＿ＨとＧ＿Ｉは、経路間の距離は近いが、それぞれのリンクに付与された速度に閾値以上の速度差があるため、違う経路となっている。このことから、  高速道路と一般道とが並走している、時間帯によって移動体の速度が大きく異なる道路であるなどの移動体の速度を考慮した分析を行うことができる。
【０１２６】
なお、上記実施形態では、経路間の距離及び速度に基づいて、両経路を統合するか否かを判定する場合について説明したが、これに限定されない。例えば、両経路の距離が小さいほど、かつ両経路に付与された速度の差が小さいほど高くなる類似度を算出し、算出した類似度に基づいて、両経路の類似判断を行うようにしてもよい。この際、両経路を複数の対応する区間に分割し、区間毎に類似度を算出し、算出した複数の類似度の平均、最大値、最小値等の統計情報に基づいて、両経路の類否判断を行ってもよい。
【０１２７】
また、上記実施形態では、非近似性のコストと複雑性のコストとを用いたコストで、最適な平面グラフを生成する場合について説明したが、これに限定されない。経路間の距離及び速度を用いて、経路分析に適した平面グラフの性質を表す評価値を算出すればよい。
【０１２８】
また、本実施形態では、経路間の距離及び速度差から非近似性のコストを算出しているが、経路間の距離に関する評価値、及び速度差に関する評価値を各々算出してもよい。例えば、経路間で距離が閾値以上となる部分に含まれる節点やリンク等の要素数に基づく評価値と、経路間の速度差が閾値以上となる部分に含まれる要素数に基づく評価値とをそれぞれ算出してもよい。そして、それぞれ算出した評価値を、和や重み付き和などで統合し、経路間の非近似性を表すコストとしてもよい。
【０１２９】
また、上記実施形態では、経路間の距離の算出に、フレッシェ距離を用いる場合について説明したが、これに限定されず、ユークリッド距離等、他の距離を用いてもよい。
【０１３０】
また、上記実施形態では、図１５のステップＳ５２４で、軌跡αに対応する部分経路Πの節点が存在しない場合に、部分経路Πに軌跡αの節点に対応する節点を追加している。このステップの処理について、図１５のステップＳ５３３及びＳ５７３のように、対応する区間において、軌跡αの対応する区間において、速度が異なる部分が生じている場合にのみ、対応する節点を追加するようにしてもよい。
【０１３１】
また、上記実施形態では、２次元の軌跡データから２次元の経路グラフを生成する場合について説明したが、緯度及び経度の情報に加えて高さ情報も含む位置データを取得し、３次元の経路グラフを生成するようにしてもよい。
【０１３２】
なお、上記では本発明に係る移動経路統合プログラムの一例である経路グラフ生成プログラム５０が記憶部４６に予め記憶（インストール）されている態様を説明したが、これに限定されない。本発明に係る移動経路統合プログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ等の記録媒体に記録された形態で提供することも可能である。
【０１３３】
以上の各実施形態に関し、更に以下の付記を開示する。
【０１３４】
（付記１）
記憶部に記憶された移動履歴情報に含まれる第１の移動に関する第１の移動経路及び該第１の移動経路における第１の移動速度と、第２の移動に関する第２の移動経路及び該第２の移動経路における第２の移動速度とを取得し、
取得した前記１の移動経路と前記第２の移動経路との間の近さに関する評価値と、前記第１の移動速度と前記第２の移動速度との間の速度差に関する評価値と、に基づいて、前記第１の移動経路と前記第２の移動経路との間で移動経路の統合処理を実行するか否か判定し、
判定結果に応じて前記第１の移動経路と前記第２の移動経路との統合処理を実行する、
処理をコンピュータに実行させることを特徴とする移動経路統合方法。
【０１３５】
（付記２）
前記第１の移動経路と、前記第２の移動経路は、それぞれ、前記第１の移動、前記第２の移動において測定された２箇所の位置を結ぶパスである、ことを特徴とする付記１に記載の移動経路統合方法。
【０１３６】
（付記３）
前記第１の移動経路に、前記第１の移動速度が異なる複数の区間が含まれる場合、前記第２の移動経路を前記複数の区間の各々に対応して分割した区間毎に、前記第１の移動経路と前記第２の移動経路との間で移動経路の統合処理を実行するか否か判定する、付記１または付記２に記載の移動経路統合方法。
【０１３７】
（付記４）
前記第１の移動経路に、前記第１の移動速度が同一の複数の区間が含まれる場合、前記第２の移動経路と、前記第１の移動経路の前記複数の区間との間で移動経路の統合処理を実行するか否か判定する、付記１または付記２に記載の移動経路統合方法。
【０１３８】
（付記５）
前記第１の移動経路と前記第２の移動経路とを統合処理する際、前記第１の移動速度と前記第２の移動速度との平均を、統合処理後の移動経路の移動速度として付与する付記１〜付記４のいずれか１項に記載の移動経路統合方法。
【０１３９】
（付記６）
前記統合処理を実行するか否か判定する際、前記１の移動経路と前記第２の移動経路との間の近さと、前記速度差とで表される前記第１の移動経路と前記第２の移動経路との近似度を評価値として算出する付記１〜付記５のいずれか１項に記載の移動経路統合方法。
【０１４０】
（付記７）
前記統合処理を実行するか否か判定する際、前記近似度を示す評価値に加え、統合処理後の移動経路の複雑さを示す評価値を算出する付記６に記載の移動経路統合方法。
【０１４１】
（付記８）
前記統合処理を実行するか否か判定する際、前記第１の移動経路と前記第２の移動経路との距離が予め定めた距離閾値以下となる部分であって、該部分の移動速度の差が予め定めた速度閾値以下の部分を統合すると判定する付記１〜付記７のいずれか１項に記載の移動経路統合方法。
【０１４２】
（付記９）
記憶部に記憶された移動履歴情報に含まれる第１の移動に関する第１の移動経路及び該第１の移動経路における第１の移動速度と、第２の移動に関する第２の移動経路及び該第２の移動経路における第２の移動速度とを取得し、
取得した前記１の移動経路と前記第２の移動経路との間の近さに関する評価値と、前記第１の移動速度と前記第２の移動速度との間の速度差に関する評価値と、に基づいて、前記第１の移動経路と前記第２の移動経路との間で移動経路の統合処理を実行するか否か判定し、
判定結果に応じて前記第１の移動経路と前記第２の移動経路との統合処理を実行する、
処理をコンピュータに実行させることを特徴とする移動経路統合プログラム。
【０１４３】
（付記１０）
前記第１の移動経路と、前記第２の移動経路は、それぞれ、前記第１の移動、前記第２の移動において測定された２箇所の位置を結ぶパスである、ことを特徴とする付記９に記載の移動経路統合プログラム。
【０１４４】
（付記１１）
前記第１の移動経路に、前記第１の移動速度が異なる複数の区間が含まれる場合、前記第２の移動経路を前記複数の区間の各々に対応して分割した区間毎に、前記第１の移動経路と前記第２の移動経路との間で移動経路の統合処理を実行するか否か判定する、付記９または付記１０に記載の移動経路統合プログラム。
【０１４５】
（付記１２）
前記第１の移動経路に、前記第１の移動速度が同一の複数の区間が含まれる場合、前記第２の移動経路と、前記第１の移動経路の前記複数の区間との間で移動経路の統合処理を実行するか否か判定する、付記９または付記１０に記載の移動経路統合プログラム。
【０１４６】
（付記１３）
前記第１の移動経路と前記第２の移動経路とを統合処理する際、前記第１の移動速度と前記第２の移動速度との平均を、統合処理後の移動経路の移動速度として付与する付記９〜付記１２のいずれか１項に記載の移動経路統合プログラム。
【０１４７】
（付記１４）
前記統合処理を実行するか否か判定する際、前記１の移動経路と前記第２の移動経路との間の近さと、前記速度差とで表される前記第１の移動経路と前記第２の移動経路との近似度を評価値として算出する付記９〜付記１３のいずれか１項に記載の移動経路統合プログラム。
【０１４８】
（付記１５）
前記統合処理を実行するか否か判定する際、前記近似度を示す評価値に加え、統合処理後の移動経路の複雑さを示す評価値を算出する付記１４に記載の移動経路統合プログラム。
【０１４９】
（付記１６）
前記統合処理を実行するか否か判定する際、前記第１の移動経路と前記第２の移動経路との距離が予め定めた距離閾値以下となる部分であって、該部分の移動速度の差が予め定めた速度閾値以下の部分を統合すると判定する付記９〜付記１５のいずれか１項に記載の移動経路統合プログラム。
【０１５０】
（付記１７）
記憶部に記憶された移動履歴情報に含まれる第１の移動に関する第１の移動経路及び該第１の移動経路における第１の移動速度と、第２の移動に関する第２の移動経路及び該第２の移動経路における第２の移動速度とを取得する取得部と、
取得した前記１の移動経路と前記第２の移動経路との間の近さに関する評価値と、前記第１の移動速度と前記第２の移動速度との間の速度差に関する評価値と、に基づいて、前記第１の移動経路と前記第２の移動経路との間で移動経路の統合処理を実行するか否か判定する判定部と、
判定結果に応じて前記第１の移動経路と前記第２の移動経路との統合処理を実行する統合部と、
を含む移動経路統合装置。
【０１５１】
（付記１８）
前記第１の移動経路と、前記第２の移動経路は、それぞれ、前記第１の移動、前記第２の移動において測定された２箇所の位置を結ぶパスである、ことを特徴とする付記１７に記載の移動経路統合装置。
【０１５２】
（付記１９）
前記判定部は、前記第１の移動経路に、前記第１の移動速度が異なる複数の区間が含まれる場合、前記第２の移動経路を前記複数の区間の各々に対応して分割した区間毎に、前記第１の移動経路と前記第２の移動経路との間で移動経路の統合処理を実行するか否か判定する、付記１７または付記１８に記載の移動経路統合装置。
【０１５３】
（付記２０）
前記判定部は、前記第１の移動経路に、前記第１の移動速度が同一の複数の区間が含まれる場合、前記第２の移動経路と、前記第１の移動経路の前記複数の区間との間で移動経路の統合処理を実行するか否か判定する、付記１７または付記１８に記載の移動経路統合装置。
【０１５４】
（付記２１）
前記統合部は、前記第１の移動速度と前記第２の移動速度との平均を、統合処理後の移動経路の移動速度として付与する付記１７〜付記２０のいずれか１項に記載の移動経路統合装置。
【０１５５】
（付記２２）
前記判定部は、前記１の移動経路と前記第２の移動経路との間の近さと、前記速度差とで表される前記第１の移動経路と前記第２の移動経路との近似度を評価値として算出する付記１７〜付記２１のいずれか１項に記載の移動経路統合装置。
【０１５６】
（付記２３）
前記判定部は、前記近似度を示す評価値に加え、統合処理後の移動経路の複雑さを示す評価値を算出する付記２２に記載の移動経路統合装置。
【０１５７】
（付記２４）
前記判定部は、前記第１の移動経路と前記第２の移動経路との距離が予め定めた距離閾値以下となる部分であって、該部分の移動速度の差が予め定めた速度閾値以下の部分を統合すると判定する付記１７〜付記２３のいずれか１項に記載の移動経路統合装置。
【符号の説明】
【０１５８】
１０   経路グラフ生成装置
１１   速度情報付与部
１２   軌跡データ探索部
１３   平面グラフ生成部
１４   コスト算出部
２０   経路グラフ生成システム
２２   軌跡データ生成装置
２４   軌跡データ記憶部
２６   センサ
２８   ネットワーク
４０   コンピュータ
４１   ＣＰＵ
４２   メモリ
４３   記憶装置
５０   経路グラフ生成プログラム
１０４ 距離近似領域
１０５ 近似領域
【図１】
0006379943.tif 000002
【図２】
0006379943.tif 000003
【図３】
0006379943.tif 000004
【図４】
0006379943.tif 000005
【図５】
0006379943.tif 000006
【図６】
0006379943.tif 000007
【図７】
0006379943.tif 000008
【図８】
0006379943.tif 000009
【図９】
0006379943.tif 000010
【図１０】
0006379943.tif 000011
【図１１】
0006379943.tif 000012
【図１２】
0006379943.tif 000013
【図１３】
0006379943.tif 000014
【図１４】
0006379943.tif 000015
【図１５】
0006379943.tif 000016
【図１６】
0006379943.tif 000017
【図１７】
0006379943.tif 000018
【図１８】
0006379943.tif 000019
【図１９】
0006379943.tif 000020
【図２０】
0006379943.tif 000021
【図２１】
0006379943.tif 000022
【図２２】
0006379943.tif 000023
【図２３】
0006379943.tif 000024
【図２４】
0006379943.tif 000025
【図２５】
0006379943.tif 000026
【図２６】
0006379943.tif 000027
【図２７】
0006379943.tif 000028
【図２８】
0006379943.tif 000029
【図２９】
0006379943.tif 000030