JP2761359B2 - 経路探索装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、地図画面上に自車位置
や目的地を表示することができる、いわゆるナビゲーシ
ョン装置で好適に実施され、目的地や経由地などまでの
経路を探索するための経路探索装置に関する。

【０００２】

【従来の技術】ナビゲーション装置は、自動車に搭載さ
れ、地図画面上に自車位置を併せて表示し、その表示を
自車の走行に伴って更新してゆく装置である。また近
年、このナビゲーション装置において、現在位置および
目的地または経由地を入力することによって、現在位置
からその目的地または経由地までで、たとえば最短距離
となる経路が演算されて、推薦経路として表示するよう
にした経路探索装置が付加されるようになってきてい
る。

【０００３】前記地図画面の元となる地図データは、大
略的に、陸地、海および川などの地形データと、道路デ
ータとから構成されている。前記道路データは、カーブ
を折線近似した折点または交差点などの道路上の地点を
表すノードデータと、２つの地点を接続する道路の経路
長および属性を表すリンクデータとを含んで構成されて
いる。

【０００４】経路探索装置においては、一般的にダイク
ストラ法が用いられる。このダイクストラ法では、上述
したリンクデータとノードデータとに基づき、探索開始
点である出発地点と目的地点までの経路に関し、ノード
データ→リンクデータ→ノードデータ→リンクデータ…
という順序で経路長が最短となる経路を算出している。
この最短経路は、ノードデータによってリンク（道路）
を接続していき、前記リンクデータにおける経路長を出
発点から目的点までの複数の経路について累積し、その
中で最短距離のものとして求められている。

【０００５】

【発明が解決しようとする課題】経路探索においては、
探索の起点が定められ、起点に接続される複数の地点が
探索点となり、起点から探索点までの経路長が最も短い
ものが最短経路として選択される。経路探索に用いる経
路長として現実の経路長（地図データとして記憶されて
いるデータ）をそのまま用いた場合、必ずしも最短経路
が選択されない場合がある。たとえば、高速道路のイン
ターチェンジ付近において、高速道路の出口と入口とが
接続している場合などは高速道路を通るよりも、一度高
速道路を出てからもう一度入り直した方が経路長として
は短くなるような場合がある。たとえば入口と出口とが
直線的に接続されており、高速道路が湾曲しているよう
な場合である。このような経路が探索されたとしても実
用性がなく、利用することができない。

【０００６】本発明の目的は、より実用性の高い経路探
索を実現することができる経路探索装置を提供すること
である。

【０００７】

【課題を解決するための手段】本発明は、道路を折線近
似した折点または交差点などの道路上の地点を表すノー
ドデータと、２つの地点を接続する道路の経路長および
属性を表すリンクデータとを含んで構成される地図デー
タに基づいて、指定された出発地点から目的地点までの
最短経路を探索する経路探索装置において、探索の起点
に接続された探索点の中から、起点からの経路長の最も
短い探索点を次の起点として選択する探索処理を、出発
地点を最初の起点として開始し、探索点と目的地点とが
一致するまで繰返し実行する探索手段と、探索の起点と
なる地点に接続されている探索点となる地点を表すノー
ドデータと、起点および探索点に接続されている道路に
対応するリンクデータとを地図データから読出して記憶
する記憶手段と、出発地点から探索点までの距離と、目
的地点から探索点までの距離との和を求め、前記和が大
きいほど起点と探索点との経路長を長くする重み付けを
行う補正手段とを含むことを特徴とする経路探索装置で
ある。また本発明は、前記補正手段は、出発地点から目
的地点までの距離に応じて重み付けの度合を変更するこ
とを特徴とする。また本発明は、前記補正手段は、出発
地点から探索点までの距離または目的地点から探索点ま
での距離が、予め定める範囲内であるときは重み付けを
行わないことを特徴とする。また本発明は、道路を折線
近似した折点または交差点などの道路上の地点を表すノ
ードデータと、２つの地点を接続する道路の経路長およ
び属性を表すリンクデータとを含んで構成される地図デ
ータに基づいて、指定された出発地点から目的地点まで
の最短経路を探索する経路探索装置において、探索の起
点に接続された探索点の中から、起点からの経路長の最
も短い探索点を次の起点として選択する探索処理を、出
発地点を最初の起点として開始し、探索点と目的地点と
が一致するまで繰返し実行する探索手段と、探索の起点
となる地点に接続されている探索点となる地点を表すノ
ードデータと、起点および探索点に接続されている道路
に対応するリンクデータとを地図データから読出して記
憶する記憶手段と、探索点が３つ以上の道路が接続され
ている交差点であるときは、起点と探索点との経路長を
長くする重み付けを行う補正手段とを含むことを特徴と
する経路探索装置である。また本発明は、前記補正手段
は、交差点に接続されている道路の属性に基づいて重み
付けの度合を変更することを特徴とする。また本発明
は、道路を折線近似した折点または交差点などの道路上
の地点を表すノードデータと、２つの地点を接続する道
路の経路長および属性を表すリンクデータとを含んで構
成される地図データに基づいて、指定された出発地点か
ら目的地点までの最短経路を探索する経路探索装置にお
いて、探索の起点に接続された探索点の中から、起点か
らの経路長の最も短い探索点を次の起点として選択する
探索処理を、出発地点を最初の起点として開始し、探索
点と目的地点とが一致するまで繰返し実行する探索手段
と、探索の起点となる地点に接続されている探索点とな
る地点を表すノードデータと、起点および探索点に接続
されている道路に対応するリンクデータとを地図データ
から読出して記憶する記憶手段と、探索点に経路探索に
おいて優先される属性を持つ道路が接続されているとき
は、起点と探索点との経路長を短くする重み付けを行う
補正手段とを含むことを特徴とする経路探索装置であ
る。

