経路探索装置
【課題】目的地までの経路が設定された後、経路を再探索する際に、不用に遠回りとなる経路など最適でない経路を探索してしまうことを抑制できる経路探索装置を提供すること。
【解決手段】制御装置３は、交通事象とその位置を示す位置情報を含む交通情報が記憶されており、かつ、経路が設定されている場合、その経路上の交通事象を特定する（Ｓ１０〜Ｓ１１）。次に、出発地及び目的地周辺の最下層の地図データの経路以外の経路上に交通事象がある場合は、交通事象が発生している位置を含む最下層の地図データ（ターゲットデータ）を特定する（Ｓ１２〜Ｓ１５）。そして、現在地（又は目的地）からターゲットデータ内まで階層構造の地図データに基づいて経路を再探索すると共に、ターゲットデータ内から目的地（又は現在地）まで階層構造の地図データに基づいて経路を再探索して、これらの再探索結果によって経路を作成する（Ｓ１６、Ｓ１７）。
【解決手段】制御装置３は、交通事象とその位置を示す位置情報を含む交通情報が記憶されており、かつ、経路が設定されている場合、その経路上の交通事象を特定する（Ｓ１０〜Ｓ１１）。次に、出発地及び目的地周辺の最下層の地図データの経路以外の経路上に交通事象がある場合は、交通事象が発生している位置を含む最下層の地図データ（ターゲットデータ）を特定する（Ｓ１２〜Ｓ１５）。そして、現在地（又は目的地）からターゲットデータ内まで階層構造の地図データに基づいて経路を再探索すると共に、ターゲットデータ内から目的地（又は現在地）まで階層構造の地図データに基づいて経路を再探索して、これらの再探索結果によって経路を作成する（Ｓ１６、Ｓ１７）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層構造化された地図データを用いて経路探索を行う経路探索装置に関するものである。
【背景技術】
【０００２】
従来、経路探索に用いる地図データは、複数の階層構造を有するものがある。その階層構造の一例としては、レイヤ１、レイヤ２、レイヤ３のように３階層構造がある。この３階層構造は、すべての地図データからなる下位階層であるレイヤ１、高速・有料道路、国道、県道からなる中位階層であるレイヤ２、高速・有料道路、国道からなる上位階層であるレイヤ３などを有する。そして、上位階層になるにつれて地図データは粗く広域になる。
【０００３】
このような、階層構造化された地図データを用いて経路探索を行う経路探索装置の一例として、特許文献１に示される車両用ナビゲーション装置があった。
【０００４】
特許文献１に示される車両用ナビゲーション装置は、車両の現在地を検出し、検出した現在地情報と、上位の道路から下位の道路までの道路の詳細度に応じて階層化された全地図データに基づいて目的地までの経路を探索し、探索した経路情報を出力し、所定時間ごと、或いは所定距離ごとに、その地図データに基づいて現在地から目的地までの最適経路を探索するものである。
【０００５】
この地図データに基づいて現在地から目的地までの最適経路を探索する場合、まず、現在地、目的地の位置座標を決定し、最も詳細な地図データからなるレイヤであって、現在地、目的地の位置座標が含まれるレイヤのブロック番号を読み出す。次いで、現在地と目的地が含まれるブロック番号が同じか否か判断し、同じであれば読み出したブロック内の地図データを全て読み込む。また、ブロック番号が異なればその上位レイヤのブロック番号を各々読み出して、上述の現在地と目的地が含まれるブロック番号が同じか否か判断する処理に戻って同様の処理を同じブロック番号になるまで繰り返す。こうして読み出した同じブロック内の全地図データにより探索処理を行う。
【０００６】
また、なお、渋滞を考慮した探索を行う場合には、ＶＩＣＳ等の情報受信装置により受信した交通情報をメモリに記憶しておき、渋滞が発生している道路データをメモリから読み出し探索コストを重くする。このようにすることにより、渋滞の発生している道路は渋滞していない同じ道路に比べ探索され難くなる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００２−１０７１６４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述の特許文献１に示される車両用ナビゲーション装置は、所定時間毎、あるいは所定距離毎に現在地から目的地までの最適経路を探索するものの、現在地から目的地の間においては、上位レイヤを用いて経路探索を行うことになる。
【０００９】
従って、例えば、渋滞などの交通情報を加味して経路探索を行う場合、その交通情報を上位側のレイヤに対して加味することが起こりうる。この場合、上位側のレイヤは下位側のレイヤよりも探索できる道路が少ないため、不用に遠回りとなる経路を探索してしまう可能性がある。
【００１０】
また、通常、ユーザーによって指定された経由地点を加味して経路探索を行う場合、経路探索する範囲は、指定された地点の周囲の狭い範囲に限定されてしまうことがある。従って、経路探索する際に、指定された地点の周囲の狭い範囲に縛られてしまい、最適な経路が他にもあるにもかかわらず、別の経路を探索してしまう可能性がある。
【００１１】
本発明は、上記問題点に鑑みなされたものであり、目的地までの経路が設定された後、経路を再探索する際に、不用に遠回りとなる経路など最適でない経路を探索してしまうことを抑制できる経路探索装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために請求項１に記載の経路探索装置は、出発地から目的地までの経路を探索するものであって、
道路網の情報の多い下位階層から道路網の情報の少ない上位階層へと複数段に階層化された地図データ、及び各階層の接続情報を取得する地図データ取得手段と、
地図データに基づいて、出発地および目的地を含む階層の地図データを特定し、各階層間の接続情報に基づいて特定された階層の地図データにおいて上位階層の地図データへ接続する点まで経路探索を行ない、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうことによって出発地から目的地までの経路探索を行なう経路探索手段と、
道路に発生している交通事象と交通事象が発生している位置を示す位置情報とを含む交通情報を取得する交通情報取得手段と、
経路探索手段にて探索された経路に発生している交通事象を含む交通情報を有している場合、交通事象が発生している位置を含む最下層の地図データを特定する特定手段と、を備え、
経路探索手段は、特定手段にて最下層の地図データが特定された場合、その特定された最下層の地図データを含めて経路を再探索することを特徴とするものである。
【００１３】
このように、階層化された地図データを用いて出発地から目的地までの経路を探索するものにおいて、探索された経路に発生している交通事象を含む交通情報を有している場合は、交通事象が発生している位置を含む最下層の地図データを特定して、この特定した最下層の地図データを含めて経路を再探索することによって、交通事象が発生している地点の周辺を詳細な地図データで探索できる。よって、交通事象を回避しつつ、不用に遠回りとなる経路を探索してしまうことを抑制でき、より最適な代替経路を探索できる。
【００１４】
また、上記目的を達成するために請求項２に記載の経路探索装置は、出発地から目的地までの経路を探索するものであって、
道路網の情報の多い下位階層から道路網の情報の少ない上位階層へと複数段に階層化された地図データ、及び各階層の接続情報を取得する地図データ取得手段と、
地図データに基づいて、出発地および目的地を含む階層の地図データを特定し、各階層間の接続情報に基づいて特定された階層の地図データにおいて上位階層の地図データへ接続する点まで経路探索を行ない、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうことによって出発地から目的地までの経路探索を行なう経路探索手段と、
指示される経由地点の経由位置情報を取得する経由位置情報取得手段と、
経由位置情報取得手段にて、経由位置情報を取得した場合、経由位置情報が示す位置を含む最下層の地図データを特定する特定手段と、を備え、
経路探索手段は、特定手段にて最下層の地図データが特定された場合、特定された最下層の地図データを含めて経路を再探索することを特徴とするものである。
【００１５】
このように、階層化された地図データを用いて出発地から目的地までの経路を探索するものにおいて、指示される経由地点の経由位置情報を取得した場合、経由位置情報が示す位置を含む最下層の地図データ（少なくとも一つの分割エリア）を特定して、この特定した最下層の地図データを含めて経路を再探索することによって、指示された経由地点の周辺の狭い範囲に限定されることなく探索できる。よって、最適な経路が他にもあるにもかかわらず、別の経路を探索してしまうことを抑制でき、より最適な代替経路を探索できる。
【００１６】
また、請求項３に示すように、経路探索手段は、特定手段にて特定された最下層の地図データが複数あり、複数の最下層の地図データが隣り合わせの場合、複数の最下層の地図データに渡って経路探索を行い、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうようにしてもよい。
【００１７】
このように、特定された複数の最下層の地図データが隣り合わせの場合は、その最下層の地図データ間において上位層の地図データを探索することなく、複数の最下層の地図データに渡って経路探索を行うことによって探索時間を短縮することができる。
【００１８】
また、請求項４に示すように、経路探索手段は、特定手段にて特定された最下層の地図データが複数あり、複数の最下層の地図データが隣り合わせでない場合、特定された最下層の地図データのそれぞれにおいては、接続情報に基づいて上位階層の地図データへ接続する点まで経路探索を行ない、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうようにしてもよい。
【００１９】
このように、特定された複数の最下層の地図データが隣り合わせでない場合は、最下層の地図データのそれぞれにおいては、接続情報に基づいて上位階層の地図データへ接続する点まで経路探索を行い、その後上位層の地図データを探索することによって、経路の途中で最下層の地図データを用いて経路探索した場合であっても、出発地から目的地までの経路を探索することができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態におけるナビゲーション装置の概略構成を示すブロック図である。
【図２】本発明の実施の形態におけるナビゲーション装置の処理動作を示すフローチャートである。
【図３】本発明の実施の形態におけるナビゲーション装置の地図データの概略構成を示すイメージ図である。
【図４】本発明の変形例におけるナビゲーション装置の処理動作を示すフローチャートである。
【発明を実施するための形態】
【００２１】
以下、本発明の実施の形態を図に基づいて説明する。本実施の形態においては、本発明の経路探索装置を車載ナビゲーション装置に適用した例を採用して説明する。
【００２２】
図１に示すように、車載ナビゲーション装置は、位置検出器１、地図データ入力器２、制御装置３、通信装置４、操作スイッチ群５、外部メモリ６、表示装置７、音声出力装置８などを有している。
【００２３】
位置検出器１は、いずれも周知の地磁気センサー１ａ、ジャイロスコープ１ｂ、距離センサー１ｃ、およびＧＰＳ受信機１ｄ等のセンサーを有しており、これらセンサーの各々の性質に基づいた、車両の現在地や向きを特定するための情報を制御装置３に出力する。
【００２４】
地図データ入力器２は、ＤＶＤやハードディスクなどの記憶媒体に記憶された地図データ、後ほど説明する各階層間の接続情報などを制御装置３に入力するものである。換言すると、制御装置３は、この地図データ入力器２から地図データ、各階層間の接続情報などを取得する（地図データ取得手段）。
【００２５】
記憶媒体に記憶されている地図データは、リンクおよびノードの位置、種別、ノードとリンクとの接続関係情報、及び等を含む道路データ、および施設データなどを有している。また、この地図データは、道路網の情報量を基に複数段に階層化された階層構造（ここでは３階層）となっている。また、階層化された各地図データは、それぞれが道路データ、施設データを有している。上位階層の地図データほど、その地図データが含むリンクおよびノード、およびその施設データが含む施設数が、下位階層の地図データに比べて間引かれている。また、各階層の地図データは、所定の等間隔の緯度・経度でメッシュ状に区切られた分割エリアごとのデータの集合によって構成されている。なお、各階層間の接続情報は、この階層化された地図データにおける上位階層と下位階層間の接続に関する情報である。
【００２６】
つまり、地図データは、広域データ（レベル３、最上層）、中域データ（レベル２、中位層）、および詳細データ（レベル１、最下層）という、３つの階層データを含んでいる。換言すると、レベル３の地図データは、最も広域をカバーしており、最も道路網の情報が少ない。レベル１の地図データは、カバーしている領域は最も狭いが（最も狭域）、最も道路網の情報が多い。そして、レベル２の地図データは、レベル３よりも狭くレベル１よりも広い領域をカバーしており、レベル３よりも情報が多くレベル１よりも情報が少ない。例えば、道路データに関しては、レベル１の地図データは、細街路を含めたその地域の全リンクおよびノードを含み、レベル２の地図データは、レベル１の地図データから細街路を除いたリンクおよびノードを含み、レベル３の地図データは、レベル２の地図データから県道等を除いた、国道および高速道路等の主要道路のみのリンクおよびノードを含んでいる。
【００２７】
このように、階層化された地図データを有する車載ナビゲーション装置においては、次のようにして経路探索を行う。まず、地図データに基づき、指定された出発地（例えば現在地）および目的地を含む階層（最下層）の地図データを特定する。そして、その特定した各地図データの接続情報に基づき、特定された地図データにおいて上位階層へ接続する点或いは部分まで経路探索を行ない、さらに上位階層に移行して接続点（部分）からの経路探索を繰り返し行なう（経路探索手段）。さらに、本実施の形態における車載ナビゲーション装置においては、経路上に交通事象がある場合は、その交通事象が発生している位置を含む最下層の地図データを含めて経路探索を行う（経路探索手段）。この点に関しては後ほど説明する。
【００２８】
制御装置３は、通常のコンピュータとして構成されており、内部には周知のＣＰＵ、ＲＯＭ、ＲＡＭ、Ｉ／Ｏ及びこれらの構成を接続するバスライン（いずれも図示せず）が備えられている。制御装置３は、位置検出器１、地図データ入力器２、通信装置４、操作スイッチ群５、外部メモリ６から入力された各種情報（データ、信号）に基づき、経路探索、経路案内などの車載ナビゲーション装置としての処理を実行する。なお、制御装置３の処理動作は、後ほど説明する。
【００２９】
通信装置４は、道路沿いに設置された路上機から無線送信された道路の渋滞情報、交通規制情報等を含む交通情報を受信するものである（交通情報取得手段）。これらの交通情報の配信システムとしては、例えば、ＶＩＣＳ（Vehicle Information and Communication System：道路交通情報通信システム（登録商標））、ＲＤＳ-ＴＭＣ（Radio Data System-Traffic Message Channel：ＦＭ多重放送による交通情報サービス）や、複数の車両からプローブ情報を収集して、そのプローブ情報に基づいて生成された交通情報を配信するプローブ情報配信システムなどがある。そして、制御装置３は、この通信装置４から交通情報を取得する（交通情報取得手段）。
【００３０】
なお、交通情報は、渋滞情報や交通規制等の道路に発生している交通事象と、その交通事象が発生している位置を示す位置情報を含むものである。さらに、渋滞度（渋滞、混雑、順調など）、渋滞の先頭位置情報、渋滞の長さ情報、リンク旅行時間情報（いわゆるＶＩＣＳリンクである交差点間を車両が走行に要する時間）、区間旅行時間情報（ＶＩＣＳリンクより長い所定区間における車両が走行に要する時間）、規制内容、原因、規制区間などの情報を含む交通情報を採用することもできる。
【００３１】
操作スイッチ群５は、車載ナビゲーション装置に設けられた複数のメカニカルスイッチ、表示装置７の表示面に重ねて設けられたタッチパネル等の入力装置から成り、ユーザーによるメカニカルスイッチの押下、タッチパネルのタッチに基づいた信号を制御装置３に出力する。例えば、ユーザーによる押下、タッチなどの操作によって、出発地、目的地などを示す信号が出力される。
【００３２】
外部メモリ６は、ハードディスク等の書き込み可能な大容量記憶装置である。外部メモリ６には、大量のデータや電源をＯＦＦしても消去してはいけないデータを記憶したり、頻繁に使用するデータを地図データ入力器２からコピーして利用したりする等の用途がある。また、外部メモリ６は、通信装置４にて受信した交通情報を記憶するようにしてもよい。
【００３３】
表示装置７は、制御装置３から出力された映像信号に基づいた映像をユーザーに表示する。表示映像としては、例えば現在地を中心とする地図等がある。音声出力装置８は、制御装置３から受けた音声データに基づく音声信号をスピーカ（図示省略）に出力する。ただし、表示装置７及び音声出力装置８は、本発明の目的を達成する際に必ずしも必要ではない。
【００３４】
ここで、図２及び図３に基づいて、車載ナビゲーション装置の処理動作に関して説明する。なお、図２のフローチャートに示す処理動作は、例えば、車載ナビゲーション装置に電源が供給されているときに所定時間毎に実行されたり、経路案内中に所定時間毎に実行されたり、経路案内の開始時又は交通情報の受信時に実行されるものである。
【００３５】
ステップＳ１０では、制御装置３は、交通情報が有り、かつ、経路が有るか否かを判定する。つまり、制御装置３は、外部メモリ６などに通信装置４にて受信した交通情報が記憶されているか否かを確認する。さらに、制御装置３は、出発地（例えば、現在地）から目的地までの経路（例えば、経路案内中の案内経路、案内開始前に交通情報を考慮せずに探索した所期経路など）を設定しているか否かを確認する。そして、交通情報が有り、経路を設定していると判定した場合はステップＳ１１へ進み、交通情報がない、もしくは経路を設定していないと判定した場合は処理を終了する。
【００３６】
ステップＳ１１では、制御装置３は、地図データを取得して、設定している経路上の交通事象を特定する。つまり、通信装置４にて受信した交通情報に、設定している経路上に該当する交通事象が含まれているか否かを確認する。換言すると、設定している経路上に渋滞情報や交通規制等の交通事象が発生しているか否かを確認する。そして、ステップＳ１２では、制御装置３は、経路上に交通事象があると判定した場合は経路の再探索が必要であるとみなしてステップＳ１３へ進み、経路上に交通事象がないと判定した場合は経路の再探索は必要ないとみなして処理を終了する。
【００３７】
ステップＳ１３では、制御装置３は、地図データを取得して、出発地及び目的地周辺（出発地及び目的地を含む）の最下層（レベル１）の地図データＤ１（分割エリア）及びＤ２（分割エリア）を特定し（図３参照）、この特定した地図データＤ１及びＤ２の経路上に交通事象を含んでいるか否かを判定する。そして、ステップＳ１４では、制御装置３は、含んでいると判定した場合は処理を終了し、含んでいないと判定した場合はステップＳ１５へ進む。ここで、出発地及び目的地周辺の最下層の地図データＤ１及びＤ２の経路上に交通事象が含まれていた場合に処理を終了するのは、もともと（従来の処理動作時に）、出発地及び目的地の周辺においては、最下層の地図データを用いて経路探索を行うため、ステップＳ１５以降の処理を行う必要がないためである。
【００３８】
ステップＳ１５では、制御装置３は、地図データを取得して、図３に示すように、経路上の交通事象が発生している位置を含む最下層の地図データ（以下の説明、図面においては、ターゲットデータ（分割エリア）とも称する）を特定する（特定手段）。これは、経路上に発生している交通事象の周辺においては、詳細な地図データ（レベル１の地図データ）を用いて経路を探索することによって、不要な遠回りを抑制するためである。なお、ターゲットデータは、最下層の地図データにおける一つ又は複数の分割エリアを示すものである。
【００３９】
ステップＳ１６では、制御装置３は、地図データ、各階層間の接続情報などを取得して（地図データ取得手段）、現在地（又は目的地）からターゲットデータ内まで、階層構造の地図データに基づいて経路を再探索する。つまり、現在地（又は目的地）周辺の最下層の地図データ及びターゲットデータの接続情報に基づき、特定された地図データ（現在地（又は目的地）周辺の最下層の地図データ及びターゲットデータ）において上位階層へ接続する点或いは部分まで経路探索を行ない、さらに上位階層に移行して接続点（部分）からの経路探索を繰り返し行なう（経路探索手段）。
【００４０】
一方、ステップＳ１７では、制御装置３は、地図データ、各階層間の接続情報などを取得して（地図データ取得手段）、ターゲットデータ内から目的地（又は現在地）まで、階層構造の地図データに基づいて経路を再探索して、この再探索結果とステップＳ１６の再探索結果とによって経路を作成する。つまり、目的地（又は現在地）周辺の最下層の地図データ及びターゲットデータの接続情報に基づき、特定された地図データ（目的地（又は現在地）周辺の最下層の地図データ及びターゲットデータ）において上位階層へ接続する点或いは部分まで経路探索を行ない、さらに上位階層に移行して接続点（部分）からの再経路探索を繰り返し行なう（経路探索手段）。そして、この探索結果とステップＳ１６の探索結果とによって経路を作成する（経路探索手段）。
【００４１】
つまり、制御装置３は、ステップＳ１５でターゲットデータを特定した場合、そのターゲットデータを含めて現在地（現在地を出発する地点とする場合は出発地）から目的地までの経路を再探索する（経路探索手段）。
【００４２】
このように、階層化された地図データを用いて出発地から目的地までの経路を探索するものにおいて、探索された経路に発生している交通事象を含む交通情報を有している場合は、交通事象が発生している位置を含む最下層の地図データ（ターゲットデータ）を特定して、この特定したターゲットデータを含めて経路を再探索することによって、交通事象が発生している地点の周辺を詳細な地図データで探索できる。よって、交通事象を回避しつつ、不用に遠回りとなる経路を探索してしまうことを抑制でき、より最適な代替経路を探索できる。
【００４３】
また、本実施の形態においては、探索された経路に発生している交通事象を含む交通情報を有している場合に、交通事象が発生している位置を含む最下層の地図データ（ターゲットデータ）を特定して、この特定したターゲットデータを含めて経路を再探索する例を採用して説明したが本発明はこれに限定されるものではない。ここで、本発明の変形例にける車載ナビゲーション装置に関して説明する。なお、上述の実施の形態における車載ナビゲーション装置と変形例における車載ナビゲーション装置とは、構成（図１）に関しては同等であるため詳しい説明は省略して、異なる点を重点的に説明する。ただし、変形例の車載ナビゲーション装置においては、必ずしも通信装置４は必要ない。
【００４４】
上述の実施の形態における車載ナビゲーション装置と変形例における車載ナビゲーション装置とで異なる点は、ユーザーによって経由地点が指示されるとターゲットデータを特定して、この特定したターゲットデータを含めて経路を再探索する点である。つまり、制御装置３は、操作スイッチ群５から経由地を示す信号（経由位置情報）が入力された場合（経由位置情報取得手段）、ターゲットデータを特定して、この特定したターゲットデータを含めて経路を再探索する。
【００４５】
ここで、図４を用いて、変形例における車載ナビゲーション装置の処理動作に関して説明する。
【００４６】
まず、ステップＳ２０では、制御装置３は、経由地が有り、かつ、経路が有るか否かを判定する。つまり、制御装置３は、操作スイッチ群５から経由位置情報が入力されているか否かを確認する。さらに、制御装置３は、出発地（例えば、現在地）から目的地までの経路（例えば、経路案内中の案内経路、案内開始前に交通情報を考慮せずに探索した所期経路など）を設定しているか否かを確認する。そして、経由位置情報が有り、経路を設定していると判定した場合はステップＳ２１へ進み、経由位置情報がない、もしくは経路を設定していないと判定した場合は処理を終了する。
【００４７】
ステップＳ２１では、制御装置３は、地図データを取得して、出発地及び目的地周辺（出発地及び目的地を含む）の最下層（レベル１）の地図データＤ１及びＤ２（図３参照）を特定し、この特定した地図データＤ１及びＤ２が経由位置情報を含んでいるか否かを判定する。そして、ステップＳ２２では、制御装置３は、含んでいると判定した場合は処理を終了し、含んでいないと判定した場合はステップＳ２３へ進む。ここで、出発地及び目的地周辺の最下層の地図データＤ１及びＤ２に経由位置情報が含まれていた場合に処理を終了するのは、もともと（従来の処理動作時に）、出発地及び目的地の周辺においては、最下層の地図データを用いて経路探索を行うため、ステップＳ２３以降の処理を行う必要がないためである。
【００４８】
ステップＳ２３では、制御装置３は、地図データを取得して（地図データ取得手段）、ユーザーによって指示された経由地を含む最下層の地図データ（ターゲットデータ）を特定する（特定手段）。これは、経由地の周辺においては、詳細な地図データ（レベル１の地図データ）を用いて経路を探索することによって、不要な遠回りを抑制するためである。
【００４９】
なお、ステップＳ２４、Ｓ２５に関しては、上述の実施の形態における図２のステップＳ１６、Ｓ１７と同等であるため説明は省略する。
【００５０】
このように、階層化された地図データを用いて出発地から目的地までの経路を探索するものにおいて、ユーザーによって指示される経由地点の経由位置情報を取得した場合、経由位置情報が示す位置を含む最下層の地図データ（ターゲットデータ（分割エリア））を特定して、この特定したターゲットデータを含めて経路を再探索することによって、ユーザーによって指示された経由地点の周辺を詳細な地図データで探索できる。つまり、ユーザーによって指示された経由地点の周辺の狭い範囲に限定されることなく探索できる。よって、最適な経路が他にもあるにもかかわらず、別の経路を探索してしまうことを抑制でき、より最適な代替経路を探索できる。
【００５１】
なお、上述の変形例においては、ユーザーによって経由地点が指示される例を採用して説明したが、本発明はこれに限定されるものではない。この経由地点は、車両（車載ナビゲーション装置の通信装置４）と通信接続が可能なセンター（サーバー、図示省略）から指示されるようにしてもよい。
【００５２】
この場合、センターは、地図データを記憶した記憶装置、車両（車載ナビゲーション装置の通信装置４）との通信を行なう通信装置、記憶装置から取得した地図データを用いた経路探索、通信装置による通信の制御などを実行可能なサーバーなどを備える構成を採用することができる。一方、車載ナビゲーション装置の制御装置３は、所定のタイミング（例えば、目的地が設定された時点、経路案内中に所定時間毎、経路案内の開始時など）で車両の現在地、及び目的地を通信装置４を介してセンター（センター側の通信装置を介してサーバー）に送信する。
【００５３】
この現在地と目的地を取得したセンター（サーバー）は、取得した車両の現在地から目的地までの最適な経路を探索する。また、センター（サーバー）は、この探索結果から最適な経路を通るための経由地点を検索する。そして、センター（サーバー）は、検索した経由地点（経由位置情報）を車両（車載ナビゲーション装置の通信装置４）に送信する。つまり、経由地点を指示する。
【００５４】
このように、センター（サーバー）によって経由地点を指示された場合であっても、経由地点の周辺の狭い範囲に限定されることなく探索できる。よって、最適な経路が他にもあるにもかかわらず、別の経路を探索してしまうことを抑制でき、より最適な代替経路を探索できる。
【００５５】
通常、車両に搭載される制御装置（マイコン）に比べて、センターなどに設置されるサーバーの方が処理能力は高く、また、情報量（地図データや交通情報など）が多い。従って、センターに設置されたサーバーは、車載ナビゲーション装置で探索された経路よりも最適な経路を探索できる可能性がある。よって、センターに設置されたサーバーにて探索された経路から検索された経由地点を指示することによって、車載ナビゲーション装置（車両に搭載される制御装置（マイコン））においても、より一層最適な経路探索を行うことができる。
【００５６】
また、上述の実施の形態、及び変形例においては、ターゲットデータ（分割エリア）は、一つである例を採用して説明したが、本発明はこれに限定されるものではない。複数のターゲットデータ（分割エリア）を特定できるようにしてもよい。
【００５７】
例えば、特定した複数のターゲットデータが隣り合わせの場合、複数のターゲットデータに渡って経路探索を行い、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうようにしてもよい。つまり、現在地（又は目的地）から複数のターゲットデータ内まで、階層構造の地図データに基づいて経路を探索する。具体的には、現在地（又は目的地）周辺の最下層の地図データ及び複数のターゲットデータのうちの一つ（現在地（又は目的地）から最も近いターゲットデータ）の接続情報に基づき、特定された地図データ（現在地（又は目的地）周辺の最下層の地図データ及び最も近いターゲットデータ）において上位階層へ接続する点或いは部分まで経路探索を行ない、さらに上位階層に移行して接続点（部分）からの経路探索を繰り返し行なう（経路探索手段）。そして、複数のターゲットデータ間で経路探索を行う。
【００５８】
一方、複数のターゲットデータ内から目的地（又は現在地）まで、階層構造の地図データに基づいて経路を探索して、この探索結果とステップＳ１６の探索結果とによって経路を作成する。つまり、目的地（又は現在地）周辺の最下層の地図データ及び複数のターゲットデータのうちの一つ（目的地（又は現在地）から最も近いターゲットデータ）の接続情報に基づき、特定された地図データ（目的地（又は現在地）周辺の最下層の地図データ及び最も近いターゲットデータ）において上位階層へ接続する点或いは部分まで経路探索を行ない、さらに上位階層に移行して接続点（部分）からの経路探索を繰り返し行なう（経路探索手段）。そして、この探索結果と上述の現在地（又は目的地）から複数のターゲットデータ内までの探索結果とによって経路を作成する（経路探索手段）。
【００５９】
このように、特定された複数のターゲットデータが隣り合わせの場合は、そのターゲットデータ間において上位層の地図データを探索することなく、複数の最下層の地図データに渡って経路探索を行うことによって探索時間を短縮することができる。
【００６０】
また、特定されたターゲットデータが隣り合わせでない場合は、最下層の地図データのそれぞれにおいては、接続情報に基づいて上位階層の地図データへ接続する点まで経路探索を行い、その後上位層の地図データを探索する（経路探索手段）ことによって、経路の途中で最下層の地図データを用いて経路探索した場合であっても、出発地から目的地までの経路を探索することができる。つまり、現在地（又は目的地）からターゲットデータ内の経路探索が終了した地図データと、探索が完了していない地図データ間で経路探索を繰り返す。具体的には、現在地（又は目的地）から現在地（又は目的地）に近いターゲットデータ内の経路探索と、ターゲットデータ内から別のターゲットデータ内の経路計算と、目的地（又は現在地）からターゲットデータ内の経路探索とを行い、これらの探索結果によって経路を作成する（経路探索手段）。
【００６１】
さらに、経路上に交通事象が発生しており、ターゲットデータが複数ある場合は、各ターゲットデータに含まれる交通事象（各ターゲットデータに含まれる経路に発生している交通事象）の重要度に応じて、再経路計算に含めるターゲットデータと含めないターゲットデータを選択するようにしてもよい。換言すると、重要度に応じて、交通事象とみなすか否かを選択する。
【００６２】
この場合、交通事象を重要度に応じて区分しておく。重要度は、例えば、渋滞１ｋｍよりも渋滞１０ｋｍの方が重要度大、渋滞よりも交通規制（通行禁止）の方が重要度大などとすることができる。このとき、交通情報は、渋滞情報や交通規制等の道路に発生している交通事象と、その交通事象が発生している位置を示す位置情報と、その交通事象の重要度を含むものである。
【００６３】
そして、制御装置３は、交通事象が発生している位置を含む複数の最下層の地図データ（ターゲットデータ）を特定した場合、各ターゲットデータに対応する交通事象の重要度を確認する（確認手段）。そして、制御装置３は、重要度に関する所定の条件を満たしている交通事象を含むターゲットデータを再経路探索に用いるものとして選択する（選択手段）。
【００６４】
所定の条件としては、例えば、重要度が最も大きい、重要度に応じて付与されたポイントの合計値が最も大きい（一つのターゲットデータに対応する交通事象が複数あった場合）、重要度に応じて付与されたポイントの合計値が所定値以上（同様に交通事象が複数あった場合）、重要度が最も小さくない、重要度に応じて付与されたポイントの合計値が最も小さくない（一つのターゲットデータに対応する交通事象が複数あった場合）などを採用することができる。
【符号の説明】
【００６５】
１ 位置検出器、１ａ 地磁気センサー、１ｂ ジャイロスコープ、１ｃ 距離センサー、１ｄ ＧＰＳ受信機、２ 地図データ入力器、３ 制御装置、４ 通信装置、５ 操作スイッチ群、６ 外部メモリ、７ 表示装置、８ 音声出力装置
【技術分野】
【０００１】
本発明は、階層構造化された地図データを用いて経路探索を行う経路探索装置に関するものである。
【背景技術】
【０００２】
従来、経路探索に用いる地図データは、複数の階層構造を有するものがある。その階層構造の一例としては、レイヤ１、レイヤ２、レイヤ３のように３階層構造がある。この３階層構造は、すべての地図データからなる下位階層であるレイヤ１、高速・有料道路、国道、県道からなる中位階層であるレイヤ２、高速・有料道路、国道からなる上位階層であるレイヤ３などを有する。そして、上位階層になるにつれて地図データは粗く広域になる。
【０００３】
このような、階層構造化された地図データを用いて経路探索を行う経路探索装置の一例として、特許文献１に示される車両用ナビゲーション装置があった。
【０００４】
特許文献１に示される車両用ナビゲーション装置は、車両の現在地を検出し、検出した現在地情報と、上位の道路から下位の道路までの道路の詳細度に応じて階層化された全地図データに基づいて目的地までの経路を探索し、探索した経路情報を出力し、所定時間ごと、或いは所定距離ごとに、その地図データに基づいて現在地から目的地までの最適経路を探索するものである。
【０００５】
この地図データに基づいて現在地から目的地までの最適経路を探索する場合、まず、現在地、目的地の位置座標を決定し、最も詳細な地図データからなるレイヤであって、現在地、目的地の位置座標が含まれるレイヤのブロック番号を読み出す。次いで、現在地と目的地が含まれるブロック番号が同じか否か判断し、同じであれば読み出したブロック内の地図データを全て読み込む。また、ブロック番号が異なればその上位レイヤのブロック番号を各々読み出して、上述の現在地と目的地が含まれるブロック番号が同じか否か判断する処理に戻って同様の処理を同じブロック番号になるまで繰り返す。こうして読み出した同じブロック内の全地図データにより探索処理を行う。
【０００６】
また、なお、渋滞を考慮した探索を行う場合には、ＶＩＣＳ等の情報受信装置により受信した交通情報をメモリに記憶しておき、渋滞が発生している道路データをメモリから読み出し探索コストを重くする。このようにすることにより、渋滞の発生している道路は渋滞していない同じ道路に比べ探索され難くなる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００２−１０７１６４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述の特許文献１に示される車両用ナビゲーション装置は、所定時間毎、あるいは所定距離毎に現在地から目的地までの最適経路を探索するものの、現在地から目的地の間においては、上位レイヤを用いて経路探索を行うことになる。
【０００９】
従って、例えば、渋滞などの交通情報を加味して経路探索を行う場合、その交通情報を上位側のレイヤに対して加味することが起こりうる。この場合、上位側のレイヤは下位側のレイヤよりも探索できる道路が少ないため、不用に遠回りとなる経路を探索してしまう可能性がある。
【００１０】
また、通常、ユーザーによって指定された経由地点を加味して経路探索を行う場合、経路探索する範囲は、指定された地点の周囲の狭い範囲に限定されてしまうことがある。従って、経路探索する際に、指定された地点の周囲の狭い範囲に縛られてしまい、最適な経路が他にもあるにもかかわらず、別の経路を探索してしまう可能性がある。
【００１１】
本発明は、上記問題点に鑑みなされたものであり、目的地までの経路が設定された後、経路を再探索する際に、不用に遠回りとなる経路など最適でない経路を探索してしまうことを抑制できる経路探索装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために請求項１に記載の経路探索装置は、出発地から目的地までの経路を探索するものであって、
道路網の情報の多い下位階層から道路網の情報の少ない上位階層へと複数段に階層化された地図データ、及び各階層の接続情報を取得する地図データ取得手段と、
地図データに基づいて、出発地および目的地を含む階層の地図データを特定し、各階層間の接続情報に基づいて特定された階層の地図データにおいて上位階層の地図データへ接続する点まで経路探索を行ない、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうことによって出発地から目的地までの経路探索を行なう経路探索手段と、
道路に発生している交通事象と交通事象が発生している位置を示す位置情報とを含む交通情報を取得する交通情報取得手段と、
経路探索手段にて探索された経路に発生している交通事象を含む交通情報を有している場合、交通事象が発生している位置を含む最下層の地図データを特定する特定手段と、を備え、
経路探索手段は、特定手段にて最下層の地図データが特定された場合、その特定された最下層の地図データを含めて経路を再探索することを特徴とするものである。
【００１３】
このように、階層化された地図データを用いて出発地から目的地までの経路を探索するものにおいて、探索された経路に発生している交通事象を含む交通情報を有している場合は、交通事象が発生している位置を含む最下層の地図データを特定して、この特定した最下層の地図データを含めて経路を再探索することによって、交通事象が発生している地点の周辺を詳細な地図データで探索できる。よって、交通事象を回避しつつ、不用に遠回りとなる経路を探索してしまうことを抑制でき、より最適な代替経路を探索できる。
【００１４】
また、上記目的を達成するために請求項２に記載の経路探索装置は、出発地から目的地までの経路を探索するものであって、
道路網の情報の多い下位階層から道路網の情報の少ない上位階層へと複数段に階層化された地図データ、及び各階層の接続情報を取得する地図データ取得手段と、
地図データに基づいて、出発地および目的地を含む階層の地図データを特定し、各階層間の接続情報に基づいて特定された階層の地図データにおいて上位階層の地図データへ接続する点まで経路探索を行ない、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうことによって出発地から目的地までの経路探索を行なう経路探索手段と、
指示される経由地点の経由位置情報を取得する経由位置情報取得手段と、
経由位置情報取得手段にて、経由位置情報を取得した場合、経由位置情報が示す位置を含む最下層の地図データを特定する特定手段と、を備え、
経路探索手段は、特定手段にて最下層の地図データが特定された場合、特定された最下層の地図データを含めて経路を再探索することを特徴とするものである。
【００１５】
このように、階層化された地図データを用いて出発地から目的地までの経路を探索するものにおいて、指示される経由地点の経由位置情報を取得した場合、経由位置情報が示す位置を含む最下層の地図データ（少なくとも一つの分割エリア）を特定して、この特定した最下層の地図データを含めて経路を再探索することによって、指示された経由地点の周辺の狭い範囲に限定されることなく探索できる。よって、最適な経路が他にもあるにもかかわらず、別の経路を探索してしまうことを抑制でき、より最適な代替経路を探索できる。
【００１６】
また、請求項３に示すように、経路探索手段は、特定手段にて特定された最下層の地図データが複数あり、複数の最下層の地図データが隣り合わせの場合、複数の最下層の地図データに渡って経路探索を行い、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうようにしてもよい。
【００１７】
このように、特定された複数の最下層の地図データが隣り合わせの場合は、その最下層の地図データ間において上位層の地図データを探索することなく、複数の最下層の地図データに渡って経路探索を行うことによって探索時間を短縮することができる。
【００１８】
また、請求項４に示すように、経路探索手段は、特定手段にて特定された最下層の地図データが複数あり、複数の最下層の地図データが隣り合わせでない場合、特定された最下層の地図データのそれぞれにおいては、接続情報に基づいて上位階層の地図データへ接続する点まで経路探索を行ない、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうようにしてもよい。
【００１９】
このように、特定された複数の最下層の地図データが隣り合わせでない場合は、最下層の地図データのそれぞれにおいては、接続情報に基づいて上位階層の地図データへ接続する点まで経路探索を行い、その後上位層の地図データを探索することによって、経路の途中で最下層の地図データを用いて経路探索した場合であっても、出発地から目的地までの経路を探索することができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態におけるナビゲーション装置の概略構成を示すブロック図である。
【図２】本発明の実施の形態におけるナビゲーション装置の処理動作を示すフローチャートである。
【図３】本発明の実施の形態におけるナビゲーション装置の地図データの概略構成を示すイメージ図である。
【図４】本発明の変形例におけるナビゲーション装置の処理動作を示すフローチャートである。
【発明を実施するための形態】
【００２１】
以下、本発明の実施の形態を図に基づいて説明する。本実施の形態においては、本発明の経路探索装置を車載ナビゲーション装置に適用した例を採用して説明する。
【００２２】
図１に示すように、車載ナビゲーション装置は、位置検出器１、地図データ入力器２、制御装置３、通信装置４、操作スイッチ群５、外部メモリ６、表示装置７、音声出力装置８などを有している。
【００２３】
位置検出器１は、いずれも周知の地磁気センサー１ａ、ジャイロスコープ１ｂ、距離センサー１ｃ、およびＧＰＳ受信機１ｄ等のセンサーを有しており、これらセンサーの各々の性質に基づいた、車両の現在地や向きを特定するための情報を制御装置３に出力する。
【００２４】
地図データ入力器２は、ＤＶＤやハードディスクなどの記憶媒体に記憶された地図データ、後ほど説明する各階層間の接続情報などを制御装置３に入力するものである。換言すると、制御装置３は、この地図データ入力器２から地図データ、各階層間の接続情報などを取得する（地図データ取得手段）。
【００２５】
記憶媒体に記憶されている地図データは、リンクおよびノードの位置、種別、ノードとリンクとの接続関係情報、及び等を含む道路データ、および施設データなどを有している。また、この地図データは、道路網の情報量を基に複数段に階層化された階層構造（ここでは３階層）となっている。また、階層化された各地図データは、それぞれが道路データ、施設データを有している。上位階層の地図データほど、その地図データが含むリンクおよびノード、およびその施設データが含む施設数が、下位階層の地図データに比べて間引かれている。また、各階層の地図データは、所定の等間隔の緯度・経度でメッシュ状に区切られた分割エリアごとのデータの集合によって構成されている。なお、各階層間の接続情報は、この階層化された地図データにおける上位階層と下位階層間の接続に関する情報である。
【００２６】
つまり、地図データは、広域データ（レベル３、最上層）、中域データ（レベル２、中位層）、および詳細データ（レベル１、最下層）という、３つの階層データを含んでいる。換言すると、レベル３の地図データは、最も広域をカバーしており、最も道路網の情報が少ない。レベル１の地図データは、カバーしている領域は最も狭いが（最も狭域）、最も道路網の情報が多い。そして、レベル２の地図データは、レベル３よりも狭くレベル１よりも広い領域をカバーしており、レベル３よりも情報が多くレベル１よりも情報が少ない。例えば、道路データに関しては、レベル１の地図データは、細街路を含めたその地域の全リンクおよびノードを含み、レベル２の地図データは、レベル１の地図データから細街路を除いたリンクおよびノードを含み、レベル３の地図データは、レベル２の地図データから県道等を除いた、国道および高速道路等の主要道路のみのリンクおよびノードを含んでいる。
【００２７】
このように、階層化された地図データを有する車載ナビゲーション装置においては、次のようにして経路探索を行う。まず、地図データに基づき、指定された出発地（例えば現在地）および目的地を含む階層（最下層）の地図データを特定する。そして、その特定した各地図データの接続情報に基づき、特定された地図データにおいて上位階層へ接続する点或いは部分まで経路探索を行ない、さらに上位階層に移行して接続点（部分）からの経路探索を繰り返し行なう（経路探索手段）。さらに、本実施の形態における車載ナビゲーション装置においては、経路上に交通事象がある場合は、その交通事象が発生している位置を含む最下層の地図データを含めて経路探索を行う（経路探索手段）。この点に関しては後ほど説明する。
【００２８】
制御装置３は、通常のコンピュータとして構成されており、内部には周知のＣＰＵ、ＲＯＭ、ＲＡＭ、Ｉ／Ｏ及びこれらの構成を接続するバスライン（いずれも図示せず）が備えられている。制御装置３は、位置検出器１、地図データ入力器２、通信装置４、操作スイッチ群５、外部メモリ６から入力された各種情報（データ、信号）に基づき、経路探索、経路案内などの車載ナビゲーション装置としての処理を実行する。なお、制御装置３の処理動作は、後ほど説明する。
【００２９】
通信装置４は、道路沿いに設置された路上機から無線送信された道路の渋滞情報、交通規制情報等を含む交通情報を受信するものである（交通情報取得手段）。これらの交通情報の配信システムとしては、例えば、ＶＩＣＳ（Vehicle Information and Communication System：道路交通情報通信システム（登録商標））、ＲＤＳ-ＴＭＣ（Radio Data System-Traffic Message Channel：ＦＭ多重放送による交通情報サービス）や、複数の車両からプローブ情報を収集して、そのプローブ情報に基づいて生成された交通情報を配信するプローブ情報配信システムなどがある。そして、制御装置３は、この通信装置４から交通情報を取得する（交通情報取得手段）。
【００３０】
なお、交通情報は、渋滞情報や交通規制等の道路に発生している交通事象と、その交通事象が発生している位置を示す位置情報を含むものである。さらに、渋滞度（渋滞、混雑、順調など）、渋滞の先頭位置情報、渋滞の長さ情報、リンク旅行時間情報（いわゆるＶＩＣＳリンクである交差点間を車両が走行に要する時間）、区間旅行時間情報（ＶＩＣＳリンクより長い所定区間における車両が走行に要する時間）、規制内容、原因、規制区間などの情報を含む交通情報を採用することもできる。
【００３１】
操作スイッチ群５は、車載ナビゲーション装置に設けられた複数のメカニカルスイッチ、表示装置７の表示面に重ねて設けられたタッチパネル等の入力装置から成り、ユーザーによるメカニカルスイッチの押下、タッチパネルのタッチに基づいた信号を制御装置３に出力する。例えば、ユーザーによる押下、タッチなどの操作によって、出発地、目的地などを示す信号が出力される。
【００３２】
外部メモリ６は、ハードディスク等の書き込み可能な大容量記憶装置である。外部メモリ６には、大量のデータや電源をＯＦＦしても消去してはいけないデータを記憶したり、頻繁に使用するデータを地図データ入力器２からコピーして利用したりする等の用途がある。また、外部メモリ６は、通信装置４にて受信した交通情報を記憶するようにしてもよい。
【００３３】
表示装置７は、制御装置３から出力された映像信号に基づいた映像をユーザーに表示する。表示映像としては、例えば現在地を中心とする地図等がある。音声出力装置８は、制御装置３から受けた音声データに基づく音声信号をスピーカ（図示省略）に出力する。ただし、表示装置７及び音声出力装置８は、本発明の目的を達成する際に必ずしも必要ではない。
【００３４】
ここで、図２及び図３に基づいて、車載ナビゲーション装置の処理動作に関して説明する。なお、図２のフローチャートに示す処理動作は、例えば、車載ナビゲーション装置に電源が供給されているときに所定時間毎に実行されたり、経路案内中に所定時間毎に実行されたり、経路案内の開始時又は交通情報の受信時に実行されるものである。
【００３５】
ステップＳ１０では、制御装置３は、交通情報が有り、かつ、経路が有るか否かを判定する。つまり、制御装置３は、外部メモリ６などに通信装置４にて受信した交通情報が記憶されているか否かを確認する。さらに、制御装置３は、出発地（例えば、現在地）から目的地までの経路（例えば、経路案内中の案内経路、案内開始前に交通情報を考慮せずに探索した所期経路など）を設定しているか否かを確認する。そして、交通情報が有り、経路を設定していると判定した場合はステップＳ１１へ進み、交通情報がない、もしくは経路を設定していないと判定した場合は処理を終了する。
【００３６】
ステップＳ１１では、制御装置３は、地図データを取得して、設定している経路上の交通事象を特定する。つまり、通信装置４にて受信した交通情報に、設定している経路上に該当する交通事象が含まれているか否かを確認する。換言すると、設定している経路上に渋滞情報や交通規制等の交通事象が発生しているか否かを確認する。そして、ステップＳ１２では、制御装置３は、経路上に交通事象があると判定した場合は経路の再探索が必要であるとみなしてステップＳ１３へ進み、経路上に交通事象がないと判定した場合は経路の再探索は必要ないとみなして処理を終了する。
【００３７】
ステップＳ１３では、制御装置３は、地図データを取得して、出発地及び目的地周辺（出発地及び目的地を含む）の最下層（レベル１）の地図データＤ１（分割エリア）及びＤ２（分割エリア）を特定し（図３参照）、この特定した地図データＤ１及びＤ２の経路上に交通事象を含んでいるか否かを判定する。そして、ステップＳ１４では、制御装置３は、含んでいると判定した場合は処理を終了し、含んでいないと判定した場合はステップＳ１５へ進む。ここで、出発地及び目的地周辺の最下層の地図データＤ１及びＤ２の経路上に交通事象が含まれていた場合に処理を終了するのは、もともと（従来の処理動作時に）、出発地及び目的地の周辺においては、最下層の地図データを用いて経路探索を行うため、ステップＳ１５以降の処理を行う必要がないためである。
【００３８】
ステップＳ１５では、制御装置３は、地図データを取得して、図３に示すように、経路上の交通事象が発生している位置を含む最下層の地図データ（以下の説明、図面においては、ターゲットデータ（分割エリア）とも称する）を特定する（特定手段）。これは、経路上に発生している交通事象の周辺においては、詳細な地図データ（レベル１の地図データ）を用いて経路を探索することによって、不要な遠回りを抑制するためである。なお、ターゲットデータは、最下層の地図データにおける一つ又は複数の分割エリアを示すものである。
【００３９】
ステップＳ１６では、制御装置３は、地図データ、各階層間の接続情報などを取得して（地図データ取得手段）、現在地（又は目的地）からターゲットデータ内まで、階層構造の地図データに基づいて経路を再探索する。つまり、現在地（又は目的地）周辺の最下層の地図データ及びターゲットデータの接続情報に基づき、特定された地図データ（現在地（又は目的地）周辺の最下層の地図データ及びターゲットデータ）において上位階層へ接続する点或いは部分まで経路探索を行ない、さらに上位階層に移行して接続点（部分）からの経路探索を繰り返し行なう（経路探索手段）。
【００４０】
一方、ステップＳ１７では、制御装置３は、地図データ、各階層間の接続情報などを取得して（地図データ取得手段）、ターゲットデータ内から目的地（又は現在地）まで、階層構造の地図データに基づいて経路を再探索して、この再探索結果とステップＳ１６の再探索結果とによって経路を作成する。つまり、目的地（又は現在地）周辺の最下層の地図データ及びターゲットデータの接続情報に基づき、特定された地図データ（目的地（又は現在地）周辺の最下層の地図データ及びターゲットデータ）において上位階層へ接続する点或いは部分まで経路探索を行ない、さらに上位階層に移行して接続点（部分）からの再経路探索を繰り返し行なう（経路探索手段）。そして、この探索結果とステップＳ１６の探索結果とによって経路を作成する（経路探索手段）。
【００４１】
つまり、制御装置３は、ステップＳ１５でターゲットデータを特定した場合、そのターゲットデータを含めて現在地（現在地を出発する地点とする場合は出発地）から目的地までの経路を再探索する（経路探索手段）。
【００４２】
このように、階層化された地図データを用いて出発地から目的地までの経路を探索するものにおいて、探索された経路に発生している交通事象を含む交通情報を有している場合は、交通事象が発生している位置を含む最下層の地図データ（ターゲットデータ）を特定して、この特定したターゲットデータを含めて経路を再探索することによって、交通事象が発生している地点の周辺を詳細な地図データで探索できる。よって、交通事象を回避しつつ、不用に遠回りとなる経路を探索してしまうことを抑制でき、より最適な代替経路を探索できる。
【００４３】
また、本実施の形態においては、探索された経路に発生している交通事象を含む交通情報を有している場合に、交通事象が発生している位置を含む最下層の地図データ（ターゲットデータ）を特定して、この特定したターゲットデータを含めて経路を再探索する例を採用して説明したが本発明はこれに限定されるものではない。ここで、本発明の変形例にける車載ナビゲーション装置に関して説明する。なお、上述の実施の形態における車載ナビゲーション装置と変形例における車載ナビゲーション装置とは、構成（図１）に関しては同等であるため詳しい説明は省略して、異なる点を重点的に説明する。ただし、変形例の車載ナビゲーション装置においては、必ずしも通信装置４は必要ない。
【００４４】
上述の実施の形態における車載ナビゲーション装置と変形例における車載ナビゲーション装置とで異なる点は、ユーザーによって経由地点が指示されるとターゲットデータを特定して、この特定したターゲットデータを含めて経路を再探索する点である。つまり、制御装置３は、操作スイッチ群５から経由地を示す信号（経由位置情報）が入力された場合（経由位置情報取得手段）、ターゲットデータを特定して、この特定したターゲットデータを含めて経路を再探索する。
【００４５】
ここで、図４を用いて、変形例における車載ナビゲーション装置の処理動作に関して説明する。
【００４６】
まず、ステップＳ２０では、制御装置３は、経由地が有り、かつ、経路が有るか否かを判定する。つまり、制御装置３は、操作スイッチ群５から経由位置情報が入力されているか否かを確認する。さらに、制御装置３は、出発地（例えば、現在地）から目的地までの経路（例えば、経路案内中の案内経路、案内開始前に交通情報を考慮せずに探索した所期経路など）を設定しているか否かを確認する。そして、経由位置情報が有り、経路を設定していると判定した場合はステップＳ２１へ進み、経由位置情報がない、もしくは経路を設定していないと判定した場合は処理を終了する。
【００４７】
ステップＳ２１では、制御装置３は、地図データを取得して、出発地及び目的地周辺（出発地及び目的地を含む）の最下層（レベル１）の地図データＤ１及びＤ２（図３参照）を特定し、この特定した地図データＤ１及びＤ２が経由位置情報を含んでいるか否かを判定する。そして、ステップＳ２２では、制御装置３は、含んでいると判定した場合は処理を終了し、含んでいないと判定した場合はステップＳ２３へ進む。ここで、出発地及び目的地周辺の最下層の地図データＤ１及びＤ２に経由位置情報が含まれていた場合に処理を終了するのは、もともと（従来の処理動作時に）、出発地及び目的地の周辺においては、最下層の地図データを用いて経路探索を行うため、ステップＳ２３以降の処理を行う必要がないためである。
【００４８】
ステップＳ２３では、制御装置３は、地図データを取得して（地図データ取得手段）、ユーザーによって指示された経由地を含む最下層の地図データ（ターゲットデータ）を特定する（特定手段）。これは、経由地の周辺においては、詳細な地図データ（レベル１の地図データ）を用いて経路を探索することによって、不要な遠回りを抑制するためである。
【００４９】
なお、ステップＳ２４、Ｓ２５に関しては、上述の実施の形態における図２のステップＳ１６、Ｓ１７と同等であるため説明は省略する。
【００５０】
このように、階層化された地図データを用いて出発地から目的地までの経路を探索するものにおいて、ユーザーによって指示される経由地点の経由位置情報を取得した場合、経由位置情報が示す位置を含む最下層の地図データ（ターゲットデータ（分割エリア））を特定して、この特定したターゲットデータを含めて経路を再探索することによって、ユーザーによって指示された経由地点の周辺を詳細な地図データで探索できる。つまり、ユーザーによって指示された経由地点の周辺の狭い範囲に限定されることなく探索できる。よって、最適な経路が他にもあるにもかかわらず、別の経路を探索してしまうことを抑制でき、より最適な代替経路を探索できる。
【００５１】
なお、上述の変形例においては、ユーザーによって経由地点が指示される例を採用して説明したが、本発明はこれに限定されるものではない。この経由地点は、車両（車載ナビゲーション装置の通信装置４）と通信接続が可能なセンター（サーバー、図示省略）から指示されるようにしてもよい。
【００５２】
この場合、センターは、地図データを記憶した記憶装置、車両（車載ナビゲーション装置の通信装置４）との通信を行なう通信装置、記憶装置から取得した地図データを用いた経路探索、通信装置による通信の制御などを実行可能なサーバーなどを備える構成を採用することができる。一方、車載ナビゲーション装置の制御装置３は、所定のタイミング（例えば、目的地が設定された時点、経路案内中に所定時間毎、経路案内の開始時など）で車両の現在地、及び目的地を通信装置４を介してセンター（センター側の通信装置を介してサーバー）に送信する。
【００５３】
この現在地と目的地を取得したセンター（サーバー）は、取得した車両の現在地から目的地までの最適な経路を探索する。また、センター（サーバー）は、この探索結果から最適な経路を通るための経由地点を検索する。そして、センター（サーバー）は、検索した経由地点（経由位置情報）を車両（車載ナビゲーション装置の通信装置４）に送信する。つまり、経由地点を指示する。
【００５４】
このように、センター（サーバー）によって経由地点を指示された場合であっても、経由地点の周辺の狭い範囲に限定されることなく探索できる。よって、最適な経路が他にもあるにもかかわらず、別の経路を探索してしまうことを抑制でき、より最適な代替経路を探索できる。
【００５５】
通常、車両に搭載される制御装置（マイコン）に比べて、センターなどに設置されるサーバーの方が処理能力は高く、また、情報量（地図データや交通情報など）が多い。従って、センターに設置されたサーバーは、車載ナビゲーション装置で探索された経路よりも最適な経路を探索できる可能性がある。よって、センターに設置されたサーバーにて探索された経路から検索された経由地点を指示することによって、車載ナビゲーション装置（車両に搭載される制御装置（マイコン））においても、より一層最適な経路探索を行うことができる。
【００５６】
また、上述の実施の形態、及び変形例においては、ターゲットデータ（分割エリア）は、一つである例を採用して説明したが、本発明はこれに限定されるものではない。複数のターゲットデータ（分割エリア）を特定できるようにしてもよい。
【００５７】
例えば、特定した複数のターゲットデータが隣り合わせの場合、複数のターゲットデータに渡って経路探索を行い、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうようにしてもよい。つまり、現在地（又は目的地）から複数のターゲットデータ内まで、階層構造の地図データに基づいて経路を探索する。具体的には、現在地（又は目的地）周辺の最下層の地図データ及び複数のターゲットデータのうちの一つ（現在地（又は目的地）から最も近いターゲットデータ）の接続情報に基づき、特定された地図データ（現在地（又は目的地）周辺の最下層の地図データ及び最も近いターゲットデータ）において上位階層へ接続する点或いは部分まで経路探索を行ない、さらに上位階層に移行して接続点（部分）からの経路探索を繰り返し行なう（経路探索手段）。そして、複数のターゲットデータ間で経路探索を行う。
【００５８】
一方、複数のターゲットデータ内から目的地（又は現在地）まで、階層構造の地図データに基づいて経路を探索して、この探索結果とステップＳ１６の探索結果とによって経路を作成する。つまり、目的地（又は現在地）周辺の最下層の地図データ及び複数のターゲットデータのうちの一つ（目的地（又は現在地）から最も近いターゲットデータ）の接続情報に基づき、特定された地図データ（目的地（又は現在地）周辺の最下層の地図データ及び最も近いターゲットデータ）において上位階層へ接続する点或いは部分まで経路探索を行ない、さらに上位階層に移行して接続点（部分）からの経路探索を繰り返し行なう（経路探索手段）。そして、この探索結果と上述の現在地（又は目的地）から複数のターゲットデータ内までの探索結果とによって経路を作成する（経路探索手段）。
【００５９】
このように、特定された複数のターゲットデータが隣り合わせの場合は、そのターゲットデータ間において上位層の地図データを探索することなく、複数の最下層の地図データに渡って経路探索を行うことによって探索時間を短縮することができる。
【００６０】
また、特定されたターゲットデータが隣り合わせでない場合は、最下層の地図データのそれぞれにおいては、接続情報に基づいて上位階層の地図データへ接続する点まで経路探索を行い、その後上位層の地図データを探索する（経路探索手段）ことによって、経路の途中で最下層の地図データを用いて経路探索した場合であっても、出発地から目的地までの経路を探索することができる。つまり、現在地（又は目的地）からターゲットデータ内の経路探索が終了した地図データと、探索が完了していない地図データ間で経路探索を繰り返す。具体的には、現在地（又は目的地）から現在地（又は目的地）に近いターゲットデータ内の経路探索と、ターゲットデータ内から別のターゲットデータ内の経路計算と、目的地（又は現在地）からターゲットデータ内の経路探索とを行い、これらの探索結果によって経路を作成する（経路探索手段）。
【００６１】
さらに、経路上に交通事象が発生しており、ターゲットデータが複数ある場合は、各ターゲットデータに含まれる交通事象（各ターゲットデータに含まれる経路に発生している交通事象）の重要度に応じて、再経路計算に含めるターゲットデータと含めないターゲットデータを選択するようにしてもよい。換言すると、重要度に応じて、交通事象とみなすか否かを選択する。
【００６２】
この場合、交通事象を重要度に応じて区分しておく。重要度は、例えば、渋滞１ｋｍよりも渋滞１０ｋｍの方が重要度大、渋滞よりも交通規制（通行禁止）の方が重要度大などとすることができる。このとき、交通情報は、渋滞情報や交通規制等の道路に発生している交通事象と、その交通事象が発生している位置を示す位置情報と、その交通事象の重要度を含むものである。
【００６３】
そして、制御装置３は、交通事象が発生している位置を含む複数の最下層の地図データ（ターゲットデータ）を特定した場合、各ターゲットデータに対応する交通事象の重要度を確認する（確認手段）。そして、制御装置３は、重要度に関する所定の条件を満たしている交通事象を含むターゲットデータを再経路探索に用いるものとして選択する（選択手段）。
【００６４】
所定の条件としては、例えば、重要度が最も大きい、重要度に応じて付与されたポイントの合計値が最も大きい（一つのターゲットデータに対応する交通事象が複数あった場合）、重要度に応じて付与されたポイントの合計値が所定値以上（同様に交通事象が複数あった場合）、重要度が最も小さくない、重要度に応じて付与されたポイントの合計値が最も小さくない（一つのターゲットデータに対応する交通事象が複数あった場合）などを採用することができる。
【符号の説明】
【００６５】
１ 位置検出器、１ａ 地磁気センサー、１ｂ ジャイロスコープ、１ｃ 距離センサー、１ｄ ＧＰＳ受信機、２ 地図データ入力器、３ 制御装置、４ 通信装置、５ 操作スイッチ群、６ 外部メモリ、７ 表示装置、８ 音声出力装置
【特許請求の範囲】
【請求項１】
出発地から目的地までの経路を探索する経路探索装置であって、
道路網の情報の多い下位階層から道路網の情報の少ない上位階層へと複数段に階層化された地図データ、及び各階層の接続情報を取得する地図データ取得手段と、
前記地図データに基づいて、前記出発地および前記目的地を含む階層の地図データを特定し、各階層間の前記接続情報に基づいて当該特定された階層の地図データにおいて上位階層の地図データへ接続する点まで経路探索を行ない、さらに上位階層の地図データに移行して当該接続する点からの経路探索を繰り返し行なうことによって前記出発地から前記目的地までの経路探索を行なう経路探索手段と、
道路に発生している交通事象と当該交通事象が発生している位置を示す位置情報とを含む交通情報を取得する交通情報取得手段と、
前記経路探索手段にて探索された経路に発生している交通事象を含む交通情報を有している場合、当該交通事象が発生している位置を含む最下層の地図データを特定する特定手段と、を備え、
前記経路探索手段は、前記特定手段にて最下層の地図データが特定された場合、当該特定された最下層の地図データを含めて経路を再探索することを特徴とする経路探索装置。
【請求項２】
出発地から目的地までの経路を探索する経路探索装置であって、
道路網の情報の多い下位階層から道路網の情報の少ない上位階層へと複数段に階層化された地図データ、及び各階層の接続情報を取得する地図データ取得手段と、
前記地図データに基づいて、前記出発地および前記目的地を含む階層の地図データを特定し、各階層間の前記接続情報に基づいて当該特定された階層の地図データにおいて上位階層の地図データへ接続する点まで経路探索を行ない、さらに上位階層の地図データに移行して当該接続する点からの経路探索を繰り返し行なうことによって前記出発地から前記目的地までの経路探索を行なう経路探索手段と、
指示される経由地点の経由位置情報を取得する経由位置情報取得手段と、
前記経由位置情報取得手段にて、経由位置情報を取得した場合、当該経由位置情報が示す位置を含む最下層の地図データを特定する特定手段と、を備え、
前記経路探索手段は、前記特定手段にて最下層の地図データが特定された場合、当該特定された最下層の地図データを含めて経路を再探索することを特徴とする経路探索装置。
【請求項３】
前記経路探索手段は、前記特定手段にて特定された最下層の地図データが複数あり、当該複数の最下層の地図データが隣り合わせの場合、当該複数の最下層の地図データに渡って経路探索を行い、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうことを特徴とする請求項１又は２に記載の経路探索装置。
【請求項４】
前記経路探索手段は、前記特定手段にて特定された最下層の地図データが複数あり、当該複数の最下層の地図データが隣り合わせでない場合、当該特定された最下層の地図データのそれぞれにおいては、前記接続情報に基づいて上位階層の地図データへ接続する点まで経路探索を行ない、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうことを特徴とする請求項１又は２に記載の経路探索装置。
【請求項１】
出発地から目的地までの経路を探索する経路探索装置であって、
道路網の情報の多い下位階層から道路網の情報の少ない上位階層へと複数段に階層化された地図データ、及び各階層の接続情報を取得する地図データ取得手段と、
前記地図データに基づいて、前記出発地および前記目的地を含む階層の地図データを特定し、各階層間の前記接続情報に基づいて当該特定された階層の地図データにおいて上位階層の地図データへ接続する点まで経路探索を行ない、さらに上位階層の地図データに移行して当該接続する点からの経路探索を繰り返し行なうことによって前記出発地から前記目的地までの経路探索を行なう経路探索手段と、
道路に発生している交通事象と当該交通事象が発生している位置を示す位置情報とを含む交通情報を取得する交通情報取得手段と、
前記経路探索手段にて探索された経路に発生している交通事象を含む交通情報を有している場合、当該交通事象が発生している位置を含む最下層の地図データを特定する特定手段と、を備え、
前記経路探索手段は、前記特定手段にて最下層の地図データが特定された場合、当該特定された最下層の地図データを含めて経路を再探索することを特徴とする経路探索装置。
【請求項２】
出発地から目的地までの経路を探索する経路探索装置であって、
道路網の情報の多い下位階層から道路網の情報の少ない上位階層へと複数段に階層化された地図データ、及び各階層の接続情報を取得する地図データ取得手段と、
前記地図データに基づいて、前記出発地および前記目的地を含む階層の地図データを特定し、各階層間の前記接続情報に基づいて当該特定された階層の地図データにおいて上位階層の地図データへ接続する点まで経路探索を行ない、さらに上位階層の地図データに移行して当該接続する点からの経路探索を繰り返し行なうことによって前記出発地から前記目的地までの経路探索を行なう経路探索手段と、
指示される経由地点の経由位置情報を取得する経由位置情報取得手段と、
前記経由位置情報取得手段にて、経由位置情報を取得した場合、当該経由位置情報が示す位置を含む最下層の地図データを特定する特定手段と、を備え、
前記経路探索手段は、前記特定手段にて最下層の地図データが特定された場合、当該特定された最下層の地図データを含めて経路を再探索することを特徴とする経路探索装置。
【請求項３】
前記経路探索手段は、前記特定手段にて特定された最下層の地図データが複数あり、当該複数の最下層の地図データが隣り合わせの場合、当該複数の最下層の地図データに渡って経路探索を行い、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうことを特徴とする請求項１又は２に記載の経路探索装置。
【請求項４】
前記経路探索手段は、前記特定手段にて特定された最下層の地図データが複数あり、当該複数の最下層の地図データが隣り合わせでない場合、当該特定された最下層の地図データのそれぞれにおいては、前記接続情報に基づいて上位階層の地図データへ接続する点まで経路探索を行ない、さらに上位階層の地図データに移行して接続する点からの経路探索を繰り返し行なうことを特徴とする請求項１又は２に記載の経路探索装置。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１１−６４４９０（Ｐ２０１１−６４４９０Ａ）
【公開日】平成２３年３月３１日（２０１１．３．３１）
【国際特許分類】
【出願番号】特願２００９−２１３３７４（Ｐ２００９−２１３３７４）
【出願日】平成２１年９月１５日（２００９．９．１５）
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
【公開日】平成２３年３月３１日（２０１１．３．３１）
【国際特許分類】
【出願日】平成２１年９月１５日（２００９．９．１５）
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
[ Back to top ]