JPH05107073A

JPH05107073A - 推奨経路案内装置

Info

Publication number: JPH05107073A
Application number: JP26921791A
Authority: JP
Inventors: Makoto Fushimi; 真伏見; Yoshiki Kamiyama; 芳樹上山; Takashi Yagyu; 岳志柳生
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1991-10-17
Filing date: 1991-10-17
Publication date: 1993-04-27

Abstract

(57)【要約】【目的】進入禁止情報を独立して持たなくても、右折
禁止等の進入禁止情報を記憶し、従来よりもはるかに高
速に経路探索を行うことができる推奨経路案内装置を提
供することを目的とする。【構成】仮想ネットワーク情報記憶手段１は、ある交
差点が右折禁止等の交通規制を伴う交差点である場合
は、その交差点に対して複数の交差点番号（ノード）を
付与して区別して記憶し、このそれぞれ区別した交差点
番号ごとに異なる道路網接続情報をもたせる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ナビゲーションシステ
ムにおける経路探索に関し、特に車両用のナビゲーショ
ンシステムにおける推奨経路探索に関する。

【０００２】

【従来の技術】従来のナビゲーションシステムにおける
経路探索装置としては、たとえば特開平１−１７３２９
８号公報に開示されている様なものがある。図１７に従
来の経路探索装置のシステム構成を示す。また図１８
に、交差点データ１７１、道路データ１７２、ノードデ
ータ１７３の内容を示す。１７４は、右左折禁止等の進
入禁止道路を除き交差点から周囲道路を検索し、指定さ
れた出発地から目的地までの最適経路を探索する経路探
索処理部である。１７５は交差点列及びノード列生成
部、１７６は交差点列及びノード列データ、１７７はナ
ビゲーション部である。

【０００３】このように構成された従来の経路探索装置
について以下に説明する。図２に本発明を説明するため
に用いる道路網を示す。図２において、Ｉ、ＩＩ、ＩＩ
Ｉ、ＩＶはそれぞれ交差点であり、それぞれ矢印で示す
道路により接続されている。また、交差点ＩＶにおいて
は、交差点ＩＩＩから来た場合に右折禁止の道路規制が
しかれている。この道路網データを用いて以下、図１
４、図１５、図１６を用い、従来例の経路探索装置につ
いて説明する。図１４は図２に示す道路網において、従
来の経路探索装置が経路探索をするために記憶する道路
網データである。Ｉ、ＩＩ，ＩＩＩ，ＩＶは交差点（ノ
ード）であり、１から９まではそれぞれノードを結ぶ道
路（リンク）である。また、矢印はそのリンクの車両進
行方向を示している。たとえばノードＩとノードＩＩの
間は、双方向道路であるので、リンク１とリンク２が存
在する。一方ノードＩＩＩとノードＩＶの間はノードＩ
ＩＩからノードＩＶに向けての一方通行道路であるの
で、リンク５だけが存在し、ノードＩＶからノードＩＩ
Ｉへは通行できないようにデータを記憶している。

【０００４】図１５は、各交差点における左折禁止、右
折禁止、直進禁止等の交通規制の情報を記憶するテーブ
ルである。実際にはこのテーブルは図１８（ｂ）の道路
データ内に含まれている。ここではノードＩＶにおいて
右折禁止が存在するので、リンク番号５に対する進入禁
止リンクとしてリンク７が記録されている。