【０００８】

【作用】本発明に従えば、経路探索の起点となる地点に
接続されている複数の探索点と出発地点までの距離と、
前記探索点と目的地点までの距離との和が、大きくなる
につれて、起点と探索点との経路長に重み付けを行い、
実際の経路長よりも長くする。このような重み付けを施
すことによって、経路探索の範囲が出発地点と目的地点
とを含んだ楕円状の領域に限定されることになり、探索
の起点となる地点から探索点までの距離が短い場合であ
っても、出発地点または目的地点から離れる方向に延び
る経路を選択することが防止され、より実用的な経路探
索を少ないデータ量で実現することができる。重み付け
は、距離の和に応じて連続的に変化させてもよいし、あ
るいは段階的に変化させるようにしてもよい。

【０００９】また好ましくは、出発地点から目的地点ま
での距離に応じて重み付けの度合を変更する。たとえば
比較的近距離の経路探索であれば、前記距離の和が比較
的大きくなったときに重み付けを行うようにし、これに
よって経路探索の範囲は円形に近い領域となる。逆に比
較的遠距離の経路探索であれば、探索範囲が長円状の領
域になるように前記距離の和が比較的小さい段階で重み
付けを行う。近距離の経路探索であれば、経路探索を広
げたとしても用いるデータ量は少なく、使用するメモリ
容量は増加しない。また近距離の経路探索において、探
索範囲を長円状に限定してしまうと、たとえば目的地と
は反対方向に高速道路などの短時間で目的地まで到達す
ることができる道路が存在していても、この高速道路が
探索範囲に含まれない場合があり、実用的な経路探索は
行われない場合がある。逆に遠距離の経路探索であれ
ば、探索範囲が円形になればなるほど、用いるデータ量
が多くなり、メモリ量は増大する。したがってある程度
方向付けをして経路探索を行うことによって、より実用
的な経路探索が実現される。

【００１０】さらに好ましくは、出発地点から探索点ま
での距離または目的地点から探索地点までの距離が予め
定める範囲内であるときは上記重み付けを行わない。こ
のような処理を行うことによって、たとえば出発地点か
ら目的地点までの方向とは反対側に高速道路などが存在
する場合、この高速道路が経路探索の範囲から外れるこ
とが防止され、より実用的な経路探索を実現することが
できる。

