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