【０００５】図１６は、この従来の経路探索装置の動作
を説明するフローチャートである。この図を用いて以
下、動作を説明する。まず、ステップ１６０１で経路探
索が開始される。次にステップ１６０２で出発地点と目
的地点を設定し、出発ノード及び目的ノードを決定す
る。次にステップ１６０３に進み、経路探索に使用する
基準ノードを選出する。ここでは、はじめてステップ１
６０３の動作を行うので、先ほどステップ１６０２で設
定した出発地ノードが基準ノードとして設定される。次
にステップ１６０４に進み、探索が終了しているかの判
断を行いつつ、経路探索が終了するまで以下ステップ１
６０５からステップ１６１５までの動作を繰り返す。ス
テップ１６０５では探索結果として記録された基準ノー
ドの使用リンクを読みだす。さらにステップ１６０６で
交差点データと道路データから基準ノードに接続するリ
ンクを順に選出していく。次にステップ１６０７で進入
禁止リンクを読みだし、先ほど選出した接続リンクが進
入禁止リンクであるかどうかをステップ１６０８、１６
０９で判断する。もし選出した接続リンクが進入禁止リ
ンクである場合はステップ１６１５に進み、基準リンク
に接続するリンクを全て選出したか判断する。次にステ
ップ１６０６で選出した接続リンクが進入禁止リンクで
ないと判断されると、ステップ１６１０に進み、次ノー
ドまでの総評価値を算出する。

【０００６】次にステップ１６１１に進み、先ほど算出
した総評価値が探索結果として記録されている次ノード
までの総評価値よりも小さいかどうかを判断する。もし
新たに算出した評価値の方が大きければ、ステップ１６
０６に戻り、また、異なる接続リンクを選出する。ステ
ップ１６１１において新たに算出した総評価値の方が以
前に記録されている総評価値よりも小さい場合には、ス
テップ１６１２に進み、その評価値を新たな総評価値と
して更新し、記録する。続いてステップ１６１３に進
み、現在探索を行った接続リンクを次ノードの使用リン
クとして記録し、ステップ１６１４で次ノードを候補状
態とする。以上の動作を基準ノードに接続する全てのリ
ンクに対して行う。基準ノードに接続する全てのリンク
に対して進入禁止リンクであるかどうかの判断、（すな
わちステップ１６０８、１６０９の動作）および総評価
値判断（ステップ１６１０、１６１１、１６１２、１６
１３、１６１４の動作）が終わると、ステップ１６０３
に戻り、新たな基準ノードを選出して同様の動作を行う
（ステップ１６１５）。そして以上の動作を経路探索が
終了するまで繰り返し、出発地点と目的地点がつながれ
ば、ステップ１６１６に進み、経路探索を終了する。

【０００７】

【発明が解決しようとする課題】しかしながら、上記の
ような構成の経路探索装置では、まず、根本的な課題と
して、求める経路上に進入禁止規制があった場合、例え
ば図１９の様な道路網のとき、ノードＤには１つ前のノ
ードとしてノードＣが記録されるので、ノードＡからノ
ードＥへ向かう経路（Ａ−Ｂ−Ｄ−Ｅ）は求められなか
った。さらに経路探索を行う場合には、右折禁止、左折
禁止、直進禁止等の情報を記録しているテーブルを常に
参照しながら経路探索を行わなければならず、探索を広
げる１回１回の処理量が多くなり、結果として探索に多
くの時間が必要であった。

【０００８】つまりステップ１６０８、１６０９におい
ては、図１５に示す進入禁止リンクを毎回、読みだして
チェックしながら探索を広げることを行っていた。

【０００９】また、記憶しておかなければならないデー
タの量も、各リンク番号に対して進入禁止リンクを記憶
する固定長のデータを持つ必要があり（検索速度を速く
するためにはデータを固定長でもってる方良い。）デー
タ量が全体として膨大なものになってしまう。

【００１０】本発明はこのような不都合を解決するもの
で、道路網データの内、進入禁止情報を独立して持たな
くてもよく、特別に進入禁止リンク情報を記録するリス
トを持つ必要がなくなり、検索の１サイクルの処理が単
純で、経路探索を従来よりも高速に行うことができ、ま
た通行可能な道路があれば必ず正確に探索を行なうこと
ができる推奨経路案内装置を提供することを目的とす
る。

【００１１】

