JP2866358B2 - ナビゲーション装置 - Google Patents
ナビゲーション装置Info
- Publication number
- JP2866358B2 JP2866358B2 JP9034957A JP3495797A JP2866358B2 JP 2866358 B2 JP2866358 B2 JP 2866358B2 JP 9034957 A JP9034957 A JP 9034957A JP 3495797 A JP3495797 A JP 3495797A JP 2866358 B2 JP2866358 B2 JP 2866358B2
- Authority
- JP
- Japan
- Prior art keywords
- road
- data
- information
- intersection
- route
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Landscapes
- Instructional Devices (AREA)
- Navigation (AREA)
- Traffic Control Systems (AREA)
Description
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、出発地から目的地
までの最短経路を探索するナビゲーション装置に関す
る。 【０００２】 【従来の技術】ナビゲーション装置は、地理の不案内な
運転者に対して目的地までコース案内を行うものであ
り、近年、このナビゲーション装置の開発が盛んに行わ
れている。 【０００３】ナビゲーション装置は、予め走行前に出発
地及び目的地を入力することによって出発地から目的地
までのコースを設定し、その設定されたコースに従って
ナビゲーションを行うものである。ナビゲーションで
は、コースを指示する場合、ＣＲＴ画面に地図を表示し
その上にコースを重ねて表示したり、また、或るもの
は、予め設定されたコースに従って次に曲がるべき交差
点に関する情報として、次に曲がるべき交差点までの距
離を数字やグラフ、特徴的な写真で表示したりさらには
音声出力も併用するものもある。 【０００４】道路網にあっては、一般に出発地から目的
地までの間に複数のコースが存在するのが普通である。
そのため、ナビゲーション装置において、出発地及び目
的地が入力されると、その間における最短時間或いは最
短距離のコース（最短コース）を探索する経路探索の手
法を採用する試みがなされている。その１つとして、例
えば図１２に示すように四叉路の交差点の場合には、右
左折、直進、Ｕターンを表現するために８つのノードと
１６本の有向リンクで交差点を表し、また、交差点相互
を接続する道路枝は２本の有向リンクで表す方法（例え
ば特開昭６２−８２３１６号公報）が報告されている。
もう１つは、最短コースを検索する毎に車両の進行が禁
止されている道路を含んでいないかをチェックし、進行
禁止の道路を含む最短コースは排除し、他の交差点を通
る最短コースを検索する方法（例えば特開昭６２−９１
８１１号公報）が報告されている。 【０００５】 【発明が解決しようとする課題】しかしながら、上記前
者の方法は、交差点での右左折禁止を全て有向リンクで
表現しているので、データ量が多くなり記憶容量が多く
なるという問題がある。また、後者の方法は、交差点で
の右左折禁止をネットワークデータとは別にして交差点
番号でもっているので、経路探索時の検索に要する処理
が多くなり、処理速度が遅くなるという問題がある。 【０００６】本発明は、上記の問題点を解決するもので
あって、記憶データ量を少なくし右左折禁止データや案
内不要データの判断も含めて高速に経路探索することが
できるナビゲーション装置を提供することを目的とする
ものである。 【０００７】 【課題を解決するための手段】そのために本発明は、ナ
ビゲーション装置において、始点から終点で表される道
路単位で道路データを格納した記憶手段と、該記憶手段
に記憶された道路データを用いて案内情報を出力する経
路案内処理部とを有し、前記記憶手段は、道路データと
して、該道路における情報、及び該道路データの始点ま
たは終点に接続する道路に関する情報を格納し、前記経
路案内処理部は、前記道路データに格納された情報に基
づき案内情報を出力することを特徴とし、前記経路案内
処理部は、前記道路データの該道路における情報及び前
記接続する道路に関する情報に基づき経路を探索して、
該探索した経路に基づき案内情報を出力することを特徴
とするものである。 【０００８】また、交差点から交差点で表される道路単
位で道路データを格納した記憶手段と、該記憶手段に記
憶された道路データを用いて案内情報を出力する経路案
内処理部とを有し、前記記憶手段は、道路データとし
て、該道路データの少なくとも１つの交差点に接続する
道路への接続に関する情報、及び該道路を表示するため
の座標に関する情報を格納し、前記経路案内処理部は、
前記道路データに格納された前記接続に関する情報に基
づき経路を探索し、該探索された経路と前記道路データ
に格納された道路を表示するための座標に関する情報に
基づき経路を表示することを特徴とし、前記記憶手段
は、道路データとして、経路探索を行うための情報と共
に道路地図を表示するための座標列に関する情報を格納
し、前記経路案内処理部は、前記道路データの経路探索
を行うための情報に基づき経路を探索し、前記座標列に
関する情報に基づき前記探索された経路と前記道路地図
を表示することを特徴とするものである。 【０００９】 【作用及び発明の効果】本発明のナビゲーション装置で
は、端点から端点で表される道路単位で道路データを格
納した記憶手段と、該記憶手段に記憶された道路データ
を用いて案内情報を出力する経路案内処理部とを有し、
前記記憶手段は、道路データとして、該道路における情
報、及び該道路データの少なくとも１つの端点に接続す
る道路への接続に関する情報を格納し、前記経路案内処
理部は、前記道路データに格納された情報に基づき案内
情報を出力するので、道路単位で道路における情報、及
び始点または終点に接続する道路に関する情報に基づき
案内情報の出力を行い、処理を簡素化できる。 【００１０】しかも、前記経路案内処理部は、前記道路
データの該道路における情報及び前記接続する道路に関
する情報に基づき経路を探索して、該探索した経路に基
づき案内情報を出力するので、接続する道路に関する情
報として、右左折禁止情報や案内不要情報を設定するこ
とにより、経路の探索や案内情報の出力で無駄な探索処
理や案内処理をなくすことができ、処理の高速化を図る
ことができる。 【００１１】また、交差点から交差点で表される道路単
位で道路データを格納した記憶手段と、該記憶手段に記
憶された道路データを用いて案内情報を出力する経路案
内処理部とを有し、前記記憶手段は、道路データとし
て、該道路データの少なくとも１つの交差点に接続する
道路への接続に関する情報、及び該道路を表示するため
の座標に関する情報を格納し、前記経路案内処理部は、
前記道路データに格納された前記接続に関する情報に基
づき経路を探索し、該探索された経路と前記道路データ
に格納された道路を表示するための座標に関する情報に
基づき経路を表示するので、道路データを経路の探索と
道路の表示に共用することができ、記憶手段に格納する
データの量を大幅に削減することができると共に、交差
点に接続する道路への接続に関する情報に基づき経路の
探索を行うことにより、効率的、かつ高速に経路の探索
を行うことができる。 【００１２】 【発明の実施の形態】以下、本発明の実施の形態を図面
を参照しつつ説明する。図１は本発明に係るナビゲーシ
ョン装置に適用される１実施例システム構成を示す図、
図２は道路網の例を示す図、図３は交差点データの例を
示す図、図４は道路データの例を示す図、図５はノード
データの例を示す図、図６は経路探索処理の流れを説明
するための図である。 【００１３】図１において、１は交差点データ、２は道
路データ、３はノードデータ、４は経路探索処理部、５
は交差点列及びノード列生成部、６は交差点列及びノー
ド列データ、７はナビゲーション部を示す。なお、交差
点データ１、道路データ２、及びノードデータ３は記憶
装置に格納され、経路探索処理部４からナビゲーション
部７により案内情報を出力する経路案内処理部を構成し
ている。経路探索処理部４は、右左折禁止等の進入禁止
道路を除き交差点から周囲道路を検索する周囲道路検索
サブルーチン、道路幅の広狭、案内の要否その他最適経
路を演算するのに必要な条件を設定する最適経路条件設
定サブルーチン、経路探索の終了を判定する終了条件サ
ブルーチンを有し、指定された出発地から目的地までの
最適経路を探索するものである。交差点列及びノード列
生成部５は、経路探索処理部４により最適経路が探索さ
れると、その経路に沿った交差点列及びノード列データ
６を生成するものであり、この交差点列及びノード列デ
ータ６によりナビゲーション（案内情報の出力）を行う
のがナビゲーション部７である。従って、ナビゲーショ
ン部７は、データ処理手段、表示や音声の出力手段を有
し、コース走行の所定の地点で交差点列及びノード列デ
ータ６を読み出し、表示出力や音声出力によりコース案
内を行う。 【００１４】道路のネットワークデータは、道路のネッ
トワークが例えば図２に示すような交差点番号Ｉ〜IV、
道路番号○１〜○８からなるものとした場合、交差点デ
ータについては図３、道路データについては図４、ノー
ドデータについては図５に示すようなデータ構成となっ
ている。 【００１５】すなわち、交差点データは、図３に示すよ
うに交差点番号Ｉ〜IVに対応して交差点名、当該交差点
が始点となっている道路のうち一番番号の小さい道路番
号、当該交差点が終点となっている道路のうち一番番号
の小さい道路番号、信号の有無からなる。 【００１６】また、道路データは、図４に示すように道
路番号○１〜○８に対応して交差点番号による始点、終
点、同じ始点を持つ道路のうち番号が次のもの、同じ終
点を持つ道路のうち番号が次のもの、道路の太さ、禁止
情報、案内不要情報、写真番号、ノード数、ノード列デ
ータの先頭アドレス、長さ等からなる。 【００１７】そして、ノードデータは、図５に示すよう
に東経、北緯、属性等からなり、道路データから明らか
なように道路番号の単位は複数個のノードからなる。す
なわち、ノードデータは道路上の１地点に関するデータ
であり、ノード間を接続するものをアークと呼ぶと、複
数のノード列のそれぞれの間をアークで接続することに
よって道路が表現される。例えば道路番号○１に関して
見ると、道路データよりノード数１５からなりノードデ
ータの先頭アドレスが１００であることから、道路番号
○１は、１００から１１４までのアドレスのノードデー
タで構成されることになる。 【００１８】これらのネットワークデータによると、例
えば交差点番号Ｉに着目した場合、ここを始点とするコ
ースでは、まず、交差点データの始点情報から道路番号
○１、次にこの道路番号○１に関する道路データの「同
じ始点を持つ道路のうち番号が次のもの」から道路番号
○７が検索される。そして、道路番号○７における同様
の情報では、逆に道路番号○１であることから周囲道路
として他の道路番号のものはないことが判断できる。こ
れは、終点に関しても同様である。また、道路データに
おける道路番号○５では、道路番号○６が禁止になって
いることから、図２に示すネットワークの交差点番号IV
において、道路番号○５から○６へは右左折禁止等のた
め進入できず、進入可能な道路は道路番号○８だけとな
る。従って、この道路番号○８への進入は案内不要とな
る。このように特に道路データでは、右左折禁止等の進
入禁止の道路番号と案内不要の道路番号をもっているこ
とにより、情報記憶の容量を少なくし、また経路探索を
容易に行えるようにしている。 【００１９】次に上記のネットワークデータにより経路
探索する場合の処理の流れを図６により説明する。ここ
でＬ(c) は距離、Ｆ(c) はフラグ、Ｒ(c) は通過してき
た道路番号、ｓ0 ，ｓ1 は出発地の両隣りの交差点番
号、ｅ0 ，ｅ1 は目的地の両隣りの交差点番号である。
また、ｃは交差点番号、フラグＦ(c) は「０」が未探
索、「１」が探索中、「２」が探索終了を示す。 【００２０】○１ 全ての交差点について 距離Ｌ(c) に無限大（∞） フラグＦ(c) に「０」（未探索） にセットする。この初期設定によりまず全ての交差点が
未探索となり、出発地からの距離が無限大となる。 【００２１】○２ 出発地の両隣りの交差点番号ｓ0 ，
ｓ1 に対応する距離Ｌ（ｓ0 ），Ｌ（ｓ1 ）に出発地か
らの距離を入れ、さらに出発地の両隣りの交差点番号ｓ
0 ，ｓ1 に対応するフラグＦ（ｓ0 ），Ｆ（ｓ1 ）にそ
れぞれ「１」、通過してきた道路番号Ｒ(c) に出発地か
らの道路番号をセットする。 【００２２】○３ フラグＦが「２」でなく且つ距離Ｌ
(c) が最小となる交差点番号ｃ0 を検索する。 【００２３】○４ 周囲道路検索サブルーチンを実行
し、交差点番号ｃ0 を始点とする周囲道路を検索する。 【００２４】○５ 周囲道路があるか否かを調べる。 【００２５】ＹＥＳの場合には次の処理○６に移り、Ｎ
Ｏの場合には処理○１１に移る。 【００２６】○６ 最適経路条件設定サブルーチンを実
行し、最適経路を探索するための道路状況その他の条件
を設定する。 【００２７】○７ その道路の終点の交差点番号を
ｃ1 、道路の長さをｌとする。 【００２８】○８ その道路の終点の交差点までの距離
Ｐを計算する。 【００２９】Ｐ＝Ｌ（ｃ0 ）＋ｌを計算する。 【００３０】ここでＬ（ｃ0 ）は出発地から交差点番号
ｃ0 までの距離であり、Ｐは交差点番号ｃ0 からその道
路（探索中の道路）を通って終点の交差点番号ｃ1 まで
の距離となる。 【００３１】○９ Ｐ＜Ｌ（ｃ1 ）で且つＦ（ｃ1 ）≠
２か否かを調べる。 【００３２】ＹＥＳの場合には次の処理○１０に移り、
ＮＯの場合には処理○４に戻る。 【００３３】○１０ 出発地から探索中の交差点番号ｃ
1 までの距離Ｌ（ｃ1 ）をＰ、その交差点番号ｃ1 のフ
ラグＦ（ｃ1 ）を「１」、交差点番号ｃ1 に至るまでに
通過してきた道路番号Ｒ（ｃ1 ）をその探索中の道路番
号とする。 【００３４】○１１ 処理○５においてＮＯの場合には
Ｆ（ｃ0 ）を「２」にセットする。 【００３５】○１２ 終了条件確認サブルーチンを実行
する。 【００３６】○１３ 処理終了か否かを調べ、ＮＯの場
合には処理○３に戻り、ＹＥＳの場合には処理を終了と
する。 【００３７】以上の処理を行うことによりそれぞれの交
差点番号に対応して出発地から当該交差点番号に至る最
適コースの道路番号がそれぞれ交差点番号毎に設定され
る。図７は周囲道路検索サブルーチンの処理の流れを説
明するための図、図８は最適経路条件設定サブルーチン
の処理の流れを説明するための図、図９は終了条件確認
サブルーチンの処理の流れを説明するための図である。 【００３８】上記処理○４の周囲道路検索サブルーチン
は、図７に示す処理を行うものである。すなわち、 ○１ 周囲道路の検索が１回目か否かを調べる。 【００３９】ＹＥＳの場合には処理○２に移り、ＮＯの
場合には処理○６に移る。 【００４０】○２ 図３に示す交差点データから現在い
る交差点ｃ0 が始点となっている道路番号を取り出し記
憶する。 【００４１】○３ 図４に示す道路データを参照して探
索中の当該交差点ｃ0 にくる道路番号における禁止道路
を取り出す。 【００４２】○４ 今取り出した道路が禁止道路か否か
を調べる。 【００４３】ＹＥＳの場合には処理○６に移り、ＮＯの
場合には次の処理○５に移る。 【００４４】○５ 今取り出した道路を周囲道路として
記憶し、リターンする（図６の処理○５へ移る）。 【００４５】○６ 道路データから前に探索した道路と
同じ始点を持ち、番号が次の道路番号を取り出す。 【００４６】○７ 最初探索した道路と今取り出した道
路が同じか否かを調べる。 【００４７】ＹＥＳの場合には次の処理○８に移り、Ｎ
Ｏの場合には処理○３に戻る。 【００４８】○８ 周囲道路なしと判定しリターンす
る。 【００４９】また、上記図６に示す処理○６の最適経路
条件設定サブルーチンは、図８に示すような処理を行う
ものである。すなわち、 ○１ 道路データから周囲道路の大きさＤと長さｌを読
み込む。 【００５０】○２ 周囲道路の大きさＤが１以下である
か否かを調べる。 【００５１】ＹＥＳの場合には次の処理○３に移り、Ｎ
Ｏの場合には処理○４に移る。 【００５２】○３ 長さｌをａ倍した長さをｌとする。
すなわち、Ｄが１より大きい道路を通常の広い道路と
し、１以下の道路を細い道路とすると、細い道路は通常
の道路に対してａ倍の距離の評価としている。従って、
ａは１より大きい数である。 【００５３】○４ 道路データから現在探索中の交差点
へ通過してきた道路の案内不要データを読み込む。 【００５４】○５ 案内不要データと一致する周囲道路
があるか否かを調べる。 【００５５】ＹＥＳの場合にはリターンし、ＮＯの場合
には次の処理○６に移る。 【００５６】○６ さらに長さｌにｂｍを加算した値を
新たな長さｌとしリターンする。すなわち、案内不要の
交差点に対して、右左折等の案内を要する交差点は、距
離に換算してｂｍ加算した評価としている。 【００５７】終了条件確認サブルーチンでは、図９に示
すように探索対象の交差点番号ｃ0と目的等の両隣りの
交差点番号との一致を調べ、一致したことを条件に例え
ば終了フラグを設定する。 【００５８】図１０は交差点列及びノード列のデータ構
造の例を示す図、図１１は交差点列及びノード列取り出
し処理の流れを説明するための図である。 【００５９】上記のように本発明の経路探索では、周囲
道路の大きさや道路の案内要／不要等の走行条件を考慮
して交差点間の距離に重み付けを行い、最短経路を探索
する。その結果、各交差点に対応して最適コースに沿っ
た道路番号情報が得られる。従って、この探索結果に従
って図１０に示す処理フローに従って交差点列及びノー
ド列のデータを生成することができる。 【００６０】○１ 探索が終了した交差点番号をメモリ
に記憶する。 【００６１】○２ その交差点にきた道路番号の始点を
メモリに記憶する。 【００６２】○３ その交差点が出発地の両隣りの交差
点か否かを調べる。 【００６３】ＹＥＳの場合には次の処理○４に移り、Ｎ
Ｏの場合には処理○２に戻る。 【００６４】○４ 記憶した交差点番号列の前と後に出
発地番号、目的地番号を加えて交差点列とする。 【００６５】○５ 道路データを参照して交差点間のノ
ード列を取り出し、ノード列をつくる。 【００６６】○６ 案内不要データを使い交差点列から
案内不要となる交差点を除く。 【００６７】このようにして経路探索の結果から生成さ
れる交差点列及びノード列データの例を示したのが図１
１である。例えば交差点列データは、図１１（ａ）に示
すように交差点名、交差点番号、その交差点の特徴風景
等を撮影した写真番号、曲がる角度、距離等の情報から
なり、また、ノード列データは、同図（ｂ）に示すよう
にそのノード位置を表す東経、北緯、そして交差点番
号、属性、角度、距離等の情報からなる。しかも、これ
らのデータは、案内不要の交差点を除いた、案内を要す
る交差点のみのデータからなる。従って、ナビゲーショ
ンでは、所定の位置に対応してこのデータを順次読み出
して出力すればよい。 【００６８】上記のように経路探索時は、右左折禁止デ
ータをチェックしながら探索し、右左折禁止が入らない
コースを探索する。 【００６９】なお、本発明は、上記の実施例に限定され
るものではなく、種々の変形が可能である。例えば上記
の実施例では出発地から経路探索をスタートさせたが、
目的地から経路探索をスタートさせるようにしてもよ
い。また、出発地から経路探索をスタートして目的地に
達したところで処理終了にしたが、全てのフラグＦ
（ｃ）が２になるまで、すなわち、全ての交差点につい
て経路探索を行うようにしてもよい。特に目的地からこ
の経路探索を行うと、全ての交差点から目的地までの最
適コース情報が作成されることになるので、途中でコー
スから外れた場合にも、経路探索を再度行うことなく、
最寄りの交差点から交差点列及びノード列を作成するこ
とができる。 【００７０】以上の説明から明らかなように、本実施例
によれば、交差点データ、道路データ及びノード列デー
タを予めＣＤーＲＯＭ等の記憶手段に格納しておき、経
路探索をする前にこれらのデータをＲＡＭ等に読み取っ
て右左折禁止をチェックしながら経路探索を行うので、
経路探索を高速化することができる。また、右左折禁止
データを道路データに含めて持っているためデータ量を
少なくすることができ、記憶容量を少なくすることがで
きる。さらには、案内不要データをもちこのデータによ
り直進か右左折かの判断するので、最短時間経路探索を
少ないデータ量で行うことができる。しかも、直進する
交差点を案内不要データから認識して交差点列から除
き、右左折する交差点のみのデータとすることが簡単な
処理で行える。
までの最短経路を探索するナビゲーション装置に関す
る。 【０００２】 【従来の技術】ナビゲーション装置は、地理の不案内な
運転者に対して目的地までコース案内を行うものであ
り、近年、このナビゲーション装置の開発が盛んに行わ
れている。 【０００３】ナビゲーション装置は、予め走行前に出発
地及び目的地を入力することによって出発地から目的地
までのコースを設定し、その設定されたコースに従って
ナビゲーションを行うものである。ナビゲーションで
は、コースを指示する場合、ＣＲＴ画面に地図を表示し
その上にコースを重ねて表示したり、また、或るもの
は、予め設定されたコースに従って次に曲がるべき交差
点に関する情報として、次に曲がるべき交差点までの距
離を数字やグラフ、特徴的な写真で表示したりさらには
音声出力も併用するものもある。 【０００４】道路網にあっては、一般に出発地から目的
地までの間に複数のコースが存在するのが普通である。
そのため、ナビゲーション装置において、出発地及び目
的地が入力されると、その間における最短時間或いは最
短距離のコース（最短コース）を探索する経路探索の手
法を採用する試みがなされている。その１つとして、例
えば図１２に示すように四叉路の交差点の場合には、右
左折、直進、Ｕターンを表現するために８つのノードと
１６本の有向リンクで交差点を表し、また、交差点相互
を接続する道路枝は２本の有向リンクで表す方法（例え
ば特開昭６２−８２３１６号公報）が報告されている。
もう１つは、最短コースを検索する毎に車両の進行が禁
止されている道路を含んでいないかをチェックし、進行
禁止の道路を含む最短コースは排除し、他の交差点を通
る最短コースを検索する方法（例えば特開昭６２−９１
８１１号公報）が報告されている。 【０００５】 【発明が解決しようとする課題】しかしながら、上記前
者の方法は、交差点での右左折禁止を全て有向リンクで
表現しているので、データ量が多くなり記憶容量が多く
なるという問題がある。また、後者の方法は、交差点で
の右左折禁止をネットワークデータとは別にして交差点
番号でもっているので、経路探索時の検索に要する処理
が多くなり、処理速度が遅くなるという問題がある。 【０００６】本発明は、上記の問題点を解決するもので
あって、記憶データ量を少なくし右左折禁止データや案
内不要データの判断も含めて高速に経路探索することが
できるナビゲーション装置を提供することを目的とする
ものである。 【０００７】 【課題を解決するための手段】そのために本発明は、ナ
ビゲーション装置において、始点から終点で表される道
路単位で道路データを格納した記憶手段と、該記憶手段
に記憶された道路データを用いて案内情報を出力する経
路案内処理部とを有し、前記記憶手段は、道路データと
して、該道路における情報、及び該道路データの始点ま
たは終点に接続する道路に関する情報を格納し、前記経
路案内処理部は、前記道路データに格納された情報に基
づき案内情報を出力することを特徴とし、前記経路案内
処理部は、前記道路データの該道路における情報及び前
記接続する道路に関する情報に基づき経路を探索して、
該探索した経路に基づき案内情報を出力することを特徴
とするものである。 【０００８】また、交差点から交差点で表される道路単
位で道路データを格納した記憶手段と、該記憶手段に記
憶された道路データを用いて案内情報を出力する経路案
内処理部とを有し、前記記憶手段は、道路データとし
て、該道路データの少なくとも１つの交差点に接続する
道路への接続に関する情報、及び該道路を表示するため
の座標に関する情報を格納し、前記経路案内処理部は、
前記道路データに格納された前記接続に関する情報に基
づき経路を探索し、該探索された経路と前記道路データ
に格納された道路を表示するための座標に関する情報に
基づき経路を表示することを特徴とし、前記記憶手段
は、道路データとして、経路探索を行うための情報と共
に道路地図を表示するための座標列に関する情報を格納
し、前記経路案内処理部は、前記道路データの経路探索
を行うための情報に基づき経路を探索し、前記座標列に
関する情報に基づき前記探索された経路と前記道路地図
を表示することを特徴とするものである。 【０００９】 【作用及び発明の効果】本発明のナビゲーション装置で
は、端点から端点で表される道路単位で道路データを格
納した記憶手段と、該記憶手段に記憶された道路データ
を用いて案内情報を出力する経路案内処理部とを有し、
前記記憶手段は、道路データとして、該道路における情
報、及び該道路データの少なくとも１つの端点に接続す
る道路への接続に関する情報を格納し、前記経路案内処
理部は、前記道路データに格納された情報に基づき案内
情報を出力するので、道路単位で道路における情報、及
び始点または終点に接続する道路に関する情報に基づき
案内情報の出力を行い、処理を簡素化できる。 【００１０】しかも、前記経路案内処理部は、前記道路
データの該道路における情報及び前記接続する道路に関
する情報に基づき経路を探索して、該探索した経路に基
づき案内情報を出力するので、接続する道路に関する情
報として、右左折禁止情報や案内不要情報を設定するこ
とにより、経路の探索や案内情報の出力で無駄な探索処
理や案内処理をなくすことができ、処理の高速化を図る
ことができる。 【００１１】また、交差点から交差点で表される道路単
位で道路データを格納した記憶手段と、該記憶手段に記
憶された道路データを用いて案内情報を出力する経路案
内処理部とを有し、前記記憶手段は、道路データとし
て、該道路データの少なくとも１つの交差点に接続する
道路への接続に関する情報、及び該道路を表示するため
の座標に関する情報を格納し、前記経路案内処理部は、
前記道路データに格納された前記接続に関する情報に基
づき経路を探索し、該探索された経路と前記道路データ
に格納された道路を表示するための座標に関する情報に
基づき経路を表示するので、道路データを経路の探索と
道路の表示に共用することができ、記憶手段に格納する
データの量を大幅に削減することができると共に、交差
点に接続する道路への接続に関する情報に基づき経路の
探索を行うことにより、効率的、かつ高速に経路の探索
を行うことができる。 【００１２】 【発明の実施の形態】以下、本発明の実施の形態を図面
を参照しつつ説明する。図１は本発明に係るナビゲーシ
ョン装置に適用される１実施例システム構成を示す図、
図２は道路網の例を示す図、図３は交差点データの例を
示す図、図４は道路データの例を示す図、図５はノード
データの例を示す図、図６は経路探索処理の流れを説明
するための図である。 【００１３】図１において、１は交差点データ、２は道
路データ、３はノードデータ、４は経路探索処理部、５
は交差点列及びノード列生成部、６は交差点列及びノー
ド列データ、７はナビゲーション部を示す。なお、交差
点データ１、道路データ２、及びノードデータ３は記憶
装置に格納され、経路探索処理部４からナビゲーション
部７により案内情報を出力する経路案内処理部を構成し
ている。経路探索処理部４は、右左折禁止等の進入禁止
道路を除き交差点から周囲道路を検索する周囲道路検索
サブルーチン、道路幅の広狭、案内の要否その他最適経
路を演算するのに必要な条件を設定する最適経路条件設
定サブルーチン、経路探索の終了を判定する終了条件サ
ブルーチンを有し、指定された出発地から目的地までの
最適経路を探索するものである。交差点列及びノード列
生成部５は、経路探索処理部４により最適経路が探索さ
れると、その経路に沿った交差点列及びノード列データ
６を生成するものであり、この交差点列及びノード列デ
ータ６によりナビゲーション（案内情報の出力）を行う
のがナビゲーション部７である。従って、ナビゲーショ
ン部７は、データ処理手段、表示や音声の出力手段を有
し、コース走行の所定の地点で交差点列及びノード列デ
ータ６を読み出し、表示出力や音声出力によりコース案
内を行う。 【００１４】道路のネットワークデータは、道路のネッ
トワークが例えば図２に示すような交差点番号Ｉ〜IV、
道路番号○１〜○８からなるものとした場合、交差点デ
ータについては図３、道路データについては図４、ノー
ドデータについては図５に示すようなデータ構成となっ
ている。 【００１５】すなわち、交差点データは、図３に示すよ
うに交差点番号Ｉ〜IVに対応して交差点名、当該交差点
が始点となっている道路のうち一番番号の小さい道路番
号、当該交差点が終点となっている道路のうち一番番号
の小さい道路番号、信号の有無からなる。 【００１６】また、道路データは、図４に示すように道
路番号○１〜○８に対応して交差点番号による始点、終
点、同じ始点を持つ道路のうち番号が次のもの、同じ終
点を持つ道路のうち番号が次のもの、道路の太さ、禁止
情報、案内不要情報、写真番号、ノード数、ノード列デ
ータの先頭アドレス、長さ等からなる。 【００１７】そして、ノードデータは、図５に示すよう
に東経、北緯、属性等からなり、道路データから明らか
なように道路番号の単位は複数個のノードからなる。す
なわち、ノードデータは道路上の１地点に関するデータ
であり、ノード間を接続するものをアークと呼ぶと、複
数のノード列のそれぞれの間をアークで接続することに
よって道路が表現される。例えば道路番号○１に関して
見ると、道路データよりノード数１５からなりノードデ
ータの先頭アドレスが１００であることから、道路番号
○１は、１００から１１４までのアドレスのノードデー
タで構成されることになる。 【００１８】これらのネットワークデータによると、例
えば交差点番号Ｉに着目した場合、ここを始点とするコ
ースでは、まず、交差点データの始点情報から道路番号
○１、次にこの道路番号○１に関する道路データの「同
じ始点を持つ道路のうち番号が次のもの」から道路番号
○７が検索される。そして、道路番号○７における同様
の情報では、逆に道路番号○１であることから周囲道路
として他の道路番号のものはないことが判断できる。こ
れは、終点に関しても同様である。また、道路データに
おける道路番号○５では、道路番号○６が禁止になって
いることから、図２に示すネットワークの交差点番号IV
において、道路番号○５から○６へは右左折禁止等のた
め進入できず、進入可能な道路は道路番号○８だけとな
る。従って、この道路番号○８への進入は案内不要とな
る。このように特に道路データでは、右左折禁止等の進
入禁止の道路番号と案内不要の道路番号をもっているこ
とにより、情報記憶の容量を少なくし、また経路探索を
容易に行えるようにしている。 【００１９】次に上記のネットワークデータにより経路
探索する場合の処理の流れを図６により説明する。ここ
でＬ(c) は距離、Ｆ(c) はフラグ、Ｒ(c) は通過してき
た道路番号、ｓ0 ，ｓ1 は出発地の両隣りの交差点番
号、ｅ0 ，ｅ1 は目的地の両隣りの交差点番号である。
また、ｃは交差点番号、フラグＦ(c) は「０」が未探
索、「１」が探索中、「２」が探索終了を示す。 【００２０】○１ 全ての交差点について 距離Ｌ(c) に無限大（∞） フラグＦ(c) に「０」（未探索） にセットする。この初期設定によりまず全ての交差点が
未探索となり、出発地からの距離が無限大となる。 【００２１】○２ 出発地の両隣りの交差点番号ｓ0 ，
ｓ1 に対応する距離Ｌ（ｓ0 ），Ｌ（ｓ1 ）に出発地か
らの距離を入れ、さらに出発地の両隣りの交差点番号ｓ
0 ，ｓ1 に対応するフラグＦ（ｓ0 ），Ｆ（ｓ1 ）にそ
れぞれ「１」、通過してきた道路番号Ｒ(c) に出発地か
らの道路番号をセットする。 【００２２】○３ フラグＦが「２」でなく且つ距離Ｌ
(c) が最小となる交差点番号ｃ0 を検索する。 【００２３】○４ 周囲道路検索サブルーチンを実行
し、交差点番号ｃ0 を始点とする周囲道路を検索する。 【００２４】○５ 周囲道路があるか否かを調べる。 【００２５】ＹＥＳの場合には次の処理○６に移り、Ｎ
Ｏの場合には処理○１１に移る。 【００２６】○６ 最適経路条件設定サブルーチンを実
行し、最適経路を探索するための道路状況その他の条件
を設定する。 【００２７】○７ その道路の終点の交差点番号を
ｃ1 、道路の長さをｌとする。 【００２８】○８ その道路の終点の交差点までの距離
Ｐを計算する。 【００２９】Ｐ＝Ｌ（ｃ0 ）＋ｌを計算する。 【００３０】ここでＬ（ｃ0 ）は出発地から交差点番号
ｃ0 までの距離であり、Ｐは交差点番号ｃ0 からその道
路（探索中の道路）を通って終点の交差点番号ｃ1 まで
の距離となる。 【００３１】○９ Ｐ＜Ｌ（ｃ1 ）で且つＦ（ｃ1 ）≠
２か否かを調べる。 【００３２】ＹＥＳの場合には次の処理○１０に移り、
ＮＯの場合には処理○４に戻る。 【００３３】○１０ 出発地から探索中の交差点番号ｃ
1 までの距離Ｌ（ｃ1 ）をＰ、その交差点番号ｃ1 のフ
ラグＦ（ｃ1 ）を「１」、交差点番号ｃ1 に至るまでに
通過してきた道路番号Ｒ（ｃ1 ）をその探索中の道路番
号とする。 【００３４】○１１ 処理○５においてＮＯの場合には
Ｆ（ｃ0 ）を「２」にセットする。 【００３５】○１２ 終了条件確認サブルーチンを実行
する。 【００３６】○１３ 処理終了か否かを調べ、ＮＯの場
合には処理○３に戻り、ＹＥＳの場合には処理を終了と
する。 【００３７】以上の処理を行うことによりそれぞれの交
差点番号に対応して出発地から当該交差点番号に至る最
適コースの道路番号がそれぞれ交差点番号毎に設定され
る。図７は周囲道路検索サブルーチンの処理の流れを説
明するための図、図８は最適経路条件設定サブルーチン
の処理の流れを説明するための図、図９は終了条件確認
サブルーチンの処理の流れを説明するための図である。 【００３８】上記処理○４の周囲道路検索サブルーチン
は、図７に示す処理を行うものである。すなわち、 ○１ 周囲道路の検索が１回目か否かを調べる。 【００３９】ＹＥＳの場合には処理○２に移り、ＮＯの
場合には処理○６に移る。 【００４０】○２ 図３に示す交差点データから現在い
る交差点ｃ0 が始点となっている道路番号を取り出し記
憶する。 【００４１】○３ 図４に示す道路データを参照して探
索中の当該交差点ｃ0 にくる道路番号における禁止道路
を取り出す。 【００４２】○４ 今取り出した道路が禁止道路か否か
を調べる。 【００４３】ＹＥＳの場合には処理○６に移り、ＮＯの
場合には次の処理○５に移る。 【００４４】○５ 今取り出した道路を周囲道路として
記憶し、リターンする（図６の処理○５へ移る）。 【００４５】○６ 道路データから前に探索した道路と
同じ始点を持ち、番号が次の道路番号を取り出す。 【００４６】○７ 最初探索した道路と今取り出した道
路が同じか否かを調べる。 【００４７】ＹＥＳの場合には次の処理○８に移り、Ｎ
Ｏの場合には処理○３に戻る。 【００４８】○８ 周囲道路なしと判定しリターンす
る。 【００４９】また、上記図６に示す処理○６の最適経路
条件設定サブルーチンは、図８に示すような処理を行う
ものである。すなわち、 ○１ 道路データから周囲道路の大きさＤと長さｌを読
み込む。 【００５０】○２ 周囲道路の大きさＤが１以下である
か否かを調べる。 【００５１】ＹＥＳの場合には次の処理○３に移り、Ｎ
Ｏの場合には処理○４に移る。 【００５２】○３ 長さｌをａ倍した長さをｌとする。
すなわち、Ｄが１より大きい道路を通常の広い道路と
し、１以下の道路を細い道路とすると、細い道路は通常
の道路に対してａ倍の距離の評価としている。従って、
ａは１より大きい数である。 【００５３】○４ 道路データから現在探索中の交差点
へ通過してきた道路の案内不要データを読み込む。 【００５４】○５ 案内不要データと一致する周囲道路
があるか否かを調べる。 【００５５】ＹＥＳの場合にはリターンし、ＮＯの場合
には次の処理○６に移る。 【００５６】○６ さらに長さｌにｂｍを加算した値を
新たな長さｌとしリターンする。すなわち、案内不要の
交差点に対して、右左折等の案内を要する交差点は、距
離に換算してｂｍ加算した評価としている。 【００５７】終了条件確認サブルーチンでは、図９に示
すように探索対象の交差点番号ｃ0と目的等の両隣りの
交差点番号との一致を調べ、一致したことを条件に例え
ば終了フラグを設定する。 【００５８】図１０は交差点列及びノード列のデータ構
造の例を示す図、図１１は交差点列及びノード列取り出
し処理の流れを説明するための図である。 【００５９】上記のように本発明の経路探索では、周囲
道路の大きさや道路の案内要／不要等の走行条件を考慮
して交差点間の距離に重み付けを行い、最短経路を探索
する。その結果、各交差点に対応して最適コースに沿っ
た道路番号情報が得られる。従って、この探索結果に従
って図１０に示す処理フローに従って交差点列及びノー
ド列のデータを生成することができる。 【００６０】○１ 探索が終了した交差点番号をメモリ
に記憶する。 【００６１】○２ その交差点にきた道路番号の始点を
メモリに記憶する。 【００６２】○３ その交差点が出発地の両隣りの交差
点か否かを調べる。 【００６３】ＹＥＳの場合には次の処理○４に移り、Ｎ
Ｏの場合には処理○２に戻る。 【００６４】○４ 記憶した交差点番号列の前と後に出
発地番号、目的地番号を加えて交差点列とする。 【００６５】○５ 道路データを参照して交差点間のノ
ード列を取り出し、ノード列をつくる。 【００６６】○６ 案内不要データを使い交差点列から
案内不要となる交差点を除く。 【００６７】このようにして経路探索の結果から生成さ
れる交差点列及びノード列データの例を示したのが図１
１である。例えば交差点列データは、図１１（ａ）に示
すように交差点名、交差点番号、その交差点の特徴風景
等を撮影した写真番号、曲がる角度、距離等の情報から
なり、また、ノード列データは、同図（ｂ）に示すよう
にそのノード位置を表す東経、北緯、そして交差点番
号、属性、角度、距離等の情報からなる。しかも、これ
らのデータは、案内不要の交差点を除いた、案内を要す
る交差点のみのデータからなる。従って、ナビゲーショ
ンでは、所定の位置に対応してこのデータを順次読み出
して出力すればよい。 【００６８】上記のように経路探索時は、右左折禁止デ
ータをチェックしながら探索し、右左折禁止が入らない
コースを探索する。 【００６９】なお、本発明は、上記の実施例に限定され
るものではなく、種々の変形が可能である。例えば上記
の実施例では出発地から経路探索をスタートさせたが、
目的地から経路探索をスタートさせるようにしてもよ
い。また、出発地から経路探索をスタートして目的地に
達したところで処理終了にしたが、全てのフラグＦ
（ｃ）が２になるまで、すなわち、全ての交差点につい
て経路探索を行うようにしてもよい。特に目的地からこ
の経路探索を行うと、全ての交差点から目的地までの最
適コース情報が作成されることになるので、途中でコー
スから外れた場合にも、経路探索を再度行うことなく、
最寄りの交差点から交差点列及びノード列を作成するこ
とができる。 【００７０】以上の説明から明らかなように、本実施例
によれば、交差点データ、道路データ及びノード列デー
タを予めＣＤーＲＯＭ等の記憶手段に格納しておき、経
路探索をする前にこれらのデータをＲＡＭ等に読み取っ
て右左折禁止をチェックしながら経路探索を行うので、
経路探索を高速化することができる。また、右左折禁止
データを道路データに含めて持っているためデータ量を
少なくすることができ、記憶容量を少なくすることがで
きる。さらには、案内不要データをもちこのデータによ
り直進か右左折かの判断するので、最短時間経路探索を
少ないデータ量で行うことができる。しかも、直進する
交差点を案内不要データから認識して交差点列から除
き、右左折する交差点のみのデータとすることが簡単な
処理で行える。
【図面の簡単な説明】
【図１】 本発明に係るナビゲーション装置に適用され
る１実施例システム構成を示す図である。 【図２】 道路網の例を示す図の例を示す図である。 【図３】 交差点データの例を示す図である。 【図４】 道路データの例を示す図である。 【図５】 ノードデータの例を示す図である。 【図６】 経路探索処理の流れを説明するための図であ
る。 【図７】 周囲道路検索サブルーチンの処理の流れを説
明するための図である。 【図８】 最適経路条件設定サブルーチンの処理の流れ
を説明するための図である。 【図９】 終了条件確認サブルーチンの処理の流れを説
明するための図である。 【図１０】 交差点列及びノード列のデータ構造の例を
示す図である。 【図１１】 交差点列及びノード列取り出し処理の流れ
を説明するための図である。 【図１２】 ノードと有向リンクで交差点情報を表した
従来の経路探索方法の例を説明するための図である。 【符号の説明】 １…交差点データ、２…道路データ、３…ノードデー
タ、４…経路探索処理部、５…交差点列及びノード列生
成部、６…交差点列及びノード列データ、７…ナビゲー
ション部。
る１実施例システム構成を示す図である。 【図２】 道路網の例を示す図の例を示す図である。 【図３】 交差点データの例を示す図である。 【図４】 道路データの例を示す図である。 【図５】 ノードデータの例を示す図である。 【図６】 経路探索処理の流れを説明するための図であ
る。 【図７】 周囲道路検索サブルーチンの処理の流れを説
明するための図である。 【図８】 最適経路条件設定サブルーチンの処理の流れ
を説明するための図である。 【図９】 終了条件確認サブルーチンの処理の流れを説
明するための図である。 【図１０】 交差点列及びノード列のデータ構造の例を
示す図である。 【図１１】 交差点列及びノード列取り出し処理の流れ
を説明するための図である。 【図１２】 ノードと有向リンクで交差点情報を表した
従来の経路探索方法の例を説明するための図である。 【符号の説明】 １…交差点データ、２…道路データ、３…ノードデー
タ、４…経路探索処理部、５…交差点列及びノード列生
成部、６…交差点列及びノード列データ、７…ナビゲー
ション部。
─────────────────────────────────────────────────────
フロントページの続き
(72)発明者 遠山 康博
愛知県安城市藤井町高根10番地 アイシ
ン・エィ・ダブリュ株式会社内
(56)参考文献 特開 平１−136300（ＪＰ，Ａ)
特開 平１−138409（ＪＰ，Ａ)
(58)調査した分野(Int.Cl.6，ＤＢ名)
G01C 21/00
G08G 1/0969
G09B 29/00
Claims (1)
- (57)【特許請求の範囲】 １．端点から端点で表される道路単位で道路データを格
納した記憶手段と、 該記憶手段に記憶された道路データを用いて案内情報を
出力する経路案内処理部とを有し、 前記記憶手段は、道路データとして、該道路における情
報、及び該道路データの少なくとも１つの端点に接続す
る道路への接続に関する情報を格納し、 前記経路案内処理部は、前記道路データに格納された情
報に基づき案内情報を出力することを特徴とするナビゲ
ーション装置。 ２．前記経路案内処理部は、前記道路データの該道路に
おける情報及び前記接続する道路に関する情報に基づき
経路を探索して、該探索した経路に基づき案内情報を出
力することを特徴とする請求項１記載のナビゲーション
装置。 ３．交差点から交差点で表される道路単位で道路データ
を格納した記憶手段と、 該記憶手段に記憶された道路データを用いて案内情報を
出力する経路案内処理部とを有し、 前記記憶手段は、道路データとして、該道路データの少
なくとも１つの交差点に接続する道路への接続に関する
情報、及び該道路を表示するための座標に関する情報を
格納し、 前記経路案内処理部は、前記道路データの前記接続に関
する情報に基づき経路を探索し、該探索された経路と前
記道路を表示するための座標に関する情報に基づき経路
を表示することを特徴とするナビゲーション装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9034957A JP2866358B2 (ja) | 1997-02-19 | 1997-02-19 | ナビゲーション装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9034957A JP2866358B2 (ja) | 1997-02-19 | 1997-02-19 | ナビゲーション装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH09329452A JPH09329452A (ja) | 1997-12-22 |
| JP2866358B2 true JP2866358B2 (ja) | 1999-03-08 |
Family
ID=12428644
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP9034957A Expired - Lifetime JP2866358B2 (ja) | 1997-02-19 | 1997-02-19 | ナビゲーション装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2866358B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2009096074A1 (ja) | 2008-01-28 | 2009-08-06 | Geo Technical Laboratory Co., Ltd. | 経路案内データベースのデータ構造 |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2812361B2 (ja) * | 1987-11-24 | 1998-10-22 | 住友電気工業株式会社 | 車載型ナビゲーションシステム |
| JP2569630B2 (ja) * | 1987-11-24 | 1997-01-08 | ソニー株式会社 | ナビゲータ装置 |
-
1997
- 1997-02-19 JP JP9034957A patent/JP2866358B2/ja not_active Expired - Lifetime
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2009096074A1 (ja) | 2008-01-28 | 2009-08-06 | Geo Technical Laboratory Co., Ltd. | 経路案内データベースのデータ構造 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH09329452A (ja) | 1997-12-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2680318B2 (ja) | ナビゲーション装置 | |
| JP2834952B2 (ja) | 経路探索方法 | |
| US7526492B2 (en) | Data structure of map data, map data storage medium, map data updating method and map data processing apparatus | |
| JP3430602B2 (ja) | 車両の走行経路案内装置 | |
| JP3477329B2 (ja) | ナビゲーション装置 | |
| JP3474380B2 (ja) | ナビゲーション装置および地図データベース装置 | |
| JPH10187033A (ja) | 地図データベース装置 | |
| WO1989006414A1 (en) | Route search method for navigation system | |
| JPH01173299A (ja) | ナビゲーション装置 | |
| JP2569624B2 (ja) | ナビゲータ装置 | |
| JP2696804B2 (ja) | ナビゲーション装置 | |
| JP3341645B2 (ja) | 経路案内装置 | |
| JP2641470B2 (ja) | ナビゲーション装置 | |
| JP2866358B2 (ja) | ナビゲーション装置 | |
| JP3637650B2 (ja) | 車載用ナビゲーション装置 | |
| JP2569630B2 (ja) | ナビゲータ装置 | |
| JP2003344084A (ja) | ナビゲーション装置および交差点案内方法 | |
| JP4133265B2 (ja) | ナビゲーション装置 | |
| JP3502230B2 (ja) | ナビゲーション装置 | |
| JP3244517B2 (ja) | 車載用ナビゲーションシステムの経路探査方法及び地図データ記憶媒体 | |
| JP2878849B2 (ja) | ナビゲ−ションにおける経路探索方法 | |
| JP4460110B2 (ja) | ナビゲーション装置 | |
| JP3766502B2 (ja) | ナビゲーション装置 | |
| JP3577426B2 (ja) | ナビゲーション映像要約方法およびナビゲーション映像要約プログラムを記録した記録媒体 | |
| JP3368722B2 (ja) | 車両用走行案内装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20071218 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20081218 Year of fee payment: 10 |
|
| EXPY | Cancellation because of completion of term | ||
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20081218 Year of fee payment: 10 |