(57)【特許請求の範囲】
【請求項１】
移動体の位置測定点に基づいて、複数のリンクが結合されて構成されたマップ上における前記移動体の位置を決定するマップマッチング装置であって、
前記位置測定点に基づいて一つ又は複数の候補地点を前記リンク上に抽出する候補地点抽出部と、
一の前記位置測定点に基づいて抽出された前記候補地点である第１候補地点のうちの一つと、他の前記位置測定点に基づいて抽出された前記候補地点である第２候補地点のうちの一つと、を結ぶ前記リンクの移動コストを、前記第１候補地点と前記第２候補地点との組み合わせ別に決定する移動コスト決定部と、
前記移動コストに基づいて、前記移動体が前記第１候補地点のうちの一つから前記第２候補地点のうちの一つまで移動可能であるか否かを、前記第１候補地点と前記第２候補地点との組み合わせ別に判定する移動可否判定部と、
前記移動可否判定部が移動可能であると判定した前記組み合わせに含まれる前記候補地点のうち何れか一つを、前記マップ上における前記移動体の位置として決定するマッチング地点決定部と、
を備えるマップマッチング装置。
【請求項２】
前記移動コスト決定部は、一のリンケージと他のリンケージとを結ぶ前記リンクの前記移動コストを前記リンケージの組み合わせ別に予め記録した移動コストテーブルに基づいて、前記第１候補地点と前記第２候補地点との組み合わせ別に移動コストを決定する、
請求項１に記載のマップマッチング装置。
【請求項３】
前記位置測定点における前記移動体の速度を取得し、当該速度に基づいて、一の前記位置測定点が測定された時間と、他の前記位置測定点が測定された時間との間に前記移動体が移動可能な移動可能距離を推定する移動可能距離推定部を更に備え、
前記移動可否判定部は、前記移動可能距離よりも前記移動コストが小さい場合、前記移動体が前記第１候補地点のうちの一つから前記第２候補地点のうちの一つまで移動可能であると判定する、
請求項１又は２に記載のマップマッチング装置。
【請求項４】
前記位置測定点と、当該位置測定点に関連する前記候補地点との距離に基づいて、前記候補地点別のスコアを算出するスコア算出部を更に備え、
前記マッチング地点決定部は、前記スコアに基づいて、前記移動可否判定部が移動可能であると判定した組み合わせに含まれる前記候補地点のうち何れか一つを、前記マップ上における前記移動体の位置として決定する、
請求項１から３の何れか一項に記載のマップマッチング装置。
【請求項５】
移動体の位置を位置測定点として測定するクライアントと、
前記クライアントが測定した前記位置測定点を収集する位置測定点収集部と、
請求項１から４の何れか一項に記載のマップマッチング装置と、
を備えるマップマッチングシステム。
【請求項６】
移動体の位置測定点に基づいて、複数のリンクが結合されて構成されたマップ上における前記移動体の位置を決定するマップマッチング方法であって、
前記位置測定点に基づいて一つ又は複数の候補地点を前記リンク上に抽出する候補地点抽出ステップと、
一の前記位置測定点に基づいて抽出された前記候補地点である第１候補地点のうちの一つと、他の前記位置測定点に基づいて抽出された前記候補地点である第２候補地点のうちの一つと、を結ぶ前記リンクの移動コストを、前記第１候補地点と前記第２候補地点との組み合わせ別に決定する移動コスト決定ステップと、
前記移動コストに基づいて、前記移動体が前記第１候補地点のうちの一つから前記第２候補地点のうちの一つまで移動可能であるか否かを、前記第１候補地点と前記第２候補地点との組み合わせ別に判定する移動可否判定ステップと、
前記移動可否判定ステップにおいて移動可能であると判定された前記組み合わせに含まれる前記候補地点のうち何れか一つを、前記マップ上における前記移動体の位置として決定するマッチング地点決定ステップと、
を有するマップマッチング方法。
【請求項７】
移動体の位置測定点に基づいて、複数のリンクが結合されて構成されたマップ上における前記移動体の位置を決定するマップマッチング装置のコンピュータを機能させるプログラムであって、
前記コンピュータを、
前記位置測定点に基づいて一つ又は複数の候補地点を前記リンク上に抽出する候補地点抽出部、
一の前記位置測定点に基づいて抽出された前記候補地点である第１候補地点のうちの一つと、他の前記位置測定点に基づいて抽出された前記候補地点である第２候補地点のうちの一つと、を結ぶ前記リンクの移動コストを、前記第１候補地点と前記第２候補地点との組み合わせ別に決定する移動コスト決定部、
前記移動コストに基づいて、前記移動体が前記第１候補地点のうちの一つから前記第２候補地点のうちの一つまで移動可能であるか否かを、前記第１候補地点と前記第２候補地点との組み合わせ別に判定する移動可否判定部、
前記移動可否判定部が移動可能であると判定した前記組み合わせに含まれる前記候補地点のうち何れか一つを、前記マップ上における前記移動体の位置として決定するマッチング地点決定部、
として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マップマッチング装置、マップマッチングシステム、マップマッチング方法及びプログラムに関する。
【背景技術】
【０００２】
例えば車両に搭載された車載器では、ＧＮＳＳ（Global Navigation Satellite System）、各種センサ等を利用して移動体の位置測定点（測位点）を取得するとともに、複数のリンク（道路）が結合されて構成されたマップ上における、当該位置測定点の位置を決定する。このとき、位置測定点に含まれる誤差、実際の道路とリンクとの形状（距離、幅、角度等）の誤差により、車両がある道路に位置するときに取得された位置測定点と、当該道路に対応するリンク上の位置とが一致しない場合がある。
このため、従来の車載器では、一定の周期毎（例えば１秒毎）に位置測定点を取得し、時系列に連続する複数の位置測定点を結んで得られる移動体の移動軌跡がリンクの形状に沿うように各位置測定点を補正するマップマッチングという処理を行っている（例えば特許文献１）。これにより、車載器は、位置測定点の誤差、マップの誤差等を除去して、車両のマップ上における位置を決定することができる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】国際公開第２００９／０６０７７６号
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、例えば、サーバがネットワークを介して複数の車載器から位置測定点を収集し、マップマッチング処理を行うシステムでは、ネットワークの状態に応じて位置測定点の収集間隔が不定期となること、車載器とサーバとの間の通信量を低減するために位置測定点の収集間隔が長く設定されること等が考えられる。このような場合、サーバがある位置測定点を取得してから、次の位置測定点を取得するまでの間に、車両が複数のリンクを移動してしまうことがある。サーバは、ある位置測定点と次の位置測定点との間を結ぶ複数のリンクのうち、車両が何れのリンクを通って移動したかを知ることができないため、ある位置測定点から車両が到達し得ないほど道のりが離れたリンクであっても、次の位置測定点に最も距離が近いリンクであると判断された場合は、当該リンク上の位置を車両の位置として決定することとなる。このように、サーバによるマップマッチング処理では、車両のマップ上における位置を正しく決定できない場合がある。【０００５】
本発明は、位置測定点の収集間隔が長い場合であっても、マップ上における移動体の位置を決定することが可能となるマップマッチング装置、マップマッチングシステム、マップマッチング方法及びプログラムを提供する。
【課題を解決するための手段】
【０００６】
本発明の第１の態様によれば、マップマッチング装置（２０）は、移動体の位置測定点に基づいて、複数のリンクが結合されて構成されたマップ上における前記移動体の位置を決定する。マップマッチング装置は、前記位置測定点に基づいて一つ又は複数の候補地点を前記リンク上に抽出する候補地点抽出部（２０１）と、一の前記位置測定点に基づいて抽出された前記候補地点である第１候補地点のうちの一つと、他の前記位置測定点に基づいて抽出された前記候補地点である第２候補地点のうちの一つと、を結ぶ前記リンクの移動コストを、前記第１候補地点と前記第２候補地点との組み合わせ別に決定する移動コスト決定部（２０２）と、前記移動コストに基づいて、前記移動体が前記第１候補地点のうちの一つから前記第２候補地点のうちの一つまで移動可能であるか否かを、前記第１候補地点と前記第２候補地点との組み合わせ別に判定する移動可否判定部（２０４）と、前記移動可否判定部が移動可能であると判定した前記組み合わせに含まれる前記候補地点のうち何れか一つを、前記マップ上における前記移動体の位置として決定するマッチング地点決定部（２０６）と、を備える。
このようにすることで、一の位置測定点と他の位置測定点との道のりが離れており、一の位置測定点と他の位置測定点とを結ぶリンクの組み合わせが複数ある場合であっても、移動可否判定部が移動コストに基づいて各リンクの組み合わせが移動可能であるか否かを判定することにより、現実に移動可能な候補地点のみをマップ上における移動体の位置として決定することができる。従って、マップマッチング装置は、位置測定点の収集間隔が長い場合であっても、マップ上における移動体の位置を決定することが可能となる。【０００７】
本発明の第２の態様によれば、前記移動コスト決定部は、一のリンケージと他のリンケージとを結ぶ前記リンクの前記移動コストを前記リンケージの組み合わせ別に予め記録した移動コストテーブルに基づいて、前記第１候補地点と前記第２候補地点との組み合わせ別に移動コストを決定する。
このようにすることで、リンケージ間の移動コストは予め移動コストテーブルに記録されているため、移動コスト決定部が移動コストを決定する処理を短縮化することができる。また、移動コスト決定部は、候補経路が複数ある場合であっても、移動コストテーブルに基づいて、各候補経路の移動コストを決定する処理を簡素化（高速化）することができる。【０００８】
本発明の第３の態様によれば、前記位置測定点における前記移動体の速度を取得し、当該速度に基づいて、一の前記位置測定点が測定された時間と、他の前記位置測定点が測定された時間との間に前記移動体が移動可能な移動可能距離を推定する移動可能距離推定部（２０３）を更に備える。前記移動可否判定部は、前記移動可能距離よりも前記移動コストが小さい場合、前記移動体が前記第１候補地点のうちの一つから前記第２候補地点のうちの一つまで移動可能であると判定する。
このようにすることで、移動可否判定部は、一の位置測定点が測定された時間から他の位置測定点が測定された時間までの間に移動体が移動可能な距離を推定することにより、移動可否判定部における移動可否の判定の精度を向上させることができる。【０００９】
本発明の第４の態様によれば、前記位置測定点と、当該位置測定点に関連する前記候補地点との距離に基づいて、前記候補地点別のスコアを算出するスコア算出部（２０５）を更に備える。前記マッチング地点決定部は、前記スコアに基づいて、前記移動可否判定部が移動可能であると判定した組み合わせに含まれる前記候補地点のうち何れか一つを、前記マップ上における前記移動体の位置として決定する。
このようにすることで、移動可能であると判定された候補地点の組み合わせが複数ある場合、当該組み合わせに含まれる候補地点のスコアに基づいて、マップ上における移動体の位置を決定することができる。【００１０】
本発明の第５の態様によれば、マップマッチングシステムは、移動体の位置を位置測定点として測定するクライアントと、前記クライアントが測定した前記位置測定点を収集する位置測定点収集部と、上述の何れか一の態様に記載のマップマッチング装置と、を備える。【００１１】
本発明の第６の態様によれば、マップマッチング方法は、移動体の位置測定点に基づいて、複数のリンクが結合されて構成されたマップ上における前記移動体の位置を決定する。マップマッチング方法は、前記位置測定点に基づいて一つ又は複数の候補地点を前記リンク上に抽出する候補地点抽出ステップと、一の前記位置測定点に基づいて抽出された前記候補地点である第１候補地点のうちの一つと、他の前記位置測定点に基づいて抽出された前記候補地点である第２候補地点のうちの一つと、を結ぶ前記リンクの移動コストを、前記第１候補地点と前記第２候補地点との組み合わせ別に決定する移動コスト決定ステップと、前記移動コストに基づいて、前記移動体が前記第１候補地点のうちの一つから前記第２候補地点のうちの一つまで移動可能であるか否かを、前記第１候補地点と前記第２候補地点との組み合わせ別に判定する移動可否判定ステップと、前記移動可否判定ステップにおいて移動可能であると判定された前記組み合わせに含まれる前記候補地点のうち何れか一つを、前記マップ上における前記移動体の位置として決定するマッチング地点決定ステップと、を有する。【００１２】
本発明の第７の態様によれば、プログラムは、移動体の位置測定点に基づいて、複数のリンクが結合されて構成されたマップ上における前記移動体の位置を決定するマップマッチング装置のコンピュータを機能させる。プログラムは、前記コンピュータを、前記位置測定点に基づいて一つ又は複数の候補地点を前記リンク上に抽出する候補地点抽出部、一の前記位置測定点に基づいて抽出された前記候補地点である第１候補地点のうちの一つと、他の前記位置測定点に基づいて抽出された前記候補地点である第２候補地点のうちの一つと、を結ぶ前記リンクの移動コストを、前記第１候補地点と前記第２候補地点との組み合わせ別に決定する移動コスト決定部、前記移動コストに基づいて、前記移動体が前記第１候補地点のうちの一つから前記第２候補地点のうちの一つまで移動可能であるか否かを、前記第１候補地点と前記第２候補地点との組み合わせ別に判定する移動可否判定部、前記移動可否判定部が移動可能であると判定した前記組み合わせに含まれる前記候補地点のうち何れか一つを、前記マップ上における前記移動体の位置として決定するマッチング地点決定部、として機能させる。
【発明の効果】
【００１３】
上述のマップマッチング装置、マップマッチングシステム、マップマッチング方法及びプログラムによれば、位置測定点の収集間隔が長い場合であっても、マップ上における移動体の位置を決定することが可能となる。
【図面の簡単な説明】
【００１４】
【図１】本発明の第１の実施形態に係るマップマッチングシステムの全体構成を示す図である。
【図２】本発明の第１の実施形態に係る位置測定点収集部が収集した位置測定点の例を示す図である。
【図３】本発明の第１の実施形態に係るマップマッチング装置の機能構成を示す図である。
【図４】本発明の第１の実施形態に係るマップマッチング装置の処理フローを示す図である。
【図５】本発明の第１の実施形態に係るマップマッチング装置の機能を説明するための図である。
【図６】本発明の第１の実施形態に係る移動コストテーブルの例を示す図である。
【図７】本発明の第１の実施形態に係る移動コスト決定部の処理を説明するための図である。
【図８】本発明の第１の実施形態に係る移動可能距離推定部の処理を説明するための第１の図である。
【図９】本発明の第１の実施形態に係る移動可能距離推定部の処理を説明するための第２の図である。
【図１０】本発明の第１の実施形態に係るマップマッチング装置のハードウェア構成の例を示す図である。
【図１１】本発明の第２の実施形態に係るマップマッチング装置の処理フローを示す図である。
【図１２】本発明の第２の実施形態に係るマップマッチング装置の機能を説明するための図である。
【図１３】本発明の第２の実施形態に係る移動コスト決定部の処理を説明するための図である。
【図１４】本発明の第２の実施形態に係るスコア算出部の処理を説明するための図である。
【発明を実施するための形態】
【００１５】
＜第１の実施形態＞
以下、第１の実施形態に係るマップマッチングシステム１について、図１〜図１０を参照して説明する。
【００１６】
（マップマッチングシステムの全体構成）
まず、マップマッチングシステムの全体構成について、図１〜図２を参照して説明する。
図１は、本発明の第１の実施形態に係るマップマッチングシステムの全体構成を示す図である。
図１に示すように、マップマッチングシステム１は、位置測定点収集部１０と、マップマッチング装置２０と、マッチングデータ記録部３０と、を備える。
位置測定点収集部１０は、車両、歩行者等の移動体の位置を示す位置測定点を収集するためのサーバである。位置測定点収集部１０は、車両に搭載された車載器、歩行者が携帯する携帯端末等の複数のクライアントＡ（Ａ１、Ａ２、…）から送信された位置測定点を、インターネット等のネットワークＮＷを介して収集する。
本実施形態において、クライアントＡは、クライアントＡを有する移動体の位置を測定する毎に、当該位置を示す位置測定点を記録している。また、クライアントＡは、所定の時間（例えば１分）が経過したとき、及び、所定のイベント（例えばクライアントＡの起動及び終了、移動体の発進及び停止等）が発生したときに測定した位置測定点を、位置測定点収集部１０へ送信する。
【００１７】
図２は、本発明の第１の実施形態に係る位置測定点収集部が収集した位置測定点の例を示す図である。
図２に示すように、位置測定点収集部１０は、複数のクライアントＡから受信した位置測定点を収集して蓄積する。
位置測定点には、クライアントＡを特定可能な機器ＩＤと、移動体の位置を示す位置情報（緯度、経度）と、位置測定点を測定した測定日時と、位置測定点を測定した時点における移動体の速度（ｋｍ／ｈ）及び移動方向（方位）とが含まれている。なお、位置測定点には、緯度、経度の他に、高度が含まれていてもよい。また、移動体の移動方向には、方位の他に、坂道等を走行していることを示す重力方向における傾きが含まれていてもよい。
【００１８】
マップマッチング装置２０は、位置測定点収集部１０が収集した位置測定点のそれぞれに基づいてマップマッチング処理を行うことにより、複数のリンク（道路）が結合されて構成されたマップ上におけるクライアントＡ（クライアントＡを有する移動体）の位置（以下、マッチング地点）を決定する。
マップマッチング装置２０がマッチング地点を決定する処理の詳細については、後述する。
【００１９】
マッチングデータ記録部３０は、マップマッチング装置２０が決定した各移動体のマッチング地点を、位置測定点と関連付けて記録するデータベースである。
【００２０】
本実施形態において、位置測定点収集部１０と、マップマッチング装置２０と、マッチングデータ記録部３０とは、ネットワークＮＷを介して接続されている。なお、位置測定点収集部１０と、マップマッチング装置２０と、マッチングデータ記録部３０とは、ＬＡＮ（Local Area Network）等のネットワークＬＮを介して接続されていてもよい。
【００２１】
（マップマッチング装置の機能構成）
次に、マップマッチング装置２０の機能構成について、図３を参照して説明する。
図３は、本発明の第１の実施形態に係るマップマッチング装置の機能構成を示す図である。
図３に示すように、マップマッチング装置２０は、候補地点抽出部２０１と、移動コスト決定部２０２と、移動可能距離推定部２０３と、移動可否判定部２０４と、スコア算出部２０５と、マッチング地点決定部２０６と、記録媒体２０７と、運行管理部２０８と、を備えている。
【００２２】
候補地点抽出部２０１は、位置測定点収集部１０が収集した位置測定点に基づいて、一つ又は複数の候補地点をリンク上に抽出する。
具体的には、候補地点抽出部２０１は、記録媒体２０７に予め記録された、複数のリンク及びリンク同士を接続するリンケージから構成されるマップ（図５）と、位置測定点の位置情報とに基づいて、当該位置測定点から所定距離（例えば１０ｍ）以内に位置する一つ又は複数のリンクを選択する。マップの詳細は後述する。
そして、候補地点抽出部２０１は、選択したリンク上の位置であって、位置測定点から最も近い位置を候補地点として抽出する。候補地点抽出部２０１は、複数のリンクを選択した場合、リンク別に候補地点を抽出する。
【００２３】
移動コスト決定部２０２は、一の位置測定点に基づいて抽出された候補地点（第１候補地点）と、他の位置測定点に基づいて抽出された候補地点（第２候補地点）とを結ぶリンクの組み合わせ別に移動コストを決定する。本実施形態において、移動コストとは、一のリンケージと他のリンケージとを結ぶ一つ又は複数のリンクの長さ（距離）の合計を、リンケージの組み合わせ別に示すものである。本実施形態では、リンクの組み合わせ別に予め移動コストが設定された移動コストテーブル（図６）が記録媒体２０７に記録されている。移動コストテーブルの詳細は後述する。移動コスト決定部２０２は、記録媒体２０７に記録された移動コストテーブルを参照して、リンクの組み合わせ別の移動コストを決定する。
なお、以降の説明では、第１候補地点と第２候補地点とを結ぶリンクの組み合わせを、候補経路とも表記する。
【００２４】
移動可能距離推定部２０３は、一の位置測定点を測定した時点（測定日時）における移動体の速度と、他の位置測定点を測定した時点（測定日時）における移動体の速度と、に基づいて、一の位置測定点を測定した時点から他の位置測定点を測定した時点までの間に当該移動体が移動可能な移動可能距離を推定する。
【００２５】
移動可否判定部２０４は、移動コスト決定部２０２が決定したリンクの組み合わせ（候補経路）別の移動コストに基づいて、移動体が各候補経路を移動可能であるか否かを判定する。
具体的には、移動可否判定部２０４は、移動可能距離推定部２０３が推定した移動体の移動可能距離と、各候補経路の移動コストとを比較する。移動可否判定部２０４は、移動可能距離よりも候補経路の移動コストが小さい場合、当該候補経路は移動可能であると判定する。一方、移動可否判定部２０４は、移動可能距離よりも候補経路の移動コストが大きい場合、当該候補経路は移動不可能であると判定する。
【００２６】
スコア算出部２０５は、位置測定点と、当該位置測定点に関連する候補地点との距離に基づいて、候補地点別のスコアを算出する。
本実施形態では、位置測定点と候補地点との距離に所定の係数を乗じた値を、候補地点のスコアとする。また、位置測定点と候補地点との距離が近いほど、スコアの値が小さくなる。
【００２７】
マッチング地点決定部２０６は、移動可否判定部２０４が移動可能であると判定したリンクの組み合わせ（候補経路）に含まれる候補地点のうち、スコアの値が最も小さい候補地点を、マッチング地点として決定する。
また、マッチング地点決定部２０６は、決定したマッチング地点と、位置測定点とを関連付けたマッチングデータを、マッチングデータ記録部３０に記録する。
【００２８】
記録媒体２０７には、マップ（図５）と、セグメント別の移動コストテーブル（図６）とが予め記録されている。
【００２９】
運行管理部２０８は、マッチングデータ記録部３０に記録されたマッチングデータに基づいて、機器ＩＤから特定されるクライアントＡ（又はクライアントＡを有する移動体）の運行管理を行う。
例えば、運送業者のトラック等に車載器が搭載されており、当該車載器が機器ＩＤから特定されるクライアントＡであるとする。運行管理部２０８は、ある機器ＩＤに紐付くマッチングデータに基づいて、当該機器ＩＤから特定されるクライアントＡ（又はクライアントＡを搭載したトラック）の移動ルート、移動距離、移動時間等の運転分析を行う。また、運行管理部２０８は、マッチングデータに基づいて、ある機器ＩＤに紐付くマッチング地点が、機器ＩＤ別（トラック別）に指定された移動ルート、目的地、中継地等から所定距離（例えば５ｋｍ）以上離れているか否かを判断するようにしてもよい。この場合、運行管理部２０８は、当該機器ＩＤに紐付くマッチング地点が指定された移動ルート等から所定距離以上離れていると判断した場合、移動ルートから逸れていることを示すアラート情報をマップマッチング装置の表示部（不図示）に表示するようにしてもよいし、ネットワークＮＷを通じてクライアントＡにアラート情報を出力する命令を送信するようにしてもよい。なお、運行管理部２０８は、クライアントＡの最新の（測定日時が最も新しい）マッチング地点から、目的地、中継地等への新たな移動ルートを生成して、当該新たな移動ルートをアラート情報に含めてもよい。
【００３０】
（マップマッチング装置の処理フロー）
以下、マップマッチング装置２０の処理フローについて、図４〜図９を参照して説明する。
【００３１】
図４は、本発明の第１の実施形態に係るマップマッチング装置の処理フローを示す図である。
図４に示すように、まず、マップマッチング装置２０の候補地点抽出部２０１は、位置測定点収集部１０から、マップマッチング処理の対象となる位置測定点を選択する（ステップＳ１００）。
本実施形態では、候補地点抽出部２０１は、ある機器ＩＤを有する複数の位置測定点のうち、測定日時が古い位置測定点Ｐｉをマップマッチング処理の対象として選択する。また、位置測定点Ｐｉよりも古い測定日時を有する位置測定点（例えば位置測定点Ｐｉの一つ前の位置測定点Ｐｉ−１）は、過去に行われたマップマッチング処理により、マッチング地点が特定されており、マッチングデータ記録部３０に記録されているものとする。
以下の例では、候補地点抽出部２０１が、図２の位置測定点のうち、マップマッチング処理の対象となる位置測定点Ｐｉとして、機器ＩＤ「０００００００１」を有する位置測定点Ｐ２を選択した場合について説明する。また、位置測定点Ｐ２の一つ前の位置測定点であって、位置測定点Ｐ２と同一の機器ＩＤを有する位置測定点Ｐｉ−１、即ち、位置測定点Ｐ１は、過去に行われたマップマッチング処理により、候補地点ｘ１がマッチング地点として決定されているものとする。
【００３２】
次に、候補地点抽出部２０１は、ステップＳ１００において選択した位置測定点Ｐｉ（位置測定点Ｐ２）の候補地点を抽出する（ステップＳ１０１）。
図５は、本発明の第１の実施形態に係るマップマッチング装置の機能を説明するための図である。
本実施形態では、図５に示すように、複数のリンク及びリンク同士を接続するリンケージから構成されるマップが、予め記録媒体２０７に記録されている。また、マップには、リンクの長さ（距離）を示す情報と、各リンクの属性情報とが記録されている。リンクの属性情報には、例えば、一方通行であること及び通行可能な方向を示す情報、自動車専用道路又は歩行者専用道路であることを示す情報、リンクの制限速度を示す情報等が含まれている。
位置測定点Ｐ２の候補地点を抽出する場合、まず、候補地点抽出部２０１は、位置測定点Ｐ２から所定距離（例えば１０ｍ）以内に位置するリンクとして、リンクＤ−Ｆ、リンクＢ−Ｆ及びリンクＤ−Ｇの三つのリンクを選択する。
そして、候補地点抽出部２０１は、選択したリンク上の位置であって、位置測定点Ｐ２から最も近い位置を候補地点として抽出する。具体的には、候補地点抽出部２０１は、図５に示すように、リンクＤ−Ｆ上の候補地点として「ｘ２ａ」を抽出し、リンクＢ−Ｆ上の候補地点として「ｘ２ｂ」を抽出し、リンクＤ−Ｇ上の候補地点として「ｘ２ｃ」を抽出する。
【００３３】
次に、移動コスト決定部２０２は、一つ前の位置測定点Ｐｉ−１の候補地点をマッチングデータ記録部３０から読み出す。そして、移動コスト決定部２０２は、位置測定点Ｐｉに基づいて抽出された候補地点と、一つ前の位置測定点Ｐｉ−１の候補地点とを結ぶリンクの移動コストを、候補地点の組み合わせ（候補経路）別に決定する（ステップＳ１０２）。
具体的には、移動コスト決定部２０２は、まず、一つ前の位置測定点Ｐ１の候補地点ｘ１をマッチングデータ記録部３０から読み出す。そして、移動コスト決定部２０２は、位置測定点Ｐ２の候補地点ｘ２ａ及び位置測定点Ｐ１の候補地点ｘ１を結ぶ候補経路Ｒ１と、位置測定点Ｐ２の候補地点ｘ２ｂ及び位置測定点Ｐ１の候補地点ｘ１を結ぶ候補経路Ｒ２と、位置測定点Ｐ２の候補地点ｘ２ｃ及び位置測定点Ｐ１の候補地点ｘ１を結ぶ候補経路Ｒ３と、の移動コストをそれぞれ決定する。
本実施形態では、移動コスト決定部２０２は、記録媒体２０７に予め格納されている移動コストテーブル（図６）に基づいて、各候補経路の移動コストを決定する。
【００３４】
図６は、本発明の第１の実施形態に係る移動コストテーブルの例を示す図である。
本実施形態では、一のリンケージから他のリンケージに移動する際の移動コスト（最小移動コスト）が記録された移動コストテーブルが、セグメント別に予め作成され、記録媒体２０７に格納されている。
セグメントとは、マップをあるリンケージ（始点リンケージ）から所定距離（例えば１ｋｍ）の範囲毎に分割したものである。例えば、図６に示すように、セグメント１には始点リンケージＡから所定距離の範囲に位置するリンケージＡ〜Ｇが含まれており、セグメント１内の各リンケージから他のリンケージへ移動する際の移動コストがそれぞれ記録されている。マップ上の全てのリンケージの組み合わせに対する移動コストを網羅すると、移動コストテーブルの容量が膨大となる。しかしながら、本実施形態では、セグメント別に移動コストテーブルが作成されているため、移動コストテーブルの容量を低減させることが可能である。
また、最小移動コストとは、あるリンケージから他のリンケージへ移動する際に通るリンクの組み合わせ（経路）が複数ある場合、各経路の移動コストのうち、最も小さい値（最も短い距離）を有する経路の移動コストを示す。図５の例では、リンケージＡからリンケージＦへの経路は複数あるが、リンクＡ−Ｄ及びリンクＤ−Ｆを通る経路の移動コストが最も小さい場合、当該経路の移動コストが最小移動コストとして移動コストテーブルに記録されている。
【００３５】
図７は、本発明の第１の実施形態に係る移動コスト決定部の処理を説明するための図である。
図４及び図７を参照し、移動コスト決定部２０２が候補経路別の移動コストを決定する処理の詳細を説明する。
例えば、位置測定点Ｐ１の候補地点ｘ１と位置測定点Ｐ２の候補地点ｘ２ａとを結ぶ候補経路Ｒ１として、図７に示すように、経路Ｒ１ａ（候補地点ｘ１〜リンケージＥ、リンクＥ−Ｄ、リンケージＤ〜候補地点ｘ２ａ）と、経路Ｒ１ｂ（候補地点ｘ１〜リンケージＣ、リンクＣ−Ｄ、リンケージＤ〜候補地点ｘ２ａ）と、経路Ｒ１ｃ（候補地点ｘ１〜リンケージＥ、リンクＥ−Ｆ、リンケージＦ〜候補地点ｘ２ａ）と、経路Ｒ１ｄ（候補地点ｘ１〜リンケージＣ、リンクＣ−Ｆ、リンケージＦ〜候補地点ｘ２ａ）の四つの経路があるとする。
移動コスト決定部２０２は、各経路Ｒ１ａ〜Ｒ１ｄの移動コストを算出する。例えば、経路Ｒ１ａの移動コストを算出する場合、移動コスト決定部２０２は、候補地点ｘ１からリンケージＥまでの移動コスト（距離）と、リンケージＤから候補地点ｘ２ａまでの移動コスト（距離）とをマップに基づいて算出するとともに、移動コストテーブルからリンクＥ−Ｄの移動コストを取得する。そして、移動コスト決定部２０２は、候補地点ｘ１からリンケージＥまでの移動コスト（１．７ｍ）と、リンクＥ−Ｄの移動コスト（２２ｍ）と、リンケージＤから候補地点ｘ２ａまでの移動コスト（５．３ｍ）とを合計して、経路Ｒ１ａの移動コスト（２９ｍ）を求める。
移動コスト決定部２０２は、同様に、経路Ｒ１ｂ〜Ｒ１ｄの移動コストを求める。なお、図５に示すように、リンクＤ−Ｆの属性情報として、リンケージＤからリンケージＦへの通行のみが許可された一方通行であることを示す情報が含まれている場合、移動コスト決定部２０２は、リンケージＦから候補地点ｘ２ａへの移動は一方通行を逆行するため不可能であると判断する。このため、移動コスト決定部２０２は、リンケージＦから候補地点ｘ２ａまでの移動コストを「∞ｍ」とする。この結果、リンケージＦから候補地点ｘ２ａまでの移動を含む経路Ｒ１ｃ及び経路Ｒ１ｄの移動コストは「∞ｍ」となる。
移動コスト決定部２０２は、このように算出した経路Ｒ１ａ〜Ｒ１ｄの移動コストのうち、最も小さい（最も距離が短い）値を有する移動コストを、候補地点ｘ１から候補地点ｘ２ａまでの候補経路Ｒ１の移動コストとして決定する。図７の例では、経路Ｒ１ａの移動コスト（２９ｍ）が最も小さい値であるため、移動コスト決定部２０２は、候補地点ｘ１から候補地点ｘ２ａまでの候補経路Ｒ１の移動コストを「２９ｍ」と決定する。
移動コスト決定部２０２は、上述の処理を繰り返し、各候補経路Ｒ１〜Ｒ３の移動コストを決定する。
【００３６】
次に、移動可能距離推定部２０３は、位置測定点Ｐｉを測定した時点（位置測定点Ｐ２の測定日時）における移動体の速度と、一つ前の位置測定点Ｐｉ−１を測定した時点（位置測定点Ｐ１の測定日時）における移動体の速度と、に基づいて、位置測定点Ｐ１の測定日時ｔ１（以下、時間ｔ１）から位置測定点Ｐ２の測定日時ｔ２（以下、時間ｔ２）までの間に移動体（機器ＩＤにより特定されるクライアントＡを搭載した移動体）が移動可能な移動可能距離を推定する（ステップＳ１０３）。
【００３７】
図８は、本発明の第１の実施形態に係る移動可能距離推定部の処理を説明するための第１の図である。
図８に示すように、移動体が時間ｔ１において速度Ｖ１で走行しており、時間ｔ２において速度Ｖ２で走行しているとする。この場合、移動可能距離推定部２０３は、移動体が速度Ｖ１から移動体の最高速度Ｖｍａｘまで加速し、最高速度Ｖｍａｘで走行を継続した後、速度Ｖ２まで減速したと仮定して、時間ｔ１から時間ｔ２までの間に移動体が移動可能な移動可能距離（最大移動可能距離）を推定する。
なお、本実施形態では、移動体の種類（車両、歩行者等）別に最高速度Ｖｍａｘ、加速性能及び減速性能が予め設定されている。また、移動可能距離推定部２０３は、機器ＩＤに基づいて移動体の種類を特定する。
図８の例では、移動可能距離推定部２０３は、時間ｔ１において速度Ｖ１から加速を開始し、最高速度Ｖｍａｘに到達するまでの移動体の速度Ｖの推移（加速度の傾き）を、移動体の加速性能に基づいて仮定する。また、移動可能距離推定部２０３は、時間ｔ２までに最高速度Ｖｍａｘから速度Ｖ２に到達するような移動体の速度Ｖの推移（減速度の傾き）を、移動体の減速性能に基づいて仮定する。移動可能距離推定部２０３は、このように仮定した時間ｔ１から時間ｔ２までの移動体の速度の推移に基づいて、当該移動体が移動可能な移動可能距離を推定する。図８に示すように、加速度の傾き、最高速度Ｖｍａｘ、減速度の傾きの内側の面積Ｍ１が、移動体の移動可能距離を示す。
【００３８】
図９は、本発明の第１の実施形態に係る移動可能距離推定部の処理を説明するための第２の図である。
位置測定点Ｐ１の測定日時ｔ１から位置測定点Ｐ２の測定日時ｔ２までの時間が短い場合等、時間ｔ１から時間ｔ２までの間に移動体の最高速度Ｖｍａｘに到達しない場合がある。この場合、移動可能距離推定部２０３は、移動体の加速性能に基づく加速度の傾きと、移動体の減速性能に基づく減速度の傾きとが交わるピーク速度Ｖｐｅａｋが、時間ｔ１から時間ｔ２の間における移動体のピーク速度であると仮定する。即ち、移動可能距離推定部２０３は、移動体が時間ｔ１において速度Ｖ１から加速を開始し、ピーク速度Ｖｐｅａｋに到達するまで加速を継続すると仮定する。そして、移動可能距離推定部２０３は、ピーク速度Ｖｐｅａｋに到達した時点から減速を開始し、時間ｔ２において速度Ｖ２に到達すると仮定する。移動可能距離推定部２０３は、このように求めた時間ｔ１から時間ｔ２までの移動体の速度の推移に基づいて、当該移動体が移動可能な移動可能距離を推定する。図９に示すように、加速度の傾き及び減速度の傾きの内側の面積Ｍ２が、移動体の移動可能距離を示す。
【００３９】
次に、移動可否判定部２０４は、移動コスト決定部２０２が決定した候補経路別（候補経路Ｒ１〜Ｒ３）の移動コストと、移動可能距離推定部２０３が推定した移動体の移動可能距離とに基づいて、移動体が各候補経路を移動可能であるか否かを判定する（ステップＳ１０４）。
本実施形態における移動コストは、実際に移動体が移動した経路ではなく、候補経路別に想定される複数の経路のうち、最も移動コストが小さい（距離が短い）経路の移動コストを示している。また、本実施形態における移動可能距離は、実際に移動体が移動した距離ではなく、位置測定点Ｐｉ−１の測定日時ｔｉ−１から位置測定点Ｐｉの測定日時ｔｉまでに、位置測定点Ｐｉ−１及び位置測定点Ｐｉにおける移動体の速度から考えられる速度のうち最も早い速度で移動体が移動した場合の、最大の移動距離を示している。即ち、本実施形態の移動可否判定部２０４は、移動体が、位置測定点Ｐｉと位置測定点Ｐｉ−１との間を、最大の速度で、且つ、最短の経路を通って移動したと仮定した場合に、候補経路が移動可能であるか否かを判定するものである。
上述の例では、移動可否判定部２０４は、移動可能距離（例えば「３７ｍ」）よりも候補経路Ｒ１の移動コスト（例えば「２９ｍ」）及び候補経路Ｒ３の移動コスト（例えば「３５ｍ」）が小さい場合、候補経路Ｒ１及び候補経路Ｒ３は移動可能であると判定する。一方、移動可否判定部２０４は、移動可能距離よりも候補経路Ｒ２の移動コスト（例えば「３９ｍ」）が大きい場合、候補経路Ｒ２は移動不可能であると判定する。
【００４０】
次に、スコア算出部２０５は、位置測定点Ｐ２と、位置測定点Ｐ２の候補地点ｘ２ａ〜ｘ２ｃとの距離に基づいて、候補地点別のスコアを算出する（ステップＳ１０５）。
なお、スコア算出部２０５は、移動可能であると判定された候補経路に含まれる候補地点のスコアのみを算出するようにしてもよい。
また、スコア算出部２０５は、位置測定点が測定された時点における移動方向と、当該位置測定点の候補地点が位置するリンクの延びる方向とに基づいて、スコアを増減させるようにしてもよい。例えば、位置測定点Ｐ２が測定された時点における移動方向が「南」（図２）である場合、スコア算出部２０５は、位置測定点Ｐ２における移動方向（南）と、候補地点ｘ２ａが位置するリンクＤ−Ｆの延びる方向（東西）とが一致しないため、スコアを増加させる係数を乗じるようにしてもよい。一方、スコア算出部２０５は、位置測定点Ｐ２における移動方向（南）と、候補地点ｘ２ｃが位置するリンクＤ−Ｇの延びる方向（南北）とが一致するため、スコアを変化させない、又は、スコアを減じる係数を乗じるようにしてもよい。
【００４１】
次に、マッチング地点決定部２０６は、移動可否判定部２０４が移動可能であると判定した候補経路に含まれる候補地点のうち、スコアの値が最も小さい候補地点を、マッチング地点として決定する（ステップＳ１０６）。
例えば、移動可否判定部２０４が移動可能であると判定した候補経路Ｒ１に含まれる候補地点ｘ２ａのスコアと、候補経路Ｒ３に含まれる候補地点ｘ２ｃのスコアとを比較する。
例えば、位置測定点Ｐ２と候補地点ｘ２ａとの距離に基づいて算出されたスコアが「０．３」であり、位置測定点Ｐ２と候補地点ｘ２ｃとの距離に基づいて算出されたスコアが「０．５」であるとする。この場合、候補地点ｘ２ｃのスコアよりも候補地点ｘ２ａのスコアの方が小さいため、マッチング地点決定部２０６は、候補地点ｘ２ａを位置測定点Ｐ２に対するマッチング地点として決定する。
【００４２】
次に、マッチング地点決定部２０６は、決定したマッチング地点（候補地点ｘ２ａ）を、位置測定点Ｐ２と関連づけて、マッチングデータ記録部３０に記録する（ステップＳ１０７）。
【００４３】
マップマッチング装置２０は、位置測定点Ｐｉ（位置測定点Ｐ２）のマップマッチング処理を完了すると、ステップＳ１００に戻り、次の位置測定点Ｐｉ＋１（位置測定点Ｐ３）を対象として、上述のマップマッチング処理を繰り返し行う。
【００４４】
（マップマッチング装置のハードウェア構成）
図１０は、本発明の第１の実施形態に係るマップマッチング装置のハードウェア構成の例を示す図である。
以下、本実施形態のマップマッチング装置２０のハードウェア構成の例について、図１０を参照して説明する。
【００４５】
コンピュータ９００は、ＣＰＵ９０１、主記憶装置９０２、補助記憶装置９０３、入出力インタフェース９０４、通信インタフェース９０５を備える。
上述のマップマッチング装置２０は、コンピュータ９００に実装される。そして、上述した各処理部の動作は、プログラムの形式で補助記憶装置９０３に記憶されている。ＣＰＵ９０１は、プログラムを補助記憶装置９０３から読み出して主記憶装置９０２に展開し、当該プログラムに従って上記処理を実行する。また、ＣＰＵ９０１は、プログラムに従って、記録媒体２０７に対応する記憶領域を主記憶装置９０２に確保する。また、ＣＰＵ９０１は、プログラムに従って、処理中のデータを記憶する記憶領域を補助記憶装置９０３に確保する。なお、コンピュータ９００は、入出力インタフェース９０４を介して、外部記憶装置９１０と接続されており、記録媒体２０７に対応する記憶領域は外部記憶装置９１０に確保されてもよい。また、コンピュータ９００は、通信インタフェース９０５を介して、外部記憶装置９２０と接続されており、記録媒体２０７に対応する記憶領域は外部記憶装置９２０に確保されてもよい。
【００４６】
なお、少なくとも１つの実施形態において、補助記憶装置９０３は、一時的でない有形の媒体の一例である。一時的でない有形の媒体の他の例としては、入出力インタフェース９０４を介して接続される磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等が挙げられる。また、このプログラムが通信回線によってコンピュータ９００に配信される場合、配信を受けたコンピュータ９００が当該プログラムを主記憶装置９０２に展開し、上記処理を実行しても良い。
【００４７】
また、当該プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、当該プログラムは、前述した機能を補助記憶装置９０３に既に記憶されている他のプログラムとの組み合わせで実現するもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００４８】
また、マップマッチング装置２０は、１台のコンピュータ９００で構成されていても良いし、通信可能に接続された複数のコンピュータで構成されていてもよい。
【００４９】
（作用効果）
以上のように、本実施形態に係るマップマッチング装置２０は、位置測定点に基づいて一つ又は複数の候補地点をリンク上に抽出する候補地点抽出部２０１と、位置測定点Ｐ２に基づいて抽出された候補地点ｘ２ａ〜ｘ２ｃ（第１候補地点）のうちの一つと、位置測定点（一つ前の位置測定点）Ｐ１に基づいて抽出された候補地点ｘ１（第２候補地点）と、を結ぶリンク（候補経路Ｒ１〜Ｒ３）の移動コストを、候補地点ｘ２ａ〜ｘ２ｃと候補地点ｘ１との組み合わせ別に決定する移動コスト決定部２０２と、移動コストに基づいて、移動体が候補地点ｘ２ａ〜ｘ２ｃのうちの一つから候補地点ｘ１まで移動可能であるか否かを、候補経路別に判定する移動可否判定部２０４と、移動可否判定部２０４が移動可能であると判定した候補経路に含まれる候補地点ｘ２ａ〜ｘ２ｃのうち何れか一つを、マップ上における移動体の位置（マッチング地点）として決定するマッチング地点決定部２０６と、を備える。
このようにすることで、位置測定点Ｐ２と位置測定点Ｐ１との道のりが離れており、位置測定点Ｐ１及びＰ２を結ぶ候補経路が複数ある場合であっても、移動可否判定部２０４が移動コストに基づいて各候補経路が移動可能であるか否かを判定することにより、移動可能な候補地点のみをマップ上における移動体の位置（マッチング地点）として決定することができる。従って、マップマッチング装置２０は、位置測定点の収集間隔が長い場合であっても、マップ上における移動体の位置を決定することが可能となる。
【００５０】
また、移動コスト決定部２０２は、一のリンケージと他のリンケージとを結ぶ一つ又は複数のリンクの移動コストを、リンケージ別に予め記録した移動コストテーブルに基づいて、候補経路別に移動コストを決定する。
このようにすることで、候補地点とリンケージ間の距離以外の、リンケージ間の移動コストは予め移動コストテーブルに記録されているため、移動コスト決定部２０２が移動コストを決定する処理を短縮化することができる。また、移動コスト決定部２０２は、候補経路が複数ある場合であっても、移動コストテーブルに基づいて、各候補経路の移動コストを容易に決定することができる。
【００５１】
また、マップマッチング装置２０は、位置測定点Ｐ１、Ｐ２における移動体の速度を取得し、当該速度に基づいて、位置測定点Ｐ１が測定された時間と、位置測定点Ｐ２が測定された時間との間に移動体が移動可能な移動可能距離を推定する移動可能距離推定部２０３を更に備える。移動可否判定部２０４は、移動可能距離よりも候補経路の移動コストが小さい場合、移動体が当該候補経路を移動可能であると判定する。
このようにすることで、移動可否判定部２０４は、位置測定点Ｐ１が測定された時間から位置測定点Ｐ２が測定された時間までの間に移動体が移動可能な距離を推定することにより、移動可否判定部２０４における移動可否の判定の精度を向上させることができる。
【００５２】
また、マップマッチング装置２０は、位置測定点Ｐ２と、当該位置測定点Ｐ２に関連する候補地点Ｘ２ａ〜ｘ２ｃとの距離に基づいて、候補地点別のスコアを算出するスコア算出部２０５を更に備える。マッチング地点決定部２０６は、スコアに基づいて、移動可否判定部２０４が移動可能であると判定した候補経路に含まれる候補地点のうち何れか一つを、マップ上における移動体の位置として決定する。
このようにすることで、移動可能であると判定された候補経路が複数ある場合、当該候補経路に含まれる候補地点のスコアに基づいて、マップ上における移動体の位置を決定することができる。
【００５３】
＜第２の実施形態＞
以下、第２の実施形態に係るマップマッチングシステム１について、図１１〜図１４を参照して説明する。
第１の実施形態と共通の構成要素には同一の符号を付して詳細説明を省略する。
なお、第１の実施形態では、位置測定点Ｐｉに対するマップマッチング処理を行いマッチング地点を決定した後に、次の位置測定点Ｐｉ＋１に対する新たなマップマッチング処理を行う態様について説明したが、本実施形態では、複数の位置測定点に対してマップマッチング処理を行う点で第１の実施形態と異なっている。
【００５４】
（マップマッチングシステムの処理フロー）
図１１は、本発明の第２の実施形態に係るマップマッチング装置の処理フローを示す図である。
図１１に示すように、まず、候補地点抽出部２０１は、位置測定点収集部１０からマップマッチング処理の対象となる複数の位置測定点を取得する（ステップＳ２００）。
本実施形態では、候補地点抽出部２０１は、ある機器ＩＤを有する複数の位置測定点のうち、任意の期間内に測定された位置測定点Ｐｉ〜Ｐｉ＋ｎをマップマッチング処理の対象として取得する。なお、他の実施形態においては、ある機器ＩＤを有する複数の位置測定点のうち、所定の個数（ｎ個）をマップマッチング処理の対象として取得するようにしてもよい。
以下の例では、候補地点抽出部２０１が、マップマッチング処理の対象となる位置測定点Ｐｉ〜Ｐｉ＋ｎとして、機器ＩＤ「０００００００１」を有する位置測定点Ｐ３〜Ｐ５を選択した場合について説明する。
【００５５】
次に、候補地点抽出部２０１は、位置測定点Ｐ３〜Ｐ５の候補地点を抽出する（Ｓ２０１）。
候補地点抽出部２０１が各位置測定点の候補地点を抽出する処理は、第１の実施形態と同様である。
図１２は、本発明の第２の実施形態に係るマップマッチング装置の機能を説明するための図である。
ここでは、候補地点抽出部２０１は、図１２に示すように、位置測定点Ｐ３の候補地点として「ｘ３ａ」及び「ｘ３ｂ」を抽出し、位置測定点Ｐ４の候補地点として「ｘ４ａ」及び「ｘ４ｂ」を抽出し、位置測定点Ｐ５の候補地点として「ｘ５ａ」及び「ｘ５ｂ」を抽出したとする。
【００５６】
次に、移動コスト決定部２０２は、位置測定点Ｐｉに基づいて抽出された候補地点（第１候補地点）のうちの一つと、位置測定点Ｐｉの一つ前の位置測定点Ｐｉ−１に基づいて抽出された候補地点（第２候補地点）のうちの一つと、を結ぶリンクの移動コストを、候補地点の組み合わせ（候補経路）別に決定する（ステップＳ２０２）。
図１３は、本発明の第２の実施形態に係る移動コスト決定部の処理を説明するための図である。
具体的には、図１３に示すように、移動コスト決定部２０２は、位置測定点Ｐ３の候補地点ｘ３ａ〜ｘ３ｂと、一つ前の位置測定点Ｐ２の候補地点ｘ２（不図示）とを結ぶ候補経路Ｒ２１〜Ｒ２２の移動コストを、移動コストテーブル（図６）に基づいて、それぞれ決定する。なお、一つ前の位置測定点Ｐ２がステップＳ２００において取得した複数の位置測定点に含まれていない場合、マッチングデータ記録部３０から位置測定点Ｐ２に関連する候補地点の情報を読み出す。
また、移動コスト決定部２０２は、位置測定点Ｐ４の候補地点ｘ４ａ〜ｘ４ｂ及び一つ前の位置測定点Ｐ３の候補地点ｘ３ａ〜ｘ３ｂを結ぶ候補経路Ｒ３１〜Ｒ３４と、位置測定点Ｐ５の候補地点ｘ５ａ〜ｘ５ｂ及び一つ前の位置測定点Ｐ４の候補地点ｘ４ａ〜ｘ４ｂを結ぶ候補経路Ｒ４１〜Ｒ４４との移動コストも、同様に移動コストテーブルに基づいて、それぞれ決定する。
【００５７】
次に、移動可能距離推定部２０３は、位置測定点Ｐｉを測定した時点（位置測定点Ｐｉの測定日時）における移動体の速度と、一つ前の位置測定点Ｐｉ−１を測定した時点（位置測定点Ｐｉ−１の測定日時）における移動体の速度と、に基づいて、位置測定点Ｐｉ−１の測定日時から位置測定点Ｐｉの測定日時までの間に移動体（機器ＩＤにより特定されるクライアントＡを搭載した移動体）が移動可能な移動可能距離（最大移動可能距離）を推定する（ステップＳ２０３）。
具体的には、移動可能距離推定部２０３は、まず、位置測定点Ｐ３の測定日時と、一つ前の位置測定点Ｐ２の測定日時との間に移動体が移動可能な移動可能距離を推定する。なお、一つ前の位置測定点Ｐ２がステップＳ２００において取得した複数の位置測定点に含まれていない場合、マッチングデータ記録部３０から位置測定点Ｐ２に関連する測定日時及び速度の情報を読み出す。
また、移動可能距離推定部２０３は、位置測定点Ｐ４の測定日時及び位置測定点Ｐ３の測定日時の間に移動体が移動可能な移動可能距離と、位置測定点Ｐ５の測定日時及び位置測定点Ｐ４の測定日時の間に移動体が移動可能な移動可能距離とを、それぞれ推定する。移動可能距離推定部２０３が移動可能距離を推定する処理は、第１の実施形態と同様である。
【００５８】
次に、移動可否判定部２０４は、移動コスト決定部２０２が決定した候補経路別の移動コストと、移動可能距離推定部２０３が推定した移動体の移動可能距離とに基づいて、移動体が各候補経路を移動可能であるか否かを判定する（ステップＳ２０４）。
具体的には、図１３に示すように、移動可否判定部２０４は、候補経路Ｒ２１〜Ｒ２２のそれぞれの移動コストと、位置測定点Ｐ２の測定日時から位置測定点Ｐ３の測定日時までの間の移動体の移動可能距離（例えば「１５ｍ」）とを比較して、移動可能距離よりも小さい移動コストを有する候補経路Ｒ２１、Ｒ２２は移動可能であると判定する。
同様に、移動可否判定部２０４は、候補経路Ｒ３１〜Ｒ３４のそれぞれの移動コストと、位置測定点Ｐ３の測定日時から位置測定点Ｐ４の測定日時までの間の移動体の移動可能距離（例えば「５．５ｍ」）とを比較して、移動可能距離よりも小さい移動コストを有する候補経路Ｒ３１、Ｒ３２、Ｒ３３は移動可能であると判定し、移動可能距離よりも大きい移動コストを有する候補経路Ｒ３４は移動不可能であると判定する。また、移動可否判定部２０４は、候補経路Ｒ４１〜Ｒ４４のそれぞれの移動コストと、位置測定点Ｐ４の測定日時から位置測定点Ｐ５の測定日時までの間の移動体の移動可能距離（例えば「３５ｍ」）とを比較して、移動可能距離よりも小さい移動コストを有する候補経路Ｒ４２、Ｒ４４は移動可能であると判定し、移動可能距離よりも大きい移動コストを有する候補経路Ｒ４１、Ｒ４３は移動不可能であると判定する。
【００５９】
次に、スコア算出部２０５は、位置測定点Ｐｉと、位置測定点Ｐｉの候補地点との距離に基づいて、候補地点別のスコアを算出する（ステップＳ２０５）。
図１４は、本発明の第２の実施形態に係るスコア算出部の処理を説明するための図である。
具体的には、図１４に示すように、スコア算出部２０５は、位置測定点Ｐ３と、位置測定点Ｐ３の候補地点ｘ３ａ〜ｘ３ｂとの距離に基づいて、候補地点ｘ３ａ〜ｘ３ｂのスコアをそれぞれ算出する。また、スコア算出部２０５は、位置測定点Ｐ４と、位置測定点Ｐ４の候補地点ｘ４ａ〜ｘ４ｂとの距離に基づいて、候補地点ｘ４ａ〜ｘ４ｂのスコアをそれぞれ算出する。更に、スコア算出部２０５は、位置測定点Ｐ５と、位置測定点Ｐ５の候補地点ｘ５ａ〜ｘ５ｂとの距離に基づいて、候補地点ｘ５ａ〜ｘ５ｂのスコアをそれぞれ算出する。スコア算出部２０５がスコアを算出する処理は、第１の実施形態と同様である。
【００６０】
次に、マッチング地点決定部２０６は、移動可否判定部２０４が移動可能であると判定した候補経路に基づいて、ステップＳ２００で取得した位置測定点Ｐｉから位置測定点Ｐｉ＋ｎに移動可能な候補経路の組み合わせを抽出する。即ち、マッチング地点決定部２０６は、ステップＳ２００で取得した位置測定点Ｐｉ〜Ｐｉ＋ｎのそれぞれから一つずつ候補地点を選択して組み合わせた候補地点の組み合わせのうち、移動可否判定部２０４が移動可能であると判定した候補経路に全ての候補地点が含まれる組み合わせを抽出する。また、マッチング地点決定部２０６は、スコア算出部２０５が算出した各候補地点のスコアに基づいて、候補地点のスコアの合計を、候補地点の組み合わせ（候補経路）別に求める。そして、マッチング地点決定部２０６は、スコアの合計が最も小さい組み合わせに含まれる候補地点を、各位置測定点に対するマッチング地点として決定する（ステップＳ２０６）。
具体的には、マッチング地点決定部２０６は、移動可否判定部２０４が移動可能であると判定した候補経路に基づいて、移動可能な候補地点の組み合わせ（候補経路）として、組み合わせＣ１（Ｒ２１（ｘ２〜ｘ３ａ）、Ｒ３１（ｘ３ａ〜ｘ４ａ）、Ｒ４２（ｘ４ａ〜ｘ５ｂ））と、組み合わせＣ２（Ｒ２１（ｘ２〜ｘ３ａ）、Ｒ３２（ｘ３ａ〜ｘ４ｂ）、Ｒ４４（ｘ４ｂ〜ｘ５ｂ））と、組み合わせＣ３（Ｒ２２（ｘ２〜ｘ３ｂ）、Ｒ３３（ｘ３ｂ〜ｘ４ａ）、Ｒ４２（ｘ４ａ〜ｘ５ｂ））とを抽出する。
また、マッチング地点決定部２０６は、スコア算出部２０５が算出した各候補地点のスコア（図１３）に基づいて、組み合わせＣ１のスコアの合計（「０．８」）と、組み合わせＣ２のスコアの合計（「０．７」）と、組み合わせＣ３のスコアの合計（「１．１」）とを求める。そして、マッチング地点決定部２０６は、スコアの合計が最も小さい組み合わせＣ２に含まれる候補地点ｘ３ａ、ｘ４ｂ、ｘ５ｂを、それぞれ、位置測定点Ｐ３、Ｐ４、Ｐ５のマッチング地点として決定する。
【００６１】
次に、マッチング地点決定部２０６は、決定したマッチング地点（候補地点ｘ３ａ、ｘ４ｂ、ｘ５ｂ）のそれぞれを、位置測定点Ｐ３、Ｐ４、Ｐ５と関連づけて、マッチングデータ記録部３０に記録する（ステップＳ２０７）。
【００６２】
マップマッチング装置２０は、ステップＳ２００において取得した位置測定点Ｐｉ〜Ｐｉ＋ｎ（位置測定点Ｐ３〜Ｐ５）のマップマッチング処理を完了すると、ステップＳ２００に戻り、次の位置測定点Ｐｉ＋ｎ＋１以降を対象として、上述のマップマッチング処理を繰り返し行う。
【００６３】
（作用効果）
以上のように、本実施形態に係るマップマッチング装置２０において、移動コスト決定部２０２は、一の位置測定点Ｐｉに基づいて抽出された候補地点（第１候補地点）のうちの一つと、他の位置測定点Ｐｉ−１に基づいて抽出された候補地点（第２候補地点）のうちの一つと、を結ぶ候補経路の移動コストを、候補経路別に決定する。マッチング地点決定部２０６は、移動可否判定部２０４が移動可能であると判定した候補経路に基づいて、ステップＳ２００で取得した位置測定点Ｐｉから位置測定点Ｐｉ＋ｎに移動可能な候補地点の組み合わせ（候補経路）を抽出する。また、マッチング地点決定部２０６は、スコア算出部２０５が算出した各候補地点のスコアに基づいて、候補地点のスコアの合計を、候補地点の組み合わせ（候補経路）別に求める。そして、マッチング地点決定部２０６は、スコアの合計が最も小さい組み合わせに含まれる候補地点を、各位置測定点に対するマッチング地点として決定する。
例えば、第１の実施形態のように、位置測定点別に、スコアが最も少ない候補地点をマッチング地点として決定する場合、位置測定点と、当該位置測定点の実際の道路上の位置との誤差が大きい場合、誤った候補地点をマッチング地点として決定してしまうことが考えられる。誤った候補地点に基づいて、次の位置測定点の候補地点を決定することにより、次の位置測定点以降のマッチング地点も誤って決定してしまう可能性がある。
しかしながら、本実施形態では、マッチング地点決定部２０６は、移動体が移動可能な位置測定点Ｐｉ〜Ｐｉ＋ｎの候補地点の組み合わせうち、スコアの合計が最も小さい組み合わせを抽出して、各位置測定点Ｐｉ〜Ｐｉ＋ｎに対するマッチング地点を決定するようにしている。このため、複数の位置測定点Ｐｉ〜Ｐｉ＋ｎの中に、大きな誤差を有する位置測定点が含まれている場合であっても、候補地点の組み合わせ別のスコアの合計を参照して総合的に候補地点の妥当性を判定することができる。従って、マッチング地点決定部２０６が各位置測定点Ｐｉ〜Ｐｉ＋ｎに対するマッチング地点を決定する精度を向上させることができる。
【００６４】
なお、上述の処理フローでは、移動コスト決定部２０２が、ステップＳ２００において取得した位置測定点Ｐｉ〜Ｐｉ＋ｎ（位置測定点Ｐ３〜Ｐ５）の全ての候補経路の移動コストを決定する処理（ステップＳ２０２）を行う態様について説明したが、これに限られることはない。
他の実施形態においては、移動コスト決定部２０２は、複数の位置測定点Ｐｉ〜Ｐｉ＋ｎのうちの一つの位置測定点Ｐｉ（位置測定点Ｐ３）の候補経路の移動コストを決定すると、次のステップＳ２０３〜Ｓ２０４に進むようにしてもよい。そして、ステップＳ２０４の処理が完了した際に、移動コストが決定されていない他の位置測定点Ｐｉ＋１がある場合は、再びステップＳ２０２に戻るようにしてもよい。
この場合、例えば、移動可否判定部２０４がステップＳ２０４において位置測定点Ｐ３の候補地点ｘ３ｂを含む全ての候補経路が移動不可能であると判定した後、ステップＳ２０２へ戻って次の位置測定点Ｐ４に対する処理を行う場合、移動コスト決定部２０２は、位置測定点Ｐ４の候補経路Ｒ３１〜Ｒ３３のうち、候補地点ｘ３ｂを含む候補経路Ｒ３３、Ｒ３４を除外して、移動コストを決定する処理を行うようにしてもよい。
【００６５】
以上、本発明の実施形態について詳細に説明したが、本発明の技術的思想を逸脱しない限り、これらに限定されることはなく、多少の設計変更等も可能である。
例えば、上述の実施形態において、移動コストテーブルは、始点リンケージから所定距離（例えば１ｋｍ）の範囲毎に分割したセグメント別に作成されている態様について説明したが、これに限られることはない。他の実施形態では、所定距離は、位置測定点の収集間隔（クライアントＡが位置測定点収集部１０へ位置測定点を送信する時間間隔）と、移動体別に予め設定された速度（例えば車両は１２０ｋｍ／ｈ、歩行者は４ｋｍ／ｈ等）とに基づいて、変更してもよい。この場合、例えば、所定距離は、ある位置測定点が送信されてから次の位置測定点が送信されるまでの間に、移動体が移動可能な距離よりも大きくなるように設定される。
【００６６】
また、上述の実施形態では、移動コストとは、一のリンケージと他のリンケージとを結ぶ一つ又は複数のリンクの長さ（距離）の合計を、リンケージの組み合わせ別に示す態様について説明したが、これに限られることはない。他の実施形態では、移動コストは、リンケージ間を結ぶ一つ又は複数のリンクを移動する際の所要時間であってもよい。また、移動コストは、各リンクの属性に応じて増減させてもよい。例えば、リンク間の移動に右左折を伴う場合は、直進する場合よりも移動コストを増加させてもよいし、リンクが坂道、カーブ等を含むことを示す属性を有している場合は、移動コストを増加させるようにしてもよい。更に、各リンクの制限速度を示す属性に応じて各リンクの移動コストを増減させるようにしてもよい。各リンクの移動コストを増減させる際には、属性に応じて所定の値を増減（αｍ増減、α秒増減等）させてもよいし、所定の係数を乗じてもよい。
【産業上の利用可能性】
【００６７】
上述のマップマッチング装置、マップマッチングシステム、マップマッチング方法及びプログラムによれば、位置測定点の収集間隔が長い場合であっても、マップ上における移動体の位置を決定することが可能となる。
【符号の説明】
【００６８】
１  マップマッチングシステム
１０  位置測定点収集部
２０  マップマッチング装置
２０１  候補地点抽出部
２０２  移動コスト決定部
２０３  移動可能距離推定部
２０４  移動可否判定部
２０５  スコア算出部
２０６  マッチング地点決定部
２０７  記録媒体
２０８  運行管理部
３０  マッチングデータ記録部
９００  コンピュータ
９０１  ＣＰＵ
９０２  主記憶装置
９０３  補助記憶装置
９０４  入出力インタフェース
９０５  通信インタフェース
９１０、９２０  外部記憶装置
【図１】
0006754444.tif 000002
【図２】
0006754444.tif 000003
【図３】
0006754444.tif 000004
【図４】
0006754444.tif 000005
【図５】
0006754444.tif 000006
【図６】
0006754444.tif 000007
【図７】
0006754444.tif 000008
【図８】
0006754444.tif 000009
【図９】
0006754444.tif 000010
【図１０】
0006754444.tif 000011
【図１１】
0006754444.tif 000012
【図１２】
0006754444.tif 000013
【図１３】
0006754444.tif 000014
【図１４】
0006754444.tif 000015