JPH04280287A - 車両用走行経路探索装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は車両用走行経路探索装置
、特にナビゲーションシステムに組み込まれ車両運転者
に出発地から目的地までの最短経路を教示するための車
両用走行経路探索装置に関する。

【０００２】

【従来の技術】従来より、車両の運転席近傍に設置され
たＣＲＴ等の表示器に車両の現在位置近傍の地名等を表
示し車両の目的地への走行を案内補助するナビゲーショ
ンシステムが知られている。このナビゲーションシステ
ムにおいては、如何に早くかつ確実に最適経路を探索し
て運転者に教示することができるかが課題となっている
。　　通常、出発地及び目的地間の最短経路が教示すべ
き最適経路となるが、このように複数のルートの中から
最短経路を探索する方法はグラフ理論として知られてお
り、種々の方法が確立されており、中でもダイキストラ
法等のラベル確定法は計算機処理に適しかつ効率が良い
という利点を有しているため、ナビゲーション用として
用いられることが多い。

【０００３】しかしながら、例えばダイキストラ法では
出発地から目的地までの各地点にラベリングを行う際、
出発地から全方角に向けて行われるため最短経路探索に
はほとんど関与しない方角の地点までラベリングが行わ
れ、計算効率が低下してしまう問題があった（探索時間
はラベリングを行う地点数にほぼ比例する）。そこで、
このような計算効率の低下を防ぐ装置及び方法が従来よ
り提案されている。

【０００４】例えば、特開昭６３−２０７００号公報に
おいては、最短経路を求める際出発地及び目的地を含む
領域を設定し、予め探索の対象とする領域を長方形領域
や楕円領域に制限してしまうことにより余分な地点を探
索せず計算効率を向上させる車両用経路誘導装置の誘導
経路設定装置が開示されている。

【０００５】また、特開平２−２６００００号公報にお
いては、各地点と目的地との直線距離を算出し、この直
線距離に応じて次の地点までの重み付けを行い最短経路
を追跡する移動経路探索方法及び装置が開示されている
。

【０００６】

【発明が解決しようとする課題】しかしながら、予め探
索領域を設定して探索範囲を制限する方法では、探索の
際各地点がその領域内にあるかどうかをその都度判定し
なければならないという問題があり、また、特に出発地
と目的地との間に海や川、山地などが存在する場合には
迂回路が最短経路となる場合が少なくないが、このよう
に探索領域を限定してしまうとこの最短経路が含まれな
くなるという問題があった（探索領域を広げれば、処理
時間の短縮という利点が失われる）。

【０００７】さらに、各地点と目的地との直線距離に応
じて次の地点までの重み付けを行う方法では、このよう
に予め探索領域を指定して制限することなく探索領域を
重み付けにより限定することができるが、やはりその都
度各地点に与えられた座標データから目的地までの直線
距離を算出して重み付けしなけれがならず、接続各地点
の座標データをその都度用いなければならず、処理に時
間がかかる問題があった。

【０００８】本発明は上記従来技術の有する課題に鑑み
なされたものであり、その目的は高速かつ確実に最短経
路を探索して運転者に教示することが可能な車両用走行
経路探索装置を提供することにある。

【０００９】

【課題を解決するための手段】上記目的を達成するため
に、本発明に係る車両用走行経路探索装置は、予め与え
られた地点間の接続距離及び接続方位を各地点の接続デ
ータとして格納する記憶手段と、出発地及び目的地を指
定する地点選択手段と、各地点における接続地点の接続
方位及び前記指定された目的地の方位の差に基づき、接
続地点が目的地の方位に位置するほど重み付けが小さく
なるように各地点における接続地点の接続距離を重み付
け評価し、前記指定された出発地と目的地間の最小累積
接続距離を選択する演算手段とを有することを特徴とす
る。

【００１０】

【作用】本発明の車両用走行経路探索装置はこのような
構成を有しており、予め地点間の接続距離及び接続方位
を各地点の接続データとして記憶装置に格納しておき、
ダイキストラ法等で最短経路を探索する際、接続地点の
方位と目的地との方位に基づきその接続地点の接続距離
を重み付け評価するのである。

【００１１】すると、各接続地点は目的地の方位に位置
するほどその接続距離が小さく評価され、逆に目的地と
異なる方位に位置する場合にはその接続距離が大きく評
価されることとなる。

【００１２】従って、接続距離の大きな反対方位に位置
する接続地点は探索されなくなり、結果的に探索領域を
目的地の方位に限定したことと等価となり、高速に最短
経路を探索することができる。