【００１１】また本発明に従えば、経路探索の起点とな
る地点に接続されている探索点が３つ以上の道路が接続
されている交差点であるときは、起点と探索点との経路
長を重み付けを行うことによって実際の経路長よりも長
くする。一般に交差点では当該交差点に進入し、交差点
に接続されている進入路とは異なる道路に移行する場
合、他の走行車両との関係で待ち時間が生じる場合が多
い。特に信号機などが交差点に設置されている場合は、
その信号機の持ち時間だけ待機する必要がある。したが
って経路長そのものは短くても、探索点である交差点を
通過する際の時間が必要となり、この時間を考慮して重
み付けを行い実際の経路長よりも長くする。これによっ
て、待ち時間が生じる交差点を選択する場合が少なくな
り、より実用的な経路探索を実現することができる。

【００１２】また好ましくは、探索点が交差点である場
合の重み付けは、当該交差点に接続されている道路の属
性に基づいて変更する。たとえば交差点に接続されてい
る道路が一般道路と国道である場合、一般道路から国道
へ進入する際には、一般道路同士の交差点に比べて待ち
時間が長くなる場合がある。したがって、交差点の種類
に応じて重み付けの度合を変更することによって、より
実用性の高い経路探索を実現することができる。

【００１３】さらに本発明に従えば、経路探索の起点と
なる地点に接続されている探索点に、経路探索において
優先される属性を持つ道路が接続されているときは、起
点と探索点との経路長を短くする。たとえば、経路探索
において高速道路や有料道路を用いて目的地まで行く経
路を探索しようとする場合、単純に短い経路長のみを探
索していたのでは、必ずしも高速道路や有料道路を選択
せずに経路探索が進行する場合がある。したがって、探
索点に優先される属性を持つ道路が接続されている場
合、たとえば探索点が高速道路のインターチェンジであ
る場合、あるいは有料道路の料金所である場合には、起
点と探索点との経路長を短くする重み付けを行い、当該
探索点が選択されるように経路長を変更する。これによ
って、ユーザが望む経路探索を確実に実現することがで
き、より実用性の高い経路探索が可能となる。

【００１４】

【実施例】図１は、本発明の一実施例である経路探索装
置が用いられるナビゲーション装置１の電気的構成を示
すブロック図である。このナビゲーション装置１は、自
動車に搭載されて、現在位置表示や目的地までの経路案
内表示を行い、運転者の進路決定などに役立てられる。

【００１５】概略的にこのナビゲーション装置１では、
操作キー２への入力操作に応答して、マイクロコンピュ
ータなどで実現される中央処理装置３が通信バス４を介
してＣＤ−ＲＯＭ装置５へ所望とする地域の地図データ
の読取りを指示する。その指示に応答して、処理回路６
が、デコーダ７を介して、ＣＤ−ＲＯＭディスク８に記
録されている地図データから対応する地域の地図データ
を読出す。処理回路６から前記通信バス４を介して入力
された地図データに対応して、前記中央処理装置３が、
表示駆動回路９を介して、液晶表示装置などで実現され
る表示装置１０を表示駆動することによって、前記所望
とする地域の地図画面表示は実現される。

