ナビゲーションシステムの走行関連時間判断方法、その方法を実行するナビゲーションシステム及びプログラム
【課題】メッシュに対してタイムオフセット値を付与することによって出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定することにより、要求されるシステムの処理能力を低減することを可能にしたナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムを提供する。
【解決手段】車両の出発地点とリンクに関するリンク情報と地図情報を互いに隣接するメッシュに分割したメッシュ情報とを取得し(S2、S3)、出発地点を含む開始メッシュから特定のメッシュへ進入するリンクの種別及び、又は数に基づくタイムオフセット値を特定のメッシュに付与し、特定のメッシュに付与されたタイムオフセット値に基づいて出発地点を含む開始メッシュから特定のメッシュへの推測走行関連時間を測定する(S4)ように構成する。
【解決手段】車両の出発地点とリンクに関するリンク情報と地図情報を互いに隣接するメッシュに分割したメッシュ情報とを取得し(S2、S3)、出発地点を含む開始メッシュから特定のメッシュへ進入するリンクの種別及び、又は数に基づくタイムオフセット値を特定のメッシュに付与し、特定のメッシュに付与されたタイムオフセット値に基づいて出発地点を含む開始メッシュから特定のメッシュへの推測走行関連時間を測定する(S4)ように構成する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、基づいて出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定するナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムにおいて、特に、メッシュに対してタイムオフセット値を付与することによって出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定するナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムに関するものである。
【背景技術】
【0002】
従来より、ナビゲーションシステムにおける目的地までの経路を探索する際には、渋滞等の交通状況を考慮して探索が行われていた。しかし、リンクの交通状況は時刻毎によって異なる(例えば、午前中のみ渋滞するリンクもあれば、深夜のみ渋滞するリンクもある)ので、そのリンクを走行する時刻を特定しなければ、正確な交通状況を考慮した経路の探索を行うことができない。そこで、対応する道路ネットワークの各区域やリンクを走行するために必要となる予測時間を提供する走行時間データベースを使用したナビゲーションシステムが知られている。そのような従来のナビゲーションシステムにおいては、探索領域内の各リンクは個々のタイムスライス、例えば、リンクの開始地点への到着時刻に基づいて付与された走行時間(リンクを走行するのに必要な所要時間)を有する。
そして、道路は時刻によって状況が変化するので、当然、個々のタイムスライスはリンクの開始地点への到着時刻によって異なるものとなっている。
【0003】
例えば、図13は1日の時刻における、ある一リンクのタイムスライス(リンク走行時間)の一例である。車両又はセンタに設置された走行時間データベースは24時間又は1週間単位で図13に示すようなタイムスライスに関するデータを格納する。そして、経路探索の利用等においては、図14に示すように複数のリンクを順に走行する場合には、車両の走行順で一つ前リンクのタイムスライスが特定されなければ、次のリンクのタイムスライスを特定できない。
【0004】
しかし、車両の走行可能性のある地図上の全てのリンクについて、個々にタイムスライスを特定することとすると、メモリの容量が不足することとなっていた。また、タイムスライスを特定する処理を行う処理装置の負担が大きくなり、処理に必要な時間も多くなっていた。従って、経路探索や走行時間の推測等を実施するためにナビゲーションシステムでは高い処理能力が要求されていた。
【0005】
例えば、欧州特許出願公開第1496338号明細書では経路探索の為の別方法が記載されている。そこでは統計的に処理された過去の交通データが、タイムスライスベースの経路探索のために使われる。そして、システムはクライアントサーバ構造に基づいて出発及び目的の場所/時間のあらゆる可能な組み合わせが考慮され、事前計算されたセットデータとして格納される。計算に使われる対応するタイムスライスの計算要求がされると、前記対応データはあらゆる必要情報と共にサーバーから送信される。
【0006】
また、特開2004−301677号公報では統計的に処理された過去の交通データを基にしたタイムスライスベースの経路探索の為の別方法が記載されている。そこでは対応する目的地が決定した後、到達メッシュと出発メッシュの間の距離を用い、特定のメッシュ領域のための基準到達時刻が計算される。そして、特定のメッシュ領域内にあるリンク計算された基準到達時刻を含む時間帯の交通情報統計値を用いて推奨経路を探索する。
【特許文献1】欧州特許出願公開第1496338号明細書
【特許文献2】特開2004−301677号公報
【発明の開示】
【発明が解決しようとする課題】
【0007】
しかしながら、前記特許文献に記載された方法では、以前として計算量が膨大となっており、更に計算後のデータを格納する記憶媒体の容量も多く必要となっていた。従って、経路探索や走行時間の推測等を実施するためにナビゲーションシステムでは高い処理能力が要求されていた。
【0008】
本発明は前記従来における問題点を解消するためになされたものであり、走行時間や到着、通過時刻といった走行関連時間を判断する際に、事前計算や格納データ量を減少させることによって、要求されるシステムの処理能力を低減することを可能にしたナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【0009】
前記目的を達成するため本願の請求項1に係るナビゲーションシステムの走行関連時間判断方法は、車両の出発地点を取得する出発地点取得ステップと、リンクに関するリンク情報と地図情報を互いに隣接するメッシュに分割したメッシュ情報とを取得する地図情報取得ステップ(S3)と、出発地点を含む開始メッシュから特定のメッシュへ進入するリンクの種別及び、又は数に基づくタイムオフセット値を前記特定のメッシュに付与する付与ステップ(S4、S105、S107、S114、S115、S117、S118)と、前記特定のメッシュに付与されたタイムオフセット値に基づいて出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定する走行関連時間測定ステップと(S4)、を有することを特徴とする。
【0010】
また、請求項2に係るナビゲーションシステムの走行関連時間判断方法は、請求項1に記載のナビゲーションシステムの走行関連時間判断方法であって、前記メッシュは互いに隣接する多角形から構成され、その多角形の隣接面をメッシュの境界とすることを特徴とする。
【0011】
また、請求項3に係るナビゲーションシステムの走行関連時間判断方法は、請求項2に記載のナビゲーションシステムの走行関連時間判断方法であって、前記多角形は少なくとも三角形、正方形、矩形、六角形及び八角形の内の一つであることを特徴とする。
【0012】
また、請求項4に係るナビゲーションシステムの走行関連時間判断方法は、請求項1乃至請求項3のいずれかに記載のナビゲーションシステムの走行関連時間判断方法であって、前記開始メッシュからの距離が同距離であって、且つ開始メッシュに対して同じ方角で一直線上に配置される特定のメッシュにそれぞれに同一タイムオフセット値が付与されることを特徴とする。
【0013】
また、請求項5に係るナビゲーションシステムの走行関連時間判断方法は、請求項1乃至請求項3のいずれかに記載のナビゲーションシステムの走行関連時間判断方法であって、前記開始メッシュからの距離が同距離であって、且つ開始メッシュに対して同じ方角で一直線上に配置される特定のメッシュにそれぞれに異なるタイムオフセット値が付与されることを特徴とする。
【0014】
また、請求項6に係るナビゲーションシステムの走行関連時間判断方法は、請求項1乃至請求項5のいずれかに記載のナビゲーションシステムの走行関連時間判断方法であって、前記メッシュのうち特定のメッシュに付与されるタイムオフセット値は、前記特定のメッシュに含まれるリンクの種別に基づいて決定されるタイムオフセット予備値を含むことを特徴とする。
【0015】
また、請求項7に係るナビゲーションシステムの走行関連時間判断方法は、請求項6に記載のナビゲーションシステムの走行関連時間判断方法であって、前記タイムオフセット予備値を含むタイムオフセット値は、特定の種別のリンクからの出口の有無に関するリンク情報に基づいて決定されることを特徴とする。
【0016】
また、請求項8に係るナビゲーションシステムの走行関連時間判断方法は、請求項1乃至請求項7のいずれかに記載のナビゲーションシステムの走行関連時間判断方法であって、前記走行関連時間測定ステップにより測定された推測走行関連時間は、タイムマップを作成するタイムマップ作成ステップ、交通マップを作成する交通マップ作成ステップ、イベントマップを作成するイベントマップ作成ステップ、設定された目的地までの経路を探索する経路探索ステップのいずれかにおいて使用されることを特徴とする。
【0017】
また、請求項9に係るナビゲーションシステムは、車両の出発地点を取得する出発地点取得手段(12)と、リンクに関するリンク情報と地図情報を互いに隣接するメッシュに分割したメッシュ情報とを記憶する記憶手段(3)と、出発地点を含む開始メッシュから特定のメッシュへ進入するリンクの種別及び、又は数に基づくタイムオフセット値を前記特定のメッシュに付与する付与手段(11)と、前記特定のメッシュに付与されたタイムオフセット値に基づいて出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定する走行関連時間測定手段(11)と、を有することを特徴とする。
【0018】
また、請求項10に係るナビゲーションシステムは、請求項9に記載のナビゲーションシステムであって、車両の出発地点から所定の目的地点までの走行経路を探索する経路探索手段を有し、前記経路探索手段は前記走行関連時間測定手段によって測定された推測走行関連時間に基づいて走行経路を探索することを特徴とする。
【0019】
また、請求項11に係るナビゲーションシステムは、請求項9又は請求項10に記載のナビゲーションシステムであって、請求項1乃至請求項8に記載のいずれかのステップを実行することを特徴とする。
【0020】
また、請求項12に係るプログラムは、前記請求項1乃至請求項8に記載のいずれかのステップをコンピュータ上で実行させることを特徴とする。
【発明の効果】
【0021】
前記構成を有する請求項1に係るナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムでは、出発地点を含む開始メッシュから特定のメッシュへ進入するリンクの種別及び、又は数に基づくタイムオフセット値を特定のメッシュに付与し、付与されたタイムオフセット値に基づいて出発地点を含む開始メッシュから特定のメッシュへの推測走行関連時間を測定するので、出発地点が手動で入力されたり、GPSレシーバ等の装置で自動的に探索されれば、目的地が決定されない場合であっても、目的領域への到着時刻の推測が十分に正確に行うことが可能となる。
また、タイムスライスの時間計算によって、設定された目的地までの交通状況を各リンクの走行時刻で推測することが可能となり、目的地への経路探索時に各リンクの走行時刻における交通状況等を考慮した、より最適な経路の選択が可能となる。
【0022】
また、メッシュ間の道路端情報や、メッシュ内にある高速道路の出口の有無といった任意の他の追加情報に基づいて付与される新たなメッシュベースの計算方法の利用により、道路リンクのタイムスライスの計算のために要求される計算量と格納するデータ量が軽減する。その結果、必要となる処理能力が著しく低減される。
また、道路リンクをグループ化もしくは、定義された一範囲(メッシュもしくはメッシュグループ)内で同一区分のリンク間の個々の違いを考慮しないことにより、メッシュ領域内の特定の道路リンクに到着するのに必要な時間を推測することが可能である。その結果、1メッシュ内の、もしくは1メッシュ内にある同一区分のすべての道路リンクは、経路探索もしくは到着時刻の推測といったその他のアプリケーションの為に同一のタイムオフセット(もしくはタイムスライス)を有することになる。従って、個々のリンクについてタイムスライスを計算する必要がなくなる。
【0023】
本発明の概念において、データベースに格納される地図情報は、決まった大きさの複数の矩形からなるメッシュへの分割されている。言い換えれば、従来のデータベースに含まれる道路リンクはメッシュ構造によって管理される。そして、メッシュ毎に管理されたデータベースに基づいてメッシュの端や、その端(隣接するメッシュ間の境界線)を横断するリンク(道路)を特定する。更に、オフセット“0”を有するメッシュ(出発地点を有するメッシュ)との比較により、すべてのメッシュのオフセットが決定する。
【0024】
尚、各メッシュに単独のオフセットを付与すること、若しくは1メッシュに含まれるリンク(道路)種別により複数のオフセットを付与することについても可能である。
【発明を実施するための最良の形態】
【0025】
以下、本発明に係るナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムについて具体化した一実施形態に基づき図面を参照しつつ詳細に説明する。
【0026】
図1は本実施形態に係るナビゲーションシステム1の概略図である。図1に示すように本実施形態に係るナビゲーションシステム1はナビゲーション装置2とデータベース3とから基本的に構成されている。
【0027】
本実施形態にかかるナビゲーション装置2は、自動車等の車両に対して載置される車載機であり、タイムスライス計算モジュール(付与手段、走行関連時間測定手段)11、GPS受信部等の位置検索モジュール(出発地点取得手段)12、経路探索モジュール(経路探索手段)13、地図描画モジュール14、送受信モジュール15、出入力モジュール16、記憶モジュール(記憶手段)17、その他のアプリケーションモジュール18等の複数の機能装置を備えている。
【0028】
また、本実施形態に係るデータベース3は道路地図データベース21、交通データベース22、イベントデータベース23、その他の地理情報データベース24等を有するデータベース3へ接続している。
【0029】
ここで、道路地図データベース21は従来の方法で、リンクデータ、ノートデータ等の道路地図データを有するデータベースであり、また道路地図データをメッシュに分割したメッシュ情報を有する。
尚、メッシュは、隣接するメッシュ間の境界(境界線)を明確にする矩形やその他の多角形を有することが可能な定常のメッシュから構成されることが望ましい。具体的に望ましい実施形態としては、メッシュは矩形、できれば決まった大きさの正方形が望ましい。しかしながら、三角形、六角形、その他の多角形を有するメッシュも用いることができる。以下の実施形態の説明では、メッシュは便宜上同じ大きさの正方形メッシュから成るメッシュを意味する。
【0030】
また、交通データベース22は統計処理された過去の交通データ等の予測交通状況に関する情報を格納するデータベースである。イベントデータベース23はコンサートホールにおけるコンサート、競技場におけるサッカーの試合等の道路リンクに関連した時間関連イベント情報を格納するデータベースである。
【0031】
尚、データベース3は完全にもしくは部分的にナビゲーション装置2内、例えば記憶モジュール17に格納することができる。または、データベース3の一部もしくは全体が外部記憶装置(例えばハードディスクドライブやフラッシュメモリ等)に格納され、送受信モジュール15を通してアクセスできるように構成することが考えられる。
【0032】
また、ナビゲーション装置2は、メッシュベースの計算を用い、走行時間、到着時刻、通過時刻等の走行関連時間を決定できるように、メッシュ情報を有する道路地図データベースを少なくとも有することが望ましい。
【0033】
また、タイムスライス計算モジュール11は位置検索モジュール12によって判断される自動車等の車両位置、若しくはヒューマン・マシン・インターフェイス等を介してユーザが入力したその他の位置を基に車両の出発位置を特定し、後述されるようなタイムスライス計算を実施する。
【0034】
そして、タイムスライス計算モジュール11によって実施されたタイムスライス計算の結果は、経路検索モジュール13、地図描画モジュール14、その他のモジュール等によるその後の処理において用いることができる。
具体的には、経路検索モジュール13はタイムスライス計算の結果に基づいて、車両の出発位置から入力された目的地までの経路を構成する各リンクについて、そのリンクの走行時点での交通状況(例えば、渋滞情報や通行規制情報等)を取得する。そして、取得した交通状況を考慮して目的地までの経路のコストを計算し、最適な経路を選択する。
【0035】
次に図2及び図3に従って、データベース3に格納されている情報を用いて実行されるナビゲーション装置2の制御処理について説明する。
【0036】
図2に示すように、ナビゲーションシステム1の動作開始後には、先ず自車の出発位置と対応する計算の為の出発時刻がステップ(以下Sと略す)1、S2において取得される。続いて、S3においてメッシュ情報が道路地図データベース21から取得される。尚、アプリケーションが出発時刻を考慮しないのであれば、S2は必要ない。
【0037】
次に、S4においては開始メッシュから特定のメッシュへの推測走行関連時間等を計測するタイムスライス計算処理が、後述される方法でタイムスライス計算モジュール11によって実行される。そして、S4のタイムスライス計算の結果はS5におけるタイムマップの展開(生成)処理に用いられる。そして、S5ではユーザの操作情報に基づいて生成されたタイムマップの出力指示があるか否かが判定され、出力指示があると判定された場合(S6:YES)には、S7において出入力モジュール16に含まれるディスプレイ等の表示部にタイムマップが出力される。一方、出力指示がないと判定された場合(S6:NO)には、S8へと移行する。
【0038】
尚、図10は前記S7におけるタイムマップの出力の一例を示した図である。そして、タイムマップの出力(S7)がユーザの意図された処理の最終結果であったならば、処理フローはS7から終了に進む。そうでない場合、若しくはS5及びS7に代わり、より精密なアプリケーションが実行される場合には、S4のタイムスライス計算の結果は以下に詳載されているようにS9において交通マップやイベントマップの生成に用いられる。
また、S8では交通データベース22や前記イベントデータベース23において交通データやその他の時間関連イベントデータが検索及び取得され、取得された交通データやその他の時間関連イベントデータ、及びS4のタイムスライス計算の結果に基づいて、S9で交通マップやイベントマップの生成が行われる。
【0039】
次に、S10ではユーザの操作情報に基づいて生成された交通マップやイベントマップの出力指示があるか否かが判定され、出力指示があると判定された場合(S10:YES)には、S11において出入力モジュール16に含まれるディスプレイ等の表示部に交通マップやイベントマップが出力される。一方、出力指示がないと判定された場合(S10:NO)には、図3のS12へと移行する。
【0040】
尚、タイムマップ、交通マップ及びイベントマップでは、到着、通過時刻(例えば9:00、9:10等)の代わりに走行時間(例えば15分等)を表示することもできる。加えて、S6、S7及び、もしくはS10、S11に加えて、S4のタイムスライス計算によって取得したデータは図3に示されているように、経路探索やその他のアプリケーションに用いることもできる。
【0041】
続いて、S13ではナビゲーション装置2において目的地が設定されているか否かが判定される。そして、目的地が設定されていると判定された場合(S13:YES)には、目的地に関するデータがS14においてデータベース3から取得される。一方、目的地が設定されていないと判定された場合(S13:NO)には処理を終了する。
【0042】
次に、S15において、最適経路検索やその他のアプリケーションの処理が実行される。具体的に、経路探索処理では、前述の各S1〜S9で取得された自車の出発地点情報、メッシュ情報、交通データやその他の時間関連イベントデータ、及び前記S4のタイムスライス計算の結果に基づいて、車両の出発位置から入力された目的地までの経路を構成する各リンクについて、そのリンクの走行時点での交通状況(例えば、渋滞情報や通行規制情報等)を取得する。そして、取得した交通状況を考慮して目的地までの経路のコストを計算し、最適な経路を選択する。
【0043】
次に、S16ではユーザの操作情報に基づいて探索された経路の出力指示があるか否かが判定され、出力指示があると判定された場合(S16:YES)には、S17において出入力モジュール16に含まれるディスプレイ等の表示部やスピーカを用いて探索された最適な経路(誘導経路)や誘導経路に従った走行の案内が出力される。一方、出力指示がないと判定された場合(S16:NO)には、S20へと移行する。
【0044】
更に、S21では、任意で更新された位置、時間データを基に経路のタイムスライスの動的な更新処理と、更新されたタイムススライスの計算結果に基づく再度の経路探索が行われる。そして、S19においては、前記S18で探索された新たな誘導経路や誘導経路に従った走行の案内がディスプレイ等の表示部やスピーカを用いて出力される。尚、S18における誘導経路の動的な更新処理やS19における再経路の出力処理は従来のタイムスライス技術もしくは、S4における更新されたタイムスライス計算の結果を用いて周知の技術により実施される。
【0045】
次に、図4を用いて前記S4におけるタイムスライスのメッシュベースに基づく計算の一例を説明する。図4はメッシュyyyxxx00、yyyxxx01、yyyxxx02と称される3つの隣接する正方形メッシュを示す。メッシュyyyxxx00は車両の出発点を含むメッシュであり、これ以降、開始メッシュと称する。尚、メッシュ(間)は境界線によって分けられる。また、図4では簡易な例を示しており、1メッシュから隣のメッシュへの移動は1方向のみと考えるものとする。従って、メッシュyyyxxx02へ移動する際にはメッシュyyyxxx01を通過して移動するものとする。
【0046】
ここで、図4に示すように開始メッシュyyyxxx00にはタイムオフセット値として0が付与される。
一方、開始メッシュyyyxxx00の隣のメッシュyyyxxx01には特定のオフセット値としてオフセット値0.25が付与される。タイムオフセット値0.25は時間基準(本実施形態においては1時間)によって積される数値であり、メッシュyyyxxx01のオフセット時間は0.25×60分=15分となる。
そして、メッシュyyyxxx01の更に隣のメッシュyyyxxx02には特定のオフセット値、オフセット値0.5が付与される。従って、例えば1時間の時間基準と考えると30分がオフセット時間となる。
【0047】
次に、オフセット値がどのように算出されるかを説明する前に、図4において示されている道路(リンク)の区分について説明する。メッシュyyyxxx00内の出発点0からノードNA、NB,NC、NDを通過し、目的地Dまでの道路(リンク)は道路種別及びオフセット種別がHとなる高速(走行)が認められた幹線道路や高速道路といった上級リンクである。また、ノードNAから境界地点BBを通過し、ノードNCまでの道路(リンク)は道路種別及びオフセット種別がMとなる中級リンクとみなされる。ノードNCを迂回するノードNBとNDを結ぶ道路(リンク)は道路種別及びオフセット種別がLの下級リンクである。
【0048】
そして、本実施形態では以下に説明するようにオフセット種別Hのオフセット予備値を0.25、オフセット種別Mのオフセット予備値を0.4、オフセット種別Lのオフセット予備値を0.7として、メッシュのオフセット値を決定する。
【0049】
メッシュベース計算の最も簡易な実施形態として本実施形態では、移動方向にあるメッシュに進入する道路の種別に基づく可能な最小オフセット値であるオフセット値を各メッシュに付与する。例えば図4の場合、移動方向は出発点0から目的地Dへの方向となる。従って、図4に示すようにメッシュyyyxxx00とメッシュyyyxxx01間の境界線において、境界線横断地点BAにおける種別Hリンクと境界線横断地点BBにおける種別Mリンクと称される、境界線を横断する2つのリンクが存在する場合には、メッシュ(例えばメッシュ内のすべてのリンク)は道路種別Hのオフセット値、例えばオフセット値0.25に決定される。
【0050】
また、図4に示すようにメッシュyyyxxx01とメッシュyyyxxx02間の境界線においては、リンク種別Hと称される1リンク(道路)のみがメッシュyyyxxx01とメッシュyyyxxx02間の境界線を横断する為、その前のメッシュメッシュyyyxxx01に対する相対的なオフセットのみが考慮されるのであれば、メッシュyyyxxx02はオフセット値0.25に決定される。但し、本実施形態では出発地点に基づく走行時間の推測を目的としている為、メッシュのオフセット値は以下の式(1)に従って算出される。
メッシュに付与されるオフセット=その上流メッシュのオフセット値+その上流メッシュからの相対的なオフセット値・・・(1)
【0051】
従って、図4に示す例では、メッシュyyyxxx02のオフセット値=その上流メッシュyyyxxx01のオフセット(=0.25)+その上流メッシュからの相対的なオフセット値(=0.25)=0.5となる。
【0052】
また、仮にノードNDと目的地D間のリンクを(リンク種別Hの代わりに)リンク種別Lと想定すると、メッシュyyyxxx02のオフセット値=0.95(0.25+0.7)となる。
【0053】
上記方法の変形例について図5を用いて説明する。図5は、メッシュXとその隣接メッシュYを示す。本変形例で考慮される移動方向は境界線B1から境界線B2を経て、境界線B3へと向かうものである。境界線横断地点BAから境界線横断地点BBを経て、境界線横断地点BCまでのリンクは種別Hリンクである。ノードNAは、種別Hのこのリンクから種別Mのリンクへの出口である。
【0054】
ここで、図4に従って説明した第一方法では、前記S4のタイムスライス計算において、1メッシュ内のすべてのリンクが一括して考慮され、そのメッシュは単一のオフセット値を受理する。従って、1メッシュのすべてのリンクに対し唯一の共通のオフセットが存在することとなる。
【0055】
しかしながら実際は、通常、1メッシュ内においてもその道路網には種々な異なるリンクが存在する。そのような差異を考慮することにより、前記メッシュベース計算の正確性が改良される。
【0056】
図5に示す変形例においては、特定の境界線を経て進入する道路種別に加え、メッシュ内の異なる種別のリンクの接続が考慮される。ここで、本目的の為に用いられる基本情報は、上級リンクである種別Hリンクからの出口の利用の可能性と任意でその数である。
【0057】
図5に示されている例において、メッシュXはノードNAと称される上級リンク出口を含んでいる。
【0058】
図5に従って説明される変形例においては、次に図6及び図7で説明されるように、メッシュ内に含まれる異なる種別のリンクに対して、1メッシュは異なるオフセット値を3つまで受理する。ここで、図6及び図7はタイムスライス計算(図2のS4)のサブ処理について説明したフローチャートである。
【0059】
図6に示すように、タイムスライス計算(図2のS4)は、先ずS101において開始メッシュを判定する。その後、S102において隣接メッシュもしくはメッシュグループが決定される。尚、それぞれの具体例については後に説明する。その後、S103において、前記S102で決定されたメッシュもしくはメッシュグループのうちの1つがタイムスライス計算を実施する為に選択される。
【0060】
その後、S104において、異なるリンク種別H(上級)、M(中級)、L(下級)のそれぞれに対して、メッシュの境界線を通って進入するリンク(道路)の数が決定される。例えば、図5に示すメッシュXは境界線B1を考えた場合、地点BAで境界線を横断する種別Hの進入リンクを1つと地点BDで境界線を横断する種別Mの進入リンク1つを有する。メッシュYは、境界線B2を考えた場合、地点BBで境界線を横断する種別Hの進入リンクを1つ、地点BEで境界線を横断する種別Mの進入リンクを1つ、そして地点BFで境界線を横断する種別Lの進入リンクを1つ有する。
【0061】
次にS105において、前記S103で選択されたメッシュもしくはメッシュグループ内にある対応する上級リンクに、種別Hの上級リンクに対応するオフセット値が付与される。
【0062】
更に、S106において、ノードNA等の上級リンクの出口がメッシュもしくはメッシュグループ内に存在するかどうかを確認する。例えば、図5に示すメッシュXには上級リンク出口が1つあるが、メッシュYには上級リンク出口はない。また、ステップS107において、メッシュもしくはメッシュグループ内にある種別MとLのリンクにオフセット値が付与される。
【0063】
そして、S108では前記S103においてまだ選択されていないメッシュもしくはメッシュグループがあるか否か判定される。その結果、選択されていないメッシュもしくはメッシュグループがあると判定された場合(S108:YES)にはS103へと戻り、残りのメッシュ若しくはメッシュグループから次のメッシュ若しくはメッシュグループが選択される。一方、全てのメッシュもしくはメッシュグループが選択済であると判定された場合(S108:NO)にはタイムスライス計算(図2のS4)のサブ処理を終了し、S5へ戻る。
【0064】
次に、図7を用いてステップS104〜S107までの変形例について説明する。尚、図7から分かるように、取得と付与の処理順序はステップS104〜S107における順序と完全に同じではない。それは、対応するステップは存在するが完全に対応する順序で行う必要はないからである。
【0065】
先ず、S111において特定のメッシュ境界線における種別Hの進入リンクの数が取得される。そして、S112では種別Hの進入リンクの数が少なくとも1以上あるか否か判定される。その結果、種別Hの進入リンクの数が少なくとも1以上あると判定された場合(S112:YES)には、S113において、メッシュグループのメッシュ内における種別Hのリンクからの出口が在るか否か判定される。
【0066】
そして、対応するメッシュ内に種別Hのリンクからの出口が存在すると判定された場合(S113:YES)には、S114において、対応するメッシュ内の(種別H、M、Lの)すべてのリンクに種別Hのオフセット(上記例においては0.25)が付与され、S108へと移行する。
【0067】
一方、対応するメッシュ内に種別Hのリンクからの出口が存在しないと判定された場合(S113:NO)には、S115において対応するメッシュ内の種別Hのリンクにのみ種別Hのオフセットが付与され、S116に進む。
【0068】
また、前記S112で種別Hの進入リンクの数が存在しないと判定された場合(S112:NO)には、S116において、種別Mの進入リンクの数が少なくとも1以上在るか否か判定される。その結果、種別Mの進入リンクの数が少なくとも1以上あると判定された場合(S116:YES)には、S117において、対応するメッシュ内のすべてのリンクに種別Mのオフセットが付与される(但し、S115を経由した場合においては残るすべてのリンクに種別Mのオフセットが付与される)。その後、S108へと移行する。
【0069】
一方、種別Mの進入リンクの数が存在しないと判定された場合(S116:YES)には、すべてのリンク、もしくは残るすべてのリンクに種別Lのオフセットが付与される。その後、S108へと移行する。
【0070】
尚、すでに記載したように図7において示される実施形態は単なる一例にすぎない。また、種別Hのリンクからの出口の数もしくは種別Mのリンクからの出口の有無やその数が考慮されうる。また、図6及び図7は異なる種別のリンク間を接続するノードの有無を考慮することができることを根本的に示唆するものである。
【0071】
即ち、種別Hのリンクを経てメッシュXへ進入した時、あたかもメッシュXにおける全走行が種別Mもしくは種別L上においてのみ実施されたかのようであるが、ノードNAと境界線の横断地点BEとを接続する種別Mのリンク上の全走行速度が(上記状況)より高速である等の事実を反映させることができる。一方、メッシュYにおいて、境界線横断地点BBを経てメッシュYへ進入した場合、種別MもしくはLのリンクへ変更する可能性はない。従って、これらのリンクは種別Hのリンク上におけるより高速な走行速度の恩恵を受けることができない。
【0072】
上記変形例においては、同じメッシュ内の異なる種別のリンクに異なるオフセットが付与されうる。異なる種別のリンクに対する異なるオフセットの付与は出口の有無等の考慮に限定されるものではない。当然、同じメッシュ内の異なる種別のリンクへの異なるオフセットの付与は出口の有無等を考慮せずとも可能である。
【0073】
次にメッシュのオフセット値を算出するためのフローパターンについて、図8を用いて説明する。図8に従って説明される例はステップS103において実施される隣接メッシュもしくはメッシュグループの選択に関する2例のうちの1例である。
図8は8×8メッシュ、例えば64メッシュのマトリクスから成るメッシュを示す。S1において取得される出発地点はメッシュ33に位置する。メッシュは正方形である。従って各メッシュは正方形の隣接面によって表される隣接メッシュとの4つの境界線を有する。図8から、出発地点を含む開始メッシュ33は4つの境界線を有し、その4つの境界線を横断する退出リンクだけが存在することは明らかである。そして、開始メッシュ33にはタイムオフセット0が付与される。また、以下で開始メッシュ、もしくは出発地点周辺の扱いの方法については種々あるが、当面の間は開始メッシュのタイムオフセットは0のみと考える。
【0074】
図8において示されるフローパターンは以下の規則に従って、開始メッシュからのメッシュの距離の増加を示す。
a)各メッシュ(開始メッシュを除く)はリンクが境界線を横断すると考えられる境界線を2つのみ有する。
b)1メッシュ内に進入リンクが存在するならば、横断する進入リンクを有する境界線の反対側の境界線が退出リンクを有する境界線であると判断される。
c)進入リンクを有さないメッシュ(開始メッシュと対角線上で交差するメッシュ)において退出リンクを有する境界線は、退出リンクを有する隣接メッシュの境界線に連続する境界線となるよう選択される。
【0075】
従って、図8において矢印によって示されるフローパターンは増加する距離のフローパターンを示す移動順序で1つのメッシュから隣接するメッシュへの移動を示す。進入リンクを有さない上記メッシュ(開始メッシュ33と対角線上で交差する位置にあるすべての「コーナーメッシュ」00,11,22,44,55,66,77,06,15,24,42,51,60)に関して上記メッシュは考慮すべき進入リンクを有さず、マトリクスの同じ列もしくは行の2つの「コーナーメッシュ」間に位置するメッシュと開始メッシュからの距離が同じであると考えなければならない。従って、上記「コーナーメッシュ」もフローパターンにおいて開始メッシュからの増加距離を示すメッシュである。
【0076】
そして、各メッシュへのオフセット値の付与は前記S4において説明された計算に基づき実施される。
【0077】
当然この場合、「コーナーメッシュ」の(オフセット値の付与の)為の解決方法が必要となる。なぜなら、これら「コーナーメッシュ」は進入メッシュを有さない為、上流メッシュや進入リンクに基づくオフセット値の計算が不可能だからである。
【0078】
ここで、「コーナーメッシュ」へのオフセット値付与の望ましい付与方法はフローパターンにおける同距離の隣接メッシュのうち低い方の値の付与である。例えば、コーナーメッシュ42の場合、メッシュ32と43のメッシュ値のうち低い値である。
【0079】
図8において示されるフローパターンに基づくオフセット値の付与の特殊な変形例は開始メッシュからの距離が同レベルで、開始メッシュに対して同じ方角(北側、西側、南側、東側)に配列されたすべてのメッシュに同じ値を付与することである。この同じ値は、同距離レベルで同じ方角に配列されたメッシュのすべてのメッシュ値のうち最も低い値であることが望ましい。一例として、メッシュ25、35、45、は(フローパターンでは同じ網かけによって示される)距離が同レベルで同じ方角(東側)に配列されている。
例えば、メッシュ25のオフセット値を0.8、メッシュ35のオフセット値を1.4、メッシュ45のオフセット値を0.65と想定すると、最も低い値(メッシュ45の0.65)がメッシュ23、35、45の各々に付与される。同様にフローパターンにおいて北側の距離が同レベルにあるメッシュ、例えばメッシュ52、53、54も同じオフセット値を有する。そのオフセット値を0.5と想定すると、2つの利用可能なメッシュ値のうち低い値(0.5)がコーナーメッシュ55に付与される。従って図8において示されるフローパターンは以下の追加規則を有する。
d)特定の選択規則に従い、開始メッシュに対して同じ方角で同距離レベルに位置するすべてのメッシュに、これらメッシュの最も高い値、最も低い値、もしくはその平均値等のうちの1つの値を付与する。
e)上記d)における同じ規則に従い、同距離レベルの隣接メッシュのオフセット値から選択されるオフセット値をコーナーメッシュに付与する。
【0080】
尚、変形例として図8に示されるフローパターンにおいて、リンク種別やメッシュ内の出口の数等を反映させて、1メッシュ内にある異なる種別のリンクに異なるオフセット値を付与することは当然可能である。また別の例としては、S103におけるグループ選択の後、グループ内のメッシュにオフセットを付与する為に各メッシュの進入リンクの数の代わりに、グループ内のすべてのメッシュに対する進入リンクの数が考慮される。
【0081】
次に、S103の隣接メッシュ、もしくはメッシュグループの選択の別例について図9を用いて説明する。図8とは異なり、図9においては、隣接メッシュ間の各境界線は進入もしくは退出リンクを有する境界線と考えられる。そのため、図8に示されているフローパターンにあるような「コーナーメッシュ」は存在しない。尚、図9に示されるフローパターンも開始メッシュからの増加距離を示すフローパターンであり、その増加距離は開始メッシュから出発する矢印によって横断される境界線の数によって表される。
【0082】
従って、図9に示すフローパターンではメッシュ23、32、34、43は開始メッシュ33からの距離が同レベルにあり、メッシュ13,22,24,31,35,42,44,53は開始メッシュからの距離が次のレベルにあり、メッシュ03,12,14,21,25,30,36,41,45,52,54,63はさらにその次の距離レベルにあるというように続いていく。
【0083】
図9に示されているフローパターンにおいては、S4に関して説明されているのと同様のオフセット値を算出、付与するための処理が用いられる。各メッシュに個別オフセット値を付与することが望ましいが、距離レベル等に応じて同じメッシュ値を付与することも可能である。
【0084】
図8及び図9において、S103の隣接メッシュもしくはメッシュグループの決定とステップS104の次のメッシュもしくはメッシュグループの選択は以下のように考えられる。
図8において、各メッシュが個別の値を受理するならば、隣接メッシュもしくはメッシュグループの決定はフロー手順で実施されることが望ましい。つまりまず、メッシュ33,34はグループ化され、もしくは流れが同一方向であるすべてのメッシュ、つまりまずメッシュ33,43、メッシュ33,34、メッシュ33,23、メッシュ33,32がグループ化され対応するオフセット値が算出される。次に、コーナーメッシュ22,24,42,44のメッシュ値が算出される。引き続き、メッシュ22,12、メッシュ23,13、メッシュ24,14、メッシュ24,25、メッシュ34,35等がグループ化され対応するオフセット値が算出、付与される。その後、コーナーメッシュ11,15,51,55のオフセット値が算出され、この論理に従って処理が続いていく。
【0085】
一方、図9において、S103の選択は同様に実施される。つまり、まずメッシュ33,23、メッシュ33,34、メッシュ33,43、メッシュ33,32がグループ化され対応するオフセット値が算出、付与される。次にグループ決定がすでに事前に実施されているかどうかを判断し、メッシュ23,22、メッシュ23,13、メッシュ23,24、メッシュ32,22、メッシュ31,21、メッシュ32,42、メッシュ34,24、メッシュ34,35、メッシュ34,44、メッシュ43,42、メッシュ43,53、メッシュ43,44等のメッシュグループが算出、付与される。メッシュ毎の単一オフセット値もしくは上述されているような出口の数等の他の要素を考慮する可能性を有する異なる種別リンクの複数のオフセット値がオフセット値を算出、付与する際に用いられる。開始メッシュと開始メッシュと共有の境界線を有するメッシュ(23,32,34,43)を除く各メッシュは進入リンクを有する2つの境界線を有する。従って、(各メッシュに)1つのオフセット値、もしくはメッシュ内の特定種別リンクに1つのオフセット値を付与することができるように、どの値が選択されるべきかという規則を確定する必要があることは明らかである。これは、例えば2つの境界線のオフセット値のうちの低い値を付与することによって実施されうるが、高い値や平均値、他の規則によって決定される値であってもよい。
【0086】
開始メッシュもしくは出発地点の周辺範囲に関しては、距離が限定されたり、道路網への接続が限られたりする為、リンク(道路)種別の違いを考慮する必要がない可能性がある。従って、上記方法の変形例としては、進入リンクの数や種別を考慮せずに、開始メッシュ周辺の複数のメッシュから構成されうる周辺範囲に、単一オフセットが付与される。図11はそのような変形例を簡素な方法で示している。
【0087】
他の変形例としては、オフセット計算はリンク種別を用いる際に、ユーザの好みを考慮する。例えば、ユーザが例えば種別Hのリンクである幹線道路や高速道路を用いることを好んだり、最短経路を用いることを好んだりした場合は、それをメッシュオフセット値の計算の考慮に入れることも可能である。
【0088】
例えば、ユーザが例えば種別Hのリンクである幹線道路や高速道路を用いることを好んだ場合、対応する種別のリンクに対して選択されるオフセット値は上述の標準オフセット値と比較して減少する。また、可能であれば他のリンク種別を単に無視することもできる。
【0089】
また、ユーザが最短経路を望むならば、図12に示す方法も可能である。先ず、出発地点を含む開始メッシュ(出発メッシュ)と目的地を含むメッシュ(ターゲットメッシュ)間の直線、例えばその2つのメッシュの中心を結ぶ直線、もしくは出発地点と目的地を結ぶ直線等を引く。ここで、図14の例に示されているように、ターゲットメッシュのオフセット値の算出の為に、メッシュAとメッシュBの2つのオフセット値のうちのどちらが選択されるが決定されなければならない。尚、ユーザは最短経路を望んでいるので、メッシュBのオフセット値の方が小さくても、この直線はメッシュAを横断している為、メッシュAの値が選択される。
【0090】
また、前記S10、S11で説明したように、交通マップおよび、もしくはイベントマップは例えば、対応経路の色分け等による交通予測や、表示された地図上に配置された所定のアイコンによって表示される(サッカーの試合、休日の交通の流れ等の)時間関連情報等を含む。従って、ユーザがT1時刻にA地点を出発し、T2時刻のコンサートに間に合うようB地点にいたいならば、X道路を使用した場合、サッカーの試合の為、C地点で交通渋滞が生じるであろうとユーザが理解できる。これにより、ユーザが経路探索機能を使わずに自分の時間スケジュールを立てたり決定しやすくなる。
【0091】
尚、上述した明細書および、もしくは請求項に開示されているすべての特徴は実施例および、もしくは請求項の特徴の構成から独立して請求されている発明の制限とともに、出願時の開示を目的として、別々に互いに独立したものとして開示されるよう意図されていることを明記している。また、すべての値の範疇および、もしくは構成要素のグループ化の指定は、請求されている発明の制限、特に値の範疇の制限とともに、出願時の開示を目的としてあらゆる可能な中間値や中間構成要素の開示を明記している。
【図面の簡単な説明】
【0092】
【図1】本実施形態に係るナビゲーションシステムの構成を示す概略ブロック図である。
【図2】本実施形態に係るナビゲーション装置の制御処理を示すフローチャートである。
【図3】本実施形態に係るナビゲーション装置の制御処理を示すフローチャートである。
【図4】本発明の単純な変形例を示す図である。
【図5】図4で示した変形例を説明する2つの隣接するメッシュを示す図である。
【図6】本実施形態に係るナビゲーション装置のオフセット付与の処理を示すフローチャートである。
【図7】本実施形態に係るナビゲーション装置のオフセット付与の処理の変形例を示すフローチャートである。
【図8】メッシュグループへのオフセット付与の例を示した図である。
【図9】各メッシュへの個別のオフセット付与の例を示した図である。
【図10】図2のS7におけるタイムマップ出力の例を示した図である。
【図11】出発地点周辺地域を個別に処理するための変形例を示した図である。
【図12】短距離経路探索の例を示す図である。
【図13】ある特定の一リンクの走行時間の例を示す図である。
【図14】最適経路探索の為の従来のタイムスライス方法を示す図である。
【符号の説明】
【0093】
1 ナビゲーションシステム
2 ナビゲーション装置
3 データベース
11 タイムスライス計算モジュール
12 位置検索モジュール
13 経路探索モジュール
14 地図描画モジュール
15 送受信モジュール
16 出入力モジュール
17 記憶モジュール
21 道路地図データベース
22 交通データベース
23 イベントデータベース
24 その他の地理情報データベース
【技術分野】
【0001】
本発明は、基づいて出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定するナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムにおいて、特に、メッシュに対してタイムオフセット値を付与することによって出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定するナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムに関するものである。
【背景技術】
【0002】
従来より、ナビゲーションシステムにおける目的地までの経路を探索する際には、渋滞等の交通状況を考慮して探索が行われていた。しかし、リンクの交通状況は時刻毎によって異なる(例えば、午前中のみ渋滞するリンクもあれば、深夜のみ渋滞するリンクもある)ので、そのリンクを走行する時刻を特定しなければ、正確な交通状況を考慮した経路の探索を行うことができない。そこで、対応する道路ネットワークの各区域やリンクを走行するために必要となる予測時間を提供する走行時間データベースを使用したナビゲーションシステムが知られている。そのような従来のナビゲーションシステムにおいては、探索領域内の各リンクは個々のタイムスライス、例えば、リンクの開始地点への到着時刻に基づいて付与された走行時間(リンクを走行するのに必要な所要時間)を有する。
そして、道路は時刻によって状況が変化するので、当然、個々のタイムスライスはリンクの開始地点への到着時刻によって異なるものとなっている。
【0003】
例えば、図13は1日の時刻における、ある一リンクのタイムスライス(リンク走行時間)の一例である。車両又はセンタに設置された走行時間データベースは24時間又は1週間単位で図13に示すようなタイムスライスに関するデータを格納する。そして、経路探索の利用等においては、図14に示すように複数のリンクを順に走行する場合には、車両の走行順で一つ前リンクのタイムスライスが特定されなければ、次のリンクのタイムスライスを特定できない。
【0004】
しかし、車両の走行可能性のある地図上の全てのリンクについて、個々にタイムスライスを特定することとすると、メモリの容量が不足することとなっていた。また、タイムスライスを特定する処理を行う処理装置の負担が大きくなり、処理に必要な時間も多くなっていた。従って、経路探索や走行時間の推測等を実施するためにナビゲーションシステムでは高い処理能力が要求されていた。
【0005】
例えば、欧州特許出願公開第1496338号明細書では経路探索の為の別方法が記載されている。そこでは統計的に処理された過去の交通データが、タイムスライスベースの経路探索のために使われる。そして、システムはクライアントサーバ構造に基づいて出発及び目的の場所/時間のあらゆる可能な組み合わせが考慮され、事前計算されたセットデータとして格納される。計算に使われる対応するタイムスライスの計算要求がされると、前記対応データはあらゆる必要情報と共にサーバーから送信される。
【0006】
また、特開2004−301677号公報では統計的に処理された過去の交通データを基にしたタイムスライスベースの経路探索の為の別方法が記載されている。そこでは対応する目的地が決定した後、到達メッシュと出発メッシュの間の距離を用い、特定のメッシュ領域のための基準到達時刻が計算される。そして、特定のメッシュ領域内にあるリンク計算された基準到達時刻を含む時間帯の交通情報統計値を用いて推奨経路を探索する。
【特許文献1】欧州特許出願公開第1496338号明細書
【特許文献2】特開2004−301677号公報
【発明の開示】
【発明が解決しようとする課題】
【0007】
しかしながら、前記特許文献に記載された方法では、以前として計算量が膨大となっており、更に計算後のデータを格納する記憶媒体の容量も多く必要となっていた。従って、経路探索や走行時間の推測等を実施するためにナビゲーションシステムでは高い処理能力が要求されていた。
【0008】
本発明は前記従来における問題点を解消するためになされたものであり、走行時間や到着、通過時刻といった走行関連時間を判断する際に、事前計算や格納データ量を減少させることによって、要求されるシステムの処理能力を低減することを可能にしたナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【0009】
前記目的を達成するため本願の請求項1に係るナビゲーションシステムの走行関連時間判断方法は、車両の出発地点を取得する出発地点取得ステップと、リンクに関するリンク情報と地図情報を互いに隣接するメッシュに分割したメッシュ情報とを取得する地図情報取得ステップ(S3)と、出発地点を含む開始メッシュから特定のメッシュへ進入するリンクの種別及び、又は数に基づくタイムオフセット値を前記特定のメッシュに付与する付与ステップ(S4、S105、S107、S114、S115、S117、S118)と、前記特定のメッシュに付与されたタイムオフセット値に基づいて出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定する走行関連時間測定ステップと(S4)、を有することを特徴とする。
【0010】
また、請求項2に係るナビゲーションシステムの走行関連時間判断方法は、請求項1に記載のナビゲーションシステムの走行関連時間判断方法であって、前記メッシュは互いに隣接する多角形から構成され、その多角形の隣接面をメッシュの境界とすることを特徴とする。
【0011】
また、請求項3に係るナビゲーションシステムの走行関連時間判断方法は、請求項2に記載のナビゲーションシステムの走行関連時間判断方法であって、前記多角形は少なくとも三角形、正方形、矩形、六角形及び八角形の内の一つであることを特徴とする。
【0012】
また、請求項4に係るナビゲーションシステムの走行関連時間判断方法は、請求項1乃至請求項3のいずれかに記載のナビゲーションシステムの走行関連時間判断方法であって、前記開始メッシュからの距離が同距離であって、且つ開始メッシュに対して同じ方角で一直線上に配置される特定のメッシュにそれぞれに同一タイムオフセット値が付与されることを特徴とする。
【0013】
また、請求項5に係るナビゲーションシステムの走行関連時間判断方法は、請求項1乃至請求項3のいずれかに記載のナビゲーションシステムの走行関連時間判断方法であって、前記開始メッシュからの距離が同距離であって、且つ開始メッシュに対して同じ方角で一直線上に配置される特定のメッシュにそれぞれに異なるタイムオフセット値が付与されることを特徴とする。
【0014】
また、請求項6に係るナビゲーションシステムの走行関連時間判断方法は、請求項1乃至請求項5のいずれかに記載のナビゲーションシステムの走行関連時間判断方法であって、前記メッシュのうち特定のメッシュに付与されるタイムオフセット値は、前記特定のメッシュに含まれるリンクの種別に基づいて決定されるタイムオフセット予備値を含むことを特徴とする。
【0015】
また、請求項7に係るナビゲーションシステムの走行関連時間判断方法は、請求項6に記載のナビゲーションシステムの走行関連時間判断方法であって、前記タイムオフセット予備値を含むタイムオフセット値は、特定の種別のリンクからの出口の有無に関するリンク情報に基づいて決定されることを特徴とする。
【0016】
また、請求項8に係るナビゲーションシステムの走行関連時間判断方法は、請求項1乃至請求項7のいずれかに記載のナビゲーションシステムの走行関連時間判断方法であって、前記走行関連時間測定ステップにより測定された推測走行関連時間は、タイムマップを作成するタイムマップ作成ステップ、交通マップを作成する交通マップ作成ステップ、イベントマップを作成するイベントマップ作成ステップ、設定された目的地までの経路を探索する経路探索ステップのいずれかにおいて使用されることを特徴とする。
【0017】
また、請求項9に係るナビゲーションシステムは、車両の出発地点を取得する出発地点取得手段(12)と、リンクに関するリンク情報と地図情報を互いに隣接するメッシュに分割したメッシュ情報とを記憶する記憶手段(3)と、出発地点を含む開始メッシュから特定のメッシュへ進入するリンクの種別及び、又は数に基づくタイムオフセット値を前記特定のメッシュに付与する付与手段(11)と、前記特定のメッシュに付与されたタイムオフセット値に基づいて出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定する走行関連時間測定手段(11)と、を有することを特徴とする。
【0018】
また、請求項10に係るナビゲーションシステムは、請求項9に記載のナビゲーションシステムであって、車両の出発地点から所定の目的地点までの走行経路を探索する経路探索手段を有し、前記経路探索手段は前記走行関連時間測定手段によって測定された推測走行関連時間に基づいて走行経路を探索することを特徴とする。
【0019】
また、請求項11に係るナビゲーションシステムは、請求項9又は請求項10に記載のナビゲーションシステムであって、請求項1乃至請求項8に記載のいずれかのステップを実行することを特徴とする。
【0020】
また、請求項12に係るプログラムは、前記請求項1乃至請求項8に記載のいずれかのステップをコンピュータ上で実行させることを特徴とする。
【発明の効果】
【0021】
前記構成を有する請求項1に係るナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムでは、出発地点を含む開始メッシュから特定のメッシュへ進入するリンクの種別及び、又は数に基づくタイムオフセット値を特定のメッシュに付与し、付与されたタイムオフセット値に基づいて出発地点を含む開始メッシュから特定のメッシュへの推測走行関連時間を測定するので、出発地点が手動で入力されたり、GPSレシーバ等の装置で自動的に探索されれば、目的地が決定されない場合であっても、目的領域への到着時刻の推測が十分に正確に行うことが可能となる。
また、タイムスライスの時間計算によって、設定された目的地までの交通状況を各リンクの走行時刻で推測することが可能となり、目的地への経路探索時に各リンクの走行時刻における交通状況等を考慮した、より最適な経路の選択が可能となる。
【0022】
また、メッシュ間の道路端情報や、メッシュ内にある高速道路の出口の有無といった任意の他の追加情報に基づいて付与される新たなメッシュベースの計算方法の利用により、道路リンクのタイムスライスの計算のために要求される計算量と格納するデータ量が軽減する。その結果、必要となる処理能力が著しく低減される。
また、道路リンクをグループ化もしくは、定義された一範囲(メッシュもしくはメッシュグループ)内で同一区分のリンク間の個々の違いを考慮しないことにより、メッシュ領域内の特定の道路リンクに到着するのに必要な時間を推測することが可能である。その結果、1メッシュ内の、もしくは1メッシュ内にある同一区分のすべての道路リンクは、経路探索もしくは到着時刻の推測といったその他のアプリケーションの為に同一のタイムオフセット(もしくはタイムスライス)を有することになる。従って、個々のリンクについてタイムスライスを計算する必要がなくなる。
【0023】
本発明の概念において、データベースに格納される地図情報は、決まった大きさの複数の矩形からなるメッシュへの分割されている。言い換えれば、従来のデータベースに含まれる道路リンクはメッシュ構造によって管理される。そして、メッシュ毎に管理されたデータベースに基づいてメッシュの端や、その端(隣接するメッシュ間の境界線)を横断するリンク(道路)を特定する。更に、オフセット“0”を有するメッシュ(出発地点を有するメッシュ)との比較により、すべてのメッシュのオフセットが決定する。
【0024】
尚、各メッシュに単独のオフセットを付与すること、若しくは1メッシュに含まれるリンク(道路)種別により複数のオフセットを付与することについても可能である。
【発明を実施するための最良の形態】
【0025】
以下、本発明に係るナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムについて具体化した一実施形態に基づき図面を参照しつつ詳細に説明する。
【0026】
図1は本実施形態に係るナビゲーションシステム1の概略図である。図1に示すように本実施形態に係るナビゲーションシステム1はナビゲーション装置2とデータベース3とから基本的に構成されている。
【0027】
本実施形態にかかるナビゲーション装置2は、自動車等の車両に対して載置される車載機であり、タイムスライス計算モジュール(付与手段、走行関連時間測定手段)11、GPS受信部等の位置検索モジュール(出発地点取得手段)12、経路探索モジュール(経路探索手段)13、地図描画モジュール14、送受信モジュール15、出入力モジュール16、記憶モジュール(記憶手段)17、その他のアプリケーションモジュール18等の複数の機能装置を備えている。
【0028】
また、本実施形態に係るデータベース3は道路地図データベース21、交通データベース22、イベントデータベース23、その他の地理情報データベース24等を有するデータベース3へ接続している。
【0029】
ここで、道路地図データベース21は従来の方法で、リンクデータ、ノートデータ等の道路地図データを有するデータベースであり、また道路地図データをメッシュに分割したメッシュ情報を有する。
尚、メッシュは、隣接するメッシュ間の境界(境界線)を明確にする矩形やその他の多角形を有することが可能な定常のメッシュから構成されることが望ましい。具体的に望ましい実施形態としては、メッシュは矩形、できれば決まった大きさの正方形が望ましい。しかしながら、三角形、六角形、その他の多角形を有するメッシュも用いることができる。以下の実施形態の説明では、メッシュは便宜上同じ大きさの正方形メッシュから成るメッシュを意味する。
【0030】
また、交通データベース22は統計処理された過去の交通データ等の予測交通状況に関する情報を格納するデータベースである。イベントデータベース23はコンサートホールにおけるコンサート、競技場におけるサッカーの試合等の道路リンクに関連した時間関連イベント情報を格納するデータベースである。
【0031】
尚、データベース3は完全にもしくは部分的にナビゲーション装置2内、例えば記憶モジュール17に格納することができる。または、データベース3の一部もしくは全体が外部記憶装置(例えばハードディスクドライブやフラッシュメモリ等)に格納され、送受信モジュール15を通してアクセスできるように構成することが考えられる。
【0032】
また、ナビゲーション装置2は、メッシュベースの計算を用い、走行時間、到着時刻、通過時刻等の走行関連時間を決定できるように、メッシュ情報を有する道路地図データベースを少なくとも有することが望ましい。
【0033】
また、タイムスライス計算モジュール11は位置検索モジュール12によって判断される自動車等の車両位置、若しくはヒューマン・マシン・インターフェイス等を介してユーザが入力したその他の位置を基に車両の出発位置を特定し、後述されるようなタイムスライス計算を実施する。
【0034】
そして、タイムスライス計算モジュール11によって実施されたタイムスライス計算の結果は、経路検索モジュール13、地図描画モジュール14、その他のモジュール等によるその後の処理において用いることができる。
具体的には、経路検索モジュール13はタイムスライス計算の結果に基づいて、車両の出発位置から入力された目的地までの経路を構成する各リンクについて、そのリンクの走行時点での交通状況(例えば、渋滞情報や通行規制情報等)を取得する。そして、取得した交通状況を考慮して目的地までの経路のコストを計算し、最適な経路を選択する。
【0035】
次に図2及び図3に従って、データベース3に格納されている情報を用いて実行されるナビゲーション装置2の制御処理について説明する。
【0036】
図2に示すように、ナビゲーションシステム1の動作開始後には、先ず自車の出発位置と対応する計算の為の出発時刻がステップ(以下Sと略す)1、S2において取得される。続いて、S3においてメッシュ情報が道路地図データベース21から取得される。尚、アプリケーションが出発時刻を考慮しないのであれば、S2は必要ない。
【0037】
次に、S4においては開始メッシュから特定のメッシュへの推測走行関連時間等を計測するタイムスライス計算処理が、後述される方法でタイムスライス計算モジュール11によって実行される。そして、S4のタイムスライス計算の結果はS5におけるタイムマップの展開(生成)処理に用いられる。そして、S5ではユーザの操作情報に基づいて生成されたタイムマップの出力指示があるか否かが判定され、出力指示があると判定された場合(S6:YES)には、S7において出入力モジュール16に含まれるディスプレイ等の表示部にタイムマップが出力される。一方、出力指示がないと判定された場合(S6:NO)には、S8へと移行する。
【0038】
尚、図10は前記S7におけるタイムマップの出力の一例を示した図である。そして、タイムマップの出力(S7)がユーザの意図された処理の最終結果であったならば、処理フローはS7から終了に進む。そうでない場合、若しくはS5及びS7に代わり、より精密なアプリケーションが実行される場合には、S4のタイムスライス計算の結果は以下に詳載されているようにS9において交通マップやイベントマップの生成に用いられる。
また、S8では交通データベース22や前記イベントデータベース23において交通データやその他の時間関連イベントデータが検索及び取得され、取得された交通データやその他の時間関連イベントデータ、及びS4のタイムスライス計算の結果に基づいて、S9で交通マップやイベントマップの生成が行われる。
【0039】
次に、S10ではユーザの操作情報に基づいて生成された交通マップやイベントマップの出力指示があるか否かが判定され、出力指示があると判定された場合(S10:YES)には、S11において出入力モジュール16に含まれるディスプレイ等の表示部に交通マップやイベントマップが出力される。一方、出力指示がないと判定された場合(S10:NO)には、図3のS12へと移行する。
【0040】
尚、タイムマップ、交通マップ及びイベントマップでは、到着、通過時刻(例えば9:00、9:10等)の代わりに走行時間(例えば15分等)を表示することもできる。加えて、S6、S7及び、もしくはS10、S11に加えて、S4のタイムスライス計算によって取得したデータは図3に示されているように、経路探索やその他のアプリケーションに用いることもできる。
【0041】
続いて、S13ではナビゲーション装置2において目的地が設定されているか否かが判定される。そして、目的地が設定されていると判定された場合(S13:YES)には、目的地に関するデータがS14においてデータベース3から取得される。一方、目的地が設定されていないと判定された場合(S13:NO)には処理を終了する。
【0042】
次に、S15において、最適経路検索やその他のアプリケーションの処理が実行される。具体的に、経路探索処理では、前述の各S1〜S9で取得された自車の出発地点情報、メッシュ情報、交通データやその他の時間関連イベントデータ、及び前記S4のタイムスライス計算の結果に基づいて、車両の出発位置から入力された目的地までの経路を構成する各リンクについて、そのリンクの走行時点での交通状況(例えば、渋滞情報や通行規制情報等)を取得する。そして、取得した交通状況を考慮して目的地までの経路のコストを計算し、最適な経路を選択する。
【0043】
次に、S16ではユーザの操作情報に基づいて探索された経路の出力指示があるか否かが判定され、出力指示があると判定された場合(S16:YES)には、S17において出入力モジュール16に含まれるディスプレイ等の表示部やスピーカを用いて探索された最適な経路(誘導経路)や誘導経路に従った走行の案内が出力される。一方、出力指示がないと判定された場合(S16:NO)には、S20へと移行する。
【0044】
更に、S21では、任意で更新された位置、時間データを基に経路のタイムスライスの動的な更新処理と、更新されたタイムススライスの計算結果に基づく再度の経路探索が行われる。そして、S19においては、前記S18で探索された新たな誘導経路や誘導経路に従った走行の案内がディスプレイ等の表示部やスピーカを用いて出力される。尚、S18における誘導経路の動的な更新処理やS19における再経路の出力処理は従来のタイムスライス技術もしくは、S4における更新されたタイムスライス計算の結果を用いて周知の技術により実施される。
【0045】
次に、図4を用いて前記S4におけるタイムスライスのメッシュベースに基づく計算の一例を説明する。図4はメッシュyyyxxx00、yyyxxx01、yyyxxx02と称される3つの隣接する正方形メッシュを示す。メッシュyyyxxx00は車両の出発点を含むメッシュであり、これ以降、開始メッシュと称する。尚、メッシュ(間)は境界線によって分けられる。また、図4では簡易な例を示しており、1メッシュから隣のメッシュへの移動は1方向のみと考えるものとする。従って、メッシュyyyxxx02へ移動する際にはメッシュyyyxxx01を通過して移動するものとする。
【0046】
ここで、図4に示すように開始メッシュyyyxxx00にはタイムオフセット値として0が付与される。
一方、開始メッシュyyyxxx00の隣のメッシュyyyxxx01には特定のオフセット値としてオフセット値0.25が付与される。タイムオフセット値0.25は時間基準(本実施形態においては1時間)によって積される数値であり、メッシュyyyxxx01のオフセット時間は0.25×60分=15分となる。
そして、メッシュyyyxxx01の更に隣のメッシュyyyxxx02には特定のオフセット値、オフセット値0.5が付与される。従って、例えば1時間の時間基準と考えると30分がオフセット時間となる。
【0047】
次に、オフセット値がどのように算出されるかを説明する前に、図4において示されている道路(リンク)の区分について説明する。メッシュyyyxxx00内の出発点0からノードNA、NB,NC、NDを通過し、目的地Dまでの道路(リンク)は道路種別及びオフセット種別がHとなる高速(走行)が認められた幹線道路や高速道路といった上級リンクである。また、ノードNAから境界地点BBを通過し、ノードNCまでの道路(リンク)は道路種別及びオフセット種別がMとなる中級リンクとみなされる。ノードNCを迂回するノードNBとNDを結ぶ道路(リンク)は道路種別及びオフセット種別がLの下級リンクである。
【0048】
そして、本実施形態では以下に説明するようにオフセット種別Hのオフセット予備値を0.25、オフセット種別Mのオフセット予備値を0.4、オフセット種別Lのオフセット予備値を0.7として、メッシュのオフセット値を決定する。
【0049】
メッシュベース計算の最も簡易な実施形態として本実施形態では、移動方向にあるメッシュに進入する道路の種別に基づく可能な最小オフセット値であるオフセット値を各メッシュに付与する。例えば図4の場合、移動方向は出発点0から目的地Dへの方向となる。従って、図4に示すようにメッシュyyyxxx00とメッシュyyyxxx01間の境界線において、境界線横断地点BAにおける種別Hリンクと境界線横断地点BBにおける種別Mリンクと称される、境界線を横断する2つのリンクが存在する場合には、メッシュ(例えばメッシュ内のすべてのリンク)は道路種別Hのオフセット値、例えばオフセット値0.25に決定される。
【0050】
また、図4に示すようにメッシュyyyxxx01とメッシュyyyxxx02間の境界線においては、リンク種別Hと称される1リンク(道路)のみがメッシュyyyxxx01とメッシュyyyxxx02間の境界線を横断する為、その前のメッシュメッシュyyyxxx01に対する相対的なオフセットのみが考慮されるのであれば、メッシュyyyxxx02はオフセット値0.25に決定される。但し、本実施形態では出発地点に基づく走行時間の推測を目的としている為、メッシュのオフセット値は以下の式(1)に従って算出される。
メッシュに付与されるオフセット=その上流メッシュのオフセット値+その上流メッシュからの相対的なオフセット値・・・(1)
【0051】
従って、図4に示す例では、メッシュyyyxxx02のオフセット値=その上流メッシュyyyxxx01のオフセット(=0.25)+その上流メッシュからの相対的なオフセット値(=0.25)=0.5となる。
【0052】
また、仮にノードNDと目的地D間のリンクを(リンク種別Hの代わりに)リンク種別Lと想定すると、メッシュyyyxxx02のオフセット値=0.95(0.25+0.7)となる。
【0053】
上記方法の変形例について図5を用いて説明する。図5は、メッシュXとその隣接メッシュYを示す。本変形例で考慮される移動方向は境界線B1から境界線B2を経て、境界線B3へと向かうものである。境界線横断地点BAから境界線横断地点BBを経て、境界線横断地点BCまでのリンクは種別Hリンクである。ノードNAは、種別Hのこのリンクから種別Mのリンクへの出口である。
【0054】
ここで、図4に従って説明した第一方法では、前記S4のタイムスライス計算において、1メッシュ内のすべてのリンクが一括して考慮され、そのメッシュは単一のオフセット値を受理する。従って、1メッシュのすべてのリンクに対し唯一の共通のオフセットが存在することとなる。
【0055】
しかしながら実際は、通常、1メッシュ内においてもその道路網には種々な異なるリンクが存在する。そのような差異を考慮することにより、前記メッシュベース計算の正確性が改良される。
【0056】
図5に示す変形例においては、特定の境界線を経て進入する道路種別に加え、メッシュ内の異なる種別のリンクの接続が考慮される。ここで、本目的の為に用いられる基本情報は、上級リンクである種別Hリンクからの出口の利用の可能性と任意でその数である。
【0057】
図5に示されている例において、メッシュXはノードNAと称される上級リンク出口を含んでいる。
【0058】
図5に従って説明される変形例においては、次に図6及び図7で説明されるように、メッシュ内に含まれる異なる種別のリンクに対して、1メッシュは異なるオフセット値を3つまで受理する。ここで、図6及び図7はタイムスライス計算(図2のS4)のサブ処理について説明したフローチャートである。
【0059】
図6に示すように、タイムスライス計算(図2のS4)は、先ずS101において開始メッシュを判定する。その後、S102において隣接メッシュもしくはメッシュグループが決定される。尚、それぞれの具体例については後に説明する。その後、S103において、前記S102で決定されたメッシュもしくはメッシュグループのうちの1つがタイムスライス計算を実施する為に選択される。
【0060】
その後、S104において、異なるリンク種別H(上級)、M(中級)、L(下級)のそれぞれに対して、メッシュの境界線を通って進入するリンク(道路)の数が決定される。例えば、図5に示すメッシュXは境界線B1を考えた場合、地点BAで境界線を横断する種別Hの進入リンクを1つと地点BDで境界線を横断する種別Mの進入リンク1つを有する。メッシュYは、境界線B2を考えた場合、地点BBで境界線を横断する種別Hの進入リンクを1つ、地点BEで境界線を横断する種別Mの進入リンクを1つ、そして地点BFで境界線を横断する種別Lの進入リンクを1つ有する。
【0061】
次にS105において、前記S103で選択されたメッシュもしくはメッシュグループ内にある対応する上級リンクに、種別Hの上級リンクに対応するオフセット値が付与される。
【0062】
更に、S106において、ノードNA等の上級リンクの出口がメッシュもしくはメッシュグループ内に存在するかどうかを確認する。例えば、図5に示すメッシュXには上級リンク出口が1つあるが、メッシュYには上級リンク出口はない。また、ステップS107において、メッシュもしくはメッシュグループ内にある種別MとLのリンクにオフセット値が付与される。
【0063】
そして、S108では前記S103においてまだ選択されていないメッシュもしくはメッシュグループがあるか否か判定される。その結果、選択されていないメッシュもしくはメッシュグループがあると判定された場合(S108:YES)にはS103へと戻り、残りのメッシュ若しくはメッシュグループから次のメッシュ若しくはメッシュグループが選択される。一方、全てのメッシュもしくはメッシュグループが選択済であると判定された場合(S108:NO)にはタイムスライス計算(図2のS4)のサブ処理を終了し、S5へ戻る。
【0064】
次に、図7を用いてステップS104〜S107までの変形例について説明する。尚、図7から分かるように、取得と付与の処理順序はステップS104〜S107における順序と完全に同じではない。それは、対応するステップは存在するが完全に対応する順序で行う必要はないからである。
【0065】
先ず、S111において特定のメッシュ境界線における種別Hの進入リンクの数が取得される。そして、S112では種別Hの進入リンクの数が少なくとも1以上あるか否か判定される。その結果、種別Hの進入リンクの数が少なくとも1以上あると判定された場合(S112:YES)には、S113において、メッシュグループのメッシュ内における種別Hのリンクからの出口が在るか否か判定される。
【0066】
そして、対応するメッシュ内に種別Hのリンクからの出口が存在すると判定された場合(S113:YES)には、S114において、対応するメッシュ内の(種別H、M、Lの)すべてのリンクに種別Hのオフセット(上記例においては0.25)が付与され、S108へと移行する。
【0067】
一方、対応するメッシュ内に種別Hのリンクからの出口が存在しないと判定された場合(S113:NO)には、S115において対応するメッシュ内の種別Hのリンクにのみ種別Hのオフセットが付与され、S116に進む。
【0068】
また、前記S112で種別Hの進入リンクの数が存在しないと判定された場合(S112:NO)には、S116において、種別Mの進入リンクの数が少なくとも1以上在るか否か判定される。その結果、種別Mの進入リンクの数が少なくとも1以上あると判定された場合(S116:YES)には、S117において、対応するメッシュ内のすべてのリンクに種別Mのオフセットが付与される(但し、S115を経由した場合においては残るすべてのリンクに種別Mのオフセットが付与される)。その後、S108へと移行する。
【0069】
一方、種別Mの進入リンクの数が存在しないと判定された場合(S116:YES)には、すべてのリンク、もしくは残るすべてのリンクに種別Lのオフセットが付与される。その後、S108へと移行する。
【0070】
尚、すでに記載したように図7において示される実施形態は単なる一例にすぎない。また、種別Hのリンクからの出口の数もしくは種別Mのリンクからの出口の有無やその数が考慮されうる。また、図6及び図7は異なる種別のリンク間を接続するノードの有無を考慮することができることを根本的に示唆するものである。
【0071】
即ち、種別Hのリンクを経てメッシュXへ進入した時、あたかもメッシュXにおける全走行が種別Mもしくは種別L上においてのみ実施されたかのようであるが、ノードNAと境界線の横断地点BEとを接続する種別Mのリンク上の全走行速度が(上記状況)より高速である等の事実を反映させることができる。一方、メッシュYにおいて、境界線横断地点BBを経てメッシュYへ進入した場合、種別MもしくはLのリンクへ変更する可能性はない。従って、これらのリンクは種別Hのリンク上におけるより高速な走行速度の恩恵を受けることができない。
【0072】
上記変形例においては、同じメッシュ内の異なる種別のリンクに異なるオフセットが付与されうる。異なる種別のリンクに対する異なるオフセットの付与は出口の有無等の考慮に限定されるものではない。当然、同じメッシュ内の異なる種別のリンクへの異なるオフセットの付与は出口の有無等を考慮せずとも可能である。
【0073】
次にメッシュのオフセット値を算出するためのフローパターンについて、図8を用いて説明する。図8に従って説明される例はステップS103において実施される隣接メッシュもしくはメッシュグループの選択に関する2例のうちの1例である。
図8は8×8メッシュ、例えば64メッシュのマトリクスから成るメッシュを示す。S1において取得される出発地点はメッシュ33に位置する。メッシュは正方形である。従って各メッシュは正方形の隣接面によって表される隣接メッシュとの4つの境界線を有する。図8から、出発地点を含む開始メッシュ33は4つの境界線を有し、その4つの境界線を横断する退出リンクだけが存在することは明らかである。そして、開始メッシュ33にはタイムオフセット0が付与される。また、以下で開始メッシュ、もしくは出発地点周辺の扱いの方法については種々あるが、当面の間は開始メッシュのタイムオフセットは0のみと考える。
【0074】
図8において示されるフローパターンは以下の規則に従って、開始メッシュからのメッシュの距離の増加を示す。
a)各メッシュ(開始メッシュを除く)はリンクが境界線を横断すると考えられる境界線を2つのみ有する。
b)1メッシュ内に進入リンクが存在するならば、横断する進入リンクを有する境界線の反対側の境界線が退出リンクを有する境界線であると判断される。
c)進入リンクを有さないメッシュ(開始メッシュと対角線上で交差するメッシュ)において退出リンクを有する境界線は、退出リンクを有する隣接メッシュの境界線に連続する境界線となるよう選択される。
【0075】
従って、図8において矢印によって示されるフローパターンは増加する距離のフローパターンを示す移動順序で1つのメッシュから隣接するメッシュへの移動を示す。進入リンクを有さない上記メッシュ(開始メッシュ33と対角線上で交差する位置にあるすべての「コーナーメッシュ」00,11,22,44,55,66,77,06,15,24,42,51,60)に関して上記メッシュは考慮すべき進入リンクを有さず、マトリクスの同じ列もしくは行の2つの「コーナーメッシュ」間に位置するメッシュと開始メッシュからの距離が同じであると考えなければならない。従って、上記「コーナーメッシュ」もフローパターンにおいて開始メッシュからの増加距離を示すメッシュである。
【0076】
そして、各メッシュへのオフセット値の付与は前記S4において説明された計算に基づき実施される。
【0077】
当然この場合、「コーナーメッシュ」の(オフセット値の付与の)為の解決方法が必要となる。なぜなら、これら「コーナーメッシュ」は進入メッシュを有さない為、上流メッシュや進入リンクに基づくオフセット値の計算が不可能だからである。
【0078】
ここで、「コーナーメッシュ」へのオフセット値付与の望ましい付与方法はフローパターンにおける同距離の隣接メッシュのうち低い方の値の付与である。例えば、コーナーメッシュ42の場合、メッシュ32と43のメッシュ値のうち低い値である。
【0079】
図8において示されるフローパターンに基づくオフセット値の付与の特殊な変形例は開始メッシュからの距離が同レベルで、開始メッシュに対して同じ方角(北側、西側、南側、東側)に配列されたすべてのメッシュに同じ値を付与することである。この同じ値は、同距離レベルで同じ方角に配列されたメッシュのすべてのメッシュ値のうち最も低い値であることが望ましい。一例として、メッシュ25、35、45、は(フローパターンでは同じ網かけによって示される)距離が同レベルで同じ方角(東側)に配列されている。
例えば、メッシュ25のオフセット値を0.8、メッシュ35のオフセット値を1.4、メッシュ45のオフセット値を0.65と想定すると、最も低い値(メッシュ45の0.65)がメッシュ23、35、45の各々に付与される。同様にフローパターンにおいて北側の距離が同レベルにあるメッシュ、例えばメッシュ52、53、54も同じオフセット値を有する。そのオフセット値を0.5と想定すると、2つの利用可能なメッシュ値のうち低い値(0.5)がコーナーメッシュ55に付与される。従って図8において示されるフローパターンは以下の追加規則を有する。
d)特定の選択規則に従い、開始メッシュに対して同じ方角で同距離レベルに位置するすべてのメッシュに、これらメッシュの最も高い値、最も低い値、もしくはその平均値等のうちの1つの値を付与する。
e)上記d)における同じ規則に従い、同距離レベルの隣接メッシュのオフセット値から選択されるオフセット値をコーナーメッシュに付与する。
【0080】
尚、変形例として図8に示されるフローパターンにおいて、リンク種別やメッシュ内の出口の数等を反映させて、1メッシュ内にある異なる種別のリンクに異なるオフセット値を付与することは当然可能である。また別の例としては、S103におけるグループ選択の後、グループ内のメッシュにオフセットを付与する為に各メッシュの進入リンクの数の代わりに、グループ内のすべてのメッシュに対する進入リンクの数が考慮される。
【0081】
次に、S103の隣接メッシュ、もしくはメッシュグループの選択の別例について図9を用いて説明する。図8とは異なり、図9においては、隣接メッシュ間の各境界線は進入もしくは退出リンクを有する境界線と考えられる。そのため、図8に示されているフローパターンにあるような「コーナーメッシュ」は存在しない。尚、図9に示されるフローパターンも開始メッシュからの増加距離を示すフローパターンであり、その増加距離は開始メッシュから出発する矢印によって横断される境界線の数によって表される。
【0082】
従って、図9に示すフローパターンではメッシュ23、32、34、43は開始メッシュ33からの距離が同レベルにあり、メッシュ13,22,24,31,35,42,44,53は開始メッシュからの距離が次のレベルにあり、メッシュ03,12,14,21,25,30,36,41,45,52,54,63はさらにその次の距離レベルにあるというように続いていく。
【0083】
図9に示されているフローパターンにおいては、S4に関して説明されているのと同様のオフセット値を算出、付与するための処理が用いられる。各メッシュに個別オフセット値を付与することが望ましいが、距離レベル等に応じて同じメッシュ値を付与することも可能である。
【0084】
図8及び図9において、S103の隣接メッシュもしくはメッシュグループの決定とステップS104の次のメッシュもしくはメッシュグループの選択は以下のように考えられる。
図8において、各メッシュが個別の値を受理するならば、隣接メッシュもしくはメッシュグループの決定はフロー手順で実施されることが望ましい。つまりまず、メッシュ33,34はグループ化され、もしくは流れが同一方向であるすべてのメッシュ、つまりまずメッシュ33,43、メッシュ33,34、メッシュ33,23、メッシュ33,32がグループ化され対応するオフセット値が算出される。次に、コーナーメッシュ22,24,42,44のメッシュ値が算出される。引き続き、メッシュ22,12、メッシュ23,13、メッシュ24,14、メッシュ24,25、メッシュ34,35等がグループ化され対応するオフセット値が算出、付与される。その後、コーナーメッシュ11,15,51,55のオフセット値が算出され、この論理に従って処理が続いていく。
【0085】
一方、図9において、S103の選択は同様に実施される。つまり、まずメッシュ33,23、メッシュ33,34、メッシュ33,43、メッシュ33,32がグループ化され対応するオフセット値が算出、付与される。次にグループ決定がすでに事前に実施されているかどうかを判断し、メッシュ23,22、メッシュ23,13、メッシュ23,24、メッシュ32,22、メッシュ31,21、メッシュ32,42、メッシュ34,24、メッシュ34,35、メッシュ34,44、メッシュ43,42、メッシュ43,53、メッシュ43,44等のメッシュグループが算出、付与される。メッシュ毎の単一オフセット値もしくは上述されているような出口の数等の他の要素を考慮する可能性を有する異なる種別リンクの複数のオフセット値がオフセット値を算出、付与する際に用いられる。開始メッシュと開始メッシュと共有の境界線を有するメッシュ(23,32,34,43)を除く各メッシュは進入リンクを有する2つの境界線を有する。従って、(各メッシュに)1つのオフセット値、もしくはメッシュ内の特定種別リンクに1つのオフセット値を付与することができるように、どの値が選択されるべきかという規則を確定する必要があることは明らかである。これは、例えば2つの境界線のオフセット値のうちの低い値を付与することによって実施されうるが、高い値や平均値、他の規則によって決定される値であってもよい。
【0086】
開始メッシュもしくは出発地点の周辺範囲に関しては、距離が限定されたり、道路網への接続が限られたりする為、リンク(道路)種別の違いを考慮する必要がない可能性がある。従って、上記方法の変形例としては、進入リンクの数や種別を考慮せずに、開始メッシュ周辺の複数のメッシュから構成されうる周辺範囲に、単一オフセットが付与される。図11はそのような変形例を簡素な方法で示している。
【0087】
他の変形例としては、オフセット計算はリンク種別を用いる際に、ユーザの好みを考慮する。例えば、ユーザが例えば種別Hのリンクである幹線道路や高速道路を用いることを好んだり、最短経路を用いることを好んだりした場合は、それをメッシュオフセット値の計算の考慮に入れることも可能である。
【0088】
例えば、ユーザが例えば種別Hのリンクである幹線道路や高速道路を用いることを好んだ場合、対応する種別のリンクに対して選択されるオフセット値は上述の標準オフセット値と比較して減少する。また、可能であれば他のリンク種別を単に無視することもできる。
【0089】
また、ユーザが最短経路を望むならば、図12に示す方法も可能である。先ず、出発地点を含む開始メッシュ(出発メッシュ)と目的地を含むメッシュ(ターゲットメッシュ)間の直線、例えばその2つのメッシュの中心を結ぶ直線、もしくは出発地点と目的地を結ぶ直線等を引く。ここで、図14の例に示されているように、ターゲットメッシュのオフセット値の算出の為に、メッシュAとメッシュBの2つのオフセット値のうちのどちらが選択されるが決定されなければならない。尚、ユーザは最短経路を望んでいるので、メッシュBのオフセット値の方が小さくても、この直線はメッシュAを横断している為、メッシュAの値が選択される。
【0090】
また、前記S10、S11で説明したように、交通マップおよび、もしくはイベントマップは例えば、対応経路の色分け等による交通予測や、表示された地図上に配置された所定のアイコンによって表示される(サッカーの試合、休日の交通の流れ等の)時間関連情報等を含む。従って、ユーザがT1時刻にA地点を出発し、T2時刻のコンサートに間に合うようB地点にいたいならば、X道路を使用した場合、サッカーの試合の為、C地点で交通渋滞が生じるであろうとユーザが理解できる。これにより、ユーザが経路探索機能を使わずに自分の時間スケジュールを立てたり決定しやすくなる。
【0091】
尚、上述した明細書および、もしくは請求項に開示されているすべての特徴は実施例および、もしくは請求項の特徴の構成から独立して請求されている発明の制限とともに、出願時の開示を目的として、別々に互いに独立したものとして開示されるよう意図されていることを明記している。また、すべての値の範疇および、もしくは構成要素のグループ化の指定は、請求されている発明の制限、特に値の範疇の制限とともに、出願時の開示を目的としてあらゆる可能な中間値や中間構成要素の開示を明記している。
【図面の簡単な説明】
【0092】
【図1】本実施形態に係るナビゲーションシステムの構成を示す概略ブロック図である。
【図2】本実施形態に係るナビゲーション装置の制御処理を示すフローチャートである。
【図3】本実施形態に係るナビゲーション装置の制御処理を示すフローチャートである。
【図4】本発明の単純な変形例を示す図である。
【図5】図4で示した変形例を説明する2つの隣接するメッシュを示す図である。
【図6】本実施形態に係るナビゲーション装置のオフセット付与の処理を示すフローチャートである。
【図7】本実施形態に係るナビゲーション装置のオフセット付与の処理の変形例を示すフローチャートである。
【図8】メッシュグループへのオフセット付与の例を示した図である。
【図9】各メッシュへの個別のオフセット付与の例を示した図である。
【図10】図2のS7におけるタイムマップ出力の例を示した図である。
【図11】出発地点周辺地域を個別に処理するための変形例を示した図である。
【図12】短距離経路探索の例を示す図である。
【図13】ある特定の一リンクの走行時間の例を示す図である。
【図14】最適経路探索の為の従来のタイムスライス方法を示す図である。
【符号の説明】
【0093】
1 ナビゲーションシステム
2 ナビゲーション装置
3 データベース
11 タイムスライス計算モジュール
12 位置検索モジュール
13 経路探索モジュール
14 地図描画モジュール
15 送受信モジュール
16 出入力モジュール
17 記憶モジュール
21 道路地図データベース
22 交通データベース
23 イベントデータベース
24 その他の地理情報データベース
【特許請求の範囲】
【請求項1】
車両の出発地点を取得する出発地点取得ステップと、
リンクに関するリンク情報と地図情報を互いに隣接するメッシュに分割したメッシュ情報とを取得する地図情報取得ステップと、
出発地点を含む開始メッシュから特定のメッシュへ進入するリンクの種別及び、又は数に基づくタイムオフセット値を前記特定のメッシュに付与する付与ステップと、
前記特定のメッシュに付与されたタイムオフセット値に基づいて出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定する走行関連時間測定ステップと、を有することを特徴とするナビゲーションシステムの走行関連時間判断方法。
【請求項2】
前記メッシュは互いに隣接する多角形から構成され、その多角形の隣接面をメッシュの境界とすることを特徴とする請求項1に記載のナビゲーションシステムの走行関連時間判断方法。
【請求項3】
前記多角形は少なくとも三角形、正方形、矩形、六角形及び八角形の内の一つであることを特徴とする請求項2に記載のナビゲーションシステムの走行関連時間判断方法。
【請求項4】
前記開始メッシュからの距離が同距離であって、且つ開始メッシュに対して同じ方角で一直線上に配置される特定のメッシュにそれぞれに同一タイムオフセット値が付与されることを特徴とする請求項1乃至請求項3のいずれかに記載のナビゲーションシステムの走行関連時間判断方法。
【請求項5】
前記開始メッシュからの距離が同距離であって、且つ開始メッシュに対して同じ方角で一直線上に配置される特定のメッシュにそれぞれに異なるタイムオフセット値が付与されることを特徴とする請求項1乃至請求項3のいずれかに記載のナビゲーションシステムの走行関連時間判断方法。
【請求項6】
前記メッシュのうち特定のメッシュに付与されるタイムオフセット値は、前記特定のメッシュに含まれるリンクの種別に基づいて決定されるタイムオフセット予備値を含むことを特徴とする請求項1乃至請求項5のいずれかに記載のナビゲーションシステムの走行関連時間判断方法。
【請求項7】
前記タイムオフセット予備値を含むタイムオフセット値は、特定の種別のリンクからの出口の有無に関するリンク情報に基づいて決定されることを特徴とする請求項6に記載のナビゲーションシステムの走行関連時間判断方法。
【請求項8】
前記走行関連時間測定ステップにより測定された推測走行関連時間は、
タイムマップを作成するタイムマップ作成ステップ、
交通マップを作成する交通マップ作成ステップ、
イベントマップを作成するイベントマップ作成ステップ、
設定された目的地までの経路を探索する経路探索ステップのいずれかにおいて使用されることを特徴とする請求項1乃至請求項7のいずれかに記載のナビゲーションシステムの走行関連時間判断方法。
【請求項9】
車両の出発地点を取得する出発地点取得手段と、
リンクに関するリンク情報と地図情報を互いに隣接するメッシュに分割したメッシュ情報とを記憶する記憶手段と、
出発地点を含む開始メッシュから特定のメッシュへ進入するリンクの種別及び、又は数に基づくタイムオフセット値を前記特定のメッシュに付与する付与手段と、
前記特定のメッシュに付与されたタイムオフセット値に基づいて出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定する走行関連時間測定手段と、を有することを特徴とするナビゲーションシステム。
【請求項10】
車両の出発地点から所定の目的地点までの走行経路を探索する経路探索手段を有し、
前記経路探索手段は前記走行関連時間測定手段によって測定された推測走行関連時間に基づいて走行経路を探索することを特徴とする請求項9に記載のナビゲーションシステム。
【請求項11】
請求項1乃至請求項8に記載のいずれかのステップを実行する請求項9又は請求項10に記載のナビゲーションシステム。
【請求項12】
請求項1乃至請求項8に記載のいずれかのステップをコンピュータ上で実行させる為のコンピュータプログラム。
【請求項1】
車両の出発地点を取得する出発地点取得ステップと、
リンクに関するリンク情報と地図情報を互いに隣接するメッシュに分割したメッシュ情報とを取得する地図情報取得ステップと、
出発地点を含む開始メッシュから特定のメッシュへ進入するリンクの種別及び、又は数に基づくタイムオフセット値を前記特定のメッシュに付与する付与ステップと、
前記特定のメッシュに付与されたタイムオフセット値に基づいて出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定する走行関連時間測定ステップと、を有することを特徴とするナビゲーションシステムの走行関連時間判断方法。
【請求項2】
前記メッシュは互いに隣接する多角形から構成され、その多角形の隣接面をメッシュの境界とすることを特徴とする請求項1に記載のナビゲーションシステムの走行関連時間判断方法。
【請求項3】
前記多角形は少なくとも三角形、正方形、矩形、六角形及び八角形の内の一つであることを特徴とする請求項2に記載のナビゲーションシステムの走行関連時間判断方法。
【請求項4】
前記開始メッシュからの距離が同距離であって、且つ開始メッシュに対して同じ方角で一直線上に配置される特定のメッシュにそれぞれに同一タイムオフセット値が付与されることを特徴とする請求項1乃至請求項3のいずれかに記載のナビゲーションシステムの走行関連時間判断方法。
【請求項5】
前記開始メッシュからの距離が同距離であって、且つ開始メッシュに対して同じ方角で一直線上に配置される特定のメッシュにそれぞれに異なるタイムオフセット値が付与されることを特徴とする請求項1乃至請求項3のいずれかに記載のナビゲーションシステムの走行関連時間判断方法。
【請求項6】
前記メッシュのうち特定のメッシュに付与されるタイムオフセット値は、前記特定のメッシュに含まれるリンクの種別に基づいて決定されるタイムオフセット予備値を含むことを特徴とする請求項1乃至請求項5のいずれかに記載のナビゲーションシステムの走行関連時間判断方法。
【請求項7】
前記タイムオフセット予備値を含むタイムオフセット値は、特定の種別のリンクからの出口の有無に関するリンク情報に基づいて決定されることを特徴とする請求項6に記載のナビゲーションシステムの走行関連時間判断方法。
【請求項8】
前記走行関連時間測定ステップにより測定された推測走行関連時間は、
タイムマップを作成するタイムマップ作成ステップ、
交通マップを作成する交通マップ作成ステップ、
イベントマップを作成するイベントマップ作成ステップ、
設定された目的地までの経路を探索する経路探索ステップのいずれかにおいて使用されることを特徴とする請求項1乃至請求項7のいずれかに記載のナビゲーションシステムの走行関連時間判断方法。
【請求項9】
車両の出発地点を取得する出発地点取得手段と、
リンクに関するリンク情報と地図情報を互いに隣接するメッシュに分割したメッシュ情報とを記憶する記憶手段と、
出発地点を含む開始メッシュから特定のメッシュへ進入するリンクの種別及び、又は数に基づくタイムオフセット値を前記特定のメッシュに付与する付与手段と、
前記特定のメッシュに付与されたタイムオフセット値に基づいて出発地点を含む開始メッシュから前記特定のメッシュへの推測走行関連時間を測定する走行関連時間測定手段と、を有することを特徴とするナビゲーションシステム。
【請求項10】
車両の出発地点から所定の目的地点までの走行経路を探索する経路探索手段を有し、
前記経路探索手段は前記走行関連時間測定手段によって測定された推測走行関連時間に基づいて走行経路を探索することを特徴とする請求項9に記載のナビゲーションシステム。
【請求項11】
請求項1乃至請求項8に記載のいずれかのステップを実行する請求項9又は請求項10に記載のナビゲーションシステム。
【請求項12】
請求項1乃至請求項8に記載のいずれかのステップをコンピュータ上で実行させる為のコンピュータプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【公開番号】特開2007−52021(P2007−52021A)
【公開日】平成19年3月1日(2007.3.1)
【国際特許分類】
【出願番号】特願2006−219495(P2006−219495)
【出願日】平成18年8月11日(2006.8.11)
【出願人】(000100768)アイシン・エィ・ダブリュ株式会社 (3,717)
【Fターム(参考)】
【公開日】平成19年3月1日(2007.3.1)
【国際特許分類】
【出願日】平成18年8月11日(2006.8.11)
【出願人】(000100768)アイシン・エィ・ダブリュ株式会社 (3,717)
【Fターム(参考)】
[ Back to top ]