【００１３】また、接続方位のデータは各地点の接続デ
ータとして与えられているため、その都度接続地点の座
標データ等をアクセスする必要がなく、処理に時間を要
することもない。

【００１４】

【実施例】以下、図面を用いながら本発明に係る車両用
走行経路探索装置の一実施例を説明する。

【００１５】図１には本発明の車両用走行経路探索装置
をナビゲーションシステムに適用した実施例の構成ブロ
ック図が示されている。図において、ＣＤ−ＲＯＭ等の
補助記憶装置１０には運転席近傍に設けられたディスプ
レイ１２に描画するための地図データや後述する走行経
路探索用の道路ネットワーク（接続データ）が格納され
ている。また、運転席近傍には入力装置１４が設けられ
、運転者により出発地及び目的地が設定されるとシステ
ムＲＯＭ１５、ＲＡＭ１７及び演算処理装置１６にて最
短経路を探索し、ＶＲＡＭ２３及びディスプレイ１２を
介して運転者に探索結果を表示する構成である。

【００１６】なお、本実施例では距離センサ１８及び方
位センサ２０を設け、その検出出力をインターフェース
２２を介して演算処理装置１６に入力することにより現
在位置を算出する構成も採用しており、このようにして
算出された現在位置を出発地として用いてもよい。

【００１７】図２には本実施例の補助記憶装置１０に格
納された道路ネットワークのデータフォーマットが示さ
れている。この道路ネットワークは交差点毎に構成され
、図に示されるように各交差点の位置を示す座標データ
（ｘ座標、ｙ座標）、この交差点における接続道路数、
各接続道路における接続先の交差点番号、接続先の交差
点までの距離、接続道路の方位が格納されている。 なお、接続先の交差点までの距離の代わりに走行所要時
間を格納してもよい。

【００１８】このように、補助記憶装置１０には道路ネ
ットワークが格納され、この道路ネットワークをもとに
出発地から目的地までの最短経路を探索するのである。 以下、探索処理を詳細に説明する。

【００１９】前述したように、最短経路探索方法はグラ
フ理論等として種々の方法が確立されており、特にナビ
ゲーションにおいてはラベル確定法が有利であることか
ら、本実施例においてもダイキストラ法を用いて最短経
路を探索することとしている。　　ダイキストラ法にお
いては、全ての交差点に出発地からの累積距離を格納す
るためのラベルを付与し、ラベルの値の小さい交差点か
ら順次接続道路を展開して目的地のラベルが最小となっ
た時に最短経路が得られるものである。

【００２０】図５にダイキストラ法の処理フローチャー
ト、そして図６に道路ネットワークの一例を示す。図に
おいて、「ノード」はグラフの頂点である交差点を表し
、「リンク」はグラフの枝である交差点間の道路を表す
。また、「コスト」は各ノード間の距離を表し、「ラベ
ル」は各ノードに付与したデータ格納領域を表し、本実
施例の場合は出発地からの累積距離である。そして、ラ
ベルの確定したノードの集合がＴ、ラベルが一時ついた
ノードの集合がＷである。

【００２１】まず、Ｓ１０１においてノード１のラベル
をＬ（１）＝０とし、それ以外のノードのラベルを無限
大とする。次にＳ１０２にてＷの要素の内、最もラベル
の小さいノードｐを見つけ、ＷからＴに移す。そして、
Ｓ１０３にてこのｐが目的点であるか否かを判定し、Ｎ
Ｏである場合にはＳ１０４にてｐに隣接しかつＴの要素
でないノードｑが存在するか否かを判定する。存在する
場合には次のＳ１０５に移行してノードｐのラベルＬ（
ｐ）にｐｑ間の距離Ｌｐｑを付加し、ｑのラベルＬ（ｑ
）と比較する。そして、Ｌ（ｑ）＞Ｌ（ｐ）＋Ｌｐｑで
ある場合には、Ｓ１０６に移行してＬ（ｑ）＝Ｌ（ｐ）
＋Ｌｐｑとし、Ｗにこのｑを加える。そして、以上の処
理をｐが目的点となるまで繰り返すことにより最短経路
が算出されるのである。