【課題を解決するための手段】上記目的を解決するた
め、本発明は、経路探索を行う出発地点と目的地点を設
定する地点設定手段と、道路網データをノードデータと
リンクデータとして記憶する仮想ネットワーク情報記憶
手段と、前記地点設定手段で設定した出発地点と目的地
点の間の経路を前記仮想ネットワーク情報記憶手段が記
憶しているデータから探索する探索手段と前記探索手段
で探索した経路を出力する出力手段とからなり、前記仮
想ネットワーク情報記憶手段は、ある交差点が右折禁
止、左折禁止、直進禁止などの交通規制を伴う交差点で
ある場合は、その交差点に対して複数の交差点番号（ノ
ード）を付与して区別して記憶し、このそれぞれ区別し
た交差点番号ごとに異なる道路網接続情報をもたせるこ
とを特徴とする推奨経路案内装置である。

【００１２】また、仮想ネットワーク情報記憶手段は、
各リンクに対してそのリンクを選ぶと往復移動をする事
になるリンクをＵターンリンクとして記憶し、探索手段
は、経路探索を行う際に前記Ｕターンリンクを対象から
省いて探索を行うことを特徴とする推奨経路案内装置で
ある。

【００１３】また、仮想ネットワーク情報記憶手段は、
ある交差点が右折禁止、左折禁止、直進禁止などの交通
規制を伴う交差点である場合は、その交差点に対して複
数の交差点番号（ノード番号）を付与して区別して記憶
し、このそれぞれ区別した交差点番号ごとに異なる道路
網接続情報をもたせ、さらに、これら区別した交差点番
号が実際は同一の交差点であることを分離交差点情報と
して記憶し、地点設定手段は、出発地点あるいは目的地
点として前記分離交差点が選択された場合には区別した
交差点番号すべてを出発地点あるいは目的地点として設
定することを特徴とする推奨経路案内装置である。

【００１４】

【作用】上記構成により、本発明における推奨経路案内
装置では、仮想ネットワーク情報記憶手段が、ある交差
点が右折禁止、左折禁止、直進禁止などの交通規制を伴
う交差点である場合は、その交差点に対して複数の交差
点番号（ノード）を付与して区別して記憶し、このそれ
ぞれ区別した交差点番号ごとに異なる道路網接続情報を
もたせることで、従来持っていた進入禁止リンク情報を
持つことが不要になる。さらに進入禁止情報を持つ交差
点に複数の情報を残すことができるので、目的地に到達
可能な経路があれば必ず求めることができる。また、Ｕ
ターンリンクを記憶し、探索手段は、経路探索を行う際
に前記Ｕターンリンクを対象から省いて探索を行うので
探索速度が向上する。

【００１５】

【実施例】以下、図面を参照しながら本発明の推奨経路
案内装置の実施例について詳細に説明する。図１に本発
明の一実施例の推奨経路案内装置のブロック構成図を示
す。同図において、１は出発地点及び目的地点を設定
する地点設定手段である。２は道路網データを、ノード
情報、リンク情報、Ｕターン情報、分離交差点情報とし
て記憶する仮想ネットワーク情報記憶手段である。３は
地点設定手段１で設定した出発地点と目的地点の間の経
路を仮想ネットワーク情報記憶手段が記憶するデータか
ら探索する探索手段である。４は探索手段３により探索
した結果をディスプレイ等の表示装置に出力する出力手
段である。

【００１６】図２は本発明を説明するために用いる道路
網である。図２において、Ｉ、ＩＩ、ＩＩＩ、ＩＶはそ
れぞれ交差点であり、それぞれ矢印で示す道路により接
続されている。また、交差点ＩＶにおいては、交差点Ｉ
ＩＩから来た場合に右折禁止の道路規制がしかれてい
る。

