JPH06174485A

JPH06174485A - 経路探索装置

Info

Publication number: JPH06174485A
Application number: JP32956492A
Authority: JP
Inventors: Atsushi Ichimura; 淳市村; Katsumi Sakata; 克己阪田
Original assignee: Denso Ten Ltd
Current assignee: Denso Ten Ltd
Priority date: 1992-12-09
Filing date: 1992-12-09
Publication date: 1994-06-24
Anticipated expiration: 2015-05-15
Also published as: JP3042569B2

Abstract

(57)【要約】【目標】本発明はカー・ナビゲーション装置に関し、
出発位置から目標位置までの経路を探索する経路探索装
置の改良を目的とする。【構成】道路を複数のリンクに細分化し各リンク毎の
道路データに基づき車両の目標位置までの最短の経路を
探索する経路探索装置に、各複数のリンクに対応するリ
ンク長に関し、道路種別で重み補正がなされ、さらに幅
員で重み補正がなされた補正リンク長を形成するリンク
長重み補正部３１と、補正リンク長を用いて出発位置か
ら目標位置までの最短の経路を探索する探索部３２と、
探索経路について出発位置から目標位置までの各リンク
の所要時間を累積した推定所要時間を算出し、さらに各
リンクでの速度と現在位置から目標位置までの距離、推
定所要時間を算出し表示させる所要推定時間算出部３３
とを設ける。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はカー・ナビゲーション装
置に関し、特に本発明では出発位置から目標位置までの
経路を探索する経路探索装置の改良に関する。

【０００２】

【従来の技術】従来このような分野の技術としてダイク
ストラ法(Dijkstra)等が経路探索装置に用いられてい
る。このダイクストラ法等では、道路を細分化したリン
クの情報に関するリンクデータと、該リンクの両端の点
であるノードの接続関係の情報に関するノードデータに
基づき、探索開始点である出発位置と目標位置までの経
路に関し、ノードデータ→リンクデータ→ノードデータ
→リンクデータ…、という順序で経路長が最短となる経
路を算出している。この最短経路は、ノードデータによ
りリンクを接続して行き、前記リンクデータにおけるリ
ンク長を出発位置から目標位置までの複数の経路につい
て累積し、その中で最短距離のものとして求められてい
る。

【０００３】

【発明が解決しようとする課題】しかしながら実際の道
路の長さをリンク長とするダイクストラ法を用いた経路
探索装置で得られた経路は、例えば、道路幅が狭い、右
左折が多い等の理由により走り難い経路（ルート）であ
ったりして、距離的には最短であっても必ずしも時間的
には最短であるとは限らないという問題があった。

【０００４】したがって本発明は上記問題点に鑑み走り
やすく時間的に最短となる経路探索装置を提供すること
を目標とする。

【０００５】

【課題を解決するための手段】本発明は前記問題点を解
決するために、道路を複数のリンクに細分化し各リンク
毎に道路データを記憶する記憶媒体を有し、前記道路デ
ータに基づき車両の出発位置から目標位置までの最短の
経路を探索する経路探索装置に、リンク長重み補正部、
探索部及び所要推定時間算出部を設ける。

【０００６】前記リンク長重み補正部は各前記複数のリ
ンクに対応するリンク長が高速道路から一般地方道路に
なるにつれて大きくなるように道路種別で重み補正がな
され、さらに広い幅の道路から狭い幅の道路になるつれ
て大きくなるように幅員で重み補正がなされた補正リン
ク長を形成するようにしてある。前記探索部は前記補正
リンク長を用いて、出発位置から目標位置までの最短の
経路をダイクストラ法により探索するようにしてある。

【０００７】前記所要推定時間算出部は探索された経路
について出発位置から目標位置までの各リンクの前記所
要時間を累積した推定所要時間を算出し、さらに各リン
クでの前記速度と現在位置から目標位置までの距離、推
定所要時間を算出し表示させるようにしてある。前記記
憶媒体は各前記複数のリンクに対応するリンク長が高速
道路から一般地方道路になるにつれて大きくなるように
道路種別で重み補正をし、さらに道路の幅が狭くなるに
つれて大きくなるように幅員で重み補正した補正リンク
長を記憶するようにしてある。

【０００８】前記補正リンク長が大きくなるにつれてリ
ンクを走行する車両の所要時間が大きくなるように、前
記補正リンク長が大きくなるにつれてリンクを走行する
速度が小さくなるように規格化してある。

【０００９】

