JP2938530B2 - ナビゲーション装置の経路探索方法 - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） この発明は、出発地点から目的地点までの経路を探索
する機能を持つナビゲーション装置の経路探索方法に関
するものである。

（従来技術） ナビケーション装置は、目的地点までの経路案内を行
うものであり、近年車載用ナビゲーション装置の開発が
盛んに行われている。

一般に、出発地点から目的地点までの間には複数の経
路が存在するため、記憶装置に記憶されている地図デー
タの道路条件に基いて、目的地点までの最短時間あるい
は最短距離となる経路を作成する経路探索の手法が考案
されている。

（発明が解決しようとする課題） しかしながら、前記最短経路は、道路データとして記
憶されている交差点間の道路リンク距離や所要時間の累
計によって決定され、目的地点が経路の左右どちら側に
位置するかという事は考えられていない。

従って第５図に示すように、探索経路R1に従って車両
１が走行した場合、目的地点２が該探索経路の最後の道
路リンクL1の進行方向右側に存在する場合がある。

この時、同図において道路L1が幅員の狭い地方道の用
な場合は実用上問題ないが、中央分離帯のある場合や片
側２車線以上の幅員の広い道路である場合等は事実上目
的地点２までの経路が作成できたとは言えない。

本発明は、上記課題を解決するものであって、経路探
索処理の最後に決定される道路リンクの進行方向右側に
目的地点が存在するような場合には該道路リンクの進行
方向右側に目的地点が位置するように経路探索を行う方
法を提供する事を目的とするものである。

（課題を解決するための手段） 上記課題は本発明によれば、道路属性データテーブル
を備えた道路データから経路を探索する経路探索手段
と、目的地点が進行方向右側に位置する事で不具合が生
じるかどうかの判別する判別手段と、不具合が生じる場
合には目的地点が進行方向左側に位置するような経路を
探索する手段とにより達成される。

（作 用） 本発明のナビゲーション装置の経路探索方法では、道
路属性データテーブルを備えた道路データから経路を探
索し、目的地点が探索経路の進行方向右側に位置すると
きに不具合が生じるかどうか判別し、不具合が生じる場
合には目的地点が進行方向左側に位置するように再度経
路を探索する。

また、目的地点が入力された時点で進行方向の右側に
目的地点が位置すると不具合が生じるかどうかを判別す
る場合に於いては、不具合が生じない場合には、目的地
点が車両進行方向右側に位置するか進行方向左側に位置
するかを考慮することなく、地図データより経路を探索
し、不具合が生じる場合には、目的地点が最終道路の進
行方向左側に位置するような経路を探索する。

（実施例） 以下、図面に基いて実施例を説明する。

第１図は本発明の実施例を示す図、第２図は本発明に係
わるナビゲーション装置のシステム構成を示す図、第３
図は道路データに含まれる道路属性データテーブルの例
を示す図、第４図は経路探索処理の流れを説明するため
の図である。

第２図において、入力装置８によって出発地点および
目的地点に入力する。尚、走行距離センサ５と方位セン
サ６の出力に基いて位置検出装置７によって検出される
車両の現在位置を出発地点として入力する事もできる。

地図データ記憶装置９は、道路地図を収録している大
容量のメモリからなり、このメモリとしてはCD−ROM等
が使用される。上記地図データ記憶装置に記録されてい
る地図データは、道路リンクデータ、交差点データ、ノ
ードデータ等からなる道路レイヤと、地図上のオブジェ
クトを表示装置11に出力するための背景レイヤと、市町
村名や国道名などを出力するための文字レイヤなどから
構成されている。

この内の道路リンクデータ（道路データ）は、第３図
に示すように、該当道路リンクの属性情報を与えるデー
タテーブルA,Bより構成されている。属性データテーブ
ルＡはリンク距離、所要時間、一方通行フラグ等のデー
タにより構成され、経路探索処理に於いて、実施例距離
最短経路あるいは時間距離最短経路の候補を作成し、決
定する際に用いられるデータ群である。

