【手続補正書】
【提出日】平成16年7月27日(2004.7.27)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
地図データ上の任意の２地点間の最適経路を選出するための方法であって、
前記地図データは、少なくとも、ノードデータおよびリンクデータを含み、
前記２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する第１のステップと、
前記基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出する第２のステップと、
前記第２のステップで算出した推定所要時間が一定時間経過する毎に、前記第１のステップで決定した基準時刻および前記推定所要時間に基づいて、地図データ上の所定のノードおよびリンクへの推定到達時刻を算出する第３のステップと、
前記２地点間に存在する地図データ上の各ノードおよびリンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得する第４のステップと、
前記第３のステップで算出した推定到達時刻において、前記第４のステップで取得した時間規制情報の規制時間帯に含まれるか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定して判定結果を記録する第５のステップと、
前記第５のステップで記録された判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第６のステップとを備える、経路選出方法。
【請求項２】
前記地図データは、ノードデータおよびリンクデータの中に少なくとも定常的な通行規制（右左折禁止規制、一方通行規制）を含んでおり、
前記第５のステップは、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かの判定結果を、前記地図データのノードデータおよびリンクデータの中の定常的な通行規制が記録されている領域に上書きする事を特徴とする、請求項１に記載の経路選出方法。
【請求項３】
地図データ上の任意の２地点間の最適経路を選出するための方法であって、
前記地図データは、少なくとも、ノードデータおよびリンクデータを含み、
前記２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する第１のステップと、
前記基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出する第２のステップと、
前記第１のステップで決定した基準時刻および前記第２のステップで算出した推定所要時間に基づいて、地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第３のステップと、
前記２地点間に存在する地図データ上の各ノードおよびリンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得する第４のステップと、
前記第３のステップで算出した推定到達時刻を含む予め決められた範囲の時間帯が、前記第４のステップで取得した時間規制情報の規制時間帯と重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定する第５のステップと、
前記第５のステップの判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第６のステップとを備える、経路選出方法。
【請求項４】
前記第５のステップは、前記第２のステップで算出した推定所要時間が増加するに従い、前記予め決められた範囲の時間帯を拡大することを特徴とする、請求項３に記載の経路選出方法。
【請求項５】
前記地図データは、少なくともノードデータおよびリンクデータおよび時間規制データを含み、時間規制データは車両特性により分類して記録されており、
前記第５のステップは、前記第４のステップで取得した時間規制情報のうち、使用する車両の特性に一致する分類に属するもののみを参照することを特徴とする、請求項１記載の経路選出方法。
【請求項６】
地図データ上の任意の２地点間の最適経路を選出するための方法であって、
前記地図データは、少なくともノードデータおよびリンクデータおよび時間規制データを含み、前記時間規制データは規制時間帯をビット列情報として記録されており、
前記地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第１のステップと、
前記第１のステップで算出した推定到達時刻を含む推定到達時刻帯と、前記地図データに記録された時間規制情報の規制時間帯とが重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定する第２のステップと、
前記第２のステップの判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第３のステップとを備える、経路選出方法。
【請求項７】
地図データ上の任意の２地点間の最適経路を選出するための方法であって、
前記地図データは、少なくともノードデータおよびリンクデータおよび時間規制データを含み、前記時間規制データは、重複するデータを別領域にまとめ、前記別領域へのポインタ情報を用いて記録しており、
前記地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第１のステップと、
前記地図データに記録された時間規制情報に用いられたポインタ情報をたどりながら記録内容を解析しつつ、前記第１のステップで算出した推定到達時刻を含む推定到達時刻帯と、前記時間規制情報の規制時間帯とが重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定する第２のステップと、
前記第２のステップの判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第３のステップとを備える、経路選出方法。
【請求項８】
地図データ上の任意の２地点間の最適経路を選出するためのシステムであって、
少なくとも、ノードデータおよびリンクデータを含む地図データを格納する地図データ格納手段と、
前記２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する基準時刻決定手段と、
前記基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出し、前記推定所要時間が一定時間経過する毎に、前記基準時刻決定手段で決定した基準時刻および前記推定所要時間に基づいて、地図データ上の所定のノードおよびリンクへの推定到達時刻を算出する推定到達時刻算出手段と、
前記２地点間に存在する地図データ上の各ノードおよびリンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得し、前記推定到達時刻算出手段で算出した推定到達時刻において、前記取得した時間規制情報の規制時間帯に含まれるか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定して判定結果を記録する時間規制判定手段と、
前記時間規制判定手段で記録された判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する経路探索手段とを備える、経路選出システム。
【請求項９】
地図データ上の任意の２地点間の最適経路を選出するためのシステムであって、
少なくとも、ノードデータおよびリンクデータを含む地図データを格納する地図データ格納手段と、
前記２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する基準時刻決定手段と、
前記基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出し、前記推定所要時間が一定時間経過する毎に、前記基準時刻決定手段で決定した基準時刻および前記推定所要時間に基づいて、地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する推定到達時刻算出手段と、
前記２地点間に存在する地図データ上の各ノードおよびリンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得し、前記推定到達時刻算出手段で算出した推定到達時刻を含む予め決められた範囲の時間帯が、前記時間規制情報の規制時間帯と重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定して判定結果を記録する時間規制判定手段と、
前記時間規制判定手段で記録された判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する経路探索手段とを備える、経路選出システム。
【請求項１０】
任意の２地点間の最適経路を選出するためのシステムであって、
少なくとも、ノードデータおよびリンクデータと、規制時間帯がビット列情報として記録される時間規制データを含む地図データを格納する地図データ格納手段と、
前記地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する推定到達時刻算出手段と、
前記推定到達時刻算出手段で算出した推定到達時刻を含む推定到達時刻帯と、前記地図データに記録された時間規制情報の規制時間帯とが重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定して判定結果を記録する時間規制判定手段と、
前記時間規制判定手段で記録された判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する経路探索手段とを備える、経路選出システム。
【請求項１１】
地図データ上の任意の２地点間の最適経路を選出するためのシステムであって、
少なくとも、ノードデータおよびリンクデータおよび時間規制データを含む地図データを格納する地図データ格納手段を備え、
前記時間規制データは、重複するデータを別領域にまとめ、前記別領域へのポインタ情報を用いて記録しており、
前記システムはさらに、
前記地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する推定到達時刻算出手段と、
前記地図データに記録された時間規制情報に用いられたポインタ情報をたどりながら記録内容を解析しつつ、前記推定到達時刻算出手段で算出した推定到達時刻を含む推定到達時刻帯と、前記時間規制情報の規制時間帯とが重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定して、判定結果を記録する時間規制判定手段と、
前記時間規制判定手段で記録された判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する経路探索手段とを備える、経路選出システム。
【請求項１２】
地図データ上の任意の２地点間の最適経路を選出するためのプログラムを記録した記録媒体であって、
前記地図データは、少なくとも、ノードデータおよびリンクデータを含み、
前記プログラムは、
前記２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する第１のステップと、
前記基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出する第２のステップと、
前記第２のステップで算出した推定所要時間が一定時間経過する毎に、前記第１のステップで決定した基準時刻および前記推定所要時間に基づいて、地図データ上の所定のノードおよびリンクへの推定到達時刻を算出する第３のステップと、
前記２地点間に存在する地図データ上の各ノードおよびリンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得する第４のステップと、
前記第３のステップで算出した推定到達時刻において、前記第４のステップで取得した時間規制情報の規制時間帯に含まれるか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定して判定結果を記録する第５のステップと、
前記第５のステップで記録された判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第６のステップとを備えるプログラムを記録した記録媒体。
【請求項１３】
地図データ上の任意の２地点間の最適経路を選出するためのプログラムを記録した記録媒体であって、
前記地図データは、少なくとも、ノードデータおよびリンクデータを含み、
前記プログラムは、
前記２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する第１のステップと、
前記基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出する第２のステップと、
前記第１のステップで決定した基準時刻および前記第２のステップで算出した推定所要時間に基づいて、地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第３のステップと、
前記２地点間に存在する地図データ上の各ノードおよびリンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得する第４のステップと、
前記第３のステップで算出した推定到達時刻を含む予め決められた範囲の時間帯が、前記第４のステップで取得した時間規制情報の規制時間帯と重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定する第５のステップと、
前記第５のステップの判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第６のステップとを備える、プログラムを記録した記録媒体。
【請求項１４】
地図データ上の任意の２地点間の最適経路を選出するためのプログラムを記録した記録媒体であって、
前記地図データは、少なくともノードデータおよびリンクデータおよび時間規制データを含み、前記時間規制データは規制時間帯をビット列情報として記録されており、
前記プログラムは、
前記地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第１のステップと、
前記第１のステップで算出した推定到達時刻を含む推定到達時刻帯と、前記地図データに記録された時間規制情報の規制時間帯とが重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定する第２のステップと、
前記第２のステップの判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第３のステップとを備える、プログラムを記録した記録媒体。
【請求項１５】
地図データ上の任意の２地点間の最適経路を選出するためのプログラムを記録した記録媒体であって、
前記地図データは、少なくともノードデータおよびリンクデータおよび時間規制データを含み、前記時間規制データは、重複するデータを別領域にまとめ、前記別領域へのポインタ情報を用いて記録しており、
前記プログラムは、
前記地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第１のステップと、
前記地図データに記録された時間規制情報に用いられたポインタ情報をたどりながら記録内容を解析しつつ、前記第１のステップで算出した推定到達時刻を含む推定到達時刻帯と、前記時間規制情報の規制時間帯とが重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定する第２のステップと、
前記第２のステップの判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第３のステップとを備える、プログラムを記録した記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】発明の詳細な説明
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、経路選出方法およびシステムに関し、より特定的には、地図データ上で交通規制を遵守した最適経路を選出するための方法およびシステムに関する。
【０００２】
【従来の技術】
周知のごとく、カーナビゲーションシステムは、車両の現在位置を検出して表示すると共に、目的地までの最適経路を自動的に探索し、当該最適経路に沿って車両を、表示ガイダンスおよび／または音声ガイダンスにより、目的地まで誘導案内するシステムである。このようなカーナビゲーションシステムにおいて、誘導案内する経路は、常に車両が通過可能である実用的な経路が求められている。そのため、一方通行規制や右左折禁止規制等の規制情報を反映した経路探索の方法が、盛んに研究および提案されている。
【０００３】
近年では、交通情報を考慮して一番短時間で到達できる最短時間経路を選出する等、誘導経路の品質の向上に関する研究開発が行われている。このような状況の中、従来は定常的に通行禁止として判断していた、時間により内容が変化する交通規制（以下、時間規制と称す）を考慮した経路探索を行う技術を特願平８−３０２２３５に開示している。これには、時間規制情報を反映した経路探索を行う方法として、以下の方法が示されている。
【０００４】
図７は、従来のカーナビゲーションシステムの構成を示すブロック図であり、図８は、従来の時間規制対応探索部のより詳細な構成を示す機能ブロック図である。
【０００５】
図７において、上記従来のカーナビゲーションシステムは、現在位置検出部７０１と、現在日時取得部７０２と、道路ネットワーク記憶部７０３と、入力部７０４と、時間規制対応探索部７０５と、誘導部７０６とを備えている。
【０００６】
現在位置検出部７０１は、ＧＰＳ、車速センサ、角速度センサ、絶対方位センサ等を含み、マップマッチング法等を用いて車両の現在位置を計算する。現在日時取得部７０２は、ＧＰＳ、車内時計等から現在日時を取得する。道路ネットワーク記憶部７０３は、交差点や道路の接続状況や座標・形状・属性・規制情報など、道路ネットワークに関する情報を記憶している。入力部７０４は、リモートコントローラ、タッチセンサ、キーボード、マウス等を含み、ユーザの操作に従って地点情報等を入力する。時間規制対応探索部７０５は、ＣＰＵやメモリ（プログラムメモリ、ワーキングメモリ）等を含み、基本的には、現在位置検出部７０１で検出した現在位置および入力部７０４でユーザーが入力した位置情報に基づいて、経路の出発地および目的地を判定する機能と、地図ネットワーク記憶部
７０３に記憶された道路ネットワーク上の探索開始点および探索終了点を設定する機能と、設定された探索開始点から探索終了点までの経路を、時間規制情報を反映しつつ、道路ネットワークに基づき選出する機能とを有している。
【０００７】
誘導部７０６は、表示装置（液晶ディスプレイ、ＣＲＴディスプレイ等）やスピーカ等を含み、現在位置検出部７０１で検出した車両の現在位置と道路ネットワーク記憶部７０３に記憶された地図データとを用いて、時間規制対応探索部７０５で選択された誘導経路を、画像や音声により誘導案内する。
【０００８】
ここで、道路ネットワーク記憶部７０３に記録される地図データについて説明する。地図データは、大きく分けて２つの構成要素からなる。第１の構成要素は、交差点に関する情報であるノードデータである。第２の構成要素は、交差点をつなぐ道路の情報であるリンクデータである。本実施形態では、それぞれのデータの中に、時間規制情報を含んでいる。ここで、時間規制情報とは、定常的に存在する交通規制ではなく、時間的に規制内容が変更されたり、無効となったりするものを指す。時間規制情報としては、例えば下記のような内容が挙げられる。
【０００９】
＜ノード時間規制＞７：００〜９：００の間は右折禁止
＜リンク時間規制＞１３：００〜２０：００の間は通行止め
さらに、時間規制対応探索部７０５について、図８を用いて詳述する。図８において、探索用データ格納部８０１は、現在位置検出部７０１や入力部７０４で入力された結果から探索範囲を特定し、道路ネットワーク記憶部７０３から該当探索範囲の地図データを読み込んで格納する。
【００１０】
経路探索部８０２は、現在位置検出部７０１や入力部７０４からの入力に基づいて探索開始点および探索終了点を決定する。ここで、時間規制反映部８０３は、現在日時取得部７０２や入力部７０４からの入力に基づいて、出発地から目的地までの走行予定時間帯を決定し、その時間帯において、探索用データ格納部８０１に格納された地図データの各ノードおよびリンクが通行可能か否かを判定し、地図データ上に判定結果すなわち規制の有無を書き込む。次に、経路探索部８０２は、時間規制反映部８０３により書き込まれた地図データに基づいて、探索開始点から探索終了点までの経路を選出する。
【００１１】
上記従来特許では、時間規制を考慮した探索を行うため、大きく分けて２種類の手法を開示している。ひとつは、探索開始前に各地点の予想通過時刻を決定し、通行不可能な時間帯であれば通行禁止情報を記録して、通常の規制情報と同様に扱って探索処理を行う手法である。
【００１２】
もうひとつは、探索処理の最中に、探索対象となった各地点において、既に求められている探索開始点からそこまでの経路情報を利用して予想通過時刻を求め、時間規制情報を参照して通過可能かどうか判定する手法である。ここで判定した結果を参照し、通過可能と判断すれば探索を接続先に広げ、通過不可能と判断されれば探索を接続先に広げないものとする。
【００１３】
このように、これらの手法を用いることにより、時間規制情報を反映した経路を選出することができる。
【００１４】
【発明が解決しようとする課題】
しかしながら、上記従来技術では、大別した２種類の手法の内、前者は予想通過時刻の算出精度が悪いため、必ずしも通過可能な最適経路が求められないという問題点があり、後者は探索処理の最中に探索対象となる全地点において、時間規制情報が存在した場合に予想通過時刻を計算して通過可能かどうか判定する必要があるため、処理が重くなり探索時間が増加するという問題点があった。
【００１５】
それ故に、本発明の目的は、時間規制を考慮し、安心して走行できる最適な経路を短時間で選出することができる経路選出方法およびシステムを提供することである。
【００１６】
【課題を解決するための手段】
第１の発明は、地図データ上の任意の２地点間の最適経路を選出するための方法であって、
前記地図データは、少なくとも、ノードデータおよびリンクデータを含み、
前記２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する第１のステップと、
前記基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出する第２のステップと、
前記第２のステップで算出した推定所要時間が一定時間経過する毎に、前記第１のステップで決定した基準時刻および前記推定所要時間に基づいて、地図データ上の所定のノードおよびリンクへの推定到達時刻を算出する第３のステップと、
前記２地点間に存在する地図データ上の各ノードおよびリンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得する第４のステップと、
前記第３のステップで算出した推定到達時刻において、前記第４のステップで取得した時間規制情報の規制時間帯に含まれるか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定して判定結果を記録する第５のステップと、
前記第５のステップで記録された判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第６のステップとを備えている。
【００１７】
第２の発明は、第１の発明において、前記地図データは、ノードデータおよびリンクデータの中に少なくとも定常的な通行規制（右左折禁止規制、一方通行規制）を含んでおり、
前記第５のステップは、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かの判定結果を、前記地図データのノードデータおよびリンクデータの中の定常的な通行規制が記録されている領域に上書きする事を特徴とする。
【００１８】
第３の発明は、地図データ上の任意の２地点間の最適経路を選出するための方法であって、前記地図データは、少なくとも、ノードデータおよびリンクデータを含み、
前記２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する第１のステップと、
前記基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出する第２のステップと、
前記第１のステップで決定した基準時刻および前記第２のステップで算出した推定所要時間に基づいて、地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第３のステップと、
前記２地点間に存在する地図データ上の各ノードおよびリンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得する第４のステップと、
前記第３のステップで算出した推定到達時刻を含む予め決められた範囲の時間帯が、前記第４のステップで取得した時間規制情報の規制時間帯と重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定する第５のステップと、
前記第５のステップの判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第６のステップとを備えている。
【００１９】
第４の発明は、第３の発明において、前記第５のステップは、前記第２のステップで算出した推定所要時間が増加するに従い、前記予め決められた範囲の時間帯を拡大することを特徴とする。
【００２０】
第５の発明は、第１の発明において、前記地図データは、少なくともノードデータおよびリンクデータおよび時間規制データを含み、時間規制データは車両特性により分類して記録されており、
前記第５のステップは、前記第４のステップで取得した時間規制情報のうち、使用する車両の特性に一致する分類に属するもののみを参照することを特徴とする。
【００２１】
第６の発明は、地図データ上の任意の２地点間の最適経路を選出するための方法であって、
前記地図データは、少なくともノードデータおよびリンクデータおよび時間規制データを含み、前記時間規制データは規制時間帯をビット列情報として記録されており、
前記地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第１のステップと、
前記第１のステップで算出した推定到達時刻を含む推定到達時刻帯と、前記地図データに記録された時間規制情報の規制時間帯とが重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定する第２のステップと、
前記第２のステップの判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第３のステップとを備えている。
【００２２】
第７の発明は、地図データ上の任意の２地点間の最適経路を選出するための方法であって、前記地図データは、少なくともノードデータおよびリンクデータおよび時間規制データを含み、前記時間規制データは、重複するデータを別領域にまとめ、前記別領域へのポインタ情報を用いて記録しており、
前記地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第１のステップと、
前記地図データに記録された時間規制情報に用いられたポインタ情報をたどりながら記録内容を解析しつつ、前記第１のステップで算出した推定到達時刻を含む推定到達時刻帯と、前記時間規制情報の規制時間帯とが重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定する第２のステップと、
前記第２のステップの判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第３のステップとを備えている。
【００２３】
第８の発明は、地図データ上の任意の２地点間の最適経路を選出するためのシステムであって、少なくとも、ノードデータおよびリンクデータを含む地図データを格納する地図データ格納手段と、
前記２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する基準時刻決定手段と、
前記基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出し、前記推定所要時間が一定時間経過する毎に、前記基準時刻決定手段で決定した基準時刻および前記推定所要時間に基づいて、地図データ上の所定のノードおよびリンクへの推定到達時刻を算出する推定到達時刻算出手段と、
前記２地点間に存在する地図データ上の各ノードおよびリンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得し、前記推定到達時刻算出手段で算出した推定到達時刻において、前記取得した時間規制情報の規制時間帯に含まれるか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定して判定結果を記録する時間規制判定手段と、
前記時間規制判定手段で記録された判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する経路探索手段とを備えている。
【００２４】
第９の発明は、地図データ上の任意の２地点間の最適経路を選出するためのシステムであって、
少なくとも、ノードデータおよびリンクデータを含む地図データを格納する地図データ格納手段と、
前記２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する基準時刻決定手段と、
前記基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出し、前記推定所要時間が一定時間経過する毎に、前記基準時刻決定手段で決定した基準時刻および前記推定所要時間に基づいて、地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する推定到達時刻算出手段と、
前記２地点間に存在する地図データ上の各ノードおよびリンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得し、前記推定到達時刻算出手段で算出した推定到達時刻を含む予め決められた範囲の時間帯が、前記時間規制情報の規制時間帯と重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定して判定結果を記録する時間規制判定手段と、
前記時間規制判定手段で記録された判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する経路探索手段とを備える。
【００２５】
第１０の発明は、任意の２地点間の最適経路を選出するためのシステムであって、
少なくとも、ノードデータおよびリンクデータと、規制時間帯がビット列情報として記録される時間規制データを含む地図データを格納する地図データ格納手段と、
前記地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する推定到達時刻算出手段と、
前記推定到達時刻算出手段で算出した推定到達時刻を含む推定到達時刻帯と、前記地図データに記録された時間規制情報の規制時間帯とが重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定して判定結果を記録する時間規制判定手段と、
前記時間規制判定手段で記録された判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する経路探索手段とを備える。
【００２６】
第１１の発明は、地図データ上の任意の２地点間の最適経路を選出するためのシステムであって、
少なくとも、ノードデータおよびリンクデータおよび時間規制データを含む地図データを格納する地図データ格納手段を備え、
前記時間規制データは、重複するデータを別領域にまとめ、前記別領域へのポインタ情報を用いて記録しており、
前記システムはさらに、
前記地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する推定到達時刻算出手段と、
前記地図データに記録された時間規制情報に用いられたポインタ情報をたどりながら記録内容を解析しつつ、前記推定到達時刻算出手段で算出した推定到達時刻を含む推定到達時刻帯と、前記時間規制情報の規制時間帯とが重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定して、判定結果を記録する時間規制判定手段と、
前記時間規制判定手段で記録された判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する経路探索手段とを備える。
【００２７】
第１２の発明は、地図データ上の任意の２地点間の最適経路を選出するためのプログラムを記録した記録媒体であって、
前記地図データは、少なくとも、ノードデータおよびリンクデータを含み、
前記プログラムは、
前記２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する第１のステップと、
前記基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出する第２のステップと、
前記第２のステップで算出した推定所要時間が一定時間経過する毎に、前記第１のステップで決定した基準時刻および前記推定所要時間に基づいて、地図データ上の所定のノードおよびリンクへの推定到達時刻を算出する第３のステップと、
前記２地点間に存在する地図データ上の各ノードおよびリンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得する第４のステップと、
前記第３のステップで算出した推定到達時刻において、前記第４のステップで取得した時間規制情報の規制時間帯に含まれるか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定して判定結果を記録する第５のステップと、
前記第５のステップで記録された判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第６のステップとを備える。
【００２８】
第１３の発明は、地図データ上の任意の２地点間の最適経路を選出するためのプログラムを記録した記録媒体であって、
前記地図データは、少なくとも、ノードデータおよびリンクデータを含み、
前記プログラムは、
前記２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する第１のステップと、
前記基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出する第２のステップと、
前記第１のステップで決定した基準時刻および前記第２のステップで算出した推定所要時間に基づいて、地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第３のステップと、
前記２地点間に存在する地図データ上の各ノードおよびリンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得する第４のステップと、
前記第３のステップで算出した推定到達時刻を含む予め決められた範囲の時間帯が、前記第４のステップで取得した時間規制情報の規制時間帯と重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定する第５のステップと、
前記第５のステップの判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第６のステップとを備える。
【００２９】
第１４の発明は、地図データ上の任意の２地点間の最適経路を選出するためのプログラムを記録した記録媒体であって、
前記地図データは、少なくともノードデータおよびリンクデータおよび時間規制データを含み、前記時間規制データは規制時間帯をビット列情報として記録されており、
前記プログラムは、
前記地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第１のステップと、
前記第１のステップで算出した推定到達時刻を含む推定到達時刻帯と、前記地図データに記録された時間規制情報の規制時間帯とが重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定する第２のステップと、
前記第２のステップの判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第３のステップとを備える。
【００３０】
第１５の発明は、地図データ上の任意の２地点間の最適経路を選出するためのプログラムを記録した記録媒体であって、
前記地図データは、少なくともノードデータおよびリンクデータおよび時間規制データを含み、前記時間規制データは、重複するデータを別領域にまとめ、前記別領域へのポインタ情報を用いて記録しており、
前記プログラムは、
前記地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第１のステップと、
前記地図データに記録された時間規制情報に用いられたポインタ情報をたどりながら記録内容を解析しつつ、前記第１のステップで算出した推定到達時刻を含む推定到達時刻帯と、前記時間規制情報の規制時間帯とが重複するか否かに基づいて、前記２地点間に存在する地図データ上の各ノードおよびリンクが通行可能か否かを判定する第２のステップと、
前記第２のステップの判定結果を参照しつつ、前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第３のステップとを備える。
【００３１】
【発明の実施の形態】
本発明の実施形態に係るカーナビゲーションシステムの構成を示すブロック図は、上記従来の技術で示した図７（従来のカーナビゲーションシステムの構成を示すブロック図）と同様である。しかし、道路ネットワーク記憶部７０３に記録された地図データと時間規制対応探索部７０５での処理が異なるので、これらについて詳述する。
【００３２】
ここで、道路ネットワーク記憶部７０３に記録される地図データについて説明する。図１は、地図データの一構成例を示している。図１に示すごとく、地図データは、大きく分けて３つの構成要素からなる。第１の構成要素は、交差点に関する情報であるノードデータである。第２の構成要素は、交差点をつなぐ道路の情報であるリンクデータである。上記２つの構成要素は従来から使われていたものである。第３の構成要素は、時間帯により規制内容が異なる時間規制情報を記録した時間規制データである。
【００３３】
上記時間規制データは、５つのリスト（普通車用情報リスト、大型車用情報リスト、ノード規制リスト、リンク規制リスト、時間帯リスト）で構成される。
【００３４】
まず、普通車用情報リストおよび大型車用情報リストは、それぞれ普通車および大型車を対象とした時間規制情報のみを記録する。ただし、規制位置や規制時間帯を記した実データを記録するのではなく、実データが記録されている場所へのポインタ情報を記録する。ここで、ノード規制ポインタは、交差点上の時間規制の実データを記したノード規制リストにおいて、該当するノード規制レコード番号で記録されるものとする。また同様に、リンク規制ポインタは、道路上の時間規制（一方通行規制）の実データを記したリンク規制リストにおいて、該当するリンク規制レコード番号で記録されるものとする。
【００３５】
次に、ノード規制リストは、ノードに関する時間規制の内容として規制位置と規制時間帯を記録している。規制位置を示す情報として、ノード番号・進入側リンク番号・脱出側リンク番号が記録されている。
【００３６】
これは、時間規制が存在するノードをノード番号で特定し、進入側リンク番号から脱出側リンク番号へ進行する方向への通行規制であることを示している。規制時間帯を示す情報として、規制時間帯の実データを記録するのではなく、実データが記録されている場所へのポインタ情報を記録している。ここで、時間帯ポインタは、規制時間帯の実データを記録した時間帯リストにおいて、該当する時間帯レコード番号で記録されるものとする。
【００３７】
さらに、リンク規制リストは、リンクに関する時間規制の内容として規制位置と規制時間帯を記録している。規制位置を示す情報として、リンク番号・規制方向（登り、下り）が記録されている。
【００３８】
これは、時間規制が存在するリンクをリンク番号で特定し、規制方向に対して通行禁止規制（一方通行規制）があることを示している。ノード規制リストと同様に、規制時間帯を示す情報として、規制時間帯の実データを記録するのではなく、実データが記録されている場所へのポインタ情報を記録している。ここで、時間帯ポインタは、規制時間帯の実データを記録した時間帯リストにおいて、該当する時間帯レコード番号で記録されるものとする。
【００３９】
最後に、時間帯リストは、０時から２４時までを１５分単位で１ビットずつ割り当てた１２バイトのビット列で表現し、規制時間帯に該当するビットを立てることにより、規制時間帯を表現する。
【００４０】
なお、ここでは普通車用情報リストと大型車用情報リストに２種類としたが、自動２輪や原付等の情報リストを含んでもかまわないし、業務用にタクシー等の分類を作成してもかまわない。
【００４１】
また、最初から時間規制データを、ノード時間規制データとリンク時間規制データに２分割していても良い。さらに、通行禁止時間帯を示す情報は単純に時間帯のみとしたが、開始月日・終了月日や週単位の条件等を規制時間帯として追加し、規制判定時に参照するようにしてもかまわない。
【００４２】
さらに、規制位置情報は規制対象となるノードやリンクが特定でき、その通過方向が分かればどのような形式でもかまわない。最後に、ノード規制ポインタ・リンク規制ポインタ・時間帯ポインタは各レコード番号としたが、各リスト先頭からのディスプレイスメントで表現しても良い。
【００４３】
図７のように構成されたカーナビゲーションシステムについて、以下にその動作を説明する。まず、入力部１０４において、ユーザーは出発地および目的地の設定を行う。すなわち、ユーザーは、入力部７０４を操作することにより、誘導部７０６に表示された地図の画像をスクロールさせ、希望する地点を出発地および目的地として入力する。なお、出発地は、現在位置検出部７０１において検出した車両の現在位置を使用してもよい。
【００４４】
次に、時間規制対応探索部７０５は、上記のように設定された出発地や目的地の位置に基づき、道路ネットワーク記憶部７０３に記憶された地図上のノードまたはリンク上の一番近い点を、探索開始点および探索終了点として採用する。
【００４５】
さらに、時間規制対応探索部７０５は、周知のダイクストラ法などを用いて最短コスト経路を計算し、求められた経路をリンク列またはノード列または座標列に変換し、誘導経路とする。本実施形態ではコストを旅行時間とみなし、旅行時間が短い経路を選出するものとする。
【００４６】
ただし、この時、時間規制対応探索部７０５は、取得した時間規制情報に基づき、現在日時取得部７０２から取得した現在時刻や、道路ネットワーク記憶部７０３に記憶された地図データ上での距離や、経路探索結果を用いて時間規制が存在する各ノードおよびリンクにおいて到達時間を推定し、そのノードおよびリンクが通過できるかどうかを判定し、探索処理に反映する。
【００４７】
最後に、誘導部７０６は、時間規制対応探索部７０５で求められた誘導経路と、現在位置検出部７０１から得られる現在位置と、道路ネットワーク記憶部７０３に記憶された地図データとに基づいて、誘導経路上を進むにはどの方向へ進めば良いかを、音声や表示を行なってユーザーに案内する。
【００４８】
図２は、本発明の実施形態のカーナビゲーションシステムで用いられる時間規制対応探索部７０５の構成を示す機能ブロック図である。図２において、この時間規制対応探索部７０５は、探索用データ格納部２０１と、経路探索部２０２と、基準日時情報決定部２０３と、時間規制定期補正部２０４とを備えている。
【００４９】
探索用データ格納部２０１は、現在位置検出部７０１や入力部７０４で入力された結果から探索範囲を特定し、道路ネットワーク記憶部７０３から該当探索範囲の地図データを読み込んで格納する。経路探索部２０２は、現在位置検出部７０１や入力部７０４からの入力に基づいて、探索開始点および探索終了点を決定する。
【００５０】
ここで、基準日時情報決定部２０３は、各ノードおよびリンクへの到達時刻を算出する基準点の基準時刻を決定するための基準日時情報を、現在日時取得部７０２または入力部７０４または探索用データ格納部２０１からの入力に基づいて決定する。
【００５１】
さらに、経路探索部２０２は、探索用データ格納部２０１に格納された地図データに基づいて経路を選出する。
【００５２】
その際、時間規制定期補正部２０４は、経路探索部２０２での経路探索処理中に、定期的に基準日時情報決定部２０３で決定された時刻を基に、探索用データ格納部２０１に格納された地図データや経路探索結果を基に予想到達時刻を算出し、各ノードおよびリンク上の時間規制が有効かどうかを判定する。
【００５３】
上記のように構成された実施形態における時間規制対応探索部７０５について、以下にその動作を詳述する。図３は、図２における経路探索部２０２の動作を示すフローチャートである。
【００５４】
まず、図３のステップＳ３０１において、経路探索部２０２は、例えば、現在位置検出部７０１で検出された車両の現在地を出発地に、入力部７０４で入力された位置を目的地に設定し、道路ネットワーク記憶部７０３から探索に必要な範囲の地図データを読み出して探索用データ格納部２０１に記憶する。その上で、出発地に一番近いノードを出発ノード、目的地に一番近いノードを目的ノードとして選出し、到達コストを０として探索用データ格納部２０１に記憶する。
【００５５】
次に、経路探索部２０２は、ステップＳ３０２において、基準日時情報決定部２０３に基準日時情報決定処理を実行させる。このステップＳ３０２では、基準日時情報決定部２０３は、基準点における基準日時を決定する。
【００５６】
図４は、上記サブルーチンステップＳ３０２の詳細を示すフローチャートである。以下、図４を参照して、基準日時情報決定部２０３の動作をより詳細に説明する。
【００５７】
まず、ステップＳ４０１において、基準日時情報決定部２０３は、基準点として出発地を採用する。次に、基準日時情報決定部２０３は、出発地側の基準時刻の入力をユーザーに促す（ステップＳ４０２）。
【００５８】
次に、基準日時情報決定部２０３は、基準時刻の入力があるか否かを判断し（ステップＳ４０３）、入力があればその時刻を出発地側の基準時刻とし、入力がなければステップＳ４０４の処理を行う。ステップＳ４０４では、基準日時情報決定部２０３は、現在日時取得部７０２から取得した現在日時を出発地側の基準時刻とする。基準日時情報決定部２０３は、以上で基準日時情報決定処理を終了する。
【００５９】
再び図３に戻り、以降、経路探索部２０２は、探索用データ格納部２０１に格納された地図データに基づいて、例えば周知のダイクストラ手法等を用いて、出発ノードから目的ノードまでの最短経路を、定期的に時間規制情報を参照し規制情報を書き換えながら選出する。ここでは、出発ノードを中心として探索を広げる出発地側探索手法をとることとする。ゆえに、出発ノードを探索開始点、目的ノードを探索終了点とも表記する。
【００６０】
ステップＳ３０３において、経路探索部２０２は、出発ノードを候補状態とする。次にステップＳ３０４では候補状態ノードの内、到達コストが最小のものを基準ノードとして、候補状態から除外する。
【００６１】
次に、ステップＳ３０５において、経路探索部２０２は、基準ノードの到達コストが予定到達コストを超えたか判断する。今は、この判断処理を実行するのは最初なので、予定到達コストを超えたものとして判断する。
【００６２】
ここで、予定到達コストを越えたと判断された場合、現在の予定到達コスト（最初の場合は現在の到達コスト）に時間規制データに記録された最小時間単位（１５分）のコストを加算して、新たな予定到達コストとした上で、ステップＳ３０６に進む。予定到達コストを超えていない場合、ステップＳ３０７以降の探索処理を続行する。
【００６３】
ステップＳ３０６では、経路探索部２０２は、探索用データ格納部２０１に読み込まれた全ての地図データ上に対して、定期的に時間規制情報を参照し、現在の予想到達時刻における規制情報を書き込む処理である時間規制定期補正処理を、時間規制定期補正部２０４にて実行する。ここで、ステップＳ３０６の時間規制定期補正処理について詳細に説明する。図５は、上記サブルーチンステップＳ３０６の詳細を示すフローチャートである。
【００６４】
まず、図５のステップＳ５０１において、時間規制定期補正部２０４は、基準日時情報決定部２０３で決定した出発地側の基準時刻と、出発ノードから基準ノードまでの到達コストから、基準ノードに到達する予想到達時刻を算出する。
【００６５】
本実施形態では、コストは旅行時間として扱っているので、出発地側の基準時刻に到達コスト分の時間を加算すればよい。ステップＳ５０２では、時間規制定期補正部２０４は、出発ノードから基準ノードまで実際に車両が走行した場合に生ずる、予想到達時刻の誤差を見込んで、補正時間帯を決定する。到達コストに誤差が２０％含まれると想定すれば、到達コストが７５分位内では＋−１５分、７５〜１５０分では＋−３０分の補正時間となる。
【００６６】
次にステップＳ５０３に進み、時間規制定期補正部２０４は、算出した予想到達時刻を中心に、決定した補正時間を含んだ予想到達時刻帯を、１５分単位のビット列情報（全１２バイト）に変換する。例えば、到達コストが４０分で、予想到達時刻が７時２５分の場合、補正時間は＋−１５分なので、予想到達時刻帯は７時１０分〜７時４０分となる。ここで、時間規制情報の時間帯情報は１５分単位であるので、最終的に予想到達時間帯は７時００分〜７時４５分と修正される。
【００６７】
次に、ステップＳ５０４で、時間規制定期補正部２０４は、ユーザーにより入力された車種情報に従い、以降の処理で参照する車種別リストを選択する。具体的には、普通車であれば普通車用情報リストを、大型車であれば大型車用情報リストを選択する。
【００６８】
次に、ステップＳ５０５〜Ｓ５１０までは、時間規制定期補正部２０４において、時間規制データのうちノード規制を参照し、規制時間帯に含まれれば規制情報を書き込む処理を行う。ステップＳ５０５では、普通車（大型車）用情報リストに記録されたノード規制数と、今まで参照したノード規制ポインタの数を比較し、まだ参照していないノード規制ポインタが残っていればステップＳ５０６に進み、残っていなければノード規制の反映処理を終了してステップＳ５１１に進む。ステップＳ５０６では、時間規制定期補正部２０４は、未参照のノード規制ポインタを読み出し、ステップＳ５０７で、ノード規制リストの該当するノード規制レコードにアクセスする。
【００６９】
次に、ステップＳ５０８は、ノード規制レコードの時間帯ポインタを読み出し、時間帯リストの該当する時間帯レコードにアクセスする。さらに、ステップＳ５０９で、時間規制定期補正部２０４は、該当するノード時間規制の規制時間帯に、ステップＳ５０３で求められた予想到達時刻帯が重複するかどうかを判定し、重複すればステップＳ５１０に進み、重複しなければステップＳ５０５の処理に戻る。
【００７０】
ここで、重複するかどうかの判定は、ステップＳ５０３で得られた予想到達時刻帯のビット列情報と、ステップＳ５０８で得られたノード時間規制の規制時間帯のビット列情報の論理積をとることにより判定する事ができる。
【００７１】
さらに、ステップＳ５０９で規制時間帯に重なると判定された場合、ステップＳ５１０で、時間規制定期補正部２０４は、該当するノード規制レコードのノード番号・進入側リンク番号・脱出側リンク番号を読み出し、ノード規制位置を特定して、ノードデータの該当するノードレコードに定常的通行禁止規制として記録する。最後に、ステップＳ５０５に戻り、未参照のノード規制ポインタがなくなるまで、ステップＳ５０５〜Ｓ５１０の処理を繰り返す。
【００７２】
ステップＳ５０５で、未参照のノード規制ポインタがなくなったと判断された場合、ステップＳ５１１に進む。ステップＳ５１１〜Ｓ５１６までは、時間規制定期補正部２０４において、時間規制データのうちリンク規制を参照し、規制時間帯に含まれれば規制情報を書き込む処理を行う。ステップＳ５１１では、普通車（大型車）用情報リストに記録されたリンク規制数と、今まで参照したリンク規制ポインタの数を比較し、まだ参照していないリンク規制ポインタが残っていればステップＳ５１２に進み、残っていなければノード規制・リンク規制双方とも反映できたと判断して、図３のステップＳ３０６の時間規制定期補正処理を終了する。ステップＳ５１２では、時間規制定期補正部２０４は、未参照のリンク規制ポインタを読み出し、ステップＳ５１３で、リンク規制リストの該当するリンク規制レコードにアクセスする。
【００７３】
次に、ステップＳ５１４は、リンク規制レコードの時間帯ポインタを読み出し、時間帯リストの該当する時間帯レコードにアクセスする。さらに、ステップＳ５１５で、時間規制定期補正部２０４は、該当するリンク時間規制の規制時間帯に、ステップＳ５０３で求められた予想到達時刻帯が重複するかどうかを判定し、重複すればステップＳ５１６に進み、重複しなければステップＳ５１１の処理に戻る。
【００７４】
ここで、重複するかどうかの判定は、ステップＳ５０３で得られた予想到達時刻帯のビット列情報と、ステップＳ５１４で得られたリンク時間規制の規制時間帯のビット列情報の論理積をとることにより判定する事ができる。
【００７５】
さらに、ステップＳ５１５で規制時間帯に重なると判定された場合、ステップＳ５１６で、時間規制定期補正部２０４は、該当するリンク規制レコードのリンク番号・規制方向を読み出し、リンク規制位置を特定して、リンクデータの該当するリンクレコードに定常的通行禁止規制として記録する。最後に、ステップＳ５１１に戻り、未参照のリンク規制ポインタがなくなるまで、ステップＳ５１１〜ステップＳ５１６の処理を繰り返す。
【００７６】
以上で、時間規制定期補正部２０４で実行される図３のステップＳ３０６の時間規制定期補正処理の説明を終了する。
【００７７】
次に、図３のフローチャートに戻り、ステップＳ３０７で、経路探索部２０２では、基準ノードが目的ノードであるか調べ、目的ノードであればステップＳ３１４の経路構成処理に進む。目的ノードでなければ、次のステップに進む。ステップＳ３０８では、基準ノードに接続するリンクは全て調査したかどうかチェックする。全て調査済みであれば、ステップＳ３０４に戻り、次の基準ノードを探す。未調査リンクがあれば、ステップＳ３０９で未調査リンクの１本を調査対象リンクとする。
【００７８】
次に、ステップＳ３１０では、基準ノードでの定常的通行禁止規制（右左折規制）や調査対象リンクの定常的通行禁止規制（一方通行規制）をチェックして、調査対象リンクの方向へ通過できなければステップＳ３０８に戻り、調査対象リンクの方向に通過できれば、次のステップに進む。ステップＳ３１１では、基準ノードへの到達コストに調査対象リンクのコストを加算して、調査対象リンクに接続する基準ノードの逆側のノード（行き先ノード）への新到達コストとする。次に、ステップＳ３１２で、行き先ノードへの到達が初めてであるか、または、新到達コストが今までの到達コスト中最小であれば、ステップＳ３１３に進み、そうでなければステップＳ３０８に戻る。
【００７９】
ステップＳ３１３では、行き先ノードを候補状態とする。さらに、探索用中間データとして、行き先ノードに対し、前リンクとして調査対象リンクを、到達コストとして新到達コストを探索用データ格納部２０１に記録してステップＳ３０８に戻る。上記処理を繰り返し、経路探索処理を行う。
【００８０】
最後に、ステップＳ３１４の経路構成処理について説明する。図６は、上記サブルーチンステップＳ３１４の詳細を示すフローチャートである。
【００８１】
まず、図６のステップＳ６０１において、調査対象ノードを目的ノードとする。次に、ステップＳ６０２で調査対象ノードは出発ノードであるかどうかチェックして、出発ノードであればステップＳ６０５に進み、今までの経路リンク列を逆順にして誘導経路とする。出発ノードでなければステップＳ６０３に進み、探索用データ格納部２０１に探索用中間データとして記録された、調査対象ノードの前リンクを経路リンク列に加える。
【００８２】
次に、ステップＳ６０４では、調査対象ノードへ記録された前リンクに接続する２つのノードの内、現在の調査対象ノードではない方のノードを、新たな調査対象ノードとしてステップＳ６０２に戻る。上記処理を繰り返し、経路構成処理を行う。
【００８３】
以上のように、本実施形態によれば、探索を一定範囲広げる毎に、読み込まれた地図上の各地点のうち時間規制情報が存在するものだけを対象に、時間規制情報を参照し規制時間帯に重なれば規制情報を書き込む手法を採ることにより、時間規制を参照する処理回数を少なくすることができるので、処理時間を軽減できる。
【００８４】
また、規制時間帯に含まれる場合、地図データとして従来から存在するノードデータやリンクデータの定常的通行禁止規制の記録領域を利用して、通行禁止規制を上書きする事により、通行禁止規制記録領域を新たに確保した上で探索処理中に参照する処理を新設する必要がない。
【００８５】
さらに、予想到達時刻を含む一定時間範囲を予想到達時刻帯とし、規制時間帯に重なった場合に通行禁止と判断することにより、実際に車両が到達した時刻が予想到達時刻から一定時間範囲はずれていても走行可能な経路を提供することができる。
【００８６】
さらに、前記一定時間範囲を探索が広がるに従い拡大することにより、実際に走行距離が長くなるほど拡大する予想到達時刻の予測誤差を反映することができるので、実際の走行に適した経路を提供することができる。
【００８７】
さらに、走行する車両に注目し、車両特性により分類して時間規制情報を記録することにより、実際に必要な時間規制情報のみにアクセスできるので、処理時間を削減することができる。
【００８８】
さらに、規制時間帯をビット情報として記録することにより、規制時間帯に含まれるか否かの判断を簡単なマスク処理で実施できるため、処理時間を削減することができる。
【００８９】
最後に、ノード規制レコード・リンク規制レコード・時間帯レコード等、サイズが大きく重複が多い情報はまとめて別領域に記録し、そこへのポインタ情報を使用することにより、記録総サイズを削減することができる。
【００９０】
なお、本実施形態では、経路探索時に、出発地側からの１階層出発地側探索を行うようにしているが、公知の階層別探索手法や双方向探索手法を使用しても良い。
【００９１】
また、基準点として出発地を採用しているが、現在車両位置・経由地・目的地等を基準点としても構わない。その場合、現在車両位置・出発地・経由地・目的地の位置関係を考慮して、走行順に各移動所要時間を推定して基準点での基準時刻を算出してもよい。
【００９２】
また、リンクの時間規制情報の有効性を判定する場合、リンクに進入する時刻だけではなく、リンクを通過しきった時刻まで考慮して通過可能かどうか判定してもよい。
【００９３】
また、基準時刻の決定は、ユーザー入力のみに基づいてもよいし、現在時刻のみに基づいてもよい。また、現在時刻に基づく場合、車両の現在位置から基準点までの距離に基づいた推定移動時間を加算してもよい。
【００９４】
また、時間規制情報が有効な場合、地図データ上に通行禁止情報を書き込んだが、時間規制情報として規制種別を記録して、ノードおよびリンクの通過コストを予め決められた値に変更する等の処理を行っても良い。
【００９５】
なお、以上説明した本実施形態において、以上に説明した各機能ブロックは、ハードウェアによって構成されても良いし、マイクロコンピュータのマルチタスクなどのプログラム処理の結果として構成されても良い。
【００９６】
さらに、交通情報取得部を付加し、交通情報として提供される時間規制情報を取得して、上記実施形態と同様にして経路探索結果に反映させても良い。
【００９７】
また、本発明は、プログラムによって実現し、これをフロッピーディスク等の記録媒体に記録して移送することにより、独立した他のコンピュータ・システムで容易に実施することができる。この場合、記録媒体は、フロッピーディスクに限らず、光ディスク、ＩＣカード、ＲＯＭカセット等、プログラムを記録できるものであれば、同様に実施することができる。
【００９８】
【発明の効果】
本願の第１に発明によれば、探索を一定範囲広げる毎に、読み込まれた地図上の各地点のうち時間規制情報が存在するものだけを対象に、時間規制情報を参照し規制時間帯に重なれば規制情報を書き込む手法を採ることにより、時間規制を参照する処理回数を少なくすることができるので、処理時間を軽減できる。
【００９９】
また、本願の第２の発明によれば、規制時間帯に含まれる場合、地図データとして従来から存在するノードデータやリンクデータの定常的通行禁止規制の記録領域を利用して、通行禁止規制を上書きする事により、通行禁止規制記録領域を新たに確保した上で探索処理中に参照する処理を新設する必要がない。
【０１００】
また、本願の第３の発明によれば、予想到達時刻を含む一定時間範囲を予想到達時刻帯とし、規制時間帯に重なった場合に通行禁止と判断することにより、実際に車両が到達した時刻が予想到達時刻から一定時間範囲はずれていても走行可能な経路を提供することができる。
【０１０１】
また、本願の第４の発明によれば、前記一定時間範囲を探索が広がるに従い拡大することにより、実際に走行距離が長くなるほど拡大する予想到達時刻の予測誤差を反映することができるので、実際の走行に適した経路を提供することができる。
【０１０２】
また、本願の第５の発明によれば、走行する車両に注目し、車両特性により分類して時間規制情報を記録することにより、実際に必要な時間規制情報のみにアクセスできるので、処理時間を削減することができる。
【０１０３】
また、本願の第６の発明によれば、規制時間帯をビット情報として記録することにより、規制時間帯に含まれるか否かの判断を簡単なマスク処理で実施できるため、処理時間を削減することができる。
【０１０４】
また、本願の第７の発明によれば、ノード規制レコード・リンク規制レコード・時間帯レコード等、サイズが大きく重複が多い情報はまとめて別領域に記録し、そこへのポインタ情報を使用することにより、記録総サイズを削減することができる。
【０１０５】
また、本願の第８に発明によれば、探索を一定範囲広げる毎に、読み込まれた地図上の各地点のうち時間規制情報が存在するものだけを対象に、時間規制情報を参照し規制時間帯に重なれば規制情報を書き込む手法を採ることにより、時間規制を参照する処理回数を少なくすることができるので、処理時間を軽減できる。