【００１６】また、ナビゲーション装置１には、ＧＰＳ
(Global Positioning System）受信機１１が設けられて
おり、このＧＰＳ受信機１１は、ＧＰＳアンテナ１２で
受信された地球周回軌道を回る測位衛星からの信号に基
づいて三角測量を行い、自車の緯度、経度、高度および
走行速度などを演算し、その演算結果を前記通信バス４
を介して中央処理装置３へ出力する。

【００１７】さらにナビゲーション装置１には、地磁気
センサ１３と、ジャイロセンサ１４と、車輪速センサ１
５とが備えられている。地磁気センサ１３は車両の進行
方向を検出し、ジャイロセンサ１４は車両の姿勢変化を
検出し、車輪速センサ１５は車体速度を検出する。セン
サ１３，１４の検出結果は、それぞれアナログ／デジタ
ル変換器１６，１７でデジタル値に変換されて処理回路
１９に入力される。また車輪速センサ１５からの車速パ
ルスは、パルスカウンタ１８でカウントされ、処理回路
１９に入力される。このとき、後退位置検出器２５によ
って変速機の変速段が後退位置であることが検出される
と、前記カウント値は負の値で表される。

【００１８】処理回路１９へは前記中央処理装置３から
操作キー２に入力された自車位置などに関するデータが
入力され、これによって該処理回路１９は、前記各セン
サ１３〜１５の検出結果から現在の自車位置を推測演算
し、その演算結果を中央処理装置３へ出力する。このよ
うにして、たとえばビル影、高架下またはトンネル内な
どで前記ＧＰＳ受信機１１によって正確な自車位置を計
測することが不可能な地点においても、いわゆる推測航
法によって正確に自車位置を計測することができる。

【００１９】中央処理装置３に関連してメモリ２０が設
けられている。このメモリ２０には、後述するように選
択された経路、目的地や経由地などが記憶されるととも
に、探索の始点または終点となった地点を記憶して保持
している。

【００２０】図２は、上述のように構成されたナビゲー
ション装置１の経路案内動作を説明するための機能ブロ
ック図である。前記操作キー２に、ＧＰＳ受信機１１お
よび処理回路１９などの入力部３１から現在位置および
目的地または経由地が入力されると、探索を開始する前
に経路探索装置３２の地点設定部３３が、入力された地
点に関連して探索を開始すべき始点または探索を終了す
べき終点となる地点を初期設定する。

【００２１】設定された地点間で探索部３４は、ＣＤ−
ＲＯＭ装置５などから参照符３５で示すように地図デー
タを読出して、始点からリンクデータに基づいて道路を
たどって経路を探索し、その探索結果３６は経路案内部
３７に与えられるとともに、経路探索装置３２内のデー
タ管理部３８で前記メモリ２０に保管される。

【００２２】一方、前記地図データ３５はまた、自車位
置検出部３９に与えられており、この自車位置検出部３
９は、前記ＧＰＳ受信機１１および処理回路１９などか
らの出力と前記地図データ３５とのマップマッチングを
行い、正確な自車位置を演算して前記経路案内部３７に
与えるとともに、前記表示駆動回路９および表示装置１
７で実現される出力部４０に与える。出力部４０にはま
た、前記経路案内部３７から、選択された経路に関する
データが与えられており、これによって経路案内部３７
によって作成された経路上に、自車位置検出部３９で計
測された自車位置が併せて表示され、経路案内を行うこ
とができる。

【００２３】図３は、経路探索装置３２の処理を説明す
るフローチャートである。前記操作キー２からの入力に
よって出発地点および目的地点の入力などが行われ、さ
らにユーザが要求する優先モード、たとえば高速道路優
先モードなどのモード設定など、経路探索に必要な情報
が入力されると処理が開始される。ステップａ１では、
図４に示すように、出発地点である始点Ｓと目的地点で
ある終点Ｇとの間の距離が算出される。この距離の算出
は、始点Ｓおよび終点Ｇが持つ経度および緯度などに基
づいて行う。

【００２４】ステップａ２では、探索の起点Ｏとなる地
点に接続されているすべての地点（以下「探索点」とい
う）Ｎに関連するリンクデータおよびノードデータを地
図データから読出し、内部のメモリ上に展開する。経路
探索の最初にあたっては、始点Ｓが探索の起点Ｏとな
り、したがって始点Ｓに接続されている道路を表すリン
クデータおよび当該リンクデータが接続する地点を表す
ノードデータが読出される。

【００２５】ステップａ３では、読出された探索点Ｎ
１，Ｎ２，Ｎ３，…のうちの１つの探索点Ｎ１について
当該探索点に接続されているリンク数Ｒ１を算出する。
リンク数とは、探索点に接続されている道路の数であ
る。

【００２６】ステップａ４では、リンク数Ｒ１が３より
小さいかどうかが判断される。判断が肯定であればステ
ップａ５に進み、判断が否定であればステップａ６に進
む。ステップａ５では、後述する経路長Ｌを算出する際
に用いる重み付け係数Ｗ１が「０」に設定される。すな
わち、リンク数Ｒ１が１である場合とは探索点が行き止
まりである地点である場合であり、リンク数Ｒ１が２で
ある場合とは、探索点が単に１本の道路上の地点である
場合であり、このような場合には単純に起点から探索点
までの長さを考慮すればよく、後述する重み付け処理を
行う必要はない。

【００２７】ステップａ６では、前記重み付け係数Ｗ１
が予め定める値ｄに設定される。すなわちリンク数Ｒ１
が３以上である場合とは、当該探索点に３つ以上の道路
が接続されていることになり、いわゆる交差点である。
一般に交差点では交差点に進入する道路から他の道路に
抜ける場合、進入する道路とは異なる道路から当該交差
点に進入するいわゆる対向車などとの関係で待ち時間が
生じる場合がある。たとえば信号機がある場合などであ
る。したがって探索点が交差点である場合、単純に起点
から探索点までの経路長を用いたのでは、探索点を通過
する時間が全く考慮されず、仮に最短距離であっても、
現実には走行時間以上の時間がかかる場合がある。した
がって本発明では、探索点が交差点である場合には、経
路長に対していわゆる一定の重み付けを行う。

【００２８】ステップａ７では、探索中の探索点につい
て当該探索点に接続されている道路の属性を求める。す
なわち、単に交差点であっても、一般道路同士が接続さ
れている交差点と、たとえば一般道路と国道などのいわ
ゆる幹線道路とが接続されている場合は、当該交差点に
おける待ち時間に差が生じる。したがって、ステップａ
８においては、求められた道路属性に応じて、交差点の
種類を判断し、ステップａ６で設定した重み付け係数Ｗ
１の値を変更する。具体的には、接続されている道路が
いわゆる幹線道路である場合には設定した重み付け係数
Ｗ１の値をそれよりも大きい値に変更する。その後、処
理はステップａ９に進む。

【００２９】ステップａ９では、始点Ｓから探索点Ｎま
での距離Ｎｓが算出される。ステップａ１０では、距離
Ｎｓが予め定める距離Ｐよりも大きいかどうかが判断さ
れる。判断が肯定であれば、ステップａ１１に進み、判
断が否定であればステップａ１８に進む。

【００３０】ステップａ１１では、終点Ｇと探索点Ｎと
の距離Ｎｇが算出される。ステップａ１２では、距離Ｎ
ｇが前記予め定める距離Ｐよりも大きいかどうかが判断
される。判断が肯定であればステップａ１３に進み、判
断が否定であればステップａ１８に進む。

【００３１】ステップａ１３では、距離Ｎｓと距離Ｎｇ
との和Ｎｓ＋Ｎｇが予め定める距離Ａよりも小さいかど
うかが判断される。判断が肯定であればステップａ１４
に進み、判断が否定であればステップａ１５に進む。ス
テップａ１５では、距離Ｎｓと距離Ｎｇとの和Ｎｓ＋Ｎ
ｇが予め定める距離Ｂよりも短いかどうかが判断され
る。判断が肯定であればステップａ１６に進み、判断が
否定であればステップａ１７に進む。

【００３２】ステップａ１４では、重み付け係数Ｗ２が
予め定める値ａに設定される。またステップａ１６で
は、重み付け係数Ｗ２が予め定める値ｂに設定される。
さらにステップａ１７では、重み付け係数Ｗ２が予め定
める値ｃに設定される。さらにまたステップａ１８で
は、重み付け係数Ｗ２が「１」に設定される。

【００３３】すなわちステップａ１０〜ステップａ１８
の処理においては、探索点Ｎが、始点Ｓおよび終点Ｇを
含む所定の領域を越えた場合に、起点Ｏから探索点Ｎま
での経路長に対して経路長を長くする重み付け処理を行
うための重み付け係数Ｗ２を決定している。探索点Ｎが
始点Ｓまたは終点Ｇの周辺である場合は、重み付け係数
Ｗ２は「１」に設定され（ステップａ１８）、経路探索
における経路長は変更されない。すなわち、出発地点お
よび目的地点付近においては、主要幹線道路などが必ず
しも出発地点から目的地点への方向あるいは目的地点か
ら出発地点への方向に存在するとは限らず、目的地とは
反対方向に進んだ方が最短経路となる場合があるからで
ある。このような場合に最適な経路探索を実現するため
に、始点Ｓおよび終点Ｇ付近では重み付けを行わずに実
際の経路長を用いて経路探索を行う。

【００３４】また、探索点Ｎが所定の領域を越えた場合
には、起点Ｏから当該探索点Ｎまでの経路長を長くする
重み付けを行うために、重み付け係数Ｗ２を「１」より
大きい値ａ，ｂ，ｃ（ａ＜ｂ＜ｃ）に設定する。前記所
定の領域とは、距離Ｎｓと距離Ｎｇとの和Ｎｓ＋Ｎｇに
よって決定される領域であり、始点Ｓおよび終点Ｇを含
む楕円形状に選ばれる。したがってこの楕円形状を越え
た範囲に探索点Ｎが達している場合は、起点Ｏから当該
探索点Ｎまでの経路長を実際よりも長く変更し、当該探
索点Ｎは選択されないように処理する。本実施例では、
図５に示すように、重み付け係数Ｗ２を３種類設定し、
閾値Ａを越えるまでは値ａを用い、閾値Ａから閾値Ｂの
範囲内であれば値ｂを用い、閾値Ｂを越えた場合は値ｃ
を用いるようにしている。本実施例では、段階的に重み
付け係数Ｗ２を決定しているけれども、距離Ｎｓ＋Ｎｇ
の値に応じて連続的に変更するようにしてもよい。

【００３５】さらに、値ａ，ｂ，ｃは、始点Ｓと終点Ｇ
との距離に応じて変更するようにしてもよい。すなわ
ち、始点Ｓと終点Ｇとが比較的近距離である場合は、探
索範囲を楕円状にするよりは円形に近付けた方がより望
ましい探索が行われるからである。また始点Ｓと終点Ｇ
との距離が比較的遠距離である場合は、始点Ｓと終点Ｇ
から予め定める距離Ｐ以上離れた地域においては、でき
る限り狭い領域で経路探索を行う方が望ましいため、探
索範囲は楕円状であることが望ましい。

【００３６】したがって、始点Ｓと終点Ｇとの距離が短
い場合は重み付け係数Ｗ２の値は比較的１に近い値
（１．１，１．２など）を用い、始点Ｓを中心に略円形
状の領域を探索範囲とする。また始点Ｓと終点Ｇとの距
離が長い場合は、値ａ，ｂ，ｃを、１よりも充分大きい
値（２，３など）を用い、探索範囲をできる限り楕円に
近付け、探索範囲を限定する。これによって、より実用
性の高い経路探索を実現することができる。

【００３７】ステップａ１９では、前述したステップａ
３〜ステップａ１８において決定された重み付け係数Ｗ
１，Ｗ２を用いて、起点Ｏから探索点Ｎまでの補正経路
長Ｌを算出する。補正経路長ＬはＬ＝Ｌ０×Ｗ２＋Ｗ１
によって算出される。

【００３８】ステップａ２０では、一般道路優先モード
かどうかが判断される。これは、経路探索にあたってユ
ーザがどのようなモードを設定したかどうかに基づいて
判断される。判断が否定であればステップａ２１に進
み、探索点Ｎに接続されている道路のリンク特性を求
め、求められたリンク特性がユーザによって設定された
優先モードと一致するかどうかを判断する。判断が肯定
であればステップａ２２に進み、優先モードに応じて予
め定められた重み付け係数Ｗ３が前記ステップａ１９に
おいて算出された補正経路長Ｌに乗算され、改めて補正
経路長Ｌが算出される。

【００３９】すなわち経路探索を行う際に遠距離の経路
探索を行う場合、何ら条件付けを行わなければ、一般道
路のみを通る経路が探索される場合がある。たとえば、
始点Ｓから高速道路や有料道路までの距離が比較的長い
場合などである。あるいは起点Ｏから高速道路や有料道
路に接続される地点が探索点Ｎの中に含まれた場合であ
っても、その探索点よりも経路長の短い探索点が存在す
る場合はそちらの探索点が優先して選択されることにな
り、高速道路や有料道路などを通る経路が探索されない
ことがある。したがって、ユーザが予め特定の道路を優
先するモードを設定していた場合、探索点Ｎが当該優先
モードに合致する道路に接続されているときは経路長を
短くし、当該探索点が最短距離として選択されるように
処理する。したがって重み付け係数Ｗ３は「１」より小
さい値に選ばれる。

【００４０】ステップａ２３では、探索点Ｎが終点Ｇに
一致したかどうかを判断する。一致している場合は当該
探索点Ｎが目的地であるので、経路探索を終了する。判
断が否定であれば、ステップａ２０に進み、現在探索の
起点Ｏとなっている地点に接続されている探索点につい
て、上述したステップａ３〜ステップａ２３までの処理
がすべて完了したかどうかを判断する。まだ処理が終了
していない探索点が存在する場合はステップａ３に進
み、前述の処理を繰返す。すべての探索点について起点
からの経路長が算出されている場合は、ステップａ２５
へ進み、起点Ｏを移動する。この起点は、直前に起点で
あった点から探索した複数の探索点の中から経路長の最
も短いものが選ばれる。起点Ｏを移動させた後ステップ
ａ２に戻り、前述と同様の処理を繰返す。

【００４１】以上のように本実施例によれば、経路探索
の範囲を出発地点および目的地点を含む楕円状の領域に
限定することによって、経路探索のために読出すデータ
量を必要最小限に抑えることができ、これによって使用
するメモリ容量が削減される。また目的地点または出発
地点から離れた方向に延びる経路が選択されることが防
止され、より実用性の高い経路探索を実現することがで
きる。これにより、探索された経路は信頼性が向上し、
ユーザに最適な経路を案内することができる。

【００４２】また、経路探索における探索点が交差点で
あるときは探索の起点となる地点から探索点までの経路
長を長くする重み付けを行うため、交差点での待ち時間
などが考慮された、より実用性の高い経路探索を行うこ
とができ、ユーザに対して最適な経路案内を行うことが
できる。

【００４３】さらに、ユーザが特定の属性を持つ道路、
たとえば高速道路や有料道路を優先して経路探索を行う
モードを設定した場合、高速道路や有料道路上の地点が
探索点となった場合、探索の起点から探索点までの経路
長を短くし、これによって当該探索点が選択されるよう
になり、ユーザが設定したモードに応じた最適な経路探
索が行われ、ユーザに対して有用な経路案内を行うこと
ができる。

【００４４】

【発明の効果】以上のように本発明によれば、経路探索
の範囲を出発地点および目的地点を含む楕円状の領域に
限定することによって、経路探索のために読出すデータ
量を必要最小限に抑えることができ、これによって使用
するメモリ容量が削減される。また目的地または出発地
から離れた方向に延びる経路が選択されることが防止さ
れ、より実用性の高い経路探索を実現することができ
る。これにより、探索された経路は信頼性が向上し、ユ
ーザに最適な経路を案内することができる。

【００４５】また本発明によれば経路探索における探索
点が交差点であるときは探索の起点となる地点から探索
点までの経路長を長くする重み付けを行うため、交差点
での待ち時間などが考慮された、より実用性の高い経路
探索を行うことができ、ユーザに対して最適な経路案内
を行うことができる。

【００４６】さらに本発明によれば、ユーザが特定の属
性を持つ道路、たとえば高速道路や有料道路を優先して
経路探索を行うモードを設定した場合、高速道路や有料
道路上の地点が探索点となった場合、探索の起点から探
索点までの経路長を短くし、これによって当該探索点が
選択されるようになり、ユーザが設定したモードに応じ
た最適な経路探索が行われ、ユーザに対して有用な経路
案内を行うことができる。

【図面の簡単な説明】

【図１】本発明の一実施例である経路探索装置が用いら
れるナビゲーション装置１の概略的構成を示すブロック
図である。

【図２】本発明の一実施例である経路探索装置３２の経
路探索動作を説明するための概略的ブロック図である。

【図３】本発明の経路探索装置３２の動作を説明するフ
ローチャートである。

【図４】本発明の一実施例を説明するための概念図であ
る。

【図５】経路探索装置３２において用いられる重み付け
係数Ｗ２と距離Ｎｓ＋Ｎｇとの関係を示すグラフであ
る。

【符号の説明】

１ ナビゲーション装置 ２ 操作キー ３ 中央処理装置 ４ 通信バス ５ ＣＤ−ＲＯＭ装置 ６ 処理回路 ７ デコーダ ８ ＣＤ−ＲＯＭディスク ９ 表示駆動回路 １０ 表示装置 ３１ 入力装置 ３２ 経路探索装置 ３３ 地点設定部 ３４ 探索部 ３５ 地図データ ３６ 探索結果記憶部 ３７ 経路案内部 ３８ データ管理部 ３９ 自車位置検出部 ４０ 出力部 Ｎ 探索点 Ｎｓ 始点Ｓから探索点Ｎまでの距離 Ｎｇ 終点Ｇから探索点Ｎまでの距離 Ｏ 起点 Ｓ 始点 Ｇ 終点

フロントページの続き (56)参考文献 特開 平１−142825（ＪＰ，Ａ) 特開 平２−172000（ＪＰ，Ａ) 特開 平２−26000（ＪＰ，Ａ) 特開 平４−205499（ＪＰ，Ａ) 特開 平６−176297（ＪＰ，Ａ) 特開 平７−129893（ＪＰ，Ａ) 特開 平７−243860（ＪＰ，Ａ) 特公 平６−44183（ＪＰ，Ｂ２) (58)調査した分野(Int.Cl.⁶，ＤＢ名) G01C 21/00