また第３図に示す属性データテーブルＢは、目的地点
が車両進行方向右側に位置する場合に実用上不具合を生
じないかどうかを判別するために用いられるデータ群で
ある。

第４図は本発明の経路探索方法の流れ図である。従来
の経路探索処理は（１）−（５）までのステップで実現
されており、本発明に係わる処理は（６）−（13）まで
のステップにより実現される。

以下順を追って説明する。

経路探索を開始するためのスイッチを押下すると、第
２図に示すデータ処理装置10は経路探索プログラム（第
４図）をスタートさせる。

まず目的地点として入力された地図上の座標をメモリ
にストアする（ステップ（１））。この時点ではまだ目
的地が経路の左右どちら側に位置するか定かではない。

次に出発地点として入力された地図上の座標をメモリ
にストアする（ステップ（２））。

出発地点と目的地点の座標から、地図上の所定の範囲
の道路レイヤのデータを適宜地図データ記憶装置９より
データ処理装置10に内蔵されているメモリに読み込む。
この時メモリに読み込む道路リンクデータの道路属性デ
ータテーブルは全データを読み込む必要はなく、処理時
間、メモリの節約の点から第３図Ａに示すデータ群だけ
でよい（ステップ（３））。

次に道路レイヤのデータを利用して、前記入力された
出発地点から目的地点までの経路の候補をいくつか作成
し、所定の条件を満たす経路を決定後、その経路を構成
するノードデータをメモリにストアする（ステップ
（４）−（５））。

この時、目的地点に最も近く、経路の最後の道路とし
て検索された道路リンクに進入するときに通過する交差
点のデータも保持しておく。

以上第４図ステップ（１）−（５）迄の処理で、出発
地点から目的地点までの経路が作成された事になるが、
第５図に示すように、目的地点２が車両進行方向右側に
位置する場合がある。道路の幅員が狭く、駐車が可能な
場合やＵターンや横断が容易な場合にはそれでも実用上
さほど問題とはならない。

しかし、近年の道路網の整備は目ざましいものがあ
り、地方に於いても市街地を迂回するためのバイバス等
４車以上の幅いを持つ道路も珍しくない。このような道
路では、交通量も多く、中央分離帯が設置されている事
もあり、道路の横断やＵターンが事実上不可能な場合も
ある。また、昨今の道路事情からさほど幅員の広くない
道路でも、都市部では駐車やＵターンができない事も多
い。

円滑に交通の流れに乗って目的地点に到着するために
は、日本に於いては車両進行方向左側に目的地点が位置
するような経路を選ぶ必要があるわけである。そこでス
テップ（６）以下の処理が必要となる。

ステップ（１）−（５）で一応の経路が探索できた
ら、目的地点が道路進行方向の左右どちら側に位置して
いるかを、道路を構成するノードの座標と、目的地点の
座標との位置関係から判断する（ステップ（６））。

もし、目的地点が経路進行方向の左側に位置している
ならば、経路探索処理はこれで終了である。

目的地点が経路進行方向の右側に位置しているときに
は、経路の最終道路となっている道路リンクの属性デー
タテーブルを参照して、目的地点が道路右側に位置して
いても実用上不具合を生じないかどうかの判断を行う
（ステップ（７）−（11））。

実用上問題ない場合には、経路探索処理はこれで終了
である。

最終道路に中央分離帯のある場合、４車線以上の場
合、駐車禁止かつＵターン禁止の場合には、ステップ
（12）に飛び、該当道路リンクの進入方向を制限する。
即ち、該当道路リンクの属性データの一方通行フラグを
立て、同道路リンクへの進入交差点３（第１図参照）か
らの進入は出来ないものとみなす。

さらにステップ（13）で、当該交差点の座標を出発地
点の座標として入力し、再度経路探索を行う。

この再経路探索により、第１図に示すように、交差点
３を出発地点とし、交差点４より最終道路リンクL1へ進
入する経路R2が作成され、目的地点は経路進行方向に位
置する事になる。