【００１７】このような道路網を記憶するために、本発
明ではノード情報として図４に示すような構成をリンク
情報としては図５に示すような構成をとる。すなわち図
２に示す道路網を図３に示すような仮想ネットワークと
して考える。図３に示すように道路規制のある交差点Ｉ
Ｖ（リンクｅから進入してきた場合に右折禁止であ
る。）をＩＶ₁、ＩＶ₂、ＩＶ₃としてあたかも３つの異
なる交差点であるかのごとく記録する。そしてこれらそ
れぞれのノードに対して、それぞれ異なる接続リンク情
報を記憶させる。ここでは交差点（ノード）ＩＶを３つ
の異なるノードとして記憶することで、ノードＩＶにお
ける右折禁止の情報を記憶している。この分離させるノ
ードの数は、右左折禁止等の交通規制がしいてある交差
点（以下、分離交差点と称す）に入り込むリンクの数だ
けあれば表現できる。動作については以下で詳細に説明
する。図５は本実施例におけるリンク情報の一例であ
る。同図に示すように各リンクに対して行き先ノード及
び、総評価値の算出に使用するリンクコストが記録され
ている。

【００１８】以上のように構成された推奨経路案内装置
について、図９に示すフローチャートを用いてその動作
を説明する。

【００１９】まず、ステップ９０１で出発ノード、目的
ノードを設定する。ステップ９０２での動作を図２０を
用いてさらに詳しく説明する。図２０は第１の実施例に
おける出発・目的ノード設定サブルーチンのフローチャ
ートである。ステップ２００１で、まず絶対座標系また
は相対座標系により出発地点の座標を入力する。ここで
例えば予め座標が設定された目標物を選択することによ
り行っても良い。次にステップ２００２で入力された出
発地の座標から最も距離的に近いノードを出発ノードと
して設定する。さらに目的地側についても同様に、ステ
ップ２００３で目的地点の入力を行い、ステップ２００
４で入力された目的地点に最も近いノードを目的ノード
として設定する。この様に出発ノードと目的ノードが設
定できるとステップ９０２に進む。ステップ９０２で
は、経路探索に使用する基準ノードを選出する。このス
テップ９０２における動作を図１０に示す基準ノード選
出サブルーチンとして詳細に説明する。初回にこのサブ
ルーチンが呼ばれたときには先ほどステップ９０１で設
定された出発地点に最も近いノードが基準ノードとして
記憶されるものとする。まず基準ノードを選出するに当
たり、ステップ１００２で全てのノードを１つずつ調査
する。この調査の際に、たとえば距離や到達時間等の情
報に基づいて調査範囲を設定するようにしてもよい。次
にステップ１００３で、これらの各ノードが基準ノード
として候補状態であるかどうかを判断する。この候補状
態であるかどうかは、以下に示す探索の過程で設定され
る。具体的には候補状態であれば状態フラグを１に設定
し、候補でない場合は２に設定する。ノードが候補状態
であればステップ１００４に進み、そのノードに対する
総評価値を読み込み、ステップ１００５でその評価値が
最小であるかどうかを判断する。もし最小であれば、ス
テップ１００６で、その値を最小評価値として記録し、
ステップ１００７で現ノードを基準ノードとして記録す
る。以上の動作を全てのノード（調査範囲を設定したと
きはその調査範囲内にある全てのノード）について行
い、全てのノードについて調査が終わってれば（ステッ
プ１００８で判断）、基準ノードを候補状態からはず
す。（状態フラグの値を２に変える。）この様にして経
路探索に用いる基準ノードを選出する。