【作用】本発明の経路探索装置によれば、各前記複数の
リンクに対応するリンク長が高速道路から一般地方道路
になるにつれて大きくなるように道路種別で重み補正が
なされ、さらに広い幅の道路から狭い幅の道路になるつ
れて大きくなるように幅員で重み補正がなされた補正リ
ンク長を形成することにより、一般的に走り易い経路を
算出できるようになる。前記補正リンク長が大きくなる
につれてリンクを走行する車両の所要時間が大きくなる
ように規格化し、探索された経路について出発位置から
目標位置までのリンクの前記所要時間を累積した推定所
要時間を表示し、前記補正リンク長が大きくなるにつれ
てリンクを走行する速度が小さくなるように規格化し、
探索された経路についてリンクの前記速度と現在位置か
ら目標位置までの推定所要時間を表示することにより、
ユーザが運転計画の立案を支援できるようになる。前記
補正リンク長が大きくなるにつれてリンクを走行する車
両の所要時間が大きくなるように、前記補正リンク長が
大きくなるにつれてリンクを走行する速度が小さくなる
ように規格化されるが、このように規格化されるのは補
正リンク長が距離／推定時間としてのディメンジョンを
持っているからである。また前記記憶媒体は各前記複数
のリンクに対応するリンク長が高速道路から一般地方道
路になるにつれて大きくなるように道路種別で重み補正
をし、さらに道路の幅が狭くなるにつれて大きくなるよ
うに幅員で重み補正した補正リンク長を記憶することに
より、処理の高速化を図ることができるようになる。

【００１０】

【実施例】以下本発明の実施例について図面を参照して
説明する。図１は本発明の実施例に係るナビゲーション
装置を示す図であり、図２は図１の表示装置４に表示さ
れる道路地図の例を示す図である。図１に示すナビゲー
ション装置は、地図、道路に関するデータベースＤＢを
記憶する、例えばＣＤ(Compact Disc)、ＩＣ(Integrate
d Circuit)カード等の記憶媒体１と、方位センサ、車速
センサ等からの信号を入力し車両位置を求め、さらに路
車間通信を行うためのビーコンからの交通情報を入力す
るロケーション装置２と、外部から目標位置を入力し、
前記ロケーション装置２から車両の現在位置を入力し、
ダイクストラ法等により出発位置から目標位置までの経
路を探索する経路探索装置３と、ＣＲＴ(Cathode Ray T
ube)、ＬＣＤ(Liquid Crystal Display)からなり、図２
に示すように、記憶媒体１からの地図データを表示し、
車両の現在位置を車両マーカで表示し、目標位置を表示
し、さらに車両位置から目標位置までの経路を、例え
ば、太線で重ね表示する表示装置４を具備する。

【００１１】図３は図１の経路探索装置の構成を示す図
である。本図に示す経路探索装置は先ず記憶媒体１から
の道路データにおけるリンクデータのリンク長を補正
し、該補正リンク長を用いて後述する経路探索部３１に
経路を探索させるリンク長重み補正部３１と、車両の現
在位置等及び目標位置を入力して前記リンク長重み補正
部によりリンク長が補正された道路データを用いて経路
を探索する経路探索部３２とを具備する。ダイクストラ
法を用いる前記経路探索部３２自体は周知技術であるの
でその詳細を省略する。以下リンク長重み補正部３１を
説明する。リンク長重み補正部３１には、経路探索部３
２に車両位置と目標位置とが入力すると、この間を含む
ある範囲の道路地図が記憶媒体１から読み出される。こ
の読み出された道路データにつき説明する。

【００１２】図４は道路データにおけるリンクデータ及
びノードデータを説明する図である。本図（ａ）に示す
ように、道路データは道路を細分化した複数のリンクに
関するリンクデータで構成される。各リンクデータは始
点ノードＮｏ．、終点ノードＮｏ．、リンクの方位、リ
ンクの実際の長さ、属性からなる。この属性は、例え
ば、一方通行、道路種別（国道、高速道路、主要地方道
路等）、幅員、車線数、速度規制等などからなる。

【００１３】また、本図（ｂ）に示すように、道路デー
タは細分化されたリンクの両端のノードに関する複数の
ノードデータからなる。各ノードデータは該各ノードに
接続する複数のリンクＮｏ．からなる。図５はリンク長
を補正する重みの第１の例を示す図である。前記リンク
長重み補正部３１では、本図（ａ）に示すように、道路
種別による重みｗａとして、例えば、高速道路の場合に
は「６」、国道の場合には「３」、主要地方道路の場合
には「２」と決め、予めテーブル化して用意する。さら
に本図（ｂ）に示すように、幅員により重みｗｂとし
て、例えば、１．５〜３．０ｍの場合には「１」、３．
０〜５．５ｍの場合には「２」、５．５〜１３の場合に
は「３」、…、１００ｍの場合には「１０」と決め、予
めテーブル化して用意する。そしてリンク長重み補正部
３１ではリンクの実際の長さをＬとし補正後のリンク長
をＬ’として、これを以下のように設定する。

