(57)【要約】【課題】移動軌跡点の間隔が広くても、また移動軌跡の始点と終点の位置情報に誤差が含まれていても、より正確に経路を決定可能とする。【解決手段】位置座標プロット部１３は、プローブ１の位置情報（座標データ）に従って、デジタル道路地図（データベース）１２の道路地図上にプロットする。照合候補点取得部１４は、移動軌跡点の各々について、所定範囲内で、近傍を通過する全ての稜線上に照合候補点を求める。コスト算出部１５は、移動軌跡点の各々から照合候補点までの距離に比例したコストを算出する。経路探索部１６は、始点および終点を含む移動軌跡点に対する照合候補点を通過する経路を探索し、探索経路毎に、探索経路上の照合候補点のコストを合計する。照合位置確定部１７は、各探索経路のコスト合計が最小となる探索経路の照合候補点を照合位置とする。【選択図】  図１
2004325083.tif 000002
【特許請求の範囲】
【請求項１】
プローブの軌跡点の座標データを入力する座標入力手段と、
頂点と稜線とで構成され、グラフ構造を有する地図データを予め記憶する記憶手段と、
前記座標入力手段から入力された座標データに基づいて、前記記憶手段に記憶されている地図データ上に軌跡点をプロットする軌跡点プロット手段と、
移動軌跡点の各々に対して、近傍を通過する全ての稜線上の近接点を照合候補点として求める照合候補点取得手段と、
照合候補点が置かれている稜線について、各照合候補点から移動軌跡点までの距離に比例し、当該稜線上の照合候補点の数に反比例するコストを算出するコスト算出手段と、
移動軌跡点の各々に対する照合候補点を通過する経路を探索する経路探索手段と、
前記経路探索手段により探索された経路上の稜線のコストの合計を算出するコスト合計算出手段と、
前記コスト合計算出手段により算出されたコストの合計が最小となる探索経路上の照合候補点を照合位置として決定する決定手段と
を具備することを特徴とする経路決定装置。
【請求項２】
前記照合候補点取得手段は、
所定の探索範囲内に存在する稜線に対して、移動軌跡点の各々に対する照合候補点を求めることを特徴とする請求項１記載の経路決定装置。
【請求項３】
前記経路探索手段は、
移動軌跡点の始点および終点を、仮想的な稜線と頂点を設定し、一時的に地図データに組み込んで、前記始点から前記終点までの経路探索することを特徴とする請求項１記載の経路決定装置。
【請求項４】
頂点と稜線とで構成され、グラフ構造を有する地図データ上にプロットされたプローブの移動軌跡点の各々に対して、近傍を通過する全ての稜線上の近接点を照合候補点として求め、照合候補点が置かれている稜線について、各照合候補点から移動軌跡点までの距離に比例し、当該稜線上の照合候補点の数に反比例するコストを算出し、移動軌跡点の各々に対する照合候補点を通過する経路を探索し、該探索された経路上の稜線のコストの合計を算出し、該コストの合計が最小となる探索経路上の照合候補点を照合位置として決定することを特徴とする経路決定方法。
【請求項５】
前記照合候補点は、所定の探索範囲内に存在する稜線に対して求められることを特徴とする請求項４記載の経路決定方法。
【請求項６】
移動軌跡点の始点および終点を、仮想的な稜線と頂点を設定し、一時的に地図データに組み込んで、前記始点から前記終点までの経路探索することを特徴とする請求項４記載の経路決定方法。
【請求項７】
頂点と稜線とで構成され、グラフ構造を有する地図データ上にプロットされたプローブの移動軌跡点の各々に対して、近傍を通過する全ての稜線上の近接点を照合候補点として求めるステップと、
照合候補点が置かれている稜線について、各照合候補点から移動軌跡点までの距離に比例し、当該稜線上の照合候補点の数に反比例するコストを算出するステップと、
移動軌跡点の各々に対する照合候補点を通過する経路を探索するステップと、
該探索された経路上の稜線のコストの合計を算出するステップと、
該コストの合計が最小となる探索経路上の照合候補点を照合位置として決定するステップと
をコンピュータに実行させることを特徴とする経路決定プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、経路決定装置、経路決定方法および経路決定プログラムに関する。
【０００２】
【従来の技術】
従来より、交通状況を知るためのデータ収集を目的として、自動車（プローブ）に状況取得（特に、位置情報）のための装置（ＧＰＳ）を搭載し、所定の時間間隔で、位置情報を取得し、これら座標位置を地図の道路上へマッピングし、自動車の経路を探索する技術が知られている（例えば非特許文献１参照）。
【０００３】
従来技術による経路決定方法では、数秒に１度程度の頻度でプローブから取得した位置情報（時刻情報を含む）に従って、各点を道路地図上に配置し、各点を一定範囲で囲む包絡線を描き、該包絡線内の道路上で、始点から終点までの最短経路を探索することにより、プローブの経路を決定する。
【０００４】
【非特許文献１】
Ｋ．  Ｍａｋｉｍｕｒａ，  ｅｔ  ａｌ．：  Ｐｅｒｆｏｒｍａｎｃｅ  ｉｎｄｉｃａｔｏｒ  ｍｅａｓｕｒｅｍｅｎｔ  ｕｓｉｎｇ  ｃａｒ  ｎａｖｉｇａｔｉｏｎ  ｓｙｓｔｅｍｓ，  Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  Ｒｅｓｅａｒｃｈ  Ｂｏａｒｄ  Ａｎｎｕａｌ  Ｍｅｅｔｉｎｇ，  Ｎｏｖ．  ２００１．
【０００５】
【発明が解決しようとする課題】
ところで、今後、自動車だけでなく、人（携帯電話を持ち歩く、あるいは所持して乗り物に乗る）も、プローブとして活用される予定にある。しかしながら、上述した従来技術では、数秒に１度程度の比較的短い間隔でプローブの位置情報を取得することを前提とした考え方であり、例えば、その間隔が数十秒から数分と長くなった場合には、経路を同定できないという問題がある。また、上述した従来技術では、包絡線内の道路上で、移動軌跡の始点と終点それぞれに最も近い地点を起終点として経路探索を行なうので、それが間違っていると、正確な経路探索を行なうことができなくなるという問題がある。
【０００６】
この発明は上述した事情に鑑みてなされたもので、移動軌跡点の間隔が広くても、また移動軌跡の始点と終点の位置情報に誤差が含まれていても、より正確に経路を決定することができる経路決定装置、経路決定方法および経路決定プログラムを提供することを目的とする。
【０００７】
【課題を解決するための手段】
上述した問題点を解決するために、請求項１記載の発明では、プローブの軌跡点の座標データを入力する座標入力手段と、頂点と稜線とで構成され、グラフ構造を有する地図データを予め記憶する記憶手段と、前記座標入力手段から入力された座標データに基づいて、前記記憶手段に記憶されている地図データ上に軌跡点をプロットする軌跡点プロット手段と、移動軌跡点の各々に対して、近傍を通過する全ての稜線上の近接点を照合候補点として求める照合候補点取得手段と、照合候補点が置かれている稜線について、各照合候補点から移動軌跡点までの距離に比例し、当該稜線上の照合候補点の数に反比例するコストを算出するコスト算出手段と、移動軌跡点の各々に対する照合候補点を通過する経路を探索する経路探索手段と、前記経路探索手段により探索された経路上の稜線のコストの合計を算出するコスト合計算出手段と、前記コスト合計算出手段により算出されたコストの合計が最小となる探索経路上の照合候補点を照合位置として決定する決定手段とを具備することを特徴とする。
【０００８】
また、請求項２記載の発明では、請求項１記載の経路決定装置において、前記照合候補点取得手段は、所定の探索範囲内に存在する稜線に対して、移動軌跡点の各々に対する照合候補点を求めることを特徴とする。
【０００９】
また、請求項３記載の発明では、請求項１記載の経路決定装置において、前記経路探索手段は、移動軌跡点の始点および終点を、仮想的な稜線と頂点を設定し、一時的に地図データに組み込んで、前記始点から前記終点までの経路探索することを特徴とする。
【００１０】
また、上述した問題点を解決するために、請求項４記載の発明では、頂点と稜線とで構成され、グラフ構造を有する地図データ上にプロットされたプローブの移動軌跡点の各々に対して、近傍を通過する全ての稜線上の近接点を照合候補点として求め、照合候補点が置かれている稜線について、各照合候補点から移動軌跡点までの距離に比例し、当該稜線上の照合候補点の数に反比例するコストを算出し、移動軌跡点の各々に対する照合候補点を通過する経路を探索し、該探索された経路上の稜線のコストの合計を算出し、該コストの合計が最小となる探索経路上の照合候補点を照合位置として決定することを特徴とする。
【００１１】
また、請求項５記載の発明では、請求項４記載の経路決定方法において、前記照合候補点は、所定の探索範囲内に存在する稜線に対して求められることを特徴とする。
【００１２】
また、請求項６記載の発明では、請求項４記載の経路決定方法において、移動軌跡点の始点および終点を、仮想的な稜線と頂点を設定し、一時的に地図データに組み込んで、前記始点から前記終点までの経路探索することを特徴とする。
【００１３】
また、上述した問題点を解決するために、請求項７記載の発明では、頂点と稜線とで構成され、グラフ構造を有する地図データ上にプロットされたプローブの移動軌跡点の各々に対して、近傍を通過する全ての稜線上の近接点を照合候補点として求めるステップと、照合候補点が置かれている稜線について、各照合候補点から移動軌跡点までの距離に比例し、当該稜線上の照合候補点の数に反比例するコストを算出するステップと、移動軌跡点の各々に対する照合候補点を通過する経路を探索するステップと、該探索された経路上の稜線のコストの合計を算出するステップと、該コストの合計が最小となる探索経路上の照合候補点を照合位置として決定するステップとをコンピュータに実行させることを特徴とする。
【００１４】
この発明では、座標入力手段から入力されたプローブの軌跡点の座標データに基づいて、軌跡点プロット手段により、前記記憶手段に記憶されている地図データ上にプロットし、照合候補点取得手段により、移動軌跡点の各々に対して、近傍を通過する全ての稜線上の近接点を照合候補点として求め、コスト算出手段により、移動軌跡点の各々から照合候補点までの距離に比例したコストを算出し、経路探索手段により、移動軌跡点の各々に対する照合候補点を通過する経路を探索し、コスト合計算出手段により、該探索された経路の各々における照合候補点のコストの合計を算出し、決定手段により、該コストの合計が最小となる探索経路上の照合候補点を照合位置として決定する。したがって、移動軌跡点の間隔が広くても、より正確に経路を決定することが可能となる。
【００１５】
【発明の実施の形態】
以下、図面を用いて本発明の実施の形態を説明する。
Ａ．実施形態の構成
図１は、本発明の実施形態による経路決定システムの構成を示すブロック図である。図１において、プローブ１は、ＧＰＳ装置を搭載した自動車、あるいは携帯する携帯型ＧＰＳ装置やＧＰＳ装置を内蔵（または外付け）した携帯電話などを携帯する人からなる。位置情報取得部２は、ＧＰＳを用いて現在位置を示す位置情報を所定の時間間隔で取得する。送信器３は、位置情報取得部２により取得された位置情報（現在時刻を含む）を送信する。すなわち、プローブ１は、移動しながら位置情報取得部２および送信器３により、所定の時間間隔（例えば、８０秒〜３００秒間隔）で位置情報（現在時刻を含む）を、経路決定装置１０へ送信する。
【００１６】
経路決定装置１０は、受信器１１、デジタル道路地図（データベース）１２、位置座標プロット部１３、照合候補点取得部１４、コスト算出部１５、経路探索部１６および照合位置確定部１７からなる。受信器１１は、上記プローブ１の送信器２からの位置情報（現在時刻を含む）を受信し、位置座標プロット部１２へ供給する。デジタル道路地図１２は、頂点（ノード）と稜線（アーク）で構成され、グラフ構造を有する道路地図データを記憶している。位置座標プロット部１３は、上記プローブの位置情報（座標データ）に従って、デジタル道路地図（データベース）１２の道路地図上にプロットする（以下、移動軌跡点という）。該位置情報には、ＧＰＳ固有の誤差、電波障害などによる誤差（データ抜け）などが含まれており、移動軌跡点が正確に道路上にプロットされるとは限らない。
【００１７】
次に、照合候補点取得部１４は、移動軌跡点の各々について、近傍を通過する全ての稜線上の近接点（移動軌跡点から最小距離となる稜線上の点、すなわち移動軌跡点から稜線上へ垂線を描き、稜線と垂線との交点）を求め、これら近接点を照合候補点とする。このとき、所定の探索範囲（例えば、移動軌跡点と近接点との距離が５０ｍとか１００ｍまでの範囲）を超える場合には、その近接点を除外する。したがって、１つの移動軌跡点には、複数の近接点、すなわち照合候補点が存在することになる。コスト算出部１５は、照合候補点が置かれている稜線について、各照合候補点から移動軌跡点までの距離に比例し、当該稜線上の照合候補点の数に反比例するコストを算出する。すなわち、距離が短いほど、その照合候補点に小さいコストを与え、ある距離以上離れた照合候補点には無限大のコストを与える。また、コストは、照合候補点の数が多いほど小さくなる。
【００１８】
次に、経路探索部１６は、始点および終点を含む移動軌跡点に対する照合候補点を通過する経路を探索する。１つの移動軌跡点には、複数の照合候補点が対応するので、この時点では、複数の経路が得られる。また、経路探索部１６は、移動軌跡の始点および終点を仮想の稜線と仮想の頂点、すなわち照合候補点で地図データのグラフに組み込む。このとき、経路探索部１６は、探索経路毎に、探索経路上の稜線のコストを合計する。照合位置確定部１７は、各探索経路のコスト合計を比較し、コスト合計が最小となる探索経路を求め、該探索経路上の照合候補点を照合位置として決定する。
【００１９】
なお、移動軌跡点を道路地図上にプロットする際、明らかに軌跡がＵターンやループする区間は、照合された経路から抜け落ちてしまい、マップ照合不可の区間となるため、それら移動軌跡点は、前もって除外しておく。また、移動軌跡点が道路地図に含まれない細街路にプロットされた場合には、近傍の代替道路上に照合されることになる。
【００２０】
なお、経路決定装置１０としては、プローブ１からの位置情報を受信してリアルタイムで経路探索を実施してもよいし、一旦、プローブ１から所定期間に取得した位置情報を記憶しておき、記憶した位置情報に対して経路探索を実施しても、あるいはオペレータなどが直接座標データを入力し、入力された座標データを位置情報として経路探索を実施するようにしてもよい。
【００２１】
Ｂ．実施形態の動作
次に、本実施形態の動作について詳細に説明する。ここで、図２は、本実施形態の動作を説明するためのフローチャートである。経路決定装置１０は、プローブ１から所定の時間間隔で送信されてくる、移動軌跡点の位置情報（座標データ）を受信器１１により受信し、位置座標プロット部１３により、上記プローブ１の位置情報に従って、デジタル道路地図１２の道路地図上に移動軌跡点としてプロットしていく（Ｓ１０）。図３には、道路地図上に移動軌跡点（白丸）がプロットされている様子が示されている。位置情報には、ＧＰＳ固有の誤差、電波障害などによる誤差（データ抜け）などが含まれており、移動軌跡点が正確に道路上にプロットされていない。
【００２２】
次に、照合候補点取得部１４により、移動軌跡点の各々について、所定の探索範囲内（例えば、５０ｍとか１００ｍ）で、デジタル道路地図１２の道路地図において、近傍を通過する全ての稜線上の近接点を求め、これら近接点を照合候補点とする（Ｓ１２）。したがって、図３に示すように、１つの移動軌跡点（白丸）には、複数の照合候補点（黒丸）が得られる。
【００２３】
次に、コスト算出部１５により、照合候補点が置かれている稜線について、各照合候補点から移動軌跡点までの距離に比例し、当該稜線上の照合候補点の数に比例するコストを算出する（Ｓ１４）。すなわち、距離が短いほど、その照合候補点に小さいコストを与え、ある距離以上離れた照合候補点には無限大のコストを与える。図３に示す例では、移動軌跡点の各々から照合候補点までの距離が短いほど（短い点線で接続されている照合候補点）、小さなコストが与えられる。また、照合候補点の数が多いほど、コストが小さくなる。
【００２４】
ここで、移動軌跡点のうち、起点と終点については、以下に述べる方法によりコストを算出する。図４に示すように、起点と終点においては、照合候補点までの距離Ｌ０に応じたコストを算出することに加えて、その照合候補点の両端ノードＮ１，Ｎ２に対して、照合候補点からの距離Ｌ１，Ｌ２に応じたコストを加算する。この場合、起点、終点におけるコストは、
【００２５】
コスト＝リンク長（Ｌ１＋Ｌ２）×距離Ｌ０÷定数
【００２６】
なる式により算出する。これは、起点（移動軌跡点）→（Ｌ０）→照合候補点→（Ｌ１）→ノードＮ１、起点（移動軌跡点）→（Ｌ０）→照合候補点→（Ｌ２）→ノードＮ２と辿ったときにかかるコストを、それぞれノードＮ１，Ｎ２の初期到達コストとするためである。これにより、元々道路地図上にない軌跡上の起点、終点は、仮想の稜線と仮想の頂点、すなわち照合候補点で地図データのグラフに組み込れ、道路上のノードＮ１、Ｎ２のいずれかに対応付けられる。
【００２７】
次に、経路探索部１６により、始点および終点を含む移動軌跡点に対する照合候補点を通過する経路を探索し、探索経路毎に、探索経路上の稜線のコストを合計し、各探索経路のコスト合計を比較し、コスト合計が最小となる探索経路を求める（Ｓ１６）。そして、照合位置確定部１７により、コスト合計が最小となる探索経路上の照合候補点を照合位置として決定する（Ｓ１８）。したがって、図３に示す例では、実線ＬＬが経路となる。
【００２８】
図５に示す例では、デジタル道路地図１２の道路地図上にプロットされた移動軌跡点（白丸）に対して、図６に示すように、道路上の照合候補点が照合位置として決定されている。また、図７に示す例では、移動軌跡点（白丸）の一部が道路地図上にはない道路（細街路）にプロットされている。この場合、図８に示すように、近傍の代替道路上に照合されることになる。
【００２９】
上述した本実施形態によれば、上述した経路探索アルゴリズムを用いることにより、移動軌跡点の間隔が広い、すなわち位置情報の取得間隔を長い場合でも、経路を照合することができる。また、移動軌跡点の起点に対して照合候補点が複数ある場合でも全体で整合性の高い経路に照合することができ、また、道路地図上位含まれない稜線（道路）を移動する場合でも、近傍を迂回する経路で補完することができる。
【００３０】
なお、上述した実施形態においては、プローブなどの移動体の軌跡について説明したが、これに限らず、対話的なデータベースシステムを用いて、利用者が問合せで経路を同定するために指定する点列に対して経路を求めるようにしてもよい。また、照合先の道路地図としては、道路ネットワーク以外にも、鉄道ネットワーク、歩行者空間ネットワークなどの空間地図情報や、グラフ構造で表現される移動体の軌跡を用いるようにしてもよい。
【００３１】
また、上述した実施形態において、経路決定装置１０の機能は、図示しない記憶部に記憶されたプログラムを実行することで実現するようになっている。記憶部は、ハードディスク装置や光磁気ディスク装置、フラッシュメモリ等の不揮発性メモリやＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）のような揮発性のメモリ、あるいはこれらの組み合わせにより構成されるものとする。また、上記記憶部とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含む。
【００３２】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワークや電話回線等の通信回線のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、上述した処理の一部を実現するためのものであってもよい。さらに、上述した処理を経路決定装置１０に既に記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【００３３】
以上、この発明の実施形態を、図面を参照して詳述してきたが、具体的な構成は、上記実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【００３４】
【発明の効果】
以上説明したように、本発明によれば、座標入力手段から入力されたプローブの軌跡点の座標データに基づいて、軌跡点プロット手段により、前記記憶手段に記憶されている、頂点と稜線とで構成され、グラフ構造を有する地図データ上にプロットし、照合候補点取得手段により、移動軌跡点の各々に対して、近傍を通過する全ての稜線上の近接点を照合候補点として求め、コスト算出手段により、照合候補点が置かれている稜線について、各照合候補点から移動軌跡点までの距離に比例し、当該稜線上の照合候補点の数に反比例するコストを算出し、経路探索手段により、移動軌跡点の各々に対する照合候補点を通過する経路を探索し、コスト合計算出手段により、該探索された経路の各々における稜線のコストを合計し、決定手段により、該コストの合計が最小となる探索経路上の照合候補点を照合位置として決定するようにしたので、移動軌跡点の間隔が広くても、また移動軌跡の始点と終点の位置情報に誤差が含まれていても、より正確に経路を決定することができるという利点が得られる。
【図面の簡単な説明】
【図１】本発明の実施形態による経路決定システムの構成を示すブロック図である。
【図２】本発明の実施形態の動作を説明するためのフローチャートである。
【図３】移動軌跡点の各々について近傍を通過する全ての稜線上の近接点、すなわち照合候補点を求める様子を示す概念図である。
【図４】移動軌跡点のうち起点および終点におけるコストを算出する方法を説明するための概念図である。
【図５】移動軌跡点を道路地図上にプロットした状態を示す概念図である。
【図６】図５に示す移動軌跡点から得られる照合候補点と最終的に得られる経路とを示す概念図である。
【図７】移動軌跡点が道路地図に含まれない細街路にプロットされた場合において移動軌跡点を道路地図上にプロットした状態を示す概念図である。
【図８】図７に示す移動軌跡点から得られる照合候補点と最終的に得られる経路とを示す概念図である。
【符号の説明】
１  プローブ
２  位置情報取得部
３  送信器
１０  経路探索装置
１１  受信器
１２  デジタル道路地図（記憶手段）
１３  位置座標プロット部（軌跡点プロット手段）
１４  照合候補点取得部（照合候補点取得手段）
１５  コスト算出部（コスト算出手段）
１６  経路探索部（経路探索手段、コスト合計算出手段）
１７  照合位置確定部（決定手段）
【図１】
2004325083.tif 000003
【図２】
2004325083.tif 000004
【図３】
2004325083.tif 000005
【図４】
2004325083.tif 000006
【図５】
2004325083.tif 000007
【図６】
2004325083.tif 000008
【図７】
2004325083.tif 000009
【図８】
2004325083.tif 000010