【００２２】図６を用いて具体的に説明すると以下のよ
うになる。すなわち、出発点がノード１であるから、ま
ず、 Ｌ（１）＝０、Ｌ（２）＝…、Ｌ（９）＝無限大　　Ｔ
＝｛　　｝、Ｗ＝｛１｝となる。次に、ノード１につい
て展開すると、 Ｌ（２）＝３、Ｌ（３）＝６、Ｌ（４）＝７　　Ｔ＝｛
１｝、Ｗ＝｛２，３，４｝となる。次にノード１に隣接
するノード２について展開すると、 Ｌ（３）＝４、Ｌ（５）＝７　　Ｔ＝｛１，２｝、Ｗ＝
｛３，４，５｝となる。なお、ここで、ノード１の展開
時においてはＬ（３）＝６であるのにノード２の展開時
においては６＞３＋１であるためＳ１０５にてＹＥＳと
判定され、Ｓ１０６でＬ（３）＝４に更新されることに
注目すべきである。以下、順次展開していくと、ノード
３を展開：Ｌ（６）＝６、Ｔ＝｛１，２，３｝、Ｗ＝｛
６，４，５｝ ノード６を展開：Ｌ（８）＝７、Ｌ（９）＝８、Ｔ＝｛
１，２，３，６｝、Ｗ＝｛４，５，８，９｝ノード４を
展開：Ｌ（７）＝１１、Ｔ＝｛１，２，３，４，６｝、
Ｗ＝｛５，８，９，７｝ ノード５を展開：更新なし、Ｔ＝｛１，２，３，４，５
，６｝、Ｗ＝｛８，９，７｝ ノード８を展開：更新なし、Ｔ＝｛１，２，３，４，５
，６，８｝、Ｗ＝｛９，７｝ となる。そして、次の最小ラベルノード９が目的地であ
るのでＳ１０３にてＹＥＳと判定され、探索は終了する
。

【００２３】この結果、最短経路はノード１→ノード２
→ノード３→ノード６→ノード９となり、この経路のコ
ストは８となる。

【００２４】このように、ダイキストラ法ではラベル、
すなわち出発点からの累積距離の少ない順に順次ノード
を展開していくため、図７に示すように出発点から目的
点まで同心円上に探索され、出発地から見て目的地と反
対方位にあるＡ点も探索されるので処理に時間がかかっ
てしまうのである。

【００２５】そこで、本実施例では各ノードを展開する
時に道路の方角が目的地からかけ離れるほど道路の長さ
を実際より長くして計算を行うことにより不要な領域の
交差点まで展開されることのないようにするのである。

【００２６】図３には本実施例の演算処理装置１６にて
行われる処理フローチャートが示されている。図におい
て、まず、Ｓ２０１にて入力装置１４から運転者が出発
地及び目的地を指定すると、Ｓ２０２にて出発地に対す
る目的地の方位が算出される。この方位算出は、図２に
示されたデータフォーマットにおいて交差点の（ｘ座標
、ｙ座標）を用いて行われる。本実施例においては図４
に示される位置関係に出発地及び目的地がある場合を考
え、出発地に対する目的地の方位が上方向（真北）を基
準として７５°であるとする。

【００２７】出発地に対する方位が算出された後、Ｓ２
０３にて補助記憶装置１０に格納された全交差点のラベ
ルを初期化する。すなわち、出発地のラベルを１とし、
それ以外の交差点のラベルを無限大とする。そして、Ｓ
２０４で出発地を次の展開交差点とし、Ｓ２０５で展開
する道路の方位と目的地への方位の差が所定値以内であ
るか否かが判定される。

【００２８】例えば、図４において、展開する交差点が
Ａ交差点である場合、この交差点に接続する道路は５個
あり、各接続道路に対して 接続道路１：接続先交差点Ｂ、距離２ｋｍ、方位２５０
° 接続道路２：接続先交差点Ｃ、距離２ｋｍ、方位１７０
° 接続道路３：接続先交差点Ｄ、距離３ｋｍ、方位８５°
接続道路４：接続先交差点Ｅ、距離４ｋｍ、方位３５０
° 接続道路５：接続先交差点Ｆ、距離３ｋｍ、方位２９０
° なる接続データが交差点Ａに与えられている。そして、
各接続道路の方位と目的地への方位の差はそれぞれ、接
続道路１：１７５° 接続道路２：９５° 接続道路３：１０° 接続道路４：８５° 接続道路５：１４５° であり、所定値を±６０゜の範囲とすると接続道路３の
みがこのステップでＹＥＳと判定され、他の接続道路で
はＮＯと判定されることになる。そして、ＮＯと判定さ
れた場合にはＳ２０６に移行し、この方位の差に応じて
距離に重み付けを行う。本実施例においては、この方位
差が大なるほど距離が大となるように重み付けを行うべ
く、 方位差±６０°〜±１２０°重み３ 方位差±１２０°〜±１８０°重み１０としている。