Claims (6)

(57)【特許請求の範囲】
1. 【請求項１】 道路を折線近似した折点または交差点な
   どの道路上の地点を表すノードデータと、２つの地点を
   接続する道路の経路長および属性を表すリンクデータと
   を含んで構成される地図データに基づいて、指定された
   出発地点から目的地点までの最短経路を探索する経路探
   索装置において、 探索の起点に接続された探索点の中から、起点からの経
   路長の最も短い探索点を次の起点として選択する探索処
   理を、出発地点を最初の起点として開始し、探索点と目
   的地点とが一致するまで繰返し実行する探索手段と、 探索の起点となる地点に接続されている探索点となる地
   点を表すノードデータと、起点および探索点に接続され
   ている道路に対応するリンクデータとを地図データから
   読出して記憶する記憶手段と、 出発地点から探索点までの距離と、目的地点から探索点
   までの距離との和を求め、前記和が大きいほど起点と探
   索点との経路長を長くする重み付けを行う補正手段とを
   含むことを特徴とする経路探索装置。
2. 【請求項２】 前記補正手段は、出発地点から目的地点
   までの距離に応じて重み付けの度合を変更することを特
   徴とする請求項１記載の経路探索装置。
3. 【請求項３】 前記補正手段は、出発地点から探索点ま
   での距離または目的地点から探索点までの距離が、予め
   定める範囲内であるときは重み付けを行わないことを特
   徴とする請求項１記載の経路探索装置。
