(57)【要約】【課題】　規制の有無や内容が時間的に変化する時間規制情報を遵守した経路を探索することのできる経路選出方法を提供する。【解決手段】　探索用データ格納部２０１は、現在位置検出部１０１等で入力された結果から探索範囲を特定し、道路ネットワーク記憶部１０３から該当探索範囲の地図データを読み込んで格納する。経路探索部２０２は、現在位置検出部１０１等からの入力に基づいて探索開始点および探索終了点を決定する。時間規制反映部２０３は、現在日時取得部１０２や入力部１０４からの入力に基づいて、出発地から目的地までの走行予定時間帯を決定し、その時間帯において、格納されている地図データの各ノードおよびリンクが通行可能か否かを判定し、地図データ上に規制の有無を書き込む。経路探索部２０２は、書き込まれた地図データに基づいて、探索開始点から探索終了点までの経路を選出する。【選択図】　図３
2004004131.tif 000002
【特許請求の範囲】
【請求項１】
　地図データ上の任意の２地点間の最適経路を選出するための方法であって、
　前記地図データは、少なくとも、ノードデータおよびリンクデータを含み、
　前記２地点間の最適経路を選出する前に予め、当該２地点間の走行予定時間帯を決定する第１のステップと、
　前記地図データ上の各ノードおよび各リンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得する第２のステップと、
　前記第１のステップで決定した走行予定時間帯と、前記第２のステップで取得した時間規制情報の規制時間帯との重複関係に基づいて、前記２地点間に存在する各リンクおよびノードが通行可能か否かを判定する第３のステップと、
　前記第３のステップの判定結果を参照しつつ前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第４のステップとを備える、経路選出方法。
【請求項２】
　前記第１のステップは、ユーザーによって入力された時間情報を、前記２地点間の走行予定時間帯として決定することを特徴とする、請求項１に記載の経路選出方法。
【請求項３】
　前記第１のステップは、ある一定時刻毎に区分した時間帯をディスプレイ上に表示し、任意の時間帯をユーザーに選択させることを特徴とする、請求項２に記載の経路選出方法。
【請求項４】
　前記第１のステップは、
　　出発予定時刻をユーザーに入力させる第５のステップと、
　　前記２地点間の直線距離に基づいて、当該２地点間の推定所要時間を算出する第６のステップと、
　　前記第５のステップで入力された出発予定時刻に、前記第６のステップで算出された推定所要時間を加算することにより、前記２地点間の走行予定時間帯を算出する第７のステップとを含む、請求項１に記載の経路選出方法。
【請求項５】
　前記第４のステップは、前記２地点間に存在するリンクおよびノードについて前記第３のステップの判定結果が反映された前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を双方向探索手法により探索することを特徴とする、請求項１に記載の経路選出方法。
【請求項６】
　地図データ上の任意の２地点間の最適経路を選出するためのシステムであって、
　少なくともノードデータおよびリンクデータを含む地図データを格納する地図データ格納手段と、
　前記２地点間の最適経路を選出する前に予め、当該２地点間の走行予定時間帯を決定する走行時間帯決定手段と、
　前記地図データ上の各ノードおよび各リンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得し、前記走行時間帯決定手段が決定した走行予定時間帯と、当該取得した時間規制情報の規制時間帯との重複関係に基づいて、前記２地点間に存在する各リンクおよびノードが通行可能か否かを判定する判定手段と、
　前記判定手段の判定結果を参照しつつ前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する経路探索手段とを備える、経路選出システム。
【請求項７】
前記経路探索手段は、前記２地点間に存在するリンクおよびノードについて前記判定手段による判定結果が反映された前記地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を双方向探索手法により探索することを特徴とする、請求項６に記載の経路選出システム。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明は、経路選出方法およびシステムに関し、より特定的には、地図データ上で交通規制を遵守した最適経路を選出するための方法およびシステムに関する。
【背景技術】
【０００２】
　周知のごとく、カーナビゲーションシステムは、車両の現在位置を検出して表示すると共に、目的地までの最適経路を自動的に探索し、当該最適経路に沿って車両を、表示ガイダンスおよび／または音声ガイダンスにより、目的地まで誘導案内するシステムである。このようなカーナビゲーションシステムにおいて、誘導案内する経路は、常に車両が通過可能である実用的な経路が求められている。そのため、一方通行規制や右左折禁止規制等の規制情報を反映した経路探索の方法が、盛んに研究および提案されている。
【０００３】
　従来、上記のような定常的な規制情報を用いて、交通規制を遵守した経路を選出するような車両用経路案内装置としては、例えば特開昭６２−８２３１６号公報に開示されているものがあった。この公開公報には、定常的な規制情報を反映する方法として、以下の方法が示されている。
【０００４】
　図２４は、上記従来の車両用経路案内装置の構成を示すブロック図である。図２４において、この車両用経路案内装置は、進入禁止や右左折禁止などの通行方向規制を考慮して、次に到達可能な隣接交差点およびそれまでの所要時間相関量等の情報を、各交差点について記述した地図データを記憶している基本情報記憶部１と、基本情報記憶部１が記憶している地図データを参照して、一定の条件の下に、出発交差点から目的交差点へ至る最短経路を検索する経路検索部２とを備えている。
【０００５】
　上記従来装置でユニークなのは、基本情報記憶部１が記憶している地図データの道路ネットワークの表現法である。すなわち、本従来装置では、交通規制を考慮した上で、到達可能な交差点への道路のみを記憶することにより、経路検索部２で複雑な処理を行わないで、規制を遵守した経路を検索することを可能としている。
【０００６】
　ここで、上記従来装置で採用している道路ネットワークの表現法を説明する。図２５は、上記従来装置における道路ネットワークの表現法を説明するための図である。例えば、図２５（ａ）に示すような交差点、すなわち各進入方向に右折禁止規制が設けられているような交差点が存在する場合、地図データ上では、図２５（ｂ）に示すように道路ネットワークを表現する。すなわち、交差点の各進入方向毎にノードを想定し、通行可能な直進／左折方向のみリンクがあるものと想定する。
【０００７】
　このように、規制情報を反映した道路ネットワークを用いて地図データを記録することにより、通常の経路検索処理を適用しつつ、定常的な交通規制を反映した経路を選出することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
　一般に、カーナビゲーションシステムでの経路探索においてユーザーが期待するものは、目的地に到達可能な実用的な経路の探索であり、これを実現することが求められている。しかし、上記した従来技術では、定常的な交通規制には対応できても、時間により内容が変化する交通規制（以下、時間規制と称す）には対応できなかった。そのため、選出された経路に沿って走行中に、時間規制により通過できないことがあり、ドライバーに心理的負担を強いるという問題点があった。
【０００９】
　それ故に、本発明の目的は、定常的な交通規制のみならず、時間規制をも考慮し、安心して走行できる最適な経路を選出することができる経路選出方法およびシステムを提供することである。
【課題を解決するための手段】
【００１０】
　第１の発明は、地図データ上の任意の２地点間の最適経路を選出するための方法であって、
　地図データは、少なくとも、ノードデータおよびリンクデータを含み、
　２地点間の最適経路を選出する前に予め、２地点間の走行予定時間帯を決定する第１のステップと、
　地図データ上の各ノードおよび各リンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得する第２のステップと、
　第１のステップで決定した走行予定時間帯と、第２のステップで取得した時間規制情報の規制時間帯との重複関係に基づいて、２地点間に存在する各リンクおよびノードが通行可能か否かを判定する第３のステップと、
　第３のステップの判定結果を参照しつつ地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第４のステップとを備えている。
【００１１】
　第２の発明は、第１の発明において、
　第１のステップは、ユーザーによって入力された時間情報を、２地点間の走行予定時間帯として決定することを特徴とする。
【００１２】
　第３の発明は、第２の発明において、
　第１のステップは、ある一定時刻毎に区分した時間帯をディスプレイ上に表示し、任意の時間帯をユーザーに選択させることを特徴とする。
【００１３】
　第４の発明は、第１の発明において、
　第１のステップは、
　　出発予定時刻をユーザーに入力させる第５のステップと、
　　２地点間の直線距離に基づいて、当該２地点間の推定所要時間を算出する第６のステップと、
　　第５のステップで入力された出発予定時刻に、第６のステップで算出された推定所要時間を加算することにより、２地点間の走行予定時間帯を算出する第７のステップとを含むことを特徴とする。
【００１４】
　第５の発明は、第１の発明に従属する発明であって、
　第４のステップは、２地点間に存在するリンクおよびノードについて第３のステップの判定結果が反映された地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を双方向探索手法により探索することを特徴とする。
【００１５】
　第６の発明は、地図データ上の任意の２地点間の最適経路を選出するためのシステムであって、
　少なくともノードデータおよびリンクデータを含む地図データを格納する地図データ格納手段と、
　２地点間の最適経路を選出する前に予め、２地点間の走行予定時間帯を決定する走行時間帯決定手段と、
　地図データ上の各ノードおよび各リンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得し、走行時間帯決定手段が決定した走行予定時間帯と、当該取得した時間規制情報の規制時間帯との重複関係に基づいて、２地点間に存在する各リンクおよびノードが通行可能か否かを判定する判定手段と、
　判定手段の判定結果を参照しつつ地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する経路探索手段とを備えている。
【００１６】
　第７の発明は、第６の発明に従属する発明であって、
　経路探索手段は、２地点間に存在するリンクおよびノードについて判定手段による判定結果が反映された地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を双方向探索手法により探索する。
【００１７】
　この発明は、以下のような他の態様も含んでいる。
　すなわち、第１の態様は、地図データ上の任意の２地点間の最適経路を選出するための方法を実現するプログラムを格納した記憶媒体であって、
　地図データは、少なくとも、ノードデータおよびリンクデータを含み、
　前記プログラムは、
　　２地点間の走行予定時間帯を決定する第１のプログラムステップと、
　　地図データ上の各ノードおよび各リンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得する第２のプログラムステップと、
　　第１のプログラムステップで決定した走行予定時間帯と、第２のプログラムステップで取得した時間規制情報の規制時間帯との重複関係に基づいて、２地点間に存在する各リンクおよびノードが通行可能か否かを判定する第３のプログラムステップと、
　　第３のプログラムステップの判定結果を参照しつつ地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第４のプログラムステップとを備えている。
【００１８】
　第２の態様は、地図データ上の任意の２地点間の最適経路を選出するための方法を実現するプログラムを格納した記憶媒体であって、
　地図データは、少なくとも、ノードデータおよびリンクデータを含み、
　前記プログラムは、
　　２地点の少なくとも一方を基準点として選択し、当該基準点における基準時刻を決定する第１のプログラムステップと、
　　基準点から地図データ上の各ノードおよび各リンクへの推定所要時間を算出する第２のプログラムステップと、
　　第１のプログラムステップで決定した基準時刻および第２のプログラムステップで算出した推定所要時間に基づいて、地図データ上の各ノードおよび各リンクへの推定到達時刻を算出する第３のプログラムステップと、
　　地図データ上の各ノードおよび各リンクについて、時間規制（時間により内容が変化する交通規制）の有無およびその内容を示した時間規制情報を取得する第４のプログラムステップと、
　　第３のプログラムステップで算出した推定到達時刻が、第４のプログラムステップで取得した時間規制情報の規制時間帯に含まれるか否かに基づいて、２地点間に存在する各リンクおよびノードが通行可能か否かを判定する第５のプログラムステップと、
　　第５のプログラムステップの判定結果を参照しつつ地図データに基づいて、時間規制を遵守した通行可能な２地点間の最適経路を探索する第６のプログラムステップとを備えている。
【発明の効果】
【００１９】
　上記第１の発明によれば、走行予定時間帯において通過できないノードまたはリンクを用いた経路は選出されないので、必ず時間規制情報を遵守した経路を選出することができる。
【００２０】
　上記第２の発明によれば、任意の時間をユーザーが選択できるので、ユーザーの希望する時間帯における最適な経路を選出することができる。
【００２１】
　上記第３の発明によれば、ある一定時刻毎に区分した時間帯をディスプレイ上に表示して、その時間帯を選択するので、ユーザーの入力作業が簡単となり、ユーザーの負担を軽減することができる。
【００２２】
　上記第４の発明によれば、ユーザーが入力した出発予定時刻と、２地点間の直線距離とに基づいて、走行予定時間帯を算出するので、ユーザーは目的地到達時刻を入力する必要がなく、ユーザーの負担を軽減することができる。
【００２３】
　上記第６の発明によれば、走行予定時間帯において通過できないノードまたはリンクを用いた経路は選出されないので、必ず時間規制情報を遵守した経路を選出することができる。
【発明を実施するための最良の形態】
【００２４】
　（第１の実施形態）
　図１は、本発明の第１の実施形態に係るカーナビゲーションシステムの構成を示すブロック図である。図１において、本実施形態のカーナビゲーションシステムは、現在位置検出部１０１と、現在日時取得部１０２と、道路ネットワーク記憶部１０３と、入力部１０４と、時間規制対応探索部１０５と、誘導部１０６とを備えている。
【００２５】
　現在位置検出部１０１は、ＧＰＳ、車速センサ、角速度センサ、絶対方位センサ等を含み、マップマッチング法等を用いて車両の現在位置を計算する。現在日時取得部１０２は、ＧＰＳ、車内時計等から現在日時を取得する。道路ネットワーク記憶部１０３は、交差点や道路の接続状況や座標・形状・属性・規制情報など、道路ネットワークに関する情報を記憶している。入力部１０４は、リモートコントローラ、タッチセンサ、キーボード、マウス等を含み、ユーザの操作に従って地点情報等を入力する。時間規制対応探索部１０５は、ＣＰＵやメモリ（プログラムメモリ、ワーキングメモリ）等を含み、基本的には、現在位置検出部１０１で検出した現在位置および入力部１０４でユーザーが入力した位置情報に基づいて、経路の出発地および目的地を判定する機能と、地図ネットワーク記憶部１０３に記憶された道路ネットワーク上の探索開始点および探索終了点を設定する機能と、設定された探索開始点から探索終了点までの経路を、時間規制情報を反映しつつ、道路ネットワークに基づき選出する機能とを有している。誘導部１０６は、表示装置（液晶ディスプレイ、ＣＲＴディスプレイ等）やスピーカ等を含み、現在位置検出部１０１で検出した車両の現在位置と道路ネットワーク記憶部１０３に記憶された地図データとを用いて、時間規制対応探索部１０５で選択された誘導経路を、画像や音声により誘導案内する。
【００２６】
　ここで、道路ネットワーク記憶部１０３に記録される地図データについて説明する。図２は、地図データの一構成例を示している。図２に示すごとく、地図データは、大きく分けて２つの構成要素からなる。第１の構成要素は、交差点に関する情報であるノードデータである。第２の構成要素は、交差点をつなぐ道路の情報であるリンクデータである。本実施形態では、それぞれのデータの中に、時間規制情報を含んでいる。ここで、時間規制情報とは、定常的に存在する交通規制ではなく、時間的に規制内容が変更されたり、無効となったりするものを指す。時間規制情報としては、例えば下記のような内容が挙げられる。
　　＜ノード時間規制＞７：００〜９：００の間は右折禁止
　　＜リンク時間規制＞１３：００〜２０：００の間は通行止め
本実施形態では、従来、地図データに記録されていた定常的なノード規制情報（右左折禁止情報）やリンク規制情報（一方通行情報）に、規制が有効となる期間情報（開始日時、終了日時等）を付加することにより、時間規制情報を表現している。
【００２７】
　なお、ここで、時間規制情報をまとめて別データとして記録しておいても良いし、必ず地図に記憶しておかなくても、交通情報を受信する交通情報受信部を追加し、移動体通信により外部から規制情報を取得してもよい。
【００２８】
　以上のように構成されたカーナビゲーションシステムについて、以下にその動作を説明する。まず、入力部１０４において、ユーザーは出発地および目的地の設定を行う。すなわち、ユーザーは、入力部１０４を操作することにより、誘導部１０６に表示された地図の画像をスクロールさせ、希望する地点を出発地および目的地として入力する。なお、出発地は、現在位置検出部１０１において検出した車両の現在位置を使用してもよい。
【００２９】
　次に、時間規制対応探索部１０５は、上記のように設定された出発地や目的地の位置に基づき、道路ネットワーク記憶部１０３に記憶された地図上のノードまたはリンク上の一番近い点を、探索開始点および探索終了点として採用する。さらに、時間規制対応探索部１０５は、周知のダイクストラ法などを用いて最短コスト経路を計算し、求められた経路をリンク列またはノード列または座標列に変換し、誘導経路とする。
【００３０】
　最後に、誘導部１０６は、時間規制対応探索部１０５で求められた誘導経路と、現在位置検出部１０１から得られる現在位置と、道路ネットワーク記憶部１０３に記憶された地図データとに基づいて、誘導経路上を進むにはどの方向へ進めば良いかを、音声や表示を行なってユーザーに案内する。
【００３１】
　図３は、図１に示す時間規制対応探索部１０５の構成を示す機能ブロック図である。図３において、この時間規制対応探索部１０５は、探索用データ格納部２０１と、経路探索部２０２と、時間規制反映部２０３とを含む。
【００３２】
　探索用データ格納部２０１は、現在位置検出部１０１や入力部１０４で入力された結果から探索範囲を特定し、道路ネットワーク記憶部１０３から該当探索範囲の地図データを読み込んで格納する。経路探索部２０２は、現在位置検出部１０１や入力部１０４からの入力に基づいて、探索開始点および探索終了点を決定する。ここで、時間規制反映部２０３は、現在日時取得部１０２や入力部１０４からの入力に基づいて、出発地から目的地までの走行予定時間帯を決定し、その時間帯において、探索用データ格納部２０１に格納された地図データの各ノードおよびリンクが通行可能か否かを判定し、当該判定の結果に基づき、地図データ上に規制の有無を書き込む。次に、経路探索部２０２は、時間規制反映部２０３によって規制の有無が書き込まれた地図データに基づいて、探索開始点から探索終了点までの経路を選出する。
【００３３】
　上記のように構成された時間規制対応探索部１０５について、フローチャートに従って以下にその動作を詳述する。図４は、時間規制対応探索部１０５における経路探索部２０２（図３参照）の動作を示すフローチャートである。
【００３４】
　まず、図４のステップＳ５００１において、経路探索部２０２は、例えば、現在位置検出部１０１で検出された車両の現在地を出発地に、入力部１０４で入力された位置を目的地に設定する。次に、経路探索部２０２は、道路ネットワーク記憶部１０３から出発地と目的地を含む探索範囲の地図データを読み出して格納するように、探索用データ格納部２０１を制御する（ステップＳ５００２）。次に、経路探索部２０２は、探索用データ格納部２０１に格納された地図データ上で、出発地に一番近いリンク上の点を探索開始点として、また目的地に一番近いリンク上の点を探索終了点として採用する（ステップＳ５００３）。
【００３５】
　次に、経路探索部２０２は、ステップＳ５００４において、時間規制反映部２０３に時間規制反映処理を実行させる。このステップＳ５００４では、時間規制反映部２０３は、移動時間帯を取得し、時間規制情報に基づいて探索用データ格納部２０１に格納された地図データ上のノードおよびリンクに通行禁止情報を書き込む。
【００３６】
　図５は、図４におけるサブルーチンステップＳ５００４（時間規制反映処理）の詳細を示すフローチャートである。以下、図５を参照して、時間規制反映部２０３の動作をより詳細に説明する。
　まず、ステップＳ５１０１において、時間規制反映部２０３は、出発地から目的地に移動する時間帯をユーザーに問い合わせる。例えば、図６（ａ）に示すような表示画面を誘導部１０６のディスプレイ上に表示し、入力部１０４によりユーザーに時間帯を数値で入力させても良い。また、図６（ｂ）に示すように、ある一定時間で区分した時間帯の棒グラフを誘導部１０６のディスプレイ上に表示し、入力部１０４の操作により時間帯を選択させてもよい。また、現在日時取得部１０２または入力部１０４から入手した出発予定時刻と、出発地−目的地間の直線距離および予め仮定した平均移動速度（例えば、行程が１００ｋｍ以上でかつ高速優先利用モードの場合は６０ｋｍ／ｈ、それ以外の場合は３０ｋｍ／ｈ）から算出した目的地までの所要時間とに基づいて、移動する時間帯を計算してもよい。
【００３７】
　次に、時間規制反映部２０３は、探索用データ格納部２０１に収納された地図データの全ノードおよびリンクの時間規制の有効性を調査したか否かをチェックし（ステップＳ５１０２）、調査済みでなければ調査を続行し、調査済みであれば時間規制反映処理を終了する。時間規制の有効性の調査が済んでいないノードまたはリンクが存在する場合、時間規制反映部２０３は、該当ノードおよびリンクに時間規制が存在し、かつ、規制時間帯がステップＳ５１０１で取得した移動時間帯に一部でも重なるか否かを判断し（ステップＳ５１０３）、重なればステップＳ５１０４に進み、それ以外の場合はステップＳ５１０２に戻る。ステップＳ５１０４では、時間規制反映部２０３は、時間規制情報の内容を定常的な規制と見なして、地図データ上に通行禁止情報等を書き込む。その後、時間規制反映部２０３は、ステップＳ５１０２に戻り、以上の処理を繰り返す。
【００３８】
　再び図４に戻り、経路探索部２０２は、周知のダイクストラ法などを用いて、探索用データ格納部２０１に格納された地図データから通行規制を遵守して探索処理を行い、最短コスト経路を計算する（ステップＳ５００５）。次に、経路探索部２０２は、求められた経路をリンク列またはノード列または座標列に変換し、誘導経路として誘導部１０６に出力する（ステップＳ５００６）。
【００３９】
　以上のように、第１の実施形態によれば、探索時に読み込まれた地図データ上の各ノードおよびリンクにおいて、移動時間帯に基づいて時間規制が有効かどうかを判定するようにしているので、必ず時間規制情報を遵守した経路を選出することができる。
　また、移動時間帯に関する時間情報を、ユーザーに入力させるようにしているので、ユーザーの希望する任意の時間帯において、適切な経路を選出することができる。
　さらに、移動時間帯をユーザーに入力させる場合に、ある一定時間毎に区分した時間帯をディスプレイ上に表示し、その時間帯を選択させることにより、移動時間帯の入力処理を簡素化でき、ユーザーの負担が軽減できる。
　最後に、出発地から目的地までの直線距離に基づいて算出した目的地までの所要時間と出発予定時刻情報とから移動時間帯を計算することにより、移動時間帯の入力処理を簡素化でき、ユーザーの負担を一層軽減できる。
【００４０】
　なお、第１の実施形態では、移動時間帯に関するユーザー入力処理を、探索開始点・探索終了点設定処理の後に行うようにしたが、出発地・目的地の地点入力時に同時に行っても良いし、探索処理の前であればいつ行っても構わない。また、第１の実施形態では、時間規制を地図データに反映させる処理を、探索開始点・探索終了点設定処理の後に行うようにしたが、探索開始点・探索終了点設定処理前に行い、時間規制を反映した地図データを用いて、探索開始点・探索終了点設定処理を行っても構わない。また、第１の実施形態では、時間規制情報が有効な場合、地図データ上に通行禁止情報を書き込んだが、規制内容によっては、ノードおよびリンクの通過コストを予め決められた値に変更する等の処理を行っても良い。
【００４１】
　（第２の実施形態）
　以下には、本発明の第２の実施形態に係るカーナビゲーションシステムについて説明するが、システム全体の構成は、図１に示す第１の実施形態と同様であるので、以下の説明では図１を援用することとし、システム全体の図示を省略する。第２の実施形態は、図１における時間規制対応探索部１０５の機能が第１の実施形態と異なっているので、以下には、時間規制対応探索部１０５の機能を中心に第２の実施形態の説明を行う。
【００４２】
　図７は、本発明の第２の実施形態のカーナビゲーションシステムで用いられる時間規制対応探索部１０５の構成を示す機能ブロック図である。図７において、この時間規制対応探索部１０５は、探索用データ格納部３０１と、経路探索部３０２と、基準日時情報決定部３０４と、時間規制判定補正部３０５とを備えている。
【００４３】
　探索用データ格納部３０１は、現在位置検出部１０１や入力部１０４で入力された結果から探索範囲を特定し、道路ネットワーク記憶部１０３から該当探索範囲の地図データを読み込んで格納する。経路探索部３０２は、現在位置検出部１０１や入力部１０４からの入力に基づいて探索開始点および探索終了点を決定する。ここで、基準日時情報決定部３０４は、各ノードおよびリンクへの到達時刻を算出する基準点の基準時刻を決定するための基準日時情報を、現在日時取得部１０２または入力部１０４からの入力に基づいて決定する。次に、時間規制判定補正部３０５は、基準日時情報決定部３０４で決定された基準日時情報を基に算出した基準点の基準時刻と、探索用データ格納部３０１に格納された地図データから得た基準点と時間規制が存在する各ノードおよびリンクとの間の距離に基づいて算出した基準点からの所要時間とにより到達時刻を推定する。さらに、時間規制判定補正部３０５は、その到達時刻において、探索用データ格納部３０１に格納された地図データの各ノードおよびリンクが通行可能か否かを判定し、当該判定結果（規制の有無）を地図データに書き込む。次に、経路探索部３０２は、時間規制判定補正部３０５によって規制の有無が書き込まれた地図データに基づいて、探索開始点から探索終了点までの経路を選出する。
【００４４】
　上記のように構成された第２の実施形態における時間規制対応探索部１０５について、以下にその動作を詳述する。図８は、図７における経路探索部３０２の動作を示すフローチャートである。
【００４５】
　まず、図８のステップＳ５２０１において、経路探索部３０２は、例えば、現在位置検出部１０１で検出された車両の現在地を出発地に、入力部１０４で入力された位置を目的地に設定する。次に、経路探索部３０２は、道路ネットワーク記憶部１０３から出発地と目的地を含む探索範囲の地図データを読み出して格納するように、探索用データ格納部３０１を制御する（ステップＳ５２０２）。次に、経路探索部３０２は、探索用データ格納部３０１に格納された地図データ上で、出発地に一番近いリンク上の点を探索開始点として、また目的地に一番近いリンク上の点を探索終了点として採用する（ステップＳ５２０３）。
【００４６】
　次に、経路探索部３０２は、ステップＳ５２０４において、基準日時情報決定部３０４に基準日時情報決定処理を実行させる。このステップＳ５２０４では、基準日時情報決定部３０４は、基準点における基準日時を決定する。
【００４７】
　図９は、図８におけるサブルーチンステップＳ５２０４（基準日時情報決定処理）の詳細を示すフローチャートである。以下、図９を参照して、基準日時情報決定部３０４の動作をより詳細に説明する。
【００４８】
　まず、ステップＳ５３０１において、基準日時情報決定部３０４は、基準点として出発地を採用する。次に、基準日時情報決定部３０４は、基準点での基準時刻の入力をユーザーに促す（ステップＳ５３０２）。次に、基準日時情報決定部３０４は、基準時刻の入力があるか否かを判断し（ステップＳ５３０３）、入力があればその時刻を基準時刻とし、入力がなければステップＳ５３０４の処理を行う。ステップＳ５３０４では、基準日時情報決定部３０４は、現在日時取得部１０２から取得した現在日時を基準時刻とする。以上で、基準日時情報決定部３０４は、基準日時情報決定処理を終了する。
【００４９】
　再び図８に戻り、経路探索部３０２は、時間規制判定補正部３０５に、時間規制判定補正処理を実行させる（ステップＳ５２０５）。時間規制判定補正部３０５は、時間規制判定補正処理として、探索用データ格納部３０１に収納された地図データの全ノードおよびリンクの時間規制の有効性を調査し、有効であれば定常的な規制として地図データを修正する。
【００５０】
　図１０は、図８におけるサブルーチンステップＳ５２０５（時間規制判定補正処理）の詳細を示すフローチャートである。以下、図１０を参照して、時間規制判定補正部３０５の動作をより詳細に説明する。
【００５１】
　まず、時間規制判定補正部３０５は、探索用データ格納部３０１に収納された地図データの全ノードおよびリンクの時間規制の有効性を調査したかどうかをチェックし（ステップＳ５０４１）、調査済みでなければ調査を続行し、調査済みであれば時間規制判定補正処理を終了する。このとき、調査済みでないノードまたはリンクが存在する場合、時間規制判定補正部３０５は、探索用データ格納部３０１に格納された地図データを基に、基準点（出発地）から時間規制情報が存在する各ノードおよびリンクまでの直線距離を求めて、予め仮定した平均移動速度（例えば、行程が１００ｋｍ以上でかつ高速優先利用モードの場合は６０ｋｍ／ｈ、それ以外の場合は３０ｋｍ／ｈ）を用いて、基準点（出発地）から各ノードおよびリンクまでの所要時間を計算し、基準日時情報決定部３０４から得た基準時刻に、この所要時間を加算することで、各ノードおよびリンクへの推定到達時刻を算出する（ステップＳ５４０２）。次に、時間規制判定補正部３０５は、該当ノードおよびリンクに時間規制が存在し、かつ、ステップＳ５４０２で算出した推定到達時刻が規制時間帯に含まれるか否かを判定し（ステップＳ５４０３）、含まれればステップＳ５４０４に進み、それ以外の場合はステップＳ５４０１に戻る。ステップＳ５４０４では、時間規制判定補正部３０５は、時間規制情報の内容を定常的な規制と見なして、通行禁止情報等を地図データ上に書き込む。さらに、時間規制判定補正部３０５は、ステップＳ５４０１に戻り、以上の処理を繰り返す。
【００５２】
　再び図８に戻り、経路探索部３０２は、周知のダイクストラ法などを用いて、探索用データ格納部３０１に格納された地図データから通行規制を遵守した探索処理を行って最短コスト経路を計算し（ステップＳ５２０６）、求められた経路をリンク列またはノード列または座標列に変換し、誘導経路として誘導部１０６に出力する（ステップＳ５２０７）。
【００５３】
　以上のように、第２の実施形態によれば、少なくとも１つ以上の基準点の基準時刻と、その基準点から各地点に至る経路上の推定旅行時間とから、各地点への到達時刻を算出し、当該算出した到達時刻に基づいて、時間規制が有効かどうかを判定するようにしているので、経路上の移動による時間の推移を考慮した適切な経路を選出することができる。
【００５４】
　なお、経路上の推定旅行時間は、概算演算（例えば、経路上の出発地・目的地・経由地を基準点とし、これら基準点から各地点への直線距離を、予め仮定した平均速度で割るような演算）により求めるようにしても良い。
　さらに、基準日時情報を現在時刻とすることで、ユーザーの入力作業が不要となり、ユーザーの負担が軽減できる。
　なお、第２の実施形態では、基準点として出発地を採用したが、経由地・目的地を採用しても良いし、現在車両位置を採用しても良い。ただし、基準点として目的地を採用した場合は、各地点への到達時刻を算出する処理は、基準時刻から経路上の推定旅行時間を減算して求めることになる。また、基準時刻の決定は、ユーザー入力のみに基づいてもよいし、現在時刻のみに基づいてもよい。また、現在時刻に基づく場合、車両の現在位置から基準点までの距離に基づいた推定移動時間を加算してもよい。また、時間規制情報が有効な場合、地図データ上に通行禁止情報を書き込むようにしたが、規制内容によっては、ノードおよびリンクの通過コストを、予め決められた値に変更する等の処理を行っても良い。
【００５５】
　（第３の実施形態）
　以下には、本発明の第３の実施形態に係るカーナビゲーションシステムについて説明するが、システム全体の構成は、図１に示す第１の実施形態と同様であるので、以下の説明では図１を援用することとし、システム全体の図示を省略する。第３の実施形態は、図１における時間規制対応探索部１０５の機能が第１の実施形態と異なっているので、以下には、時間規制対応探索部１０５の機能を中心に第３の実施形態の説明を行う。
【００５６】
　図１１は、本発明の第３の実施形態のカーナビゲーションシステムで用いられる時間規制対応探索部１０５の構成を示す機能ブロック図である。図１１において、この時間規制対応探索部１０５は、探索用データ格納部４０１と、経路探索部４０２と、基準日時情報決定部４０４と、時間規制判定部４０５とを備えている。
【００５７】
　探索用データ格納部４０１は、現在位置検出部１０１や入力部１０４で入力された結果から探索範囲を特定し、道路ネットワーク記憶部１０３から該当探索範囲の地図データを読み込んで格納する。経路探索部４０２は、現在位置検出部１０１や入力部１０４からの入力に基づいて、探索開始点および探索終了点を決定する。ここで、基準日時情報決定部４０４は、各ノードおよびリンクへの到達時刻を算出する基準点の基準時刻を決定するための基準日時情報を、現在日時取得部１０２または入力部１０４または探索用データ格納部４０１からの入力に基づいて決定する。さらに、経路探索部４０２は、探索用データ格納部４０１に格納された地図データに基づいて経路を選出する。その際、時間規制判定部４０５は、経路探索部４０２での経路探索処理中に、基準日時情報決定部４０４で決定された時刻を基に、探索用データ格納部４０１に格納された地図データや経路探索結果を基に、各ノードおよびリンクへの到達時刻を算出し、規制が有効かどうかを判定する。
【００５８】
　上記のように構成された第３の実施形態における時間規制対応探索部１０５について、以下にその動作を詳述する。図１２は、図１１における経路探索部４０２の動作を示すフローチャートである。
【００５９】
　まず、図１２のステップＳ５５０１において、経路探索部４０２は、例えば、現在位置検出部１０１で検出された車両の現在地を出発地に、入力部１０４で入力された位置を目的地に設定する。次に、経路探索部４０２は、道路ネットワーク記憶部１０３から出発地と目的地を含む探索範囲の地図データを読み出して格納するように、探索用データ格納部４０１を制御する（ステップＳ５５０２）。次に、経路探索部４０２は、探索用データ格納部４０１に格納された地図データ上で、出発地に一番近いリンク上の点を探索開始点として採用し、また目的地に一番近いリンク上の点をもう一つの探索開始点として採用する（ステップＳ５５０３）。
【００６０】
　次に、経路探索部４０２は、ステップＳ５５０４において、基準日時情報決定部４０４に基準日時情報決定処理を実行させる。このステップＳ５５０４では、基準日時情報決定部４０４は、基準点における基準日時を決定する。
【００６１】
　図１３は、上記サブルーチンステップＳ５５０４の詳細を示すフローチャートである。以下、図１３を参照して、基準日時情報決定部４０４の動作をより詳細に説明する。
【００６２】
　まず、ステップＳ５６０１において、基準日時情報決定部４０４は、基準点として出発地と目的地を採用する。次に、基準日時情報決定部４０４は、出発地側の基準時刻の入力をユーザーに促す（ステップＳ５６０２）。次に、基準日時情報決定部４０４は、基準時刻の入力があるか否かを判断し（ステップＳ５６０３）、入力があればその時刻を出発地側の基準時刻とし、入力がなければステップＳ５６０４の処理を行う。ステップＳ５６０４では、基準日時情報決定部４０４は、現在日時取得部１０２から取得した現在日時を出発地側の基準時刻とする。次に、基準日時情報決定部４０４は、探索用データ格納部４０１に格納された地図データを基に出発地から目的地までの直線距離を求め、予め仮定した平均移動速度（例えば、行程が１００ｋｍ以上でかつ高速優先利用モードの場合は６０ｋｍ／ｈ、それ以外の場合は３０ｋｍ／ｈ）を用いて、出発地から目的地までの移動所要時間を概算し、出発地の基準時刻に加算することにより、目的地の基準時刻を求める（ステップＳ５６０５）。基準日時情報決定部４０４は、以上で基準日時情報決定処理を終了する。
【００６３】
　再び図１２に戻り、経路探索部４０２は、探索用データ格納部４０１に格納された地図データに基づいて、例えば周知の双方向探索手法等を用いて、探索開始点から探索終了点までの最短経路を選出する（ステップＳ５５０５、ステップＳ５５０６）。
【００６４】
　ここで、図１４を参照して、双方向探索手法を説明する。図１４（ａ）は出発地を基準とした一方向探索手法の概念図であり、図１４（ｂ）は双方向探索手法の概念図である。このように、双方向探索手法とは、出発地側を起点とした一方向探索と、目的地側を起点とした一方向探索を行い、双方の経路を組み合わせて一本の経路を構成することにより、探索範囲を縮小し、探索時間の短縮を図るものである。本手法において、出発地を基準とした探索範囲を出発地側探索範囲、目的地を基準とした探索範囲を目的地側探索範囲と呼ぶ。
【００６５】
　ここで、出発地側探索範囲の時間規制対応探索処理を目的地側とは区別して、出発地側時間規制対応探索処理と表記する。まず、出発地側時間規制対応探索処理（ステップＳ５５０５）から説明する。
【００６６】
　図１５は、図１２におけるサブルーチンステップＳ５５０５（出発地側時間規制対応探索処理）の詳細を示すフローチャートである。本処理は、ステップＳ５７０１〜Ｓ５７１０で構成されているが、殆どの部分は最短コスト経路を選出するための処理であり、公知のダイクストラ手法そのものであるので、その部分の説明は省略する。本処理で重要なのは、ステップＳ５７０６、ステップＳ５７０７の処理である。経路探索部４０２は、探索を広げる基準となる探索対象ノードを選出し（ステップＳ５７０３）、探索対象ノードに接続する各リンクに対して探索処理を広げる際に、算出した探索対象ノードへの到達時刻に基づいて時間規制が有効かどうか判定する出発地側時間規制判定処理（ステップＳ５７０６）を、時間規制判定部４０５に実行させ、その結果に基づいて該当リンクに対して探索処理を行うかどうかを決定する（ステップＳ５７０７）。これにより、時間規制が有効であれば、その方向へ探索処理が広がらないので、選出された経路は規制を遵守した経路のみとなる。
【００６７】
　図１６は、図１５におけるサブルーチンステップＳ５７０６（時間規制判定部４０５により実行される出発地側時間規制判定処理）の詳細を示すフローチャートである。以下、図１６を参照して、出発地側時間規制判定処理について説明する。
【００６８】
　まず、ステップＳ５８０１において、時間規制判定部４０５は、出発地側の基準時間に出発地→探索対象ノードまでの経路上のコストを加算することにより、探索対象ノードまたはリンクへの到達時刻を求める。ただし、これは探索を行うコストが旅行時間で表現されている場合であり、例えばコストが距離で表現されている場合は平均速度で除算する等、旅行時間に変換する処理が必要となる。次に、時間規制判定部４０５は、該当ノードおよびリンクに時間規制が存在し、かつ、ステップＳ５８０１で算出した推定到達時刻が規制時間帯に含まれるか否かを判断し（ステップＳ５８０２）、含まれればステップＳ５８０３に進み、それ以外の場合は本処理を終了して図１５のステップ５７０７に戻る。ステップＳ５８０３では、時間規制判定部４０５は、到達時刻において時間規制は有効であるため、通行不可能と判定する。その後、本処理が終了し、経路探索部４０２は、図１５のステップ５７０７に戻る。
　以上で、出発地側時間規制対応探索処理（図１２のステップＳ５５０５）の説明を終了する。
【００６９】
　次に、目的地側時間規制対応探索処理（図１２のサブルーチンステップＳ５５０６）について説明する。図１７は、図１２におけるサブルーチンステップＳ５６０６の詳細を示すフローチャートである。図１８は、図１７におけるサブルーチンステップＳ５９０６（時間規制判定部４０５により実行される目的地側時間規制判定処理）の詳細を示すフローチャートである。これらは、目的地を探索開始点とする以外は、出発地側時間規制対応探索処理と殆ど同じ処理となるので、詳しい説明は省略する。特に、出発地側と違う点は、図１８のステップＳ６００１において、探索対象ノードおよびリンクへの到達時刻を計算する手法である。すなわち、目的地側では、目的地の基準時刻から目的地→探索対象ノードまでの経路上のコストを減算することにより、探索対象ノードおよびリンクへの到達時刻を求める。ただし、これは探索を行うコストが旅行時間で表現されている場合であり、例えばコストが距離で表現されている場合は平均速度で除算する等、旅行時間に変換する処理が必要となる。
　以上で、目的地側時間規制対応探索処理（図１２のステップＳ５５０６）の説明を終了する。
【００７０】
　最後に図１２に戻り、経路探索部４０２は、ステップＳ５５０５とステップＳ５５０６で求められた経路を、リンク列またはノード列または座標列に変換し、誘導経路として誘導部１０６に出力する（ステップＳ５５０７）。
【００７１】
　ここで、図１９を参照して、これらの時間規制対応探索処理（ステップＳ５５０５またはステップＳ５５０６）について簡単に説明する。経路探索部４０２の探索処理において、ノードＡから他のノードＢへ探索範囲を広げる際には、ノードＡまでの経路は探索用データ格納部４０１に探索結果として格納されている（例えば、ノードＡへの経路上の一つ前のノードはノードＣであり、到達コストは５００秒である等）が、ノードＡまでの経路情報を利用して、ノードＡまでの経路上の所要時間を算出する。経路を選択する評価コストの単位が所要時間であれば、ノードＡへの到達コストをそのまま用いることができるし、当該単位が距離であれば、道路種別毎の積算距離を計算することにより、予め想定した道路種別毎の平均速度を利用して経路上の所要時間を算出できる。ゆえに、経路探索部４０２において、ノードＡからノードＢへ探索範囲を広げる際に、基準点での基準時刻と、基準点からノードＡまでの経路上の所要時間とから、ノードＡへの到達時刻を算出する。ただし、出発地側探索範囲においては、出発地の基準時刻にノードＡまでの経路上の所要時間を加算し、目的地側探索範囲においては、目的地の基準時刻からノードＡまでの経路上の所要時間を減算する。このようにして算出したノードＡへの到達時刻に基づいて、探索用データ格納部４０１に格納された地図データからノードＡおよびノードＡ・Ｂ間のリンクに存在する時間規制情報を読み出し、通過できるかどうかを判定し、通過できるのであればノードＢへの探索を広げ、通過できないのであればノードＢへの探索を広げない。これにより、時間規制が有効であればその方向へ探索が広がらないので、選出された経路は規制を遵守した経路のみとなる。
【００７２】
　以上のように、第３の実施形態によれば、探索開始点を基準点とし、探索処理中に探索結果である各地点への経路情報に基づいて、基準点から各地点への経路上の推定所要時間を算出するようにしているので、推定精度を大幅に向上することができる。
　また、基準点が出発地以外の場合、出発地から基準点までの直線距離から基準点までの移動所要時間を算出し、出発地の基準時刻に加算して基準点の基準時刻を算出するようにしているので、ユーザーの入力作業が不要となり、ユーザーの負担が軽減できる。
【００７３】
　なお、第３の実施形態では、経路探索時に、双方向探索を行うようにしているが、出発地側からの一方向探索、または目的地側からの一方向探索を行うようにしても良い。また、基準点として出発地と目的地を採用しているが、現在車両位置・経由地等を基準点としても構わない。その場合、現在車両位置・出発地・経由地・目的地の位置関係を考慮して、走行順に各移動所要時間を推定して基準点での基準時刻を算出してもよい。また、リンクの時間規制情報の有効性を判定する場合、リンクに進入する時刻だけではなく、リンクを通過しきった時刻まで考慮して通過可能かどうか判定してもよい。また、基準時刻の決定は、ユーザー入力のみに基づいてもよいし、現在時刻のみに基づいてもよい。また、現在時刻に基づく場合、車両の現在位置から基準点までの距離に基づいた推定移動時間を加算してもよい。また、時間規制情報が有効な場合、地図データ上に通行禁止情報を書き込んだが、規制内容によっては、ノードおよびリンクの通過コストを予め決められた値に変更する等の処理を行っても良い。
【００７４】
　（第４の実施形態）
　以下には、本発明の第４の実施形態に係るカーナビゲーションシステムについて説明するが、システム全体の構成は、図１に示す第１の実施形態と同様であるので、以下の説明では図１を援用することとし、システム全体の図示を省略する。第４の実施形態は、図１における時間規制対応探索部１０５の機能が第１の実施形態と異なっているので、以下には、時間規制対応探索部１０５の機能を中心に第４の実施形態の説明を行う。
【００７５】
　図２０は、本発明の第４の実施形態のカーナビゲーションシステムで用いられる時間規制対応探索部１０５の構成を示す機能ブロック図である。図２０において、この時間規制対応探索部１０５は、探索用データ格納部５０１と、経路探索部５０２と、基準日時情報決定部５０４と、時間規制判定部５０５と、探索起動部５０６とを備えている。
【００７６】
　探索用データ格納部５０１は、現在位置検出部１０１や入力部１０４で入力された結果から探索範囲を特定し、道路ネットワーク記憶部１０３から該当探索範囲の地図データを読み込んで格納する。経路探索部５０２は、現在位置検出部１０１や入力部１０４からの入力に基づいて、探索開始点および探索終了点を決定する。ここで、基準日時情報決定部５０４は、各ノードおよびリンクへの到達時刻を算出する基準点の基準時刻を決定するための基準日時情報を、現在日時取得部１０２または入力部１０４または探索用データ格納部５０１からの入力に基づいて決定する。さらに、経路探索部５０２は、探索用データ格納部５０１に格納された地図データに基づいて経路を選出する。その際、時間規制判定部５０５は、経路探索部５０２での経路探索処理中に、基準日時情報決定部５０４で決定された時刻，探索用データ格納部５０１に格納された地図データ，経路探索結果を基に、各ノードおよびリンクへの到達時刻を算出し、規制が有効かどうかを判定する。探索起動部５０６は、誘導案内中に現在位置検出部１０１や現在日時取得部１０２で得られた情報から、予め決められたタイミングで現在位置から目的地までの探索を起動する。
【００７７】
　上記のように構成された第４の実施形態における時間規制対応探索部１０５について、以下にその動作を詳述する。第３の実施形態と本実施形態との違いは、探索起動部５０６の処理と、それに伴なった基準日時情報決定部５０４の処理だけであるので、その差異をフローチャートに従って説明する。図２１は、図２０における探索起動部５０６の動作を示すフローチャートである。
【００７８】
　第３の実施形態の説明に従い、目的地までの経路を求めた上で、誘導案内中に図２１に示す処理を行う。まず、ステップＳ６１０１において、探索起動部５０６は、現在位置検出部１０１から車両の現在位置を、また、現在日時取得部１０２から現在日時を取得する。次に、探索起動部５０６は、取得した車両の現在位置から目的地に到着したか否かを判定し（ステップＳ６１０２）、到着したならば処理を終了し、到着していなければステップＳ６１０３に進む。ステップＳ６１０３において、探索起動部５０６は、現在日時と車両の現在位置から探索起動タイミングの条件を満たしているか否かを判定する。ここで、探索起動タイミングの条件は、ステップＳ６１０１で取得した車両の現在位置および現在日時を用いて算出した前回探索時からの車両の移動距離および経過時間に基づき、予め決められているものとする（例えば、前回探索時から２０分経過、または１０ｋｍ移動した時等）。探索起動部５０６は、ステップＳ６１０３の判断の結果、探索タイミングの条件が満たされていなければステップＳ６１０１に戻って処理を繰り返し、条件が満たされていればステップＳ６１０４に進む。
【００７９】
　ステップＳ６１０４において、探索起動部５０６は、前回の探索により求められた経路情報から目的地への到達予定時刻を算出し、目的地の基準時刻として探索用データ格納部５０１に格納する。ここで、経路を選択する評価コストの単位が旅行時間であれば、目的地への到達コストをそのまま用いることができるし、当該単位が距離であれば、道路種別毎の積算距離を計算することにより、予め想定した道路種別毎の平均速度を利用して経路上の所要時間を算出できる。次に、探索起動部５０６は、現在位置を出発地、現在日時を出発地の基準時刻として、探索用データ格納部５０１に格納する（ステップＳ６１０５）。その上で、第３の実施形態で説明した時間規制対応探索処理（図１２に記載）を起動する。ただし、出発地や目的地の位置情報，基準時刻情報等は、既に上記で設定された値を用いる。時間規制対応探索処理が終了したならば、探索起動部５０６は、ステップＳ６１０１に戻り、上記の処理を目的地に到達するまで繰り返す。
【００８０】
　以上のように、第４の実施形態によれば、推定した各地点への到達時刻と実到達時刻との誤差が大幅に拡大する前に、予め決められたタイミングで経路探索処理を繰り返し、時間規制を遵守した経路を求め直すことにより、通れるべき誘導経路上の地点が、実際には到達時刻の推定誤差のため通れないという現象を防ぐことができる。
　また、予め探索した結果から目的地への到達時間を推定して、目的地の基準時刻を計算することにより、直線距離等から目的地の基準時刻を推定する場合よりも、推定精度を向上させることができ、目的地側探索範囲の時間規制の反映を正確にすることができる。
【００８１】
　なお、第４の実施形態では、経路探索時に双方向探索を行うようにしたが、出発地側または目的地側から一方向探索を行うようにしても良い。また、基準点として出発地と目的地を採用したが、現在車両位置・経由地等を基準点として採用しても構わない。その場合、現在車両位置・出発地・経由地・目的地の位置関係を考慮して、走行順に各移動所要時間を推定して基準点での基準時刻を算出してもよい。また、リンクの時間規制情報の有効性を判定する場合、リンクに進入する時刻だけではなく、リンクを通過しきった時刻まで考慮して通過可能かどうかを判定してもよい。また、基準時刻の決定は、ユーザー入力のみに基づいてもよいし、現在時刻のみに基づいてもよい。また、現在時刻に基づく場合、車両の現在位置から基準点までの距離に基づいた推定移動時間を加算してもよい。また、再探索を行うタイミングを移動距離と時間で決定したが、到達時間の推定誤差が拡大する前であればどのようなタイミングでも構わない。さらに、一番最初の探索時は目的地側の基準時刻の推定を出発地からの直線距離に基づいて計算したが、目的地までの予備探索（時間規制を反映しない探索）を行い候補経路を選出して到達時間を計算した後で、本探索を行っても構わない。
【００８２】
　（第５の実施形態）
　以下には、本発明の第５の実施形態に係るカーナビゲーションシステムについて説明するが、システム全体の構成は、図１に示す第１の実施形態と同様であるので、以下の説明では図１を援用することとし、システム全体の図示を省略する。第５の実施形態は、図１における時間規制対応探索部１０５の機能が第１の実施形態と異なっているので、以下には、時間規制対応探索部１０５の機能を中心に第５の実施形態の説明を行う。
【００８３】
　図２２は、本発明の第５の実施形態のカーナビゲーションシステムで用いられる時間規制対応探索部１０５の構成を示す機能ブロック図である。図２２において、この時間規制対応探索部１０５は、探索用データ格納部６０１と、経路探索部６０２と、基準日時情報決定部６０４と、適用範囲限定時間規制判定部６０５と、探索起動部６０６とを備えている。
【００８４】
　探索用データ格納部６０１は、現在位置検出部１０１や入力部１０４で入力された結果から探索範囲を特定し、道路ネットワーク記憶部１０３から該当探索範囲の地図データを読み込んで格納する。経路探索部６０２は、現在位置検出部１０１や入力部１０４からの入力に基づいて、探索開始点および探索終了点を決定する。ここで、基準日時情報決定部６０４は、各ノードおよびリンクへの到達時刻を算出する基準点の基準時刻を決定するための基準日時情報を、現在日時取得部１０２または入力部１０４または探索用データ格納部２０１からの入力に基づいて決定する。さらに、経路探索部６０２は、探索用データ格納部６０１に格納された地図データに基づいて経路を選出する。その際、適用範囲限定時間規制判定部６０５は、出発地から一定範囲内の各ノードおよびリンクを対象として、経路探索部６０２での経路探索処理中に、基準日時情報決定部６０４で決定された時刻，探索用データ格納部６０１に格納された地図データ，経路探索結果を基に、各ノードおよびリンクへの到達時刻を算出し、規制が有効かどうかを判定する。探索起動部６０６は、誘導案内中に現在位置検出部１０１や現在日時取得部１０２で得られた情報から、予め決められたタイミングで現在位置から目的地までの探索を起動する。
【００８５】
　上記のように構成された第５の実施形態における時間規制対応探索部１０５について、以下にその動作を詳述する。第４の実施形態と本実施形態との違いは、適用範囲限定時間規制判定部６０５の処理だけであるので、その差異をフローチャートに従って説明する。図２３は、図２２における適用範囲限定時間規制判定部６０５の動作を示すフローチャートである。
【００８６】
　図２３のフローチャートが、第４の実施形態の時間規制判定部５０５の動作（実質的には、第３の実施形態における時間規制判定部４０５の動作を示す図１６と同じ）と異なるのは、ステップＳ６２０１が最初に追加された点である。ステップＳ６２０１において、適用範囲限定時間規制判定部６０５は、目的地が出発地から予め決められた範囲内（例えば、出発地から６０分以内）にあるか否かを判断し、範囲内であれば、ステップＳ６２０２に進み、時間規制の有効性を判定する処理を続行するが、出発地から予め決められた範囲外であれば、時間規制の有効性を判定する処理を中断する。なお、ここでは、出発地側の探索範囲は時間規制を反映する予め決められた範囲よりも十分広いとして、図２３のフローチャートは出発地を基準点とした場合のみ示した。これにより、予め決められた範囲内のみに時間規制情報を反映させ、それ以外の範囲には時間規制の判定は行わないものとする。その上で、探索起動部６０６は、経路誘導中にあるタイミング（上記の予め決められた範囲を走行する時間よりは十分短いもの）で探索処理を起動し、経路探索部６０２で目的地までの経路を選出し直す。
【００８７】
　以上のように、第５の実施形態によれば、出発地から予め決められた範囲のみの時間規制情報に関して経路探索に反映することにより、探索時の処理負荷を軽減し、探索時間を短縮化することができる。
　なお、第５の実施形態では、時間規制を判定する予め決められた範囲を出発地からの一定時間で決定したが、広すぎない範囲であればよく、距離で制限してもよいし、地図の記録範囲で制限してもよい。また、出発地側の探索範囲は、時間規制を反映する予め決められた範囲よりも十分広いものとして、図２３のフローチャートは出発地を基準点とした場合のみを示したが、目的地を基準点とした場合にも探索対象ノードおよびリンクへの到達時間の算出法を目的地側用にすることにより、同様に適用できる。
【００８８】
　なお、以上説明した全ての実施形態において、以上に説明した各機能ブロックは、ハードウェアによって構成されても良いし、マイクロコンピュータのマルチタスクなどのプログラム処理の結果として構成されても良い。
【００８９】
　また、道路ネットワーク記憶部１０３には、階層化した地図を記録しておき、時間規制対応探索部１０５は、出発地・目的地周辺は詳細地図で、その間の長距離経路は距離に応じて詳細度の異なる地図を用いて探索を行うようにしても良い。
　また、経路探索部２０２〜６０２における経路探索処理は、出発地側からの一方向探索に限らず、目的地側からの一方向探索でも良いし、双方向探索でも良い。
　また、現在位置検出部１０１は、現在位置が検出できる構成であればどのような構成でも良い。
　また、現在日時取得部１０２は、ＧＰＳの時刻情報や車内時計からの情報を用いて現在時刻を得ているが、コンピュータのクロックを積算して現在時刻を計算しても良く、原理的には現在時刻が得られればどのような構成でも良い。
　また、入力部１０４は、誘導部１０６に表示された地図の画像をスクロールさせることで位置を指定するようにしているが、予め記憶した緯度経度を選択する方法で位置を指定しても良く、原理的には位置が特定できれば良い。
　また、時間規制対応探索部１０５は、最初の探索時には出発地、目的地にそれぞれ近い点を探索開始点または探索終了点としているが、それぞれに複数の地点を設定するようにしても良い。
　また、探索手法として、ここではダイクストラ法を例に挙げたが、リンク毎のコスト情報を基に複数地点間の最短コスト経路を求める方法であれば、どのような方法を用いても良い。
　また、誘導部１０６において、表示や音声により誘導を行うこととしたが、例えば自動操縦部を付加し、選出した経路を自動車の操縦系に与えるようにしても良い。
　さらに、交通情報取得部を付加し、交通情報として提供される時間規制情報を取得して、上記実施形態と同様にして経路探索結果に反映させても良い。
　また、直線距離から経路上の推定所要時間を算出する場合、ここでは平均走行速度を「行程が１００ｋｍ以上でかつ高速優先利用モードの場合は６０ｋｍ／ｈ、それ以外の場合は３０ｋｍ／ｈ」と設定したが、地形等、他の条件を構成要素に含んでもよいし、妥当な値であれば構わない。
【００９０】
　また、本発明は、プログラムによって実現し、これをフロッピー（Ｒ）ディスク等の記録媒体に記録して移送することにより、独立した他のコンピュータ・システムで容易に実施することができる。この場合、記録媒体は、フロッピー（Ｒ）ディスクに限らず、光ディスク、ＩＣカード、ＲＯＭカセット等、プログラムを記録できるものであれば、同様に実施することができる。
【産業上の利用可能性】
【００９１】
　以上のように、本発明は、定常的な交通規制のみならず、時間規制をも考慮し、安心して走行できる最適な経路を選出することができる経路選出方法およびシステム等として利用することができる。
【図面の簡単な説明】
【００９２】
【図１】本発明の第１の実施形態に係るカーナビゲーションシステムの構成を示すブロック図。
【図２】地図データの一構成例を示す図解図。
【図３】第１の実施形態で用いられる時間規制対応探索部のより詳細な構成を示す機能ブロック図。
【図４】図３に示す経路探索部２０２の動作を示すフローチャート。
【図５】図４に示す時間規制反映処理（ステップＳ５００４）の詳細を示すフローチャート。
【図６】入力部１０４における時刻情報の入力方式例を示す図解図。
【図７】本発明の第２の実施形態に係るカーナビゲーションシステムにおいて用いられる時間規制対応探索部の構成を示す機能ブロック図。
【図８】図７に示す経路探索部３０２の動作を示すフローチャート。
【図９】図８に示す基準日時情報決定処理（ステップＳ５２０４）の詳細を示すフローチャート。
【図１０】図８に示す時間規制判定補正処理（ステップＳ５２０５）の詳細を示すフローチャート。
【図１１】本発明の第３の実施形態に係るカーナビゲーションシステムにおいて用いられる時間規制対応探索部の構成を示す機能ブロック図。
【図１２】図１１に示す経路探索部４０２の動作を示すフローチャート。
【図１３】図１１に示す基準日時情報決定部４０４の動作を示すフローチャート。
【図１４】一方向探索手法と双方向探索手法の説明図。
【図１５】図１２に示す出発地側時間規制対応探索処理（ステップＳ５５０５）の詳細を示すフローチャート。
【図１６】図１５に示す出発地側時間規制判定処理（ステップＳ５７０６）の詳細を示すフローチャート。
【図１７】図１２に示す目的地側時間規制対応探索処理（ステップＳ５５０７）の詳細を示すフローチャート。
【図１８】図１７に示す目的地側時間規制判定処理（ステップＳ５９０６）の詳細を示すフローチャート。
【図１９】図３の実施形態において、経路探索部４０２と時間規制判定部４０５の動作を説明するための図解図。
【図２０】本発明の第４の実施形態に係るカーナビゲーションシステムにおいて用いられる時間規制対応探索部の構成を示す機能ブロック図。
【図２１】図２０に示す探索起動部５０６の動作を示すフローチャート。
【図２２】本発明の第５の実施形態に係るカーナビゲーションシステムにおいて用いられる時間規制対応探索部の構成を示す機能ブロック図。
【図２３】図２２に示す適用範囲限定時間規制判定部６０５の動作を示すフローチャート。
【図２４】従来の車両用経路案内装置の構成を示すブロック図。
【図２５】従来の車両用経路案内装置で採用されている道路ネットワークの表現例を説明するための図。
【符号の説明】
【００９３】
１０１　現在位置検出部
１０２　現在日時取得部
１０３　道路ネットワーク記憶部
１０４　入力部
１０５　時間規制対応探索部
１０６　誘導部
２０１、３０１、４０１、５０１、６０１　探索用データ格納部
２０２、３０２、４０２、５０２、６０２　経路探索部
２０３　時間規制反映部
３０４、４０４、５０４、６０４　基準日時情報決定部
３０５　時間規制判定補正部
４０５、５０５　時間規制判定部
５０６　探索起動部
６０５　適用範囲限定時間規制判定部
【図１】
2004004131.tif 000003
【図２】
2004004131.tif 000004
【図３】
2004004131.tif 000005
【図４】
2004004131.tif 000006
【図５】
2004004131.tif 000007
【図６】
2004004131.tif 000008
【図７】
2004004131.tif 000009
【図８】
2004004131.tif 000010
【図９】
2004004131.tif 000011
【図１０】
2004004131.tif 000012
【図１１】
2004004131.tif 000013
【図１２】
2004004131.tif 000014
【図１３】
2004004131.tif 000015
【図１４】
2004004131.tif 000016
【図１５】
2004004131.tif 000017
【図１６】
2004004131.tif 000018
【図１７】
2004004131.tif 000019
【図１８】
2004004131.tif 000020
【図１９】
2004004131.tif 000021
【図２０】
2004004131.tif 000022
【図２１】
2004004131.tif 000023
【図２２】
2004004131.tif 000024
【図２３】
2004004131.tif 000025
【図２４】
2004004131.tif 000026
【図２５】
2004004131.tif 000027