(57)【特許請求の範囲】
【請求項１】
車両の出発地点を取得する出発地点取得ステップと、
リンクに関するリンク情報を取得するリンク情報取得ステップと、
地図情報を互いに隣接するメッシュ毎に分割したメッシュ情報を取得する地図情報取得ステップと、
前記メッシュ毎に、出発地点を含む開始メッシュから進入するリンクの種別及び、又は数に基づいて算出されたタイムオフセット値を付与する付与ステップと、
前記メッシュ毎に、該メッシュに付与されたタイムオフセット値に基づいて、該メッシュ領域内の道路リンクに到着する予定の時刻をメッシュ単位で測定する走行関連時間測定ステップと、を有することを特徴とするナビゲーションシステムの走行関連時間判断方法。
【請求項２】
前記付与ステップは、前記開始メッシュ側に隣接するメッシュである上流メッシュに付与された前記タイムオフセット値に、前記上流メッシュから進入するリンクの種別及び、又は数に基づいて算出された相対的なタイムオフセット値を加算した値を、前記タイムオフセット値として付与することを特徴とする請求項１に記載のナビゲーションシステムの走行関連時間判断方法。
【請求項３】
前記開始メッシュからの距離が同距離であって、且つ開始メッシュに対して同じ方角で一直線上に配置される前記メッシュにそれぞれに同一タイムオフセット値が付与されることを特徴とする請求項１又は請求項２に記載のナビゲーションシステムの走行関連時間判断方法。
【請求項４】
前記開始メッシュからの距離が同距離であって、且つ開始メッシュに対して同じ方角で一直線上に配置される前記メッシュにそれぞれに異なるタイムオフセット値が付与されることを特徴とする請求項１乃至請求項３のいずれかに記載のナビゲーションシステムの走行関連時間判断方法。
【請求項５】
前記メッシュに付与されるタイムオフセット値は、前記メッシュに含まれるリンクの種別に基づいて決定されるタイムオフセット予備値を含むことを特徴とする請求項１乃至請求項４のいずれかに記載のナビゲーションシステムの走行関連時間判断方法。
【請求項６】
前記タイムオフセット予備値を含むタイムオフセット値は、特定の種別のリンクからの出口の有無に関するリンク情報に基づいて決定されることを特徴とする請求項５に記載のナビゲーションシステムの走行関連時間判断方法。
【請求項７】
前記走行関連時間測定ステップにより測定された推測走行関連時間は、
タイムマップを作成するタイムマップ作成ステップ、
交通マップを作成する交通マップ作成ステップ、
イベントマップを作成するイベントマップ作成ステップ、
設定された目的地までの経路を探索する経路探索ステップのいずれかにおいて使用されることを特徴とする請求項１乃至請求項６のいずれかに記載のナビゲーションシステムの走行関連時間判断方法。
【請求項８】
車両の出発地点を取得する出発地点取得手段と、
リンクに関するリンク情報と地図情報を互いに隣接するメッシュに分割したメッシュ情報とを記憶する記憶手段と、
前記メッシュ毎に、出発地点を含む開始メッシュから進入するリンクの種別及び、又は数に基づいて算出されたタイムオフセット値を付与する付与手段と、
前記メッシュ毎に、該メッシュに付与されたタイムオフセット値に基づいて、該メッシュ領域内の道路リンクに到着する予定の時刻をメッシュ単位で測定する走行関連時間測定手段と、を有することを特徴とするナビゲーションシステム。
【請求項９】
車両の出発地点から所定の目的地点までの走行経路を探索する経路探索手段を有し、
前記経路探索手段は前記走行関連時間測定手段によって測定された推測走行関連時間に基づいて走行経路を探索することを特徴とする請求項８に記載のナビゲーションシステム。
【請求項１０】
請求項１乃至請求項７に記載のいずれかの方法を実行する請求項８又は請求項９に記載のナビゲーションシステム。
【請求項１１】
請求項１乃至請求項７に記載のいずれかの方法をコンピュータ上で実行させる為のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地点を含む開始メッシュから他のメッシュへの推測走行関連時間を測定するナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムに関するものである。
【背景技術】
【０００２】
従来より、ナビゲーションシステムにおける目的地までの経路を探索する際には、渋滞等の交通状況を考慮して探索が行われていた。しかし、リンクの交通状況は時刻毎によって異なる（例えば、午前中のみ渋滞するリンクもあれば、深夜のみ渋滞するリンクもある）ので、そのリンクを走行する時刻を特定しなければ、正確な交通状況を考慮した経路の探索を行うことができない。そこで、対応する道路ネットワークの各区域やリンクを走行するために必要となる予測時間を提供する走行時間データベースを使用したナビゲーションシステムが知られている。そのような従来のナビゲーションシステムにおいては、探索領域内の各リンクは個々のタイムスライス、例えば、リンクの開始地点への到着時刻に基づいて付与された走行時間（リンクを走行するのに必要な所要時間）を有する。
そして、道路は時刻によって状況が変化するので、当然、個々のタイムスライスはリンクの開始地点への到着時刻によって異なるものとなっている。
【０００３】
例えば、図１３は１日の時刻における、ある一リンクのタイムスライス（リンク走行時間）の一例である。車両又はセンタに設置された走行時間データベースは２４時間又は１週間単位で図１３に示すようなタイムスライスに関するデータを格納する。そして、経路探索の利用等においては、図１４に示すように複数のリンクを順に走行する場合には、車両の走行順で一つ前リンクのタイムスライスが特定されなければ、次のリンクのタイムスライスを特定できない。
【０００４】
しかし、車両の走行可能性のある地図上の全てのリンクについて、個々にタイムスライスを特定することとすると、メモリの容量が不足することとなっていた。また、タイムスライスを特定する処理を行う処理装置の負担が大きくなり、処理に必要な時間も多くなっていた。従って、経路探索や走行時間の推測等を実施するためにナビゲーションシステムでは高い処理能力が要求されていた。
【０００５】
例えば、欧州特許出願公開第１４９６３３８号明細書では経路探索の為の別方法が記載されている。そこでは統計的に処理された過去の交通データが、タイムスライスベースの経路探索のために使われる。そして、システムはクライアントサーバ構造に基づいて出発及び目的の場所／時間のあらゆる可能な組み合わせが考慮され、事前計算されたセットデータとして格納される。計算に使われる対応するタイムスライスの計算要求がされると、前記対応データはあらゆる必要情報と共にサーバーから送信される。
【０００６】
また、特開２００４−３０１６７７号公報では統計的に処理された過去の交通データを基にしたタイムスライスベースの経路探索の為の別方法が記載されている。そこでは対応する目的地が決定した後、到達メッシュと出発メッシュの間の距離を用い、特定のメッシュ領域のための基準到達時刻が計算される。そして、特定のメッシュ領域内にあるリンク計算された基準到達時刻を含む時間帯の交通情報統計値を用いて推奨経路を探索する。
【特許文献１】欧州特許出願公開第１４９６３３８号明細書
【特許文献２】特開２００４−３０１６７７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、前記特許文献に記載された方法では、以前として計算量が膨大となっており、更に計算後のデータを格納する記憶媒体の容量も多く必要となっていた。従って、経路探索や走行時間の推測等を実施するためにナビゲーションシステムでは高い処理能力が要求されていた。
【０００８】
本発明は前記従来における問題点を解消するためになされたものであり、出発地から走行を開始する車両が、周辺の道路リンクに到着する予定の時刻を測定する際に、事前計算や格納データ量を減少させることによって、要求されるシステムの処理能力を低減することを可能にしたナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
前記目的を達成するため本願の請求項１に係るナビゲーションシステムの走行関連時間判断方法は、車両の出発地点を取得する出発地点取得ステップと、リンクに関するリンク情報を取得するリンク情報取得ステップと、地図情報を互いに隣接するメッシュ毎に分割したメッシュ情報を取得する地図情報取得ステップ（Ｓ３）と、前記メッシュ毎に、出発地点を含む開始メッシュから進入するリンクの種別及び、又は数に基づいて算出されたタイムオフセット値を付与する付与ステップ（Ｓ４、Ｓ１０５、Ｓ１０７、Ｓ１１４、Ｓ１１５、Ｓ１１７、Ｓ１１８）と、前記メッシュ毎に、該メッシュに付与されたタイムオフセット値に基づいて、該メッシュ領域内の道路リンクに到着する予定の時刻をメッシュ単位で測定する走行関連時間測定ステップ（Ｓ４）と、を有することを特徴とする。
【００１０】
また、請求項２に係るナビゲーションシステムの走行関連時間判断方法は、請求項１に記載のナビゲーションシステムの走行関連時間判断方法であって、前記付与ステップは、前記開始メッシュ側に隣接するメッシュである上流メッシュに付与された前記タイムオフセット値に、前記上流メッシュから進入するリンクの種別及び、又は数に基づいて算出された相対的なタイムオフセット値を加算した値を、前記タイムオフセット値として付与することを特徴とする。
【００１２】
また、請求項３に係るナビゲーションシステムの走行関連時間判断方法は、請求項１又は請求項２に記載のナビゲーションシステムの走行関連時間判断方法であって、前記開始メッシュからの距離が同距離であって、且つ開始メッシュに対して同じ方角で一直線上に配置される前記メッシュにそれぞれに同一タイムオフセット値が付与されることを特徴とする。
【００１３】
また、請求項４に係るナビゲーションシステムの走行関連時間判断方法は、請求項１乃至請求項３のいずれかに記載のナビゲーションシステムの走行関連時間判断方法であって、前記開始メッシュからの距離が同距離であって、且つ開始メッシュに対して同じ方角で一直線上に配置される前記メッシュにそれぞれに異なるタイムオフセット値が付与されることを特徴とする。
【００１４】
また、請求項５に係るナビゲーションシステムの走行関連時間判断方法は、請求項１乃至請求項４のいずれかに記載のナビゲーションシステムの走行関連時間判断方法であって、前記メッシュに付与されるタイムオフセット値は、前記メッシュに含まれるリンクの種別に基づいて決定されるタイムオフセット予備値を含むことを特徴とする。
【００１５】
また、請求項６に係るナビゲーションシステムの走行関連時間判断方法は、請求項５に記載のナビゲーションシステムの走行関連時間判断方法であって、前記タイムオフセット予備値を含むタイムオフセット値は、特定の種別のリンクからの出口の有無に関するリンク情報に基づいて決定されることを特徴とする。
【００１６】
また、請求項７に係るナビゲーションシステムの走行関連時間判断方法は、請求項１乃至請求項６のいずれかに記載のナビゲーションシステムの走行関連時間判断方法であって、前記走行関連時間測定ステップにより測定された推測走行関連時間は、タイムマップを作成するタイムマップ作成ステップ、交通マップを作成する交通マップ作成ステップ、イベントマップを作成するイベントマップ作成ステップ、設定された目的地までの経路を探索する経路探索ステップのいずれかにおいて使用されることを特徴とする。
【００１７】
また、請求項８に係るナビゲーションシステムは、車両の出発地点を取得する出発地点取得手段（１２）と、リンクに関するリンク情報と地図情報を互いに隣接するメッシュに分割したメッシュ情報とを記憶する記憶手段（３）と、前記メッシュ毎に、出発地点を含む開始メッシュから進入するリンクの種別及び、又は数に基づいて算出されたタイムオフセット値を付与する付与手段（１１）と、前記メッシュ毎に、該メッシュに付与されたタイムオフセット値に基づいて、該メッシュ領域内の道路リンクに到着する予定の時刻をメッシュ単位で測定する走行関連時間測定手段（１１）と、を有することを特徴とする。
【００１８】
また、請求項９に係るナビゲーションシステムは、請求項８に記載のナビゲーションシステムであって、車両の出発地点から所定の目的地点までの走行経路を探索する経路探索手段を有し、前記経路探索手段は前記走行関連時間測定手段によって測定された推測走行関連時間に基づいて走行経路を探索することを特徴とする。
【００１９】
また、請求項１０に係るナビゲーションシステムは、請求項８又は請求項９に記載のナビゲーションシステムであって、請求項１乃至請求項７に記載のいずれかの方法を実行することを特徴とする。
【００２０】
また、請求項１１に係るプログラムは、前記請求項１乃至請求項７に記載のいずれかの方法をコンピュータ上で実行させることを特徴とする。
【発明の効果】
【００２１】
前記構成を有する請求項１に係るナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムでは、メッシュ毎に、出発地点を含む開始メッシュから進入するリンクの種別及び、又は数に基づいて算出されたタイムオフセット値を付与し、メッシュ毎に、該メッシュに付与されたタイムオフセット値に基づいて、該メッシュ領域内の道路リンクに到着する予定の時刻をメッシュ単位で測定するので、出発地点が手動で入力されたり、ＧＰＳレシーバ等の装置で自動的に探索されれば、目的地が決定されない場合であっても、目的領域への到着時刻の推測が十分に正確に行うことが可能となる。
また、タイムスライスの時間計算によって、設定された目的地までの交通状況を各リンクの走行時刻で推測することが可能となり、目的地への経路探索時に各リンクの走行時刻における交通状況等を考慮した、より最適な経路の選択が可能となる。
【００２２】
また、メッシュ間の道路端情報や、メッシュ内にある高速道路の出口の有無といった任意の他の追加情報に基づいて付与される新たなメッシュベースの計算方法の利用により、道路リンクのタイムスライスの計算のために要求される計算量と格納するデータ量が軽減する。その結果、必要となる処理能力が著しく低減される。
また、道路リンクをグループ化もしくは、定義された一範囲（メッシュもしくはメッシュグループ）内で同一区分のリンク間の個々の違いを考慮しないことにより、メッシュ領域内の特定の道路リンクに到着するのに必要な時間を推測することが可能である。その結果、１メッシュ内の、もしくは１メッシュ内にある同一区分のすべての道路リンクは、経路探索もしくは到着時刻の推測といったその他のアプリケーションの為に同一のタイムオフセット（もしくはタイムスライス）を有することになる。従って、個々のリンクについてタイムスライスを計算する必要がなくなる。
【００２３】
本発明の概念において、データベースに格納される地図情報は、決まった大きさの複数の矩形からなるメッシュへの分割されている。言い換えれば、従来のデータベースに含まれる道路リンクはメッシュ構造によって管理される。そして、メッシュ毎に管理されたデータベースに基づいてメッシュの端や、その端（隣接するメッシュ間の境界線）を横断するリンク（道路）を特定する。更に、オフセット“０”を有するメッシュ（出発地点を有するメッシュ）との比較により、すべてのメッシュのオフセットが決定する。
【００２４】
尚、各メッシュに単独のオフセットを付与すること、若しくは1メッシュに含まれるリンク（道路）種別により複数のオフセットを付与することについても可能である。
【発明を実施するための最良の形態】
【００２５】
以下、本発明に係るナビゲーションシステムの走行関連時間判断方法、ナビゲーションシステム及びプログラムについて具体化した一実施形態に基づき図面を参照しつつ詳細に説明する。
【００２６】
図1は本実施形態に係るナビゲーションシステム１の概略図である。図１に示すように本実施形態に係るナビゲーションシステム１はナビゲーション装置２とデータベース３とから基本的に構成されている。
【００２７】
本実施形態にかかるナビゲーション装置２は、自動車等の車両に対して載置される車載機であり、タイムスライス計算モジュール（付与手段、走行関連時間測定手段）１１、ＧＰＳ受信部等の位置検索モジュール（出発地点取得手段）１２、経路探索モジュール（経路探索手段）１３、地図描画モジュール１４、送受信モジュール１５、出入力モジュール１６、記憶モジュール（記憶手段）１７、その他のアプリケーションモジュール１８等の複数の機能装置を備えている。
【００２８】
また、本実施形態に係るデータベース３は道路地図データベース２１、交通データベース２２、イベントデータベース２３、その他の地理情報データベース２４等を有するデータベース３へ接続している。
【００２９】
ここで、道路地図データベース２１は従来の方法で、リンクデータ、ノートデータ等の道路地図データを有するデータベースであり、また道路地図データをメッシュに分割したメッシュ情報を有する。
尚、メッシュは、隣接するメッシュ間の境界（境界線）を明確にする矩形やその他の多角形を有することが可能な定常のメッシュから構成されることが望ましい。具体的に望ましい実施形態としては、メッシュは矩形、できれば決まった大きさの正方形が望ましい。しかしながら、三角形、六角形、その他の多角形を有するメッシュも用いることができる。以下の実施形態の説明では、メッシュは便宜上同じ大きさの正方形メッシュから成るメッシュを意味する。
【００３０】
また、交通データベース２２は統計処理された過去の交通データ等の予測交通状況に関する情報を格納するデータベースである。イベントデータベース２３はコンサートホールにおけるコンサート、競技場におけるサッカーの試合等の道路リンクに関連した時間関連イベント情報を格納するデータベースである。
【００３１】
尚、データベース３は完全にもしくは部分的にナビゲーション装置２内、例えば記憶モジュール１７に格納することができる。または、データベース３の一部もしくは全体が外部記憶装置（例えばハードディスクドライブやフラッシュメモリ等）に格納され、送受信モジュール１５を通してアクセスできるように構成することが考えられる。
【００３２】
また、ナビゲーション装置２は、メッシュベースの計算を用い、走行時間、到着時刻、通過時刻等の走行関連時間を決定できるように、メッシュ情報を有する道路地図データベースを少なくとも有することが望ましい。
【００３３】
また、タイムスライス計算モジュール１１は位置検索モジュール１２によって判断される自動車等の車両位置、若しくはヒューマン・マシン・インターフェイス等を介してユーザが入力したその他の位置を基に車両の出発位置を特定し、後述されるようなタイムスライス計算を実施する。
【００３４】
そして、タイムスライス計算モジュール１１によって実施されたタイムスライス計算の結果は、経路検索モジュール１３、地図描画モジュール１４、その他のモジュール等によるその後の処理において用いることができる。
具体的には、経路検索モジュール１３はタイムスライス計算の結果に基づいて、車両の出発位置から入力された目的地までの経路を構成する各リンクについて、そのリンクの走行時点での交通状況（例えば、渋滞情報や通行規制情報等）を取得する。そして、取得した交通状況を考慮して目的地までの経路のコストを計算し、最適な経路を選択する。
【００３５】
次に図２及び図３に従って、データベース３に格納されている情報を用いて実行されるナビゲーション装置２の制御処理について説明する。
【００３６】
図２に示すように、ナビゲーションシステム１の動作開始後には、先ず自車の出発位置と対応する計算の為の出発時刻がステップ（以下Ｓと略す）１、Ｓ２において取得される。続いて、Ｓ３においてメッシュ情報が道路地図データベース２１から取得される。尚、アプリケーションが出発時刻を考慮しないのであれば、Ｓ２は必要ない。
【００３７】
次に、Ｓ４においては開始メッシュから特定のメッシュへの推測走行関連時間等を計測するタイムスライス計算処理が、後述される方法でタイムスライス計算モジュール１１によって実行される。そして、Ｓ４のタイムスライス計算の結果はＳ５におけるタイムマップの展開（生成）処理に用いられる。そして、Ｓ５ではユーザの操作情報に基づいて生成されたタイムマップの出力指示があるか否かが判定され、出力指示があると判定された場合（Ｓ６：ＹＥＳ）には、Ｓ７において出入力モジュール１６に含まれるディスプレイ等の表示部にタイムマップが出力される。一方、出力指示がないと判定された場合（Ｓ６：ＮＯ）には、Ｓ８へと移行する。
【００３８】
尚、図１０は前記Ｓ７におけるタイムマップの出力の一例を示した図である。そして、タイムマップの出力（Ｓ７）がユーザの意図された処理の最終結果であったならば、処理フローはＳ７から終了に進む。そうでない場合、若しくはＳ５及びＳ７に代わり、より精密なアプリケーションが実行される場合には、Ｓ４のタイムスライス計算の結果は以下に詳載されているようにＳ９において交通マップやイベントマップの生成に用いられる。
また、Ｓ８では交通データベース２２や前記イベントデータベース２３において交通データやその他の時間関連イベントデータが検索及び取得され、取得された交通データやその他の時間関連イベントデータ、及びＳ４のタイムスライス計算の結果に基づいて、Ｓ９で交通マップやイベントマップの生成が行われる。
【００３９】
次に、Ｓ１０ではユーザの操作情報に基づいて生成された交通マップやイベントマップの出力指示があるか否かが判定され、出力指示があると判定された場合（Ｓ１０：ＹＥＳ）には、Ｓ１１において出入力モジュール１６に含まれるディスプレイ等の表示部に交通マップやイベントマップが出力される。一方、出力指示がないと判定された場合（Ｓ１０：ＮＯ）には、図３のＳ１３へと移行する。
【００４０】
尚、タイムマップ、交通マップ及びイベントマップでは、到着、通過時刻（例えば９：００、９：１０等）の代わりに走行時間（例えば１５分等）を表示することもできる。加えて、Ｓ６、Ｓ７及び、もしくはＳ１０、Ｓ１１に加えて、Ｓ４のタイムスライス計算によって取得したデータは図３に示されているように、経路探索やその他のアプリケーションに用いることもできる。
【００４１】
続いて、Ｓ１３ではナビゲーション装置２において目的地が設定されているか否かが判定される。そして、目的地が設定されていると判定された場合（Ｓ１３：ＹＥＳ）には、目的地に関するデータがＳ１４においてデータベース３から取得される。一方、目的地が設定されていないと判定された場合（Ｓ１３：ＮＯ）には処理を終了する。
【００４２】
次に、Ｓ１５において、最適経路検索やその他のアプリケーションの処理が実行される。具体的に、経路探索処理では、前述の各Ｓ１〜Ｓ９で取得された自車の出発地点情報、メッシュ情報、交通データやその他の時間関連イベントデータ、及び前記Ｓ４のタイムスライス計算の結果に基づいて、車両の出発位置から入力された目的地までの経路を構成する各リンクについて、そのリンクの走行時点での交通状況（例えば、渋滞情報や通行規制情報等）を取得する。そして、取得した交通状況を考慮して目的地までの経路のコストを計算し、最適な経路を選択する。
【００４３】
次に、Ｓ１６ではユーザの操作情報に基づいて探索された経路の出力指示があるか否かが判定され、出力指示があると判定された場合（Ｓ１６：ＹＥＳ）には、Ｓ１７において出入力モジュール１６に含まれるディスプレイ等の表示部やスピーカを用いて探索された最適な経路（誘導経路）や誘導経路に従った走行の案内が出力される。一方、出力指示がないと判定された場合（Ｓ１６：ＮＯ）には、Ｓ２０へと移行する。
【００４４】
更に、Ｓ２１では、任意で更新された位置、時間データを基に経路のタイムスライスの動的な更新処理と、更新されたタイムススライスの計算結果に基づく再度の経路探索が行われる。そして、Ｓ１９においては、前記Ｓ１８で探索された新たな誘導経路や誘導経路に従った走行の案内がディスプレイ等の表示部やスピーカを用いて出力される。尚、Ｓ１８における誘導経路の動的な更新処理やＳ１９における再経路の出力処理は従来のタイムスライス技術もしくは、Ｓ４における更新されたタイムスライス計算の結果を用いて周知の技術により実施される。
【００４５】
次に、図４を用いて前記Ｓ４におけるタイムスライスのメッシュベースに基づく計算の一例を説明する。図４はメッシュｙｙｙｘｘｘ００、ｙｙｙｘｘｘ０１、ｙｙｙｘｘｘ０２と称される３つの隣接する正方形メッシュを示す。メッシュｙｙｙｘｘｘ００は車両の出発点を含むメッシュであり、これ以降、開始メッシュと称する。尚、メッシュ（間）は境界線によって分けられる。また、図４では簡易な例を示しており、１メッシュから隣のメッシュへの移動は１方向のみと考えるものとする。従って、メッシュｙｙｙｘｘｘ０２へ移動する際にはメッシュｙｙｙｘｘｘ０１を通過して移動するものとする。
【００４６】
ここで、図４に示すように開始メッシュｙｙｙｘｘｘ００にはタイムオフセット値として０が付与される。
一方、開始メッシュｙｙｙｘｘｘ００の隣のメッシュｙｙｙｘｘｘ０１には特定のオフセット値としてオフセット値０．２５が付与される。タイムオフセット値０．２５は時間基準（本実施形態においては１時間）によって積される数値であり、メッシュｙｙｙｘｘｘ０１のオフセット時間は０．２５×６０分＝１５分となる。
そして、メッシュｙｙｙｘｘｘ０１の更に隣のメッシュｙｙｙｘｘｘ０２には特定のオフセット値、オフセット値０．５が付与される。従って、例えば１時間の時間基準と考えると３０分がオフセット時間となる。
【００４７】
次に、オフセット値がどのように算出されるかを説明する前に、図４において示されている道路（リンク）の区分について説明する。メッシュｙｙｙｘｘｘ００内の出発点０からノードＮＡ、ＮＢ，ＮＣ、ＮＤを通過し、目的地Ｄまでの道路（リンク）は道路種別及びオフセット種別がＨとなる高速（走行）が認められた幹線道路や高速道路といった上級リンクである。また、ノードＮＡから境界地点ＢＢを通過し、ノードＮＣまでの道路（リンク）は道路種別及びオフセット種別がＭとなる中級リンクとみなされる。ノードＮＣを迂回するノードＮＢとＮＤを結ぶ道路（リンク）は道路種別及びオフセット種別がＬの下級リンクである。
【００４８】
そして、本実施形態では以下に説明するようにオフセット種別Ｈのオフセット予備値を０．２５、オフセット種別Ｍのオフセット予備値を０．４、オフセット種別Ｌのオフセット予備値を０．７として、メッシュのオフセット値を決定する。
【００４９】
メッシュベース計算の最も簡易な実施形態として本実施形態では、移動方向にあるメッシュに進入する道路の種別に基づく可能な最小オフセット値であるオフセット値を各メッシュに付与する。例えば図４の場合、移動方向は出発点０から目的地Ｄへの方向となる。従って、図４に示すようにメッシュｙｙｙｘｘｘ００とメッシュｙｙｙｘｘｘ０１間の境界線において、境界線横断地点ＢＡにおける種別Ｈリンクと境界線横断地点ＢＢにおける種別Ｍリンクと称される、境界線を横断する２つのリンクが存在する場合には、メッシュ（例えばメッシュ内のすべてのリンク）は道路種別Ｈのオフセット値、例えばオフセット値０．２５に決定される。
【００５０】
また、図４に示すようにメッシュｙｙｙｘｘｘ０１とメッシュｙｙｙｘｘｘ０２間の境界線においては、リンク種別Ｈと称される１リンク（道路）のみがメッシュｙｙｙｘｘｘ０１とメッシュｙｙｙｘｘｘ０２間の境界線を横断する為、その前のメッシュメッシュｙｙｙｘｘｘ０１に対する相対的なオフセットのみが考慮されるのであれば、メッシュｙｙｙｘｘｘ０２はオフセット値０．２５に決定される。但し、本実施形態では出発地点に基づく走行時間の推測を目的としている為、メッシュのオフセット値は以下の式（１）に従って算出される。
メッシュに付与されるオフセット＝その上流メッシュのオフセット値＋その上流メッシュからの相対的なオフセット値・・・（１）
【００５１】
従って、図４に示す例では、メッシュｙｙｙｘｘｘ０２のオフセット値＝その上流メッシュｙｙｙｘｘｘ０１のオフセット（＝０．２５）＋その上流メッシュからの相対的なオフセット値（＝０．２５）＝０．５となる。
【００５２】
また、仮にノードＮＤと目的地Ｄ間のリンクを（リンク種別Ｈの代わりに）リンク種別Ｌと想定すると、メッシュｙｙｙｘｘｘ０２のオフセット値＝０．９５（０．２５＋０．７）となる。
【００５３】
上記方法の変形例について図５を用いて説明する。図５は、メッシュＸとその隣接メッシュＹを示す。本変形例で考慮される移動方向は境界線Ｂ１から境界線Ｂ２を経て、境界線Ｂ３へと向かうものである。境界線横断地点ＢＡから境界線横断地点ＢＢを経て、境界線横断地点ＢＣまでのリンクは種別Ｈリンクである。ノードＮＡは、種別Ｈのこのリンクから種別Ｍのリンクへの出口である。
【００５４】
ここで、図４に従って説明した第一方法では、前記Ｓ４のタイムスライス計算において、１メッシュ内のすべてのリンクが一括して考慮され、そのメッシュは単一のオフセット値を受理する。従って、１メッシュのすべてのリンクに対し唯一の共通のオフセットが存在することとなる。
【００５５】
しかしながら実際は、通常、１メッシュ内においてもその道路網には種々な異なるリンクが存在する。そのような差異を考慮することにより、前記メッシュベース計算の正確性が改良される。
【００５６】
図５に示す変形例においては、特定の境界線を経て進入する道路種別に加え、メッシュ内の異なる種別のリンクの接続が考慮される。ここで、本目的の為に用いられる基本情報は、上級リンクである種別Ｈリンクからの出口の利用の可能性と任意でその数である。
【００５７】
図５に示されている例において、メッシュＸはノードＮＡと称される上級リンク出口を含んでいる。
【００５８】
図５に従って説明される変形例においては、次に図６及び図７で説明されるように、メッシュ内に含まれる異なる種別のリンクに対して、１メッシュは異なるオフセット値を３つまで受理する。ここで、図６及び図７はタイムスライス計算（図２のＳ４）のサブ処理について説明したフローチャートである。
【００５９】
図６に示すように、タイムスライス計算（図２のＳ４）は、先ずＳ１０１において開始メッシュを判定する。その後、Ｓ１０２において隣接メッシュもしくはメッシュグループが決定される。尚、それぞれの具体例については後に説明する。その後、Ｓ１０３において、前記Ｓ１０２で決定されたメッシュもしくはメッシュグループのうちの１つがタイムスライス計算を実施する為に選択される。
【００６０】
その後、Ｓ１０４において、異なるリンク種別Ｈ（上級）、Ｍ（中級）、Ｌ（下級）のそれぞれに対して、メッシュの境界線を通って進入するリンク（道路）の数が決定される。例えば、図５に示すメッシュＸは境界線Ｂ１を考えた場合、地点ＢＡで境界線を横断する種別Ｈの進入リンクを１つと地点ＢＤで境界線を横断する種別Ｍの進入リンク１つを有する。メッシュＹは、境界線Ｂ２を考えた場合、地点ＢＢで境界線を横断する種別Ｈの進入リンクを１つ、地点ＢＥで境界線を横断する種別Ｍの進入リンクを１つ、そして地点ＢＦで境界線を横断する種別Ｌの進入リンクを１つ有する。
【００６１】
次にＳ１０５において、前記Ｓ１０３で選択されたメッシュもしくはメッシュグループ内にある対応する上級リンクに、種別Ｈの上級リンクに対応するオフセット値が付与される。
【００６２】
更に、Ｓ１０６において、ノードＮＡ等の上級リンクの出口がメッシュもしくはメッシュグループ内に存在するかどうかを確認する。例えば、図５に示すメッシュＸには上級リンク出口が１つあるが、メッシュＹには上級リンク出口はない。また、ステップＳ１０７において、メッシュもしくはメッシュグループ内にある種別ＭとＬのリンクにオフセット値が付与される。
【００６３】
そして、Ｓ１０８では前記Ｓ１０３においてまだ選択されていないメッシュもしくはメッシュグループがあるか否か判定される。その結果、選択されていないメッシュもしくはメッシュグループがあると判定された場合（Ｓ１０８：ＹＥＳ）にはＳ１０３へと戻り、残りのメッシュ若しくはメッシュグループから次のメッシュ若しくはメッシュグループが選択される。一方、全てのメッシュもしくはメッシュグループが選択済であると判定された場合（Ｓ１０８：ＮＯ）にはタイムスライス計算（図２のＳ４）のサブ処理を終了し、Ｓ５へ戻る。
【００６４】
次に、図７を用いてステップＳ１０４〜Ｓ１０７までの変形例について説明する。尚、図７から分かるように、取得と付与の処理順序はステップＳ１０４〜Ｓ１０７における順序と完全に同じではない。それは、対応するステップは存在するが完全に対応する順序で行う必要はないからである。
【００６５】
先ず、Ｓ１１１において特定のメッシュ境界線における種別Ｈの進入リンクの数が取得される。そして、Ｓ１１２では種別Ｈの進入リンクの数が少なくとも１以上あるか否か判定される。その結果、種別Ｈの進入リンクの数が少なくとも１以上あると判定された場合（Ｓ１１２：ＹＥＳ）には、Ｓ１１３において、メッシュグループのメッシュ内における種別Ｈのリンクからの出口が在るか否か判定される。
【００６６】
そして、対応するメッシュ内に種別Ｈのリンクからの出口が存在すると判定された場合（Ｓ１１３：ＹＥＳ）には、Ｓ１１４において、対応するメッシュ内の（種別Ｈ、Ｍ、Ｌの）すべてのリンクに種別Ｈのオフセット（上記例においては０．２５）が付与され、Ｓ１０８へと移行する。
【００６７】
一方、対応するメッシュ内に種別Ｈのリンクからの出口が存在しないと判定された場合（Ｓ１１３：ＮＯ）には、Ｓ１１５において対応するメッシュ内の種別Ｈのリンクにのみ種別Ｈのオフセットが付与され、Ｓ１１６に進む。
【００６８】
また、前記Ｓ１１２で種別Ｈの進入リンクの数が存在しないと判定された場合（Ｓ１１２：ＮＯ）には、Ｓ１１６において、種別Ｍの進入リンクの数が少なくとも１以上在るか否か判定される。その結果、種別Ｍの進入リンクの数が少なくとも１以上あると判定された場合（Ｓ１１６：ＹＥＳ）には、Ｓ１１７において、対応するメッシュ内のすべてのリンクに種別Ｍのオフセットが付与される（但し、Ｓ１１５を経由した場合においては残るすべてのリンクに種別Ｍのオフセットが付与される）。その後、Ｓ１０８へと移行する。
【００６９】
一方、種別Ｍの進入リンクの数が存在しないと判定された場合（Ｓ１１６：ＹＥＳ）には、すべてのリンク、もしくは残るすべてのリンクに種別Ｌのオフセットが付与される。その後、Ｓ１０８へと移行する。
【００７０】
尚、すでに記載したように図７において示される実施形態は単なる一例にすぎない。また、種別Ｈのリンクからの出口の数もしくは種別Ｍのリンクからの出口の有無やその数が考慮されうる。また、図６及び図７は異なる種別のリンク間を接続するノードの有無を考慮することができることを根本的に示唆するものである。
【００７１】
即ち、種別Ｈのリンクを経てメッシュＸへ進入した時、あたかもメッシュＸにおける全走行が種別Ｍもしくは種別Ｌ上においてのみ実施されたかのようであるが、ノードＮＡと境界線の横断地点ＢＥとを接続する種別Ｍのリンク上の全走行速度が（上記状況）より高速である等の事実を反映させることができる。一方、メッシュＹにおいて、境界線横断地点ＢＢを経てメッシュＹへ進入した場合、種別ＭもしくはＬのリンクへ変更する可能性はない。従って、これらのリンクは種別Ｈのリンク上におけるより高速な走行速度の恩恵を受けることができない。
【００７２】
上記変形例においては、同じメッシュ内の異なる種別のリンクに異なるオフセットが付与されうる。異なる種別のリンクに対する異なるオフセットの付与は出口の有無等の考慮に限定されるものではない。当然、同じメッシュ内の異なる種別のリンクへの異なるオフセットの付与は出口の有無等を考慮せずとも可能である。
【００７３】
次にメッシュのオフセット値を算出するためのフローパターンについて、図８を用いて説明する。図８に従って説明される例はステップＳ１０３において実施される隣接メッシュもしくはメッシュグループの選択に関する２例のうちの１例である。
図８は８×８メッシュ、例えば６４メッシュのマトリクスから成るメッシュを示す。Ｓ１において取得される出発地点はメッシュ３３に位置する。メッシュは正方形である。従って各メッシュは正方形の隣接面によって表される隣接メッシュとの４つの境界線を有する。図８から、出発地点を含む開始メッシュ３３は４つの境界線を有し、その４つの境界線を横断する退出リンクだけが存在することは明らかである。そして、開始メッシュ３３にはタイムオフセット０が付与される。また、以下で開始メッシュ、もしくは出発地点周辺の扱いの方法については種々あるが、当面の間は開始メッシュのタイムオフセットは０のみと考える。
【００７４】
図８において示されるフローパターンは以下の規則に従って、開始メッシュからのメッシュの距離の増加を示す。
ａ）各メッシュ（開始メッシュを除く）はリンクが境界線を横断すると考えられる境界線を２つのみ有する。
ｂ）１メッシュ内に進入リンクが存在するならば、横断する進入リンクを有する境界線の反対側の境界線が退出リンクを有する境界線であると判断される。
ｃ）進入リンクを有さないメッシュ（開始メッシュと対角線上で交差するメッシュ）において退出リンクを有する境界線は、退出リンクを有する隣接メッシュの境界線に連続する境界線となるよう選択される。
【００７５】
従って、図８において矢印によって示されるフローパターンは増加する距離のフローパターンを示す移動順序で１つのメッシュから隣接するメッシュへの移動を示す。進入リンクを有さない上記メッシュ（開始メッシュ３３と対角線上で交差する位置にあるすべての「コーナーメッシュ」００，１１，２２，４４，５５，６６，７７，０６，１５，２４，４２，５１，６０）に関して上記メッシュは考慮すべき進入リンクを有さず、マトリクスの同じ列もしくは行の２つの「コーナーメッシュ」間に位置するメッシュと開始メッシュからの距離が同じであると考えなければならない。従って、上記「コーナーメッシュ」もフローパターンにおいて開始メッシュからの増加距離を示すメッシュである。
【００７６】
そして、各メッシュへのオフセット値の付与は前記Ｓ４において説明された計算に基づき実施される。
【００７７】
当然この場合、「コーナーメッシュ」の（オフセット値の付与の）為の解決方法が必要となる。なぜなら、これら「コーナーメッシュ」は進入メッシュを有さない為、上流メッシュや進入リンクに基づくオフセット値の計算が不可能だからである。
【００７８】
ここで、「コーナーメッシュ」へのオフセット値付与の望ましい付与方法はフローパターンにおける同距離の隣接メッシュのうち低い方の値の付与である。例えば、コーナーメッシュ４２の場合、メッシュ３２と４３のメッシュ値のうち低い値である。
【００７９】
図８において示されるフローパターンに基づくオフセット値の付与の特殊な変形例は開始メッシュからの距離が同レベルで、開始メッシュに対して同じ方角（北側、西側、南側、東側）に配列されたすべてのメッシュに同じ値を付与することである。この同じ値は、同距離レベルで同じ方角に配列されたメッシュのすべてのメッシュ値のうち最も低い値であることが望ましい。一例として、メッシュ２５、３５、４５、は（フローパターンでは同じ網かけによって示される）距離が同レベルで同じ方角（東側）に配列されている。
例えば、メッシュ２５のオフセット値を０．８、メッシュ３５のオフセット値を１．４、メッシュ４５のオフセット値を０．６５と想定すると、最も低い値（メッシュ４５の０．６５）がメッシュ２３、３５、４５の各々に付与される。同様にフローパターンにおいて北側の距離が同レベルにあるメッシュ、例えばメッシュ５２、５３、５４も同じオフセット値を有する。そのオフセット値を０．５と想定すると、２つの利用可能なメッシュ値のうち低い値（０．５）がコーナーメッシュ５５に付与される。従って図８において示されるフローパターンは以下の追加規則を有する。
ｄ）特定の選択規則に従い、開始メッシュに対して同じ方角で同距離レベルに位置するすべてのメッシュに、これらメッシュの最も高い値、最も低い値、もしくはその平均値等のうちの１つの値を付与する。
ｅ）上記ｄ）における同じ規則に従い、同距離レベルの隣接メッシュのオフセット値から選択されるオフセット値をコーナーメッシュに付与する。
【００８０】
尚、変形例として図８に示されるフローパターンにおいて、リンク種別やメッシュ内の出口の数等を反映させて、１メッシュ内にある異なる種別のリンクに異なるオフセット値を付与することは当然可能である。また別の例としては、Ｓ１０３におけるグループ選択の後、グループ内のメッシュにオフセットを付与する為に各メッシュの進入リンクの数の代わりに、グループ内のすべてのメッシュに対する進入リンクの数が考慮される。
【００８１】
次に、Ｓ１０３の隣接メッシュ、もしくはメッシュグループの選択の別例について図９を用いて説明する。図８とは異なり、図９においては、隣接メッシュ間の各境界線は進入もしくは退出リンクを有する境界線と考えられる。そのため、図８に示されているフローパターンにあるような「コーナーメッシュ」は存在しない。尚、図９に示されるフローパターンも開始メッシュからの増加距離を示すフローパターンであり、その増加距離は開始メッシュから出発する矢印によって横断される境界線の数によって表される。
【００８２】
従って、図９に示すフローパターンではメッシュ２３、３２、３４、４３は開始メッシュ３３からの距離が同レベルにあり、メッシュ１３，２２，２４，３１，３５，４２，４４，５３は開始メッシュからの距離が次のレベルにあり、メッシュ０３，１２，１４，２１，２５，３０，３６，４１，４５，５２，５４，６３はさらにその次の距離レベルにあるというように続いていく。
【００８３】
図９に示されているフローパターンにおいては、Ｓ４に関して説明されているのと同様のオフセット値を算出、付与するための処理が用いられる。各メッシュに個別オフセット値を付与することが望ましいが、距離レベル等に応じて同じメッシュ値を付与することも可能である。
【００８４】
図８及び図９において、Ｓ１０３の隣接メッシュもしくはメッシュグループの決定とステップＳ１０４の次のメッシュもしくはメッシュグループの選択は以下のように考えられる。
図８において、各メッシュが個別の値を受理するならば、隣接メッシュもしくはメッシュグループの決定はフロー手順で実施されることが望ましい。つまりまず、メッシュ３３，３４はグループ化され、もしくは流れが同一方向であるすべてのメッシュ、つまりまずメッシュ３３，４３、メッシュ３３，３４、メッシュ３３，２３、メッシュ３３，３２がグループ化され対応するオフセット値が算出される。次に、コーナーメッシュ２２，２４，４２，４４のメッシュ値が算出される。引き続き、メッシュ２２，１２、メッシュ２３，１３、メッシュ２４，１４、メッシュ２４，２５、メッシュ３４，３５等がグループ化され対応するオフセット値が算出、付与される。その後、コーナーメッシュ１１，１５，５１，５５のオフセット値が算出され、この論理に従って処理が続いていく。
【００８５】
一方、図９において、Ｓ１０３の選択は同様に実施される。つまり、まずメッシュ３３，２３、メッシュ３３，３４、メッシュ３３，４３、メッシュ３３，３２がグループ化され対応するオフセット値が算出、付与される。次にグループ決定がすでに事前に実施されているかどうかを判断し、メッシュ２３，２２、メッシュ２３，１３、メッシュ２３，２４、メッシュ３２，２２、メッシュ３１，２１、メッシュ３２，４２、メッシュ３４，２４、メッシュ３４，３５、メッシュ３４，４４、メッシュ４３，４２、メッシュ４３，５３、メッシュ４３，４４等のメッシュグループが算出、付与される。メッシュ毎の単一オフセット値もしくは上述されているような出口の数等の他の要素を考慮する可能性を有する異なる種別リンクの複数のオフセット値がオフセット値を算出、付与する際に用いられる。開始メッシュと開始メッシュと共有の境界線を有するメッシュ（２３，３２，３４，４３）を除く各メッシュは進入リンクを有する２つの境界線を有する。従って、（各メッシュに）１つのオフセット値、もしくはメッシュ内の特定種別リンクに１つのオフセット値を付与することができるように、どの値が選択されるべきかという規則を確定する必要があることは明らかである。これは、例えば２つの境界線のオフセット値のうちの低い値を付与することによって実施されうるが、高い値や平均値、他の規則によって決定される値であってもよい。
【００８６】
開始メッシュもしくは出発地点の周辺範囲に関しては、距離が限定されたり、道路網への接続が限られたりする為、リンク（道路）種別の違いを考慮する必要がない可能性がある。従って、上記方法の変形例としては、進入リンクの数や種別を考慮せずに、開始メッシュ周辺の複数のメッシュから構成されうる周辺範囲に、単一オフセットが付与される。図１１はそのような変形例を簡素な方法で示している。
【００８７】
他の変形例としては、オフセット計算はリンク種別を用いる際に、ユーザの好みを考慮する。例えば、ユーザが例えば種別Ｈのリンクである幹線道路や高速道路を用いることを好んだり、最短経路を用いることを好んだりした場合は、それをメッシュオフセット値の計算の考慮に入れることも可能である。
【００８８】
例えば、ユーザが例えば種別Ｈのリンクである幹線道路や高速道路を用いることを好んだ場合、対応する種別のリンクに対して選択されるオフセット値は上述の標準オフセット値と比較して減少する。また、可能であれば他のリンク種別を単に無視することもできる。
【００８９】
また、ユーザが最短経路を望むならば、図１２に示す方法も可能である。先ず、出発地点を含む開始メッシュ（出発メッシュ）と目的地を含むメッシュ（ターゲットメッシュ）間の直線、例えばその２つのメッシュの中心を結ぶ直線、もしくは出発地点と目的地を結ぶ直線等を引く。ここで、図１２の例に示されているように、ターゲットメッシュのオフセット値の算出の為に、メッシュＡとメッシュＢの２つのオフセット値のうちのどちらが選択されるが決定されなければならない。尚、ユーザは最短経路を望んでいるので、メッシュＢのオフセット値の方が小さくても、この直線はメッシュＡを横断している為、メッシュＡの値が選択される。
【００９０】
また、前記Ｓ１０、Ｓ１１で説明したように、交通マップおよび、もしくはイベントマップは例えば、対応経路の色分け等による交通予測や、表示された地図上に配置された所定のアイコンによって表示される（サッカーの試合、休日の交通の流れ等の）時間関連情報等を含む。従って、ユーザがＴ１時刻にＡ地点を出発し、Ｔ２時刻のコンサートに間に合うようＢ地点にいたいならば、Ｘ道路を使用した場合、サッカーの試合の為、Ｃ地点で交通渋滞が生じるであろうとユーザが理解できる。これにより、ユーザが経路探索機能を使わずに自分の時間スケジュールを立てたり決定しやすくなる。
【００９１】
尚、上述した明細書および、もしくは請求項に開示されているすべての特徴は実施例および、もしくは請求項の特徴の構成から独立して請求されている発明の制限とともに、出願時の開示を目的として、別々に互いに独立したものとして開示されるよう意図されていることを明記している。また、すべての値の範疇および、もしくは構成要素のグループ化の指定は、請求されている発明の制限、特に値の範疇の制限とともに、出願時の開示を目的としてあらゆる可能な中間値や中間構成要素の開示を明記している。
【図面の簡単な説明】
【００９２】
【図１】本実施形態に係るナビゲーションシステムの構成を示す概略ブロック図である。
【図２】本実施形態に係るナビゲーション装置の制御処理を示すフローチャートである。
【図３】本実施形態に係るナビゲーション装置の制御処理を示すフローチャートである。
【図４】本発明の単純な変形例を示す図である。
【図５】図４で示した変形例を説明する２つの隣接するメッシュを示す図である。
【図６】本実施形態に係るナビゲーション装置のオフセット付与の処理を示すフローチャートである。
【図７】本実施形態に係るナビゲーション装置のオフセット付与の処理の変形例を示すフローチャートである。
【図８】メッシュグループへのオフセット付与の例を示した図である。
【図９】各メッシュへの個別のオフセット付与の例を示した図である。
【図１０】図２のＳ７におけるタイムマップ出力の例を示した図である。
【図１１】出発地点周辺地域を個別に処理するための変形例を示した図である。
【図１２】短距離経路探索の例を示す図である。
【図１３】ある特定の一リンクの走行時間の例を示す図である。
【図１４】最適経路探索の為の従来のタイムスライス方法を示す図である。
【符号の説明】
【００９３】
１        ナビゲーションシステム
２        ナビゲーション装置
３        データベース
１１      タイムスライス計算モジュール
１２      位置検索モジュール
１３      経路探索モジュール
１４      地図描画モジュール
１５      送受信モジュール
１６      出入力モジュール
１７      記憶モジュール
２１      道路地図データベース
２２      交通データベース
２３      イベントデータベース
２４      その他の地理情報データベース
【図１】
0005130674.tif 000002
【図２】
0005130674.tif 000003
【図３】
0005130674.tif 000004
【図４】
0005130674.tif 000005
【図５】
0005130674.tif 000006
【図６】
0005130674.tif 000007
【図７】
0005130674.tif 000008
【図８】
0005130674.tif 000009
【図９】
0005130674.tif 000010
【図１０】
0005130674.tif 000011
【図１１】
0005130674.tif 000012
【図１２】
0005130674.tif 000013
【図１３】
0005130674.tif 000014
【図１４】
0005130674.tif 000015