【００２０】次にステップ９０３で基準リンクが目的ノ
ードであるか判断することにより終了判断を行いつつ、
以下の動作を行う。まず、ステップ９０４で先ほど選出
した基準ノードに対して接続リンクを選出する。ここ
で、例えば基準地点としてノードＩＩＩが選ばれていた
とすると、接続リンクとしては図４に示すようにｄとｅ
が選択できる。次にステップ９０５で次ノードまでの総
評価値を算出する。ここでは基準ノードとしてノードＩ
ＩＩが選択されているので、次ノードとしてはノードＩ
ＩとノートＩＶ₃の２つが候補に上がる。次にステップ
９０６で算出した総評価値が探索結果情報に記録された
次ノードの総評価値よりも小さいかどうかを判断する。
ただし、総評価値の初期値はとりえる値の最大値として
おく。ここで今回算出した総評価値が前回のものよりも
小さければ、ステップ９０７で探索結果情報の更新を行
なう。図６は探索結果情報の記録例である。ここでは基
準ノードとしてノードＩＩＩが選択され、ノードＩＩの
総評価値は前回のノーのＩＩの総評価値よりも大きく、
探索結果情報の更新は行なわれなかったとする（ステッ
プ９０６からステップ９１０に飛ぶ）。また、ノードＩ
Ｖ₃の総評価値は、前回のノードＩＶ₃の総評価値が初期
値としてとりえる値の最大値が入っているので、ステッ
プ９０７でノードＩＶ₃の総評価値として算出した総評
価値を記憶させる。次にステップ９０８に進み、前ノー
ド番号としてノードＩＩＩを記憶し、さらに使用リンク
として接続リンクｅを記憶する。次にステップ９０９で
ノードＩＶ₃を基準ノードとしての候補状態にする。次
にステップ９１０に進み、基準ノードに接続するリンク
を全て選出して上記の判断をしたかどうかを判断し、全
てのリンクについて判断できていれば、ステップ９０２
に戻り、基準ノードを新たなノードに更新する。

【００２１】今、説明している例によれば、基準ノード
がノードＩＩＩの時、基準ノードとしての候補にはＩＶ
₃しかあがらないので、図２に示すノードＩＩＩからノ
ードＩＶに進み、さらにノードＩＩに進むような経路を
探索することはない。

【００２２】このようにして、経路探索を行ってゆき、
ステップ９０３で経路探索が終了と判断されるとステッ
プ９１１に進み探索した経路を再構成する。

【００２３】ステップ９１１の経路再構成の動作を図１
１を用いて経路再構成サブルーチンとして説明する。図
１１に示す経路再構成サブルーチンにおいて、まずステ
ップ１１０２で目的ノードを現ノードとして設定する。
次にステップ１１０３に進み、探索結果情報の中から使
用リンクを経路の一部として記録する。次にステップ１
１０５に進み、目的ノードの１つ手前のノードを現ノー
ドとして新たに設定しなおし、ステップ１１０３に戻っ
て、同様の動作を行う。この動作を現ノードが出発ノー
ドになるまで繰り返し、現ノードが出発ノードであると
判断されると（ステップ１１０４）、経路の再構成は終
了したとしてこの処理を終了する。

【００２４】次にステップ９１２に進み、先に求めた経
路をディスプレイ等の表示装置に出力する。以上で経路
探索の動作は終了する。

【００２５】以上のように、本実施例によれば、仮想ネ
ットワーク情報記憶手段２が、ある交差点が右折禁止、
左折禁止、直進禁止などの交通規制を伴う交差点である
場合は、その交差点を分離交差点として、複数の交差点
番号（ノード番号）を付与して区別して記憶し、このそ
れぞれ区別した交差点番号ごとに異なる道路網接続情報
をもたせ、さらに、これら区別した交差点番号が実際は
同一の交差点であることを位置情報として記憶すること
で、従来データとして持っていた進入禁止リンク情報を
持たなくても、通常の経路探索を行うだけで、右左折禁
止等の進入禁止道路を探索することがなく、経路探索を
行うことができる。また、目的地への経路が存在すれば
必ず求めることが出来る。またリンク毎に進入禁止リン
ク情報を保持する必要がなく、探索速度も向上する。

