米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 測定; 光学 -> アルパイン株式会社

発明の名称 経路探索装置
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2001−74482(P2001−74482A)
公開日 平成13年3月23日(2001.3.23)
出願番号 特願平11−251178
出願日 平成11年9月6日(1999.9.6)
代理人 【識別番号】100111947
【弁理士】
【氏名又は名称】木村 良雄
【テーマコード(参考)】
2C032
2F029
5H180
【Fターム(参考)】
2C032 HB05 HD16 
2F029 AA02 AB01 AB07 AB09 AC01 AC02 AC04
5H180 AA01 BB13 FF04 FF05 FF14 FF22 FF27 FF32
発明者 遠藤 康弘
要約 目的


構成
特許請求の範囲
【請求項1】 地図領域を任意の矩形に分割した各矩形分割領域毎に、矩形分割領域内経路データと、各矩形分割領域に近接した高速道路のインターチェンジ迄、及び主要一般道路の交差点迄の主要道路アクセス用経路データとを備えるとともに、全矩形分割領域共通に高速道路のインターチェンジ相互間、及び主要一般道路交差点相互間の主要道路経路データを備え、現在地が含まれる矩形分割領域、及び目的地が含まれる矩形分割領域の前記各データと、前記主要道路経路データとに基づいて現在地と目的地間の経路を探索することを特徴とする経路探索装置。
【請求項2】 高速道路優先の探索指示入力時に、前記矩形分割領域内道路データと、各矩形分割領域に近接した高速道路のインターチェンジ迄の主要道路アクセス用経路データと、全矩形分割領域共通の高速道路のインターチェンジ相互間の主要道路経路データに基づいて現在地と目的地間の経路を探索する請求項1記載の経路探索装置。
【請求項3】 一般道路優先の探索指示入力時に、前記矩形分割領域内道路データと、各矩形分割領域に近接した主要一般道路の交差点までの主要道路アクセス用経路データと、全矩形分割領域共通の主要一般道路の交差点相互間の主要道路経路データに基づいて現在地と目的地間の経路を探索する請求項1記載の経路探索装置。
【請求項4】 前記主要道路アクセス用経路データを高速道路、及び主要一般道路毎に複数備えている請求項1記載の経路探索装置。
【請求項5】 各矩形分割領域には交差点を1つだけ含むように矩形分割領域を設定している請求項1記載の経路探索装置。
発明の詳細な説明
【0001】
【発明の属する技術分野】本発明は、自動車等に用いるナビゲーション装置において、目的地までの最適経路を探索し、現在位置を示す地図上に探索経路を表示するための経路探索装置に関する【0002】
【従来の技術】ナビゲーション装置においては、DVD−ROM、CD−ROM等の地図データ記憶媒体を駆動する駆動装置と、ディスプレイ装置と、GPS、ジャイロ、及び車速センサ等の車両の現在位置及び現在の進行方位を検出する車両移動検出装置等を有し、車両の現在位置を含む地図データに基づいて車両位置の周囲の地図画像をディスプレイ装置上に描画すると共に、車両位置マークをディスプレイ画面に重ね合わせて表示し、車両の移動に応じて地図画像をスクロール表示し、また、地図画像を画面に固定し車両位置マークを移動させる等により、車両が現在どこを走行しているのかを一目でわかるようにしている。
【0003】また、通常、車載用ナビゲーション装置には、運転者が所望の目的地に向けて道路を間違うことなく容易に走行できるようにした経路誘導機能を備えている。この経路誘導機能によれば、地図データを用いて出発地から目的地までを結ぶ最もコストが低い経路を自動探索し、その探索した経路を誘導経路データとして記憶しておき、走行中、地図画像上に誘導経路を他の道路とは色を変えて太く描画して画面表示し、車両が誘導経路上の進路を変更すべき交差点に一定距離内に近づいたときに、地図画像上の進路を変更すべき交差点に進路を示す矢印を描画し、また交差点拡大図を画面表示したりすることで、目的地に向けた最適な経路を運転者が確実に、且つ容易に把握できるようにし、また、音声等によって各種走行をガイドし、運転者が安全に経路誘導による走行を行うことができるようにしている。
【0004】上記のような経路誘導を行うため、DVD−ROM等の記録媒体には図9に示すような地図データが記録されている。即ち、この地図データにはディスクラベル1,描画パラメータ2,図葉管理情報3,図葉(地図データ)4、索引データ5、経路データ6等を有している。図葉4には後述するように文字データ、背景データ、道路データなどが格納されており、例えば日本全国の地形図を緯度、経度で分割した単位地図毎のデータが記憶されている。この図葉には、広範囲の地域を荒く示す図葉と、狭い範囲の地域を詳細に示す図葉とがあり、この図葉は同一の地域を示した地図表示レベルA、B、Cを有している。この地図表示レベルA、B、Cはこの順に詳細に示されている。また、地図表示レベルA、B、Cは地図表示レベル管理情報7と、各地図表示レベルの地域を4個、9個等に分割した、各分割地域を示す複数ユニット8からなる。この各ユニットはユニットヘッダ10、文字レイヤ11、背景レイヤ12、道路レイヤ13、オプションレイヤ14等を有している。
【0005】道路レイヤ13は図10に示すように、ノードデータNDDT20、道路リンクデータRLDT21、交差点データCRDT22で構成されており、このうち道路リンクデータRLDT21は、当該道路リンクの属性情報を与えるもので、リンクを構成する全ノード数、リンクを構成する各ノードのノードデータNDDT20上の番号、道路名、国道、県道等の道路の種別、道路の幅員等のデータにより構成されている。また、交差点データCRDT22は地図上の交差点毎に、該交差点に連結するリンク上の該交差点に最も近いノード(各交差点ノードという)のノードデータNDDT20上の番号の集合である。また、ノードデータNDDT20は地図上の全ノードリストであり、ノード毎に座標情報(経度、緯度)、該ノードが交差点であるか否かの交差点識別フラグ、交差点であれば交差点を指し、交差点でなければ該ノードが属する道路リンクを指すポインタ等で構成されている。
【0006】一方、図9に示す経路探索データ6は、例えば図11に示すように、狭い地域を対象とした階層0から広い階層m迄、各階層毎に探索データが記録されている。各階層の探索データは、ノード接続データ16、リンク毎の想定通過時間等を示すリンクコストデータ17、経路表示データ18から構成されている。上記ノード接続データ16は図12に示すように、各ノードa〜g、P、Qがどのノードと接続されているかを示すデータである。また、リンクコストデータ17は、図12中に示すように、各ノード間のリンクのリンクコストを示すものであり、例えば、ノードaとノードbとの間のリンクのリンクコストは10であり、ノードaとノードPとの間のリンクコストは13であることを示している。また上記リンクコストは、[ リンクコスト=リンク距離×道路幅係数×道路種別係数×階層係数 ]
から求められ、ここで、道路幅係数とは、道路幅の大きさに対して設定される係数であり、道路種別係数とは、有料道路等の道路種別に応じて設定される係数である。また、出発地から各ノードまでの経路コストは、その間の個々の経路コストの和として求められる。経路表示データ18は、経路探索により選択された経路を画像表示装置の地図上に表示するためのデータである。
【0007】従来のナビゲーション装置において、上記のようなDVD−ROM等の記録媒体に記録されたデータに基づいて経路探索を行う際の基本的な考え方は、図12に示すように、現在位置ノードPから目的地ノードQに至る全ての経路のリンクコストを加算し、最もリンクコストが低い経路を選択するものであり、同図の場合は図中太線で示すように、P−b−e−d−f−g−Qのリンクコストの合計が30で最も小さくなるため、この経路が誘導経路として選択される。
【0008】実際の誘導経路探索においては、まず出発地、目的地の位置から最も近い出発ノード及び目的ノードを選択する。図12に示す例においては、ノードPが出発ノードに、またノードQが目的ノードに選択されたことを示している。次に、出発ノードPを含む経路探索データを読込み、出発地側の経路探索を行う。この経路探索は、前述の通り、リンクコストの合計が最も低くなる経路を選択するものである。次に経路探索の結果、目的ノードに接続したか否かが判定される。出発地から目的地までの距離が比較的近く、例えば図11に示す階層0の最も詳細な階層の中に目的ノードも存在する場合は、この階層のデータのみで目的ノードへの誘導経路が選択される。
【0009】それに対して、出発地から目的地が遠い場合には、目的ノードに接続したと判定されないため、目的ノードQを含む経路探索データが記録媒体から読出され、目的地側の経路探索を行う。この目的地側の経路探索により選択された経路が、出発地側の探索経路に接続されない場合には、探索階層のランク上げる。以降、探索階層のランクを上げて出発ノードと目的ノードとの最適経路を探索する方法には種々のものが提案されているが、例えば図13に示すような手段がある。即ち、市町村道レベルまで表示されている階層0において、出発ノードPが含まれる経路探索データAを調べて、目的ノードQが存在しないときには、県道レベルまで表示する階層1の経路探索データLを読出し、ここに目的ノードQが存在するか否かを調べ、もしも存在するときはそこで最適経路を計算する。図示の例のようにそこに存在しない場合は、その経路探索データLにおける目的ノード側への候補ノードをリンクコスト順にリストアップする。なお、階層1の経路探索データのノードは階層0の経路探索データの一部のみが抽出されており、その結果、図13の例において、階層0において太線のリンクで示される道路のみが階層1に存在し、同様に階層1において太線のリンクで示される道路のみが階層2に存在し、上位階層ではその範囲のノード及びリンクデータの中で経路探索が行われる。
【0010】同様に目的ノードQが存在する階層0の経路探索データB側でも階層レベル1の経路探索データMを読出し、ここに出発ノードPが存在するか否かを調べ、図示の例のように出発ノードが存在しない場合にはその経路探索データMにおける目的ノード側への候補ノードをリンクコスト順にリストアップする。この操作を繰り返すことによって、如何に多数の階層が存在しても、或いは出発ノードと目的ノードが遠く離れていても、いつかは両者の候補ノードを含む階層のデータが存在するので、最終的に出発ノードと目的ノード間の最もリンクコストの低い最適経路が設定される。図13の例においては階層2の経路探索データSにおいて両ノードが結びつき、前記下位の階層における探索経路を加味して国道を利用した両者間の最適経路が探索される。なお、経路の探索に際して、利用者から高速道路優先探索の指示が行われていたときには、階層3における高速道路網の経路探索データHが用いられ、階層0における経路探索の段階から、最も近いインターチェンジへの経路探索が行われる。その際も、最も近いインターチェンジを探すために、上記のような階層を順に切換える探索が行われる。
【0011】
【発明が解決しようとする課題】階層0における1つの経路探索データ中に出発ノードと目的ノードが存在しない場合の上記経路探索方法においては、1つずつ階層を上げて両者が結びつくまでその操作を繰り返すものであるが、経路探索データは階層を1つ上げる毎に下位のノードの一部が消えるため、正確な経路探索を行うためにはできる限り詳細なデータを備えた階層0における経路探索データを広範囲に読出し、その中で両者の最適経路を探索することが好ましい。しかしながら、このような経路探索方法は精度が良くなる反面、経路探索データが大になるのでリンクコストの計算処理に多くの時間がかかるという問題がある。
【0012】その対策として、例えば前記図13に示す例において、階層0での最小の範囲の経路探索データによる経路探索処理に続いて直ちに階層2に上げ、ここで経路探索を行うことも提案されている。しかしながらこのような手法を用いると、探索経路が荒くならざるを得ず、また、階層0におけるノードの多くのものが階層2に存在しなくなるため、両階層間のノードの連結が適切に行われなくなることもある。
【0013】上記のように、階層の異なる経路探索データを適宜階層を切換えて経路探索を行う際には、適切なタイミングで階層を切換えて使用する必要があるが、早い段階でデータ密度の少ない上位の階層のネットワークを用いると探索経路の精度を落とし、また、データ密度の大きい下位の階層のネットワークでの経路探索を広く行うと、多くの時間がかかることとなる。また、出発ノード、目的ノード周辺の探索開始リンクを作成するにも、下位の階層での経路探索を広く行うと多くの候補ノードが生じ、以降の経路探索に多くの時間がかかってしまい、逆に早い段階で階層の上のネットワークを用いると、探索経路の精度を落とすこととなる。
【0014】したがって、本発明は、経路探索の精度を落とすことなく、且つ高速で経路を探索することができる新規な経路探索データ構造を備えた経路探索装置を提供することを主たる目的としている。
【0015】
【課題を解決するための手段】本発明は、上記課題を解決するため、地図領域を任意の矩形に分割した各矩形分割領域毎に、矩形分割領域内経路データと、各矩形分割領域に近接した高速道路のインターチェンジ迄、及び主要一般道路の交差点迄の主要道路アクセス用経路データとを備えるとともに、全矩形分割領域共通に高速道路のインターチェンジ相互間、及び主要一般道路交差点相互間の主要道路経路データを備え、現在地が含まれる矩形分割領域、及び目的地が含まれる矩形分割領域の前記各データと、前記主要道路経路データとに基づいて現在地と目的地間の経路を探索することを特徴とする経路探索装置としたものである。
【0016】請求項2に係る発明は、高速道路優先の探索指示入力時に、前記矩形分割領域内道路データと、各矩形分割領域に近接した高速道路のインターチェンジ迄の主要道路アクセス用経路データと、全矩形分割領域共通の高速道路のインターチェンジ相互間の主要道路経路データに基づいて現在地と目的地間の経路を探索する請求項1記載の経路探索装置としたものである。
【0017】請求項3に係る発明は、一般道路優先の探索指示入力時に、前記矩形分割領域内道路データと、各矩形分割領域に近接した主要一般道路の交差点までの主要道路アクセス用経路データと、全矩形分割領域共通の主要一般道路の交差点相互間の主要道路経路データに基づいて現在地と目的地間の経路を探索する請求項1記載の経路探索装置としたものである。
【0018】請求項4に係る発明は、前記主要道路アクセス用経路データを高速道路、及び主要一般道路毎に複数備えている請求項1記載の経路探索装置としたものである。
【0019】請求項5に係る発明は、各矩形分割領域には交差点を1つだけ含むように矩形分割領域を設定している請求項1記載の経路探索装置としたものである。
【0020】
【発明の実施の形態】本発明の実施の形態を図面に沿って説明する。図1(a)は本発明による経路探索装置で用いられる経路探索データにおける基本的な考え方である地図領域を矩形分割領域に分けた例を示しており、図1(b)は図1(a)における現在位置Pを含む矩形分割領域の拡大図を示している。本発明に用いる地図データは、前記図9に示す従来のものと同様であるが、経路探索データ6のデータ構造を異にしている。即ち、前記図9に示す従来のものにおいては、この経路探索データを前記図11に示すような階層0〜階層mの多層階層となし、各階層毎にノード接続データ16、リンクコストデータ17、経路表示データ18等の各種データを持つ構造としていたのに対して、本発明においては前記従来例における最も詳細な最下層レベルのデータのみを備え、例えば日本国内の詳細地図全体に対して、その内部を任意の矩形に分割した矩形分割領域で細分化している。但し、経路の情報として、ノードと、各ノードを結ぶリンクによってデータを構成している点は同様である。
【0021】この矩形分割領域の設定に際しては、原則として1つの矩形分割領域には交差点ノードは1つだけ入るように設定し、交差点の無い矩形分割領域は少なくとも道路が1つ存在するように分割することが好ましい。但し、その際に、各矩形分割領域にはあまり多くのノード、及び各ノードを結ぶリンクが存在することは好ましくなく、ノード数が多くなりそうなときにはそれを細分化した矩形分割領域を設定する。
【0022】図示実施例において、図1(a)の中央部分に示される矩形分割領域K32515(全国の詳細地図データを元にして適宜の大きさ、形状に分割した矩形分割領域に対して付した連続番号の一例を意味する)は図1(b)に拡大図で示しており、この図から明らかなように、この矩形分割領域K32515は、T字路型の交差点である交差点ノードN32515-1(矩形分割領域K32515内のノード番号No.1を示している)を中心に、任意の大きさに設定した矩形分割領域である。この矩形分割領域内には他の交差点ノード等が存在せず、矩形分割領域K32515には前記交差点ノードN32515-1の他、隣接する矩形分割領域へ至る道路としてのリンクL32515-1(矩形分割領域K32515内のリンク番号No.1を示している)が接続する接続ノードN32525-2、同様にリンクL32515-2が接続する接続ノードN32515-3、リンクL32515-3が接続する接続ノードN32515-4が存在する。なお、図示実施例において、リンクL32515-1及びL32515-2は市道の一部として示されている。
【0023】上記実施例において、この矩形分割領域K32515内には前記のように現在位置Pが存在し、この現在位置Pから後述する目的地Qに対する経路探索を行うとき、この矩形分割領域K32515から他の矩形分割領域に向かうリンクは3個存在し、各リンクに対応する前記接続ノードから、各々目的地Qへの経路探索のためのリンクコストの計算が行われることとなる。したがって、各接続ノードは、この矩形分割領域内の地点から他の矩形分割領域への経路探索を行う際の「探索開始ノード」となる。
【0024】上記のような矩形分割領域K32515と同様に、例えば上記市道が県道C361(全国の県道に対して連番を付したNo.361の県道を意味する)と交差する交差点ノードC361-65(県道C361を構成するノードに対して連番を付したノード番号で、No.65のノードを意味する)を中心とする任意の矩形により矩形分割領域K32519を形成している。同様に上記県道C361が高速道路A4(全国の高速道路に対して連番を付したNo.4の高速道路を意味する)と交差し、インターチェンジ(IC)となっている交差点ノードA4-26(高速道路A4のインターチェンジに対して連番を付したNo.26のインタチェンジを意味する)を中心とする任意の矩形により矩形分割領域K32513を形成している。また、前記現在地Pが存在する矩形分割領域K32515の接続ノードN32515-4から先に延びる道路が国道B6(全国の国道に対して連番を付したNo.6の国道を意味する)と交差する交差点ノードB6-126(国道B6を構成するノードに対して連番を付したNo.126のノードを意味する)は、矩形分割領域K32512となっている。このように、各交差点を中心に任意の矩形分割領域が形成され、これらの矩形分割領域を連結するように、例えば矩形分割領域K32510、K32511、K32514、K32516、K32517、K32518、K32520、等を形成している。
【0025】このようにして、全国にわたって全て任意の矩形分割領域で分割し、各々の矩形分割領域を基本的なデータブロックとする。各矩形分割領域毎に、経路探索用の基本データとして、例えば図2に示すような矩形分割領域内経路データを備えている。図2(a)は矩形を形成している矩形分割領域ユニットの経路データの全体構成を示す図であり、各矩形のヘッダとしてのユニットヘッダ(図示の例では上記矩形分割領域のK32515)、矩形に含まれるノードを列記し、後述する接続ノードテーブルの格納位置も示すノードテーブル(NT32515)と、全ノードの詳細データを記録した接続ノードテーブル(CNT32515)と、隣接する2つのノードによって特定される上記リンクの詳細データを納めたリンクテーブル(LT32515)と、これら矩形分割領域内の経路データに加えて、この矩形分割領域から主要な道路にアクセスするための経路データを記録した主要近接ノードリスト(KNL32515)が含まれている。
【0026】上記ノードテーブル(NT32515)は図2(b)に示すように、この矩形分割領域内の全ノードであるN32515-1、N32515-2、N32515-3、N32515-4のノードレコードを格納し、また、各ノードに対応する接続ノードテーブルの格納位置のデータも備えている。また、接続ノードテーブル(CNT32515)は図2(c)に示すように、各ノード毎に、a.そのノードの正規化経度・緯度、b.このノードが交差点ノードであるか否かを示す交差点ノードフラグ、他の矩形分割領域との境界にあるノードであるかを示す接続ノードフラグ等からなるノードの属性フラグ、c.このノードをリンクの一方端とするリンクがある場合に各リンクの他方端を構成するノードの数を示す接続しているノードの数、d.このノードに接続されているリンクに右折禁止やUターン禁止等の交通規制が存在する場合にはその交通規制の数、e.このノードが一方端となっている各リンクのリンク番号を示すリンク本数分の接続ノードレコード、f.上述した交通規制が存在する場合にはその数に対応した交通規制の具体的な内容を示す交通規制レコード、g.このノードが他の矩形分割領域との境界にあるノードである場合には、隣接する矩形分割領域の対応する接続ノードテーブルの位置を示す接続ノードレコード、h.このノードが交差点ノードである場合には、交差点ユニットにおける対応する交差点レコードの格納位置及びサイズ、等が含まれる。
【0027】また、リンクテーブル(LT32515)は図2(d)に示すように、着目している矩形分割領域に含まれる全てのリンクに対応したリンク番号順の複数のリンクレコードを含んでいる。これらの各リンクレコードは図2(e)に示すように、a.主に探索経路表示用に各リンクに付されたコードであるリンクNo.、b.リンクの両端に位置する2つのノードを特定するノード番号1及びノード番号2,c.リンクの距離、d.このリンクを走行する場合の実際の所要時間を、各リンクの順方向、逆方向の両方について求めたリンクコスト、e.このリンクに対応した実際の道路が高速道路、国道、県道、市町村道であるか等の道路種別を示す道路種別データ、f.このリンクに対応した道路に付された路線番号、等が含まれる。
【0028】図2(a)に示した矩形分割領域ユニットのデータにおける主要近接ノードリスト(KNL32515)の詳細は、図3に示すように、各矩形ユニット内の地点から、高速道路や国道等の主要な道路のインターチェンジや交差点に入る際、最も近いインターチェンジや交差点のデータを記録している。図示実施例における矩形分割領域(K32515)においては、図1と対応して記載しているとおり、高速道路(A4)の25番インターチェンジ(A4-25)が最もリンクコストが小さく、次いで同高速道路の26番のインターチェンジ(A4-26)であることを示している。更に、この矩形分割領域から前記各インターチェンジ(近接ノード)に至るまでのリンクコストを記録しており、例えば目的地がこの高速道路のいずれの方向にあるかによって全体のリンクコストが相違する可能性があるとき等に際しては、このリンクコストを加味して最適のインターチェンジが選択され、誘導経路が設定される。また、予め各経路に対するリンクコストが計算されているので、後述する経路探索時にこのデータをそのまま利用することができ、改めてリンクコストの計算を行う必要がなくなる。
【0029】また、上記近接ノードまで至る通過ノード列を記録しており、この通過ノード列は経路探索終了後に誘導経路を表示画面の地図上に重ねて表示し、更に車両走行中における誘導経路の案内のために使用される。図示の例においては、矩形分割領域(K32515)から最も近い高速道路のインターチェンジ(IC;A4-25)には、図1から明らかなように、矩形分割領域(K32515)の接続ノードである探索開始ノード(N32515-2)から、隣接している矩形分割領域(K32511)において前記探索開始ノードに対応している接続ノード(N32511-2)を通り、更にその途中において県道(C350)との交差点であるノード(C350-25)を経由し、最終的に高速道路(A4)のインターチェンジ(A4-25)に至る通過ノード列を記録している。同様に、次にリンクコストの少ないインターチェンジ(IC;A4-26)には、N32515-3、N32518-1を通り、途中において県道(C361)との交差点であるノード(C361-65)を経由し、最終的にインターチェンジ(A4-26)に至る通過ノード列を記録している。
【0030】上記矩形ユニットの主要近接ノードリストには、主要道路へ至るデータとして、前記のような高速道路のインターチェンジへの経路データの他、国道へ至るデータも記録している。図示の例においては、矩形分割領域(K32515)から国道へ至る最もリンクコストの小さいルートは国道(B6)の交差点(B6-126)へのルートであり、そこへのコスト、及び、その交差点への通過ノード列を前記と同様に記録している。更に、次にリンクコストの小さなルートとして、国道(B6)の交差点(B6−125)へのルートに関するデータを記録し、更にその次にリンクコストの小さなルーとして、国道(B6)の交差点(B6−127)へのルートに関するデータを記録している。図3に示す例においては、それらに加えて主要一般道路としての県道に至る最もリンクコストの小さなルート及び次にリンクコストの小さなルートを前記と同様に記録している。なお、この県道へのルートは必要に応じて省略することができ、或いは更に主要な市道等が存在する場合には、ノードリストのその他の部分に、その市道等への経路データを記録することもできる。
【0031】このように、1つの矩形分割領域に対して主要道路アクセス用経路データを1つ備えているので、例えば各矩形分割領域における接続ノード毎に主要道路アクセス用経路データを記録する必要がなく、記録するデータ量を大幅に少なくすることができる。また、前記のように各矩形分割領域を充分に小さく設定することにより、各接続ノード毎に主要道路アクセス用経路データを持つものと比較してその探索精度が落ちることが無くなる。なお、データ記録媒体の記憶容量に十分余裕がある場合には、各接続ノード毎に図3に示すものと同様の、主要の道路へのルートのデータを作成し記録しても良い。
【0032】本発明による経路探索装置のデータ構成は、図4にその概要を示すように、前記の矩形分割領域毎の経路データにおいては、矩形分割領域内の経路データと主要道路アクセス用経路データとを備え、主要道路アクセス用経路データとしては前記のように近接するインターチェンジまでの経路データと、近接する主要一般道路の交差点までの経路データとを備えている。また、後述するように、全矩形分割領域に対して共通の経路データを備え、その中には高速道路インターチェンジ相互間の経路データと、主要一般道路の交差点相互間の経路データとを備えている。
【0033】上記全矩形分割領域に対して共通の経路データとしては、図5に示すようなマトリクス状のリンクコスト集計リストを備えている。このリンクコスト集計リストにおいて、例えば高速道路についてみると図5(a)に示すように、全国の高速道路について全て連続番号A1〜Amを付し、図示実施例においては東名高速道路をA1、東北自動車道をA2、中央自動車道をA3、常磐自動車道をA4とし、以降九州自動車道のAmまで連続番号を付している。また、各高速道路について、順にインターチェンジに番号を付しており、図中1,2,3,・・・nとして示している。このような全国の高速道路について、各インターチェンジ間の最小リンクコストのデータを予め計算し記録しておく。図5のマトリクス上において破線のハッチング部分は、ハッチングを付していない部分とデータが重複するのでデータ入力の不要の部分として示している。
【0034】図5のマトリックスにおいて、各列と行とが交差する矩形部分には、各列のインターチェンジから各行のインターチェンジに至る最小のリンクコストとなるデータが記録されている。例えば図6(a)に示すように、東名高速道路の第1インターチェンジであるA1−1から高速道路に入った場合、各高速道路のインターチェンジで降りる際のリンクコスト、また、その際の主要な通過ノードの列を前記図3と同様のデータ形式で記録している。なお、この主要通過ノード列は図3のデータと同様に誘導経路に沿った案内のために使用される。各インターチェンジ相互間について同様のリストが記録されるが、例えば図6(b)に示すように、中央高速道路の第2インターチェンジであるA3−2からのデータは、前記図4のマトリックスの破線のハッチングで示す部分のデータは不要であるので、中央高速道路の第3インターチェンジ以降のデータのみが記録される。したがって、例えば中央高速道路(A3)の第2インターチェンジ(A3−2)から東北自動車道(A2)の第3インターチェンジ(A2−3)間のデータは、東北自動車道の第3インターチェンジ(A2−3)のデータとして記録されている部分から読出される。なお、この高速道路に関するデータにおいて、主要通過ノード列として記録されているノードは必ずしも全て高速道路網のノードとは限らず、高速道路のみで進んだときには極めて遠回りとなるときには、途中で一般道路に降りて再度高速道路に入る等の、通常の経路探索によるデータと同様のデータが記録されている。
【0035】更に、全国の国道についても、各国道の交差点毎に、上記高速道路のインターチェンジと同様のデータを記録している。すなわち、図5(b)に一部を示すように前記図5(a)と同様のマトリックス型のデータ構造をなし、国道1号をB1として、順にB2,B3,B4・・・Bmの国道を配置し、各国道毎に交差点を順に1,2,3・・・nと配置している。このマトリックスにおいても、図中破線のハッチングで示す部分のデータは不要となる。また、ここにおいても、各列と行とが交差する矩形部分には、各列の交差点から各行の交差点に至る最小のリンクコストとなるデータが記録されており、そのデータの構成は前記図6に示す高速道路のインターチェンジ毎のデータと同様であるので、ここでの説明は省略する。
【0036】全国の国道について交差点毎に上記のようなデータを作成するには多くのデータ処理を必要とするが、従来のナビゲーション装置用の経路探索データを用い、上記マトリックスに沿って自動的に順番に経路探索を行うようプログラムを組み、探索された経路を自動的にメモリすることにより、格別の人手をかけることなく、上記一連のデータを得ることができ、このデータをそのまま本発明の経路探索用データとして使用することができる。このように容易に上記データを得ることができるので、県道についても同様のデータを得て記録し、これを使用することもできる。
【0037】本発明の経路探索装置においては、上記のようなデータ構成としているので、その経路探索に際しては、図7に示すような作動フローにしたがって探索が行われる。即ち、経路探索を開始し(S1)、現在地が例えば図8に示すように高速道路A4と国道B6に挟まれたP地点であり、この現在地データがナビゲーション装置に入力されると(S2)、この地点が含まれる矩形分割領域のデータである図2及び図3の経路探索データがDVDから読出される(S3)。この矩形分割領域が、例えば図1に示す矩形分割領域(K32515)であるとき、現在地Pからこの矩形分割領域の探索開始ノード(N32515-2,N32515-3,N32515-4)へのリンクコストが計算されメモリされる(S4)。
【0038】一方、目的地が図8に示す高速道路A3と国道B3に近いQ点であるとき、このデータがナビゲーション装置に入力されると(S5)、前記現在地のデータ読出しと同様にこの目的地の地点が含まれる矩形分割領域のデータが読出される(S6)。この矩形分割領域は前記現在地の矩形分割領域と同様のデータ構成となっており、前記現在地における作動と同様に、目的地Qからこの矩形分割領域の探索開始ノードへのリンクコストが計算されメモリされる(S7)。
【0039】次いで、この経路探索において高速道路優先の指示がなされているか否かを判別する(S8)。ここで高速道路優先の指示がなされているときには、現在地の存在する矩形分割領域における図3に示す主要近接ノードリストから、高速道路のインターチェンジに近いルートを記録しているデータを読出す。図3に示す実施例においては、インターチェンジA4−25とA4−26へのリンクコストと通過ノード列が読出される。同様に目的地の存在する矩形分割領域についても近接しているインターチェンジへのリンクコストと通過ノード列が読出される(S9)。
【0040】次に、前記現在地及び目的地の矩形分割領域に近接しているインターチェンジの候補について、各インターチェンジ間の最小リンクコストを、図6に示されるような予め計算されているデータを読出すことにより求める(S10)。上記のように計算され、読出されたリンクコストを合計し、最もリンクコストの小さいルートを誘導経路として設定する(S11)。
【0041】一方、前記高速道路優先の経路探索か否かの判別において(S8)、高速道路優先の経路探索の指示がなされていないときには、現在地の存在する矩形分割領域における図3に示す主要近接ノードリストから、国道の交差点に近いルートを記録しているデータを読出す。図3に示す実施例においては、交差点B6−126,B6−125、B6−127へのリンクコストと通過ノード列が読出される。同様に目的地が存在する矩形分割領域に近接している国道の交差点へのリンクコストと通過ノード列が読出される(S12)。次に前記現在地及び目的地の矩形分割領域に近接している国道の交差点の候補について、各交差点間の最小リンクコストを、図6と類似のデータ構成からなるリストのデータを読出すことにより求める(S13)。以下は前記高速道路優先の場合と同様にリンクコストを合計し、最もリンクコストの小さいルートを誘導経路として設定する(S14)。
【0042】なお、上記実施例において、高速道路優先ではないときに、現在地及び目的地の矩形分割領域における主要一般道路の交差点への経路データ読出しに際して、国道の交差点へのルートを読出す例を示したが、現在地と目的地とが比較的近接していて、近くに国道が存在しない場合等においては、各矩形分割領域に近接している県道、或いはその他の道路の交差点へのルートのデータを用いることができる。また、上記の例において、各矩形分割領域から高速道路や国道へのルートを複数備えている例を示したが、各矩形領域が充分に小さく、或いは細かなリンクコストの差を無視しても良い場合は、各矩形領域から高速道路や国道へのルートはリンクコストの小さなものを1つだけ記憶しておき、このデータに基づいて経路を探索するようにしても良い。
【0043】
【発明の効果】本発明の請求項1に係る発明においては、従来の経路探索装置のように、経路の探索に際して階層の異なるデータを切換えて使う必要がないので、切換え時期の選択により、データ密度の大きい階層を広く検索することによる探索時間の増加、データ量の少ない階層を広く検索することによる探索経路の精度の悪化等の欠点を生じることが無くなり、常に高速で且つ適切な経路探索を行うことができる。
【0044】また、請求項2に係る発明においては、高速道路優先の探索指示入力時に、高精度で高速に適切な経路探索を高速道路優先で行うことができる。また、請求項3に係る発明においては、一般道路優先の探索指示入力時に、高精度で高速に適切な経路探索を一般道路優先で行うことができる。また、請求項4に係る発明においては、主要道路アクセス用経路データを高速道路、及び主要一般道路毎に複数備えているので、複数の経路の候補の中から最適な経路を探索することができ、より適切な経路探索が可能となる。また、請求項5に係る発明においては、各矩形分割領域には交差点を1つだけ含むように矩形分割領域を設定しているので、各矩形分割領域内、及び各矩形分割領域から近接主要道路へのアクセス経路のデータが簡素化し、高精度で高速に適切な経路探索を行うことができる。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013