【００１４】Ｌ’＝Ｌ／（ｗａ・ｗｂ） …（１）本実施例によれば、補正リンク長Ｌ’は高速道路では他
の道路と比較しリンク長が見かけ上小さくなり、さらに
幅員が広い道路ではリンク長が見かけ上小さくなる。前
記経路探索部３２ではこのような補正リンク長を用いて
道路種別、幅員を考慮してダイクストラ法により経路探
索を行うことができる。このため走りやすい経路を求め
ることができ、かつ時間的にも最短な経路を求めること
ができる。なお、一方通行の逆走となる経路は探索対象
外とする。

【００１５】図６はリンク長を補正する重みの第２の例
を示す図である。本図では道路の曲がりによる重みの付
け方を説明する。あるノードまでの経路長が確定した時
のリンク方位をｄ’とする。次に探索するリンクの方位
をｄとする。この時道路の曲がりを以下の式Δｄで定義
する。 Δｄ＝ｄ−ｄ’ 図６では、この曲がりΔｄを横軸にとり、道路の曲がり
に関する重みｗｃを決める。曲がりΔｄが０°付近では
ｍｉｎであり、大きくなるにつれて重みｗｃが大きくな
るようにするが一般的には左折時よりも右折時の方が所
要時間がかかるため右折時の方が傾きを大きくしてあ
る。曲がりΔｄ＝±１８０°付近の重みｗｃがｍａｘに
なっているのはＵターンするような経路を回避するため
である。この重みｗｃと第１の例の場合の重みとを合成
して補正リンク長Ｌ’を以下のように決める。

【００１６】Ｌ’＝Ｌ／（ｗａ・ｗｂ）＋ｗｃ …
（２）以上の説明ではリンク長重み補正部３２で補正リンクを
形成していたが、このリンク長重み補正部３２に代わ
り、地図、道路に関するデータベースＤＢを記憶媒体１
に作成時に重みを付けた補正リンク長をデータベース内
に格納するようにしてもよい。このようにして、処理の
高速化を図ることができる。さらに前記重みｗａ、ｗ
ｂ、ｗｃは静的な情報であるので、地図、道路に関する
データベースＤＢを記憶媒体１に作成時に、予め区間平
均速度（ｗａ、ｗｂに関し）、区間平均所要時間（ｗｃ
に関し）として、データベースに格納しておいてもよ
い。これにより処理速度は向上する。

【００１７】図７はリンク長を補正する重みの第３の例
を示す図である。本図では道路の渋滞による重みの付け
方につき説明する。ビーコンからロケーション装置を介
した路車間通信により交通渋滞情報が得られる。渋滞情
報によりリンク長の重みを以下のようにする。すなわち
渋滞区間しか分からないときには渋滞区間の重みｗｄを
ある定数まで下げる。渋滞区間と渋滞の度合い（移動速
度）が分かるときは、本図に示すように、渋滞区間の重
みｗｄはその度合いに比例した値に決める。この時補正
リンク長は以下のようになる。

【００１８】Ｌ’＝Ｌ／ｗｄさらに第１及び２の例と合成して、Ｌ’＝Ｌ／（ｗａ・ｗｂ・ｗｄ）＋ｗｃ …（３）図３に戻り経路探索装置３は所要推定時間算出部３３を
具備する。道路種別により重みｗａ、幅員により重みｗ
ｂ、は一般的に速度に比例し、道路の曲がりΔｄは時間
に比例する。例えば、一般的に高速道路＞国道＞主要地
方道路＞その他の順で速く走れる。また幅員が広い程、
道が曲がっていない程速く走れる。そこで所要推定時間
算出部３３では、適切に重みを規格化し、上記式（２）
を以下のように変形して、推定所要時間を算出する。