【００２６】なお、地点設定手段が、出発地点あるいは
目的地点を設定する際に、分離交差点が選択された場合
には、同一地点で分離交差点として区別した交差点番号
すべてを出発地点あるいは目的地点として設定するよう
にしてもよい。こうすることで出発地点から適正な経路
を探索することができる。（もし、こうしないと出発地
点の段階から右左折禁止、直進禁止などの道路規制があ
ることになり、適正な経路探索ができない。）また、地
点設定手段がこのような処理をするためには例えば分離
交差点リストとして図８に示すようなものを記憶してお
けば良い。

【００２７】次に本発明第２の実施例について、説明す
る。この実施例は、第１の実施例に加え、図７に示すＵ
ターンリンク情報をもたせたものであり、装置のブロッ
ク構成図は第１の実施例と同様である。本実施例におい
ても、説明のために図２に示す道路網を用いて説明す
る。図２に示す道路網を図３に示す仮想ネットワークと
して記憶する際に、本実施例では、第１の実施例の記憶
データに加え、図７に示すＵターンリンク情報を双方向
通行可のリンクに対してそれぞれ記憶する。すなわち図
３に示す仮想ネットワークでは、リンクａに対してはリ
ンクｂがＵターンリンクであり、また逆にリンクＢに対
してリンクａがＵターンリンクである。同様にリンクｃ
に対してはリンクｄを、リンクｄに対してはリンクｃを
それぞれＵターンリンクとして記憶する。以下、その他
のリンクに対しては図７に示す通りである。あるリンク
に対してＵターンリンクが存在しない場合にはＵターン
リンクが無いことを記憶しても良いし、そのリンク番号
自体を存在させないような構成にしても良い。

【００２８】また、Ｕターンリンクを記憶させるに当た
り、分離交差点から通常ノードに向かうリンクにおいて
は、通常ノードから、同一交差点であるなかの他の進入
可能な分離交差点へのリンクを指し、その他のノード間
においては自リンクに対して逆向きのリンクをそのまま
指す様にすれば良い。

【００２９】また、このＵターンリンクを記憶させる時
には、例えばそのノードに接続する順位（北から時計回
りに何番目とか）の情報を記憶しておけば良い。

【００３０】さらに、本実施例では、先ほど述べた分離
交差点リスト（図８）も採用している。

【００３１】以上のように構成した第２の実施例につい
て、その動作を図１２に示すフローチャートを用いて説
明する。

【００３２】図１２において、ステップ１２０１で、ま
ず経路探索が開始される。ステップ１２０２で出発ノー
ド、目的ノードを選出する。このステップ１２０２で、
先ほど述べた分離交差点リストを参照する。この動作を
図１３に示す、出発・目的ノード設定サブルーチンとし
て詳細に説明する。図１３において、まずステップ１３
０２でキー入力等の操作により出発地点が設定されると
ステップ１３０３でのそ出発地点にいちばん近いノード
を出発ノードに設定する。次にステップ１３０４に進
み、先ほど設定した出発ノードが分離交差点かどうかを
判断する。もし分離交差点でなければ、その出発ノード
をそのまま維持し、さら次のステップへと移行する。ス
テップ１３０６で設定した出発ノードが分離交差点であ
ると判断された場合には、ステップ１３０５に進み、図
８に示す同一地点にある同一分離交差点全てを出発ノー
ドとして設定する。出発ノードの設定が終わると次にス
テップ１３０６に進み、目的地点を設定する。以下ステ
ップ１３０８、１３０９において出発地点と同様、その
地点が分離交差点であるかどうかを判断し、もし分離交
差点であれば、同一地点の分離交差点全てを目的ノード
として設定し、経路探索を行ってゆく。

【００３３】このように、分離交差点リストを用いるこ
とで、ステップ１２０２において、出発ノードあるいは
目的ノードに分離交差点が選ばれても、道路規制情報の
有無にかかわらず、適正な経路探索を行うことができ
る。

