(57)【要約】【課題】ナビゲーション装置において、道路ネットワークデータのデータ量を従来よりも低減する。【解決手段】主要道路２０上のノードが、他の主要道路２１、２５に接続する格上ノード３０、３１、３５、３６と、非主要道路２２〜２４に接続する格下ノード３２〜３４とに区別され、道路ネットワークデータは、リンク情報データフレームおよび格下ノード接続情報データフレームを含み、リンク情報データフレームは、単位区間４１〜４３のそれぞれを通過する場合のコストを特定する情報を含み、単位区間４２は、主要道路２０上における格上ノード同士３１、３５を他の格上ノードを介さずに繋ぐと共に格下ノード３２〜３４を含む。また、格下ノード接続情報データフレームには、格下ノード３２〜３４のそれぞれから直近の格上ノードまでの付加道路区間７１〜７６の情報として、付加道路区間７１〜７６のそれぞれを通過した場合のコストを特定する情報が含まれる。【選択図】図３
2010243306.tif 000002
【特許請求の範囲】
【請求項１】
出発地点から目的地点までの誘導経路の案内を行うナビゲーション装置であって、
道路ネットワークデータが記録された記憶媒体と、
前記記憶媒体に記録された前記道路ネットワークデータを用いて、出発地点から目的地点までの誘導経路を算出する誘導経路算出手段と、を備え、
前記道路ネットワークデータにおいては、第１の主要道路（２０）上の複数のノード（３１〜３６）が、他の主要道路（２１、２５）に接続する複数の格上ノード（３０、３１、３５、３６）と、非主要道路（２２〜２４）に接続する複数の格下ノード（３２〜３４）と、に区別され、
前記道路ネットワークデータには、リンク情報データフレームおよび格下ノード接続情報データフレームが含まれ、
前記リンク情報データフレームには、複数の単位区間（４１〜４３）のそれぞれについて、当該単位区間（４１〜４３）を通過する場合のコストを特定するための単位道路区間コスト特定情報が含まれ、前記複数の単位区間（４１〜４３）のうち少なくとも１つは、前記第１の主要道路（２０）上における第１の格上ノード（３１）および第２の格上ノード（３５）を他の格上ノードを介さずに繋ぐと共に格下ノード（３２〜３４）を含む単位道路区間（４２）であり、
前記格下ノード接続情報データフレームには、前記第１の主要道路（２０）上における前記複数の格下ノード（３２〜３４）のそれぞれから直近の格上ノード（３１、３５）までの付加道路区間（７１〜７６）の情報として、それら複数の付加道路区間（７１〜７６）のそれぞれを通過した場合のコストを特定するための情報が含まれ、
前記誘導経路算出手段は、出発地点のノードから目的地点のノードまで、前記複数の単位区間（４１〜４３）および前記複数の付加道路区間（７１〜７６）に沿って探索範囲を順次拡大することで、当該複数の単位区間（４１〜４３）および複数の付加道路区間（７１〜７６）を通過した場合のコストに基づいて、当該探索範囲内の各ノードまでの最小コストおよび最小コストとなる経路を確定していき、それにより、出発地点のノードから目的地点のノードまでの最小コストとなる経路を算出することを特徴とするナビゲーション装置。
【請求項２】
前記道路ネットワークデータは、テーブル番号およびコストの値から成る組を複数組含むリンクコストテーブルを有し、
前記リンク情報データフレームに含まれる前記単位道路区間コスト情報は、前記リンクコストテーブルのテーブル番号を示しており、
前記誘導経路算出手段は、単位道路区間のコストを算出する際、当該単位道路区間についての単位道路区間コスト情報が示すテーブル番号をリンクコストテーブルから検索し、その結果見つかったテーブル番号と組になっているコスト値を、当該単位道路区間のコストの値として採用することを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
出発地点から目的地点までの誘導経路の案内を行うナビゲーション装置が前記誘導経路を算出するために用いる道路ネットワークデータであって、
第１の主要道路（２０）上の複数のノード（３１〜３６）が、他の主要道路（２１、２５）に接続する複数の格上ノード（３０、３１、３５、３６）と、非主要道路（２２〜２４）に接続する複数の格下ノード（３２〜３４）と、に区別され、
リンク情報データフレームおよび格下ノード接続情報データフレームを含み、
前記リンク情報データフレームには、複数の単位区間（４１〜４３）のそれぞれについて、当該単位区間（４１〜４３）を通過する場合のコストを特定するための単位道路区間コスト特定情報が含まれ、前記複数の単位区間（４１〜４３）のうち少なくとも１つは、前記第１の主要道路（２０）上における第１の格上ノード（３１）および第２の格上ノード（３５）を他の格上ノードを介さずに繋ぐと共に格下ノード（３２〜３４）を含む単位道路区間（４２）であり、
前記格下ノード接続情報データフレームには、前記第１の主要道路（２０）上における前記複数の格下ノード（３２〜３４）のそれぞれから直近の格上ノード（３１、３５）までの付加道路区間（７１〜７６）の情報として、それら複数の付加道路区間（７１〜７６）のそれぞれを通過した場合のコストを特定するための情報が含まれていることを特徴とする道路ネットワークデータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置および道路ネットワークデータに関するものである。
【背景技術】
【０００２】
従来、出発地点から目的地点までの誘導経路を算出して案内を行うナビゲーション装置において、誘導経路を算出するために、階層構造の道路ネットワークデータを利用する技術が広く知られている（例えば、特許文献１参照）。
【０００３】
階層構造の道路ネットワークデータにおいては、道路が主要道路（例えば高速道路、国道）と非主要道路（例えば県道、細街路）に区別され、道路ネットワークデータの下位層には主要道路と非主要道路の両方のデータが含まれ、上位層には主要道路のデータのみが含まれるようになっている。
【０００４】
このような構成の階層構造の道路ネットワークデータを用いれば、周知の通り、誘導経路計算の際には、出発地点の周辺および目的地点の周辺においては下位層のデータを用いて経路計算を行い、それ以外の部分では、上位層のデータを用いて主要道のみを通る経路について経路計算を行う（例えば、特許文献１参照）。このようにすることで、誘導経路の算出に要する処理負荷が低減し、誘導経路の算出処理が高速化する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平１１−２４８４７４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、このような階層構造の道路ネットワークデータは、同じリンクまたはノードを表すデータが上位層と下位層の両方に重複して含まれるので、道路ネットワークデータのデータ量が多くなってしまう。
【０００７】
本発明は上記点に鑑み、出発地点から目的地点までの誘導経路を算出して案内を行うナビゲーション装置において、道路ネットワークデータのデータ量を従来よりも低減することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するための請求項１に記載の発明は、出発地点から目的地点までの誘導経路の案内を行うナビゲーション装置であって、道路ネットワークデータが記録された記憶媒体と、当該記憶媒体に記録された当該道路ネットワークデータを用いて、出発地点から目的地点までの誘導経路を算出する誘導経路算出手段と、を備え、当該道路ネットワークデータにおいては、第１の主要道路（２０）上の複数のノード（３１〜３６）が、他の主要道路（２１、２５）に接続する複数の格上ノード（３０、３１、３５、３６）と、非主要道路（２２〜２４）に接続する複数の格下ノード（３２〜３４）と、に区別され、当該道路ネットワークデータには、リンク情報データフレームおよび格下ノード接続情報データフレームが含まれている。
【０００９】
このリンク情報データフレームには、複数の単位区間（４１〜４３）のそれぞれについて、当該単位区間（４１〜４３）を通過する場合のコストを特定するための情報が含まれ、当該複数の単位区間（４１〜４３）のうち少なくとも１つは、当該第１の主要道路（２０）上における第１の格上ノード（３１）および第２の格上ノード（３５）を他の格上ノードを介さずに繋ぐと共に格下ノード（３２〜３４）を含む単位道路区間（４２）である。
【００１０】
また、格下ノード接続情報データフレームには、第１の主要道路（２０）における当該複数の格下ノード（３２〜３４）のそれぞれから直近の格上ノード（３１、３５）までの付加道路区間（７１〜７６）の情報として、それら複数の付加道路区間（７１〜７６）のそれぞれを通過した場合のコストを特定するための情報が含まれる。
【００１１】
また、誘導経路算出手段は、出発地点のノードから目的地点のノードまで、当該複数の単位区間（４１〜４３）および当該複数の付加道路区間（７１〜７６）に沿って探索範囲を順次拡大することで、当該複数の単位区間（４１〜４３）および複数の付加道路区間（７１〜７６）を通過した場合のコストに基づいて、当該探索範囲内の各ノードまでの最小コストおよび最小コストとなる経路を確定していき、それにより、出発地点のノードから目的地点のノードまでの最小コストとなる経路を算出する。
【００１２】
道路ネットワークデータがこのような非階層構造をとなっていることで、同じリンクまたはノードに複数の異なるデータが重複して割り当てられる必要がない。したがって、従来の階層構造の道路ネットワークデータに比べて、データ量が少なくなる。
【００１３】
また、第１の格上ノード（３１）から第２の格上ノード（３１）までの経路は、複数のリンクから成るものの、１つの単位道路区間であり、また、リンク情報データフレームにおいては、単位道路区間毎にコストを特定するための情報が記録されている。したがって、ナビゲーション装置は、単一のリンクレコード（すなわち、単位道路区間４２に対応する道路区間）のコストテーブル番号を参照するだけで、当該経路のコストを算出することができる。すなわち、第１の格上ノード（３１）から第２の格上ノード（３５）までの経路のコストについては、リンク毎にコストを特定してそれらを総和するといった煩雑な処理をして算出する必要がない。
【００１４】
このようになっているので、第１の主要道路（２０）におけるコスト計算が簡素化され、その結果、誘導経路算出に要する処理負荷が低下し、ひいては、誘導経路の算出に要する時間が短くなる。
【００１５】
また、請求項２に記載のように、道路ネットワークデータは、テーブル番号およびコストの値から成る組を複数組含むリンクコストテーブルを有し、リンク情報データフレームに含まれる単位道路区間コスト情報は、当該リンクコストテーブルのテーブル番号を示しており、当該誘導経路算出手段は、単位道路区間のコストを算出する際、当該単位道路区間についての単位道路区間コスト情報が示すテーブル番号をリンクコストテーブルから検索し、その結果見つかったテーブル番号と組になっているコスト値を、当該単位道路区間のコストの値として採用するようになっていてもよい。
【００１６】
一般に、道路ネットワークデータ中の全ての単位道路区間でコストの値が違っている可能性は極めて低く、むしろ多くの単位道路区間でコストの値が同じとなる可能性が高い。すなわち、１つの道路ネットワークデータ中では、単位道路区間の数よりも、単位道路区間のコスト値のバリエーションの数の方が、遙かに少ない。
【００１７】
そこで、上記のように、単位道路区間のコストの情報をリンクコストテーブルとし、リンクコストテーブルにおいては、コスト値とそのコスト値のテーブル番号とを対応付けるようにしている。そして、リンク情報データフレームの単位道路区間コスト情報には、テーブル番号を示す情報を含ませていことで、道路ネットワークデータのデータサイズを大幅に低減することができる。
【００１８】
また、請求項３に記載のように、請求項１に記載のナビゲーション装置において誘導経路を算出するために用いる道路ネットワークデータとして、本発明を捉えることもできる。
【００１９】
なお、上記および特許請求の範囲における括弧内の符号は、特許請求の範囲に記載された用語と後述の実施形態に記載される当該用語を例示する具体物等との対応関係を示すものである。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施形態に係る車両用ナビゲーション装置１の構成図である。
【図２】道路構造の一例を示す図である。
【図３】本実施形態に係る道路ネットワークデータの構成例を示す図である。
【図４】従来の階層構造の道路ネットワークデータの構成例を示す図である。
【図５】本実施形態に係る道路ネットワークデータの詳細構成を示す図である。
【図６】従来の地図データによる経路６１、６２、６３と本実施形態の地図データによる経路６４、６３とを示す図である。
【発明を実施するための形態】
【００２１】
以下、本発明の一実施形態について説明する。図１に、本実施形態に係る車両用ナビゲーション装置１のハードウェア構成を示す。この車両用ナビゲーション装置１は、車両に搭載され、位置検出器１１、画像表示装置１２、操作部１３、スピーカ１４、地図データ取得部１６、および制御回路１７を有している。
【００２２】
位置検出器１１は、いずれも周知の図示しない加速度センサ、地磁気センサ、ジャイロセンサ、車速センサ、およびＧＰＳ受信機等のセンサを有しており、これらセンサの各々の性質に基づいた、車両の現在位置、向き、および速度を特定するための情報を制御回路１７に出力する。
【００２３】
画像表示装置１２は、制御回路１７から出力された映像信号に基づいた映像をユーザに表示する。表示映像としては、例えば現在地を中心とする地図等がある。
【００２４】
操作部１３は、車両用ナビゲーション装置１に設けられた複数のメカニカルスイッチ、画像表示装置１２の表示面に重ねて設けられたタッチパネル等の入力装置から成り、ユーザによるメカニカルスイッチの押下、タッチパネルのタッチに基づいた信号を制御回路１７に出力する。
【００２５】
地図データ取得部１６は、ＤＶＤ、ＣＤ、ＨＤＤ等の不揮発性の記憶媒体およびそれら記憶媒体に対してデータの読み出し（および可能ならば書き込み）を行う装置から成る。当該記憶媒体は、制御回路１７が実行するプログラム、および地図データ等を記憶している。地図データ取得部１６は、この記憶媒体から地図データを取得して制御回路１７に出力する。
【００２６】
地図データは、地図表示用の道路形状データ、目的地検索用の施設データ、および誘導経路計算用の道路ネットワークデータ等を含んでいる。道路形状データは、複数のリンクのそれぞれについて、そのリンクを固有に識別するリンクＩＤおよびそのリンクの形状を示す形状情報を含んでいる。施設データは、施設毎のレコードを複数有しており、各レコードは、対象とする施設の名称情報、所在位置情報、土地地番情報、施設種類情報等を示すデータを有している。道路ネットワークデータは、リンクとノードとの接続関係、リンクのコスト等の情報を含む。
【００２７】
なお、本実施形態においては、ノードは、交差点、道路分岐点、道路合流点等、２本以上の道路が接続する地点そのものを指す用語であって、ノードそれ自体はデータではないとする。また、リンクとは、２つのノードを直接（すなわち他のノードを介さず）繋ぐ道路区間そのものを指す用語であって、リンクそれ自体はデータではないとする。地図データ中でリンクを表すデータおよびノードを表すデータについては後述する。
【００２８】
制御回路（コンピュータに相当する）１７は、ＣＰＵ、ＲＡＭ、ＲＯＭ、Ｉ／Ｏ等を有するマイコンである。ＣＰＵは、ＲＯＭまたは地図データ取得部１６から読み出した車両用ナビゲーション装置１の動作のためのプログラムを実行し、その実行の際にはＲＡＭ、ＲＯＭ、および地図データ取得部１６から情報を読み出し、ＲＡＭおよび（可能であれば）地図データ取得部１６の記憶媒体に対して情報の書き込みを行い、位置検出器１１、画像表示装置１２、操作部１３、およびスピーカ１４と信号の授受を行う。
【００２９】
制御回路１７がプログラムを実行することによって行う具体的な処理としては、現在位置特定処理、地図表示処理、誘導経路算出処理、経路案内処理等がある。
【００３０】
現在位置特定処理は、位置検出器１１からの信号に基づいて、周知のマップマッチング等の技術を用いて車両の現在位置や向きを特定する処理である。
【００３１】
地図表示処理は、車両の現在位置の周辺等の特定の領域の地図を、画像表示装置１２に表示させる処理である。この際、地図表示のために用いる情報は、地図データ中の道路形状データから取得する。
【００３２】
誘導経路算出処理は、操作部１３からユーザによる目的地点の入力を受け付け、出発地点（例えば現在位置）から当該目的地点までの最適な誘導経路を、例えばダイクストラ法によって算出する処理である。
【００３３】
経路案内処理は、誘導経路上の右左折交差点等の案内ポイントの手前に自車両が到達したときに、右折、左折等を指示する案内音声をスピーカ１４に出力させ、当該案内ポイントの拡大図を画像表示装置１２に表示させることで、誘導経路に沿った車両の運転を案内する処理である。
【００３４】
以下、本実施形態の特徴について説明する。本実施形態の特徴の１つは、道路ネットワークデータの構造が従来と異なっていることである。本実施形態の道路ネットワークデータの構造について、従来の階層構造の道路ネットワークデータと比較して説明する。
【００３５】
図２に、道路構造の一例を示す。この道路構造においては、主要道路（例えば、高速度路、国道）２０がノード３０〜３６を通るようになっている。そして、同じく主要道である道路２１がノード３１で主要道路２０に接続している。また、非主要道路（例えば、県道、細街路）２２、２３、２４が、それぞれノード３２、３３、３４で、主要道路２０に接続している。また、主要道である道路２５がノード３５で主要道路２０と接続している。
【００３６】
このような道路構造を従来の階層構造の道路ネットワークデータで表現すると、例えば図３のようになる。すなわち、道路ネットワークデータが上位層のデータと下位層のデータを含む。そして、下位層のデータには、主要道路２０、２１、２５を構成するリンク群を表すリンクレコード、非主要道路２２〜２４を構成するリンク群を表すリンクレコード、および、これら道路２０〜２５が相互に接続するノード３０〜３６を表すノードレコードが含まれる。
【００３７】
また、上位層のデータには、主要道路２０、２１、２５を構成するリンク群を表すリンクレコード、および、これら主要道路２０、２１、２５同士が相互に接続するノード３０、３１、３５、３６を表すノードレコードが含まれる。しかし、この上位層のデータには、非主要道路２２〜２４を構成するリンク群を表すリンクレコードが含まれず、また、非主要道路２２〜２４同士が接続するノードを表すノードレコードも含まれず、また、非主要道路２２〜２４と主要道路２０、２１、２５とが交わるノード３２〜３４を表すノードレコードも含まれない。
【００３８】
すなわち、階層構造の道路ネットワークデータにおいては、下位層のデータには、主要道路および非主要道路の両方の道路についてのリンク、ノードのデータが含まれ、上位層のデータには、主要道路と非主要道路のうち、主要道路のみを構成するリンク、ノードのデータしか含まれない。そして、各リンクは、リンクレコードとして記録され、各ノードは、ノードレコードとして記録される。
【００３９】
このような構成の階層構造の道路ネットワークデータを用いれば、周知の通り、誘導経路計算の際には、出発地点の周辺および目的地点の周辺においては下位層のデータを用いて経路計算を行い、それ以外の部分では、上位層のデータを用いて主要道のみを通る経路について経路計算を行う（例えば、特許文献１参照）。このようにすることで、誘導経路の算出に要する処理負荷が低減し、誘導経路の算出処理が高速化する。しかし、同じリンクまたはノードを表すデータが上位層と下位層の両方に重複して含まれるので、道路ネットワークデータのデータ量が多くなってしまう。例えば、ノード３０、３１、３５、３６を表すノードレコードは、上位層と下位層の両方に記録される。また例えば、ノード３０とノード３１を両端とするリンクを表すリンクレコードも、上位層と下位層の両方に記録される。
【００４０】
一方、本実施形態の道路ネットワークデータにおいては、図２のような道路構造は、例えば図４のように構成される。この図４に示すように、本実施形態の道路ネットワークデータは、階層構造とはなっていない。したがって、道路ネットワークデータ中で、１つのリンクを表すデータが重複して存在することもなく、かつ、１つのノードを表すデータが重複して存在することもない。したがって、従来の階層構造の道路ネットワークデータに比べて、データ量が少なくなる。
【００４１】
そして、本実施形態の道路ネットワークデータにおいては、実際には主要道路２０上に位置するノード３０〜３６が、他の主要道路（例えば道路２１、２５）と接続する格上ノード３０、３１、３５、３６と、非主要道路２２〜２４と接続する格下ノード３２〜３４と、に区別されている。
【００４２】
そして、主要道路２０は、格上ノード３０、３１、３５、３６を表すノードレコードと、それら格上ノード３０、３１、３５、３６のいずれかを両端とする道路区間４１、４２、４３を表すリンクレコードとから構成される。すなわち、データ表現上、主要道路２０から格下ノード３２〜３４が分離されている。なお、道路区間４２は、実際には複数のリンクから構成されているが、本実施形態においては、１つのリンクレコードで表すようになっている。
【００４３】
ただし、本実施形態の道路ネットワークデータは、主要道路２０から分離された格下ノード３２〜３４についても、主要道路２０との繋がりを示すデータを含んでいる。具体的には、後述する格下ノード接続情報データフレームが、格下ノード３２〜３４のそれぞれと、主要道路２０上で当該ノードの直近の（すなわち当該ノードに最も近い）両側にある格上ノード３１、３５と、が接続している旨の情報を含んでいる。すなわち、図４中の点線７１〜７６に示す道路区間の情報が、格下ノード接続情報データフレームに含まれる。
【００４４】
以下、上記のような特徴を実現するための本実施形態の道路ネットワークデータの詳細構成について、図５を参照して説明する。本実施形態の道路ネットワークデータは、図５に示すように、リンク情報、ノード情報、ノード接続情報、統合交差点情報、規制詳細情報、およびリンクコストテーブルという、６つのデータフレームを含んでいる。
【００４５】
リンク情報データフレームは、複数のリンクレコードを含み、各リンクレコードは、１つの単位道路区間を表すデータを含んでいる。単位道路区間とは、本実施形態の道路ネットワークデータにおいて、２つのノードを繋ぐ道路区間をいう。
【００４６】
より詳しくは、主要道路２０、２１、２５等の主要道路上においては、２つの格上道路を、他の格上道路を介さずに繋ぐ道路区間が、単位道路区間となる。したがって、例えば図４の主要道路２０上においては、隣り合う格上ノード３０、３１を繋ぐ単位区間４１、隣り合う格上ノード３１、３５を繋ぐ単位区間４２、隣り合う格上ノード３５、３６を繋ぐ単位区間４３が存在する。
【００４７】
このように、主要道路２０上においては、単位道路区間４１、４３は、１つのリンクのみから成る。しかし、単位道路区間４２は、実際には格下ノード３２、３３、３４を含むが故に、複数の連続するリンクから成る。なお、非主要道路２２〜２４、２６等の非主要道路上においては、１つのリンクが１つの単位道路区間となる。
【００４８】
１つの単位道路区間を表すリンクレコードのそれぞれには、差分付きリンクＩＤ、ノード番号、距離、上りコストテーブル番号、下りコストテーブル番号の情報が含まれる。
【００４９】
差分付きリンクＩＤの情報は、当該単位道路区間に含まれるリンクのリンクＩＤのうち、最小のリンクＩＤと、当該単位道路区間に含まれるリンクの数から１を減算した数と、を含むデータである。なお、１つの道路上で連続するリンクには、その並びの順に連番となるリンクＩＤが割り振られている。
【００５０】
例えば、図４の単位道路区間４１に唯一含まれるリンクのリンクＩＤをＸとすると、この単位道路区間４１の差分付きリンクＩＤは、「Ｘプラス０」と表される。また例えば、図４の単位道路区間４２に含まれる４つリンクのリンクＩＤのうち、最小のリンクＩＤをＹとすると、この単位道路区間４２の差分付きリンクＩＤは、「Ｙプラス３」と表される。このような差分付きリンクＩＤを参照することで、単位道路区間４１はリンクＩＤがＸのリンクをただ１つ含んでいることがわかり、単位道路区間４２はリンクＩＤがＹのリンクと、リンクＩＤがそれぞれＹ＋１からＹ＋３となる３つのリンクとを含んでいることがわかる。
【００５１】
ノード番号の情報は、当該単位道路区間の両端に位置するノードの番号の情報である。例えば、単位道路区間４２のリンクレコードにおいては、ノード番号は、ノード３１のノード番号およびノード３５のノード番号を含んでいる。距離の情報は、当該単位道路区間の総行程の距離を示す情報である。
【００５２】
上りコストテーブル番号の情報は、当該単位道路区間を主要道路２０の上り方向（あらかじめ定められている）に通過する場合のコストを示すコストテーブルのテーブル番号である。下りコストテーブル番号の情報は、当該単位道路区間を主要道路２０の下り方向に通過する場合のコストを示すリンクコストテーブルのテーブル番号である。
【００５３】
リンクコストテーブルのデータフレームは、テーブル番号およびコストの値から成る組を複数組含んでいる。一般に、道路ネットワークデータ中の全ての単位道路区間でコストの値が違っている可能性は極めて低く、むしろ多くの単位道路区間でコストの値が同じとなる可能性が高い。すなわち、１つの道路ネットワークデータ中では、単位道路区間の数よりも、単位道路区間のコスト値のバリエーションの数の方が、遙かに少ない。
【００５４】
そこで、本実施形態では、上記のように、単位道路区間のコストの情報をリンクレコードから分離してリンクコストテーブルとし、リンクコストテーブルにおいては、互いに異なるコスト値とそのコスト値のテーブル番号とを対応付けるようにしている。そして、リンクレコードにはそのテーブル番号を示す情報を含ませている。このテーブル番号は、コスト値そのものよりもデータサイズが小さい。それは、コスト値として原理的に可能な値（例えば１６ビット値）のバリエーションの数（例えば１６ビット値なら６５５３６）に比べ、現実に各単位道路区間に割り当てられているコスト値のバリエーションの数の方が遙かに少ないからである。したがって、このようなデータ構造を有することで、道路ネットワークデータのデータサイズを大幅に低減することができる。
【００５５】
換言すれば、経路計算に必要なコストの類型がテーブル化され、リンク情報やノード情報と分離する構成となっていることで、階層化されていない道路ネットワークデータを用いることによる経路探索データの増加を抑制することができる。
【００５６】
また、リンクコストテーブルのデータフレームがこのような構造となっていることで、リンクレコード中の上りコストテーブル番号の情報および下りコストテーブル番号の情報は、当該単位区間を上り方向または下り方向に通過する場合のコストを特定するための単位道路区間コスト特定情報となる。
【００５７】
ノード情報データフレームは、複数のノードレコードを含み、各ノードレコードは、１つのノードを表すデータを含んでいる。ノードレコードのそれぞれには、ノード番号、通行可否情報、規制詳細情報番号、信号機情報等が含まれる。
【００５８】
通行可否情報は、当該ノードにおける進入退出方向毎の通行規制を示す情報である。進入退出方向は、進入リンクと退出リンクの組によって一意に定まる。当該ノードにリンクＡ、リンクＢ、リンクＣが接続している場合、例えば、リンクＡから進入してリンクＢに退出する道路が規制されているという情報が、通行可否情報の一例に該当する。信号機情報は、当該ノードにおける信号機の有無を示す情報である。
【００５９】
規制詳細情報番号の情報は、通行規制の対象となっている進入退出方向の規制内容に対応する規制詳細情報番号を示す情報である。
【００６０】
規制詳細情報データフレームは、複数のレコードから成り、各レコードは、規制詳細情報番号および規制の詳細内容の情報（具体的には時間規制の情報）を含んでいる。一般に、全てのノードで規制の詳細内容が違っている可能性は極めて低く、むしろ多くのノードで規制の詳細内容が同じとなる可能性が高い。すなわち、１つの道路ネットワークデータ中では、ノードの数よりも、規制の詳細内容のバリエーションの数の方が、遙かに少ない。
【００６１】
そこで、本実施形態では、上記のように、ノードの規制の詳細内容の情報をノードレコードから分離して規制詳細情報データフレームとし、規制詳細情報データフレームにおいては、規制の詳細内容と規制詳細情報番号とを対応付けるようにしている。そして、リンクレコードにはその規制詳細情報番号を指定する情報を含ませている。この規制詳細情報番号は、規制の詳細内容の情報そのものよりもデータサイズが小さい。したがって、このようなデータ構造を有することで、道路ネットワークデータのデータサイズを大幅に低減することができる。
【００６２】
統合交差点情報データフレームは、複数のレコードを含み、各レコードは、１つのノードに対応している。レコードのそれぞれには、ノード番号、および交差点詳細情報が含まれる。交差点詳細情報は、対応するノードに該当する交差点（または合流点、分岐点）の詳細を示す情報である。例えば、対応するノードを進行方向別に更に複数のノードに分離した情報が、交差点詳細情報の一例に該当する。
【００６３】
一般に、全てのノードで交差点詳細情報が違っている可能性は極めて低く、むしろ多くのノードで交差点詳細情報が同じとなる可能性が高い。すなわち、１つの道路ネットワークデータ中では、ノードの数よりも、交差点詳細情報のバリエーションの数の方が、遙かに少ない。
【００６４】
そこで、本実施形態では、上記のように、ノードの交差点詳細情報をノードレコードから分離して統合交差点情報データフレームとし、統合交差点情報データフレームにおいては、交差点詳細情報とノード番号とを対応付けるようにしている。したがって、リンクレコード中のノード番号から、当該リンクレコードに対応する交差点詳細情報を特定することができる。したがって、このようなデータ構造を有することで、同じ内容の交差点詳細情報を重複して有することが無くなるので、道路ネットワークデータのデータサイズを大幅に低減することができる。
【００６５】
格下ノード接続情報データフレームは、複数の格下ノードレコードを有し、格下ノードレコードのそれぞれは、１つの格下ノード（例えば、図４における格下ノード３２〜３４）に対応している。
【００６６】
格下ノードレコードのそれぞれは、上りノード番号、上り距離、上りリンクＩＤ差分、下りノード番号、下り距離、および、下りリンクＩＤ差分の情報を含んでいる。
【００６７】
上りノード番号の情報は、当該格下ノードの直近の両側にある格上ノードのうち、上り側にある格上ノードのノード番号を示す情報である。例えば、当該格下ノードが図４のノード３２であり、ノード３０からノード３６への方向が上り方向である場合、上りノード番号は、格上ノード３５のノード番号を示す。
【００６８】
当該格下ノードから上り側にある直近の格上ノードまでの道路区間は、格下ノードから直近の格上ノードまでの道路区間（以下、付加道路区間という）の１つである。したがって、上りノード番号の情報は、付加道路区間を示す情報である。図４においては、道路区間７１〜７６のそれぞれが、付加道路区間に相当する。
【００６９】
上り距離の情報は、当該格下ノードの直近の両側にある格上ノードのうち、上り側にある格上ノードを上り格上ノードとすると、当該格下ノードから上り格上ノードまでの付加道路区間の総行程の距離を示す情報である。
【００７０】
上りリンクＩＤ差分の情報は、当該格下ノードから当該上り格上ノードまでの区間に存在するリンクのＩＤのうち、最小のリンクＩＤと、当該区間に含まれるリンクの数から１を減算した数と、を含むデータである。例えば、当該格下ノードが図４の格下ノード３２であり、ノード３０からノード３６への方向が上り方向であり、ノード３２からノード３５までのリンクＩＤのうち最小のものがＺである場合、上りリンクＩＤ差分は、「Ｚプラス２」と表される。
【００７１】
下りノード番号の情報は、当該格下ノードの直近の両側にある格上ノードのうち、下り側にある格上ノードのノード番号を示す情報である。例えば、当該格下ノードが図４のノード３２であり、ノード３０からノード３６への方向が上り方向である場合、下りノード番号は、格上ノード３１のノード番号を示す。当該格下ノードから下り側にある直近の格上ノードまでの道路区間は、格下ノードから直近の格上ノードまでの付加道路区間の１つである。したがって、下りノード番号の情報は、付加道路区間を示す情報である。
【００７２】
下り距離の情報は、当該格下ノードの直近の両側にある格上ノードのうち、下り側にある格上ノードを下り格上ノードとすると、下り格上ノードから当該格下ノードまでの総行程の距離を示す情報である。
【００７３】
下りリンクＩＤ差分の情報は、当該格下ノードから当該下り格上ノードまでの区間に存在するリンクのＩＤのうち、最小のリンクＩＤと、当該区間に含まれるリンクの数から１を減算した数と、を含むデータである。例えば、当該格下ノードが図４の格下ノード３３であり、ノード３０からノード３６への方向が上り方向であり、ノード３１からノード３３までのリンクＩＤのうち最小のものがＰである場合、上りリンクＩＤ差分は、「Ｐプラス１」と表される。
【００７４】
次に、以上のような道路ネットワークデータを用いて制御回路１７が行う誘導経路計算処理について説明する。
【００７５】
この誘導経路計算においては、出発地点のノードから目的地点のノードまで探索範囲を順次拡大することで、ダイクストラ法等により、出発地点から当該探索範囲内の各ノードまでの最小コストおよび最小コストとなる経路を確定していく。ただし、探索範囲内の各ノードにおいて、当該ノードのノードレコード中で通行制限があるとされている進入退出方向については、当該ノードレコードに含まれる規制詳細情報番号を抽出し、当該規制詳細情報番号を含むレコードを規制詳細情報データフレーム中で検索し、見つかったレコード中の詳細規制内容（すなわち規制のある時間）に基づいて、現在時刻が規制時間内であれば、当該進入退出方向には探索範囲を伸ばさない。
【００７６】
なお、探索範囲中の経路のコストを算出する際に、ノード間を移動する経路として採用するのは、リンクレコードとして記録されている単位道路区間に加え、格下ノード接続情報データフレームに記録されている、格下ノードから直近の格上ノードまでの付加道路区間である。
【００７７】
すなわち、制御回路１７は、誘導経路計算処理において、出発地点のノードから目的地点のノードまで、単位区間および付加道路区間に沿って探索範囲を順次拡大することで、当該単位区間および付加道路区間を通過した場合のコストを加算し、それにより、当該探索範囲内の各ノードまでの最小コストおよび最小コストとなる経路を確定していき、出発地点のノードから目的地点のノードまでの最小コストとなる経路を算出するようになっている。
【００７８】
格下ノード接続情報データフレームに記録されている付加道路区間は、図４の例では、点線で示した付加道路区間７１〜７６である。すなわち、格下ノード接続情報データフレームの格下ノードレコードには、上りノード番号および下りノード番号の情報が含まれているが、当該格下ノードレコードに対応する格下ノード（例えば格下ノード３４）から上りノード番号に対応する格上ノード（例えば格上ノード３５）までの道路区間が、格下ノード接続情報データフレームに記録されている付加道路区間に該当する。また、当該格下ノードレコードに対応する格下ノード（例えば格下ノード３５）から下りノード番号に対応する格上ノード（例えば格上ノード３１）までの道路区間も、格下ノード接続情報データフレームに記録されている付加道路区間に該当する。
【００７９】
このように、格下ノード接続情報データフレームに記録されている道路区間とは、格下ノード（例えば格下ノード３２〜３４のいずれか）から、主要道路２０に沿ってその格下ノードの両側にある直近の格上ノード（例えば格上ノード３１、３５）のそれぞれまでの、付加道路区間をいう。
【００８０】
なお、リンクレコードとして記録されている道路区間の上り方向または下り方向のコストについては、当該リンクレコード中の上りコストテーブル番号または下りコストテーブル番号をリンクコストテーブルから検索し、その結果見つかったテーブル番号と組になっているコスト値を採用する。
【００８１】
また、格下ノード接続情報データフレームに記録されている道路区間のコストの算出方法については、図４の格下ノード３３を例に取って説明する。まず、格下ノード３３から上り側の直近の格上ノード３５までの付加道路区間のコストは、当該格下ノード３３の直近の両端の格上ノード３１、３５の間の単位道路区間４２の上り方向のコストを、上述の通りリンクレコードおよびリンクコストテーブルを用いて決定する。続いて、格下ノード接続情報データフレームから、格下ノード３３の格下ノードレコードを読み出し、読み出した格下ノードレコード中の上り距離と下り距離の比率から、当該単位道路区間４２中の総行程に対する上り距離の割合αを特定する。さらに続いて、単位道路区間４２の上り方向のコストに、当該割合αを乗算した結果のコストを、格下ノード３３から直近の上り側の格上ノード３５までの道路区間のコストとして採用する。
【００８２】
また同様に、格下ノード３３から下り側の直近の格上ノード３１までの付加道路区間のコストは、まず、当該格下ノード３３の直近の両端の格上ノード３１、３５の間の単位道路区間４２の下り方向のコストを、上述の通りリンクレコードおよびリンクコストテーブルを用いて決定する。続いて、格下ノード接続情報データフレームから、格下ノード３３の格下ノードレコードを読み出し、読み出した格下ノードレコード中の上り距離と下り距離の比率から、当該単位道路区間４２中の総行程に対する下り距離の割合βを特定する。さらに続いて、単位道路区間４２の下り方向のコストに、当該割合βを乗算した結果のコストを、格下ノード３３から直近の下り側の格上ノード３１までの道路区間のコストとして採用する。
【００８３】
このように、制御回路１７は、格下ノードレコード中の上り距離と下り距離を用いて、付加道路区間のコストを算出している。したがって、格下ノードレコード中の上り距離と下り距離は、付加道路区間のコストを特定するための情報（すなわち、付加道路区間コスト特定情報）である。したがって、格下ノード接続情報データフレームにおいては、複数の格下ノード３２〜３４のそれぞれから直近の格上ノードまでの付加道路区間７１〜７６の情報として、それら複数の付加道路区間７１〜７６のそれぞれを通過した場合のコストを特定するための情報が含まれていることになる。
【００８４】
このように、制御回路１７は、誘導経路算出処理において、リンクレコードとして記録されている単位道路区間および格下ノードから直近の格上ノードまでの付加道路区間を採用して探索範囲を広げていく。
【００８５】
例えば、図２に示すように、ノード５０が出発地点で、ノード５１が目的地であったとする。この場合、出発地点５０から探索を開始すると、格上ノード３１まで探索範囲が広がる。そして、図４に示すように、格上ノード３１から格上ノード３５までの経路は、複数のリンクから成るものの、１つの単位道路区間４２なので、単一のリンクレコード（すなわち、単位道路区間４２に対応する道路区間）のコストテーブル番号を参照するだけで、当該経路のコストを算出することができる。すなわち、格上ノード３１から格上ノード３５までの経路のコストについては、リンク毎にコストを参照してそれらを総和するといった煩雑な処理をして算出する必要がない。
【００８６】
このようになっているので、主要道路２０におけるコスト計算が簡素化され、その結果、誘導経路算出処理に要する処理負荷が低下し、ひいては、誘導経路算出処理に要する時間が短くなる。
【００８７】
また、制御回路１７は、格下ノードから直近の格上ノードまでの道路区間については、格下ノードから格上ノードの方向への探索にのみ用い、格上ノードから格下ノードの方向への探索には用いないようになっていてもよい。
【００８８】
このようにすると、出発地点５０から探索範囲が格上ノード３１まで広がったときに、格上ノード３１から格下ノード３２、３３、３４には探索範囲が広がらず、格上ノード３１から格上ノード３５までは探索範囲が広がる。したがって、探索範囲が一旦主要道路２０に乗ると、次の格上ノードまでは探索範囲が主要道路２０から他の道路に広がらない。したがって、このようにしない場合に比べ、探索範囲が限定されるので、誘導経路算出処理に要する処理負荷が低下し、ひいては、誘導経路算出処理に要する時間が短くなる。
【００８９】
ここで、本実施形態の道路ネットワークデータを用いた誘導経路算出処理と、従来の階層構造の道路ネットワークデータを用いた誘導経路算出処理とを比較する。従来の階層構造の道路ネットワークデータを用いた誘導経路算処理を行う場合は、図６に示すように、出発地点５２を含むリージョン６０内に探索範囲を絞って下位層の各ノードへの最小コストとなる経路を算出し、それら下位層の各ノードのうち、上位層にも含まれるノード３１から、主要道路２０上の目的地３６まで、上位層のデータを用いて探索を行う。
【００９０】
その結果、例えば、経路６１、６２、６３のような誘導経路が算出される。このように、下位層における出発地点５２の近傍の探索範囲は、リージョン６０内に限定されるので、出発地点５２から下位層にしか属さない非主要道路のみを用いては、リージョン６０を出ることができない。それ故、仮に経路６４、６３の方がコストが低いとしても、制御回路１７は、経路６１、６２、６３を誘導経路に選出してしまう。
【００９１】
一方、本実施形態においては、探索範囲がリージョン６０に限定されないので、経路６４、６３も探索範囲に含まれる。その結果、経路６４、６３のコストが最も低ければ、経路６４、６３が誘導経路に選出される。
【００９２】
また、本実施形態の制御回路１７も、従来と同様に、出発地点５２を含む所定の第１のリージョン内に探索範囲を限定し、その探索範囲内で主要道２０上のノードまでの経路を探索し、その後は、目的地地点を含む所定の第２のリージョンまでは、主要道２０内に探索範囲を限定して探索を行うことで、第２のリージョン内かつ主要道２０上の格下ノードまでの経路を算出し、その後は、当該格下ノードから第２のリージョン内に探索範囲を限定して探索を行うことで、目的地点までの経路を算出するようになっていてもよい。
【００９３】
しかし、その場合であっても、本実施形態の道路ネットワークデータは、従来の階層構造の道路ネットワークデータよりもデータ量が少ないので、第１のリージョンおよび第２のリージョンの大きさを、従来よりも大きくすることができる。
【００９４】
上記のように構成された道路ネットワークデータを用いて上述のように誘導経路の算出を行うことで、データの階層やデータの境界を考慮することなく経路計算を行うことができる。
【００９５】
なお、本実施形態においては、制御回路１７が、誘導経路算出処理を実行することで、誘導経路算出手段の一例として機能する。
【００９６】
（他の実施形態）
以上、本発明の実施形態について説明したが、本発明の範囲は、上記実施形態のみに限定されるものではなく、本発明の各発明特定事項の機能を実現し得る種々の形態を包含するものである。
【００９７】
例えば、上記実施形態においては、リンク情報データフレーム中の単位道路区間コスト特定情報は、リンクコストテーブルのノード番号を示す情報である。しかし、必ずしもこのようになっておらずともよく、例えば、単位道路区間コスト特定情報は、対応する単位道路区間のコスト値そのものであってもよい。その場合は、リンクコストテーブルは不要となる。
【００９８】
また、上記実施形態においては、付加道路区間のコストを特定するための情報（すなわち、付加道路区間コスト特定情報）は、格下ノードレコード中の上り距離と下り距離の情報であった。しかし、必ずしもこのようになっておらずともよく、例えば、付加道路区間コスト特定情報は、対応する付加道路区間のコスト値そのものであってもよい。
【００９９】
また、道路形状データは、道路ネットワークデータに含まれていてもよい。
【０１００】
また、上記の実施形態において、制御回路１７がプログラムを実行することで実現している各機能は、それらの機能を有するハードウェア（例えば回路構成をプログラムすることが可能なＦＰＧＡ）を用いて実現するようになっていてもよい。
【０１０１】
また、本発明のナビゲーション装置は、必ずしも車載用のものでなくともよい。例えば、ナビゲーション装置は、ユーザが携帯するタイプのものであってもよい。
【符号の説明】
【０１０２】
１                                車両用ナビゲーション装置
１１                              位置検出器
１２                              画像表示装置
１３                              操作部
１４                              スピーカ
１６                              地図データ取得部
１７                              制御回路
２０、２１、２５                  主要道路
２２〜２４、２６                  非主要道路
３０、３１、３５、３６            格上ノード
３２〜３４                        格下ノード
４１〜４３                        単位区間
５０、５２                        出発地点
５１                              目的地点
６０                              リージョン
７１〜７６                        付加道路区間
【図１】
2010243306.tif 000003
【図２】
2010243306.tif 000004
【図３】
2010243306.tif 000005
【図４】
2010243306.tif 000006
【図５】
2010243306.tif 000007
【図６】
2010243306.tif 000008