(57)【特許請求の範囲】
【請求項１】
入力された２点間の道のりを概算で推定するための道のり推定装置であって、
メッシュ単位に経路選択の自由度を表す交差点数または総道路距離を格納した記憶手段と、
前記入力された２点をつなぐ線分を対角線とする矩形に含まれるメッシュを前記記憶手段から取得するメッシュ取得手段と、
取得した前記メッシュの自由度の数値の和ｃと、前記矩形の面積Ｓを求め、該面積Ｓが
小さいほど、また、該自由度の数値の和ｃが大きいほど大きくなるパラメータｐを算出するパラメータ算出手段と、
前記パラメータｐを用い、
【数５】
0005795238.tif 000005
(但し、βは事前に設定したパラメータ定数、ｘ１，ｘ２，ｙ１，ｙ２は前記入力された２点の座標)
の式を用いて、前記入力された２点の道のりを推定する推定手段と、
を有することを特徴とする道のり推定装置。
【請求項２】
コンピュータを、
請求項１に記載の道のり推定装置の各手段として機能させる道のり推定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道のり推定装置及びプログラムに係り、特に、都市内・都市間の指定された２点間の道のりを推定するための道のり推定装置及びプログラムに関する。
【背景技術】
【０００２】
２点間の道のりを自動的に推定するための技術として、従来より、
１）カーナビゲーションシステムに見られるように、道路地図相当の情報を保持し、２点間を結ぶ様々な経路のうち最短のものを返す方法（例えば、特許文献１参照）；
２）直線距離やマンハッタン距離を用いる方法；
という大きく２通りの方法が存在する。
【０００３】
上記の１）の方法は、正確な道のりの算出を行うことができるため、カーナビゲーションのように正確さが要求される状況で用いられている。
【０００４】
上記の２)の方法は、大きな記憶装置を必要とせず、より高速に算出を行えるため、道のりの算出を高頻度に行う必要がある状況、例えば、与えられた多数の地点の任意の２点間を結ぶ道のりを全て算出するような状況や、利用できる記憶資源が限られている状況などで用いられている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第３０７６０２６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、従来技術のうち、１)の方式によれば、膨大な地図データを必要とする上に、２点間での移動可能な各種経路の算出や、各経路を辿った場合の移動距離の算出を行う必要があった。すなわち、大規模な記憶装置が必要であるという課題と、計算のために必要な処理が大きいという問題があった。
【０００７】
また、２）の方式によれば、都市内で現実的な移動実態を反映した正確な道のりの算出をすることができないという問題があった。
【０００８】
本発明は、上記の点に鑑みなされたもので、大規模な記憶装置を必要とせず、高速に算出可能であって、しかも、都市内での現実的な移動実態を反映したより正確な道のりを算出することができるような道のり推定装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するため、本発明（請求項１）は、入力された２点間の道のりを概算で推定するための道のり推定装置であって、
メッシュ単位に経路選択の自由度を表す交差点数または総道路距離を格納した記憶手段と、
前記入力された２点をつなぐ線分を対角線とする矩形に含まれるメッシュを前記記憶手段から取得するメッシュ取得手段と、
取得した前記メッシュの自由度の数値の和ｃと、前記矩形の面積Ｓを求め、該面積Ｓが小さいほど、また、該自由度の数値の和ｃが大きいほど大きくなるパラメータｐを算出するパラメータ算出手段と、
前記パラメータｐを用い、
【数１】
0005795238.tif 000002
(但し、βは事前に設定したパラメータ定数、ｘ１，ｘ２，ｙ１，ｙ２は前記入力された２点の座標)
の式を用いて、前記入力された２点の道のりを推定する推定手段と、を有する。
【発明の効果】
【００１４】
本発明によれば、道のりの算出を直線距離ではなく、都市内での移動を反映した距離を用い、当該距離において、パラメータｐを用いたＬｐノルムを用い、単位矩形内のメッシュ毎の交差点数を用いるため、大規模な記憶装置を必要とせずに、高速に、より正確な２点間の道のりの推定が可能となる。
【００１５】
また、対象矩形内の総交差点数を取得した後には２つの数式のみであるので、高速に計算可能である。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施の形態における道のり推定装置の構成図である。
【図２】本発明の一実施の形態におけるメッシュ−交差点数データベースのデータ例である。
【図３】本発明の一実施の形態における概要動作のフローチャートである。
【発明を実施するための形態】
【００１７】
以下図面と共に、本発明の実施の形態を説明する。
【００１８】
図１は、本発明の一実施の形態における道のり推定装置の構成を示す。
【００１９】
同図に示す道のり推定装置は、矩形内メッシュ情報取得部１、距離調整パラメータ決定部２、道のり推定部３、メッシュ−交差点数データベース４から構成される。
【００２０】
メッシュ−交差点数データベース４は、図２に示すように、各メッシュの番号、そのメッシュの範囲、そのメッシュ内に含まれる交差点の数量を記録したものであり、ハードディスク等の記憶媒体に設けられる。本装置が取り扱う緯度経度から一意にメッシュ番号を特定するように構成することも可能である。その場合は、メッシュ範囲を持たず、メッシュ番号と、交差点数だけで構成することも可能である。
【００２１】
また、メッシュ−交差点数データベース４に格納する情報は、そのメッシュ範囲内で自由に移動のしやすさと相関にある情報であれば、必ずしも交差点数である必要はない。例えば、交差点数の代わりにメッシュ内での総道路距離等を用いることも可能である。
【００２２】
図３は、本発明の一実施の形態における概要動作のフローチャートである。
【００２３】
ステップ１）  矩形内メッシュ情報取得部１は、装置に入力された２点の座標を入力として受け取り、この２点をつなぐ線分を対角線とする矩形に含まれる全てのメッシュの情報をメッシュ−交差点数データベース４に問い合わせる。
【００２４】
ステップ２）  矩形メッシュ情報取得部１は、取得した矩形に含まれる全てのメッシュ情報について、メッシュ−交差点数データベース４を参照し、矩形内の総交差点数を得る。
【００２５】
ステップ３）  距離調整パラメータ決定部２では、矩形内メッシュ情報取得部１で得られた総交差点数ｃと矩形の面積（すなわち、装置に入力された２点をつなぐ線分を対角線とするような矩形の面積)Ｓを用いて、以下の式により非負の距離調整パラメータｐを決定する。
【００２６】
【数３】
0005795238.tif 000003
もし、上記の式(1)により算出したｐの値が負となった場合はｐ＝０とする。ここで、αは調整のためのパラメータ定数であり、想定されるＳ，ｃにおいて、ｐの値が概ね１〜２の値となるように決定することが望ましい。このαの決定方法としては、例えば、標準的な都市において２点間を選択した場合に、本装置により算出した道のりと実際の道のりが一致するように調整することが可能である。
【００２７】
ステップ４）  道のり推定部３では、装置へ入力された２点の座標(ｘ１，ｙ１)，（ｘ２，ｙ２）と、距離調整パラメータ決定部２によって決定された距離調整パラメータｐを用いて、以下の式(2)によって道のりを推定し、これを出力する。
【００２８】
【数４】
0005795238.tif 000004
ここで、βは事前に設定したパラメータ定数である。特に、ｐ＝０の場合は、２点間のｘ座標が同じか否か、および、ｙ座標が同じか否かによって場合分けされる。すなわち、２点が完全に一致であれば、０、ｘ座標とｙ座標のうち、いずれか１つが異なればβ、ｘ座標、ｙ座標ともに異なれば、β×２である。
【００２９】
上記のように本発明では、例えば、メッシュ−交差点数データベース４において、メッシュ範囲を持たない構成とした上で、総メッシュ数１万であるとき、交差点数を各１０ビットで表現した場合は、１０万ビットだけでよく、高速に２点間の道のりの推定が可能となる。
【００３０】
なお、上記の図１の道のり推定装置の各構成要素の動作をプログラムとして構築し、道のり推定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００３１】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００３２】
１  矩形内メッシュ情報取得部
２  距離調整パラメータ決定部
３  道のり推定部
４  メッシュ−交差点数データベース
【図１】
0005795238.tif 000006
【図２】
0005795238.tif 000007
【図３】
0005795238.tif 000008