【００３４】次に、ステップ１２０３に進み基準ノード
を選出する。このステップ１２０３における基準ノード
の選出は第１の実施例と同様である。次にステップ１２
０４で経路探索が終了しているかどうかを判断しなが
ら、以下のステップを繰り返す。

【００３５】まず、ステップ１２０５において、図７に
示すＵターンリンク情報を参照しながら、探索結果情報
として記憶された基準ノードへの使用リンクのＵターン
リンクを求める。次にステップ１２０６に進み、基準ノ
ードに対する接続リンクを選出する。続いてステップ１
２０７に進み、先ほどステップ１２０６で選出した接続
リンクがステップ１２０５で求めたＵターンリンクかど
うかを判断する。もし、Ｕターンリンクでなければステ
ップ１２０８に進み、そのリンクに対する次ノードまで
の総評価値を算出し、ステップ１２０９において、その
総評価値が探索結果情報に記録された次ノードの総評価
値より小さいかどうかを判断する。ステップ１２０８で
算出した総評価値が探索結果情報に記録された次ノード
の総評価値より小さいければステップ１２１０に進み、
算出した総評価値を次ノードの総評価値として記憶す
る。そしてステップ１２１１で基準ノードを前ノードと
して記録し、また接続リンクを使用リンクとして記録
し、次ノードを基準ノードとしての候補状態とする。
（状態フラグを１に設定する。）もし、ステップ１２０
７で接続リンクがＵターンリンクであれば、ステップ１
２１３に飛び、総評価値の算出等の処理（ステップ１２
０８からステップ１２１２までの処理）は行わない。し
たがってＵターンリンクに対しての処理分だけ計算時間
が短縮される。次にステップ１２１３で基準ノードに接
続するリンクを全て選出したかどうかを判別し、全ての
リンクに対して、上記のステップの行程を行うと、ま
た、ステップ１２０３に戻り、次の基準ノードを選出す
る。

【００３６】ステップ１２０４において、経路探索が終
了したと判断されると、ステップ１２１４に進み、経路
の再構成を行い、ステップ１２１５でその結果を表示さ
せ、経路探索を終了する。なお、ステップ１２１４、１
２１５、１２１６における動作はは第１の実施例と同様
である。

【００３７】以上のように、本実施例によれば、第１の
実施例に加えて、Ｕターンリンク情報を記憶しているの
で、例えば、図３に示すような道路網において、ノード
ＩＩＩーＩＶ₃ーＩーＩＶ₁−ＩＩのようなＵターン経路
を選出する事がなくなり、より適正な経路を探索するこ
とができる。また、通常ノードに対してもＵターンリン
クの対しては総評価値算出等の処理を一切行わないの
で、処理速度も向上する。

【００３８】また、分離交差点リストを持つことによ
り、地点設定時に出発地点あるいは目的地点に分離交差
点が設定されても、探索が広がらないリンクが存在する
ことなく、適正な経路を探索することができる。

【００３９】なお、本実施例においては、出発ノード、
目的ノードを出発地、目的地に最も近いものとしたが、
これは車両や２地点間の方向性を加味して設定するよう
にしてもよい。また、リンク情報及びノード情報はお互
いの接続関係が正しく表現されているものならどの様な
ものであってもよい。

【００４０】さらに、探索結果情報はノード毎にそのノ
ードまでの総評価値と現在の状態、及び前ノードまたは
使用リンクを示す情報が記録されていていればよい。

【００４１】

【発明の効果】以上説明したように、本発明は、仮想ネ
ットワーク情報記憶手段が、ある交差点が右折禁止、左
折禁止、直進禁止などの交通規制を伴う交差点である場
合は、その交差点に対して複数の交差点番号（ノード）
を付与して区別して記憶し、このそれぞれ区別した交差
点番号ごとに異なる道路網接続情報をもたせることで、
従来持っていた進入禁止リンク情報を持つことが不要に
なる。また、Ｕターンリンクを記憶し、探索手段は、経
路探索を行う際に前記Ｕターンリンクを対象から省いて
探索を行うので探索速度が大幅に向上する。

