最適経路検索方法
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は車両用ナビゲーション装置等に用いる道路ネットワークでの最適経路検索方法に関する。
〔発明の概要〕
本発明は車両用ナビゲーション装置等に用いる道路ネットワークでの最適経路検索方法に関し、流入出端を示す交差点を接続道路数の複数のサブノードとし、この複数のサブノード間に通行可又は通行不可のフラグを設け、道路ネットワークの最適経路検索時に交差点内の複数のサブノード間のフラグを同時に検索することで、交通規則に従った最適な経路を高速に得る様にしたものである。
〔従来の技術〕
従来、車両の現在位置を地図上に表示する車両用ナビゲーション装置は第４図の様に構成されていた。
第４図において、信号処理手段（１）はCPU及びROM、RAM等の記憶手段によって構成される。そして表示手段（２）は液晶、CRT等の表示用デバイスから成る。信号処理手段（１）には地図等の情報が記憶されたコンパクトディスクメモリ（以下CD−ROMという）の再生装置又は地図等の情報の記憶／再生を可能とする装置等から成る地図データ記憶手段（３）及び車両の進行方向に対し、例えば地磁気のＸ及びＹ成分を検出する方位センサと、この方位センサの出力を使用して車両の進行方向に応じて地磁気のX,Y成分のデジタル信号を発生する方位検出手段と、単位走行距離毎に所定パルス等を発生する距離センサ等を備える距離検出手段とから成る走行位置検出手段（４）とからなるデータが与えられ、これら各データはキーボード等からなる入力手段（５）の指示に基づき信号処理手段（１）が演算処理を実行し、特定地区の地図情報，信号処理手段（１）の演算結果，現在位置等を表示手段（２）に表示させる様に成されている。
上述のナビゲータ装置によれば表示手段（２）上に表示された道路ネットワーク画像をみながら出発地点と目的地点を入力手段（５）から入力指示すると、地図データ記憶手段（３）からの地図データに基づいて信号処理手段（１）内で最小インピーダンス経路を検索する。ここで最小インピーダンス経路とは入力手段（５）から与えられる入力条件に応じて、例えば最短距離、最小時間、或は最低料金等で出発地点から目的地点迄に到達するための経路であり、各交差点での右左折禁止条件、或はガソリン使用量、渋滞状況等が加味されて定められる。
例えば、出発地点から目的地点迄の最短の車両進行コースを道路用の地図データから検索する方法としては交差点を１つのノードとし、道路をリンクと考えて、ダイクストラ（Dijkstra）法、或はニコルソン（Nicholson）法を用いて道路ネットワーク内で始点ノードから、終点ノード迄の最短経路検索を行なう方法が知られている。
これらのうち例えば、ダイクストラ法で出発地点と目的地点迄の最短経路を求めるためのアルゴニズムは次の様に示される。
ここではｉはノード、dikiはノードik,iを結ぶリンク長を表わす。ｉ＝０は始点であり、ｉ＝Ｎは終点である。Ｇ（ｉ）は始点よりノードｉまでの最短路長を表わす、またＰはＧ（ｉ）がまだ求められていないノードの集合を表わす。
出発地点から目的地点迄の最短経路を検索する場合、交差点をノード、道路をリンクとして、地図データベースを構築したのでは各交差点での右左折禁止等のデータが存在しないため道路規則を正しく反映した最適経路の検索方法とならないために、第５図に示す様にインピーダンスを加味し、各交差点を接続道路数×２のサブノード（６）と、接続道路数×（接続道路数−１）のリンク（７）に分解する方法が情報処理学会、第33回（昭和61年後期）全国大会論文集2401頁、論文番号5W−５「首都圏道路網最適経路情報提供システム」に記載されている。
〔発明が解決しようとする課題〕
然し、この検索方法によっては、ノード数及びリンク数が大幅に増大し、取り扱うデータ量は膨大となる。更に交差点の入口から出口迄に１本のリンクを設定するために、この処理に１回のループ処理を要し、全体の検索時間が増大する欠点を有していた。
本発明は叙上の欠点に鑑みなされたもので、その目的とするところは最適経路検索を交通規則に従って高速に検索しようとするものである。
〔課題を解決するための手段〕
本発明の最適経路検索方法はその１例が第１図乃至第３図３図に示されている様に車の流入出端を示す交差点（８）を接続道路数と等しい複数のサブノード（61）（62）（63）（64）とし、複数のサブノード（61）（62）（63）（64）間に通行可又は通行不可のフラグデータを記憶した交差点内サブノード間通行可、不可フラグデータを記憶した記憶手段（21）と、サブノード暫定距離データ記憶手段（13）と、道路ネットワークの最適経路検索を行なう信号処理手段（1a）とを具備し、信号処理手段（1a）は道路ネットワークの最適経路検索時に交差点の前回距離が確定した距離確定サブノードより進行が可能か否かを交差点内サブノード間通行可、不可フラグデータ記憶手段（21）の通行可又は通行不可のフラグを読み込んで判断し、通行不可の場合は次のフロー動作に移行するが、通行可の場合は交差点（８）を経過し、次のサブノードへ進んだ場合の距離とサブノード暫定距離データ記憶手段（13）の値を比較し、小さい値をサブノード暫定距離データ記憶手段（13）に更新する様にしたものである。
〔作用〕
本発明の最適経路検索方法では交差点を複数の接続道路数のサブノードと、この複数のサブノード間に通行可又は通行不可のフラグを設けて、最適経路検索時に同時に検索する様にしたので道路交通規則にのっとった高速な検索を行なうことが出来る。
〔実施例〕
以下、本発明の最適経路検索方法の一実施例を第１図乃至第３図について詳記する。
第１図は本発明の最適経路検索方法を実現するための車載用ナビゲータ装置に用いられる信号処理手段（１）の機能ブロックを示すもので、他の部分については第４図R>図と同様に構成されているものとして第４図との対応部分とは同一符号を付してその説明を援用する。
第１図で入力手段（５）のキーボードから第１図に示されていないが表示手段（２）に表示される地図上に最適経路、例えば、出発地点から目的地点迄の最短経路を表示させるために出発地点と目的地点等が入力されると信号処理手段（１）は最適経路の検索を行なう様になされている。信号処理手段（１）内には演算手段（1a）を有し、この信号処理手段（１）内に通常配設されているROM,RAM等の記憶手段（以下RAMと記す）内にカウンタ（９）、距離確定ノードポインタ（10）、確定距離バッファ（11）、距離未確定ノードデータ記憶手段（12）、サブノード暫定距離データ記憶手段（13）、終点ノード記憶手段（14）、リンク長データ記憶手段（15）、経路前サブノード記憶手段（16）、距離未確定サブノードデータ記憶手段（17）、距離確定サブノードポインタ（18）、ノード、サブノード対応データ記憶手段（19）、サブノード接続関係データ記憶手段（20）、交差点サブノード間通行可、不可フラグデータ記憶手段（21）、距離最短サブノードバッファ（22）を備えている。
第２図は第１図のフローチャートを示すものであり、先ず、入手手段（５）から第１ステップSTP1に示す様に始点ノードiSと終点ノードiEを入力すると演算手段（1a）は第２ステップSTP2に示す様に初期化が行なわれる。演算手段（1a）はCPUのRAM内のカウンタ（９）のカウント値ｋをｋ＝０とし、距離確定ノードポインタ（前回のループで最短距離が確定したノードを示す）（10）のRAM内の値iKを始点ノードiSにセットし、更に演算手段（1a）はRAM内の終点ノード記憶手段（14）に入力された終点ノードのiEを記憶する。距離未確定ノードデータ記憶手段（12）に記憶されたデータより始点ノードiSを除去して距離未確定サブノードデータ記憶手段（17）に記憶したデータより始点ノードiS以外のノードに属するサブノード全体の集合Ｑをセットし、更に演算手段（1a）は距離未確定サブノードデータ記憶手段（17）をチェックし、登録してあるサブノードｊについてサブノード暫定距離データ記憶手段（13）の値ｇ（ｊ）を無限大としてｇ（ｊ）＝∞とすることで第２のステップSTP2の初期化が終了する。
次の第３ステップSTP3で演算手段（1a）はノード、サブノード対応データ記憶手段（19）をチェックし、距離確定ノードポインタ（10）が指しているノードiK＝iS、即ち始点ノードiSに属するサブノードの集合Ｓ（iS）を求め、これらのサブノードに対して第４ステップSTP4から第７ステップSTP7（第５ステップSTP5及び第６ステップSTP6）の処理を行なう。
第５ステップSTP5では始点ノードiSに属するサブノードｊに接続しているサブノードｊ′を求めてｊ′＝ｌ（ｊ）とする。即ち演算手段（1a）はサブノード接続関係データ記憶手段（20）をチェックし、距離確定ノードポインタ（10）が指しているノードiK＝iSのサブノードｊに接続しているサブノードｊ′を求める。
次に第６ステップSTP6ではサブノードｊ′のサブノード暫定距離データ記憶手段（13）中の値をリンク長データ記憶手段（15）で調べて始点ノードiSのサブノードｊと結ぶリンク値に設定する。更に演算手段（1a）はサブノードｊ′に到達した経路前サブノード記憶手段（16）の値Ｒ（ｊ′）をｊにセットして経路前サブノードの登録を行なう。以上の処理を、始点ノードiSに属する全てのサブノードに対して処理したら演算手段（1a）は第８ステップSTP8で距離未確定サブノードデータ記憶手段（17）及びサブノード暫定距離データ記憶手段（13）をチェックし、距離が未確定であるサブノード中で暫定距離が最小であるサブノードｊ＊を求める。次の第９ステップSTP9では最小であるサブノードｊ＊が属するノードｉ＊を求める。第10ステップSTP10では演算手段（1a）は距離が確定したサブノードが属するノードｉ＊が終点ノードiEかどうかを判断し、“YES"であれば終了に至るが、“NO"であれば第11ステップSTP11に進む。第11ステップSTP11ではカウンタ（９）のｋを１インクリメントしてｋ＋１とし、距離確定ノードポインタ（10）の値iKを第９ステップSTP9で求めたサブノードにし、距離が確定したサブノードが属するノードの再設定iK＝ｉ＊が行なわれる。更に、距離が確定したサブノードが属するノードを距離確定サブノードポインタ（10）の値iKに再設定を行なうjK＝ｊ＊が行なわれる。そして確定距離の再設定の為に確定距離バッファ（11）の値Ｇを、サブノード暫定距離データ記憶手段（13）中の最小の値ｇ（jK）とする。又、距離未確定ノードデータ記憶手段（12）よりjKをとり出し、距離未確定サブノードデータ記憶手段（17）のサブノード集合Ｑより前記jKを除去する。第12ステップSTP12では演算手段（1a）はノード、サブノード対応データ記憶手段（19）をチェックし、距離確定ノードポインタ（10）が指しているノードiKに属するサブノードの集合Ｓ（iK）を求める。そして、この求めたサブノードに対して第13ステップSTP13から第19ステップSTP19までの処理を行なう。第14ステップSTP14ではサブノードｊと接続されたサブノードｌ（ｊ）を求めｊ′＝ｌ（ｊ）とする。第15ステップSTP15では演算手段（1a）が距離未確定サブノードデータ記憶手段（17）をチェックし、このサブノードｊ′が距離未確定ではない（“NO"）、即ち、距離が確定しているのであれば第19ステップSTP19に至るが距離が未確定（“YES"）であれば第16ステップSTP16に進む。第16ステップSTP16では前記距離が確定したサブノード（距離確定サブノードポインタ（18）が指している）jKよりｊへこの交差点iK内で進行することが可能か否かを演算手段（1a）は判断し、進行が不可能（“NO"）であれば第19ステップSTP19に至るが、進行が可能（“YES"）であれば第17ステップSTP17に進む。演算手段（1a）は交差点内サブノード間通行可、不可フラグ記憶手段（21）によって求める。そしてフラグについてはＦ（jk,j）＝“1"なら通行可であり“0"なら通行不可と定めておく。第17ステップSTP17ではjKを経由してｊ′へ進んだ場合の距離と、サブノード暫定距離データ記憶手段（13）中の始点ノードからの値を比較する。そして第18ステップSTP18で小さい方の値をサブノード暫定距離データ記憶手段（13）に登録し直してｇ（ｊ′）＝Ｇ＋djj′の更新が行なわれる。この更新が行なわれた場合には演算手段（1a）は経路前サブノード記憶手段（16）の値ｈ（ｊ′）をjkにして経路前サブノードの登録を行ない、以上の処理をノードiKに属する全てのサブノードに対して行なったら、演算手段（1a）は第20ステップSTP20及び第21ステップSTP21に示す様に距離未確定サブノードデータ記憶手段（17）及びサブノード暫定距離データ記憶手段（13）をチェックし、距離が未確定であるサブノードの中で暫定距離が最小であるノードを決定する。第22ステップSTP22ではｊ＊が属するノードｉ＊、即ち距離が確定したサブノードが終点ノードであるか否かの判定を行って“YES"であれば終了に至るが“NO"であれは第11ステップSPT11に戻ることになる。
上述のフローを第３図で定性的に説明すると、第３図では交差点（８）を例えば接続道路数＝４として４つのサブノード（61）（62）（63）（64）に展開する、そして接続道路数のサブノード（61）（62）（63）（64）と各サブノード間で通行可、不可フラグを立てて、例えば最小インピーダンス条件を満足する最短距離を求める場合には交差点（８）内に於いては例えば、サブノード（61）とサブノード（62）間で進行可、通行不可フラグをチェックし、進行可である場合のみ最短距離を求めるアルゴリズムを進める様にしたのでサブノード（61）とサブノード（62）間にリンクを考える必要もなく、データ量も、処理数も大幅に減少することになる。
本発明はダイクストラ法について説明したがニコルソン法にも適用可能であり、本発明の要旨を逸脱しない範囲で種々の変形が可能である。
〔発明の効果〕
本発明の最適経路検索方法によれば道路交通規則に従った正しい最適経過の検索が可能であり、且つデータ量が少なく検索速度を高速化することが出来るものである。
【図面の簡単な説明】
第１図は本発明の最適経路検索方法の一実施例を示す機能ブロック図、第２図は本発明の最適経路検索方法を示すフローチャート例、第３図は交差点でのサブノード説明図、第４図は従来のナビゲーション装置を示すブロック図、第５図は従来の交差点のサブノードとリンクの説明図である。
（１）は信号処理手段、（1a）は演算手段、（３）は地図データ記憶手段、（５）は入力手段、（19）はノード、サブノード対応データ記憶手段、（20）はサブノード間接続関係データ記憶手段、（21）は交差点内サブノード間通行可、不可フラグデータ記憶手段である。
〔産業上の利用分野〕
本発明は車両用ナビゲーション装置等に用いる道路ネットワークでの最適経路検索方法に関する。
〔発明の概要〕
本発明は車両用ナビゲーション装置等に用いる道路ネットワークでの最適経路検索方法に関し、流入出端を示す交差点を接続道路数の複数のサブノードとし、この複数のサブノード間に通行可又は通行不可のフラグを設け、道路ネットワークの最適経路検索時に交差点内の複数のサブノード間のフラグを同時に検索することで、交通規則に従った最適な経路を高速に得る様にしたものである。
〔従来の技術〕
従来、車両の現在位置を地図上に表示する車両用ナビゲーション装置は第４図の様に構成されていた。
第４図において、信号処理手段（１）はCPU及びROM、RAM等の記憶手段によって構成される。そして表示手段（２）は液晶、CRT等の表示用デバイスから成る。信号処理手段（１）には地図等の情報が記憶されたコンパクトディスクメモリ（以下CD−ROMという）の再生装置又は地図等の情報の記憶／再生を可能とする装置等から成る地図データ記憶手段（３）及び車両の進行方向に対し、例えば地磁気のＸ及びＹ成分を検出する方位センサと、この方位センサの出力を使用して車両の進行方向に応じて地磁気のX,Y成分のデジタル信号を発生する方位検出手段と、単位走行距離毎に所定パルス等を発生する距離センサ等を備える距離検出手段とから成る走行位置検出手段（４）とからなるデータが与えられ、これら各データはキーボード等からなる入力手段（５）の指示に基づき信号処理手段（１）が演算処理を実行し、特定地区の地図情報，信号処理手段（１）の演算結果，現在位置等を表示手段（２）に表示させる様に成されている。
上述のナビゲータ装置によれば表示手段（２）上に表示された道路ネットワーク画像をみながら出発地点と目的地点を入力手段（５）から入力指示すると、地図データ記憶手段（３）からの地図データに基づいて信号処理手段（１）内で最小インピーダンス経路を検索する。ここで最小インピーダンス経路とは入力手段（５）から与えられる入力条件に応じて、例えば最短距離、最小時間、或は最低料金等で出発地点から目的地点迄に到達するための経路であり、各交差点での右左折禁止条件、或はガソリン使用量、渋滞状況等が加味されて定められる。
例えば、出発地点から目的地点迄の最短の車両進行コースを道路用の地図データから検索する方法としては交差点を１つのノードとし、道路をリンクと考えて、ダイクストラ（Dijkstra）法、或はニコルソン（Nicholson）法を用いて道路ネットワーク内で始点ノードから、終点ノード迄の最短経路検索を行なう方法が知られている。
これらのうち例えば、ダイクストラ法で出発地点と目的地点迄の最短経路を求めるためのアルゴニズムは次の様に示される。
ここではｉはノード、dikiはノードik,iを結ぶリンク長を表わす。ｉ＝０は始点であり、ｉ＝Ｎは終点である。Ｇ（ｉ）は始点よりノードｉまでの最短路長を表わす、またＰはＧ（ｉ）がまだ求められていないノードの集合を表わす。
出発地点から目的地点迄の最短経路を検索する場合、交差点をノード、道路をリンクとして、地図データベースを構築したのでは各交差点での右左折禁止等のデータが存在しないため道路規則を正しく反映した最適経路の検索方法とならないために、第５図に示す様にインピーダンスを加味し、各交差点を接続道路数×２のサブノード（６）と、接続道路数×（接続道路数−１）のリンク（７）に分解する方法が情報処理学会、第33回（昭和61年後期）全国大会論文集2401頁、論文番号5W−５「首都圏道路網最適経路情報提供システム」に記載されている。
〔発明が解決しようとする課題〕
然し、この検索方法によっては、ノード数及びリンク数が大幅に増大し、取り扱うデータ量は膨大となる。更に交差点の入口から出口迄に１本のリンクを設定するために、この処理に１回のループ処理を要し、全体の検索時間が増大する欠点を有していた。
本発明は叙上の欠点に鑑みなされたもので、その目的とするところは最適経路検索を交通規則に従って高速に検索しようとするものである。
〔課題を解決するための手段〕
本発明の最適経路検索方法はその１例が第１図乃至第３図３図に示されている様に車の流入出端を示す交差点（８）を接続道路数と等しい複数のサブノード（61）（62）（63）（64）とし、複数のサブノード（61）（62）（63）（64）間に通行可又は通行不可のフラグデータを記憶した交差点内サブノード間通行可、不可フラグデータを記憶した記憶手段（21）と、サブノード暫定距離データ記憶手段（13）と、道路ネットワークの最適経路検索を行なう信号処理手段（1a）とを具備し、信号処理手段（1a）は道路ネットワークの最適経路検索時に交差点の前回距離が確定した距離確定サブノードより進行が可能か否かを交差点内サブノード間通行可、不可フラグデータ記憶手段（21）の通行可又は通行不可のフラグを読み込んで判断し、通行不可の場合は次のフロー動作に移行するが、通行可の場合は交差点（８）を経過し、次のサブノードへ進んだ場合の距離とサブノード暫定距離データ記憶手段（13）の値を比較し、小さい値をサブノード暫定距離データ記憶手段（13）に更新する様にしたものである。
〔作用〕
本発明の最適経路検索方法では交差点を複数の接続道路数のサブノードと、この複数のサブノード間に通行可又は通行不可のフラグを設けて、最適経路検索時に同時に検索する様にしたので道路交通規則にのっとった高速な検索を行なうことが出来る。
〔実施例〕
以下、本発明の最適経路検索方法の一実施例を第１図乃至第３図について詳記する。
第１図は本発明の最適経路検索方法を実現するための車載用ナビゲータ装置に用いられる信号処理手段（１）の機能ブロックを示すもので、他の部分については第４図R>図と同様に構成されているものとして第４図との対応部分とは同一符号を付してその説明を援用する。
第１図で入力手段（５）のキーボードから第１図に示されていないが表示手段（２）に表示される地図上に最適経路、例えば、出発地点から目的地点迄の最短経路を表示させるために出発地点と目的地点等が入力されると信号処理手段（１）は最適経路の検索を行なう様になされている。信号処理手段（１）内には演算手段（1a）を有し、この信号処理手段（１）内に通常配設されているROM,RAM等の記憶手段（以下RAMと記す）内にカウンタ（９）、距離確定ノードポインタ（10）、確定距離バッファ（11）、距離未確定ノードデータ記憶手段（12）、サブノード暫定距離データ記憶手段（13）、終点ノード記憶手段（14）、リンク長データ記憶手段（15）、経路前サブノード記憶手段（16）、距離未確定サブノードデータ記憶手段（17）、距離確定サブノードポインタ（18）、ノード、サブノード対応データ記憶手段（19）、サブノード接続関係データ記憶手段（20）、交差点サブノード間通行可、不可フラグデータ記憶手段（21）、距離最短サブノードバッファ（22）を備えている。
第２図は第１図のフローチャートを示すものであり、先ず、入手手段（５）から第１ステップSTP1に示す様に始点ノードiSと終点ノードiEを入力すると演算手段（1a）は第２ステップSTP2に示す様に初期化が行なわれる。演算手段（1a）はCPUのRAM内のカウンタ（９）のカウント値ｋをｋ＝０とし、距離確定ノードポインタ（前回のループで最短距離が確定したノードを示す）（10）のRAM内の値iKを始点ノードiSにセットし、更に演算手段（1a）はRAM内の終点ノード記憶手段（14）に入力された終点ノードのiEを記憶する。距離未確定ノードデータ記憶手段（12）に記憶されたデータより始点ノードiSを除去して距離未確定サブノードデータ記憶手段（17）に記憶したデータより始点ノードiS以外のノードに属するサブノード全体の集合Ｑをセットし、更に演算手段（1a）は距離未確定サブノードデータ記憶手段（17）をチェックし、登録してあるサブノードｊについてサブノード暫定距離データ記憶手段（13）の値ｇ（ｊ）を無限大としてｇ（ｊ）＝∞とすることで第２のステップSTP2の初期化が終了する。
次の第３ステップSTP3で演算手段（1a）はノード、サブノード対応データ記憶手段（19）をチェックし、距離確定ノードポインタ（10）が指しているノードiK＝iS、即ち始点ノードiSに属するサブノードの集合Ｓ（iS）を求め、これらのサブノードに対して第４ステップSTP4から第７ステップSTP7（第５ステップSTP5及び第６ステップSTP6）の処理を行なう。
第５ステップSTP5では始点ノードiSに属するサブノードｊに接続しているサブノードｊ′を求めてｊ′＝ｌ（ｊ）とする。即ち演算手段（1a）はサブノード接続関係データ記憶手段（20）をチェックし、距離確定ノードポインタ（10）が指しているノードiK＝iSのサブノードｊに接続しているサブノードｊ′を求める。
次に第６ステップSTP6ではサブノードｊ′のサブノード暫定距離データ記憶手段（13）中の値をリンク長データ記憶手段（15）で調べて始点ノードiSのサブノードｊと結ぶリンク値に設定する。更に演算手段（1a）はサブノードｊ′に到達した経路前サブノード記憶手段（16）の値Ｒ（ｊ′）をｊにセットして経路前サブノードの登録を行なう。以上の処理を、始点ノードiSに属する全てのサブノードに対して処理したら演算手段（1a）は第８ステップSTP8で距離未確定サブノードデータ記憶手段（17）及びサブノード暫定距離データ記憶手段（13）をチェックし、距離が未確定であるサブノード中で暫定距離が最小であるサブノードｊ＊を求める。次の第９ステップSTP9では最小であるサブノードｊ＊が属するノードｉ＊を求める。第10ステップSTP10では演算手段（1a）は距離が確定したサブノードが属するノードｉ＊が終点ノードiEかどうかを判断し、“YES"であれば終了に至るが、“NO"であれば第11ステップSTP11に進む。第11ステップSTP11ではカウンタ（９）のｋを１インクリメントしてｋ＋１とし、距離確定ノードポインタ（10）の値iKを第９ステップSTP9で求めたサブノードにし、距離が確定したサブノードが属するノードの再設定iK＝ｉ＊が行なわれる。更に、距離が確定したサブノードが属するノードを距離確定サブノードポインタ（10）の値iKに再設定を行なうjK＝ｊ＊が行なわれる。そして確定距離の再設定の為に確定距離バッファ（11）の値Ｇを、サブノード暫定距離データ記憶手段（13）中の最小の値ｇ（jK）とする。又、距離未確定ノードデータ記憶手段（12）よりjKをとり出し、距離未確定サブノードデータ記憶手段（17）のサブノード集合Ｑより前記jKを除去する。第12ステップSTP12では演算手段（1a）はノード、サブノード対応データ記憶手段（19）をチェックし、距離確定ノードポインタ（10）が指しているノードiKに属するサブノードの集合Ｓ（iK）を求める。そして、この求めたサブノードに対して第13ステップSTP13から第19ステップSTP19までの処理を行なう。第14ステップSTP14ではサブノードｊと接続されたサブノードｌ（ｊ）を求めｊ′＝ｌ（ｊ）とする。第15ステップSTP15では演算手段（1a）が距離未確定サブノードデータ記憶手段（17）をチェックし、このサブノードｊ′が距離未確定ではない（“NO"）、即ち、距離が確定しているのであれば第19ステップSTP19に至るが距離が未確定（“YES"）であれば第16ステップSTP16に進む。第16ステップSTP16では前記距離が確定したサブノード（距離確定サブノードポインタ（18）が指している）jKよりｊへこの交差点iK内で進行することが可能か否かを演算手段（1a）は判断し、進行が不可能（“NO"）であれば第19ステップSTP19に至るが、進行が可能（“YES"）であれば第17ステップSTP17に進む。演算手段（1a）は交差点内サブノード間通行可、不可フラグ記憶手段（21）によって求める。そしてフラグについてはＦ（jk,j）＝“1"なら通行可であり“0"なら通行不可と定めておく。第17ステップSTP17ではjKを経由してｊ′へ進んだ場合の距離と、サブノード暫定距離データ記憶手段（13）中の始点ノードからの値を比較する。そして第18ステップSTP18で小さい方の値をサブノード暫定距離データ記憶手段（13）に登録し直してｇ（ｊ′）＝Ｇ＋djj′の更新が行なわれる。この更新が行なわれた場合には演算手段（1a）は経路前サブノード記憶手段（16）の値ｈ（ｊ′）をjkにして経路前サブノードの登録を行ない、以上の処理をノードiKに属する全てのサブノードに対して行なったら、演算手段（1a）は第20ステップSTP20及び第21ステップSTP21に示す様に距離未確定サブノードデータ記憶手段（17）及びサブノード暫定距離データ記憶手段（13）をチェックし、距離が未確定であるサブノードの中で暫定距離が最小であるノードを決定する。第22ステップSTP22ではｊ＊が属するノードｉ＊、即ち距離が確定したサブノードが終点ノードであるか否かの判定を行って“YES"であれば終了に至るが“NO"であれは第11ステップSPT11に戻ることになる。
上述のフローを第３図で定性的に説明すると、第３図では交差点（８）を例えば接続道路数＝４として４つのサブノード（61）（62）（63）（64）に展開する、そして接続道路数のサブノード（61）（62）（63）（64）と各サブノード間で通行可、不可フラグを立てて、例えば最小インピーダンス条件を満足する最短距離を求める場合には交差点（８）内に於いては例えば、サブノード（61）とサブノード（62）間で進行可、通行不可フラグをチェックし、進行可である場合のみ最短距離を求めるアルゴリズムを進める様にしたのでサブノード（61）とサブノード（62）間にリンクを考える必要もなく、データ量も、処理数も大幅に減少することになる。
本発明はダイクストラ法について説明したがニコルソン法にも適用可能であり、本発明の要旨を逸脱しない範囲で種々の変形が可能である。
〔発明の効果〕
本発明の最適経路検索方法によれば道路交通規則に従った正しい最適経過の検索が可能であり、且つデータ量が少なく検索速度を高速化することが出来るものである。
【図面の簡単な説明】
第１図は本発明の最適経路検索方法の一実施例を示す機能ブロック図、第２図は本発明の最適経路検索方法を示すフローチャート例、第３図は交差点でのサブノード説明図、第４図は従来のナビゲーション装置を示すブロック図、第５図は従来の交差点のサブノードとリンクの説明図である。
（１）は信号処理手段、（1a）は演算手段、（３）は地図データ記憶手段、（５）は入力手段、（19）はノード、サブノード対応データ記憶手段、（20）はサブノード間接続関係データ記憶手段、（21）は交差点内サブノード間通行可、不可フラグデータ記憶手段である。
【特許請求の範囲】
【請求項１】車の流入出端を示す交差点を接続道路数と等しい複数のサブノードとし、該複数のサブノード間に通行可又は通行不可のフラグデータを記憶した交差点内サブノード間通行可、不可フラグデータを記憶した記憶手段と、サブノード暫定距離データ記憶手段と、道路ネットワークの最適経路検索を行なう信号処理手段とを具備し、上記信号処理手段は道路ネットワークの最適経路検索時に上記交差点の前回距離が確定した距離確定サブノードより進行が可能か否かを上記交差点内サブノード間通行可、不可フラグデータ記憶手段の通行可又は通行不可のフラグを読み込んで判断し、通行不可の場合は次のフロー動作に移行するが、通行可の場合は該交差点を経過し、次のサブノードへ進んだ場合の距離と上記サブノード暫定距離データ記憶手段の値を比較し、小さい値を該サブノード暫定距離データ記憶手段に更新する様に成したこを特徴とする最適経路検索方法。
【請求項１】車の流入出端を示す交差点を接続道路数と等しい複数のサブノードとし、該複数のサブノード間に通行可又は通行不可のフラグデータを記憶した交差点内サブノード間通行可、不可フラグデータを記憶した記憶手段と、サブノード暫定距離データ記憶手段と、道路ネットワークの最適経路検索を行なう信号処理手段とを具備し、上記信号処理手段は道路ネットワークの最適経路検索時に上記交差点の前回距離が確定した距離確定サブノードより進行が可能か否かを上記交差点内サブノード間通行可、不可フラグデータ記憶手段の通行可又は通行不可のフラグを読み込んで判断し、通行不可の場合は次のフロー動作に移行するが、通行可の場合は該交差点を経過し、次のサブノードへ進んだ場合の距離と上記サブノード暫定距離データ記憶手段の値を比較し、小さい値を該サブノード暫定距離データ記憶手段に更新する様に成したこを特徴とする最適経路検索方法。
【第１図】
【第５図】
【第２図】
【第３図】
【第４図】
【第５図】
【第２図】
【第３図】
【第４図】
【特許番号】第２８２１６０４号
【登録日】平成１０年（１９９８）９月４日
【発行日】平成１０年（１９９８）１１月５日
【国際特許分類】
【出願番号】特願平１−５２６７
【出願日】平成１年（１９８９）１月１２日
【公開番号】特開平２−１８４９９９
【公開日】平成２年（１９９０）７月１９日
【審査請求日】平成８年（１９９６）１月１２日
【出願人】（９９９９９９９９９）ソニー株式会社
【参考文献】
【文献】特開 昭６２−８２３１６（ＪＰ，Ａ）
【文献】特開 平１−１７３２９７（ＪＰ，Ａ）
【文献】特開 平２−３８９９（ＪＰ，Ａ）
【文献】特開 昭６３−１０２９９（ＪＰ，Ａ）
【登録日】平成１０年（１９９８）９月４日
【発行日】平成１０年（１９９８）１１月５日
【国際特許分類】
【出願日】平成１年（１９８９）１月１２日
【公開番号】特開平２−１８４９９９
【公開日】平成２年（１９９０）７月１９日
【審査請求日】平成８年（１９９６）１月１２日
【出願人】（９９９９９９９９９）ソニー株式会社
【参考文献】
【文献】特開 昭６２−８２３１６（ＪＰ，Ａ）
【文献】特開 平１−１７３２９７（ＪＰ，Ａ）
【文献】特開 平２−３８９９（ＪＰ，Ａ）
【文献】特開 昭６３−１０２９９（ＪＰ，Ａ）
[ Back to top ]