【００１９】推定所要時間＝Ｌ／（ｗａ・ｗｂ・Ａ）＋ｗｃ・Ｂ＝距離／推定速度＋推定時間ここに、Ａ、Ｂは規格定数である。このリンク毎の推定
所要時間を累積すると、その累積値が出発点から目標値
点までの推定所要時間となる。この推定所要時間をユー
ザに提示することにより、ユーザの運転計画を支援する
ことができる。さらに車両が移動する毎に移動に要した
時間を減算し、残りの所要時間も算出する。また車両が
存在する道路が分かる場合は、探索結果より目標位置ま
での推定所要時間すなわち約何ｋｍ／ｈで走行すれば所
要時間通りに目標位置に到達できるという情報や残りの
実走行距離も提示する。なお、重み付けする要素として
は、他にリンクの形状データから右左折を判断し、右折
の重みを左折のものよりも大きくする補正をしてもよ
い。さらに交通渋滞の情報を入力し、渋滞が発生してい
るリンクの重みを他のものより大きくする補正をしても
よい。

【００２０】

【発明の効果】以上説明したように本発明によれば、各
複数のリンクに対応するリンク長が高速道路から一般地
方道路になるにつれて大きくなるように道路種別で重み
補正がなされ、さらに広い幅の道路から狭い幅の道路に
なるつれて大きくなるように幅員で重み補正がなされた
補正リンク長を形成することにより、走り易い経路を算
出できるようになる。また補正リンク長が大きくなるに
つれてリンクを走行する車両の所要時間が大きくなるよ
うに規格化し、探索された経路について出発位置から目
標位置までのリンクの前記所要時間を累積した推定所要
時間を表示し、前記補正リンク長が大きくなるにつれて
リンクを走行する速度が小さくなるように規格化し、探
索された経路についてリンクの速度と現在位置から目標
位置までの推定所要時間を表示することにより、ユーザ
が運転計画の立案を支援できるようになる。

【図面の簡単な説明】

【図１】本発明の実施例に係るナビゲーション装置を示
す図である。

【図２】図１の表示装置４に表示される道路地図の例を
示す図である。

【図３】図１の経路探索装置の構成を示す図である。

【図４】道路データにおけるリンクデータ及びノードデ
ータを説明する図である。

【図５】リンク長を補正する重みの第１の例を示す図で
ある。

【図６】リンク長を補正する重みの第２の例を示す図で
ある。

【図７】リンク長を補正する重みの第３の例を示す図で
ある。

【符号の説明】

１…記憶媒体２…ロケーション装置３…経路探索装置４…表示装置３１…リンク長重み補正部３２…経路探索部３３…所要推定時間算出部

Claims

【特許請求の範囲】

【請求項１】道路を複数のリンクに細分化し各リンク
毎に道路データを記憶する記憶媒体（１）を有し、前記
道路データに基づき車両の出発位置から目標位置までの
最短の経路を探索する経路探索装置であって、各前記複数のリンクに対応するリンク長が高速道路から
一般地方道路になるにつれて大きくなるように道路種別
で重み補正がなされ、さらに広い幅の道路から狭い幅の
道路になるつれて大きくなるように幅員で重み補正がな
された補正リンク長を形成するリンク長重み補正部（３
１）と、前記補正リンク長を用いて、出発位置から目標位置まで
の最短の経路を探索する探索部（３２）と、探索された経路について出発位置から目標位置までの各
リンクの前記所要時間を累積した推定所要時間を算出
し、さらに各リンクでの前記補正リンク長と現在位置か
ら目標位置までの距離、推定所要時間を算出し表示させ
る所要推定時間算出部（３３）とを備えることを特徴と
する経路探索装置。
【請求項２】道路を複数のリンクに細分化し各リンク
毎に道路データを記憶する記憶媒体（１）を有し、前記
道路データに基づき車両の出発位置から目標位置までの
最短の経路を探索する経路探索装置であって、前記記憶媒体（１）は各前記複数のリンクに対応するリ
ンク長が高速道路から一般地方道路になるにつれて大き
くなるように道路種別で重み補正をし、さらに道路の幅
が狭くなるにつれて大きくなるように幅員で重み補正し
た補正リンク長を記憶する経路探索装置。
【請求項３】所要推定時間算出部（３３）では前記補
正リンク長が大きくなるにつれてリンクを走行する車両
の所要時間が大きくなるように規格化する請求項１又は
２記載の経路探索装置。
【請求項４】所要推定時間算出部（３３）では前記補
正リンク長が大きくなるにつれてリンクを走行する車両
の速度が小さくなるように規格化する請求項１又は２記
載の経路探索装置。
【請求項５】リンク長重み補正部（３１）ではリンク
の右左折形状に関し、右折の重みが左折のものよりも大
きくなるように補正する請求項１記載の経路探索装置。
【請求項６】リンク長重み補正部（３１）では渋滞が
発生しているリンクの重みを大きくするように補正する
請求項１記載の経路探索装置。