この時作成された交差点３より目的地点に至る経路R2
は、メモリにストアされている一回目の経路検索で得た
経路R1から最終道路リンクを除外した経路に付加され
る。

上記処理により、最初に入力した出発地点より目的地
点までの経路が探索される事になる。

尚、本実施例では一回目の経路検索を終了してから目
的地点が道路リンクの右側にあるかどうかの判断と、そ
れによる不具合が生じるかどうかの判断を行っている
が、目的地点が入力された時点で、目的地点に最も近い
道路リンクの属性データテーブルを参照して、目的地点
が進行方向右側にあると不具合を生じるかどうかの判断
（ステップ（７）−（11））。を行うようにしてもよ
い。

この場合、目的地点が経路進行方向の右側に位置して
も不具合を生じないときには、ステップ（３）−（５）
の処理を行う事により、経路を探索できる。

目的地点が経路進行方向の右側に位置することで不具
合を生じる場合には、経路探索処理を始める前に、最終
道路の道路属性データテーブルの中一方通行フラグを立
てて進入方向の制限を行う事により、目的地点が進行方
向の右側に位置するような経路を作成する。

以上の説明で明らかなように、出発地点から目的地点
までの経路を探索する際、目的地点が進行方向右側に位
置する事で不具合が生じる場合には目的地点が進行方向
左側に位置するような経路を探索する事が可能となり、
ドライバーが交流の流れに沿って目的地まで到着する事
が出来る。

尚、本実施例では左側通行の日本の交通事情に合わせ
て記述したが、第４図の目的地点の位置判断ステップ
（６）で、目的地点が進行方向右側にあるかどうかの判
断を、左側にあるかどうかの判断に置き換える事によ
り、右側通行の外国の場合にも本経路探索方法を適用す
る事が出来る。

（発明の効果） 以上のように本発明の経路探索方法によれば、目的地
点が進行方向右側に位置する事で不具合が生じる場合に
は目的地点が進行方向左側に位置するような経路を探索
する事が可能となり、ドライバーが交通の流れに沿って
目的地まで到着する事が出来る。

【図面の簡単な説明】

第１図は本発明の経路探索方法の説明図、第２図は車載
用ナビゲーション装置のブロック図、第３図は道路デー
タに含まれる道路属性データテーブルを説明するための
図、第４図は本発明の経路探索処理の流れ図、第５図は
従来の経路探索方法による問題点を説明するための図で
ある。 １……車両、２……目的地点 3,4……交差点、L1……最終道路リンク R1,R2……探索経路

Claims (2)

(57)【特許請求の範囲】
1. 【請求項１】出発地点から目的地点までの所定の条件を
   満たす経路を探索する機能を持つナビゲーション装置の
   経路探索方法に於いて、 道路属性データテーブルを備えた道路データから前記条
   件を満たす経路を探索するステップと、 目的地点が前記探索経路を進行方向右側に位置する場合
   に、右側に位置して不具合が生じるかどうかを道路属性
   データを参照して判断するステップと、 不具合が生じる場合には目的地点が経路の進行方向左側
   に位置するように再度経路を探索するステップとを有す
   る事を特徴とする経路探索方法。
2. 【請求項２】出発地点から目的地点までの所定の条件を
   満たす経路を探索する機能を持つナビゲーション装置の
   経路探索方法に於いて、 道路データに含まれる道路属性データテーブルを参照し
   て、目的地点が最終道路の進行方向右側に位置する場合
   に、右側に位置して不具合が生じるかどうかを判断する
   ステップと、 不具合が生じない場合には、目的地点が車両進行方向右
   側に位置するか進行方向左側に位置するかを考慮するこ
   となく、地図データより前記条件を満たす経路を探索す
   るステップと、 不具合が生じる場合には、目的地点が最終道路の進行方
   向左側に位置するように前記条件を満足する経路を探索
   するステップとを有する事を特徴とする経路探索方法。