• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:

    公开号:WO1989006414A1
    申请号:PCT/JP1988/001301
    申请日:1988-12-23
    公开日:1989-07-13
    发明作者:Takashi Yamada；Mitsuhiro Nimura；Yasuhiro Toyama；Shoji Yokohama
    申请人:Aisin Aw Co., Ltd.；Kabushiki Kaisha Shinsangyokaihatsu；
    IPC主号:G08G1-00
    专利说明:
    [0001] 明 細 書 ナビゲ一ショ ン装置のル一 ト探索方式
    [0002] 技 術 分 野
    [0003] 本発明は、 出発地から目的地までの最短経路を探索する ルー ト探索方法に関し、 特に、 地図データを階層構造にし て経路を探索するナビゲーショ ン装置のルート探索方式に 関する。
    [0004] 背 景 技 術
    [0005] ナビゲーショ ン装置は、 地理の不案内な運転者に対して 目的地までルー ト案内を行うものであり、 近年、 このナビ ゲーショ ン装置の開発が盛んに行われている。
    [0006] ナビゲ一シヨン装置は、 予め走行前に出発地及び目的地 を入力することによって出発地から目的地までのルートを 設定し、 その設定されたルー卜に従ってナビゲーションを 行うものである。 ナビゲーシヨ ンでは、 ルートを指示する 場合、 C R T画面に地図を表示しその上にルー トを重ねて 表示したり、 また、 或るものは、 予め設定されたルートに 従って次に曲がるべき交差点に関する情報として、 次に曲 がるべき交差点までの距離を数字やグラフ、 特徴的な写真 で表示したりさらには音声出力も併用するものもある。 道路網にあっては、 一般に出発地から目的地までの間に 複数のルートが存在するのが普通である。 そのため、 ナビ ゲーショ ン装置において、 出発地及び目的地が入力される と、 その間における最短時間或いは最短距離のルー ト （最 短ルート） を探索するルート探索の手法を採用する試みが なされている。 その 1つとして、 例えば四叉路の交差点の 場合には、 右左折、 直進、 Uターンを表現するために 8つ のノードと 1 6本の有向リンクで交差点を表し、 また、 交 差点柜互を接続する道路枝は 2本の有向リンクで表す方法 が報告されている。 もう 1つは、 最短ルートを検索した後、 進行禁止コースと比較し進行禁止ルートを含む最短ルート を除去することによつて進行禁止ルートを含まない最短ル ートを検索する方法 （例えば特開昭 6 2— 9 1 8 1 1号公 報） が提案されている。
    [0007] しかしながら、 上記前者の方法は、 交差点での右左折情 報を全て有向リンクで 現しているので、 データ量が多く なり、 そのため記憶容量が多くなるという問題がある。 ま た、 従来のデータ構造では、 右左折を検出して右左折によ り重み付けを行って最短時間のルート探索を行おうとする と、 右左折の判断の計算が複雑になり、 時間がかかる。 特 に、 四差路を 8つのノードと 1 6本の有向リンクで表現し ている場合には、 1 6本の有向リンクに重み付けした距離 又は時間のデータをもたなければならないため、 データ量 が多くなる。
    [0008] さらに加えて、 ルート探索では、 出発地から目的地まで の距離が長くなると、 また、 道路網の密度が高くなると、 それだけルート搮索の対象となる交差点が多くなる。 その ため、 ルート探索に要する計算時間や探索処理時に用いる メモリの記憶容量が増えるという問題がある。 本発明の目的は、 記憶データ量を少なく し右左折禁止デ —タの判断も含めて高速にルート探索できるようにするこ とである。 本発明の田の目的は、 ルー ト探索の計算時間の 短縮できるようにすることである。
    [0009] 発 明 の 開 示
    [0010] 上記目的を達成するため、 本発明は、 指定された出発地 から目的地までルートを設定してルートに沿って案内する ナビゲーショ ン装置において、 ルード探索に用いる地図デ ータとして、 位置情報とその属性に関する情報からなるノ 一ドデータと交差点に関する情報からなる交差点データと 道路に関する情報からなる道路データを備え、 交差点デ一 タと道路データから最適経路を探索することを特徵とする ものであり、 ルー ト探索に用いる地図データを階層化構造 にし、 幹線道路網の上位階層に対して幹線道路網に連結さ れる支線道路網を展開すると共にブロック分割し、 下位階 層から上位階層の道路網に連結している交差点までの探索 を順次繰り返し行い出発地から目的地までのルー トを探索 することを特徵とする。 また、 地図データとして、 各階層 の各ブ Πック毎に交差点と交差点間の道路に関する連結情 報及び上位階層との連結交差点情報を有し、 情報量に応じ て下位階層の分割プロック数を増やし、 出発地のプロック と目的地のプロックが同一プロック又は隣接プロックにな るまで下位階層から探索を繰り返しながら上位階層へ上げ てゆく。 地図データに右左折禁止情報、 案内不要や通過難 易度等の経路換算情報を設定し、 経路を探索する際には右 左折禁止情報の設定された道路を探索コ一スから除外し、 柽路換算情報を付加して最適経路を探索する。
    [0011] 上記構成により、 ルー ト探索では、 まず、 最下位の階層 で出発地、 目的地を舍むブロックでルート探索を行う場合 でそれが上位階層の交差点番号を持っているときは、 その 階層のブロックでルート探索を行う。 上位階層の交差点審 号を持っていない場合には、 その交差点から上位階層の交 差点蕃号を持つ交差点までのルート探索を行い、 さらに上 位階層のプロックに移行する。 そして、 出発地のプロック と目的地のブ σックが同一ブロック又は隣接ブロックにな ると、 その間で出発地から目的地までのルー ト探索を I 了 させる。
    [0012] 従って、 データ量が同程度になるように各階層ともプロ ック単位を設定することによって、 情報量が多く複雑な道 路網であっても、 常に同じ容量の中でルート探索を繰り返 し行うだけでよい。 そのため、 ルート探索に必要な記憶容 量も少なくてよいし、 効率良くルート搮索を行うことがで き、 ルート探索のための計算時間の短縮を図ることができ る。
    [0013] また、 道路データに右左折禁止情報や経路換算情報を設 定すると、 また、 経路探索手段が経路を探索する際には右 左折禁止情報の設定された道路を探索コースから除外し、 経路換算情報を使って効率よく最適経路を探索できるので、 無駄な探索処理がなくなり、 処理の高速化を図ることがで きる。 図面の簡単な説明 ·
    [0014] 第 1図は本発明に係るルート探索方法の 1実施例を説明 するための図、
    [0015] 第 2図は第 1図のレイヤ 2におけるプロック 1のデータ 構造の例を示す図、
    [0016] 第 3図は第 1図のレイヤ 2におけるプロック 4のデータ 構造の例を示す図、
    [0017] 第 4図は第 1図のレイヤ 2におけるプロック 6のデータ 構造の例を示す図、
    [0018] 第 5図は第 1図のレイャ 1におけるプロック 1のデータ 構造の例を示す図、 一
    [0019] 第 6図はワークファイルとイ ンデックスファイルの構造 を示す図、
    [0020] 第 7図は経路探索における全体の処理の流れを説明する ための図、
    [0021] 第 8図は同一ブロック探索ルーチンの例を示す図、 第 9図は隣接プロック探索ルーチンの例を示す図、 第 1 0図は遠隔ブロック探索ルーチンの例を示す図、 第 1 1図は経路探索サブルーチンの例を示す図、 第 1 2図は周囲道路検索サブルーチンの処理の流れを説 明するための図、
    [0022] 第 1 3図は最適経路条件設定サブルーチンの処理の流れ を説明するための図、
    [0023] 第 1 4図は終了条件確認サブルーチンの処理の流れを説 明するための図、 第 1 5図は道路網と交差点データ、 道路データ及びノー ド列データの例を示す図、
    [0024] 第 1 6図は本発明に係るナビゲ一シヨ ン装置のルー ト探 索方式に適用される 1実施例システム構成を示す図、 第 1 7図は本発明に係るルート探索により生成された交 差点列及びノ一ド列のデータ構造の例を示す図、
    [0025] 第 1 8図は交差点列及びノ一ド列取り出し処理の流れを 説明するための図である。
    [0026] 発明を実施するための最良の形態
    [0027] 第 1図において、 レイヤ 1は、 交差点番号 I、 Π、 ΠΙ、
    [0028] ……を持つ主要幹線道路網の地図であり、 1つのブロック 1で構成している。 レイヤ 2は、 レイヤ 1の主要幹線道路 '網に連結される支線の道路網も含めた地図であり、 6つの ブロック 1〜6で構成している。 そして、 ブロック間の接 続道路には、 レイヤ 2のブロック 1、 2間の交差点番号 V と Πのように、 ブロックで処理単位を構成することができ るように擬似的に交差点を設定している。 ブロック数は、 それぞれで情報量がほぼ同程度になるように設定される。 従って、 レイヤ 1のブロック 1とレイヤ 2のブロック 1〜 6は、 それぞれが道路網データとして同程度の情報量を有 するものである。
    [0029] 上記のように本発明のルー ト探索方法は、 地図データと して、 下位へ向けて幹線から支線へ展開すると共にブロッ ク分割した各レイヤ 1、 2、 ……からなる階層化構造のも のを用い、 出発地から目的地までのルートを探索するもの である。 従って、 レイヤ 2の道路網の下位にさらに支線の 道路がある場合には、 レイヤ 3が設定され、 情報量に応じ てブロック数も多くなる。 同様に、 レイヤ 1のブロック 1 だけでなくさらにその周囲の道路網も対象とする場合には 、 レイヤ 1がブロック 1とその周りの道路網のブロックに より構成される。 そして、 この場合には、 レイヤ 1の上位 階層のレイヤが設定される。
    [0030] 次に第 1図の道路データを用いたルート探索方法の 1例 を説明する。
    [0031] 例えば出発地と目的地がそれぞれレイヤ 2のブロック 1 にある交差点審号 Iとプロッグ 6にある交差点蕃号 mであ るとする。
    [0032] まず、 ブロック 1にある交差点審号 Iの出発地について は、 上位階層のレイヤ 1にない交差点審号である。 そこで 、 上位階層のレイヤ 1にある交差点審号を見つけ、 その交 差点番号 mと IV (レイヤ 1では交差点番号 Iと π ) までの ルー トを探索して上位階層に上がる。
    [0033] 他方、 ブロック 6にある交差点審号! [[は、 上位階層のレ ィャ 1に交差点蕃号 VDIとしてあるので、 そのまま上位階層 に上がる。 上位階層のレイヤ 1では、 下位階層のレイヤ 2で探索した情報と合わせて交差点審号 I又は Πから交差点審号 IIまでのルート探索を行う。
    [0034] 上記の例から明らかなように、 出発 、 目的地が存在す るブロックにより、 ①同じブロックの場合と、 ②隣接プロ ックの場合と、 ③離れたブロックの場合の 3種類に分類で きる。 そこで、 本発明のルー ト探索方法は、 それぞれに応 じて次のようにルート探索を行う。
    [0035] まず、 ①の出発地と目的地が同じブロックにある場合に は、 そのブロックの中でルート探索を行う。 また、 ②の出 発地と目的地の各ブロックが隣接している場合には、 出発 地ブロックと目的地プロックが接続している交差点 （接続 交差点） を検出し、 出発地から接続交差点、 目的地から接 続交差点の 2回に分けてルー ト探索を行う。 しかし、 ③の 出発地と目的地の各プロック間が離れている場合には、 上 記の例のように出発地ブロックで出発地から上位のレイヤ に接続している交差点までの探索を行い、 同様に目的地ブ 口ックで目的地から上位のレイヤ'に接続している交差点ま で'の探索を行う。 そして、 上記'①又は②の条件が満足する まで同様のルート探索を上位のレイヤに上がつて行う。 次に上記のルー ト探索方法に用いるのに好適な道路デ一 タめ具体的な構造例を示す。
    [0036] 各ブロック単位のデータは、 第 2図〜第 5図に示すよう に、 それぞれ道路データ （同図 (a)) と交差点データ （同図 (b)) からなる。 そして、 例えば第 2図に示すように道路デ —タは、 ブ口ック内の各道路蕃号に対応して、 始点の交差 点審号、 終点の交差点蕃号、 同じ始点をもつ道路蕃号、 同 じ^点をもつ道路蕃号、 案内不要道路、 道路の相対長さ、 レイヤ等の情報を有している。 道路蕃号の単位は、 通常、 複数個のノードからなる。 ノードデータは、 図示しないが 道路上の 1地点に闋するデータであり、 ノ一ド間を接続す るものをアークと呼ぶと、 複数のノ一ド列のそれぞれの間 をアークで接続することによって道路が表現される。 また、 交差点データは、 ブ nック内の交差点審号に対応して、 東 経、 北緯、 出る道路番号、 入る道路蕃号、 上のレイヤの交 差点番号、 下のレイヤの交差点番号、 横のブロックの交差 点番号 （接続交差点審号） 等の情報を有している。
    [0037] これらのうち、 同じ始点 （終点） をもつ道路審号ゃ出る (入る） 道路蕃号は、 それぞれ交差点における連結道路の 情報であり、 通常、 複数の道路審号が存在するので、 その うちの一審小さい道路蕃号を登録しておく。 このようにす ると、 後述するように交差点の連結道路の検索が容易に行 える。 また、 案内不要道路や道路の相対長さは、 走行に要 する実質的な時間を算出する場合に必要となる情報である。 例えば、 同じ幅や長さの道路であっても案内を要する道路 より案内不要道路の方が実質的な走行時間は短めに換算す ることができ、 同じ長さの道路であっても走行条件が悪い とか渋滞がしゃすい道路であれば相対長さが長くなる。 レ ィャは、 道路のランクを示している。 つまり、 どの順位の レイヤでもつ道路かを示す情報である。 上 （下） のレイヤ の交差点蕃号、 例えば 1一 1— 2は、 レイヤ 1一ブロック 1一そのレイヤブロックでの交差点番号を示している。 横 のブロックの交差点番号も同様である。
    [0038] 次に本発明に係るルート探索方法を処理の流れに従って 説明する。
    [0039] ワークファイルは、 ブロック単位で探索を行う際に、 ブ 口ック内の交差点データ及び道路データを読み込んで使用 するものであり、 第 6図 (a)に示すように交差点数、 始点、 終点、 道路数、 ブロックの探索結果得られる交差点に入る 道路蕃号、 ブロックの探索の出発地と目的地を示すフラグ 等の情報を格納するものである。 イ ンデックスファイルは ブロックの情報を管理するものであり、 同図 (b)に示すよう にブロック数とプロック蕃号等の情報を有している。
    [0040] 第 7図に示すように経路探索では、 まず、 イ ンデックス ファイルより出発地、 目的地のブ nックの位置関係を調べ その位置関係により以下の同一ブロック探索、 瞵接ブ口ッ ク探索、 遠隔ブロック探索のいずれかの処理ルーチンに分 岐する。
    [0041] 同一ブロック探索では、 第 8図に示すように交差点デー タ、 道路データを入力するとともに、 ワークエリアを初期 化し、 出発地、 目的地を設定する。 しかる後、 経路探索サ ブルーチンに分岐し、 そこで探索、 生成されたルートを出 力する。
    [0042] 隣接ブロック探索は、 交差点蕃号を C (レイヤーブロッ クー交差点蕃号） 、 道路審号を R (レイヤーブロック一道 路蕃号） の形式で表し、 出発地を C ( 2 - 1 - 1 ) 、 目的 地を C ( 2— 4一 4 ) とすると、 第 9図に示すステップで 次のように処理する。
    [0043] ①、 ② 出発地のあるレイヤ 2、 ブロック 1のデータを読 み込む ο
    [0044] ③ 接続交差点 Sを下記のようにメモリに記憶する。 接 続 交 差 点 s
    [0045] C (2 - 1 - 6) C (2 -4 - 5)
    [0046] C (2 - 1 - 7) C (2 -4 -4)
    [0047] ④ ワークエリァにおけるプロック内の全ての交差点を下 記のように設定して初期化する。
    [0048] 交差点に来る道路— 0
    [0049] フラグ —未探索
    [0050] 距離 — 7 FFFFFFFH
    [0051] ⑤ ワークエリアにおける出発地交差点 C (2 - 1 - 1 ) のフラグに 「仮」 、 距離に 「0」 をセッ 卜する。
    [0052] ⑥ 目的地として連続交差点 （2— 1— 6) 、 C (2 - 1 -7) を設定する。
    [0053] ⑦ 出発地交差点 C (2 - 1 - 1) から仮の目的地である 連続交差点 （2— 1一 6) 、 C (2 - 1 - 7) までの探索 を行う。
    [0054] ⑧、 ⑨ ワークエリアをセーブする。 このとき接続交差点 までの距離を下記のようにメモリに記憶する。
    [0055]
    [0056] ⑩〜⑮ 出発地を C (2 -4 - 1) 、 目的地を接続交差点 C (2 -4 - 5) 、 C (2 -4 -4) として④〜⑦と同様 の探索を行う。 2
    [0057] ⑯〜⑰ 最短コースとなる接続交差点を選ぶ。 例えば出発 地からの距離、 目的地からの距離が
    [0058] であるとすると、 接続交差点は、
    [0059] (6 + 5) < (1 1 + 8)
    [0060] から距離が短い方の C (2- 1-6) 、 C (2-4-5) となる。
    [0061] ⑱ 目的地ブロックのルート C (2-4-1) 一 C (2— 4-5) を作成する。
    [0062] ⑲〜⑳ ワークエリァをロードし、 出発地ブロックのル一 ト C (2-1-1) -C (2-1-3) 一 C (2-1-6) を作成する。
    [0063] @ 上記のそれぞれのルートを合成し、 C (2-1 -1) -C (2-1 -3) 一 C (2-1 -6) 一 (2-4-1) 一 C (2-4-5) を出力する。
    [0064] 続いて遠隔ブロック探索を説明する。 ここでは、 出発地 を C (2-1 -1) 、 目的地を C (2-6-2) とする。 ①〜② 出発地のあるレイヤ 2、 ブロック 1のデータを読 み込む o
    [0065] ③ 上位のレイヤへの接続交差点 S 2を検出する。
    [0066] 一一以下余白 —— 接 続 交 差 点 S 2
    [0067] C (1 -1 -1)
    [0068] C (1 -1 -2)
    [0069] ④〜⑦ 出 u発地を C (2-1 -1) 、 目的地を C (2-1 一 3) 、 C ( 12-1 -4) として探索し、 ワークエリアを セーブする。
    [0070] ⑧ 出発地から接続交差い点 S 2までの距離をメモリに記憶 する。
    [0071]
    [0072] ⑨〜⑩ 目的地のあるレイヤ 2、 ブロック 6のデータを読 み込む。
    [0073] ⑪ 上位のレイヤへの接続交差点 D 2を検出する。
    [0074]
    [0075] ⑫〜⑮ 出発地を C (2-6-2) 、 目的地を C (2-6 - 1 ) 、 C (2-6-3) として探索し、 ワークエリアを セーブする。
    [0076] ⑬ 出発地から接続交差点 D 2までの距離をメモリに記憶 する。
    [0077] ⑰〜⑱ 上位のレイヤ 1、 ブロック 1のデータをそれぞれ 入力する。
    [0078] ⑲ 出発地として接続交差点 S 2 (C (1— 1一 1) 、 C
    [0079] (1-1-2) ) を設定する。 また、 距離の初期地として 出発地から接続交差点 S 2までの距離をセットしておく。 ⑳ 目的地として接続交差点 D 2 (C (1-1 -7) 、 C
    [0080] (1-1-8) ) を設定する。
    [0081] ㉑ 接続交差点 S 2 (C (1-1-1) . C (1-1-
    [0082] 2) ) から接続交差点 D 2 (G (1-1-7) 、 C (1一
    [0083] 1-8) ) 探索を行う。
    [0084] © 出発地から接続交差点 D 2までの距離と目的地から接 続交差点 D 2までの距離を比較する。 例えば出発地からの 距離、 目的地からの距離が
    [0085]
    [0086] であるとすると、 接続交差点は、
    [0087] (22 + 3) < (2 1 + 2)
    [0088] から距離が短い方の C (2-6-3) 、 C (1-1-8) が最短ルートとなる接続交差点 D 2である。 ㉓ レイヤ 1のルート C ( 1 - 1 - 8) — C ( 1一 1一 6) 一 C ( 1 - 1 - 5) — C ( 1 - 1 - 2) を取り出す。 ㉔〜 ® 出発地ブロックのワークエリアをロードし、 出発 地ブロックのルート C (2 - 1 - 4) -C ( 2 - 1 - 2 ) -C (2 - 1 - 1 ) を取り出す。
    [0089] ⑳〜 © 目的地ブロックのワークエリアをロードし、 目的 地ブロックのルー ト C (2 - 6 - 3) -C (2 - 6 - 2) を取り出す。
    [0090] ⑳ 上記のそれぞれのルー トを合成し、 C ( 2— 1— 1 ) — C (2 - 1 - 2) 一 C ( 2 - 1 - 4) 一 C ( 1一 1一 5) 一 C ( 1 - 1 - 6) 一 C ( 2 - 6 - 3) 一 C (2 - 6 - 2) を出力する。
    [0091] 次に経路探索サブルーチンを説明する。
    [0092] 第 1 1図において、 L (c) は距離、 F (c) はフラグ、 R (c) は通過してきた道路番号、 s。 ， s , は出発地の両隣 りの交差点審号、 e。 ， は目的地の両隣りの交差点審 号である。 また、 cは交差点蕃号、 フラグ F (c) は 「 0」 が未探索、 「 1」 が探索中、 「 2」 が探索終了を示す。
    [0093] ① 全ての交差点について
    [0094] 距離 L (c) に無限大 （∞)
    [0095] フラグ F (c) に 「 0」 （未探索） '
    [0096] にセッ トする。 この初期設定によりまず全ての交差点が未 探索となり、 出発地からの距離が無限大となる。
    [0097] ② 出発地の両隣りの交差点蕃号 s。 ， s , に対応する距 離 L (s。 ） ， L (S l ) に出発地からの距離を入れ、 さ らに出発地の雨隣りの交差点蕃号 s。 ， s , に対応するフ ラグ F ( s。 ） ， F ( s , ) にそれぞれ 「 1」 をセッ トし、 通過してきた道路審号 R (c) に出発地からの道路審号をセ ッ トす o
    [0098] ③ フラグ Fが 「 2」 でなく且つ距離 L (c) が最小となる 交差点審号 cQ を検索する。
    [0099] ④ 周囲道路検索サブルーチンを実行し、 交差点審号 c。 を始点とする周囲道路を検索する。
    [0100] ⑤ 周囲道路があるか否かを調べる。
    [0101] YE Sの場合には次の処理⑥に移り、 NOの場合には処 理⑪に移る。
    [0102] ⑥ 最適経路条件設定サブル チンを実行し、 最適経路を 搮索するための道路状況その他の条件を設定する。
    [0103] ⑦ その道路 終点の交差点蕃号を c , 、 道路の長さを とする。
    [0104] ⑧ その道路の終点の交差点までの距離 Ρを計算する。
    [0105] P = L (co ) を計算する。
    [0106] ここで L (c。 ） は出発地から交差点審号 cD までの距離 であり、 Pは交差点蕃号 c。 からその道路 （探索中の道路 ) を通って終点の交差点蕃号 c , までの距離となる。
    [0107] ⑨ Pく L ( c ） で且つ F ( c , ) ≠ 2か否かを調べる。
    [0108] YESの場合には次の処理⑩に移り、 NOの場合には処 理④に苠る。
    [0109] ⑩ 出発地から探索中の交差点蕃号 c , までの合計距離 L (c i ) を P、 その交差点蕃号 c , のフラグ F (c , ) を 「 1」 、 交差点番号 c , に至るまでに通過してきた道路番 号 R ( c , ) をその探索中の道路審号とする。
    [0110] ⑪ 処理⑤において N Oの場合には F ( c；。 ） を 「2」 に セッ トすな o
    [0111] ⑫ 終了条件確認サブルーチンを実行する。
    [0112] ⑬ 処理終了か否かを調べ、 N Oの場合には処理③に戻り、 Y E Sの場合には処理を終了とする。
    [0113] 以上の処理を行うことによりそれぞれの交差点番号に対 応して出発地から当該交差点蕃号に至る最適コースの道路 蕃号がそれぞれ交差点蕃号毎に設定される。
    [0114] 上記処理④の周囲道路検索サブルーチンは、 第 1 2図に 示す処理を行う。 すなわち、 -
    [0115] ① 周囲道路の検索が 1回目か否かを調べる。
    [0116] Y E Sの場合には処理②に移り、 N Oの場合には処理⑥ に移る。
    [0117] ② 交差点データから現在いる交差点 c D が始点となって レ、る道路蕃号を取り出し記憶する。
    [0118] ③ 道路データを参照し探索中の当該交差点 c。 にくる道 路審号における禁止道路を取り出す。 ④ 今取り出した道 路が禁止道路か否かを調べる。
    [0119] Y E Sの場合には処理⑥に移り、 N Oの場合には次の処 理⑤に移る。
    [0120] ⑤ 今取り出した道路を周囲道路として記憶し、 リターン する （第 1 1図の処理⑤へ移る） 。
    [0121] ⑥ 道路データから前に探索した道路と同じ始点を持ち、 蕃号が次の道路審号を取り出す。
    [0122] ⑦ 最初探索した道路と今取り出した道路が同じか否かを 調べる。 -
    [0123] Y E Sの場合には次の処理⑧に移り、 N Oの場合には処 理③に戻る。
    [0124] ⑧ 周囲道路なしと判定しリターンする。
    [0125] また、 上記第 1 1図に示す処理⑥の最適経路条件設定サ ブル一チンは、 第 1 3図に示すような処理を行うものであ る。 すなわち、
    [0126] ① 道路データから相对長さ ^を読み込む。
    [0127] ② 道路データから現在探索中の交差点へ通過してきた道 路の案内不要データを読み込む。
    [0128] ③ 案内不要データと一致する周囲道路があるか否かを調 ベる。
    [0129] Y E Sの場合にはリターンし、 N Oの場合には次の処理 ⑥に移る。
    [0130] ④ さらに長さ Άに b mを加算した値を新たな長さ ^とし リターンする。 すなわち、 案内不要の交差点に对して、 右 左折等の案内を要する交差点は、 距離に換算して b m加算 した評価としている。
    [0131] 終了条件確認サブルーチンでは、 第 1 4図に示すように 探索対象の交差点審号 c 0 と目的等の両隣りの交差点蕃号 との一致を調べ、 一致したことを条件に例えば終了フラグ を設定する。
    [0132] 次に、 本発明に係るルート探索方法に使用される道路デ ータ等の他の構成例を第 1 5図により説明する。
    [0133] 道路のネッ トワークデータは、 道路のネッ トワークが例 えば第 1 5図 (a)に示すような交差点審号 I〜！ V、 道路番号
    [0134] ①〜⑧からなるものとした場合、 交差点データについては 同図 (b)、 道路データについては同図 (c)、 ノ一ドデータにつ いては同図 (d)に示すようなデータ構成となっている。
    [0135] すなわち、 交差点データは、 同図 (b)に示すように交差点 審号 I〜！ Vに対応して交差点名、 当該交差点が始点となつ ている道路のうちー蕃審号の小さい道路審号、 当該交差点 が終点となっている道路のうち一審番号の小さい道路審号、 信号の有無からなる。
    [0136] また、 道路データは、 同図 (c)に示すように道路蕃号①〜
    [0137] ⑧に対応して交差点番号による始点、 終点、 同じ始点を持 つ道路のうち番号が次のもの、 同じ終点を持つ道路のうち 審号が次のもの、 道路の太さ、 禁止情報、 案内不要情報、 写真審号、 ノード数、 ノード列データの先頭ア ドレス、 長 さ等カヽらなる。
    [0138] そして、 ノードデータは、 同図 (d)に示すように東経、 北 緯、 属性等からなり、 道路データから明らかなように道路 審号の単位は複数個のノ一ドからなる。 すなわち、 ノード データは道路上の 1地点に関するデータであり、 ノ一ド間 を接続するものをアークと呼ぶと、 複数のノード列のそれ ぞれの間をァ一クで接続することによつて道路が表現され る。 例えば道路蕃号①に関して見ると、 道路データよりノ ード数 1 5からなりノードデータの先頭アドレスが 1 0 0 であることから、 道路蕃号①は、 1 0 0から 1 1 4までの ァドレスのノ一ドデータで構成されることになる。
    [0139] これらのネッ トワークデータによると、 例えば、 交差点 蕃号 Iに着目した場合、 ここを始点とするコースでは、 ま ず交差点データの始点情報から道路蕃号①、 次にこの道路 蕃号①に関する道路データの 「同じ始点を持つ道路のうち 審号が次のもの」 から道路審号⑦が検索される。 そして、 道路蕃号⑦における同様の情報では、 逆に道路蕃号①であ ることから周囲道路として他の道路蕃号のものはないこと が判断できる。 これは、 終点に関しても同様である。 また 道路データにおける道路審号⑤では、 道路蕃号⑥が禁止に なっていることから、 第 1 5図 (a)に示すネッ トワークの交 差点蕃号 IVにおいて、 道路審号⑤から⑥へは右左折禁止等 のために進入できず、 進入可能な道路は道路審号⑧だけと なる。 従って、 この道路審号⑧への進入は案内不要となる。 このように特に道路データでは、 右左折禁止等の進入禁止 の道路審号と案内不要の道路蕃号をもっていることにより、 情報記憶の容量を少なくし、 また経路探索を容易に行える ようにしている。
    [0140] 次に、 本発明に係るルート探索方法が適用されるシステ ムの例を第 1 6図により説明する。
    [0141] 第 1 6図において 1は交差点データ、 2は道路データ、 3はノードデータ、 4はル一ト搮索処理部、 5は交差点列 及びノード列生成部、 6は交差点列及びノード列データ、 7はナビゲーション部を示す。 経路探索処理部 4は、 第 7 図に示す処理を行うものであり、 先に說明した同一プロッ ク探索処理ルーチン、 隣接ブロック探索処理ルーチン、 遠 隔ブロック探索処理ルーチン、 探索サブルーチンを有する。
    [0142] さらに、 探索サブルーチンの下には、 右左折禁止等の進 入禁止道路を除き交差点から周囲道路を検索する周囲道路 検索サブルーチン、 道路幅の広狭、 案内の要否その他最適 経路を演算するのに必要な条件を設定する最適経路条件設 定サブルーチン、 経路探索の終了を判定する終了条件サブ ルーチンを有し、 指定された出発地から目的地までの最適 経路を探索する。 交差点列及びノ一ド列生成部 5は、 経路 探索処理部 4により最適経路が探索されると、 その経路に 沿った第 1 7図に示すような交差点列及びノ一ド列データ 6を生成するものであり、 この交差点列及びノ一ド列デ一 タ 6によりナピゲ一ショ ンを行うのがナピゲ一シヨン部 7 である。 ナビゲーシヨン部 7は、 データ処理手段、 表示や 音声の出力手段を有し、 コース走行の所定の地点で交差点 列及びノ一ド列データ 6を読み出し、 表示出力や音声出力 によりコース案内を行う。
    [0143] 上記のように本発明のルート探索では、 周囲道路の大き さや道路の案内要 不要等の走行条件を考慮して交差点間 の距離に重み付けを行い、 最短経路を探索する。 その結果、 各交差点に対応して最適コースに沿った道路番号情報が得 られる。 従って、 この探索結果に従って第 1 8図に示す処 理フローに従って交差点列及びノ一ド列のデータを生成す ることができる。 ① 探索が終了した交差点審号をメモリに記憶する。
    [0144] ② その交差点にきた道路審号の始点をメモリに記憶する。
    [0145] ③ その交差点が出発地の両隣りの交差点か否かを調べる。
    [0146] Y E Sの場合には次の処理④に移り、 N Oの場合には処 理②に戻る。
    [0147] ④ 記憶した交差点蕃号列の前と後に出発地蕃号、 目的地 蕃号を加えて交差点列とする。
    [0148] ⑤ 道路データを参照して交差点間のノード列を取り出し、 ノ一ド列をつくる。
    [0149] ⑥ 案内不要データを使い交差点列から案内不要となる交 差点を除く。
    [0150] このようにして経路探索の結果から生成される交差点列 およびノ一ド列データの例を示したのが第 1 7図である。 例えば交差点列データは、 第 1 7図 (a)に示すように交差点 名、 交差点蕃号、 その交差点の特徵風景等を撮影した写真 番号、 曲がる角度、 距離等の情報からなり、 また、 ノード 列データは、 同図 (b)に示すようにそのノ一ド位置を表す東 経、 北緯、 そして交差点蕃号、 属性、 角度、 距離等の情報 からなる。 しかも、 これらのデータは、 案内不要の交差点 を除いた、 案内を要する交差点のみのデータからなる。 従 つて、 ナビゲーシヨンでは、 所定の位置に対応してこのデ ータを順次読み出して出力すればよい。
    [0151] 上記のように本発明のルート探索では、 右左折禁止デー タをチユックしながら探索し、 右左折禁止が入らないコー スを搮索する。 また、 周囲道路の大きさや道路の案内要 Z 不要等の走行条件を考慮した通過難易度等の経路換算情報 により交差点間の距離に重み付けを行い、 最短ルートを探 索する。
    [0152] なお、 本発明は、 上記の実施例に限定されるものではな く、 種々の変形が可能である。 例えば上記の実施例では、 出発地と目的地が同一プロックになるか、 隣接プロックに なるまで上位階層へ上げて探索を行うようにしたが、 隣接 ブロックの場合も探索を行って上位のレイヤに上げ、 最終 的には同一プロック内の探索により出発地と目的地とを連 結するようにしてもよい。 ただ、 このようにすると、 隣接 プロック間で上位のレイヤにはないが、 上位のレイヤでの 主要道路のルートよりも適当なルートがあっても、 このル ートが設定されなくなる。 従って、 隣接ブロックの場合に はその階層でルート探索を終了させる方が効率的であると いえる。
    [0153] 例えば出発地から経路探索をスタートさせたが、 目的地 から経路探索をスタートさせるようにしてもよい。 また、 出発地から経路探索をスタートして目的地に達したところ で処理終了にしたが、 全てのフラグ F ( c ) が 2になるま で、 すなわち、 全ての交差点について経路探索を行うよう にしてもよい。 特に目的地からこの経路探索を行うと、 全 ての交差点から目的地までの最適コース情報が作成される ことになるので、 途中でコースから外れた場合にも、 経路 探索を再度行うことなく、 最寄りの交差点から交差点列及 びノード列を作成することができる。 以上の説明から明らかなように、 本発明によれば、 父 点データ、 道路データ等の道路網データを階層化構造にし て持ち、 下位階層 （レイヤ） から順に上位階層へ上げて探 索を行うので、 探索範囲を限定して処理することができ、 探索処理の高速化を図ることができる。 また、 各階層にお いてデータ量に応じてブロック分割し、 ブロック単位で探 索を行うので、 探索に必要な作業領域を少なくすることが でき、 記憶領域の節減を図ることができる。
    [0154] 交差点データ、 道路データ及びノ―ド列データを予め C D— R O M等の記憶手段に格納しておき、 経路探索をする 前にこれらのデータを R A M等に読み取つて右左折禁止を チェックしながら経路探索を行うので、 経路探索を高速化 することができる。 また、 右左折禁止データを道路データ に舍めて持っているためデータ量を少なくすることができ、 記憶容量を少なくすることができる。 さらには、 案内不要 データをもちこのデータにより直進か右左折かの判断する ので、 最短時間経路探索を少ないデータ量で行うことがで きる。 しかも、 直進する交差点を案内不要データから認識 して交差点列から除き、 右左折する交差点のみのデータと することが簡単な処理で行える。
    权利要求:
    Claims
    1 . 指定された出発地から目的地までルートを設定してル 一トに沿って案内するナビゲ一ション装置において、 ルー ト探索に用いる地図データとして、 位置情報とその属性に 関する情報からなるノードデータと交差点に関する情報か らなる交差点データと道路に関する情報からなる道路デ一 タを備え、 交差点データと道路データから最適経路を探索 することを特徵とするナビゲ一ション装置のルート探索方 の
    式。
    2 . 地図データを階層化構造にし、 幹線道路網の上位階層 に対して幹線道路網に連結される支線道囲路網を展開すると 共にプロック分割し、 下位階層から上位階層の道路網に連 結している交差点までの探索を順次繰り返し行い出発地か ら目的地までのルー トを探索することを特徴とする請求項 1記載のナビゲ—ショ ン装置のルー ト探索方式。
    3 . 情報量に応じて下位階層の分割ブ nック数を増やし、 出発地のプロックと目的地のプロックが同一ブロック又は 隣接プロックになるまで下位階層から上位階層への探索を 繰り返すことを特徴とする請求項 2記載のナビゲーション 装置のルー ト探索方式。
    4 . 地図データとして、 各階層の各ブロック毎に交差点と 交差点間の道路に関する連結情報及び上位階層との連結交 差点情報を有することを特徴とする請求項 2記載のナピゲ —シヨン装置のルー ト探索方式。
    5. 地図データに右左折禁止情報、 案内不要や通過 ip易度 等の経路換算情報を設定し、 経路を探索する際には右左折 禁止情報の設定された道路を探索コースから除外し、 経路 換算情報を付加して最適経路を探索することを特徴とする 請求項 1記載のナビゲーション装置のルート探索方式。
    类似技术:
    公开号 | 公开日 | 专利标题
    US10001378B2|2018-06-19|Incremental map generation, refinement and extension with GPS traces
    US6144318A|2000-11-07|Navigation system
    US5899955A|1999-05-04|Method and apparatus for searching a route
    EP1315136B1|2004-11-17|Navigation system
    DE69731579T2|2005-03-31|Routensuch- und Routenführungsvorrichtung
    CN101097153B|2011-12-14|导航装置
    CN100543422C|2009-09-23|导航装置
    JP3769104B2|2006-04-19|交差点ルーチング用ナビゲーションシステム及び交差点ルーチング方法
    US6598016B1|2003-07-22|System for using speech recognition with map data
    JP5004388B2|2012-08-22|ルートのコンパクト表現のための方法及びシステム
    DE60130054T2|2008-05-15|Verfahren und Vorrichtung zur Routenführung
    EP1855263B1|2012-08-15|Map display device
    US6487305B2|2002-11-26|Deformed map automatic generation system including automatic extraction of road area from a block map and shape deformation of at least one road area drawn in the map
    JP3639412B2|2005-04-20|標識テキスト表示方法及び車両ナビゲーションシステム
    US5848375A|1998-12-08|Method of automatically generating road network information and system for embodying the same
    US6023655A|2000-02-08|Map database apparatus
    US6249742B1|2001-06-19|Method and system for providing a preview of a route calculated with a navigation system
    US6347280B1|2002-02-12|Navigation system and a memory medium in which programs are stored
    JP4793703B2|2011-10-12|経路案内システムのセンタ装置
    US5121326A|1992-06-09|Display system in navigation apparatus
    EP0807803B1|2005-02-23|Road map information readout apparatus, recording medium and transmitting method
    DE69732015T2|2005-11-03|Karthographisches Datenbankgerät
    JP3675891B2|2005-07-27|車両ナビゲーションシステムにおけるルート計算を行なうためのハイウェイアクセスランプ識別方法
    EP1589511B1|2008-12-31|Apparatus and method for processing traffic information
    US6810327B2|2004-10-26|Navigation apparatus, map information storage medium, and method of providing information about area lying beyond intersection
    同族专利:
    公开号 | 公开日
    US5168452A|1992-12-01|
    EP0346492A1|1989-12-20|
    DE3853719T2|1995-10-05|
    DE3853719D1|1995-06-08|
    EP0346492B1|1995-05-03|
    EP0346492A4|1991-11-13|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    1989-07-13| AK| Designated states|Kind code of ref document: A1 Designated state(s): US |
    1989-07-13| AL| Designated countries for regional patents|Kind code of ref document: A1 Designated state(s): AT BE CH DE FR GB IT LU NL SE |
    1989-08-25| WWE| Wipo information: entry into national phase|Ref document number: 1989900884 Country of ref document: EP |
    1989-12-20| WWP| Wipo information: published in national office|Ref document number: 1989900884 Country of ref document: EP |
    1995-05-03| WWG| Wipo information: grant in national office|Ref document number: 1989900884 Country of ref document: EP |
    优先权:
    申请号 | 申请日 | 专利标题
    JP62333038A|JP2641470B2|1987-12-28|1987-12-28|ナビゲーション装置|
    JP62/333038||1987-12-28||
    JP63/207762||1988-08-22||
    JP20776288A|JP2653847B2|1988-08-22|1988-08-22|ナビゲーション装置及びそのルート探索方法|DE19883853719| DE3853719D1|1987-12-28|1988-12-23|Wegsuchverfahren für navigationssystem.|
    EP89900884A| EP0346492B1|1987-12-28|1988-12-23|Route search method for navigation system|
    DE19883853719| DE3853719T2|1987-12-28|1988-12-23|Wegsuchverfahren für navigationssystem.|
    [返回顶部]