【００２９】すると、接続データは新たに接続道路１：
接続先交差点Ｂ、距離２０ｋｍ、方位２５０° 接続道路２：接続先交差点Ｃ、距離６ｋｍ、方位１７０
° 接続道路３：接続先交差点Ｄ、距離３ｋｍ、方位８５°
接続道路４：接続先交差点Ｅ、距離１２ｋｍ，方位３５
０° 接続道路５：接続先交差点Ｆ、距離３０ｋｍ、方位２９
０° となり、目的地の方位とは反対方向に位置する交差点Ｂ
，Ｅ，Ｆはその接続距離が拡大されることが理解される
。

【００３０】従って、Ａ交差点までの累積距離が２６ｋ
ｍであった場合には Ｂ点：展開済み Ｃ点：２６＋６＝３２ｋｍ Ｄ点：２６＋３＝２９ｋｍ Ｅ点：２６＋１２＝３８ｋｍ Ｆ点：２６＋３０＝５６ｋｍ と各交差点のラベルは更新されることとなる。

【００３１】従って、順次各交差点についてそのラベル
の値の小さい交差点から順次接続道路を展開して目的地
まで行うと（Ｓ２０５〜Ｓ２１１）、目的地の方位にあ
る接続道路は次々に展開されて行くが、反対方位にある
接続道路は本実施例の場合ではほとんど展開されないこ
とになり（１０ｋｍ先の目的地まで探索した時には逆方
向には１ｋｍしか進んでいないことになる）、結局探索
領域を限定することが可能となる。そして、目的地まで
探索が完了した時には、ディスプレイ１２上に探索結果
を表示して運転者に教示することにより、確実に車両を
目的地に誘導することができる。

【００３２】なお、本実施例においては、出発地と目的
地との方位、及び各接続道路の方位の差を求めて重み付
けを行ったが、その都度各交差点における目的地の方位
、及び各接続道路の方位の差を求めて重み付けを行って
もよい。すなわち、各交差点のｘ座標、ｙ座標及び目標
地のｘ座標及びｙ座標から各交差点に対する目的地の方
位を算出し、この算出方位と各接続道路の方位との差を
求めて重み付けを行うのである。このように重み付けを
行うと探索範囲が更に限定され、処理時間の短縮化を図
ることができる。

【００３３】また、本実施例ではダイキストラ法を用い
た例を示したが、双方向探索のニコルソン法にも適用で
きることはいうまでもない。

【００３４】

【発明の効果】以上説明したように、本発明の車両用走
行経路探索装置によれば、各地点における接続データと
して格納されている接続地点の方位を用い目的地に対し
て逆方位の探索範囲を限定するため、高速に最短経路を
探索することが可能となる。

【００３５】また、右折や左折の回数の多い経路は自然
に除外されるため、目的地までできるだけ直進していけ
る経路を選択することができる。

【００３６】さらに、方位に応じた重み付けを行う際、
例えば出発地や目的地の近くでは重みを小さくすること
により少し大まわりをして高速のインターへ進入する等
の経路を自動的に選択することも可能となる。

【図面の簡単な説明】

【図１】本発明の一実施例の構成ブロック図。

【図２】同実施例の道路ネットワークのデータフォーマ
ット図。

【図３】同実施例の処理フローチャート図。

【図４】同実施例の重み付け説明図。

【図５】ダイキストラ法の処理フローチャート図。

【図６】ダイキストラ法の処理説明図。

【図７】ダイキストラ法による探索範囲説明図。

【符号の説明】

１０　　補助記憶装置 １２　　ディスプレイ １４　　入力装置 １６　　演算処理装置

Claims (1)

【特許請求の範囲】
1. 【請求項１】予め与えられた地点間の接続距離及び接続
   方位を各地点の接続データとして格納する記憶手段と、
   出発地及び目的地を指定する地点選択手段と、各地点に
   おける接続地点の接続方位及び前記指定された目的地の
   方位の差に基づき、接続地点が目的地の方位に位置する
   ほどその重み付けが小さくなるように各地点における接
   続地点の接続距離を重み付け評価し、前記指定された出
   発地と目的地間の最小累積接続距離を選択する演算手段
   と、を有することを特徴とする車両用走行経路探索装置
   。