4. 【請求項４】 道路を折線近似した折点または交差点な
   どの道路上の地点を表すノードデータと、２つの地点を
   接続する道路の経路長および属性を表すリンクデータと
   を含んで構成される地図データに基づいて、指定された
   出発地点から目的地点までの最短経路を探索する経路探
   索装置において、 探索の起点に接続された探索点の中から、起点からの経
   路長の最も短い探索点を次の起点として選択する探索処
   理を、出発地点を最初の起点として開始し、探索点と目
   的地点とが一致するまで繰返し実行する探索手段と、 探索の起点となる地点に接続されている探索点となる地
   点を表すノードデータと、起点および探索点に接続され
   ている道路に対応するリンクデータとを地図データから
   読出して記憶する記憶手段と、 探索点が３つ以上の道路が接続されている交差点である
   ときは、起点と探索点との経路長を長くする重み付けを
   行う補正手段とを含むことを特徴とする経路探索装置。
5. 【請求項５】 前記補正手段は、交差点に接続されてい
   る道路の属性に基づいて重み付けの度合を変更すること
   を特徴とする請求項４記載の経路探索装置。
6. 【請求項６】 道路を折線近似した折点または交差点な
   どの道路上の地点を表すノードデータと、２つの地点を
   接続する道路の経路長および属性を表すリンクデータと
   を含んで構成される地図データに基づいて、指定された
   出発地点から目的地点までの最短経路を探索する経路探
   索装置において、 探索の起点に接続された探索点の中から、起点からの経
   路長の最も短い探索点を次の起点として選択する探索処
   理を、出発地点を最初の起点として開始し、探索点と目
   的地点とが一致するまで繰返し実行する探索手段と、 探索の起点となる地点に接続されている探索点となる地
   点を表すノードデータと、起点および探索点に接続され
   ている道路に対応するリンクデータとを地図データから
   読出して記憶する記憶手段と、 探索点に経路探索において優先される属性を持つ道路が
   接続されているときは、起点と探索点との経路長を短く
   する重み付けを行う補正手段とを含むことを特徴とする
   経路探索装置。