ルート検索装置、方法、及びコンピュータプログラム
【課題】移動軌跡を基にして、道路状況等を反映させたルート検索を行うことができる。
【解決手段】移動体の移動軌跡を示す軌跡データを記憶する軌跡データ記憶部１３と、軌跡データに基づいて、移動軌跡の出発点及び到着点を抽出する抽出手段としての条件抽出部１４と、軌跡データに基づいて、移動軌跡上の一以上の通過地点を抽出する通過地点抽出手段としての条件抽出部と、出発点及び到着点をそれぞれ出発地及び目的地とし、かつ、一以上の通過地点を経由地としたルート検索を行うルート検索部１５と、を備える。
【解決手段】移動体の移動軌跡を示す軌跡データを記憶する軌跡データ記憶部１３と、軌跡データに基づいて、移動軌跡の出発点及び到着点を抽出する抽出手段としての条件抽出部１４と、軌跡データに基づいて、移動軌跡上の一以上の通過地点を抽出する通過地点抽出手段としての条件抽出部と、出発点及び到着点をそれぞれ出発地及び目的地とし、かつ、一以上の通過地点を経由地としたルート検索を行うルート検索部１５と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動体のルート検索を行う装置に関する。
【背景技術】
【０００２】
従来、移動体の移動軌跡を利用したルート表示装置として、例えば非特許文献１が知られている。
【０００３】
非特許文献１のルート表示装置は、例えば、利用者が、よく使うルートを通るとき、他の人に道案内してもらったとき等にその移動軌跡を記録しておくことで、そのルートをもう一度通りたい場合に、記録しておいた移動軌跡をそのままルートとして表示させることが出来る。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】パイオニア株式会社 ＤＶＤナビゲーションマップ Ｔｙｐｅ２ Ｐ４８−５０
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１記載のルート表示のように、移動軌跡をそのままルートとして使用する場合には、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）の測位がずれてしまった位置データも含まれてしまうことがある。この場合、正確な移動軌跡をルートとして使用することが難しくなってしまう。
【０００６】
また、移動軌跡をそのままルートとして使用した場合、交通状況は反映されない。例えば、車両での移動の際には、工事中の道路、渋滞中の道路がルートとして表示されてしまったりする。このため、移動軌跡を再現でき、かつ交通状況を反映させたルートを表示する装置が切望されていた。
【０００７】
本発明の目的は、移動軌跡を基にして、道路状況等を反映させたルート検索を行うことが出来るルート検索装置を提供することにある。
【課題を解決するための手段】
【０００８】
本発明の一つの実施態様に従うルート検索装置は、移動体の移動軌跡を示す軌跡データを記憶する軌跡データ記憶部と、前記軌跡データに基づいて、前記移動軌跡の出発点及び到着点を抽出する手段と、前記移動軌跡の出発点及び到着点を、それぞれ出発地及び目的地とした仮ルート検索を行う仮ルート検索手段と、前記移動軌跡上の通過地点であって、前記仮ルート上にはない一以上の通過地点を抽出する通過地点抽出手段と、前記出発地から前記目的地まで、前記通過地点抽出手段で抽出された通過地点を経由地としてルート検索を行うルート検索手段と、を備えた。
【０００９】
好適な実施態様では、前記通過地点抽出手段が抽出する一以上の通過地点は、前記仮ルートと最も乖離している前記移動軌跡上の通過地点を含むようにしてもよい。
【００１０】
好適な実施態様では、前記通過地点抽出手段が抽出する一以上の通過地点は、前記仮ルート上に複数存在するノードのそれぞれについて、前記各ノードから前記移動軌跡までの最短距離を算出し、前記算出した各ノードからの最短距離のうち、最長距離となるノードに対応する前記移動軌跡上の通過地点を含むようにしてもよい。
【００１１】
好適な実施形態では、前記仮ルート検索手段が、前記通過地点抽出手段で抽出された通過地点を経由地として仮ルート検索を再度行う再仮ルート処理と、前記通過地点抽出手段が、前記再仮ルート検索により抽出された仮ルートと前記移動軌跡との距離に基づいて、前記移動軌跡上の通過地点を再度抽出する再抽出処理とを、所定回数繰り返し、前記ルート検索手段は、前記仮ルート検索手段による再仮ルート検索及び前記通過地点抽出手段による再抽出処理が、前記所定回数繰り返されて抽出された通過地点を経由地としてルート検索を行うようにしてもよい。
【００１２】
好適な実施形態では、前記仮ルート検索手段による再仮ルート処理と、前記通過地点抽出手段による再抽出処理とを所定回数繰り返した後、前記通過地点抽出手段により抽出された複数の通過地点と、出発地及び目的地とを折れ線で結び、前記移動軌跡の近似を行う折れ線近似手段を、さらに有し、前記通過地点抽出手段は、前記折れ線近似手段で得られた折れ線と前記移動経路との交点を前記通過地点として抽出し、前記ルート検索手段は、前記複数の通過地点を経由地としてルート検索を行うようにしてもよい。
【図面の簡単な説明】
【００１３】
【図１】本発明の第１実施形態にかかるルート検索装置の機能ブロック図である。
【図２】図１の軌跡データ生成部が行うフィルタリング処理の概要説明するための図である。
【図３】図１の軌跡データ記憶部に記憶されたデータ構造の一例を示す図である。
【図４】図１の端末装置に表示されたルート検索の条件設定画面を示す図である。
【図５】第１実施形態における、通過地点の抽出及びルート検索を説明するための図である。
【図６】第２実施形態における、折れ線近似の方法を説明するための図である。
【図７】仮ルートから最も乖離した移動軌跡上の通過地点を抽出する方法を示すフローチャートである
【図８】第３実施形態における、通過地点の抽出を説明するための図である。
【図９】第３実施形態に係るルート検索装置の動作を表すフローチャートである
【図１０】第３実施形態における、通過地点の抽出を説明するための図である。
【図１１】第３実施形態における、通過地点の抽出を説明するための図である。
【発明を実施するための形態】
【００１４】
＜第１実施形態＞
以下、本発明の第１実施形態に係るルート検索装置を一例に挙げ、図面を参照して詳細に説明する。
【００１５】
図１は、端末装置３に接続されたルート検索装置１の機能ブロック図である。
【００１６】
図示例では、端末装置３は、ネットワークを２介してルート検索装置１に接続されているが、端末装置３の内部にルート検索装置１を設けてもよい。
【００１７】
端末装置３は、図示例のように、携帯電話等の移動通信機器を用いてもよいし、自動車などの車両４に固定的に搭載される車載用の端末、車両４に着脱自在に搭載される端末等、様々な種類の端末装置を用いてもよい。
【００１８】
端末装置３は、図示しないＧＰＳ受信機を備える。ＧＰＳ受信機は、複数のＧＰＳ衛星５から日時データを含む電波を受信し、端末装置３の現在位置を測位する。端末装置３は、自身の端末装置３を特定するための端末ＩＤと、測位データとを、ネットワーク２を介してルート検索装置１に送信する。なおここでいう、測位データには、ＧＰＳ受信機により、所定距離間隔（例えば１０ｍ毎）、又は、所定時間間隔（例えば1秒毎）に測位された端末装置３の位置を示す測位点（緯度及び経度）及び測位された日時が含まれる。
【００１９】
端末装置３は、ルート検索装置１から受信した後述するルートデータ及び地図データに基づいて、検索したルートをディスプレイ上に表示する。
【００２０】
ルート検索装置１は、出発地から目的地までのルートを現在の交通情報を加味して検索し、検索したルートを端末装置３に送信するルート検索機能を備えた装置である。ルート検索機能は、ルート検索装置１内部の図示しないプロセッサ及びメモリを用いて所定のプログラムを実行することにより実現される。なお、ルート検索装置１は、ナビゲーション機能を併せて備えてもよい。
【００２１】
ルート検索装置１は、入出力部１１と、軌跡データ生成部１２と、軌跡データ記憶部１３と、条件抽出部１４と、ルート検索部１５と、ルート記憶部１６と、地図情報記憶部１７とを主に備える。
【００２２】
入出力部１１は、端末装置３との間でデータの送受信を行う。入出力部１１は、例えば、端末装置３から端末ＩＤ及び測位データを受信し、受信した端末ＩＤ及び測位データを軌跡データ生成部１２へ送信する。また例えば、入出力部１１は、後述するルートデータ及び地図データを端末装置３へ送信する。
【００２３】
軌跡データ生成部１２は、端末装置３が送信した端末ＩＤ及び測位データを、入出力部１１を介して受信し、これら端末ＩＤ及び測位データから軌跡データ生成し、軌跡データ記憶部１３に記憶する。軌跡データは、例えば、測位データの異常値を取り除くフィルタリング処理、一連の連続する測位点を移動軌跡Ｔとしてグループ化する処理等によって生成される。以下に、軌跡データ生成のための各処理を詳細に説明する。
【００２４】
まず、フィルタリング処理について説明する。
【００２５】
図２は、軌跡データ生成部１２が行う、フィルタリング処理の概要を説明するための図である。
【００２６】
軌跡データ生成部１２は、入出力部１１から測位データを受け取ると、順次フィルタリング処理を行う。フィルタリング処理は、複数の測位点の中から、異常値を示す測位点（以下、異常点という）を取り除く処理である。なお、本実施形態では、フィルタリング処理は、軌跡データを生成するための一過程として行っているが、フィルタリング処理を行うタイミングは、これだけには限られない。例えば、フィルタリング処理は、軌跡データを生成する際に行われた後、さらに、後述するルート検索の際にも行われるようにしてもよいし、ルート検索の際にのみ行われるようにしてもよい。
【００２７】
図２（ａ）は、フィルタリング処理によって、異常点が検出される過程を説明するための図である。
【００２８】
軌跡データ生成部１２は、例えば、連続する測位点について、これら測位点間の距離に基づき異常点を検出し、取り除く。例えば、Ｄ１、Ｄ２、Ｄ３の順に測位された測位点について、まず軌跡データ生成部１２は、測位点Ｄ１、Ｄ２間の距離を算出する。このとき、例えば、２つの測位点Ｄ１、Ｄ２間が所定距離内である場合には、Ｄ２は正常な測位点として扱われる。一方、図２（ａ）のように、測位点Ｄ１、Ｄ２間の距離が所定（図示例では３００ｍ）以上離れている場合には、軌跡データ生成部１２は、続いて測位点Ｄ１、Ｄ３間の距離を算出する。ここでは、測位点Ｄ１、Ｄ３間の距離は３００ｍ以上離れていない。このため、軌跡データ生成部１２は、測位点Ｄ１、Ｄ３が連続し、測位点Ｄ２は異常値を示すものと判断し、Ｄ２のみを異常点として検出し、取り除く。
【００２９】
図２（ｂ）は、フィルタリング処理による、他の例を説明するための図である。
【００３０】
図２（ｂ）では、測位点は、Ｄ４、Ｄ５、Ｄ６の順に測位されたものとする。図示例では、Ｄ４、Ｄ５間の距離が３００ｍ離れているが、Ｄ４、Ｄ６間も距離が３００ｍ以上離れている。この場合には、例えば、端末装置３を乗せた車両４がトンネル内を走行しているなど、何らかの事情で３００ｍ以上測位データが受信されなかったものと判断し、フィルタリング処理部はＤ４を異常点と扱わず正常な測位点とする。
【００３１】
次に、移動軌跡Ｔを形成するための処理を説明する。本明細書中では、移動軌跡Ｔは、所定ルールに基づいてグループ化された、連続する複数の測位点のことをいう。この場合の所定ルールは、どのように設定してもよい。例えば、連続する２つの測位点間の距離又は時間が、それぞれ所定範囲以内である複数の測位点をグループ化するというルールにしてもよい。また、移動軌跡Ｔを構成する複数の測位点のうち、最も早い日時の点を出発点とし、最も遅い日時の点を到着点としてもよい。
【００３２】
軌跡データ生成部１２は、フィルタリング処理を行った後の測位データを用いて、所定ルールに基づいてグループ化し、移動軌跡Ｔとして同じ軌跡ＩＤを付与する。例えば、軌跡データ生成部１２は、連続する２つの測位点が、所定以上時間間隔が空いた場合には、後の測位点から次の移動軌跡Ｔとして扱ってもよい。また例えば、軌跡データ生成部１２は、連続する測位点のうち、前後２つの測位点について、所定以上距離の差が開いた場合には、後の測位点から次の移動軌跡Ｔとして扱ってもよい。なお、上記のように、移動軌跡Ｔを形成することで、１つの移動軌跡Ｔに所定数以下しか測位点が存在しなくなった場合には、これらの測位点を移動軌跡Ｔと扱わなくてもよい。
【００３３】
軌跡データ生成部１２は、フィルタリング処理によって異常点を取り除いた後の測位データに、端末ＩＤ及び軌跡ＩＤを対応づけて軌跡データ記憶部１３に記憶する。
【００３４】
軌跡データ記憶部は１３、端末装置３の移動軌跡Ｔを示す軌跡データが格納される記憶部である。
【００３５】
図３は、軌跡データ記憶部１３内に記憶されたデータ構造の一例としての、端末装置３毎の軌跡データテーブル２０である。
【００３６】
端末装置３毎（各端末ＩＤ２１）の軌跡データテーブル２０には、例えば、軌跡ＩＤ２２、位置２３、日時２４、及びフラグ２５が記憶される。
【００３７】
軌跡ＩＤ２２は、移動軌跡Ｔを識別するためのＩＤである。位置２３は、測位点の緯度（Ｘｎ）及び経度（Ｙｎ）である。日時２４は、位置２３が測位された日時を示す。フラグ２５には、軌跡ＩＤ２２の中で最も早い日時のものが出発点、最も遅い日時のものが到着点として記録される。
【００３８】
条件抽出部１４は、軌跡データ記憶部１３から移動軌跡Ｔの出発点及び到着点を抽出する。例えば、条件抽出部１４は、軌跡データ記憶部１３から所望の軌跡ＩＤ２２を有する軌跡データをすべて読み出す。そして、読みだした軌跡データの中から、フラグ２５が出発点及び到着点であるデータを抽出する。
【００３９】
また、条件抽出部１４は、読みだした軌跡データの中から、移動軌跡Ｔ上の一以上の通過地点を抽出する。通過地点の抽出には様々な方法があるが、例えば、以下のようにしてもよい。
【００４０】
すなわち、移動軌跡Ｔを所定条件に基づいて複数に分割したときの分割点を通過地点として抽出してもよい。この場合、例えば通過地点は、移動軌跡Ｔを、およそ同じ長さ（距離）を有する複数の区間に分割した分割点としてもよいし、日時データ２４に基づいて時間的に略等間隔な複数の区間に分割した分割点としてもよい。例えば、分割点は、軌跡データから、略均等な距離又は時間間隔を有する複数の位置２３としてもよい。なお、通過地点の数は、予め設定しておいてもよい。これは例えば、利用者が手動で設定してもよいし、デフォルトで設定されていてもよい。
【００４１】
条件抽出部１４は、抽出した出発点、到着点、及び通過地点をルート検索部１５に通知する。
【００４２】
ルート検索部は１５、条件抽出部１４からの通知を受けると、出発点及び到着点をそれぞれ出発地及び目的地とし、かつ、一以上の通過地点を経由地としたルート検索を行う。
【００４３】
ルート検索部１５は、また、ルート検索の際には現在の交通情報を加味して最適なルートを検索するようにしてもよい。
【００４４】
ルート検索部１５は、検索したルートのルートデータをルート記憶部１６に格納する。ルート検索部１５は、検索したルートのルートデータを、地図情報記憶部１７から抽出した周辺の地図データとともに入出力部１１を介して、端末装置３に送信する。
【００４５】
次に、第１実施形態におけるルート検索装置１の動作を説明する。
【００４６】
図４は、端末装置３のディスプレイに表示されたルート検索の条件設定画面３１を示す図である。図５（ａ）は、第１実施形態における、通過地点の抽出を説明するための図である。図５（ｂ）は第１実施形態における、ルート検索を説明するための図である。
【００４７】
利用者は、図４に示す条件設定画面３１から、ルート検索のための設定条件を選択する。設定条件は、例えば、有料道路の利用の有無等の選択３２と、どの移動軌跡Ｔを利用するかの選択３３である。例えば、利用者は、このような設定条件の選択によって、有料道路等、自分の通りたい道を選択することができ、また、以前通ったことのある移動軌跡に基づいたルート検索を行うことができる。以下には、いずれかの移動軌跡Ｔを選択した場合のルート検索について説明する。
【００４８】
端末装置３は、条件設定画面３１で選択された設定条件をルート検索装置１に送信する。
【００４９】
設定条件を受信したルート検索装置１の条件抽出部１４は、設定条件に基づいて、軌跡データ記憶部１３から所望の移動軌跡Ｔの軌跡データを読み出し、その中から出発点、到着点及び通過地点を抽出する。
【００５０】
図５（ａ）では、出発点Ｓから到着点Ｇまでの移動軌跡Ｔを、同じ長さ（距離）を有する複数の区間に分割した４つの通過地点ｐ１０〜ｐ１３が抽出されている。条件抽出部１４は、抽出された出発点Ｓ、到着点Ｇ及び通過地点ｐ１０〜ｐ１３をルート検索部１５に通知する。
【００５１】
ルート検索部１５は、通知された出発点Ｓ、到着点Ｇ及び通過地点ｐ１０〜ｐ１３に基づいてルート検索を行う。図５（ｂ）は、出発点Ｓを出発地、到着点Ｇを目的地とし、４つの通過地点ｐ１０〜ｐ１３を経由地としてルート検索を行った結果である。点線で示されたルートが検索されたルートである。この場合、前述したように、利用者が端末装置３を介して有料道路の使用の有無等の条件を設定していれば、ルート検索部１５は、その条件を反映させたルート検索を行うこととなる。
【００５２】
本発明に係る第１実施形態によれば、移動軌跡Ｔ上の通過地点を経由地に設定することで、以前通った道に基づいて、道路状況などを反映させたルート検索を行うことができる。
＜第２実施形態＞
【００５３】
次に、第２実施形態について説明する。
【００５４】
上述の第１実施形態では、条件抽出部１４は、移動軌跡Ｔを所定条件に基づいて複数に分割したときの分割点を通過地点として抽出していたが、これに限定されない。
【００５５】
例えば、第２実施形態では、条件抽出部１４は、移動軌跡Ｔを、折れ線近似によって得られた折れ線と、移動軌跡Ｔとの交点を移動軌跡Ｔ上の一以上の通過地点として抽出する機能をさらに有するようにしてもよい。また例えば、この折れ線近似は、出発地と目的地とを結ぶ仮想直線からの距離が極大となる移動軌跡Ｔとの交点を、通過地点として抽出するようにしてもよい。
【００５６】
上記した、出発地と目的地とを結ぶ仮想直線からの距離が極大となる移動軌跡Ｔとの交点を、通過地点として抽出する折れ線近似の方法について、図６を参照して以下に詳細に説明する。しかしながら、折れ線近似の方法は、以下に説明するものに限定されるものではない。
【００５７】
図６（ａ）は、第１の通過地点を決定する方法を説明する図である。
【００５８】
条件抽出部１４は、まず、出発点Ｓと到着点Ｇの間を、直線Ｉ１で結ぶ。
【００５９】
次に、条件抽出部１４は、直線Ｉ１と移動軌跡Ｔとを、所定間隔ごとに、直線Ｉ１に直交する直線Ｉ２で結ぶ。なお、図示例のＩ２の間隔は、説明のために設定したものであり、これに限られない。
【００６０】
条件抽出部１４は、直線Ｉ１から移動軌跡Ｔまでにおいて、長さが最も長い直線Ｉ２と、移動軌跡Ｔとの交点を第１の通過地点Ｐ２１に設定する。
【００６１】
図６（ｂ）は、第２及び第３の通過地点を決定する方法を説明する図である。
【００６２】
条件抽出部１４は、移動軌跡Ｔ上に位置する、出発点Ｓ、到着点Ｇ及び第１の通過地点ｐ２１を折れ線で結び、移動軌跡の近似を行う。換言すると、条件抽出部１４は、出発点Ｓと第１の通過地点Ｐ２１、第１の通過地点ｐ２１と到着点Ｇとの間を、それぞれ直線Ｉ１１、Ｉ１２で結ぶ。
【００６３】
次に条件抽出部１４は、直線Ｉ１１及びＩ１２と移動軌跡Ｔとを、所定間隔ごとに直線Ｉ１１及びＩ１２に直交する直線Ｉ２で結ぶ（図示なし）。
【００６４】
そして、直線Ｉ１１に直交する最も長い直線Ｉ２と、移動軌跡Ｔとの交点をｐ２２とし、直線Ｉ１２に直交する最も長い直線Ｉ２と、移動軌跡Ｔの交点をｐ２３とする。
【００６５】
図６（ｃ）は、第２及び第３の通過地点を折れ線で結んで近似する方法を説明する図である。
【００６６】
条件抽出部１４は、移動軌跡Ｔ上に位置する、出発点Ｓ、到着点Ｇ、第１の通過地点ｐ２１、第２の通過地点ｐ２２、第３の通過地点ｐ２３を折れ線で結び、再度、移動軌跡の近似を行う。換言すると、条件抽出部１４は、出発地と第２の通過地点Ｐ２２、第２の通過地点ｐ２２と第１の通過地点ｐ２１、第１の通過地点ｐ２１と第３の通過地点ｐ２３、第３の通過地点ｐ２３と到着地との間を、それぞれ直線Ｉ１３、Ｉ１４、Ｉ１５、Ｉ１６で結ぶ。
【００６７】
ルート検索の際には、条件抽出部１４は、移動軌跡Ｔの出発点Ｓ、到着点Ｇとともに、上記のように抽出した通過地点ｐ２１〜２３をルート検索部１５に通知する。そして、ルート検索部１５は、通知された出発点Ｓを出発地、到着点Ｇを目的地、通過地点ｐ２１〜２３を経由地としてルート検索を行う。
【００６８】
本発明に係る第２実施形態によれば、移動軌跡Ｔ上の通過地点を経由地に設定することで、以前通った軌跡に基づき、かつ道路状況などを反映させたルート検索を行うことができる。また、第１実施形態のように経由地を移動軌跡Ｔ上に略均等に設定した場合に比べて、移動軌跡Ｔにより近似したルート検索を行うことができる。
＜第３実施形態＞
【００６９】
次に、第３実施形態について説明する。
【００７０】
条件抽出部１４及びルート検索部１５の機能は、上述した第１実施形態及び第２実施形態に例示した機能には限定されない。以下の第３実施形態に示す機能をさらに有してもよい。
【００７１】
第３実施形態では、条件抽出部１４は、移動軌跡Ｔの出発点Ｓ及び到着点Ｇを、それぞれ出発地及び目的地とした仮ルート検索をルート検索部１５に行わせ、移動軌跡Ｔ上の通過地点であって、仮ルート上にはない一以上の通過地点を抽出してもよい。
【００７２】
この場合、例えば、条件抽出部１４は、仮ルート検索をルート検索部１５に依頼するとともに、抽出した出発点Ｓ及び到着点Ｇの軌跡データをルート検索部１５に通知する。また、条件抽出部１４は、ルート検索部１５から仮ルート検索により生成されたルートデータを受信し、ルートデータに基づいて、通過地点の軌跡データを抽出する。詳細は後述する。
【００７３】
またこの場合、ルート検索部１５は、条件抽出部１４から通知された出発点Ｓ及び到着点Ｇの軌跡データをそれぞれ出発地及び目的地として、仮ルート検索を行う。ルート検索部１５は、また、仮ルート検索により生成されたルートデータを条件抽出部１４に送信する。
【００７４】
第３実施形態では、条件抽出部１４が抽出する一以上の通過地点は、仮ルートと最も乖離している移動軌跡Ｔ上の通過地点を含んでもよい。例えば、条件抽出部１４が抽出する一以上の通過地点は、仮ルート上に複数存在するノードのそれぞれについて、各ノードから移動軌跡Ｔまでの最短距離を算出し、算出した各ノードからの最短距離のうち最長距離となるノードに対応する移動軌跡Ｔ上の地点としてもよい。通過地点を抽出する方法の具体例を以下に説明する。
【００７５】
図７は、仮ルートから最も乖離した移動軌跡上の通過地点を抽出する方法を示すフローチャートである。図８は、移動軌跡Ｔ及び仮ルートＩＲから通過地点を抽出する方法を説明するため図である。
【００７６】
まず、条件抽出部１４は軌跡データ記憶部１３から軌跡データを読み出し、測位点（位置２３）を抽出する（ステップＳ１００）。
【００７７】
次に条件抽出部１４は、ルート検索部１５から受け取った仮ルートのルートデータから、各リンクをつなぐノードを抽出する（ステップＳ１０１）。
【００７８】
次に、条件抽出部１４は、ステップＳ１００で抽出した各測位点（位置２３）及びステップＳ１１１で抽出した各ノードに基づいて、各ノードから最も近い測位点（位置２３）をそれぞれ検索する（ステップＳ１０２）。
【００７９】
図８（ａ）は移動軌跡Ｔと仮ルートＩＲの拡大図である。説明のため、移動軌跡Ｔ上の測位点（位置２３）をＤ１１〜Ｄ１６で示し、仮ルートＩＲ上のノードをＮ１〜Ｎ３とした。図８（ａ）を参照して、ある１つのノードＮ１について最も近い測位点（位置２３）を検索する様子を説明する。例えば、条件抽出部１４は、ノードＮ１と移動軌跡Ｔ上のすべての測位点（位置２３）との距離を算出し、最も近い距離を選択する。図示例の場合、移動軌跡上Ｔ上のすべての測位点（位置２３）のうちどれが一番近いかを、例えばＤ１１、Ｄ１２、Ｄ１３、Ｄ１４、Ｄ１５、Ｄ１６というように順次検索する。ノードＮ１といちばん近い測位点はＤ１１であるので、これらを直線で結ぶ。
【００８０】
上記処理を、条件抽出部１４は、仮ルート上の複数のノードについて行う。図８（ｂ）では、Ｎ１とＤ１１、Ｎ２とＤ１４、Ｎ３とＤ１６とが、それぞれ直線で結ばれている。
【００８１】
条件抽出部１４は、ステップ１０２の結果から、各ノード及び各測位点（位置２３）を結ぶ直線の距離が一番長いものを抽出する（ステップＳ１０３）。
【００８２】
図示例ではＮ２とＤ１４を結ぶ直線の距離が一番長い。このため、この直線と移動軌跡Ｔとの交点であるＤ１４が通過地点（例えばＰ３０）として抽出される。
【００８３】
また、第３実施形態では、ルート検索部１５が、条件抽出部１４で抽出された通過地点を経由地として仮ルート検索を再度行う再仮ルート処理と、条件抽出部１４が、再仮ルート検索により抽出された仮ルート上にはない、移動軌跡Ｔ上の通過地点を再度抽出する再抽出処理とを、所定回数繰り返し、ルート検索部１５は、再仮ルート処理及び再抽出処理が、所定回数繰り返されて抽出された通過地点を経由地としてルート検索を行ってもよい。例えば、再仮ルート処理及び再抽出処理の繰り返し回数は、経由地をいくつ設けるかによって設定するようにしてもよい。利用者が手動で設定してもよいし、デフォルトで設定されていてもよい。
【００８４】
次に、第３実施形態に係るルート検索装置１の動作を図９〜１１を用いて以下に説明する。
【００８５】
図９は、第３実施形態に係るルート検索装置１の動作を表すフローチャートである。図１０は、第３実施形態における、通過地点の抽出方法を説明するための図である。図１１は、第３実施形態における、通過地点の抽出方法を説明するための図である。
【００８６】
端末装置３は、利用者がルート検索の条件設定画面３１から入力した設定条件を(図４参照)送信し、ルート検索装置１の条件抽出部１４は、この設定条件を受信する（ステップＳ１１０）。
【００８７】
Ｓ１１０で設定条件を受信した条件抽出部１４は、その設定条件に基づいて、軌跡データ記憶部１３から軌跡データを読み出し、この中から出発点Ｓ及び到着点Ｇを抽出する（ステップＳ１１１）。
【００８８】
そして、条件抽出部１４は、抽出した出発点Ｓ及び到着点Ｇをルート検索部１５に通知し、仮ルート検索を依頼する。
【００８９】
ルート検索部１５は、条件抽出部１４から通知された出発点Ｓを出発地、到着点Ｇを目的地として仮ルート検索を行う（ステップＳ１１２）。
【００９０】
図１０（ａ）は、ルート検索部１５による１回目の仮ルート検索の結果である。出発地から目的地までの移動軌跡Ｔを実線で示し、検索された仮ルートＩＲを二点鎖線で示す。ルート検索部１５は、検索した仮ルートのルートデータを条件抽出部１４に通知する。
【００９１】
条件抽出部１４は、ルート検索部１５から通知された仮ルートのルートデータ及びステップＳ１１１で軌跡データ記憶部１３から読み出した軌跡データに基づいて、通過地点を抽出する（ステップＳ１１３）。
【００９２】
図１０（ｂ）は、ステップＳ１１３によって、第１の通過地点ｐ４０が抽出された様子を示す。ここでは、上述したように、仮ルートから最も乖離した移動軌跡Ｔ上の点を第１の通過地点ｐ４０とした。
【００９３】
条件抽出部１４は、抽出した通過地点が所定数に達したか否かを判定する（ステップＳ１１４）。なお、前述したとおり、通過地点の数は予め設定しておいてもよい。
【００９４】
通過地点が所定数に達していない場合には（ステップＳ１１４：Ｎｏ）、ステップＳ１１２及びステップＳ１１３を再度行う。
【００９５】
この場合、条件抽出部１４は、移動軌跡Ｔの出発点Ｓ、到着点Ｇ、及び、ステップＳ１１３によって抽出されたすべての通過地点をルート検索部１５に通知する。通知を受けたルート検索部１５は、出発点Ｓを出発地、到着点Ｇを目的地、通過地点を経由地として、再度仮ルート検索が行う（ステップＳ１１２）。
【００９６】
図１１（ａ）は、ルート検索部１５による２回目の仮ルート検索及び第２の通過地点抽出の結果である。検索された仮ルートＩＲは第１の通過地点ｐ４０を経由地としている。また、検索された仮ルートから最も乖離した移動軌跡上の点を第２の通過地点ｐ５０としている。
【００９７】
図１１（ｂ）は、ルート検索部１５による３回目の仮ルート検索及び第３の通過地点抽出の結果である。検索された仮ルートＩＲは第１の通過地点ｐ４０、第２の通過地点ｐ５０を経由地としている。また、検索された仮ルートから最も乖離した移動軌跡Ｔ上の点を第３の通過地点ｐ６０としている。
【００９８】
通過地点が所定数に達した場合には（ステップＳ１１４：Ｙｅｓ）、条件抽出部１４は、移動軌跡Ｔの出発点Ｓ、到着点Ｇ及び抽出したすべての通過地点をルート検索部１５に通知する。そして、ルート検索部１５は、通知された出発点Ｓを出発地、到着点Ｇを目的地、通過地点を経由地としてルート検索を行う（ステップＳ１１５）。
【００９９】
本発明に係る第３実施形態によれば、移動軌跡Ｔ上の通過地点を経由地に設定することで、以前通った道に基づいて、道路状況などを反映させたルート検索を行うことができる。また、第１実施形態のように経由地を移動軌跡Ｔ上に略均等に設定した場合に比べて、移動軌跡Ｔにより近いルート検索を行うことができる。また、本実施形態では、経由地の設定に仮ルートを使用するため、経由地の選択においても、有料道路等の各種道路状況、道路状況などを考慮することができる。
【０１００】
上述した実施形態１〜３に示す条件抽出部１４の機能を組み合わせてもよい。例えば、第３実施形態に示すように、仮ルートを利用して通過地点を所定数抽出した後、抽出した通過地点を折れ線で結び、以降、第２実施形態に示した折れ線近似によって、移動軌跡上の通過地点をさらに抽出してもよい。
【０１０１】
上述した本発明の実施形態は、本発明の説明のための例示であり、本発明の範囲をそれらの実施形態にのみ限定する趣旨ではない。当業者は、本発明の要旨を逸脱することなしに、他の様々な態様で本発明を実施することができる。
【符号の説明】
【０１０２】
１ ルート検索装置
２ ネットワーク
３ 端末装置
１１ 入出力部
１２ 軌跡データ生成部
１３ 軌跡データ記憶部
１４ 条件抽出部
１５ ルート検索部
１６ ルート記憶部
１７ 地図情報記憶部
ＩＲ 仮ルート
Ｔ 移動軌跡
【技術分野】
【０００１】
本発明は、移動体のルート検索を行う装置に関する。
【背景技術】
【０００２】
従来、移動体の移動軌跡を利用したルート表示装置として、例えば非特許文献１が知られている。
【０００３】
非特許文献１のルート表示装置は、例えば、利用者が、よく使うルートを通るとき、他の人に道案内してもらったとき等にその移動軌跡を記録しておくことで、そのルートをもう一度通りたい場合に、記録しておいた移動軌跡をそのままルートとして表示させることが出来る。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】パイオニア株式会社 ＤＶＤナビゲーションマップ Ｔｙｐｅ２ Ｐ４８−５０
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１記載のルート表示のように、移動軌跡をそのままルートとして使用する場合には、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）の測位がずれてしまった位置データも含まれてしまうことがある。この場合、正確な移動軌跡をルートとして使用することが難しくなってしまう。
【０００６】
また、移動軌跡をそのままルートとして使用した場合、交通状況は反映されない。例えば、車両での移動の際には、工事中の道路、渋滞中の道路がルートとして表示されてしまったりする。このため、移動軌跡を再現でき、かつ交通状況を反映させたルートを表示する装置が切望されていた。
【０００７】
本発明の目的は、移動軌跡を基にして、道路状況等を反映させたルート検索を行うことが出来るルート検索装置を提供することにある。
【課題を解決するための手段】
【０００８】
本発明の一つの実施態様に従うルート検索装置は、移動体の移動軌跡を示す軌跡データを記憶する軌跡データ記憶部と、前記軌跡データに基づいて、前記移動軌跡の出発点及び到着点を抽出する手段と、前記移動軌跡の出発点及び到着点を、それぞれ出発地及び目的地とした仮ルート検索を行う仮ルート検索手段と、前記移動軌跡上の通過地点であって、前記仮ルート上にはない一以上の通過地点を抽出する通過地点抽出手段と、前記出発地から前記目的地まで、前記通過地点抽出手段で抽出された通過地点を経由地としてルート検索を行うルート検索手段と、を備えた。
【０００９】
好適な実施態様では、前記通過地点抽出手段が抽出する一以上の通過地点は、前記仮ルートと最も乖離している前記移動軌跡上の通過地点を含むようにしてもよい。
【００１０】
好適な実施態様では、前記通過地点抽出手段が抽出する一以上の通過地点は、前記仮ルート上に複数存在するノードのそれぞれについて、前記各ノードから前記移動軌跡までの最短距離を算出し、前記算出した各ノードからの最短距離のうち、最長距離となるノードに対応する前記移動軌跡上の通過地点を含むようにしてもよい。
【００１１】
好適な実施形態では、前記仮ルート検索手段が、前記通過地点抽出手段で抽出された通過地点を経由地として仮ルート検索を再度行う再仮ルート処理と、前記通過地点抽出手段が、前記再仮ルート検索により抽出された仮ルートと前記移動軌跡との距離に基づいて、前記移動軌跡上の通過地点を再度抽出する再抽出処理とを、所定回数繰り返し、前記ルート検索手段は、前記仮ルート検索手段による再仮ルート検索及び前記通過地点抽出手段による再抽出処理が、前記所定回数繰り返されて抽出された通過地点を経由地としてルート検索を行うようにしてもよい。
【００１２】
好適な実施形態では、前記仮ルート検索手段による再仮ルート処理と、前記通過地点抽出手段による再抽出処理とを所定回数繰り返した後、前記通過地点抽出手段により抽出された複数の通過地点と、出発地及び目的地とを折れ線で結び、前記移動軌跡の近似を行う折れ線近似手段を、さらに有し、前記通過地点抽出手段は、前記折れ線近似手段で得られた折れ線と前記移動経路との交点を前記通過地点として抽出し、前記ルート検索手段は、前記複数の通過地点を経由地としてルート検索を行うようにしてもよい。
【図面の簡単な説明】
【００１３】
【図１】本発明の第１実施形態にかかるルート検索装置の機能ブロック図である。
【図２】図１の軌跡データ生成部が行うフィルタリング処理の概要説明するための図である。
【図３】図１の軌跡データ記憶部に記憶されたデータ構造の一例を示す図である。
【図４】図１の端末装置に表示されたルート検索の条件設定画面を示す図である。
【図５】第１実施形態における、通過地点の抽出及びルート検索を説明するための図である。
【図６】第２実施形態における、折れ線近似の方法を説明するための図である。
【図７】仮ルートから最も乖離した移動軌跡上の通過地点を抽出する方法を示すフローチャートである
【図８】第３実施形態における、通過地点の抽出を説明するための図である。
【図９】第３実施形態に係るルート検索装置の動作を表すフローチャートである
【図１０】第３実施形態における、通過地点の抽出を説明するための図である。
【図１１】第３実施形態における、通過地点の抽出を説明するための図である。
【発明を実施するための形態】
【００１４】
＜第１実施形態＞
以下、本発明の第１実施形態に係るルート検索装置を一例に挙げ、図面を参照して詳細に説明する。
【００１５】
図１は、端末装置３に接続されたルート検索装置１の機能ブロック図である。
【００１６】
図示例では、端末装置３は、ネットワークを２介してルート検索装置１に接続されているが、端末装置３の内部にルート検索装置１を設けてもよい。
【００１７】
端末装置３は、図示例のように、携帯電話等の移動通信機器を用いてもよいし、自動車などの車両４に固定的に搭載される車載用の端末、車両４に着脱自在に搭載される端末等、様々な種類の端末装置を用いてもよい。
【００１８】
端末装置３は、図示しないＧＰＳ受信機を備える。ＧＰＳ受信機は、複数のＧＰＳ衛星５から日時データを含む電波を受信し、端末装置３の現在位置を測位する。端末装置３は、自身の端末装置３を特定するための端末ＩＤと、測位データとを、ネットワーク２を介してルート検索装置１に送信する。なおここでいう、測位データには、ＧＰＳ受信機により、所定距離間隔（例えば１０ｍ毎）、又は、所定時間間隔（例えば1秒毎）に測位された端末装置３の位置を示す測位点（緯度及び経度）及び測位された日時が含まれる。
【００１９】
端末装置３は、ルート検索装置１から受信した後述するルートデータ及び地図データに基づいて、検索したルートをディスプレイ上に表示する。
【００２０】
ルート検索装置１は、出発地から目的地までのルートを現在の交通情報を加味して検索し、検索したルートを端末装置３に送信するルート検索機能を備えた装置である。ルート検索機能は、ルート検索装置１内部の図示しないプロセッサ及びメモリを用いて所定のプログラムを実行することにより実現される。なお、ルート検索装置１は、ナビゲーション機能を併せて備えてもよい。
【００２１】
ルート検索装置１は、入出力部１１と、軌跡データ生成部１２と、軌跡データ記憶部１３と、条件抽出部１４と、ルート検索部１５と、ルート記憶部１６と、地図情報記憶部１７とを主に備える。
【００２２】
入出力部１１は、端末装置３との間でデータの送受信を行う。入出力部１１は、例えば、端末装置３から端末ＩＤ及び測位データを受信し、受信した端末ＩＤ及び測位データを軌跡データ生成部１２へ送信する。また例えば、入出力部１１は、後述するルートデータ及び地図データを端末装置３へ送信する。
【００２３】
軌跡データ生成部１２は、端末装置３が送信した端末ＩＤ及び測位データを、入出力部１１を介して受信し、これら端末ＩＤ及び測位データから軌跡データ生成し、軌跡データ記憶部１３に記憶する。軌跡データは、例えば、測位データの異常値を取り除くフィルタリング処理、一連の連続する測位点を移動軌跡Ｔとしてグループ化する処理等によって生成される。以下に、軌跡データ生成のための各処理を詳細に説明する。
【００２４】
まず、フィルタリング処理について説明する。
【００２５】
図２は、軌跡データ生成部１２が行う、フィルタリング処理の概要を説明するための図である。
【００２６】
軌跡データ生成部１２は、入出力部１１から測位データを受け取ると、順次フィルタリング処理を行う。フィルタリング処理は、複数の測位点の中から、異常値を示す測位点（以下、異常点という）を取り除く処理である。なお、本実施形態では、フィルタリング処理は、軌跡データを生成するための一過程として行っているが、フィルタリング処理を行うタイミングは、これだけには限られない。例えば、フィルタリング処理は、軌跡データを生成する際に行われた後、さらに、後述するルート検索の際にも行われるようにしてもよいし、ルート検索の際にのみ行われるようにしてもよい。
【００２７】
図２（ａ）は、フィルタリング処理によって、異常点が検出される過程を説明するための図である。
【００２８】
軌跡データ生成部１２は、例えば、連続する測位点について、これら測位点間の距離に基づき異常点を検出し、取り除く。例えば、Ｄ１、Ｄ２、Ｄ３の順に測位された測位点について、まず軌跡データ生成部１２は、測位点Ｄ１、Ｄ２間の距離を算出する。このとき、例えば、２つの測位点Ｄ１、Ｄ２間が所定距離内である場合には、Ｄ２は正常な測位点として扱われる。一方、図２（ａ）のように、測位点Ｄ１、Ｄ２間の距離が所定（図示例では３００ｍ）以上離れている場合には、軌跡データ生成部１２は、続いて測位点Ｄ１、Ｄ３間の距離を算出する。ここでは、測位点Ｄ１、Ｄ３間の距離は３００ｍ以上離れていない。このため、軌跡データ生成部１２は、測位点Ｄ１、Ｄ３が連続し、測位点Ｄ２は異常値を示すものと判断し、Ｄ２のみを異常点として検出し、取り除く。
【００２９】
図２（ｂ）は、フィルタリング処理による、他の例を説明するための図である。
【００３０】
図２（ｂ）では、測位点は、Ｄ４、Ｄ５、Ｄ６の順に測位されたものとする。図示例では、Ｄ４、Ｄ５間の距離が３００ｍ離れているが、Ｄ４、Ｄ６間も距離が３００ｍ以上離れている。この場合には、例えば、端末装置３を乗せた車両４がトンネル内を走行しているなど、何らかの事情で３００ｍ以上測位データが受信されなかったものと判断し、フィルタリング処理部はＤ４を異常点と扱わず正常な測位点とする。
【００３１】
次に、移動軌跡Ｔを形成するための処理を説明する。本明細書中では、移動軌跡Ｔは、所定ルールに基づいてグループ化された、連続する複数の測位点のことをいう。この場合の所定ルールは、どのように設定してもよい。例えば、連続する２つの測位点間の距離又は時間が、それぞれ所定範囲以内である複数の測位点をグループ化するというルールにしてもよい。また、移動軌跡Ｔを構成する複数の測位点のうち、最も早い日時の点を出発点とし、最も遅い日時の点を到着点としてもよい。
【００３２】
軌跡データ生成部１２は、フィルタリング処理を行った後の測位データを用いて、所定ルールに基づいてグループ化し、移動軌跡Ｔとして同じ軌跡ＩＤを付与する。例えば、軌跡データ生成部１２は、連続する２つの測位点が、所定以上時間間隔が空いた場合には、後の測位点から次の移動軌跡Ｔとして扱ってもよい。また例えば、軌跡データ生成部１２は、連続する測位点のうち、前後２つの測位点について、所定以上距離の差が開いた場合には、後の測位点から次の移動軌跡Ｔとして扱ってもよい。なお、上記のように、移動軌跡Ｔを形成することで、１つの移動軌跡Ｔに所定数以下しか測位点が存在しなくなった場合には、これらの測位点を移動軌跡Ｔと扱わなくてもよい。
【００３３】
軌跡データ生成部１２は、フィルタリング処理によって異常点を取り除いた後の測位データに、端末ＩＤ及び軌跡ＩＤを対応づけて軌跡データ記憶部１３に記憶する。
【００３４】
軌跡データ記憶部は１３、端末装置３の移動軌跡Ｔを示す軌跡データが格納される記憶部である。
【００３５】
図３は、軌跡データ記憶部１３内に記憶されたデータ構造の一例としての、端末装置３毎の軌跡データテーブル２０である。
【００３６】
端末装置３毎（各端末ＩＤ２１）の軌跡データテーブル２０には、例えば、軌跡ＩＤ２２、位置２３、日時２４、及びフラグ２５が記憶される。
【００３７】
軌跡ＩＤ２２は、移動軌跡Ｔを識別するためのＩＤである。位置２３は、測位点の緯度（Ｘｎ）及び経度（Ｙｎ）である。日時２４は、位置２３が測位された日時を示す。フラグ２５には、軌跡ＩＤ２２の中で最も早い日時のものが出発点、最も遅い日時のものが到着点として記録される。
【００３８】
条件抽出部１４は、軌跡データ記憶部１３から移動軌跡Ｔの出発点及び到着点を抽出する。例えば、条件抽出部１４は、軌跡データ記憶部１３から所望の軌跡ＩＤ２２を有する軌跡データをすべて読み出す。そして、読みだした軌跡データの中から、フラグ２５が出発点及び到着点であるデータを抽出する。
【００３９】
また、条件抽出部１４は、読みだした軌跡データの中から、移動軌跡Ｔ上の一以上の通過地点を抽出する。通過地点の抽出には様々な方法があるが、例えば、以下のようにしてもよい。
【００４０】
すなわち、移動軌跡Ｔを所定条件に基づいて複数に分割したときの分割点を通過地点として抽出してもよい。この場合、例えば通過地点は、移動軌跡Ｔを、およそ同じ長さ（距離）を有する複数の区間に分割した分割点としてもよいし、日時データ２４に基づいて時間的に略等間隔な複数の区間に分割した分割点としてもよい。例えば、分割点は、軌跡データから、略均等な距離又は時間間隔を有する複数の位置２３としてもよい。なお、通過地点の数は、予め設定しておいてもよい。これは例えば、利用者が手動で設定してもよいし、デフォルトで設定されていてもよい。
【００４１】
条件抽出部１４は、抽出した出発点、到着点、及び通過地点をルート検索部１５に通知する。
【００４２】
ルート検索部は１５、条件抽出部１４からの通知を受けると、出発点及び到着点をそれぞれ出発地及び目的地とし、かつ、一以上の通過地点を経由地としたルート検索を行う。
【００４３】
ルート検索部１５は、また、ルート検索の際には現在の交通情報を加味して最適なルートを検索するようにしてもよい。
【００４４】
ルート検索部１５は、検索したルートのルートデータをルート記憶部１６に格納する。ルート検索部１５は、検索したルートのルートデータを、地図情報記憶部１７から抽出した周辺の地図データとともに入出力部１１を介して、端末装置３に送信する。
【００４５】
次に、第１実施形態におけるルート検索装置１の動作を説明する。
【００４６】
図４は、端末装置３のディスプレイに表示されたルート検索の条件設定画面３１を示す図である。図５（ａ）は、第１実施形態における、通過地点の抽出を説明するための図である。図５（ｂ）は第１実施形態における、ルート検索を説明するための図である。
【００４７】
利用者は、図４に示す条件設定画面３１から、ルート検索のための設定条件を選択する。設定条件は、例えば、有料道路の利用の有無等の選択３２と、どの移動軌跡Ｔを利用するかの選択３３である。例えば、利用者は、このような設定条件の選択によって、有料道路等、自分の通りたい道を選択することができ、また、以前通ったことのある移動軌跡に基づいたルート検索を行うことができる。以下には、いずれかの移動軌跡Ｔを選択した場合のルート検索について説明する。
【００４８】
端末装置３は、条件設定画面３１で選択された設定条件をルート検索装置１に送信する。
【００４９】
設定条件を受信したルート検索装置１の条件抽出部１４は、設定条件に基づいて、軌跡データ記憶部１３から所望の移動軌跡Ｔの軌跡データを読み出し、その中から出発点、到着点及び通過地点を抽出する。
【００５０】
図５（ａ）では、出発点Ｓから到着点Ｇまでの移動軌跡Ｔを、同じ長さ（距離）を有する複数の区間に分割した４つの通過地点ｐ１０〜ｐ１３が抽出されている。条件抽出部１４は、抽出された出発点Ｓ、到着点Ｇ及び通過地点ｐ１０〜ｐ１３をルート検索部１５に通知する。
【００５１】
ルート検索部１５は、通知された出発点Ｓ、到着点Ｇ及び通過地点ｐ１０〜ｐ１３に基づいてルート検索を行う。図５（ｂ）は、出発点Ｓを出発地、到着点Ｇを目的地とし、４つの通過地点ｐ１０〜ｐ１３を経由地としてルート検索を行った結果である。点線で示されたルートが検索されたルートである。この場合、前述したように、利用者が端末装置３を介して有料道路の使用の有無等の条件を設定していれば、ルート検索部１５は、その条件を反映させたルート検索を行うこととなる。
【００５２】
本発明に係る第１実施形態によれば、移動軌跡Ｔ上の通過地点を経由地に設定することで、以前通った道に基づいて、道路状況などを反映させたルート検索を行うことができる。
＜第２実施形態＞
【００５３】
次に、第２実施形態について説明する。
【００５４】
上述の第１実施形態では、条件抽出部１４は、移動軌跡Ｔを所定条件に基づいて複数に分割したときの分割点を通過地点として抽出していたが、これに限定されない。
【００５５】
例えば、第２実施形態では、条件抽出部１４は、移動軌跡Ｔを、折れ線近似によって得られた折れ線と、移動軌跡Ｔとの交点を移動軌跡Ｔ上の一以上の通過地点として抽出する機能をさらに有するようにしてもよい。また例えば、この折れ線近似は、出発地と目的地とを結ぶ仮想直線からの距離が極大となる移動軌跡Ｔとの交点を、通過地点として抽出するようにしてもよい。
【００５６】
上記した、出発地と目的地とを結ぶ仮想直線からの距離が極大となる移動軌跡Ｔとの交点を、通過地点として抽出する折れ線近似の方法について、図６を参照して以下に詳細に説明する。しかしながら、折れ線近似の方法は、以下に説明するものに限定されるものではない。
【００５７】
図６（ａ）は、第１の通過地点を決定する方法を説明する図である。
【００５８】
条件抽出部１４は、まず、出発点Ｓと到着点Ｇの間を、直線Ｉ１で結ぶ。
【００５９】
次に、条件抽出部１４は、直線Ｉ１と移動軌跡Ｔとを、所定間隔ごとに、直線Ｉ１に直交する直線Ｉ２で結ぶ。なお、図示例のＩ２の間隔は、説明のために設定したものであり、これに限られない。
【００６０】
条件抽出部１４は、直線Ｉ１から移動軌跡Ｔまでにおいて、長さが最も長い直線Ｉ２と、移動軌跡Ｔとの交点を第１の通過地点Ｐ２１に設定する。
【００６１】
図６（ｂ）は、第２及び第３の通過地点を決定する方法を説明する図である。
【００６２】
条件抽出部１４は、移動軌跡Ｔ上に位置する、出発点Ｓ、到着点Ｇ及び第１の通過地点ｐ２１を折れ線で結び、移動軌跡の近似を行う。換言すると、条件抽出部１４は、出発点Ｓと第１の通過地点Ｐ２１、第１の通過地点ｐ２１と到着点Ｇとの間を、それぞれ直線Ｉ１１、Ｉ１２で結ぶ。
【００６３】
次に条件抽出部１４は、直線Ｉ１１及びＩ１２と移動軌跡Ｔとを、所定間隔ごとに直線Ｉ１１及びＩ１２に直交する直線Ｉ２で結ぶ（図示なし）。
【００６４】
そして、直線Ｉ１１に直交する最も長い直線Ｉ２と、移動軌跡Ｔとの交点をｐ２２とし、直線Ｉ１２に直交する最も長い直線Ｉ２と、移動軌跡Ｔの交点をｐ２３とする。
【００６５】
図６（ｃ）は、第２及び第３の通過地点を折れ線で結んで近似する方法を説明する図である。
【００６６】
条件抽出部１４は、移動軌跡Ｔ上に位置する、出発点Ｓ、到着点Ｇ、第１の通過地点ｐ２１、第２の通過地点ｐ２２、第３の通過地点ｐ２３を折れ線で結び、再度、移動軌跡の近似を行う。換言すると、条件抽出部１４は、出発地と第２の通過地点Ｐ２２、第２の通過地点ｐ２２と第１の通過地点ｐ２１、第１の通過地点ｐ２１と第３の通過地点ｐ２３、第３の通過地点ｐ２３と到着地との間を、それぞれ直線Ｉ１３、Ｉ１４、Ｉ１５、Ｉ１６で結ぶ。
【００６７】
ルート検索の際には、条件抽出部１４は、移動軌跡Ｔの出発点Ｓ、到着点Ｇとともに、上記のように抽出した通過地点ｐ２１〜２３をルート検索部１５に通知する。そして、ルート検索部１５は、通知された出発点Ｓを出発地、到着点Ｇを目的地、通過地点ｐ２１〜２３を経由地としてルート検索を行う。
【００６８】
本発明に係る第２実施形態によれば、移動軌跡Ｔ上の通過地点を経由地に設定することで、以前通った軌跡に基づき、かつ道路状況などを反映させたルート検索を行うことができる。また、第１実施形態のように経由地を移動軌跡Ｔ上に略均等に設定した場合に比べて、移動軌跡Ｔにより近似したルート検索を行うことができる。
＜第３実施形態＞
【００６９】
次に、第３実施形態について説明する。
【００７０】
条件抽出部１４及びルート検索部１５の機能は、上述した第１実施形態及び第２実施形態に例示した機能には限定されない。以下の第３実施形態に示す機能をさらに有してもよい。
【００７１】
第３実施形態では、条件抽出部１４は、移動軌跡Ｔの出発点Ｓ及び到着点Ｇを、それぞれ出発地及び目的地とした仮ルート検索をルート検索部１５に行わせ、移動軌跡Ｔ上の通過地点であって、仮ルート上にはない一以上の通過地点を抽出してもよい。
【００７２】
この場合、例えば、条件抽出部１４は、仮ルート検索をルート検索部１５に依頼するとともに、抽出した出発点Ｓ及び到着点Ｇの軌跡データをルート検索部１５に通知する。また、条件抽出部１４は、ルート検索部１５から仮ルート検索により生成されたルートデータを受信し、ルートデータに基づいて、通過地点の軌跡データを抽出する。詳細は後述する。
【００７３】
またこの場合、ルート検索部１５は、条件抽出部１４から通知された出発点Ｓ及び到着点Ｇの軌跡データをそれぞれ出発地及び目的地として、仮ルート検索を行う。ルート検索部１５は、また、仮ルート検索により生成されたルートデータを条件抽出部１４に送信する。
【００７４】
第３実施形態では、条件抽出部１４が抽出する一以上の通過地点は、仮ルートと最も乖離している移動軌跡Ｔ上の通過地点を含んでもよい。例えば、条件抽出部１４が抽出する一以上の通過地点は、仮ルート上に複数存在するノードのそれぞれについて、各ノードから移動軌跡Ｔまでの最短距離を算出し、算出した各ノードからの最短距離のうち最長距離となるノードに対応する移動軌跡Ｔ上の地点としてもよい。通過地点を抽出する方法の具体例を以下に説明する。
【００７５】
図７は、仮ルートから最も乖離した移動軌跡上の通過地点を抽出する方法を示すフローチャートである。図８は、移動軌跡Ｔ及び仮ルートＩＲから通過地点を抽出する方法を説明するため図である。
【００７６】
まず、条件抽出部１４は軌跡データ記憶部１３から軌跡データを読み出し、測位点（位置２３）を抽出する（ステップＳ１００）。
【００７７】
次に条件抽出部１４は、ルート検索部１５から受け取った仮ルートのルートデータから、各リンクをつなぐノードを抽出する（ステップＳ１０１）。
【００７８】
次に、条件抽出部１４は、ステップＳ１００で抽出した各測位点（位置２３）及びステップＳ１１１で抽出した各ノードに基づいて、各ノードから最も近い測位点（位置２３）をそれぞれ検索する（ステップＳ１０２）。
【００７９】
図８（ａ）は移動軌跡Ｔと仮ルートＩＲの拡大図である。説明のため、移動軌跡Ｔ上の測位点（位置２３）をＤ１１〜Ｄ１６で示し、仮ルートＩＲ上のノードをＮ１〜Ｎ３とした。図８（ａ）を参照して、ある１つのノードＮ１について最も近い測位点（位置２３）を検索する様子を説明する。例えば、条件抽出部１４は、ノードＮ１と移動軌跡Ｔ上のすべての測位点（位置２３）との距離を算出し、最も近い距離を選択する。図示例の場合、移動軌跡上Ｔ上のすべての測位点（位置２３）のうちどれが一番近いかを、例えばＤ１１、Ｄ１２、Ｄ１３、Ｄ１４、Ｄ１５、Ｄ１６というように順次検索する。ノードＮ１といちばん近い測位点はＤ１１であるので、これらを直線で結ぶ。
【００８０】
上記処理を、条件抽出部１４は、仮ルート上の複数のノードについて行う。図８（ｂ）では、Ｎ１とＤ１１、Ｎ２とＤ１４、Ｎ３とＤ１６とが、それぞれ直線で結ばれている。
【００８１】
条件抽出部１４は、ステップ１０２の結果から、各ノード及び各測位点（位置２３）を結ぶ直線の距離が一番長いものを抽出する（ステップＳ１０３）。
【００８２】
図示例ではＮ２とＤ１４を結ぶ直線の距離が一番長い。このため、この直線と移動軌跡Ｔとの交点であるＤ１４が通過地点（例えばＰ３０）として抽出される。
【００８３】
また、第３実施形態では、ルート検索部１５が、条件抽出部１４で抽出された通過地点を経由地として仮ルート検索を再度行う再仮ルート処理と、条件抽出部１４が、再仮ルート検索により抽出された仮ルート上にはない、移動軌跡Ｔ上の通過地点を再度抽出する再抽出処理とを、所定回数繰り返し、ルート検索部１５は、再仮ルート処理及び再抽出処理が、所定回数繰り返されて抽出された通過地点を経由地としてルート検索を行ってもよい。例えば、再仮ルート処理及び再抽出処理の繰り返し回数は、経由地をいくつ設けるかによって設定するようにしてもよい。利用者が手動で設定してもよいし、デフォルトで設定されていてもよい。
【００８４】
次に、第３実施形態に係るルート検索装置１の動作を図９〜１１を用いて以下に説明する。
【００８５】
図９は、第３実施形態に係るルート検索装置１の動作を表すフローチャートである。図１０は、第３実施形態における、通過地点の抽出方法を説明するための図である。図１１は、第３実施形態における、通過地点の抽出方法を説明するための図である。
【００８６】
端末装置３は、利用者がルート検索の条件設定画面３１から入力した設定条件を(図４参照)送信し、ルート検索装置１の条件抽出部１４は、この設定条件を受信する（ステップＳ１１０）。
【００８７】
Ｓ１１０で設定条件を受信した条件抽出部１４は、その設定条件に基づいて、軌跡データ記憶部１３から軌跡データを読み出し、この中から出発点Ｓ及び到着点Ｇを抽出する（ステップＳ１１１）。
【００８８】
そして、条件抽出部１４は、抽出した出発点Ｓ及び到着点Ｇをルート検索部１５に通知し、仮ルート検索を依頼する。
【００８９】
ルート検索部１５は、条件抽出部１４から通知された出発点Ｓを出発地、到着点Ｇを目的地として仮ルート検索を行う（ステップＳ１１２）。
【００９０】
図１０（ａ）は、ルート検索部１５による１回目の仮ルート検索の結果である。出発地から目的地までの移動軌跡Ｔを実線で示し、検索された仮ルートＩＲを二点鎖線で示す。ルート検索部１５は、検索した仮ルートのルートデータを条件抽出部１４に通知する。
【００９１】
条件抽出部１４は、ルート検索部１５から通知された仮ルートのルートデータ及びステップＳ１１１で軌跡データ記憶部１３から読み出した軌跡データに基づいて、通過地点を抽出する（ステップＳ１１３）。
【００９２】
図１０（ｂ）は、ステップＳ１１３によって、第１の通過地点ｐ４０が抽出された様子を示す。ここでは、上述したように、仮ルートから最も乖離した移動軌跡Ｔ上の点を第１の通過地点ｐ４０とした。
【００９３】
条件抽出部１４は、抽出した通過地点が所定数に達したか否かを判定する（ステップＳ１１４）。なお、前述したとおり、通過地点の数は予め設定しておいてもよい。
【００９４】
通過地点が所定数に達していない場合には（ステップＳ１１４：Ｎｏ）、ステップＳ１１２及びステップＳ１１３を再度行う。
【００９５】
この場合、条件抽出部１４は、移動軌跡Ｔの出発点Ｓ、到着点Ｇ、及び、ステップＳ１１３によって抽出されたすべての通過地点をルート検索部１５に通知する。通知を受けたルート検索部１５は、出発点Ｓを出発地、到着点Ｇを目的地、通過地点を経由地として、再度仮ルート検索が行う（ステップＳ１１２）。
【００９６】
図１１（ａ）は、ルート検索部１５による２回目の仮ルート検索及び第２の通過地点抽出の結果である。検索された仮ルートＩＲは第１の通過地点ｐ４０を経由地としている。また、検索された仮ルートから最も乖離した移動軌跡上の点を第２の通過地点ｐ５０としている。
【００９７】
図１１（ｂ）は、ルート検索部１５による３回目の仮ルート検索及び第３の通過地点抽出の結果である。検索された仮ルートＩＲは第１の通過地点ｐ４０、第２の通過地点ｐ５０を経由地としている。また、検索された仮ルートから最も乖離した移動軌跡Ｔ上の点を第３の通過地点ｐ６０としている。
【００９８】
通過地点が所定数に達した場合には（ステップＳ１１４：Ｙｅｓ）、条件抽出部１４は、移動軌跡Ｔの出発点Ｓ、到着点Ｇ及び抽出したすべての通過地点をルート検索部１５に通知する。そして、ルート検索部１５は、通知された出発点Ｓを出発地、到着点Ｇを目的地、通過地点を経由地としてルート検索を行う（ステップＳ１１５）。
【００９９】
本発明に係る第３実施形態によれば、移動軌跡Ｔ上の通過地点を経由地に設定することで、以前通った道に基づいて、道路状況などを反映させたルート検索を行うことができる。また、第１実施形態のように経由地を移動軌跡Ｔ上に略均等に設定した場合に比べて、移動軌跡Ｔにより近いルート検索を行うことができる。また、本実施形態では、経由地の設定に仮ルートを使用するため、経由地の選択においても、有料道路等の各種道路状況、道路状況などを考慮することができる。
【０１００】
上述した実施形態１〜３に示す条件抽出部１４の機能を組み合わせてもよい。例えば、第３実施形態に示すように、仮ルートを利用して通過地点を所定数抽出した後、抽出した通過地点を折れ線で結び、以降、第２実施形態に示した折れ線近似によって、移動軌跡上の通過地点をさらに抽出してもよい。
【０１０１】
上述した本発明の実施形態は、本発明の説明のための例示であり、本発明の範囲をそれらの実施形態にのみ限定する趣旨ではない。当業者は、本発明の要旨を逸脱することなしに、他の様々な態様で本発明を実施することができる。
【符号の説明】
【０１０２】
１ ルート検索装置
２ ネットワーク
３ 端末装置
１１ 入出力部
１２ 軌跡データ生成部
１３ 軌跡データ記憶部
１４ 条件抽出部
１５ ルート検索部
１６ ルート記憶部
１７ 地図情報記憶部
ＩＲ 仮ルート
Ｔ 移動軌跡
【特許請求の範囲】
【請求項１】
移動体の移動軌跡を示す軌跡データを記憶する軌跡データ記憶部と、
前記軌跡データに基づいて、前記移動軌跡の出発点及び到着点を抽出する手段と、
前記移動軌跡の出発点及び到着点を、それぞれ出発地及び目的地とした仮ルート検索を行う仮ルート検索手段と、
前記移動軌跡上の通過地点であって、前記仮ルート上にはない一以上の通過地点を抽出する通過地点抽出手段と、
前記出発地から前記目的地まで、前記通過地点抽出手段で抽出された通過地点を経由地としてルート検索を行うルート検索手段と、を備えたルート検索装置。
【請求項２】
前記通過地点抽出手段が抽出する一以上の通過地点は、前記仮ルートと最も乖離している前記移動軌跡上の通過地点を含む、請求項１記載のルート検索装置。
【請求項３】
前記通過地点抽出手段が抽出する一以上の通過地点は、前記仮ルート上に複数存在するノードのそれぞれについて、前記各ノードから前記移動軌跡までの最短距離を算出し、前記算出した各ノードからの最短距離のうち、最長距離となるノードに対応する前記移動軌跡上の通過地点を含む、請求項１又は２記載のルート検索装置。
【請求項４】
前記仮ルート検索手段が、前記通過地点抽出手段で抽出された通過地点を経由地として仮ルート検索を再度行う再仮ルート処理と、前記通過地点抽出手段が、前記再仮ルート検索により抽出された仮ルートと前記移動軌跡との距離に基づいて、前記移動軌跡上の通過地点を再度抽出する再抽出処理とを、所定回数繰り返し、
前記ルート検索手段は、前記仮ルート検索手段による再仮ルート検索及び前記通過地点抽出手段による再抽出処理が、前記所定回数繰り返されて抽出された通過地点を経由地としてルート検索を行う、請求項１〜３のいずれかの項に記載のルート検索装置。
【請求項５】
前記仮ルート検索手段による再仮ルート処理と、前記通過地点抽出手段による再抽出処理とを所定回数繰り返した後、
前記通過地点抽出手段により抽出された複数の通過地点と、出発地及び目的地とを折れ線で結び、前記移動軌跡の近似を行う折れ線近似手段を、さらに有し、
前記通過地点抽出手段は、前記折れ線近似手段で得られた折れ線と前記移動経路との交点を前記通過地点として抽出し、
前記ルート検索手段は、前記複数の通過地点を経由地としてルート検索を行う、請求項４に記載のルート検索装置。
【請求項６】
ルート検索装置が行う方法であって、
移動体の移動軌跡を示す軌跡データをサーバに記憶するステップと、
前記移動軌跡の出発点及び到着点を、それぞれ出発地及び目的地とした仮ルート検索を行うステップと、
前記移動軌跡上の通過地点であって、前記仮ルート上にはない一以上の通過地点を抽出するステップと、
前記出発地から前記目的地まで、前記通過地点抽出手段で抽出された通過地点を経由地としてルート検索を行うステップと、
を備えた方法。
【請求項７】
ルート検索を行うためのコンピュータプログラムであって、
移動体の移動軌跡を示す軌跡データをサーバに記憶するステップと、
前記移動軌跡の出発点及び到着点を、それぞれ出発地及び目的地とした仮ルート検索を行うステップと、
前記移動軌跡上の通過地点であって、前記仮ルート上にはない一以上の通過地点を抽出するステップと、
前記出発地から前記目的地まで、前記通過地点抽出手段で抽出された通過地点を経由地としてルート検索を行うステップと、をコンピュータに実行させるための実現されるコンピュータプログラム。
【請求項１】
移動体の移動軌跡を示す軌跡データを記憶する軌跡データ記憶部と、
前記軌跡データに基づいて、前記移動軌跡の出発点及び到着点を抽出する手段と、
前記移動軌跡の出発点及び到着点を、それぞれ出発地及び目的地とした仮ルート検索を行う仮ルート検索手段と、
前記移動軌跡上の通過地点であって、前記仮ルート上にはない一以上の通過地点を抽出する通過地点抽出手段と、
前記出発地から前記目的地まで、前記通過地点抽出手段で抽出された通過地点を経由地としてルート検索を行うルート検索手段と、を備えたルート検索装置。
【請求項２】
前記通過地点抽出手段が抽出する一以上の通過地点は、前記仮ルートと最も乖離している前記移動軌跡上の通過地点を含む、請求項１記載のルート検索装置。
【請求項３】
前記通過地点抽出手段が抽出する一以上の通過地点は、前記仮ルート上に複数存在するノードのそれぞれについて、前記各ノードから前記移動軌跡までの最短距離を算出し、前記算出した各ノードからの最短距離のうち、最長距離となるノードに対応する前記移動軌跡上の通過地点を含む、請求項１又は２記載のルート検索装置。
【請求項４】
前記仮ルート検索手段が、前記通過地点抽出手段で抽出された通過地点を経由地として仮ルート検索を再度行う再仮ルート処理と、前記通過地点抽出手段が、前記再仮ルート検索により抽出された仮ルートと前記移動軌跡との距離に基づいて、前記移動軌跡上の通過地点を再度抽出する再抽出処理とを、所定回数繰り返し、
前記ルート検索手段は、前記仮ルート検索手段による再仮ルート検索及び前記通過地点抽出手段による再抽出処理が、前記所定回数繰り返されて抽出された通過地点を経由地としてルート検索を行う、請求項１〜３のいずれかの項に記載のルート検索装置。
【請求項５】
前記仮ルート検索手段による再仮ルート処理と、前記通過地点抽出手段による再抽出処理とを所定回数繰り返した後、
前記通過地点抽出手段により抽出された複数の通過地点と、出発地及び目的地とを折れ線で結び、前記移動軌跡の近似を行う折れ線近似手段を、さらに有し、
前記通過地点抽出手段は、前記折れ線近似手段で得られた折れ線と前記移動経路との交点を前記通過地点として抽出し、
前記ルート検索手段は、前記複数の通過地点を経由地としてルート検索を行う、請求項４に記載のルート検索装置。
【請求項６】
ルート検索装置が行う方法であって、
移動体の移動軌跡を示す軌跡データをサーバに記憶するステップと、
前記移動軌跡の出発点及び到着点を、それぞれ出発地及び目的地とした仮ルート検索を行うステップと、
前記移動軌跡上の通過地点であって、前記仮ルート上にはない一以上の通過地点を抽出するステップと、
前記出発地から前記目的地まで、前記通過地点抽出手段で抽出された通過地点を経由地としてルート検索を行うステップと、
を備えた方法。
【請求項７】
ルート検索を行うためのコンピュータプログラムであって、
移動体の移動軌跡を示す軌跡データをサーバに記憶するステップと、
前記移動軌跡の出発点及び到着点を、それぞれ出発地及び目的地とした仮ルート検索を行うステップと、
前記移動軌跡上の通過地点であって、前記仮ルート上にはない一以上の通過地点を抽出するステップと、
前記出発地から前記目的地まで、前記通過地点抽出手段で抽出された通過地点を経由地としてルート検索を行うステップと、をコンピュータに実行させるための実現されるコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１１−２０３０１４（Ｐ２０１１−２０３０１４Ａ）
【公開日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願番号】特願２０１０−６８６２２（Ｐ２０１０−６８６２２）
【出願日】平成２２年３月２４日（２０１０．３．２４）
【出願人】（０００１５５４６９）株式会社野村総合研究所 (1,067)
【Ｆターム（参考）】
【公開日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願日】平成２２年３月２４日（２０１０．３．２４）
【出願人】（０００１５５４６９）株式会社野村総合研究所 (1,067)
【Ｆターム（参考）】
[ Back to top ]