【００４２】また、目的地までの経路が存在すれば、必
ず経路を選出することが出来る。

【図面の簡単な説明】

【図１】本発明第１の実施例の推奨経路案内装置のブロ
ック構成図

【図２】本発明の説明に使用する道路網図

【図３】本発明で使用する仮想ネットワークを示す図

【図４】本発明におけるノード情報の記憶状態を示す図

【図５】本発明におけるリンク情報の記憶状態を示す図

【図６】本発明における探索結果情報の記憶状態を示す
図

【図７】本発明におけるＵターンリンク情報の記憶状態
を示す図

【図８】本発明における分離交差点リストの記憶状態を
示す図

【図９】本発明の第１の実施例の動作を示すフローチャ
ート

【図１０】本発明の実施例における基準ノード選出サブ
ルーチンのフローチャート

【図１１】本発明の実施例における経路再構成サブルー
チンのフローチャート

【図１２】本発明の第２の実施例の動作を示すフローチ
ャート

【図１３】本発明の第２の実施例における出発・目的ノ
ード設定サブルーチンのフローチャート

【図１４】従来の経路探索装置の説明に用いる道路網図

【図１５】従来の経路探索装置が持っている進入禁止情
報を示す図

【図１６】従来の経路探索装置の動作を示すフローチャ
ート

【図１７】従来の経路探索装置のブロック構成図

【図１８】（ａ）は、従来の経路探索装置が持つ交差点
データの記憶状態を示す図（ｂ）は、従来の経路探索装置が持つ道路データの記憶
状態を示す図（ｃ）は、従来の経路探索装置が持つノードデータの記
憶状態を示す図

【図１９】従来の経路探索装置では探索できない経路が
存在する道路網を示す図

【図２０】本発明の実施例における出発・目的ノード設
定サブルーチンのフローチャート

【符号の説明】

１地点設定手段２仮想ネットワーク情報記憶手段３探索手段４出力手段

Claims

【特許請求の範囲】

【請求項１】経路探索を行う出発地点と目的地点を設定
する地点設定手段と、道路網データをノードデータとリ
ンクデータとして記憶する仮想ネットワーク情報記憶手
段と、前記地点設定手段で設定した出発地点と目的地点
の間の経路を前記仮想ネットワーク情報記憶手段が記憶
しているデータから探索する探索手段と前記探索手段で
探索した経路を出力する出力手段とからなり、前記仮想
ネットワーク情報記憶手段は、ある交差点が右折禁止、
左折禁止、直進禁止などの交通規制を伴う交差点である
場合は、その交差点に対して複数の交差点番号（ノー
ド）を付与して区別して記憶し、このそれぞれ区別した
交差点番号ごとに異なる道路網接続情報をもたせること
を特徴とする推奨経路案内装置。
【請求項２】仮想ネットワーク情報記憶手段は、各リン
クに対してそのリンクを選ぶと往復移動をする事になる
リンクをＵターンリンクとして記憶し、探索手段は、経
路探索を行う際に前記Ｕターンリンクを対象から省いて
探索を行うことを特徴とする請求項１記載の推奨経路案
内装置。
【請求項３】仮想ネットワーク情報記憶手段は、ある交
差点が右折禁止、左折禁止、直進禁止などの交通規制を
伴う交差点である場合は、その交差点に対して複数の交
差点番号（ノード）を付与して区別して記憶し、このそ
れぞれ区別した交差点番号ごとに異なる道路網接続情報
をもたせ、さらに、これら区別した交差点番号が実際は
同一の交差点であることを分離交差点情報として記憶
し、地点設定手段は、出発地点あるいは目的地点として
前記分離交差点が選択された場合には区別した交差点番
号すべてを出発地点あるいは目的地点として設定するこ
とを特徴とする請求項１または２記載の推奨経路案内装
置。