JPH06309595A - ナビゲーション装置 - Google Patents

ナビゲーション装置

Info

Publication number
JPH06309595A
JPH06309595A JP5099806A JP9980693A JPH06309595A JP H06309595 A JPH06309595 A JP H06309595A JP 5099806 A JP5099806 A JP 5099806A JP 9980693 A JP9980693 A JP 9980693A JP H06309595 A JPH06309595 A JP H06309595A
Authority
JP
Japan
Prior art keywords
route
point
destination
search
optimum 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.)
Pending
Application number
JP5099806A
Other languages
English (en)
Inventor
Kenichi Nobe
健一 野辺
Morio Araki
盛雄 荒木
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Pioneer Corp
Original Assignee
Pioneer Electronic Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Pioneer Electronic Corp filed Critical Pioneer Electronic Corp
Priority to JP5099806A priority Critical patent/JPH06309595A/ja
Priority to EP94302998A priority patent/EP0622611B1/en
Priority to US08/233,255 priority patent/US5506774A/en
Priority to DE69419066T priority patent/DE69419066T2/de
Publication of JPH06309595A publication Critical patent/JPH06309595A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/34—Route searching; Route guidance
    • G01C21/3446—Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/34—Route searching; Route guidance
    • G01C21/3453—Special cost functions, i.e. other than distance or default speed limit of road segments
    • G01C21/3461—Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types or segments such as motorways, toll roads or ferries
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/34—Route searching; Route guidance
    • G01C21/3453—Special cost functions, i.e. other than distance or default speed limit of road segments
    • G01C21/3492—Special cost functions, i.e. other than distance or default speed limit of road segments employing speed data or traffic data, e.g. real-time or historical

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Automation & Control Theory (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Navigation (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Traffic Control Systems (AREA)
  • Image Analysis (AREA)

Abstract

(57)【要約】 【目的】 本発明は、現在地点から目的地点までの最適
な経路をより短時間で探索し、更に運転支援を効果的に
行うことのできるナビゲーション装置を提供することを
目的としている。 【構成】 目的地点が設定入力されると、最適経路検索
手段において、予め記憶されている各地点の情報（例え
ば、道路の距離・幅員、渋滞情報など）を用いて現在地
点から目的地点までの種々の経路が評価され、これらの
経路の中で最も評価の優れた経路を最適経路として選択
され、当該選択された最適経路が進行経路として表示さ
れるように作用する。このようにして、最適な経路を効
率よく探索でき、効果的に運転支援を行うことができ
る。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、現在地点、進行経路等
を指示表示して自動車等の移動体の運行を支援するナビ
ゲーション装置に係り、特に、初めに目的地点を設定入
力し、予め入力された地図情報に基づき最適走行経路を
求め、当該経路を誘導表示するナビゲーション装置に関
する。
【０００２】
【従来の技術】自動車等に搭載されているナビゲーショ
ン装置では、自車の現在地点及び進行方向を正確に測位
し、自車の現在地点に対応する地図情報を逐次ディスプ
レイ等により的確かつ迅速に表示するとともに、現在地
点から目的地点までの経路をドライバーに提供すること
が要求されている。
【０００３】従来より、自動車等に搭載されているナビ
ゲーション装置では、入力された目的地点、及び現在地
点から目的地点までの種々の経路の位置情報を用いて、
自車の現在地点から目的地点への方位が最も近い経路を
選択し、現在地点から目的地点までの進行経路を誘導表
示している。
【０００４】図１１に、従来のナビゲーション装置を用
いた場合の経路探索例を示す。図１１において、Ｓは現
在地点、Ｄは目的地点であり、番号１〜６は、それぞれ
自車が通過する交差点である。自車の現在位置から目的
地への方位が最も近い経路を選択する従来のナビゲーシ
ョン装置の場合、目的地点Ｄを入力すると、自車は現在
地点Ｓから交差点３まで直進し、交差点３において右折
し、交差点４において左折し、交差点５において右折
し、交差点６において左折し、目的地点Ｄに到達する経
路を誘導表示し、運転を支援するようにされていた。
【０００５】
【発明が解決しようとする課題】しかしながら、図１２
に示す経路を従来のナビゲーション装置を用いて探索し
た場合、現在地点Ｓと目的地点Ｄとの間に経路が存在し
ないため、無限ループとなり、目的地点Ｄまでの経路が
見いだせない場合がある。すなわち、図１２の場合、現
在地点Ｓにおいて、目的地点Ｄを入力すると、自車は現
在地点Ｓから交差点３まで直進し、交差点３においてＵ
ターンし、交差点１まで直進する。よって、以後交差点
１と交差点３との間を往復するといった移動経路を誘導
表示することとなる。この際、自車がデータの端点に至
る場合、又は自車のすべての進行方向が一度通過した点
で囲まれる場合に、その地点を禁止地点とし、自車が一
つ前の地点に戻るという処理を施すことで上記不都合を
解消することもできる。しかし、図１３に示すように、
目的地点Ｄに至るまで多くの経路を検索しなければなら
ず、処理が複雑であり、多くの検索時間が必要となる。
【０００６】本発明は、このような問題点を解消するた
めになされたもので、現在地点から目的地点までの最適
な経路をより短時間で探索し、更に運転支援を効果的に
行うことのできるナビゲーション装置を提供することを
目的としている。
【０００７】
【課題を解決するための手段】上記目的を達成するため
本発明によるナビゲーション装置は、目的地点を入力
し、自己の現在地点から目的地点までの進行経路の表示
を行うナビゲーション装置において、予め記憶されてい
る各地点の情報を用いて、現在地点から目的地点までの
種々の経路を評価し、最適な経路を探索する最適経路探
索手段を備えていることを特徴としている。
【０００８】
【作用】上記本発明の構成によれば、目的地点が設定入
力されると、最適経路検索手段において、予め記憶され
ている各地点の情報（例えば、道路の距離・幅員、渋滞
情報など）を用いて現在地点から目的地点までの種々の
経路が評価され、これらの経路の中で最も評価の優れた
経路が最適経路として選択され、当該選択された最適経
路が進行経路として表示されるように作用する。このよ
うにして、最適な経路を効率よく探索でき、効果的に運
転支援を行うことができる。
【０００９】
【実施例】以下図面を参照して本発明の実施例を説明す
る。図１に、本発明による車載用ナビゲーション装置の
構成図を示す。同図に示すように、車載用ナビゲーショ
ン装置は、地磁気（地球磁界）に基づいて車両の絶対方
位角度データを出力する方位検出装置である地磁気セン
サ１と、車両の方向変化に伴う角速度を検出し角速度デ
ータを出力する角速度センサであるジャイロ２と、車両
が移動中であるか停止中であるかを検出してその状態を
出力するとともに車両の走行速度および移動距離データ
を出力する走行距離センサ３と、複数のＧＰＳ衛星から
の電波を受信して演算を行い、緯度・経度・高度・進行
方位等のデータを生成して出力するＧＰＳ測位器４と、
演算・制御等の各種処理を行うシステムコントローラ５
と、システムコントローラ５へ指示入力するための入力
装置１４と、液晶あるいはＣＲＴ等のディスプレイ１５
と、を備えて構成されている。
【００１０】システムコントローラ５は、地磁気センサ
１、ジャイロ２、走行距離センサ３、およびＧＰＳ測位
器４の出力を入力してＡ／Ｄ変換等を行うインタフェー
ス６と、プログラムに従って各種演算・制御を行うＣＰ
Ｕ（Central Processing Unit ）７と、各種の処理プロ
グラムやその他必要な情報があらかじめ書き込まれたＲ
ＯＭ（Read Only Memory）８と、プログラムを実行する
上で必要な情報の書込みおよび読出しが行われるＲＡＭ
（Random Access Memory）９と、ＣＤ−ＲＯＭ、ＩＣカ
ード等からなりディジタル化された地図情報等が記録さ
れている記録媒体１０と、Ｖ−ＲＡＭ（ビデオＲＡＭ）
等からなり即時表示可能にデータ展開された画像情報を
一時記憶するフレームバッファであるバッファメモリ１
１と、ＣＰＵ７の指令により送られてくる地図情報等の
グラフィックデータをバッファメモリ１１に描画し、そ
の描画データを画像情報として出力するグラフィックコ
ントローラ１２と、このグラフィックコントローラ１２
から出力される画像情報を入力してディスプレイ１２の
画像表示を制御する表示制御回路１３と、を備えて構成
されている。
【００１１】上記構成のナビゲーション装置において、
システムコントローラ５は起動されると、現在位置表示
手段として次の制御を行う。まず記録媒体１０から地図
表示情報等をアクセスするための情報と自車位置マーク
の表示情報等を読出してＲＡＭ９に記憶する。次に、Ｇ
ＰＳ測位器４から自車位置情報である緯度・経度のデー
タと車両の進行方位データを読取り、自車位置に対応す
る地図データを記録媒体１０から読出してグラフィック
コントローラ１２に送り、現在地の地図をディスプレイ
１５に表示する。さらに、自車位置情報と進行方位から
地図中に自車位置マークを表示する処理を行い、続いて
定期的にＧＰＳ測位器４から自車位置情報と進行方位デ
ータを読取り、その情報により自車位置マークの表示位
置と方向および必要であれば表示する地図の更新処理を
行う。また、地磁気センサ１、ジャイロ２、および走行
距離センサ３の出力データを定期的に読取り、その出力
データから所定の演算を行って自車位置と進行方位を算
出し、その算出したデータとＧＰＳ測位器４からのデー
タとを比較し互いの誤差を調整して修正処理を行う。
【００１２】また、本実施例のナビゲーション装置で
は、最適経路検索機能を備えている。この最適経路検索
機能では、システムコントローラ５が、指示入力により
まず従来と同様に目的地点の設定入力を受け付ける。設
定入力の受付後、ＣＤ−ＲＯＭ１０に記憶されている現
在地点から目的地点に至る種々の経路の道路情報（道路
の距離・幅員など）、渋滞情報などをＲＡＭ９に記憶す
る。そして、現在地点からの走行において、各地点の前
記道路情報等を用いて、現在地点から目的地点までの種
々の経路が評価され、これらの経路の中で最も評価の優
れた経路が最適経路として選択され、当該選択された最
適経路が進行経路として表示される。第１実施例 図２に、本発明による最適経路探索機能を有しているナ
ビゲーション装置の第１実施例のフローチャートを示
し、図３に、探索方法の説明図を示す。
【００１３】探索機能が開始されると（ステップ２
１）、探索対象となる最初の１点（図３の点Ｐ）が特定
される（ステップ２２）。次に有効な接続数Ｎ個に対し
て使用順テーブルを作成し、カウンタのカウント値Ｃを
ゼロに設定する（ステップ２３）。図３の場合では、例
えば目的地点の方位が最も近い点から採用される。ま
た、処理の高速化のため、探索対象点を現在地点と目的
地点とを焦点とする楕円内に限定することもできる。こ
こで、有効な接続数とは、点Ｐから移動可能な探索対象
点の数をいう。例えば点Ｐと点との間の道が探索対象
点から点Ｐへの一方通行路である場合、点Ｐから点
に直接移動することはできない。この場合、有効な接続
数Ｎは３となる。
【００１４】次に、Ｃ＞Ｎ−１であるか否かを判断する
（ステップ２４）。この場合、Ｃ＝０，Ｎ−１＝３−１
＝２であり、Ｃ＜Ｎ−１となる。Ｃ＞Ｎ−１でない場合
（ステップ２４，ＮＯ）、ＣＤ−ＲＯＭ１０の使用順テ
ーブルからＣの位置データを読み出す（図２、ステップ
２８）。
【００１５】次に、探索対象点が禁止点であるか否か
を判断する（ステップ２９）。ここで、禁止点とは、デ
ータの端点の場合、すべての方向が使用済みの点に囲ま
れた場合等である。探索対象点が禁止点の場合（ステ
ップ２９，ＹＥＳ）、カウント値Ｃをインクリメントし
（ステップ３１）、次の探索対象点、例えば図３の点
について上記と同様のステップが繰り返される。一方、
探索対象点が禁止点でない場合（ステップ２９、Ｎ
Ｏ）、探索対象点が使用済み点か否かを判断し（ステ
ップ３０）、使用済み点の場合には（ステップ３０、Ｙ
ＥＳ）上記と同様にカウント値Ｃをインクリメントし
（ステップ３１）、次の探索対象点について上記と同様
のステップが繰り返される。探索対象点が使用済み点
でない場合には（ステップ３０、ＮＯ）探索対象点が
目的地点か否かを判断する（ステップ３２）。目的地点
の場合（ステップ３２、ＹＥＳ）、探索を終了する（ス
テップ３３）。一方、目的地点でない場合（ステップ３
２、ＮＯ）、当該探索対象点を経路点として登録し（ス
テップ３４）、評価値を計算する（ステップ３５）。評
価値の計算については後述する。
【００１６】次に、計算された評価値が悪化したか否か
について判断し（ステップ３６）、評価値が悪化した場
合には（ステップ３６，ＹＥＳ）探索を中止し（ステッ
プ３７）、評価値が悪化しなかった場合には（ステップ
３６、ＮＯ）経路点ポインタをインクリメントし（ステ
ップ３８）、点Ｐの代わりに探索対象点について上記
と同様のステップが繰り返される。
【００１７】また、Ｃ＞Ｎ−１である場合（ステップ２
４，ＹＥＳ）には、探索対象点が禁止点として登録さ
れ（ステップ２６）、経路点ポインタがデクリメントさ
れる（ステップ２７）。すなわち、点Ｐの一つ手前の探
索対象点について上記ステップが繰り返される。１）評価値の計算 次に、ステップ３５の評価値の計算について説明する。
一般的に、最適な経路とは、所要時間が短く（距離が
短い、渋滞がない）、運転が容易でわかりやすく（直
線的、幅員が大きい）、経済的な経路である。このよ
うな要素を考慮して、以下に評価式の２つの例を示す。
【００１８】 Ｗ1 Σ（道のり／幅員）＋Ｗ2 Σ（渋
滞度）＋Ｗ3 Σ（直進性）＋Ｗ4 Σ（料金）＋Ｗ5 （右
折回数）＋Ｗ6 （左折回数） Ｗ1 Σ（（道のり／幅員）×（渋滞度）×（直進
性）×（料金））＋Ｗ2 （右折回数）＋Ｗ3 （左折回
数） ここで、各式における係数Ｗ1 〜Ｗ6 は、いづれも各パ
ラメータへの重み付けであり、ユーザの重要度に応じて
変化する。また、加算は各ノード単位で現在地点から目
的地点まで行う。
【００１９】各式により求めた値が小さいほど良い経路
となる。例えば、（１）式において、運転が容易な道幅
の大きな道を最優先とする場合には、Ｗ1 の値を大きく
する。２）重み付けの方法 パラメータ毎とパラメータ間（全体）とに分けて説明す
る。
【００２０】 パラメータ毎の重み付け方法の一例を
以下に説明する。 道のり：距離に比例し所要時間が大きくなることから、
距離に比例させて大きくする。
【００２１】幅 員：例えば、１車線道路と細街路では
走り易さがかなり異なるが、１車線道路と２車線道路又
は２車線道路と３車線道路とでは走り易さにさほど大き
な差はないものと思われる。したがって、単純に幅員に
比例させるのではなく、走り易さの変化の程度を考慮す
る。
【００２２】渋滞度：渋滞時の平均速度に比例させて大
きくする。将来的には、下記通信情報等から渋滞の程度
を判断し、係数を設定できるようにする。 直進性：ここでいう直進性とは、交差点（経路点）及び
その前後の３点間の直進性をいう。３点間の直進性は、
経路点への流入角と流出角との角度差により求まる。こ
の場合にも、重み係数を単純に角度に比例させるのでは
なく，Ｕターンに近い屈曲がより悪い直進性となるよう
に重み付けを行う。
【００２３】料 金：金額に比例させ、係数を大きくす
る。 右折回数及び左折回数：回数に比例させて係数を大きく
する。なお、現在実験中であるが将来的には、ＶＩＣＳ
（Vehicle Information andCommunication System）デ
ータを取り込み、ここから得られる渋滞情報、交通規制
情報（通行禁止区間など）等から特定パラメータの重み
付けを変更することができる。
【００２４】 パラメータ間の重み付けの方法の一例
を以下に説明する。一般的に、評価値が悪化した場合、
それ相当分の道のりが長くなったものと考えることがで
きる。ここでは、道のりの長さ［ｍ］を基準として重み
付けを行う。以下に、実験（コンピュータでのシュミレ
ーション）により求めたパラメータ間の比率の一例を示
す。
【００２５】道のり：基準 幅 員：計算式は、（道のり／幅員）である。幅員の影
響により、カッコ内の値が本来の値の約０．５〜２倍程
度になるようにする。すなわち、細街道の場合に本来の
道のりの２倍程度、３車線道路の場合に０．５倍程度と
なるようにする。
【００２６】渋滞度：渋滞時の平均速度が通常時の平均
速度とどれだけ相違するかによって決定する。 直進性：最大で、すなわちＵターンに近い、経路点への
流入角と流出角との角度差が最大で１．５倍程度となる
ようにする。
【００２７】料 金：ユーザが有料道路を優先するか否
かによって異なる。通常、一般道路の道のりの１．５倍
を有料道路の道のりとする。 右折回数：左折回数の２倍程度の重み付けとする。特
に、曲がる回数を低減させたい場合には、右折１回につ
き本来の道のりを１．４〜１．５倍程度とする。
【００２８】左折回数：右折回数の１／２倍程度の重み
付けとする。すなわち、右折１回に付き１．４〜１．５
倍程度の重み付けをする場合には左折１回に付き１．２
〜１．２５倍程度の重み付けを行う。第２実施例 図４に、本発明による最適経路探索機能を有しているナ
ビゲーション装置の第２実施例のフローチャート示し、
図５に、その探索方法の説明図を示す。
【００２９】第１実施例の探索により、例えば図５に示
す経路１→２→３→４→５→６→７→８→９が探索でき
たものとする。第１実施例では、開始点を１とし、終了
点を９とした場合の探索結果が１〜９になったわけであ
るが、点線で示すようなもっと好適な経路を見落として
いる可能性がある。そこで、第１回目のある区間の評価
値と第２回目のある区間の評価値とを比較し、より好ま
しい経路を新しい経路として置き換える。これを１から
７、１から６、１から５、…、７から９と繰り返し、よ
り優れた経路を見いだすことができなくなった時点で最
適化を終了する。
【００３０】この方法で最適化を行った場合の探索回数
を以下に示す。ここで、Ｎを探索回数、ｎを経路点数と
する。 Ｎ＝（ｎ2 −３ｎ＋２）／２ … しかし、最適化の過程で経路の置き換えが行われると、
経路点数が変化するため、必ずしも式に示す値とはな
らない。
【００３１】以下、図４を参照して、第２実施例による
最適経路探索の処理を説明する。最適経路探索が開始さ
れると（ステップ４０）、最適化対象点を決定する（ス
テップ４２）。ここで、経路番号を０からｎとする。上
記式からもわかる通り、探索回数がｎの二乗に比例す
るので、この通り探索を実行するとかなりの処理時間を
要する。そこで、探索回数を減らすことが必要となる。
最適化の本来の目的は、曲がった経路をできる限り直線
に近づけることである。このため、すでに直線に近い区
間の最適化はあまり必要なく、経路が屈曲している点間
でのみ経路探索を行う。すなわち、経路が屈曲する点を
対象点として選択する（屈曲点間最適化）。また、より
よい経路を見落としてしまうことを防止するため、幅員
レベルを限定することもできる。すなわち、直線区間内
でも、探索対象の幅員レベルの道路が交差する経路点が
存在する場合には、これも最適化対象点とする。
【００３２】次に、探索区間ｉ、ｊを設定する。初期値
を、ｉ＝０、ｊ＝ｎ−１に設定し、この間の１つの経路
をｋ０とする（ステップ４２）。次に、ｉ→ｊ間（経路
ｋ０）の評価値（ｈ０）を計算する（ステップ４３）。
評価値の計算方法及び重み付けの方法については第１実
施例と同様である。更に、ｉ→ｊ間の他の経路（ｋ１）
を第１実施例と同様に再探索し（ステップ４４）、経路
ｋ１の評価値ｈ１を計算する（ステップ４５）。この
後、ｈ０＞ｈ１であるか否かを判断し（ステップ４
６）、ｈ０＞ｈ１の場合（ステップ４６、ＹＥＳ）には
経路ｋ０よりも経路ｋ１の方が好適であると判断し、ｋ
０をｋ１で置換し（ステップ４９）、上記ステップ４１
から４５までが繰り返される。一方、ｈ０＞ｈ１でない
場合には、ｉ，ｊの値を更新し（ステップ４７）、すべ
ての点間の調査が終了したか否かを判断する（ステップ
４８）。ここで、ｉは０からｎ−２までの正数、ｊはｎ
−１からｉ＋２までの正数である。すべての点間の調査
が終了した場合（ステップ４８、ＹＥＳ）には最適化探
索を終了し（ステップ５０）、終了していない場合（ス
テップ４８、ＮＯ）には上記ステップ４３からの行程が
繰り返される。第３実施例 図６に、本発明による最適経路探索機能を有しているナ
ビゲーション装置の第３実施例のフローチャート示し、
図７及び８を用いて、その探索方法の説明する。第３実
施例では、使用する経路データをできるだけ少なくする
ために、経路データを階層化している。具体的には、現
在地点と目的地点とがかなり離れている場合には上位階
層データを使用し、近い場合には下位階層のデータを使
用する。
【００３３】図７に、経路データの階層化の一例を示
す。ここでは、階層１が階層２及び３の上位階層であ
り、階層３が最下位の階層である。また、階層１〜３が
同一の範囲を示しているが、ユニット（ここで、ユニッ
トとは、データをメッシュに切ったときの１つの矩形領
域のことである。）の大きさは上位階層程大きいものと
する。例えば、階層１は、高速道路、有料道路、国道を
示し、階層２は、主要道、県道等を示し、階層３は、こ
れらよりも細い道路、すなわち、細街道等を示すものと
する。経路点データを階層化することによって効率よく
探索を行うことができる。すなわち、遠距離の場合には
上位階層（高速道路、国道、県道など）で検索を行い、
近距離の場合は下位階層（主要道等）で探索を行う。
【００３４】図８に、現在地点と目的地点とを含む４ユ
ニット内探索の説明図を示す。図８において、４ユニッ
トを取り出すとき、現在地点（Ｓ）と目的地点（Ｄ）が
入るぎりぎりの大きさではなく、ある程度の余裕を持た
せるようにする。また、図８に点線で示すように、点Ｄ
から点Ｄ’を探索する場合、又は点Ｓから点Ｓ’を探索
する場合にも、より小さなユニットで同様の処理を行
う。
【００３５】以下、図６を参照して、第２実施例による
最適経路探索の処理を説明する。当該処理を開始すると
（ステップ８０）、ＣＤ−ＲＯＭ１０から現在地点Ｓと
目的地点Ｄとが含まれる経路データ４ユニットがロード
される（ステップ８１）。この時、ロードされた経路デ
ータ上に現在地点Ｓが存在しない場合には現在地点Ｓに
近く且つ目的地点Ｄに近づく方向の経路点Ｓ’を探索し
（ステップ８２）、同様に、ロードされた経路上に目的
地点Ｄが存在しない場合には目的地点に近く且つ現在地
点に近づく方向の経路点Ｄ’を探索し（ステップ８
３）、地点Ｓ’から地点Ｄ’までの経路を、第１実施例
又は第２実施例の方法に従って最適化探索する（ステッ
プ８４）。
【００３６】次に、地点Ｓと地点Ｓ’とが非常に近いか
否かを判断し（ステップ８５）、非常に近くない場合に
は（ステップ８５、ＮＯ）Ｓ，Ｓ’が含まれる下位階層
のユニットがロードされ（ステップ８６）、ＳからＳ’
までの経路を第１実施例又は第２実施例の方法に従って
最適化探索する（ステップ８７）。一方、地点Ｓと地点
Ｓ’とが非常に近い場合には（ステップ８５、ＹＥＳ）
上記ステップ８６及び８７を省略し、次の処理が行われ
る。
【００３７】更に、地点ＤとＤ’とが非常に近いか否か
を判断し（ステップ８８）、非常に近くない場合には
（ステップ８８、ＮＯ）、Ｄ，Ｄ’が含まれる下位階層
のユニットがロードされ（ステップ８９）、ＤからＤ’
までの経路を第１実施例又は第２実施例の方法に従って
最適化探索する（ステップ９１）。一方、地点Ｓと地点
Ｓ’とが非常に近い場合には（ステップ８８、ＮＯ）上
記ステップ８９及び９１を省略し、処理を終了する（ス
テップ９２）。
【００３８】なお、探索の時間間隔を階層により変化さ
せることもできる。すなわち、遠い地点の探索は、初め
に概略的な探索を行うため、長い時間間隔で行い、近い
地点の探索は、より細かな探索を行うため短い時間間隔
で行うことが好適である。
【００３９】本発明によるナビゲーション装置を用いて
図１１及び図１２に示す経路の探索を行った場合の探索
経路をそれぞれ図９及び図１０に示す。
【００４０】
【発明の効果】上記本発明によるナビゲーション装置の
構成によれば、ユーザの要求に応じて評価パラメータの
重み付けを変更することができ、ユーザの要求に近い経
路を選択することができる。特に、経路の直進性が考慮
され、右左折の少ない経路を探索できる。また、探索と
同時に評価を行っているので探索精度を維持しつつ、処
理を高速化することができ、よりよい経路をリアルタイ
ムで予測しつつ探索することができる。従って、もし自
動車が初期の経路を逸脱した場合でもすばやく対応する
ことができる。また、評価値が悪くなりそうな経路の探
索を早い段階で打ち切ることによって、無駄な探索をな
くし、処理速度を向上させることができる。
【００４１】また、屈曲点間最適化では対象点を大幅に
減少させることができるので処理速度を向上させること
ができる。幅員レベルを考慮することで、屈曲点間のみ
では見いだすことができない経路を探索すること、又は
幅員レベルを限定することで、例えば幅員５．５ｍ未満
の道路を探索対象からはずすことで処理速度を向上させ
ることができる。更に、探索対象としての道路の種別を
限定し、処理速度を向上させることができる。
【００４２】更に、経路データを階層化することで、探
索をより効率よく短時間で行うことができる。
【図面の簡単な説明】
【図１】本発明の説明図である。
【図２】本発明による最適経路探索機能を有しているナ
ビゲーション装置の第１実施例を示すフローチャートで
ある。
【図３】探索方法の説明図である。
【図４】本発明による最適経路探索機能を有しているナ
ビゲーション装置の第２実施例を示すフローチャートで
ある。
【図５】探索方法の説明図である。
【図６】本発明による最適経路探索機能を有しているナ
ビゲーション装置の第３実施例を示すフローチャートで
ある。
【図７】階層化された経路データの説明図である。
【図８】現在地点と目的地点とを含む４ユニット内探索
の説明図である。
【図９】本発明によるナビゲーション装置を用いた場合
の探索経路を示す図である。
【図１０】本発明によるナビゲーション装置を用いた場
合の探索経路を示す図である。
【図１１】従来のナビゲーション装置を用いた場合の経
路探索の説明図である。
【図１２】従来のナビゲーション装置を用いた場合の経
路探索の説明図である。
【図１３】従来のナビゲーション装置を用いた場合の経
路探索の説明図である。
【符号の説明】
１…地磁気センサ ２…ジャイロ ３…走行距離センサ ４…ＧＰＳ測位器 ５…システムコントローラ ６…インターフェイス ７…ＣＰＵ ８…ＲＯＭ ９…ＲＡＭ １０…ＣＤ−ＲＯＭ １１…バッファメモリ １２…グラフィックコントローラ １３…表示制御回路 １４…入力装置 １５…ディスプレイ

Claims (2)

    【特許請求の範囲】
  1. 【請求項１】 目的地点を入力し、自己の現在地点から
    目的地点までの進行経路の表示を行うナビゲーション装
    置において、 予め記憶されている各地点の情報を用いて、現在地点か
    ら目的地点までの種々の経路を評価し、最適な経路を探
    索する最適経路探索手段を備えていることを特徴とする
    ナビゲーション装置。
  2. 【請求項２】 請求項１記載のナビゲーション装置にお
    いて、 前記最適経路探索手段が、道のり・幅員・渋滞度・直進
    性・料金・右折回数・左折回数等のパラメータに各々重
    み付けして得られる評価用パラメータに基づいて現在地
    点から目的地点までの疑似距離を計算し、当該疑似距離
    から前記現在地点から目的地点までの種々の経路を評価
    することを特徴とするナビゲーション装置。
JP5099806A 1993-04-26 1993-04-26 ナビゲーション装置 Pending JPH06309595A (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
JP5099806A JPH06309595A (ja) 1993-04-26 1993-04-26 ナビゲーション装置
EP94302998A EP0622611B1 (en) 1993-04-26 1994-04-26 Navigation apparatus
US08/233,255 US5506774A (en) 1993-04-26 1994-04-26 Navigation apparatus
DE69419066T DE69419066T2 (de) 1993-04-26 1994-04-26 Navigationsvorrichtung

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP5099806A JPH06309595A (ja) 1993-04-26 1993-04-26 ナビゲーション装置

Publications (1)

Publication Number Publication Date
JPH06309595A true JPH06309595A (ja) 1994-11-04

Family

ID=14257118

Family Applications (1)

Application Number Title Priority Date Filing Date
JP5099806A Pending JPH06309595A (ja) 1993-04-26 1993-04-26 ナビゲーション装置

Country Status (4)

Country Link
US (1) US5506774A (ja)
EP (1) EP0622611B1 (ja)
JP (1) JPH06309595A (ja)
DE (1) DE69419066T2 (ja)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2007078587A (ja) * 2005-09-15 2007-03-29 Pioneer Electronic Corp 経路探索装置、経路探索方法、経路探索プログラムおよびコンピュータに読み取り可能な記録媒体
WO2007135855A1 (ja) 2006-05-18 2007-11-29 Pioneer Corporation 情報案内装置、情報案内方法、情報案内プログラムおよびコンピュータに読み取り可能な記録媒体
JP2010519124A (ja) * 2007-02-22 2010-06-03 ネーデルランデ オルガニサチエ ヴォール トエゲパスト−ナツールウェテンスハペリエク オンデルゾエク ティーエヌオー 車両運転補助装置
JP2011220902A (ja) * 2010-04-12 2011-11-04 Alpine Electronics Inc ナビゲーション装置および誘導経路探索方法
KR20180080918A (ko) * 2017-01-05 2018-07-13 현대자동차주식회사 차량 주행모드 추천 서버 및 이를 이용한 주행모드 추천 방법

Families Citing this family (53)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE4402614A1 (de) * 1994-01-28 1995-08-03 Deutsche Telekom Mobil Verfahren zur Ermittlung von Gebühren für die Nutzung von Verkehrswegen durch Fahrzeuge
JP3341955B2 (ja) * 1994-09-01 2002-11-05 アイシン・エィ・ダブリュ株式会社 ナビゲーション装置
JP3632706B2 (ja) * 1994-09-22 2005-03-23 アイシン・エィ・ダブリュ株式会社 車両用ナビゲーション装置
US5712788A (en) * 1995-02-09 1998-01-27 Zexel Corporation Incremental route calculation
US5938720A (en) * 1995-02-09 1999-08-17 Visteon Technologies, Llc Route generation in a vehicle navigation system
US6249767B1 (en) * 1995-08-23 2001-06-19 Hitachi, Ltd. Portable information terminal surrounding formulation of an optimum plan
JPH1082647A (ja) * 1996-09-05 1998-03-31 Mitsubishi Electric Corp 移動体用ナビゲーション装置
US6002982A (en) * 1996-11-01 1999-12-14 Fry; William R. Sports computer with GPS receiver and performance tracking capabilities
US6463385B1 (en) 1996-11-01 2002-10-08 William R. Fry Sports computer with GPS receiver and performance tracking capabilities
JPH10341206A (ja) * 1997-06-06 1998-12-22 Nec Corp 波長多重伝送装置
US6212472B1 (en) 1997-09-04 2001-04-03 Visteon Technologies, Llc Method and apparatus for displaying current vehicle position
US6192314B1 (en) 1998-03-25 2001-02-20 Navigation Technologies Corp. Method and system for route calculation in a navigation application
US6144919A (en) 1998-03-27 2000-11-07 Visteon Technologies, Llc Method and apparatus for using non-digitized cities for route calculation
US6097316A (en) * 1998-04-20 2000-08-01 Visteon Technologies, Llc Communication protocol for a vehicle navigation system
JPH11311533A (ja) 1998-04-28 1999-11-09 Xanavi Informatics Corp 経路探索装置
US6298305B1 (en) 1998-07-15 2001-10-02 Visteon Technologies, Llc Methods and apparatus for providing voice guidance in a vehicle navigation system
US6088649A (en) * 1998-08-05 2000-07-11 Visteon Technologies, Llc Methods and apparatus for selecting a destination in a vehicle navigation system
FR2784776B1 (fr) * 1998-10-19 2000-12-01 Renault Procede de guidage d'un vehicule routier
US6064319A (en) * 1998-10-22 2000-05-16 Matta; David M. Method and system for regulating switching of a traffic light
US6278935B1 (en) 1999-07-23 2001-08-21 Navigation Technologies Corp. Method and system for providing instructions about tollways with a navigation system
US6360165B1 (en) 1999-10-21 2002-03-19 Visteon Technologies, Llc Method and apparatus for improving dead reckoning distance calculation in vehicle navigation system
US6282496B1 (en) 1999-10-29 2001-08-28 Visteon Technologies, Llc Method and apparatus for inertial guidance for an automobile navigation system
US6324470B1 (en) * 2000-03-07 2001-11-27 Navigation Technologies Corporation Method and system for representing restricted driving maneuvers
US6456935B1 (en) 2000-03-28 2002-09-24 Horizon Navigation, Inc. Voice guidance intonation in a vehicle navigation system
US6735516B1 (en) 2000-09-06 2004-05-11 Horizon Navigation, Inc. Methods and apparatus for telephoning a destination in vehicle navigation
JP4622101B2 (ja) * 2000-12-27 2011-02-02 ソニー株式会社 情報処理装置、情報処理装置の情報処理方法および情報処理システム
AU2002255568B8 (en) 2001-02-20 2014-01-09 Adidas Ag Modular personal network systems and methods
US6704645B1 (en) * 2001-12-11 2004-03-09 Garmin Ltd. System and method for estimating impedance time through a road network
US7283905B1 (en) 2001-12-11 2007-10-16 Garmin Ltd. System and method for estimating impedance time through a road network
US6545637B1 (en) 2001-12-20 2003-04-08 Garmin, Ltd. Systems and methods for a navigational device with improved route calculation capabilities
US7184886B1 (en) 2001-12-21 2007-02-27 Garmin Ltd. Navigation system, method and device with detour algorithm
US7277794B1 (en) 2001-12-21 2007-10-02 Garmin Ltd. Guidance with feature accounting for insignificant roads
US6892135B1 (en) 2001-12-21 2005-05-10 Garmin Ltd. Navigation system, method and device with automatic next turn page
US6847890B1 (en) 2001-12-21 2005-01-25 Garmin Ltd. Guidance with feature accounting for insignificant roads
US6999873B1 (en) 2001-12-21 2006-02-14 Garmin Ltd. Navigation system, method and device with detour algorithm
US6751552B1 (en) 2002-06-28 2004-06-15 Garmin Ltd. Rugged, waterproof, navigation device with touch panel
US6850844B1 (en) 2002-06-28 2005-02-01 Garmin Ltd. Portable navigation device with integrated GPS and dead reckoning capabilities
US6721651B1 (en) 2002-06-28 2004-04-13 Garmin Ltd. Rugged, waterproof, navigation device with touch panel
US6801855B1 (en) 2002-06-28 2004-10-05 Garmin Ltd. Systems and methods with integrated GPS and dead reckoning capabilities
US6842696B2 (en) * 2002-07-01 2005-01-11 Intel Corporation Method and device for location detection for a scheduling program
US20060212185A1 (en) * 2003-02-27 2006-09-21 Philp Joseph W Method and apparatus for automatic selection of train activity locations
DE10313542A1 (de) * 2003-03-26 2004-10-14 Robert Bosch Gmbh Navigationsendgerät und Verfahren zur Berechnung und Ausgabe von Fahrtrouten
JP2005017047A (ja) * 2003-06-24 2005-01-20 Nec Corp 位置測位機能付き端末
DE102004055736A1 (de) * 2004-11-18 2006-06-01 Siemens Ag Navigationsvorrichtung und Navigationssystem
US7908080B2 (en) 2004-12-31 2011-03-15 Google Inc. Transportation routing
FI119006B (fi) * 2006-01-03 2008-06-13 Navicore Oy Kaksivaiheinen reititysproseduuri
US7925320B2 (en) 2006-03-06 2011-04-12 Garmin Switzerland Gmbh Electronic device mount
US8149139B2 (en) * 2008-06-02 2012-04-03 Electronic Transaction Consultants Dynamic pricing for toll lanes
US8941482B1 (en) * 2011-06-23 2015-01-27 BenJoaquin Tomas Gouverneur Automating turn indication systems
JP5724919B2 (ja) * 2012-03-22 2015-05-27 トヨタ自動車株式会社 軌道生成装置、移動体、軌道生成方法及びプログラム
JP2016095425A (ja) * 2014-11-14 2016-05-26 アルパイン株式会社 地図データ作成装置及びコンピュータプログラム
WO2018200999A1 (en) * 2017-04-27 2018-11-01 Walmart Apollo, Llc Methods and systems for managing shipment of products from a distribution center
CN115507856A (zh) * 2022-10-28 2022-12-23 九天创新(广东)智能科技有限公司 基于栅格地图的路径规划方法、装置及自移动设备

Family Cites Families (19)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0246452A3 (en) * 1986-04-24 1989-01-18 Norda S.P.A. Computerized trip planner and automotive navigator
JP2613232B2 (ja) * 1987-12-28 1997-05-21 アイシン・エィ・ダブリュ株式会社 車両用ナビゲーション装置
JP2680318B2 (ja) * 1987-12-28 1997-11-19 アイシン・エィ・ダブリュ株式会社 ナビゲーション装置
US5031104A (en) * 1988-12-05 1991-07-09 Sumitomo Electric Industries, Ltd. Adaptive in-vehicle route guidance system
US5293163A (en) * 1990-06-06 1994-03-08 Mazda Motor Corporation Navigation apparatus for vehicles
US5323321A (en) * 1990-06-25 1994-06-21 Motorola, Inc. Land vehicle navigation apparatus
US5184303A (en) * 1991-02-28 1993-02-02 Motorola, Inc. Vehicle route planning system
US5272638A (en) * 1991-05-31 1993-12-21 Texas Instruments Incorporated Systems and methods for planning the scheduling travel routes
US5187667A (en) * 1991-06-12 1993-02-16 Hughes Simulation Systems, Inc. Tactical route planning method for use in simulated tactical engagements
US5285391A (en) * 1991-08-05 1994-02-08 Motorola, Inc. Multiple layer road memory storage device and route planning system
JP2955073B2 (ja) * 1991-08-05 1999-10-04 ビステオン・テクノロジーズ，エル・エル・シー 車両用ナビゲーションシステム
US5345388A (en) * 1991-08-06 1994-09-06 Pioneer Electronic Corporation Navigation system utilizing locus data compression
JP2771911B2 (ja) * 1991-08-09 1998-07-02 三菱電機株式会社 車載用ナビゲーション装置
JP3140100B2 (ja) * 1991-08-29 2001-03-05 パイオニア株式会社 ナビゲーション装置
JP2848061B2 (ja) * 1991-11-06 1999-01-20 三菱電機株式会社 ナビゲーション装置
US5291412A (en) * 1992-03-24 1994-03-01 Zexel Corporation Navigation system
US5291414A (en) * 1992-04-14 1994-03-01 Zexel Corporation Diahatsu-Nissan Ikebukuro Navigation system for guiding a vehicle along a precomputed optimal route
US5303159A (en) * 1992-04-14 1994-04-12 Zexel Corporation Daihatsu-Nissan Navigation system with off-route detection and route recalculation
US5291413A (en) * 1992-04-14 1994-03-01 Zexel Corporation Daihatsu-Nissan Ikebukuro Navigation system for guiding a vehicle along a precomputed optimal route

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2007078587A (ja) * 2005-09-15 2007-03-29 Pioneer Electronic Corp 経路探索装置、経路探索方法、経路探索プログラムおよびコンピュータに読み取り可能な記録媒体
WO2007135855A1 (ja) 2006-05-18 2007-11-29 Pioneer Corporation 情報案内装置、情報案内方法、情報案内プログラムおよびコンピュータに読み取り可能な記録媒体
US8200422B2 (en) 2006-05-18 2012-06-12 Pioneer Corporation Information presentation apparatus, information presentation method, information presentation program, and computer-readable recording medium
JP2010519124A (ja) * 2007-02-22 2010-06-03 ネーデルランデ オルガニサチエ ヴォール トエゲパスト−ナツールウェテンスハペリエク オンデルゾエク ティーエヌオー 車両運転補助装置
US8428860B2 (en) 2007-02-22 2013-04-23 Nederlandse Organisatie Voor Toegepast-Natuurwetenschappelijk Onderzoek Tno Vehicle driving assistance
JP2011220902A (ja) * 2010-04-12 2011-11-04 Alpine Electronics Inc ナビゲーション装置および誘導経路探索方法
US8977487B2 (en) 2010-04-12 2015-03-10 Alpine Electronics, Inc. Navigation device and guide route search method
KR20180080918A (ko) * 2017-01-05 2018-07-13 현대자동차주식회사 차량 주행모드 추천 서버 및 이를 이용한 주행모드 추천 방법

Also Published As

Publication number Publication date
US5506774A (en) 1996-04-09
DE69419066D1 (de) 1999-07-22
EP0622611A1 (en) 1994-11-02
EP0622611B1 (en) 1999-06-16
DE69419066T2 (de) 2000-01-27

Similar Documents

Publication Publication Date Title
JPH06309595A (ja) ナビゲーション装置
US6950746B2 (en) Navigation apparatus and rerouting method
JP4225849B2 (ja) ナビゲーションシステムの誘導地図表示方法及び装置
JP3412684B2 (ja) ナビゲーション装置及び該装置の記録媒体
JP2003214879A (ja) ナビゲーション装置
US20090248296A1 (en) Driving support system, driving support method and computer program
JP2004239864A (ja) ナビゲーション装置並びに該装置用プログラム及び記録媒体
JPH05323872A (ja) 経路表示装置
JP2000146604A (ja) 車両用ナビゲ―ション・システム及び方法
JP3590437B2 (ja) 経路探索装置
JP2001227971A (ja) 車載用ナビゲーション装置
JP4198955B2 (ja) ナビゲーション装置
JPH07134795A (ja) 経路表示方法および装置
JP3022269B2 (ja) 経路情報提供装置
JP3510964B2 (ja) 車載用ナビゲーション装置の誘導経路探索方法
JP3309670B2 (ja) 車両用ナビゲーション装置
JPH0990868A (ja) 地図表示装置およびそれを用いたナビゲーション装置
JPH07113652A (ja) 走行経路案内装置
JP4302703B2 (ja) ナビゲーション装置、ルート再検索方法、ルート再検索プログラム、及びルート再検索プログラムが記録された記録媒体
JPH0567295A (ja) ビーコンから取得した道路情報の選別表示方法
JP4760774B2 (ja) ナビゲーション装置
JP4302702B2 (ja) ナビゲーション装置、ルート再検索方法、ルート再検索プログラム、及びルート再検索プログラムが記録された記録媒体
JP2019078675A (ja) 運転支援システム、運転支援プログラム
JP2001304887A (ja) ナビゲーション装置
JPH04177287A (ja) 最適経路決定装置

Legal Events

Date Code Title Description
A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20040109

A911 Transfer of reconsideration by examiner before appeal (zenchi)

Free format text: JAPANESE INTERMEDIATE CODE: A911

Effective date: 20040226

A912 Removal of reconsideration by examiner before appeal (zenchi)

Free format text: JAPANESE INTERMEDIATE CODE: A912

Effective date: 20040416