JP2834952B2 - 経路探索方法 - Google Patents
経路探索方法Info
- Publication number
- JP2834952B2 JP2834952B2 JP28426392A JP28426392A JP2834952B2 JP 2834952 B2 JP2834952 B2 JP 2834952B2 JP 28426392 A JP28426392 A JP 28426392A JP 28426392 A JP28426392 A JP 28426392A JP 2834952 B2 JP2834952 B2 JP 2834952B2
- Authority
- JP
- Japan
- Prior art keywords
- intersection
- adjacent
- search
- route
- destination
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims description 76
- 238000013138 pruning Methods 0.000 claims description 21
- 239000013256 coordination polymer Substances 0.000 description 90
- 230000001186 cumulative effect Effects 0.000 description 38
- 238000010586 diagram Methods 0.000 description 27
- 238000001514 detection method Methods 0.000 description 7
- 230000002194 synthesizing effect Effects 0.000 description 5
- 244000141353 Prunus domestica Species 0.000 description 3
- 239000000470 constituent Substances 0.000 description 3
- 230000006870 function Effects 0.000 description 3
- 241000406668 Loxodonta cyclotis Species 0.000 description 2
- 238000004364 calculation method Methods 0.000 description 2
- 101100325756 Arabidopsis thaliana BAM5 gene Proteins 0.000 description 1
- 101150046378 RAM1 gene Proteins 0.000 description 1
- 101100476489 Rattus norvegicus Slc20a2 gene Proteins 0.000 description 1
- 241000555745 Sciuridae Species 0.000 description 1
- 238000009825 accumulation Methods 0.000 description 1
- 239000008186 active pharmaceutical agent Substances 0.000 description 1
- 230000001174 ascending effect Effects 0.000 description 1
- 230000007423 decrease Effects 0.000 description 1
- 230000002035 prolonged effect Effects 0.000 description 1
- 230000000717 retained effect Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
- G01C21/34—Route searching; Route guidance
- G01C21/3446—Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Navigation (AREA)
- Traffic Control Systems (AREA)
- Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
- Instructional Devices (AREA)
Description
【０００１】
【産業上の利用分野】本発明は経路探索方法に係り、特
に道路データを参照して出発地から目的地までを結ぶ最
適経路を探索する際、出発地から目的地に向けた方向か
ら外れる経路を枝刈りしたり優先度を下げて探索するよ
うにした経路探索方法に関する。
に道路データを参照して出発地から目的地までを結ぶ最
適経路を探索する際、出発地から目的地に向けた方向か
ら外れる経路を枝刈りしたり優先度を下げて探索するよ
うにした経路探索方法に関する。
【０００２】
【従来の技術】車載ナビゲータは、大量の地図データを
記憶するＣＤ−ＲＯＭ等の大容量記憶装置、ディスプレ
イ装置、車両の現在位置を検出する車両位置検出装置等
を有し、車両の現在位置に応じた地図データをＣＤ−Ｒ
ＯＭから読み出し、該地図データに基づいて地図をディ
スプレイ画面に描画するとともに、車両位置マーク（ロ
ケーションカーソル）をディスプレイ画面の特定位置
（例えば画面中央）に固定し、車両の移動に応じて地図
をスクロール表示したり、或いは地図は画面に固定し、
車両位置マークを移動表示したりして、車両が現在どこ
を走行しているか一目で判るようにしてある。
記憶するＣＤ−ＲＯＭ等の大容量記憶装置、ディスプレ
イ装置、車両の現在位置を検出する車両位置検出装置等
を有し、車両の現在位置に応じた地図データをＣＤ−Ｒ
ＯＭから読み出し、該地図データに基づいて地図をディ
スプレイ画面に描画するとともに、車両位置マーク（ロ
ケーションカーソル）をディスプレイ画面の特定位置
（例えば画面中央）に固定し、車両の移動に応じて地図
をスクロール表示したり、或いは地図は画面に固定し、
車両位置マークを移動表示したりして、車両が現在どこ
を走行しているか一目で判るようにしてある。
【０００３】ＣＤ−ＲＯＭに記憶されている地図は縮尺
レベルに応じて適当な大きさの経度幅、緯度幅の図葉に
区切られており、道路等は経緯度で表現された頂点（ノ
ード）の座標集合で示され、これらの描画は各ノードを
順に直線で接続することにより行われる。なお、道路は
２以上のノードの連結からなり、２つのノードを連結し
た部分はリンクと呼ばれる。地図データは、図１９に示
す如く、１枚の図葉を４分割したデータユニット毎（４
分割図葉毎）にまとめられており、１データユニットが
１画面に相当している。地図データには、（１）道路リ
スト、ノードテーブル、交差点構成ノードリスト、隣接
ノードリストなどからなる道路レイヤ、（２）地図画面
上の道路、建物、河川等を表示するための背景レイヤ、
（３）市町村名、道路名等を表示するための文字レイヤ
などから構成されている。
レベルに応じて適当な大きさの経度幅、緯度幅の図葉に
区切られており、道路等は経緯度で表現された頂点（ノ
ード）の座標集合で示され、これらの描画は各ノードを
順に直線で接続することにより行われる。なお、道路は
２以上のノードの連結からなり、２つのノードを連結し
た部分はリンクと呼ばれる。地図データは、図１９に示
す如く、１枚の図葉を４分割したデータユニット毎（４
分割図葉毎）にまとめられており、１データユニットが
１画面に相当している。地図データには、（１）道路リ
スト、ノードテーブル、交差点構成ノードリスト、隣接
ノードリストなどからなる道路レイヤ、（２）地図画面
上の道路、建物、河川等を表示するための背景レイヤ、
（３）市町村名、道路名等を表示するための文字レイヤ
などから構成されている。
【０００４】この内、道路レイヤは図２０に示す構成を
有している。道路リストＲＤＬＴは道路別に、道路の種
別（高速道路、国道、その他の道路）、道路を構成する
全ノード数、道路を構成するノードのノードテーブルＮ
ＤＴＢ上での位置と、次のノードまでの幅員等のデータ
より構成されている。交差点構成ノードリストＣＲＬＴ
は地図上の各交差点毎の該交差点に連結するリンク他端
ノード（交差点構成ノードという）のノードテーブルＮ
ＤＴＢ上での位置の集合である。隣接ノードリストＮＮ
ＬＴは、ノードが複数のユニットに跨がる道路について
ユニット境界に定義されて複数のユニットに共有される
隣接ノードの場合（図２１参照）、自身のユニットを除
いて他に共有するユニット数を示す隣接ノード数（図２
１（１）でユニットＡＵ1 （ＡＵ2 ）で定義された隣接
ノードＲＮについて、他に共有するユニットはＡＵ
2 （ＡＵ1 ）の１つであるから隣接ノード数は１、図２
１（２）でユニットＡＵ11で定義された隣接ノードＲＮ
について、他に共有するユニットはＡＵ11、ＡＵ21、Ａ
Ｕ22の３つであるから隣接ノード数は３）、図葉番号、
該図葉内で隣接ノードが属するユニットコード、該ユニ
ットでのノードテーブル上での位置により構成される。
ノードテーブルＮＤＴＢは地図上の全ノードのリストで
あり、ノード毎に座標情報（経度、緯度）、該ノードが
交差点であるか否かの交差点識別フラグ、交差点であれ
ば交差点構成ノードリスト上での位置を指し、交差点で
なければ道路リスト上で当該ノードが属する道路の位置
を指すポインタ、また、当該ノードが隣接ノードである
か否かの隣接ノード識別フラグ、隣接ノードであれば、
隣接ノードリストＮＮＬＴでの位置を指すポインタ等で
構成されている。
有している。道路リストＲＤＬＴは道路別に、道路の種
別（高速道路、国道、その他の道路）、道路を構成する
全ノード数、道路を構成するノードのノードテーブルＮ
ＤＴＢ上での位置と、次のノードまでの幅員等のデータ
より構成されている。交差点構成ノードリストＣＲＬＴ
は地図上の各交差点毎の該交差点に連結するリンク他端
ノード（交差点構成ノードという）のノードテーブルＮ
ＤＴＢ上での位置の集合である。隣接ノードリストＮＮ
ＬＴは、ノードが複数のユニットに跨がる道路について
ユニット境界に定義されて複数のユニットに共有される
隣接ノードの場合（図２１参照）、自身のユニットを除
いて他に共有するユニット数を示す隣接ノード数（図２
１（１）でユニットＡＵ1 （ＡＵ2 ）で定義された隣接
ノードＲＮについて、他に共有するユニットはＡＵ
2 （ＡＵ1 ）の１つであるから隣接ノード数は１、図２
１（２）でユニットＡＵ11で定義された隣接ノードＲＮ
について、他に共有するユニットはＡＵ11、ＡＵ21、Ａ
Ｕ22の３つであるから隣接ノード数は３）、図葉番号、
該図葉内で隣接ノードが属するユニットコード、該ユニ
ットでのノードテーブル上での位置により構成される。
ノードテーブルＮＤＴＢは地図上の全ノードのリストで
あり、ノード毎に座標情報（経度、緯度）、該ノードが
交差点であるか否かの交差点識別フラグ、交差点であれ
ば交差点構成ノードリスト上での位置を指し、交差点で
なければ道路リスト上で当該ノードが属する道路の位置
を指すポインタ、また、当該ノードが隣接ノードである
か否かの隣接ノード識別フラグ、隣接ノードであれば、
隣接ノードリストＮＮＬＴでの位置を指すポインタ等で
構成されている。
【０００５】ところで車載ナビゲータには、出発地から
目的地まで最短距離を辿るような最適経路を探索し、画
面に誘導経路表示して運転者の走行案内をする経路誘導
機能があり、実際の運転に際して、誘導経路を特定色で
太く表示するなど他の道路と識別可能にしたりして、運
転者が目的地まで容易に到達できるようにしてある。出
発地から目的地を結ぶ最適経路を求める方法として、横
型探索法を利用した方法が提案されている。この方法
は、道路データを参照して、出発地と目的地を結ぶ直線
を対角線とする方形領域を全て含む１又は隣接する複数
の４分割図葉内に存在する全交差点（本来の交差点のほ
か、隣接ノードとなっている単純ノードも含む）を対象
にして、各交差点につき、交差点ネットリストＣＲＮＬ
を作成し、経路探索メモリに記憶しておき、出発地から
目的地迄の最短経路を交差点ネットリストを参照して探
索するものである。
目的地まで最短距離を辿るような最適経路を探索し、画
面に誘導経路表示して運転者の走行案内をする経路誘導
機能があり、実際の運転に際して、誘導経路を特定色で
太く表示するなど他の道路と識別可能にしたりして、運
転者が目的地まで容易に到達できるようにしてある。出
発地から目的地を結ぶ最適経路を求める方法として、横
型探索法を利用した方法が提案されている。この方法
は、道路データを参照して、出発地と目的地を結ぶ直線
を対角線とする方形領域を全て含む１又は隣接する複数
の４分割図葉内に存在する全交差点（本来の交差点のほ
か、隣接ノードとなっている単純ノードも含む）を対象
にして、各交差点につき、交差点ネットリストＣＲＮＬ
を作成し、経路探索メモリに記憶しておき、出発地から
目的地迄の最短経路を交差点ネットリストを参照して探
索するものである。
【０００６】交差点ネットリストＣＲＮＬは、交差点
（交差点ノードのほか、単純ノードの内、隣接ノードと
なっているものを含む。）毎に、 （１）交差点シーケンシャル番号（当該交差点を特定す
る情報） （２）該交差点が含まれる地図の図葉番号 （３）データユニットコード （４）ノードテーブル上の位置 （５）経度 （６）緯度 以上、交差点ＩＤ （７）交差点構成ノードリスト上の位置（当該交差点が
本来の交差点ノードのとき） （８）交差点構成ノード数（同上） （９）隣接ノードリスト上の位置（当該交差点が隣接ノ
ードのとき） （１０）隣接ノード数（同上） （１１）各隣接交差点のシーケンシャル番号 （１２）各隣接交差点までの距離 （１３）当該交差点の１つ手前の交差点シーケンシャル
番号 （１４）出発地から当該交差点までの累計距離 （１５）当該交差点の検索次数 等が登録されるようになっている（但し、（１３）〜
（１５）は経路探索実行時に登録される）。
（交差点ノードのほか、単純ノードの内、隣接ノードと
なっているものを含む。）毎に、 （１）交差点シーケンシャル番号（当該交差点を特定す
る情報） （２）該交差点が含まれる地図の図葉番号 （３）データユニットコード （４）ノードテーブル上の位置 （５）経度 （６）緯度 以上、交差点ＩＤ （７）交差点構成ノードリスト上の位置（当該交差点が
本来の交差点ノードのとき） （８）交差点構成ノード数（同上） （９）隣接ノードリスト上の位置（当該交差点が隣接ノ
ードのとき） （１０）隣接ノード数（同上） （１１）各隣接交差点のシーケンシャル番号 （１２）各隣接交差点までの距離 （１３）当該交差点の１つ手前の交差点シーケンシャル
番号 （１４）出発地から当該交差点までの累計距離 （１５）当該交差点の検索次数 等が登録されるようになっている（但し、（１３）〜
（１５）は経路探索実行時に登録される）。
【０００７】交差点ネットリストＣＲＮＬの作成手法
は、まず、図２２に示す如く、出発地と目的地を結ぶ直
線を対角線とする方形領域を含む各図葉につき、地図デ
ータの図葉管理情報から図葉番号を得る。そして、地図
データからこれらの各図葉の中で、出発地と目的地を結
ぶ直線を対角線とする方形領域を含む各４分割図葉（図
２２のＡＵ11〜ＡＵ44）に対する道路データを入力し
（個々の４分割図葉は、図葉番号とデータユニットコー
ドで特定される）、ノードテーブルＮＤＴＢから交差点
識別フラグや隣接ノード識別フラグの立っているノード
を探し、連番で交差点シーケンシャル番号（１）をふっ
た交差点ネットリストを経路探索メモリ上に用意し、交
差点ＩＤを登録する（（２）〜（６））。そして、ノー
ドテーブル、交差点構成ノードリスト、隣接ノードリス
トから、交差点構成ノードリスト上の位置、交差点構成
ノード数、隣接ノードリスト上の位置、隣接ノード数を
得て、（７）〜（１０）を登録する。次に、道路リスト
ＲＤＬＴの各道路につき、ノードテーブルＮＤＴＢを参
照して、相隣る交差点（一方が単純ノードでの隣接ノー
ドの場合を含む）相互間のリンクの距離を求め、リンク
の一方の交差点に係る交差点ネットリストに、リンクの
他方の交差点を隣接交差点とし、該隣接交差点に係る交
差点ネットリストに登録された交差点シーケンシャル番
号（隣接交差点シーケンシャル番号）、当該リンクの距
離を登録していく（（１１）、（１２））。そして、交
差点ネットリストの作られた対象が、交差点ノードで隣
接ノードを兼ねている場合と、単純ノードの隣接ノード
である場合、同一隣接ノードにつき、他の共有ユニット
の下でも交差点ネットリストが作られている場合がある
ことから、隣接ノードリストＮＮＬＴを参照して、他の
全ての共有ユニットでの交差点シーケンシャル番号を探
し、当該交差点ネットリストの中に、隣接交差点シーケ
ンシャル番号と距離を登録し、隣接ノード接続処理を行
う。この際、距離は０とする。
は、まず、図２２に示す如く、出発地と目的地を結ぶ直
線を対角線とする方形領域を含む各図葉につき、地図デ
ータの図葉管理情報から図葉番号を得る。そして、地図
データからこれらの各図葉の中で、出発地と目的地を結
ぶ直線を対角線とする方形領域を含む各４分割図葉（図
２２のＡＵ11〜ＡＵ44）に対する道路データを入力し
（個々の４分割図葉は、図葉番号とデータユニットコー
ドで特定される）、ノードテーブルＮＤＴＢから交差点
識別フラグや隣接ノード識別フラグの立っているノード
を探し、連番で交差点シーケンシャル番号（１）をふっ
た交差点ネットリストを経路探索メモリ上に用意し、交
差点ＩＤを登録する（（２）〜（６））。そして、ノー
ドテーブル、交差点構成ノードリスト、隣接ノードリス
トから、交差点構成ノードリスト上の位置、交差点構成
ノード数、隣接ノードリスト上の位置、隣接ノード数を
得て、（７）〜（１０）を登録する。次に、道路リスト
ＲＤＬＴの各道路につき、ノードテーブルＮＤＴＢを参
照して、相隣る交差点（一方が単純ノードでの隣接ノー
ドの場合を含む）相互間のリンクの距離を求め、リンク
の一方の交差点に係る交差点ネットリストに、リンクの
他方の交差点を隣接交差点とし、該隣接交差点に係る交
差点ネットリストに登録された交差点シーケンシャル番
号（隣接交差点シーケンシャル番号）、当該リンクの距
離を登録していく（（１１）、（１２））。そして、交
差点ネットリストの作られた対象が、交差点ノードで隣
接ノードを兼ねている場合と、単純ノードの隣接ノード
である場合、同一隣接ノードにつき、他の共有ユニット
の下でも交差点ネットリストが作られている場合がある
ことから、隣接ノードリストＮＮＬＴを参照して、他の
全ての共有ユニットでの交差点シーケンシャル番号を探
し、当該交差点ネットリストの中に、隣接交差点シーケ
ンシャル番号と距離を登録し、隣接ノード接続処理を行
う。この際、距離は０とする。
【０００８】このようにして、交差点ネットリストＣＲ
ＮＬが完成したならば、出発地データと目的地データに
基づき、横型探索法により最適経路の探索処理を行う。
図２３は横型探索法の概略説明図であり、道路を直線、
交差点（単純ノードでの隣接ノードを含む）を直線の交
点としてクラフ化したものであり、各交差点間の距離は
既知で、ＳＴＰは出発地（交差点）、ＤＳＰは目的地
（交差点）である。横型探索法においては、交差点ネッ
トリストＣＲＮＬを参照しながら、出発地を０次交差点
（次数０は交差点ネットリストの（１５）に登録され
る）として、該０次交差点に道路に沿って隣接する１次
交差点Ａ1 〜Ａ4 を探し、各１次交差点Ａ1 〜Ａ4 につ
き、対応する１つ手前の交差点（次数の１つ低い交差
点。ここでは、出発地交差点）を経由した出発地からの
累計距離を求め、各交差点Ａ1 〜Ａ4 に対応させて、各
々の交差点ネットリスト中に、１つ手前の交差点を特定
する交差点シーケンシャル番号、検索次数１とともに登
録する（交差点ネットリストの（１３）〜（１５））。
次いで、各１次交差点Ａ1 〜Ａ4 について２次交差点Ｂ
ijを探し、各２次交差点につき、対応する１つ手前の１
次交差点を経由した出発地からの累計距離を求め、各交
差点Ｂijに対応させて、各々の交差点ネットリストに１
つ手前の交差点を特定する交差点シーケンシャル番号、
検索次数２とともに登録する。
ＮＬが完成したならば、出発地データと目的地データに
基づき、横型探索法により最適経路の探索処理を行う。
図２３は横型探索法の概略説明図であり、道路を直線、
交差点（単純ノードでの隣接ノードを含む）を直線の交
点としてクラフ化したものであり、各交差点間の距離は
既知で、ＳＴＰは出発地（交差点）、ＤＳＰは目的地
（交差点）である。横型探索法においては、交差点ネッ
トリストＣＲＮＬを参照しながら、出発地を０次交差点
（次数０は交差点ネットリストの（１５）に登録され
る）として、該０次交差点に道路に沿って隣接する１次
交差点Ａ1 〜Ａ4 を探し、各１次交差点Ａ1 〜Ａ4 につ
き、対応する１つ手前の交差点（次数の１つ低い交差
点。ここでは、出発地交差点）を経由した出発地からの
累計距離を求め、各交差点Ａ1 〜Ａ4 に対応させて、各
々の交差点ネットリスト中に、１つ手前の交差点を特定
する交差点シーケンシャル番号、検索次数１とともに登
録する（交差点ネットリストの（１３）〜（１５））。
次いで、各１次交差点Ａ1 〜Ａ4 について２次交差点Ｂ
ijを探し、各２次交差点につき、対応する１つ手前の１
次交差点を経由した出発地からの累計距離を求め、各交
差点Ｂijに対応させて、各々の交差点ネットリストに１
つ手前の交差点を特定する交差点シーケンシャル番号、
検索次数２とともに登録する。
【０００９】例えば、１次交差点Ａ1 については３つの
２次交差点Ｂ11，Ｂ12，Ｂ13を見出し、これら各交差点
に対応させて、 Ｂ11：１次交差点Ａ1 経由での出発地からの累計距離Ｂｄ11 Ｂ12：１次交差点Ａ1 経由での出発地からの累計距離Ｂｄ12 Ｂ13：１次交差点Ａ1 経由での出発地からの累計距離Ｂｄ13 ・・（ａ） を対応する交差点Ａ1 の交差点シーケンシャル番号とと
もに記憶する。また、１次交差点Ａ2 に対しては３つの
２次交差点Ｂ21，Ｂ22，Ｂ23が求まり、各２次交差点Ｂ
21，Ｂ22，Ｂ23に対応させて、 Ｂ21：１次交差点Ａ2 経由での出発地からの累計距離Ｂｄ21 Ｂ22：１次交差点Ａ2 経由での出発地からの累計距離Ｂｄ22 Ｂ23：１次交差点Ａ2 経由での出発地からの累計距離Ｂｄ23 ・・（ｂ） を対応する交差点Ａ1 の交差点シーケンシャル番号とと
もに記憶する。他の１次交差点Ａ3 ，Ａ4 についても同
様に隣接する２次交差点を探して所定のデータを記憶す
る。ところで、交差点Ｂ13とＢ21は同一の交差点であ
る。このように、データを記憶すべき交差点が重複し、
既に、該交差点に対し、異なる経路での累計距離が記憶
されているとき、（ａ）の累計距離Ｂｄ13と（ｂ）の累
計距離Ｂｄ21の大小を比較し、小さい方のデータに書き
換えて記憶する。たとえば、Ｂｄ13＞Ｂｄ21であれば、
交差点Ｂ13（＝Ｂ21）の交差点ネットリストには、
（ｂ）に示す累計距離Ｂｄ21と対応する１つ手前の交差
点Ａ2 のシーケンシャル番号が最終的に記憶される。
２次交差点Ｂ11，Ｂ12，Ｂ13を見出し、これら各交差点
に対応させて、 Ｂ11：１次交差点Ａ1 経由での出発地からの累計距離Ｂｄ11 Ｂ12：１次交差点Ａ1 経由での出発地からの累計距離Ｂｄ12 Ｂ13：１次交差点Ａ1 経由での出発地からの累計距離Ｂｄ13 ・・（ａ） を対応する交差点Ａ1 の交差点シーケンシャル番号とと
もに記憶する。また、１次交差点Ａ2 に対しては３つの
２次交差点Ｂ21，Ｂ22，Ｂ23が求まり、各２次交差点Ｂ
21，Ｂ22，Ｂ23に対応させて、 Ｂ21：１次交差点Ａ2 経由での出発地からの累計距離Ｂｄ21 Ｂ22：１次交差点Ａ2 経由での出発地からの累計距離Ｂｄ22 Ｂ23：１次交差点Ａ2 経由での出発地からの累計距離Ｂｄ23 ・・（ｂ） を対応する交差点Ａ1 の交差点シーケンシャル番号とと
もに記憶する。他の１次交差点Ａ3 ，Ａ4 についても同
様に隣接する２次交差点を探して所定のデータを記憶す
る。ところで、交差点Ｂ13とＢ21は同一の交差点であ
る。このように、データを記憶すべき交差点が重複し、
既に、該交差点に対し、異なる経路での累計距離が記憶
されているとき、（ａ）の累計距離Ｂｄ13と（ｂ）の累
計距離Ｂｄ21の大小を比較し、小さい方のデータに書き
換えて記憶する。たとえば、Ｂｄ13＞Ｂｄ21であれば、
交差点Ｂ13（＝Ｂ21）の交差点ネットリストには、
（ｂ）に示す累計距離Ｂｄ21と対応する１つ手前の交差
点Ａ2 のシーケンシャル番号が最終的に記憶される。
【００１０】以降、同様にして、各２次交差点Ｂijにつ
いて隣接する３次交差点Ｃijを求め、各交差点Ｃijにつ
き、対応する１つ手前の交差点を経由する出発地からの
累計距離を求め、当該１つ手前の交差点シーケンシャル
番号とともに記憶し、一般に、交差点ネットリストを参
照しながら各第ｉ次交差点について第（ｉ＋１）次交差
点を求め、各第（ｉ＋１）次交差点につき、１つ手前の
第ｉ次交差点を経由する出発地からの累計距離を求め、
１つ手前の交差点の交差点シーケンシャル番号ととも
に、第（ｉ＋１）次交差点の交差点ネットリストに記憶
していけば、最終的に目的地（交差点）ＤＳＰに到達す
る。目的地に到達したあと、目的地（ｍ次交差点とす
る）の交差点ネットリストに記憶してある（ｍ−１）次
の交差点、（ｍ−１）次の交差点の交差点ネットリスト
に記憶してある（ｍ−２）次の交差点、・・・、２次の
交差点の交差点ネットリストに記憶してある１次交差
点、１次交差点の交差点ネットリストに記憶してある０
次の交差点（出発地）を、順次、出発地側から目的地側
に向けた順序で結んでなる経路が最短の最適経路とな
る。
いて隣接する３次交差点Ｃijを求め、各交差点Ｃijにつ
き、対応する１つ手前の交差点を経由する出発地からの
累計距離を求め、当該１つ手前の交差点シーケンシャル
番号とともに記憶し、一般に、交差点ネットリストを参
照しながら各第ｉ次交差点について第（ｉ＋１）次交差
点を求め、各第（ｉ＋１）次交差点につき、１つ手前の
第ｉ次交差点を経由する出発地からの累計距離を求め、
１つ手前の交差点の交差点シーケンシャル番号ととも
に、第（ｉ＋１）次交差点の交差点ネットリストに記憶
していけば、最終的に目的地（交差点）ＤＳＰに到達す
る。目的地に到達したあと、目的地（ｍ次交差点とす
る）の交差点ネットリストに記憶してある（ｍ−１）次
の交差点、（ｍ−１）次の交差点の交差点ネットリスト
に記憶してある（ｍ−２）次の交差点、・・・、２次の
交差点の交差点ネットリストに記憶してある１次交差
点、１次交差点の交差点ネットリストに記憶してある０
次の交差点（出発地）を、順次、出発地側から目的地側
に向けた順序で結んでなる経路が最短の最適経路とな
る。
【００１１】但し、有る経路で目的地に到達しても、目
的地の交差点ネットリストに記憶された累計距離に対
し、累計距離の短い経路が存在する間は経路探索を継続
し、若し、他の経路でも目的地に到達したとき、該経路
での累計距離の方が、既に目的地の交差点ネットリスト
に記憶されている累計距離より短ければ、書き換えを行
い、その後、どの経路も目的地の交差点ネットリストに
登録された累計距離より長くなったとき、経路探索を終
えるようにしてもよい。また、交差点ネットリストＣＲ
ＮＬは、以上のようにＣＤ−ＲＯＭに記憶された、交差
点ネットリストを含まない道路データから車載ナビゲー
タ内で作成し、道路リスト、交差点ネットリスト等と合
わせて拡張した道路データの一部として用意するほか、
道路データ（道路レイヤ）の一部として、予め、ＣＤ−
ＲＯＭに記憶しておくようにしてもよい。更に、目的地
交差点を起点にして出発地交差点に向けて経路探索を進
めても同様に最適な誘導経路を求めることができる。
的地の交差点ネットリストに記憶された累計距離に対
し、累計距離の短い経路が存在する間は経路探索を継続
し、若し、他の経路でも目的地に到達したとき、該経路
での累計距離の方が、既に目的地の交差点ネットリスト
に記憶されている累計距離より短ければ、書き換えを行
い、その後、どの経路も目的地の交差点ネットリストに
登録された累計距離より長くなったとき、経路探索を終
えるようにしてもよい。また、交差点ネットリストＣＲ
ＮＬは、以上のようにＣＤ−ＲＯＭに記憶された、交差
点ネットリストを含まない道路データから車載ナビゲー
タ内で作成し、道路リスト、交差点ネットリスト等と合
わせて拡張した道路データの一部として用意するほか、
道路データ（道路レイヤ）の一部として、予め、ＣＤ−
ＲＯＭに記憶しておくようにしてもよい。更に、目的地
交差点を起点にして出発地交差点に向けて経路探索を進
めても同様に最適な誘導経路を求めることができる。
【００１２】このように横型探索法によれば、グラフ理
論的に最短距離を指標にした最適経路が求まる。よっ
て、画面の地図画像中に、車両位置マークとともに、最
適な誘導経路を特定の強調色で表示することで、運転者
に対し、所望の目的地に向けた経路誘導を行うことがで
きる。
論的に最短距離を指標にした最適経路が求まる。よっ
て、画面の地図画像中に、車両位置マークとともに、最
適な誘導経路を特定の強調色で表示することで、運転者
に対し、所望の目的地に向けた経路誘導を行うことがで
きる。
【００１３】なお、誘導経路の探索には上記した横型探
索法の他にダイクストラ法（dijkstra法）も良く利用さ
れる。ダイクストラ法でも交差点ネットリストを用いる
が、検索次数の登録は必要がない。図２４はダイクスト
ラ法の概略説明図である。ダイクストラ法においては、
交差点ネットリストＣＲＮＬを参照しながら、まず、出
発地交差点ＳＴＰに係る交差点ネットリストの累計距離
を零としたあと、出発地交差点ＳＴＰを最初の探索枝先
端ノードＣＰtop とし、該ＣＰtop に隣接した交差点の
内の１つ、Ａ1 までの出発地交差点ＳＴＰからの累計距
離Ａｄ1 を求め、交差点Ａ1 に係る交差点ネットリスト
中に、１つ手前の交差点（現在のＣＰtop ）を特定する
交差点シーケンシャル番号とともに登録する（交差点ネ
ットリストの（１３）と（１４））。次いで、探索枝先
端バッファに今回の隣接交差点Ａ1 を特定する交差点シ
ーケンシャル番号を登録する。ＣＰtop に隣接する他の
交差点Ａ2 〜Ａ4 についても同様にして、出発地交差点
ＳＴＰからの累計距離Ａｄ1 〜Ａｄ4 を求め、各交差点
の交差点ネットリスト中に、１つ手前の交差点を特定す
る交差点シーケンシャル番号とともに登録し、探索枝先
端バッファに交差点シーケンシャル番号を追加登録する
（図２４（１）参照）。
索法の他にダイクストラ法（dijkstra法）も良く利用さ
れる。ダイクストラ法でも交差点ネットリストを用いる
が、検索次数の登録は必要がない。図２４はダイクスト
ラ法の概略説明図である。ダイクストラ法においては、
交差点ネットリストＣＲＮＬを参照しながら、まず、出
発地交差点ＳＴＰに係る交差点ネットリストの累計距離
を零としたあと、出発地交差点ＳＴＰを最初の探索枝先
端ノードＣＰtop とし、該ＣＰtop に隣接した交差点の
内の１つ、Ａ1 までの出発地交差点ＳＴＰからの累計距
離Ａｄ1 を求め、交差点Ａ1 に係る交差点ネットリスト
中に、１つ手前の交差点（現在のＣＰtop ）を特定する
交差点シーケンシャル番号とともに登録する（交差点ネ
ットリストの（１３）と（１４））。次いで、探索枝先
端バッファに今回の隣接交差点Ａ1 を特定する交差点シ
ーケンシャル番号を登録する。ＣＰtop に隣接する他の
交差点Ａ2 〜Ａ4 についても同様にして、出発地交差点
ＳＴＰからの累計距離Ａｄ1 〜Ａｄ4 を求め、各交差点
の交差点ネットリスト中に、１つ手前の交差点を特定す
る交差点シーケンシャル番号とともに登録し、探索枝先
端バッファに交差点シーケンシャル番号を追加登録する
（図２４（１）参照）。
【００１４】次に、探索枝先端バッファに登録された交
差点の中で、それまてにＣＰtop とされたものを除い
て、累計距離が最小となっているものを探し、これを新
たなＣＰtop とする。探索枝先端バッファには、Ａ1 〜
Ａ4 が登録されているが、Ａｄ 1 〜Ａｄ4 の中で、Ａｄ
1 が最小であったならば、ＣＰtop ＝Ａ1 となる（図２
４（２）実線参照）。この場合、Ａ1 に隣接した隣接交
差点の内の１つ、Ｂ11までのＡ1 を経由した出発地ＳＴ
Ｐからの累計距離Ｂｄ11を求める。ＳＴＰ−Ａ1間の累
計距離は既に交差点Ａ1 の交差点ネットリストに累計距
離Ａｄ1 として登録されており、Ａ1 −Ｂ11間の距離は
Ａ1 の交差点ネットリストに当該交差点Ａ 1 から隣接交
差点Ｂ11までの距離として登録されているので、これら
の和として累計距離Ｂｄ11が求まる。そして、隣接交差
点Ｂ11の交差点ネットリストに、ＣＰtop ＝Ａ1 を特定
する交差点シーケンシャル番号とともに登録し、探索枝
先端バッファにＢ11を特定する交差点シーケンシャル番
号を追加登録する。Ａ1 に隣接する他の交差点Ｂ12，Ｂ
14についても同様に、各交差点の交差点ネットリスト
に、累計距離とＡ1 の交差点シーケンシャル番号を登録
し、かつ、探索枝先端バッファにＢ12，Ｂ14の交差点シ
ーケンシャル番号を登録する。なお、Ａ1 に隣接する交
差点Ｂ13については、出発地交差点ＳＴＰと同一であ
り、該出発地交差点ＳＴＰの交差点ネットリストには既
に累計距離＝零が登録されており、かつ、ＳＴＰ−Ａ1
間の距離の２倍である累計距離Ｂｄ13より必ず小さいこ
とから、Ｂ13について交差点ネットリストへの累計距
離、交差点シーケンシャル番号の登録はせず、また、探
索枝先端バッファへの登録もしない。
差点の中で、それまてにＣＰtop とされたものを除い
て、累計距離が最小となっているものを探し、これを新
たなＣＰtop とする。探索枝先端バッファには、Ａ1 〜
Ａ4 が登録されているが、Ａｄ 1 〜Ａｄ4 の中で、Ａｄ
1 が最小であったならば、ＣＰtop ＝Ａ1 となる（図２
４（２）実線参照）。この場合、Ａ1 に隣接した隣接交
差点の内の１つ、Ｂ11までのＡ1 を経由した出発地ＳＴ
Ｐからの累計距離Ｂｄ11を求める。ＳＴＰ−Ａ1間の累
計距離は既に交差点Ａ1 の交差点ネットリストに累計距
離Ａｄ1 として登録されており、Ａ1 −Ｂ11間の距離は
Ａ1 の交差点ネットリストに当該交差点Ａ 1 から隣接交
差点Ｂ11までの距離として登録されているので、これら
の和として累計距離Ｂｄ11が求まる。そして、隣接交差
点Ｂ11の交差点ネットリストに、ＣＰtop ＝Ａ1 を特定
する交差点シーケンシャル番号とともに登録し、探索枝
先端バッファにＢ11を特定する交差点シーケンシャル番
号を追加登録する。Ａ1 に隣接する他の交差点Ｂ12，Ｂ
14についても同様に、各交差点の交差点ネットリスト
に、累計距離とＡ1 の交差点シーケンシャル番号を登録
し、かつ、探索枝先端バッファにＢ12，Ｂ14の交差点シ
ーケンシャル番号を登録する。なお、Ａ1 に隣接する交
差点Ｂ13については、出発地交差点ＳＴＰと同一であ
り、該出発地交差点ＳＴＰの交差点ネットリストには既
に累計距離＝零が登録されており、かつ、ＳＴＰ−Ａ1
間の距離の２倍である累計距離Ｂｄ13より必ず小さいこ
とから、Ｂ13について交差点ネットリストへの累計距
離、交差点シーケンシャル番号の登録はせず、また、探
索枝先端バッファへの登録もしない。
【００１５】このようにして、今回のＣＰtop について
処理し終えたならば、探索枝先端バッファに登録された
交差点の中で、それまでにＣＰtop とされたものを除い
て、累計距離が最小となっているものを探し、これを新
たなＣＰtop とする。探索枝先端バッファには、Ａ1 〜
Ａ4 、Ｂ11、Ｂ12、Ｂ14が登録されているが、Ａ1 は除
外される。よって、Ａｄ2 〜Ａｄ4 、Ｂｄ11、Ｂｄ12、
Ｂｄ14の中で、Ａｄ2が最小であったならば、ＣＰtop
＝Ａ2 となる（図２４（２）破線参照）。この場合、Ａ
2 に隣接した隣接交差点の内の１つ、Ｂ22までのＡ2 を
経由した出発地交差点ＳＴＰからの累計距離Ｂｄ22を求
める。そして、隣接交差点Ｂ22の交差点ネットリスト
に、ＣＰtop ＝Ａ2 の交差点シーケンシャル番号ととも
に登録し、探索枝先端バッファにＢ22の交差点シーケン
シャル番号を登録する。Ａ2 に隣接する他の交差点Ｂ23
についても同様にして交差点ネットリストに、Ａ2 を経
由した出発地交差点ＳＴＰからの累計距離とＡ2 の交差
点シーケンシャル番号を登録し、かつ、探索枝先端バッ
ファにＢ23の交差点シーケンシャル番号を登録する。
処理し終えたならば、探索枝先端バッファに登録された
交差点の中で、それまでにＣＰtop とされたものを除い
て、累計距離が最小となっているものを探し、これを新
たなＣＰtop とする。探索枝先端バッファには、Ａ1 〜
Ａ4 、Ｂ11、Ｂ12、Ｂ14が登録されているが、Ａ1 は除
外される。よって、Ａｄ2 〜Ａｄ4 、Ｂｄ11、Ｂｄ12、
Ｂｄ14の中で、Ａｄ2が最小であったならば、ＣＰtop
＝Ａ2 となる（図２４（２）破線参照）。この場合、Ａ
2 に隣接した隣接交差点の内の１つ、Ｂ22までのＡ2 を
経由した出発地交差点ＳＴＰからの累計距離Ｂｄ22を求
める。そして、隣接交差点Ｂ22の交差点ネットリスト
に、ＣＰtop ＝Ａ2 の交差点シーケンシャル番号ととも
に登録し、探索枝先端バッファにＢ22の交差点シーケン
シャル番号を登録する。Ａ2 に隣接する他の交差点Ｂ23
についても同様にして交差点ネットリストに、Ａ2 を経
由した出発地交差点ＳＴＰからの累計距離とＡ2 の交差
点シーケンシャル番号を登録し、かつ、探索枝先端バッ
ファにＢ23の交差点シーケンシャル番号を登録する。
【００１６】なお、交差点Ｂ24については、出発地交差
点ＳＴＰと同一であり、該出発地交差点ＳＴＰの交差点
ネットリストには既に累計距離＝零が登録されており、
かつ、ＳＴＰ−Ａ2 間の距離の２倍である累計距離Ｂｄ
24より必ず小さいことから、Ｂ24について交差点ネット
リストへの累計距離、交差点シーケンシャル番号の登録
はせず、また、探索枝先端バッファへの登録もしない。
また、隣接交差点Ｂ21についても、隣接交差点Ｂ12と同
一であるので、ＳＴＰ−Ａ2 −Ｂ21の累計距離Ｂｄ21を
登録しようとするとき、Ｂ12の交差点ネットリストには
既に累計距離Ｂｄ12が登録されている。この場合、Ｂｄ
21をＢｄ12と大小比較し、Ｂｄ21の方が小さい場合の
み、Ｂ12（＝Ｂ21）の交差点ネットリストに累計距離Ｂ
ｄ21とＢ21の交差点シーケンシャル番号を書き換え登録
し、探索枝先端バッファにＢ21の交差点シーケンシャル
番号を追加登録する。若し、Ｂｄ21の方が大きい場合
は、Ｂｄ21とＢ21の交差点シーケンシャル番号の書き換
え登録はせず、探索枝先端バッファへのＢ21の追加登録
もしない。
点ＳＴＰと同一であり、該出発地交差点ＳＴＰの交差点
ネットリストには既に累計距離＝零が登録されており、
かつ、ＳＴＰ−Ａ2 間の距離の２倍である累計距離Ｂｄ
24より必ず小さいことから、Ｂ24について交差点ネット
リストへの累計距離、交差点シーケンシャル番号の登録
はせず、また、探索枝先端バッファへの登録もしない。
また、隣接交差点Ｂ21についても、隣接交差点Ｂ12と同
一であるので、ＳＴＰ−Ａ2 −Ｂ21の累計距離Ｂｄ21を
登録しようとするとき、Ｂ12の交差点ネットリストには
既に累計距離Ｂｄ12が登録されている。この場合、Ｂｄ
21をＢｄ12と大小比較し、Ｂｄ21の方が小さい場合の
み、Ｂ12（＝Ｂ21）の交差点ネットリストに累計距離Ｂ
ｄ21とＢ21の交差点シーケンシャル番号を書き換え登録
し、探索枝先端バッファにＢ21の交差点シーケンシャル
番号を追加登録する。若し、Ｂｄ21の方が大きい場合
は、Ｂｄ21とＢ21の交差点シーケンシャル番号の書き換
え登録はせず、探索枝先端バッファへのＢ21の追加登録
もしない。
【００１７】以下、同様の処理を繰り返していき、或る
ＣＰtop の隣接交差点につき、累計距離とＣＰtop の交
差点シーケンシャル番号の登録及び、探索枝先端バッフ
ァへの隣接交差点の交差点シーケンシャル番号の追加登
録が終わったところで、当該隣接交差点が目的地交差点
ＤＳＰと一致したならば、探索を終える。ＣＰtop は、
常に、累計距離の最小距離のものが選択されているの
で、目的地交差点ＤＳＰ（ｍ次の交差点とする）、目的
地交差点の交差点ネットリストに累計距離とともに記憶
してある（ｍ−１）次の交差点、該（ｍ−１）次の交差
点の交差点ネットリストに記憶してある（ｍ−２）次の
交差点、・・・、２次の交差点の交差点ネットリストに
記憶してある１次交差点、該１次交差点の交差点ネット
リストに記憶してある０次の交差点（出発地交差点ＳＴ
Ｐ）を、順次、０次の交差点側から目的地側に向けた順
序で結んでなる経路が最短の最適経路となる。このよう
にダイクストラ法によれば、前述した横型探索法より的
確に最短の経路を探索することができる。但し、探索速
度は、横型探索法より遅い。
ＣＰtop の隣接交差点につき、累計距離とＣＰtop の交
差点シーケンシャル番号の登録及び、探索枝先端バッフ
ァへの隣接交差点の交差点シーケンシャル番号の追加登
録が終わったところで、当該隣接交差点が目的地交差点
ＤＳＰと一致したならば、探索を終える。ＣＰtop は、
常に、累計距離の最小距離のものが選択されているの
で、目的地交差点ＤＳＰ（ｍ次の交差点とする）、目的
地交差点の交差点ネットリストに累計距離とともに記憶
してある（ｍ−１）次の交差点、該（ｍ−１）次の交差
点の交差点ネットリストに記憶してある（ｍ−２）次の
交差点、・・・、２次の交差点の交差点ネットリストに
記憶してある１次交差点、該１次交差点の交差点ネット
リストに記憶してある０次の交差点（出発地交差点ＳＴ
Ｐ）を、順次、０次の交差点側から目的地側に向けた順
序で結んでなる経路が最短の最適経路となる。このよう
にダイクストラ法によれば、前述した横型探索法より的
確に最短の経路を探索することができる。但し、探索速
度は、横型探索法より遅い。
【００１８】
【発明が解決しようとする課題】ところで、上記した横
型探索法、ダイクストラ法のいずれにおいても、経路探
索範囲を出発地と目的地を結ぶ直線を対角線とする方形
領域内に限ったとしても、該領域内に含まれる全ての経
路をしらみつぶしに探索するため、探索が完了するまで
かなりの時間を要し、運転者が経路誘導を受けて走行を
開始できるようになるまで、長く又されることになる。
この問題を解決するため、ヒューリスティック探索法
（heuristic −発見的探索法）が提案されている。この
探索法は、経験的に最適経路が出発地と目的地を結ぶ直
線から或る範囲内となる場合が殆どなので、出発地から
目的地に向けた方向から外れる経路は枝刈りしたり、距
離に重付けをして優先度を下げるなどして不要な経路を
探索しないようにしたものである。
型探索法、ダイクストラ法のいずれにおいても、経路探
索範囲を出発地と目的地を結ぶ直線を対角線とする方形
領域内に限ったとしても、該領域内に含まれる全ての経
路をしらみつぶしに探索するため、探索が完了するまで
かなりの時間を要し、運転者が経路誘導を受けて走行を
開始できるようになるまで、長く又されることになる。
この問題を解決するため、ヒューリスティック探索法
（heuristic −発見的探索法）が提案されている。この
探索法は、経験的に最適経路が出発地と目的地を結ぶ直
線から或る範囲内となる場合が殆どなので、出発地から
目的地に向けた方向から外れる経路は枝刈りしたり、距
離に重付けをして優先度を下げるなどして不要な経路を
探索しないようにしたものである。
【００１９】しかしながら、経路の探索対象が郊外の場
合、道路の密度が低く、しかも、回り込んだ道路しか存
在しない場合も多く、例えば、図２５に示す如く、目的
地近くのＣＰX まで探索が進んだあと、出発地から目的
地ＤＳＰに向けた方向から一旦外れる経路Ａを取らない
と目的地ＤＳＰに到達できないようになっていることが
あり、かかるとき、ヒューリスティック探索では経路Ａ
が枝刈りされてしまって目的地ＤＳＰに至る最適経路の
探索が不可能となってしまったり、経路Ａの優先度が下
がって経路探索に長時間かかってしまう問題があった。
以上から本発明の目的は、探索対象範囲の道路状況に応
じて常に的確な最適経路の探索を行えるようにした経路
探索方法を提供することにある。
合、道路の密度が低く、しかも、回り込んだ道路しか存
在しない場合も多く、例えば、図２５に示す如く、目的
地近くのＣＰX まで探索が進んだあと、出発地から目的
地ＤＳＰに向けた方向から一旦外れる経路Ａを取らない
と目的地ＤＳＰに到達できないようになっていることが
あり、かかるとき、ヒューリスティック探索では経路Ａ
が枝刈りされてしまって目的地ＤＳＰに至る最適経路の
探索が不可能となってしまったり、経路Ａの優先度が下
がって経路探索に長時間かかってしまう問題があった。
以上から本発明の目的は、探索対象範囲の道路状況に応
じて常に的確な最適経路の探索を行えるようにした経路
探索方法を提供することにある。
【００２０】
【課題を解決するための手段】上記課題は、本発明にお
いては、道路データから探索対象範囲が都市部に存在す
るか郊外に存在するか判別する手段と、都市部に存在す
るときは、出発地と目的地を結ぶ直線の方向から外れる
経路を枝刈りしたり優先度を下げるなどしてヒューリス
ティック探索する手段と、郊外に存在するときは、ヒュ
ーリスティックでない通常の探索をする手段とを設けた
ことにより達成される。
いては、道路データから探索対象範囲が都市部に存在す
るか郊外に存在するか判別する手段と、都市部に存在す
るときは、出発地と目的地を結ぶ直線の方向から外れる
経路を枝刈りしたり優先度を下げるなどしてヒューリス
ティック探索する手段と、郊外に存在するときは、ヒュ
ーリスティックでない通常の探索をする手段とを設けた
ことにより達成される。
【００２１】
【作用】本発明によれば、道路データから探索対象範囲
が都市部に存在するか郊外に存在するか判別し、都市部
に存在するときは、出発地と目的地を結ぶ直線の方向か
ら外れる経路を枝刈りしたり優先度を下げるなどしてヒ
ューリスティック探索し、郊外に存在するときは、ヒュ
ーリスティックでない通常の探索をする。これにより、
探索対象範囲が道路密度の高い都市部であれば、ヒュー
リスティック探索によって短時間に最適経路の探索を行
え、また、探索対象範囲が道路密度の低い郊外であって
も確実に最適経路の探索を行えるので、探索不能という
事態が生じたり、経路探索に長時間掛かったりしない。
が都市部に存在するか郊外に存在するか判別し、都市部
に存在するときは、出発地と目的地を結ぶ直線の方向か
ら外れる経路を枝刈りしたり優先度を下げるなどしてヒ
ューリスティック探索し、郊外に存在するときは、ヒュ
ーリスティックでない通常の探索をする。これにより、
探索対象範囲が道路密度の高い都市部であれば、ヒュー
リスティック探索によって短時間に最適経路の探索を行
え、また、探索対象範囲が道路密度の低い郊外であって
も確実に最適経路の探索を行えるので、探索不能という
事態が生じたり、経路探索に長時間掛かったりしない。
【００２２】
【実施例】全体の構成 図１は本発明の経路探索方法を具現した車載ナビゲータ
の全体構成図である。図中、１１は地図データを記憶す
るＣＤ−ＲＯＭ（地図情報記憶部）である。地図データ
は、道路レイヤ、背景レイヤ、文字レイヤなどから構成
されている。１２は車両の現在位置に応じた地図画像や
車両位置マーク、最適経路探索で探索された誘導経路等
を描画するディスプレイ装置（ＣＲＴ）、１３は走行中
の車両の走行距離と方位に基づいて車両の現在位置を算
出する車両位置検出部である。車両位置検出部１３は、
図示しないが、車両の進行方位を検出する方位センサや
走行距離を検出する距離センサ、方位や走行距離に基づ
いて車両の現在位置（経度、緯度）を算出する位置計算
用ＣＰＵを有している。１４は地図検索キー、拡大・縮
小キー、地図スクロールキー、経路誘導モードキー等を
備えた操作部、１５は地図表示制御装置であり、地図デ
ータに基づき車両の現在地周辺の地図画像を発生すると
ともに、車両位置マークや誘導経路画像を発生する。
の全体構成図である。図中、１１は地図データを記憶す
るＣＤ−ＲＯＭ（地図情報記憶部）である。地図データ
は、道路レイヤ、背景レイヤ、文字レイヤなどから構成
されている。１２は車両の現在位置に応じた地図画像や
車両位置マーク、最適経路探索で探索された誘導経路等
を描画するディスプレイ装置（ＣＲＴ）、１３は走行中
の車両の走行距離と方位に基づいて車両の現在位置を算
出する車両位置検出部である。車両位置検出部１３は、
図示しないが、車両の進行方位を検出する方位センサや
走行距離を検出する距離センサ、方位や走行距離に基づ
いて車両の現在位置（経度、緯度）を算出する位置計算
用ＣＰＵを有している。１４は地図検索キー、拡大・縮
小キー、地図スクロールキー、経路誘導モードキー等を
備えた操作部、１５は地図表示制御装置であり、地図デ
ータに基づき車両の現在地周辺の地図画像を発生すると
ともに、車両位置マークや誘導経路画像を発生する。
【００２３】地図表示制御装置１５において、１５ａは
車両位置データに基づき、現在地周辺で画面表示範囲よ
り広い範囲の地図データ（例えば９画面分の地図デー
タ）をＣＤ−ＲＯＭ１１から読み出し、一旦、バッファ
メモリに格納させるとともに、該地図データに基づいて
ドットイメージの地図画像を発生する地図画像描画部で
ある。１５ｂはＣＤ−ＲＯＭ１１から読み出された地図
データを一時記憶するバッファメモリ、１５ｃは最適経
路探索処理により得られた誘導経路データに基づいて誘
導経路画像を発生する誘導経路描画部、１５ｄは地図画
像及び誘導経路画像を記憶するビデオＲＡＭである。地
図画像描画部１５ａはディスプレイ画面の表示範囲がビ
デオＲＡＭ１５ｄの画像範囲を越えないように、車両の
走行に従って、随時、ビデオＲＡＭ１５ｄを書き換え、
また誘導経路描画部１５ｃも車両の走行に応じて誘導経
路画像を発生してビデオＲＡＭ１５ｄに記憶させるよう
になっている。１５ｅは車両の現在位置がディスプレイ
画面の中心に位置するようにビデオＲＡＭ１５ｄから１
画面分の地図画像を読み出す読み出し制御部であり、読
み出し位置は地図画像描画部１５ａから指示される。１
５ｆはディスプレイ画面の中心に車両位置マークを表示
するための車両位置マーク発生部であり、車両位置検出
部１３から車両方位データを入力して、該データの示す
方向に向けた車両位置マークを発生する。
車両位置データに基づき、現在地周辺で画面表示範囲よ
り広い範囲の地図データ（例えば９画面分の地図デー
タ）をＣＤ−ＲＯＭ１１から読み出し、一旦、バッファ
メモリに格納させるとともに、該地図データに基づいて
ドットイメージの地図画像を発生する地図画像描画部で
ある。１５ｂはＣＤ−ＲＯＭ１１から読み出された地図
データを一時記憶するバッファメモリ、１５ｃは最適経
路探索処理により得られた誘導経路データに基づいて誘
導経路画像を発生する誘導経路描画部、１５ｄは地図画
像及び誘導経路画像を記憶するビデオＲＡＭである。地
図画像描画部１５ａはディスプレイ画面の表示範囲がビ
デオＲＡＭ１５ｄの画像範囲を越えないように、車両の
走行に従って、随時、ビデオＲＡＭ１５ｄを書き換え、
また誘導経路描画部１５ｃも車両の走行に応じて誘導経
路画像を発生してビデオＲＡＭ１５ｄに記憶させるよう
になっている。１５ｅは車両の現在位置がディスプレイ
画面の中心に位置するようにビデオＲＡＭ１５ｄから１
画面分の地図画像を読み出す読み出し制御部であり、読
み出し位置は地図画像描画部１５ａから指示される。１
５ｆはディスプレイ画面の中心に車両位置マークを表示
するための車両位置マーク発生部であり、車両位置検出
部１３から車両方位データを入力して、該データの示す
方向に向けた車両位置マークを発生する。
【００２４】１５ｇは最適経路探索部であり、経路誘導
モードに設定後、目的地が入力されると、その時点の自
車位置（出発地）と目的地の位置関係から、出発地と目
的地を結ぶ直線を対角線とする方形領域を含む１枚又は
互いに隣接する複数枚の４分割図葉の地図データをＣＤ
−ＲＯＭ１１からバッファメモリ１５ｂに読み出しなが
ら交差点ネットリストを作成して経路探索メモリに記憶
させたのち、横型探索法により出発地から目的地までを
結ぶ最適経路（最短経路）を探索する。最適経路探索部
１５ｇは、経路探索の対象範囲が都市部のときはヒュー
リスティック探索を行い、郊外のときは通常の探索を行
う。１５ｈは経路探索開始前に経路探索対象範囲が都市
部か郊外かを判別して、判別結果を最適経路探索部へ通
知する地域判別部である。一般に、都市部と郊外では交
差点密度に差があり、都市部では密度が大きく、郊外で
は小さい。地域判別部１５ｈはこれを利用して都市部か
郊外かを判別するものとする。具体的には、例えば、交
差点ネットリストを作成し終わった時点で、交差点ネッ
トリストの全数である全交差点数を交差点ネットリスト
の作成対象エリアの大きさで割って交差点密度（単位面
積当たりの交差点数）を計算し、一定の基準値、ここで
は一例として1000個／100km 2 と比較して、基準値より
大きいときは都市部、基準値より小さいときは郊外とす
る。
モードに設定後、目的地が入力されると、その時点の自
車位置（出発地）と目的地の位置関係から、出発地と目
的地を結ぶ直線を対角線とする方形領域を含む１枚又は
互いに隣接する複数枚の４分割図葉の地図データをＣＤ
−ＲＯＭ１１からバッファメモリ１５ｂに読み出しなが
ら交差点ネットリストを作成して経路探索メモリに記憶
させたのち、横型探索法により出発地から目的地までを
結ぶ最適経路（最短経路）を探索する。最適経路探索部
１５ｇは、経路探索の対象範囲が都市部のときはヒュー
リスティック探索を行い、郊外のときは通常の探索を行
う。１５ｈは経路探索開始前に経路探索対象範囲が都市
部か郊外かを判別して、判別結果を最適経路探索部へ通
知する地域判別部である。一般に、都市部と郊外では交
差点密度に差があり、都市部では密度が大きく、郊外で
は小さい。地域判別部１５ｈはこれを利用して都市部か
郊外かを判別するものとする。具体的には、例えば、交
差点ネットリストを作成し終わった時点で、交差点ネッ
トリストの全数である全交差点数を交差点ネットリスト
の作成対象エリアの大きさで割って交差点密度（単位面
積当たりの交差点数）を計算し、一定の基準値、ここで
は一例として1000個／100km 2 と比較して、基準値より
大きいときは都市部、基準値より小さいときは郊外とす
る。
【００２５】なお、バッファメモリ１５ｂに読み出され
た各４分割図葉に係る道路データ中のノードテーブルＮ
ＤＴＢの中から、交差点識別フラグの立っているノード
の数を全て数えたり、または、交差点構成ノードリスト
ＣＲＬＴで定義された交差点数を数えたりすることで、
経路探索対象範囲に含まれる交差点数を求めたり、更
に、経路探索メモリ１５ｉに作成された交差点ネットリ
ストの占める容量で凡その交差点数を推定したり、各４
分割図葉に係る道路データ中の交差点構成ノードリスト
ＣＲＬＴの大きさの合計等から凡その交差点数を推定し
てもよい。また、地図データ中に各４分割図葉単位また
は図葉単位で、予め、都市部か郊外かを示すデータを含
めておき、該データを参照して、経路探索対象範囲が都
市部か郊外かを判別するようにしてもよい。
た各４分割図葉に係る道路データ中のノードテーブルＮ
ＤＴＢの中から、交差点識別フラグの立っているノード
の数を全て数えたり、または、交差点構成ノードリスト
ＣＲＬＴで定義された交差点数を数えたりすることで、
経路探索対象範囲に含まれる交差点数を求めたり、更
に、経路探索メモリ１５ｉに作成された交差点ネットリ
ストの占める容量で凡その交差点数を推定したり、各４
分割図葉に係る道路データ中の交差点構成ノードリスト
ＣＲＬＴの大きさの合計等から凡その交差点数を推定し
てもよい。また、地図データ中に各４分割図葉単位また
は図葉単位で、予め、都市部か郊外かを示すデータを含
めておき、該データを参照して、経路探索対象範囲が都
市部か郊外かを判別するようにしてもよい。
【００２６】１５ｉは最適経路探索部と接続されて交差
点ネットリスト等の道路データが記憶される経路探索メ
モリ、１５ｊは最適経路を構成するノード列を誘導経路
データとして記憶する誘導経路記憶部である。なお、経
路探索メモリ１５ｉ、誘導経路記憶部１５ｊは、車載ナ
ビゲータの電源がオフされてもバックアップ電源の供給
でデータが保持されるようになっている。１５ｋは合成
部であり、ビデオＲＡＭ１５ｄ、車両位置マーク発生部
１５ｆからそれぞれ読み出された地図画像及び誘導経路
画像、車両位置マーク画像を合成してディスプレイ装置
１２に出力し、画像表示させる。
点ネットリスト等の道路データが記憶される経路探索メ
モリ、１５ｊは最適経路を構成するノード列を誘導経路
データとして記憶する誘導経路記憶部である。なお、経
路探索メモリ１５ｉ、誘導経路記憶部１５ｊは、車載ナ
ビゲータの電源がオフされてもバックアップ電源の供給
でデータが保持されるようになっている。１５ｋは合成
部であり、ビデオＲＡＭ１５ｄ、車両位置マーク発生部
１５ｆからそれぞれ読み出された地図画像及び誘導経路
画像、車両位置マーク画像を合成してディスプレイ装置
１２に出力し、画像表示させる。
【００２７】地図データ ＣＤ−ＲＯＭ１１に記憶されている地図は適当な大きさ
の経度幅、緯度幅の図葉に区切られている。各図葉の地
図データは、１画面分に相当する４つのデータユニット
毎（４分割図葉毎）に分割されており（図１９参照）、
地図データでは、道路等は経緯度で表現された頂点（ノ
ード）の座標集合で示され、これらの描画は各ノードを
順に直線で接続することにより行われる。なお、道路は
２以上のノードの連結からなり、２つのノードを連結し
た部分はリンクと呼ばれる。地図データには、（１）道
路リスト、ノードテーブル、交差点構成ノードリスト、
隣接交差点リストなどからなる道路レイヤ、（２）地図
画面上の道路、建物、河川等を表示するための背景レイ
ヤ、（３）市町村名、道路名等を表示するための文字レ
イヤなどから構成されている。この内、道路レイヤは、
図２０と全く同様のデータ構造を有しており、道路リス
トＲＤＬＴ、交差点構成ノードリストＣＲＬＴ、ノード
テーブルＮＤＴＢ、隣接ノードリストＮＮＬＴなどが含
まれている。
の経度幅、緯度幅の図葉に区切られている。各図葉の地
図データは、１画面分に相当する４つのデータユニット
毎（４分割図葉毎）に分割されており（図１９参照）、
地図データでは、道路等は経緯度で表現された頂点（ノ
ード）の座標集合で示され、これらの描画は各ノードを
順に直線で接続することにより行われる。なお、道路は
２以上のノードの連結からなり、２つのノードを連結し
た部分はリンクと呼ばれる。地図データには、（１）道
路リスト、ノードテーブル、交差点構成ノードリスト、
隣接交差点リストなどからなる道路レイヤ、（２）地図
画面上の道路、建物、河川等を表示するための背景レイ
ヤ、（３）市町村名、道路名等を表示するための文字レ
イヤなどから構成されている。この内、道路レイヤは、
図２０と全く同様のデータ構造を有しており、道路リス
トＲＤＬＴ、交差点構成ノードリストＣＲＬＴ、ノード
テーブルＮＤＴＢ、隣接ノードリストＮＮＬＴなどが含
まれている。
【００２８】交差点ネットリスト 最適経路探索部１５ｇが作成する交差点ネットリストＣ
ＲＮＬは、図２に示す如く構成されるようになってお
り、本来の交差点（交差点ノード（隣接ノードであるか
否かを問わない））のほか、単純ノードの内、隣接ノー
ドとなっているものを含めて交差点毎に、 （１）交差点シーケンシャル番号（当該交差点を特定す
る情報） （２）該交差点が含まれる地図の図葉番号 （３）データユニットコード （４）ノードテーブル上の位置 （５）経度 （６）緯度 以上、交差点ＩＤ （７）交差点構成ノードリスト上の位置 （８）交差点構成ノード数 （９）隣接ノードリスト上の位置 （１０）隣接ノード数 （１１）各隣接交差点のシーケンシャル番号 （１２）当該交差点から各隣接交差点までの距離 （１３）当該交差点の１つ手前の交差点シーケンシャル
番号 （１４）出発地から当該交差点までの累計距離 （１５）当該交差点の検索次数 等が登録されるようになっている（但し、（１３）〜
（１５）は経路探索実行時に登録される）。
ＲＮＬは、図２に示す如く構成されるようになってお
り、本来の交差点（交差点ノード（隣接ノードであるか
否かを問わない））のほか、単純ノードの内、隣接ノー
ドとなっているものを含めて交差点毎に、 （１）交差点シーケンシャル番号（当該交差点を特定す
る情報） （２）該交差点が含まれる地図の図葉番号 （３）データユニットコード （４）ノードテーブル上の位置 （５）経度 （６）緯度 以上、交差点ＩＤ （７）交差点構成ノードリスト上の位置 （８）交差点構成ノード数 （９）隣接ノードリスト上の位置 （１０）隣接ノード数 （１１）各隣接交差点のシーケンシャル番号 （１２）当該交差点から各隣接交差点までの距離 （１３）当該交差点の１つ手前の交差点シーケンシャル
番号 （１４）出発地から当該交差点までの累計距離 （１５）当該交差点の検索次数 等が登録されるようになっている（但し、（１３）〜
（１５）は経路探索実行時に登録される）。
【００２９】図３〜図８は、地図表示制御装置１５の処
理を示す流れ図、図９は交差点ネットリストの作成対象
図葉の説明図、図１０は横型探索法による経路探索の説
明図、図１１は枝刈りの説明図であり、以下、これらの
図に従って説明する。
理を示す流れ図、図９は交差点ネットリストの作成対象
図葉の説明図、図１０は横型探索法による経路探索の説
明図、図１１は枝刈りの説明図であり、以下、これらの
図に従って説明する。
【００３０】電源オンによる前回電源オフ直前状態の再
現 車載ナビゲータの電源が投入されると、地図表示制御装
置１５は前回、電源オフ直前の地図画像表示状態を再現
する（図３のステップ１０１）。ここでは、通常案内モ
ードが再現されるものとすると、地図画像描画部１５ａ
は、先ず、ＣＤ−ＲＯＭ１１から図葉管理情報をバッフ
ァメモリ１５ｂに読み出すとともに、該図葉管理情報を
参照して、ＣＤ−ＲＯＭ１１から自車位置周辺の複数枚
の図葉に係る地図データをバッファメモリ１５ｂに読み
出し、自車位置を含む９画面分の領域の地図画像をビデ
オＲＡＭ１５ｄに描画するとともに、車両位置検出部１
３から入力した車両位置データに基づき、読み出し制御
部１５ｅをして、ビデオＲＡＭ１５ｄから車両位置を中
心とする１画面分の地図画像を切り出し、合成部１５ｋ
へ出力する。また、車両位置マーク発生部１５ｆも、車
両位置検出部１３で検出された車両方位データの示す向
きで所定の車両位置マークを発生して合成部１５ｋへ出
力する。合成部１５ｋは地図画像に車両位置マークを合
成し、ディスプレイ装置１２へ出力して、画面に表示さ
せる。これにより、画面には、自車位置周辺の地図画像
が車両位置マークとともに表示される。
現 車載ナビゲータの電源が投入されると、地図表示制御装
置１５は前回、電源オフ直前の地図画像表示状態を再現
する（図３のステップ１０１）。ここでは、通常案内モ
ードが再現されるものとすると、地図画像描画部１５ａ
は、先ず、ＣＤ−ＲＯＭ１１から図葉管理情報をバッフ
ァメモリ１５ｂに読み出すとともに、該図葉管理情報を
参照して、ＣＤ−ＲＯＭ１１から自車位置周辺の複数枚
の図葉に係る地図データをバッファメモリ１５ｂに読み
出し、自車位置を含む９画面分の領域の地図画像をビデ
オＲＡＭ１５ｄに描画するとともに、車両位置検出部１
３から入力した車両位置データに基づき、読み出し制御
部１５ｅをして、ビデオＲＡＭ１５ｄから車両位置を中
心とする１画面分の地図画像を切り出し、合成部１５ｋ
へ出力する。また、車両位置マーク発生部１５ｆも、車
両位置検出部１３で検出された車両方位データの示す向
きで所定の車両位置マークを発生して合成部１５ｋへ出
力する。合成部１５ｋは地図画像に車両位置マークを合
成し、ディスプレイ装置１２へ出力して、画面に表示さ
せる。これにより、画面には、自車位置周辺の地図画像
が車両位置マークとともに表示される。
【００３１】なお、前回、電源オフ時に、若し、経路誘
導モードであったならば、電源投入後、経路誘導モード
となり、ステップ１０１において、前述した地図画像描
画部１５ａの処理に加えて、誘導経路描画部１５ｃが車
両位置データに基づき、誘導経路記憶部１５ｊに記憶さ
れた誘導経路データの中から、ビデオＲＡＭ１５ｄに描
画されたエリアに入る部分を選び出し、ビデオＲＡＭ１
５ｄに誘導経路を所定色で太く強調させて描画する。こ
れにより、画面には、自車位置周辺の地図画像が車両位
置マーク、出発地から交差点を結ぶ最適な誘導経路とと
もに表示される。
導モードであったならば、電源投入後、経路誘導モード
となり、ステップ１０１において、前述した地図画像描
画部１５ａの処理に加えて、誘導経路描画部１５ｃが車
両位置データに基づき、誘導経路記憶部１５ｊに記憶さ
れた誘導経路データの中から、ビデオＲＡＭ１５ｄに描
画されたエリアに入る部分を選び出し、ビデオＲＡＭ１
５ｄに誘導経路を所定色で太く強調させて描画する。こ
れにより、画面には、自車位置周辺の地図画像が車両位
置マーク、出発地から交差点を結ぶ最適な誘導経路とと
もに表示される。
【００３２】経路探索の準備 電源オンで通常案内モードが再現されたものとして、運
転者が所望の目的地まで経路誘導モード下で走行したい
場合、操作部１４上の経路誘導モードキーを押圧して経
路誘導モードにする（図３のステップ１０４でＹＥＳ、
１０５）。次いで、地図検索キー等を操作し、地図画像
描画部１５ａにより目的地を含む地図画像をディスプレ
イ画面に表示させ、しかる後、地図スクロールキーを用
いて車両位置マークを目的地に位置決めし、目的地を設
定する（ステップ１０６）。
転者が所望の目的地まで経路誘導モード下で走行したい
場合、操作部１４上の経路誘導モードキーを押圧して経
路誘導モードにする（図３のステップ１０４でＹＥＳ、
１０５）。次いで、地図検索キー等を操作し、地図画像
描画部１５ａにより目的地を含む地図画像をディスプレ
イ画面に表示させ、しかる後、地図スクロールキーを用
いて車両位置マークを目的地に位置決めし、目的地を設
定する（ステップ１０６）。
【００３３】目的地が設定されると、最適経路探索部１
５ｇは、現在の自車位置を目的地として自動設定し（ス
テップ１０７）。出発地を含む図葉の地図データに基づ
き、出発地が道路データで定義された交差点（本来の交
差点ノード又は単純ノードの内の隣接ノード）であるか
調べ（ステップ１０８）、交差点であれば出発地交差点
ＳＴＰとし（ステップ１０９）、ステップ１１１以降の
処理を行い、交差点でなければ、道路データで定義され
た最寄りの交差点を出発地交差点ＳＴＰとし（ステップ
１１０）、ステップ１１１以降の処理を行う。出発地交
差点ＳＴＰが決まれば、最適経路探索部１５ｇは目的地
が道路データで定義された交差点（本来の交差点ノート
又は単純ノードの内の隣接ノード）であるか調べ（ステ
ップ１１１）、交差点であれば目的地交差点ＤＳＰとし
（ステップ１１２）、図４のステップ２０１以降の処理
を行い、交差点でなければ、最寄りの交差点を目的地交
差点ＤＳＰとし（ステップ１１３）、ステップ２０１以
降の処理を行う。
５ｇは、現在の自車位置を目的地として自動設定し（ス
テップ１０７）。出発地を含む図葉の地図データに基づ
き、出発地が道路データで定義された交差点（本来の交
差点ノード又は単純ノードの内の隣接ノード）であるか
調べ（ステップ１０８）、交差点であれば出発地交差点
ＳＴＰとし（ステップ１０９）、ステップ１１１以降の
処理を行い、交差点でなければ、道路データで定義され
た最寄りの交差点を出発地交差点ＳＴＰとし（ステップ
１１０）、ステップ１１１以降の処理を行う。出発地交
差点ＳＴＰが決まれば、最適経路探索部１５ｇは目的地
が道路データで定義された交差点（本来の交差点ノート
又は単純ノードの内の隣接ノード）であるか調べ（ステ
ップ１１１）、交差点であれば目的地交差点ＤＳＰとし
（ステップ１１２）、図４のステップ２０１以降の処理
を行い、交差点でなければ、最寄りの交差点を目的地交
差点ＤＳＰとし（ステップ１１３）、ステップ２０１以
降の処理を行う。
【００３４】出発地交差点ＳＴＰ及び目的地交差点ＤＳ
Ｐが決まれば、最適経路探索部１５ｇは、図葉管理情報
を参照して、出発地と目的地を結ぶ直線を対角線とする
方形領域を含む１又は複数の４分割図葉を求め、これら
の４分割図葉全てにつき、地図データをＣＤ−ＲＯＭ１
１からバッファメモリ１５ｂに読み出したのち（図４の
ステップ２０１）、各４分割図葉毎に、道路データか
ら、各交差点（本来の交差点ノードと、単純ノードの
内、隣接ノードとなっているものを含む）毎に、交差点
ネットリストを経路探索メモリ１５ｈに作成する（ステ
ップ２０２以降の処理）。
Ｐが決まれば、最適経路探索部１５ｇは、図葉管理情報
を参照して、出発地と目的地を結ぶ直線を対角線とする
方形領域を含む１又は複数の４分割図葉を求め、これら
の４分割図葉全てにつき、地図データをＣＤ−ＲＯＭ１
１からバッファメモリ１５ｂに読み出したのち（図４の
ステップ２０１）、各４分割図葉毎に、道路データか
ら、各交差点（本来の交差点ノードと、単純ノードの
内、隣接ノードとなっているものを含む）毎に、交差点
ネットリストを経路探索メモリ１５ｈに作成する（ステ
ップ２０２以降の処理）。
【００３５】交差点ネットリストの作成では、対象とな
る４分割図葉が例えば図９に示す如く、ＢＵ11〜ＢＵ33
から成る時、まず、４分割図葉の１つＢＵ11につき、デ
ータユニットのノードテーブルＮＤＴＢから交差点識別
フラグの立っている交差点ノードと、交差点識別フラグ
の落ちている単純ノードであるが隣接ノード識別フラグ
の立っている隣接ノードを探し、１から昇順する連続番
号で交差点シーケンシャル番号をふった各交差点ネット
リストを経路探索メモリ上に用意し、交差点ＩＤを登録
する（図２の（０）〜（５）。ステップ２０２、２０
３）。そして、ノードテーブルＮＤＴＢ、交差点構成ノ
ードリストＣＲＤＴ、隣接ノードリストＮＮＬＴから、
交差点構成ノードリスト上の位置、交差点構成ノード
数、隣接ノートリスト上の位置、隣接ノード数を得て、
図２の（６）〜（９）を登録する（ステップ２０４）。
次に、道路リストＲＤＬＴの各道路につき、ノードテー
ブルＮＤＴＢを参照して、相隣る交差点（一方が単純ノ
ードでの隣接ノードの場合を含む）相互間のリンクの距
離を求め、リンクの一方の交差点に係る交差点ネットリ
ストに、リンクの他方の交差点を隣接交差点とし、該隣
接交差点に係る交差点ネットリストに登録された交差点
シーケンシャル番号（隣接交差点シーケンシャル番
号）、当該リンクの距離を登録していく（図２の（１
０）〜（２４）。ステップ２０５）。
る４分割図葉が例えば図９に示す如く、ＢＵ11〜ＢＵ33
から成る時、まず、４分割図葉の１つＢＵ11につき、デ
ータユニットのノードテーブルＮＤＴＢから交差点識別
フラグの立っている交差点ノードと、交差点識別フラグ
の落ちている単純ノードであるが隣接ノード識別フラグ
の立っている隣接ノードを探し、１から昇順する連続番
号で交差点シーケンシャル番号をふった各交差点ネット
リストを経路探索メモリ上に用意し、交差点ＩＤを登録
する（図２の（０）〜（５）。ステップ２０２、２０
３）。そして、ノードテーブルＮＤＴＢ、交差点構成ノ
ードリストＣＲＤＴ、隣接ノードリストＮＮＬＴから、
交差点構成ノードリスト上の位置、交差点構成ノード
数、隣接ノートリスト上の位置、隣接ノード数を得て、
図２の（６）〜（９）を登録する（ステップ２０４）。
次に、道路リストＲＤＬＴの各道路につき、ノードテー
ブルＮＤＴＢを参照して、相隣る交差点（一方が単純ノ
ードでの隣接ノードの場合を含む）相互間のリンクの距
離を求め、リンクの一方の交差点に係る交差点ネットリ
ストに、リンクの他方の交差点を隣接交差点とし、該隣
接交差点に係る交差点ネットリストに登録された交差点
シーケンシャル番号（隣接交差点シーケンシャル番
号）、当該リンクの距離を登録していく（図２の（１
０）〜（２４）。ステップ２０５）。
【００３６】同様の処理を、図９のＢＵ12〜ＢＵ33につ
いても行ったあと（ステップ２０６、２０２〜２０５の
繰り返し）、最後に、交差点ネットリストの作られた対
象が、交差点ノードで隣接ノードを兼ねている場合と、
交差点ネットリストの作られた対象が単純ノードの隣接
ノートである場合、同一隣接ノードにつき、他の共有ユ
ニットの下でも交差点ネットリストが作られている場合
があることから（図９の隣接ノードＲＮ1 、ＲＮ2 参
照）、隣接ノードリストＮＮＬＴを参照して、他の全て
の共有ユニットでの交差点シーケンシャル番号を探し、
当該交差点ネットリストの中に、隣接交差点シーケンシ
ャル番号と距離（＝０）を登録し、分割図葉間での隣接
ノード接続処理を行う（ステップ２０７）。
いても行ったあと（ステップ２０６、２０２〜２０５の
繰り返し）、最後に、交差点ネットリストの作られた対
象が、交差点ノードで隣接ノードを兼ねている場合と、
交差点ネットリストの作られた対象が単純ノードの隣接
ノートである場合、同一隣接ノードにつき、他の共有ユ
ニットの下でも交差点ネットリストが作られている場合
があることから（図９の隣接ノードＲＮ1 、ＲＮ2 参
照）、隣接ノードリストＮＮＬＴを参照して、他の全て
の共有ユニットでの交差点シーケンシャル番号を探し、
当該交差点ネットリストの中に、隣接交差点シーケンシ
ャル番号と距離（＝０）を登録し、分割図葉間での隣接
ノード接続処理を行う（ステップ２０７）。
【００３７】このようにして、出発地と目的地を結ぶ直
線を対角線とする方形領域を含む１又は複数の全ての４
分割図葉につき、交差点ネットリストが完成した状態に
なったならば、続いて、地域判別部１５ｈが経路探索メ
モリ１５ｉに作成された交差点ネットリストの全数（全
交差点数に相当）を交差点シーケンシャル番号の最大値
から求め、今回の経路探索対象エリアの大きさ（４分割
図葉ＢＵ11〜ＢＵ33を合計した大きさ）で割って交差点
密度を計算する（ステップ２０８）。次いで、一定の基
準値、ここでは一例として1000個／100km 2 と大小比較
を行い、経路探索対象範囲が都市部に存在するか郊外に
存在するか判別し（ステップ２０９）、結果を最適経路
探索部１５ｇに通知する。
線を対角線とする方形領域を含む１又は複数の全ての４
分割図葉につき、交差点ネットリストが完成した状態に
なったならば、続いて、地域判別部１５ｈが経路探索メ
モリ１５ｉに作成された交差点ネットリストの全数（全
交差点数に相当）を交差点シーケンシャル番号の最大値
から求め、今回の経路探索対象エリアの大きさ（４分割
図葉ＢＵ11〜ＢＵ33を合計した大きさ）で割って交差点
密度を計算する（ステップ２０８）。次いで、一定の基
準値、ここでは一例として1000個／100km 2 と大小比較
を行い、経路探索対象範囲が都市部に存在するか郊外に
存在するか判別し（ステップ２０９）、結果を最適経路
探索部１５ｇに通知する。
【００３８】経路探索（都市部） 交差点密度が大きく都市部であったとすると、最適経路
探索部１５ｇは、交差点ネットリストを用いてヒューリ
スティック法による横型探索法により出発地から目的地
を結ぶ最適経路を探索する（図１０参照）。交差点密度
が大きいと道路密度が大きく、大きく回り込まなければ
到達できない場所は存在せず、出発地から目的地に向か
う方向から外れる経路を枝刈りするヒューリスティック
探索を行っても最適経路が探索不能となることはない。
まず、最適経路探索部１５ｇは、出発地交差点ＳＴＰと
目的地交差点ＤＳＰの間の距離を求め、1.5 倍してＬ
LMT として経路探索メモリ１５ｉに登録する（ステップ
２１０）。ＬLMT は、横型探索中、累計距離がＬLMT を
越える経路を枝刈りするために用いる。また、出発地交
差点ＳＴＰを基準とする目的地交差点ＤＳＰの方位（真
北を基準にして時計回りに測るものとする）θ0 を計算
し（図１１参照）、経路探索メモリ１５ｉに登録する
（ステップ２１１）。θ0 は、横型探索中、出発地から
目的地に向かう方向から外れる経路を枝刈りするために
用いる。
探索部１５ｇは、交差点ネットリストを用いてヒューリ
スティック法による横型探索法により出発地から目的地
を結ぶ最適経路を探索する（図１０参照）。交差点密度
が大きいと道路密度が大きく、大きく回り込まなければ
到達できない場所は存在せず、出発地から目的地に向か
う方向から外れる経路を枝刈りするヒューリスティック
探索を行っても最適経路が探索不能となることはない。
まず、最適経路探索部１５ｇは、出発地交差点ＳＴＰと
目的地交差点ＤＳＰの間の距離を求め、1.5 倍してＬ
LMT として経路探索メモリ１５ｉに登録する（ステップ
２１０）。ＬLMT は、横型探索中、累計距離がＬLMT を
越える経路を枝刈りするために用いる。また、出発地交
差点ＳＴＰを基準とする目的地交差点ＤＳＰの方位（真
北を基準にして時計回りに測るものとする）θ0 を計算
し（図１１参照）、経路探索メモリ１５ｉに登録する
（ステップ２１１）。θ0 は、横型探索中、出発地から
目的地に向かう方向から外れる経路を枝刈りするために
用いる。
【００３９】次に、最適経路探索部１５ｇは、まず、検
索次数を０として（図５のステップ３０１）、第０次交
差点（０次は出発地交差点）に隣接する交差点が残存す
るかを出発地交差点ＳＴＰの交差点ネットリストＣＲＮ
Ｌを参照して調べる（ステップ３０２）。なお、ステッ
プ３０２では、それまでに第ｊ次交差点（ｊ＝０，１，
・・，ｉ）とされたのは除く。隣接交差点が残存すれ
ば、その内、１つの隣接交差点、例えばＡ4 について、
第０次交差点を基準にした隣接交差点Ａ4 の方位θを求
め（ステップ３０３、図１１参照）、θ0 との差の絶対
値が一定値θC （ここでは、一例としてθC ＝67.5°と
する）以内か判定する（ステップ３０４）。θは、第０
次交差点の交差点ネットリストから該第０次交差点の経
度、緯度座標を読み出すとともに、第０次交差点の交差
点ネットリストに登録された隣接交差点Ａ4 の交差点シ
ーケンシャル番号に対応する隣接交差点Ａ4 の交差点ネ
ットリストから該隣接交差点Ａ4 の経度，緯度座標を読
み出し、三角関数を用いて計算することができる。経
度，緯度座標は、図２の交差点ネットリストの（５），
（６）の項目に登録されている。
索次数を０として（図５のステップ３０１）、第０次交
差点（０次は出発地交差点）に隣接する交差点が残存す
るかを出発地交差点ＳＴＰの交差点ネットリストＣＲＮ
Ｌを参照して調べる（ステップ３０２）。なお、ステッ
プ３０２では、それまでに第ｊ次交差点（ｊ＝０，１，
・・，ｉ）とされたのは除く。隣接交差点が残存すれ
ば、その内、１つの隣接交差点、例えばＡ4 について、
第０次交差点を基準にした隣接交差点Ａ4 の方位θを求
め（ステップ３０３、図１１参照）、θ0 との差の絶対
値が一定値θC （ここでは、一例としてθC ＝67.5°と
する）以内か判定する（ステップ３０４）。θは、第０
次交差点の交差点ネットリストから該第０次交差点の経
度、緯度座標を読み出すとともに、第０次交差点の交差
点ネットリストに登録された隣接交差点Ａ4 の交差点シ
ーケンシャル番号に対応する隣接交差点Ａ4 の交差点ネ
ットリストから該隣接交差点Ａ4 の経度，緯度座標を読
み出し、三角関数を用いて計算することができる。経
度，緯度座標は、図２の交差点ネットリストの（５），
（６）の項目に登録されている。
【００４０】ステップ３０４でＹＥＳとなったとき、最
適経路探索部１５ｇは第０次交差点から隣接交差点Ａ4
への経路は特に目的地方向から外れないので枝刈りせ
ず、ＮＯとなったときは、目的地方向から外れるので枝
刈りする（図１０参照）。ここではＮＯとなるので枝刈
りし、ステップ３０２に戻って、第０次交差点に隣接す
る他の交差点が残存するか第０次交差点の交差点ネット
リストを参照して調べる。隣接交差点Ａ1 が残存するの
で、続いて、第０次交差点を基準にした隣接交差点Ａ1
の方位θを求め、θ0 との差の絶対値が一定値θC （こ
こでは、一例としてθC ＝67.5°とする）以内か判定す
る（ステップ３０３、３０４）。今度は、ＹＥＳとなる
ので、続いて、出発地交差点ＳＴＰから隣接交差点Ａ1
までの累計距離Ｄを計算する（ステップ３０５）。Ｄは
出発地交差点ＳＴＰから第ｉ次交差点までの累計距離を
ｄ1 、第ｉ次交差点から当該隣接交差点Ａ1 までの距離
をｄ2 とすると、次式 ｄ1 ＋ｄ2 →Ｄ により求まるが、初めｉ＝０のときはｄ1 ＝０なのでＤ
＝ｄ2 となる。ｄ2 は出発地交差点ＳＴＰに係る交差点
ネットリストＣＲＮＬの図２における（１１）、（１
３）等の項目に記憶されている。
適経路探索部１５ｇは第０次交差点から隣接交差点Ａ4
への経路は特に目的地方向から外れないので枝刈りせ
ず、ＮＯとなったときは、目的地方向から外れるので枝
刈りする（図１０参照）。ここではＮＯとなるので枝刈
りし、ステップ３０２に戻って、第０次交差点に隣接す
る他の交差点が残存するか第０次交差点の交差点ネット
リストを参照して調べる。隣接交差点Ａ1 が残存するの
で、続いて、第０次交差点を基準にした隣接交差点Ａ1
の方位θを求め、θ0 との差の絶対値が一定値θC （こ
こでは、一例としてθC ＝67.5°とする）以内か判定す
る（ステップ３０３、３０４）。今度は、ＹＥＳとなる
ので、続いて、出発地交差点ＳＴＰから隣接交差点Ａ1
までの累計距離Ｄを計算する（ステップ３０５）。Ｄは
出発地交差点ＳＴＰから第ｉ次交差点までの累計距離を
ｄ1 、第ｉ次交差点から当該隣接交差点Ａ1 までの距離
をｄ2 とすると、次式 ｄ1 ＋ｄ2 →Ｄ により求まるが、初めｉ＝０のときはｄ1 ＝０なのでＤ
＝ｄ2 となる。ｄ2 は出発地交差点ＳＴＰに係る交差点
ネットリストＣＲＮＬの図２における（１１）、（１
３）等の項目に記憶されている。
【００４１】次いで、累計距離ＤがＬLMT を越えている
かチェックし（ステップ３０６）、以下であれば、隣接
交差点Ａ1 に係る交差点ネットリストＣＲＮＬの図２に
おける（２５）以降の項目を参照して、既に、交差点Ａ
1 につき、異なる経路での累計距離及び１つ手前の交差
点を特定する情報（交差点シーケンシャル番号）等が登
録済みかチェックし（ステップ３０７）、ここではＮＯ
となるので、当該隣接交差点Ａ1 に係る交差点ネットリ
ストＣＲＮＬの図２における（２５）〜（２７）に、以
下のデータ （Ａ）現在着目している第０次交差点ＳＴＰの交差点シ
ーケンシャル番号、 （Ｂ）第０次交差点ＳＴＰから当該隣接交差点Ａ1 まで
の累計距離、 （Ｃ）当該隣接交差点Ａ1 の検索次数としての（ｉ＋
１）＝１ を登録し（ステップ３０８）、以降、ステップ３０２に
戻り、出発地交差点ＳＴＰを対象とした交差点ネットリ
ストＣＲＮＬを参照して、着目している第０次交差点に
隣接する交差点がなお残存するか調べ、残存すれば同様
の処理を繰り返す。
かチェックし（ステップ３０６）、以下であれば、隣接
交差点Ａ1 に係る交差点ネットリストＣＲＮＬの図２に
おける（２５）以降の項目を参照して、既に、交差点Ａ
1 につき、異なる経路での累計距離及び１つ手前の交差
点を特定する情報（交差点シーケンシャル番号）等が登
録済みかチェックし（ステップ３０７）、ここではＮＯ
となるので、当該隣接交差点Ａ1 に係る交差点ネットリ
ストＣＲＮＬの図２における（２５）〜（２７）に、以
下のデータ （Ａ）現在着目している第０次交差点ＳＴＰの交差点シ
ーケンシャル番号、 （Ｂ）第０次交差点ＳＴＰから当該隣接交差点Ａ1 まで
の累計距離、 （Ｃ）当該隣接交差点Ａ1 の検索次数としての（ｉ＋
１）＝１ を登録し（ステップ３０８）、以降、ステップ３０２に
戻り、出発地交差点ＳＴＰを対象とした交差点ネットリ
ストＣＲＮＬを参照して、着目している第０次交差点に
隣接する交差点がなお残存するか調べ、残存すれば同様
の処理を繰り返す。
【００４２】隣接交差点Ａ2 が残存するので、第０次交
差点を基準とする隣接交差点Ａ2 の方位θを求め、θ0
との差の絶対値がθC 以内か判定する。ここでも、ＹＥ
Ｓとなるので、Ａ1 の場合と同様にして、出発地交差点
ＳＴＰから隣接交差点Ａ2 までの累計距離Ｄを求め、該
累計距離ＤがＬLMT 以下であれば、隣接交差点Ａ2 の交
差点ネットリストに、第０次交差点の交差点シーケンシ
ャル番号と検索次数（ｉ＋１）とともに登録する（ステ
ップ３０２〜３０８）。そして、ステップ３０２に戻
る。まだ隣接交差点Ａ3 が残存するが、第０次交差点を
基準とする方位θとθ0 との差の絶対値がθC を越えて
いるので（ステップ３０４でＮＯ）、ステップ３０５以
降には進まず、枝刈りする。この結果、出発地交差点Ｓ
ＴＰの交差点ネットリストに隣接交差点Ａ1 〜Ａ4が存
在しており、この内、Ａ1 とＡ2 だけが１次交差点とさ
れ、対応する各交差点ネットリストＣＲＮＬに、１つ手
前の交差点（ここでは出発地交差点ＳＴＰ）の交差点シ
ーケンシャル番号、出発地からの累計距離Ａｄ1 ，Ａｄ
2 、検索次数１が登録される。一方、Ａ4 とＡ3 の交差
点ネットリストにはこれらのデータは登録されない。
差点を基準とする隣接交差点Ａ2 の方位θを求め、θ0
との差の絶対値がθC 以内か判定する。ここでも、ＹＥ
Ｓとなるので、Ａ1 の場合と同様にして、出発地交差点
ＳＴＰから隣接交差点Ａ2 までの累計距離Ｄを求め、該
累計距離ＤがＬLMT 以下であれば、隣接交差点Ａ2 の交
差点ネットリストに、第０次交差点の交差点シーケンシ
ャル番号と検索次数（ｉ＋１）とともに登録する（ステ
ップ３０２〜３０８）。そして、ステップ３０２に戻
る。まだ隣接交差点Ａ3 が残存するが、第０次交差点を
基準とする方位θとθ0 との差の絶対値がθC を越えて
いるので（ステップ３０４でＮＯ）、ステップ３０５以
降には進まず、枝刈りする。この結果、出発地交差点Ｓ
ＴＰの交差点ネットリストに隣接交差点Ａ1 〜Ａ4が存
在しており、この内、Ａ1 とＡ2 だけが１次交差点とさ
れ、対応する各交差点ネットリストＣＲＮＬに、１つ手
前の交差点（ここでは出発地交差点ＳＴＰ）の交差点シ
ーケンシャル番号、出発地からの累計距離Ａｄ1 ，Ａｄ
2 、検索次数１が登録される。一方、Ａ4 とＡ3 の交差
点ネットリストにはこれらのデータは登録されない。
【００４３】出発地交差点ＳＴＰを対象とした交差点ネ
ットリストＣＲＮＬに含まれる全ての隣接交差点につき
処理が終わると、最適経路探索部１５ｇは、出発地交差
点ＳＴＰ以外に第０次交差点が存在するか判断し（ステ
ップ３０９）、存在しないので、続いて目的地交差点Ｄ
ＳＰに到達したか、換言すれば第（ｉ＋１）次交差点と
した中に目的地交差点ＤＳＰが含まれているか判断し
（ステップ３１０）、含まれていなければ、ｉをインク
リメントして１とする（ステップ３１１）。そして、第
１次交差点とされた内の１つ、例えばＡ1 に着目して、
経路探索メモリ１５ｉに記憶された交差点Ａ1 に係る交
差点ネットリストを参照して、それまでに第０次交差
点、第１次交差点とされた交差点以外で隣接交差点が存
在するか判断する（ステップ３０２）。ここでは、
Ｂ11，Ｂ12，Ｂ13が存在するので、その内の１つ、例え
ば隣接交差点Ｂ11につき、交差点Ａ1 の交差点ネットリ
ストと隣接交差点Ｂ11の交差点ネットリストを参照し
て、第１次交差点Ａ1 を基準とする隣接交差点Ｂ11の方
位θを求め、θ0 との差の絶対値がθC 以内か判定する
（ステップ３０３、３０４）。ここではＮＯとなるの
で、ステップ３０５以降には進まず交差点Ａ1 からＢ11
に向かう経路は枝刈りし、ステップ３０２に戻り、交差
点Ａ1 に隣接する他の交差点が存在するか調べる。
ットリストＣＲＮＬに含まれる全ての隣接交差点につき
処理が終わると、最適経路探索部１５ｇは、出発地交差
点ＳＴＰ以外に第０次交差点が存在するか判断し（ステ
ップ３０９）、存在しないので、続いて目的地交差点Ｄ
ＳＰに到達したか、換言すれば第（ｉ＋１）次交差点と
した中に目的地交差点ＤＳＰが含まれているか判断し
（ステップ３１０）、含まれていなければ、ｉをインク
リメントして１とする（ステップ３１１）。そして、第
１次交差点とされた内の１つ、例えばＡ1 に着目して、
経路探索メモリ１５ｉに記憶された交差点Ａ1 に係る交
差点ネットリストを参照して、それまでに第０次交差
点、第１次交差点とされた交差点以外で隣接交差点が存
在するか判断する（ステップ３０２）。ここでは、
Ｂ11，Ｂ12，Ｂ13が存在するので、その内の１つ、例え
ば隣接交差点Ｂ11につき、交差点Ａ1 の交差点ネットリ
ストと隣接交差点Ｂ11の交差点ネットリストを参照し
て、第１次交差点Ａ1 を基準とする隣接交差点Ｂ11の方
位θを求め、θ0 との差の絶対値がθC 以内か判定する
（ステップ３０３、３０４）。ここではＮＯとなるの
で、ステップ３０５以降には進まず交差点Ａ1 からＢ11
に向かう経路は枝刈りし、ステップ３０２に戻り、交差
点Ａ1 に隣接する他の交差点が存在するか調べる。
【００４４】隣接交差点Ｂ12が存在するので、交差点Ａ
1 を基準とする隣接交差点Ｂ12の方位θを求め、θ0 と
の差の絶対値がθC 以内か判定する（ステップ３０３、
３０４）。今度はＹＥＳなので、交差点Ａ1 に係る交差
点ネットリストを参照しながら、出発地交差点ＳＴＰ、
現在着目している第１次交差点Ａ1 、隣接交差点Ｂ12の
経路における累計距離Ｄを計算する（ステップ３０
５）。出発地交差点ＳＴＰから現在着目している第１次
交差点Ａ1 までの累計距離Ａｄ1 と第１次交差点Ａ 1 か
ら当該隣接交差点Ｂ12までの距離ｄ2 は交差点Ａ1 の交
差点ネットリストＣＲＮＬの図２における項目（２６）
と、（１１），（１３），（１５）等の中の１つとして
記憶されているから、 Ａｄ1 ＋ｄ2 →Ｄ により出発地交差点ＳＴＰから当該隣接交差点Ｂ12まで
の累計距離Ｄが求まる。次いで、ＬLMT 以下かチェック
し（ステップ３０６）、ＹＥＳであれば隣接交差点Ｂ12
に係る交差点ネットリストＣＲＮＬを参照して、図２の
（２７）の項目に登録された検索次数が（ｉ＋１）＝２
かチェックし（ステップ３０７）、ここではＮＯなの
で、当該隣接交差点Ｂ12に対応させて、以下のデータ （Ａ）現在着目している第１次交差点Ａ1 の交差点シー
ケンシャル番号、 （Ｂ）出発地から当該隣接交差点Ｂ12までの累計距離、 （Ｃ）当該隣接交差点Ｂ12の検索次数としての（ｉ＋
１）＝２ を交差点Ｂ12の交差点ネットリストＣＲＮＬの図２の
（２５）〜（２７）に登録し（ステップ３０５）、ステ
ップ３０２側に戻って、第１次交差点Ａ1 に係る次の隣
接交差点があれば、同様の処理を行う。
1 を基準とする隣接交差点Ｂ12の方位θを求め、θ0 と
の差の絶対値がθC 以内か判定する（ステップ３０３、
３０４）。今度はＹＥＳなので、交差点Ａ1 に係る交差
点ネットリストを参照しながら、出発地交差点ＳＴＰ、
現在着目している第１次交差点Ａ1 、隣接交差点Ｂ12の
経路における累計距離Ｄを計算する（ステップ３０
５）。出発地交差点ＳＴＰから現在着目している第１次
交差点Ａ1 までの累計距離Ａｄ1 と第１次交差点Ａ 1 か
ら当該隣接交差点Ｂ12までの距離ｄ2 は交差点Ａ1 の交
差点ネットリストＣＲＮＬの図２における項目（２６）
と、（１１），（１３），（１５）等の中の１つとして
記憶されているから、 Ａｄ1 ＋ｄ2 →Ｄ により出発地交差点ＳＴＰから当該隣接交差点Ｂ12まで
の累計距離Ｄが求まる。次いで、ＬLMT 以下かチェック
し（ステップ３０６）、ＹＥＳであれば隣接交差点Ｂ12
に係る交差点ネットリストＣＲＮＬを参照して、図２の
（２７）の項目に登録された検索次数が（ｉ＋１）＝２
かチェックし（ステップ３０７）、ここではＮＯなの
で、当該隣接交差点Ｂ12に対応させて、以下のデータ （Ａ）現在着目している第１次交差点Ａ1 の交差点シー
ケンシャル番号、 （Ｂ）出発地から当該隣接交差点Ｂ12までの累計距離、 （Ｃ）当該隣接交差点Ｂ12の検索次数としての（ｉ＋
１）＝２ を交差点Ｂ12の交差点ネットリストＣＲＮＬの図２の
（２５）〜（２７）に登録し（ステップ３０５）、ステ
ップ３０２側に戻って、第１次交差点Ａ1 に係る次の隣
接交差点があれば、同様の処理を行う。
【００４５】なお、隣接交差点Ｂ13が存在しており、現
在着目している第１次交差点Ａ1 を基準とする隣接交差
点Ｂ13の方位θを求め、θ0 との差の絶対値がθC 以内
か判定する。ここでも、ＹＥＳとなるので、Ｂ12の場合
と同様にして、出発地交差点ＳＴＰから隣接交差点Ｂ13
までの累計距離Ｄを求め、隣接交差点Ｂ13の交差点ネッ
トリストに、第１次交差点Ａ1 の交差点シーケンシャル
番号と検索次数（ｉ＋１）とともに登録する（ステップ
３０３〜３０８）。そして、ステップ３０２に戻る。こ
の結果、第１次交差点Ａ1 の交差点ネットリストに出発
地交差点以外に隣接交差点Ｂ11〜Ｂ13が存在しており、
この内、Ｂ12とＢ13だけが１次交差点とされ、対応する
各交差点ネットリストＣＲＮＬに、１つ手前の交差点の
交差点シーケンシャル番号、出発地からの累計距離Ｂｄ
12，Ｂｄ13、検索次数２が登録される。一方、Ｂ11の交
差点ネットリストには、これらのデータは登録されな
い。
在着目している第１次交差点Ａ1 を基準とする隣接交差
点Ｂ13の方位θを求め、θ0 との差の絶対値がθC 以内
か判定する。ここでも、ＹＥＳとなるので、Ｂ12の場合
と同様にして、出発地交差点ＳＴＰから隣接交差点Ｂ13
までの累計距離Ｄを求め、隣接交差点Ｂ13の交差点ネッ
トリストに、第１次交差点Ａ1 の交差点シーケンシャル
番号と検索次数（ｉ＋１）とともに登録する（ステップ
３０３〜３０８）。そして、ステップ３０２に戻る。こ
の結果、第１次交差点Ａ1 の交差点ネットリストに出発
地交差点以外に隣接交差点Ｂ11〜Ｂ13が存在しており、
この内、Ｂ12とＢ13だけが１次交差点とされ、対応する
各交差点ネットリストＣＲＮＬに、１つ手前の交差点の
交差点シーケンシャル番号、出発地からの累計距離Ｂｄ
12，Ｂｄ13、検索次数２が登録される。一方、Ｂ11の交
差点ネットリストには、これらのデータは登録されな
い。
【００４６】交差点Ａ1 を対象とした交差点ネットリス
トＣＲＮＬに含まれる全ての隣接交差点につき処理が終
わると、最適経路探索部１５ｇは、交差点Ａ1 以外に第
１次交差点が存在するか判断し（ステップ３０９）、こ
こでは交差点Ａ2 が存在するので、新たな第１次交差点
として（ステップ３１２）、ステップ３０２以降の処理
を繰り返す。交差点Ａ2 の交差点ネットリストには、出
発地以外に隣接交差点Ｂ21〜Ｂ23が存在している。この
内、Ｂ21とＢ22はステップ３０４で枝刈りされないが、
Ｂ23はθとθ0 の差の絶対値がθC を越えるので枝刈り
される。Ｂ21の処理においては、ステップ３０６でＹＥ
Ｓとなったとき、Ｂ13＝Ｂ21なので、ステップ３０７に
おいて、隣接交差点Ｂ13の次数が既に２となっているた
めＹＥＳとなる。これは、先に第１次交差点Ａ1 に隣接
する交差点Ｂ13として処理済み（前記（Ａ）〜（Ｃ）の
データが記憶済み）であることを示すが、この場合、該
隣接交差点Ｂ13に係る交差点ネットリストＣＲＮＬに登
録してある出発地交差点ＳＴＰからの累計距離Ｄ′＝Ｂ
ｄ13と、今回ステップ３０３で求めた距離Ｄの大小を比
較する（ステップ３１３）。
トＣＲＮＬに含まれる全ての隣接交差点につき処理が終
わると、最適経路探索部１５ｇは、交差点Ａ1 以外に第
１次交差点が存在するか判断し（ステップ３０９）、こ
こでは交差点Ａ2 が存在するので、新たな第１次交差点
として（ステップ３１２）、ステップ３０２以降の処理
を繰り返す。交差点Ａ2 の交差点ネットリストには、出
発地以外に隣接交差点Ｂ21〜Ｂ23が存在している。この
内、Ｂ21とＢ22はステップ３０４で枝刈りされないが、
Ｂ23はθとθ0 の差の絶対値がθC を越えるので枝刈り
される。Ｂ21の処理においては、ステップ３０６でＹＥ
Ｓとなったとき、Ｂ13＝Ｂ21なので、ステップ３０７に
おいて、隣接交差点Ｂ13の次数が既に２となっているた
めＹＥＳとなる。これは、先に第１次交差点Ａ1 に隣接
する交差点Ｂ13として処理済み（前記（Ａ）〜（Ｃ）の
データが記憶済み）であることを示すが、この場合、該
隣接交差点Ｂ13に係る交差点ネットリストＣＲＮＬに登
録してある出発地交差点ＳＴＰからの累計距離Ｄ′＝Ｂ
ｄ13と、今回ステップ３０３で求めた距離Ｄの大小を比
較する（ステップ３１３）。
【００４７】Ｄ＜Ｄ′であれば、当該隣接交差点Ｂ
13（＝Ｂ12）の交差点ネットリストＣＲＮＬの図２にお
ける（２５）と（２６）の項目に記憶してある、第ｉ次
交差点Ａ 1 の交差点シーケンシャル番号を現在着目して
いる第ｉ次交差点Ａ2 の交差点シーケンシャル番号で置
き換えるとともに、累計距離Ｄ′をＤ＝Ｂｄ21で書き換
え（ステップ３１３）、以降、ステップ３０２に戻る。
また、Ｄ≧Ｄ′の場合は、当該交差点Ｂ13（＝Ｂ21）に
係る交差点ネットリストＣＲＮＬの図２における（２
５）〜（２６）の内容を変更せずステップ３０２に戻
る。交差点Ａ2 に関して、各隣接交差点に対する所定の
処理を終え、別の第１次交差点が存在しなくなれば、目
的地交差点ＤＳＰに到達したかチェックし（ステップ３
０１）、まだなので、ｉをインクリメントして２とする
（ステップ３１１）。次いで、ステップ３０２へ進み、
前述と同様の処理を順に繰り返していく。
13（＝Ｂ12）の交差点ネットリストＣＲＮＬの図２にお
ける（２５）と（２６）の項目に記憶してある、第ｉ次
交差点Ａ 1 の交差点シーケンシャル番号を現在着目して
いる第ｉ次交差点Ａ2 の交差点シーケンシャル番号で置
き換えるとともに、累計距離Ｄ′をＤ＝Ｂｄ21で書き換
え（ステップ３１３）、以降、ステップ３０２に戻る。
また、Ｄ≧Ｄ′の場合は、当該交差点Ｂ13（＝Ｂ21）に
係る交差点ネットリストＣＲＮＬの図２における（２
５）〜（２６）の内容を変更せずステップ３０２に戻
る。交差点Ａ2 に関して、各隣接交差点に対する所定の
処理を終え、別の第１次交差点が存在しなくなれば、目
的地交差点ＤＳＰに到達したかチェックし（ステップ３
０１）、まだなので、ｉをインクリメントして２とする
（ステップ３１１）。次いで、ステップ３０２へ進み、
前述と同様の処理を順に繰り返していく。
【００４８】このように、第ｉ次交差点から或る隣接交
差点へ向かう経路の方向が出発地から見た目的地の方向
よりθC 以上ずれている場合、当該経路は枝刈りされて
それより先へ探索が進まないので、不要な経路の探索が
省かれ、また、目的地に到達しないまま累計距離がＬ
LMT を越えた場合も、それより先へ探索が進まないの
で、目的地から外れるような経路の探索が省かれる。
差点へ向かう経路の方向が出発地から見た目的地の方向
よりθC 以上ずれている場合、当該経路は枝刈りされて
それより先へ探索が進まないので、不要な経路の探索が
省かれ、また、目的地に到達しないまま累計距離がＬ
LMT を越えた場合も、それより先へ探索が進まないの
で、目的地から外れるような経路の探索が省かれる。
【００４９】その後、ステップ３１０のチェックにおい
て、第（ｉ＋１）次とされた全ての交差点の中に目的地
交差点ＤＳＰが含まれていて、ＹＥＳと判断されたと
き、目的地交差点ＤＳＰ、該目的地交差点ＤＳＰ（ｍ次
の交差点とする）に係る交差点ネットリストＣＲＮＬの
図２の（２５）の項目として記憶してある（ｍ−１）次
の交差点、該（ｍ−１）次の交差点に係る交差点ネット
リストＣＲＮＬに記憶してある（ｍ−２）次の交差点、
・・・、２次の交差点に係る交差点ネットリストＣＲＮ
Ｌに記憶してある１次交差点、１次交差点に係る交差点
ネットリストＣＲＮＬに記憶してある０次交差点＝出発
地交差点ＳＴＰを、出発地側から目的地側に向けた順序
で順次結んで最短経路を決定する（ステップ３１５）。
そして、求めた最短経路を構成するノード列を誘導経路
データとして誘導経路記憶部１５ｊに記憶させて経路探
索処理を終了する（ステップ３１６）。
て、第（ｉ＋１）次とされた全ての交差点の中に目的地
交差点ＤＳＰが含まれていて、ＹＥＳと判断されたと
き、目的地交差点ＤＳＰ、該目的地交差点ＤＳＰ（ｍ次
の交差点とする）に係る交差点ネットリストＣＲＮＬの
図２の（２５）の項目として記憶してある（ｍ−１）次
の交差点、該（ｍ−１）次の交差点に係る交差点ネット
リストＣＲＮＬに記憶してある（ｍ−２）次の交差点、
・・・、２次の交差点に係る交差点ネットリストＣＲＮ
Ｌに記憶してある１次交差点、１次交差点に係る交差点
ネットリストＣＲＮＬに記憶してある０次交差点＝出発
地交差点ＳＴＰを、出発地側から目的地側に向けた順序
で順次結んで最短経路を決定する（ステップ３１５）。
そして、求めた最短経路を構成するノード列を誘導経路
データとして誘導経路記憶部１５ｊに記憶させて経路探
索処理を終了する（ステップ３１６）。
【００５０】経路探索（郊外） これと異なり、図４のステップ２０９で交差点密度が小
さく郊外と判別された場合、最適経路探索部１５ｇは、
交差点ネットリストを用いてヒューリスティックでない
通常の横型探索法により出発地から目的地までを結ぶ最
適経路を探索する（図２３参照）。交差点密度が小さい
と道路密度が小さく、大きく回り込まなければ目的地に
到達できない場合がある。
さく郊外と判別された場合、最適経路探索部１５ｇは、
交差点ネットリストを用いてヒューリスティックでない
通常の横型探索法により出発地から目的地までを結ぶ最
適経路を探索する（図２３参照）。交差点密度が小さい
と道路密度が小さく、大きく回り込まなければ目的地に
到達できない場合がある。
【００５１】このとき、最適経路探索部１５ｇは、図６
のステップ４０１へ進み、まず、検索次数を０として、
第０次交差点（０次は出発地交差点）に隣接する交差点
が残存するかを出発地交差点ＳＴＰの交差点ネットリス
トＣＲＮＬを参照して調べる（ステップ４０２）。Ａ1
が存在するので、出発地交差点ＳＴＰから隣接交差点Ａ
1 までの累計距離Ｄを計算する（ステップ４０３）。Ｄ
は出発地交差点ＳＴＰから第ｉ次交差点までの累計距離
をｄ1 、第ｉ次交差点から当該隣接交差点Ａ1 までの距
離ｄ2 とすると、次式 ｄ1 ＋ｄ2 →Ｄ により求まるが、初めｉ＝０のときはｄ1 ＝０なのでＤ
＝ｄ2 となる。ｄ2 は出発地交差点ＳＴＰに係る交差点
ネットリストＣＲＮＬの図２における（２６）等の項目
に記憶されている。
のステップ４０１へ進み、まず、検索次数を０として、
第０次交差点（０次は出発地交差点）に隣接する交差点
が残存するかを出発地交差点ＳＴＰの交差点ネットリス
トＣＲＮＬを参照して調べる（ステップ４０２）。Ａ1
が存在するので、出発地交差点ＳＴＰから隣接交差点Ａ
1 までの累計距離Ｄを計算する（ステップ４０３）。Ｄ
は出発地交差点ＳＴＰから第ｉ次交差点までの累計距離
をｄ1 、第ｉ次交差点から当該隣接交差点Ａ1 までの距
離ｄ2 とすると、次式 ｄ1 ＋ｄ2 →Ｄ により求まるが、初めｉ＝０のときはｄ1 ＝０なのでＤ
＝ｄ2 となる。ｄ2 は出発地交差点ＳＴＰに係る交差点
ネットリストＣＲＮＬの図２における（２６）等の項目
に記憶されている。
【００５２】次いで、隣接交差点Ａ1 に係る交差点ネッ
トリストＣＲＮＬの図２における（２５）以降の項目を
参照して、既に、交差点Ａ1 につき、異なる経路での累
計距離及び１つ手前の交差点を特定する情報（交差点シ
ーケンシャル番号）等が登録済みかチェックし（ステッ
プ４０４）、ＮＯとなるので、当該隣接交差点Ａ1 に係
る交差点ネットリストＣＲＮＬの図２における（２５）
〜（２７）に、以下のデータ （Ａ）現在着目している第０次交差点ＳＴＰの交差点シ
ーケンシャル番号、 （Ｂ）第０次交差点ＳＴＰから当該隣接交差点Ａ1 まで
の累計距離、 （Ｃ）当該隣接交差点Ａ1 の検索次数としての（ｉ＋
１）＝１ を登録し（ステップ４０５）、以降、ステップ４０２に
戻り、出発地交差点ＳＴＰを対象とした交差点ネットリ
ストＣＲＮＬを参照して、着目している第０次交差点に
隣接する交差点がなお残存するか調べ、残存すれば同様
の処理を繰り返す。この結果、出発地交差点ＳＴＰの交
差点ネットリストに隣接交差点Ａ1 〜Ａ4が存在してお
り、これら全てが１次交差点とされ、対応する各交差点
ネットリストＣＲＮＬに、１つ手前の交差点（ここでは
出発地交差点ＳＴＰ）の交差点シーケンシャル番号、出
発地からの累計距離Ａｄ1 〜Ａｄ4 、検索次数１が登録
される。
トリストＣＲＮＬの図２における（２５）以降の項目を
参照して、既に、交差点Ａ1 につき、異なる経路での累
計距離及び１つ手前の交差点を特定する情報（交差点シ
ーケンシャル番号）等が登録済みかチェックし（ステッ
プ４０４）、ＮＯとなるので、当該隣接交差点Ａ1 に係
る交差点ネットリストＣＲＮＬの図２における（２５）
〜（２７）に、以下のデータ （Ａ）現在着目している第０次交差点ＳＴＰの交差点シ
ーケンシャル番号、 （Ｂ）第０次交差点ＳＴＰから当該隣接交差点Ａ1 まで
の累計距離、 （Ｃ）当該隣接交差点Ａ1 の検索次数としての（ｉ＋
１）＝１ を登録し（ステップ４０５）、以降、ステップ４０２に
戻り、出発地交差点ＳＴＰを対象とした交差点ネットリ
ストＣＲＮＬを参照して、着目している第０次交差点に
隣接する交差点がなお残存するか調べ、残存すれば同様
の処理を繰り返す。この結果、出発地交差点ＳＴＰの交
差点ネットリストに隣接交差点Ａ1 〜Ａ4が存在してお
り、これら全てが１次交差点とされ、対応する各交差点
ネットリストＣＲＮＬに、１つ手前の交差点（ここでは
出発地交差点ＳＴＰ）の交差点シーケンシャル番号、出
発地からの累計距離Ａｄ1 〜Ａｄ4 、検索次数１が登録
される。
【００５３】出発地交差点ＳＴＰを対象とした交差点ネ
ットリストＣＲＮＬに含まれる全ての隣接交差点につき
処理が終わると、最適経路探索部１５ｇは、出発地交差
点ＳＴＰ以外に第０次交差点が存在するか判断し（ステ
ップ４０６）、存在しないので、続いて目的地交差点Ｄ
ＳＰに到達したか判断し（ステップ４０７）、まだであ
れば、ｉをインクリメントして１とする（ステップ４０
８）。そして、第１次交差点とされた内の１つである例
えばＡ1 に着目して、まず、経路探索メモリ１５ｉに記
憶された交差点Ａ1 に係る交差点ネットリストを参照し
て、それまでに第０次交差点、第１次交差点とされた交
差点以外で隣接交差点が存在するか判断する（ステップ
４０２）。ここでは、Ｂ11，Ｂ12，Ｂ13が存在するの
で、その内の１つ、例えば隣接交差点Ｂ11につき、交差
点Ａ1 の交差点ネットリストを参照しながら、出発地交
差点ＳＴＰ、現在着目している第１次交差点Ａ1 、隣接
交差点Ｂ11の経路における累計距離Ｄを計算する（ステ
ップ４０３）。出発地交差点ＳＴＰから現在着目してい
る第１次交差点Ａ1 までの累計距離ｄ1 （＝Ａｄ1 ）と
第１次交差点Ａ1 から当該隣接交差点Ｂ11までの距離ｄ
2 は交差点Ａ1 の交差点ネットリストＣＲＮＬの図２に
おける項目（２６）と、（１１），（１３），（１５）
等の中の１つとして記憶されていから、 ｄ1 ＋ｄ2 →Ｄ により出発地交差点ＳＴＰから当該隣接交差点Ｂ11まで
の累計距離Ｄが求まる。
ットリストＣＲＮＬに含まれる全ての隣接交差点につき
処理が終わると、最適経路探索部１５ｇは、出発地交差
点ＳＴＰ以外に第０次交差点が存在するか判断し（ステ
ップ４０６）、存在しないので、続いて目的地交差点Ｄ
ＳＰに到達したか判断し（ステップ４０７）、まだであ
れば、ｉをインクリメントして１とする（ステップ４０
８）。そして、第１次交差点とされた内の１つである例
えばＡ1 に着目して、まず、経路探索メモリ１５ｉに記
憶された交差点Ａ1 に係る交差点ネットリストを参照し
て、それまでに第０次交差点、第１次交差点とされた交
差点以外で隣接交差点が存在するか判断する（ステップ
４０２）。ここでは、Ｂ11，Ｂ12，Ｂ13が存在するの
で、その内の１つ、例えば隣接交差点Ｂ11につき、交差
点Ａ1 の交差点ネットリストを参照しながら、出発地交
差点ＳＴＰ、現在着目している第１次交差点Ａ1 、隣接
交差点Ｂ11の経路における累計距離Ｄを計算する（ステ
ップ４０３）。出発地交差点ＳＴＰから現在着目してい
る第１次交差点Ａ1 までの累計距離ｄ1 （＝Ａｄ1 ）と
第１次交差点Ａ1 から当該隣接交差点Ｂ11までの距離ｄ
2 は交差点Ａ1 の交差点ネットリストＣＲＮＬの図２に
おける項目（２６）と、（１１），（１３），（１５）
等の中の１つとして記憶されていから、 ｄ1 ＋ｄ2 →Ｄ により出発地交差点ＳＴＰから当該隣接交差点Ｂ11まで
の累計距離Ｄが求まる。
【００５４】次いで、隣接交差点Ｂ11に係る交差点ネッ
トリストＣＲＮＬを参照して、図２の（２７）の項目に
登録された検索次数が（ｉ＋１）＝２かチェックし（ス
テップ３０４）、ＮＯなので、当該隣接交差点Ｂ11に対
応させて、以下のデータ （Ａ）現在着目している第１次交差点Ａ1 の交差点シー
ケンシャル番号、 （Ｂ）出発地から当該隣接交差点Ｂ11までの累計距離、 （Ｃ）当該隣接交差点Ｂ11の検索次数としての（ｉ＋
１）＝２ を交差点Ｂ11に係る交差点ネットリストＣＲＮＬの図２
の（２５）〜（２７）に登録し（ステップ４０５）、ス
テップ４０２側に戻って、第１次交差点Ａ1 に係る次の
隣接交差点があれば、同様の処理を行う。
トリストＣＲＮＬを参照して、図２の（２７）の項目に
登録された検索次数が（ｉ＋１）＝２かチェックし（ス
テップ３０４）、ＮＯなので、当該隣接交差点Ｂ11に対
応させて、以下のデータ （Ａ）現在着目している第１次交差点Ａ1 の交差点シー
ケンシャル番号、 （Ｂ）出発地から当該隣接交差点Ｂ11までの累計距離、 （Ｃ）当該隣接交差点Ｂ11の検索次数としての（ｉ＋
１）＝２ を交差点Ｂ11に係る交差点ネットリストＣＲＮＬの図２
の（２５）〜（２７）に登録し（ステップ４０５）、ス
テップ４０２側に戻って、第１次交差点Ａ1 に係る次の
隣接交差点があれば、同様の処理を行う。
【００５５】交差点Ａ1 の交差点ネットリストになお、
隣接交差点Ｂ12、Ｂ13が存在しているので、Ｂ11の場合
と同様にして、出発地交差点ＳＴＰから隣接交差点
Ｂ12，Ｂ 13までの累計距離Ｄを求め、各隣接交差点
Ｂ12，Ｂ13の交差点ネットリストに、第１次交差点Ａ1
の交差点シーケンシャル番号と検索次数（ｉ＋１）とと
もに登録する（ステップ４０２〜４０５）。そして、ス
テップ４０２に戻る。この結果、第１次交差点Ａ1 に隣
接する隣接交差点Ｂ11，Ｂ12，Ｂ13が存在しており、こ
れらに対応する各交差点ネットリストＣＲＮＬに、１つ
手前の交差点の交差点シーケンシャル番号、出発地から
の累計距離Ｂｄ11，Ｂｄ12，Ｂｄ13、検索次数２が登録
される。
隣接交差点Ｂ12、Ｂ13が存在しているので、Ｂ11の場合
と同様にして、出発地交差点ＳＴＰから隣接交差点
Ｂ12，Ｂ 13までの累計距離Ｄを求め、各隣接交差点
Ｂ12，Ｂ13の交差点ネットリストに、第１次交差点Ａ1
の交差点シーケンシャル番号と検索次数（ｉ＋１）とと
もに登録する（ステップ４０２〜４０５）。そして、ス
テップ４０２に戻る。この結果、第１次交差点Ａ1 に隣
接する隣接交差点Ｂ11，Ｂ12，Ｂ13が存在しており、こ
れらに対応する各交差点ネットリストＣＲＮＬに、１つ
手前の交差点の交差点シーケンシャル番号、出発地から
の累計距離Ｂｄ11，Ｂｄ12，Ｂｄ13、検索次数２が登録
される。
【００５６】交差点Ａ1 を対象とした交差点ネットリス
トＣＲＮＬに含まれる全ての隣接交差点につき処理が終
わると、最適経路探索部１５ｇは、交差点Ａ1 以外に第
１次交差点が存在するか判断し（ステップ４０６）、交
差点Ａ2 が存在するので、新たな第１次交差点として
（ステップ４０９）、ステップ４０２以降の処理を繰り
返す。交差点Ａ2 の交差点ネットリストに、出発地交差
点以外に隣接交差点Ｂ21〜Ｂ23が存在しており、Ａ1 の
場合と同様に処理される。Ｂ21の処理において、Ｂ21＝
Ｂ13なので、ステップ４０４において、隣接交差点Ｂ13
の次数が既に２となっているためＹＥＳとなる。これ
は、先に第１次交差点Ａ1 に隣接する交差点Ｂ13として
処理済み（前記（Ａ）〜（Ｃ）のデータが記憶済み）で
あることを示すが、この場合、該隣接交差点Ｂ13に係る
交差点ネットリストＣＲＮＬに登録してある出発地交差
点ＳＴＰからの累計距離Ｄ′＝Ｂｄ13と、今回ステップ
４０３で求めた距離Ｄの大小を比較する（ステップ４１
０）。Ｄ＜Ｄ′であれば、当該隣接交差点Ｂ13（＝
Ｂ21）の交差点ネットリストＣＲＮＬの図２における
（２５）と（２６）の項目に記憶してある、第ｉ次交差
点Ａ 1 の交差点シーケンシャル番号を現在着目している
第ｉ次交差点Ａ2 の交差点シーケンシャル番号で書き換
えるとともに、累計距離Ｄ′をＤ＝Ｂｄ21で書き換え
（ステップ４１１）、以降、ステップ４０２に戻る。ま
た、Ｄ≧Ｄ′の場合は、当該交差点Ｂ13（＝Ｂ21）に係
る交差点ネットリストＣＲＮＬの図２における（２５）
〜（２７）の内容を変更せずステップ４０２に戻る。
トＣＲＮＬに含まれる全ての隣接交差点につき処理が終
わると、最適経路探索部１５ｇは、交差点Ａ1 以外に第
１次交差点が存在するか判断し（ステップ４０６）、交
差点Ａ2 が存在するので、新たな第１次交差点として
（ステップ４０９）、ステップ４０２以降の処理を繰り
返す。交差点Ａ2 の交差点ネットリストに、出発地交差
点以外に隣接交差点Ｂ21〜Ｂ23が存在しており、Ａ1 の
場合と同様に処理される。Ｂ21の処理において、Ｂ21＝
Ｂ13なので、ステップ４０４において、隣接交差点Ｂ13
の次数が既に２となっているためＹＥＳとなる。これ
は、先に第１次交差点Ａ1 に隣接する交差点Ｂ13として
処理済み（前記（Ａ）〜（Ｃ）のデータが記憶済み）で
あることを示すが、この場合、該隣接交差点Ｂ13に係る
交差点ネットリストＣＲＮＬに登録してある出発地交差
点ＳＴＰからの累計距離Ｄ′＝Ｂｄ13と、今回ステップ
４０３で求めた距離Ｄの大小を比較する（ステップ４１
０）。Ｄ＜Ｄ′であれば、当該隣接交差点Ｂ13（＝
Ｂ21）の交差点ネットリストＣＲＮＬの図２における
（２５）と（２６）の項目に記憶してある、第ｉ次交差
点Ａ 1 の交差点シーケンシャル番号を現在着目している
第ｉ次交差点Ａ2 の交差点シーケンシャル番号で書き換
えるとともに、累計距離Ｄ′をＤ＝Ｂｄ21で書き換え
（ステップ４１１）、以降、ステップ４０２に戻る。ま
た、Ｄ≧Ｄ′の場合は、当該交差点Ｂ13（＝Ｂ21）に係
る交差点ネットリストＣＲＮＬの図２における（２５）
〜（２７）の内容を変更せずステップ４０２に戻る。
【００５７】交差点Ａ2 に関して、各隣接交差点に対す
る所定の処理を終えたならば、交差点Ａ3 ，Ａ4 につい
ても同様に処理し、別の第１次交差点が存在しなくなれ
ば、目的地交差点ＤＳＰに到達したかチェックし（ステ
ップ４０７）、まだなので、ｉをインクリメントして２
とする（ステップ４０８）。次いで、ステップ４０２へ
進み、前述と同様の処理を順に繰り返していく。
る所定の処理を終えたならば、交差点Ａ3 ，Ａ4 につい
ても同様に処理し、別の第１次交差点が存在しなくなれ
ば、目的地交差点ＤＳＰに到達したかチェックし（ステ
ップ４０７）、まだなので、ｉをインクリメントして２
とする（ステップ４０８）。次いで、ステップ４０２へ
進み、前述と同様の処理を順に繰り返していく。
【００５８】その後、ステップ４０７のチェックにおい
て、第（ｉ＋１）次とされた交差点の中に目的地交差点
ＤＳＰが含まれていて、ＹＥＳと判断されたとき、目的
地交差点ＤＳＰ、該目的地交差点ＤＳＰ（ｍ次の交差点
とする）に係る交差点ネットリストＣＲＮＬの図２の
（２７）の項目として記憶してある（ｍ−１）次の交差
点、該（ｍ−１）次の交差点に係る交差点ネットリスト
ＣＲＮＬに記憶してある（ｍ−２）次の交差点、・・
・、２次の交差点に係る交差点ネットリストＣＲＮＬに
記憶してある１次交差点、１次交差点に係る交差点ネッ
トリストＣＲＮＬに記憶してある０次交差点＝出発地交
差点ＳＴＰを、出発地側から目的地側に向けた順序で順
次結んで最短経路を決定する（ステップ４１２）。そし
て、求めた最短経路を構成するノード列を誘導経路デー
タとして誘導経路記憶部１５ｊに記憶させて経路探索処
理を終了する（ステップ４１３）。
て、第（ｉ＋１）次とされた交差点の中に目的地交差点
ＤＳＰが含まれていて、ＹＥＳと判断されたとき、目的
地交差点ＤＳＰ、該目的地交差点ＤＳＰ（ｍ次の交差点
とする）に係る交差点ネットリストＣＲＮＬの図２の
（２７）の項目として記憶してある（ｍ−１）次の交差
点、該（ｍ−１）次の交差点に係る交差点ネットリスト
ＣＲＮＬに記憶してある（ｍ−２）次の交差点、・・
・、２次の交差点に係る交差点ネットリストＣＲＮＬに
記憶してある１次交差点、１次交差点に係る交差点ネッ
トリストＣＲＮＬに記憶してある０次交差点＝出発地交
差点ＳＴＰを、出発地側から目的地側に向けた順序で順
次結んで最短経路を決定する（ステップ４１２）。そし
て、求めた最短経路を構成するノード列を誘導経路デー
タとして誘導経路記憶部１５ｊに記憶させて経路探索処
理を終了する（ステップ４１３）。
【００５９】なお、或る１つの経路で目的地ＤＳＰに到
達しても、目的地交差点に係る交差点ネットリストに登
録された累計距離に対し、累計距離の短い経路が存在す
る間は経路探索を継続し、若し、他の経路でも目的地Ｄ
ＳＰに到達したとき、該経路での累計距離の方が、既に
目的地交差点に係る交差点ネットリストに登録されてい
る累計距離より短ければ、書き換えを行い、その後、ど
の経路も目的地交差点に係る交差点ネットリストに登録
された累計距離より長くなったとき、経路探索を終える
ようにしてもよい。また、誘導経路データが交差点（単
純ノードの内、隣接ノードとなっているものを含む）だ
けで構成されていることから、交差点ネットリストや道
路データ中の道路リストＲＤＬＴ、ノードテーブルＮＤ
ＴＢ等を参照して交差点間を単純ノード補間し、詳細な
経路誘導データとしたのち、誘導経路記憶部１５ｊに記
憶させるようにしてもよい。更に、目的地側から出発地
側に向けて経路探索を行い、探索したノード列を逆順で
並べて誘導経路データとしてもよい。
達しても、目的地交差点に係る交差点ネットリストに登
録された累計距離に対し、累計距離の短い経路が存在す
る間は経路探索を継続し、若し、他の経路でも目的地Ｄ
ＳＰに到達したとき、該経路での累計距離の方が、既に
目的地交差点に係る交差点ネットリストに登録されてい
る累計距離より短ければ、書き換えを行い、その後、ど
の経路も目的地交差点に係る交差点ネットリストに登録
された累計距離より長くなったとき、経路探索を終える
ようにしてもよい。また、誘導経路データが交差点（単
純ノードの内、隣接ノードとなっているものを含む）だ
けで構成されていることから、交差点ネットリストや道
路データ中の道路リストＲＤＬＴ、ノードテーブルＮＤ
ＴＢ等を参照して交差点間を単純ノード補間し、詳細な
経路誘導データとしたのち、誘導経路記憶部１５ｊに記
憶させるようにしてもよい。更に、目的地側から出発地
側に向けて経路探索を行い、探索したノード列を逆順で
並べて誘導経路データとしてもよい。
【００６０】経路誘導 このあと、地図表示制御装置１５は、運転者に対し目的
地まで経路誘導画像の表示処理を行う（図７のステップ
５０１）。即ち、地図画像描画部１５ａが車両位置検出
部１３から車両位置データを入力し、図葉管理情報を参
照して、車両位置周辺の９つの４分割図葉に係る地図デ
ータをＣＤ−ＲＯＭ１１からバッファメモリ１５ｂに読
み出すとともに、ビデオＲＡＭ１５ｄに９画面分の地図
画像を描画する。また、誘導経路描画部１５ｃは、地図
画像描画部１５ａから入力したビデオＲＡＭ１５ｄの表
示エリア情報に基づき、誘導経路記憶部１５ｊに記憶さ
れた誘導経路データの中から、ビデオＲＡＭ１５ｄに描
画されたエリアに入る部分を選び出し、ビデオＲＡＭ１
５ｄに誘導経路を所定色で太く強調させて描画する。そ
して、車両の走行で車両位置が変化するに従い、地図画
像描画部１５ａは車両位置検出部１３から入力した車両
位置データに基づき、ビデオＲＡＭ１５ｄから車両位置
を中心とする１画面分の画像を読み出し制御部１５ｅを
して読み出させる。
地まで経路誘導画像の表示処理を行う（図７のステップ
５０１）。即ち、地図画像描画部１５ａが車両位置検出
部１３から車両位置データを入力し、図葉管理情報を参
照して、車両位置周辺の９つの４分割図葉に係る地図デ
ータをＣＤ−ＲＯＭ１１からバッファメモリ１５ｂに読
み出すとともに、ビデオＲＡＭ１５ｄに９画面分の地図
画像を描画する。また、誘導経路描画部１５ｃは、地図
画像描画部１５ａから入力したビデオＲＡＭ１５ｄの表
示エリア情報に基づき、誘導経路記憶部１５ｊに記憶さ
れた誘導経路データの中から、ビデオＲＡＭ１５ｄに描
画されたエリアに入る部分を選び出し、ビデオＲＡＭ１
５ｄに誘導経路を所定色で太く強調させて描画する。そ
して、車両の走行で車両位置が変化するに従い、地図画
像描画部１５ａは車両位置検出部１３から入力した車両
位置データに基づき、ビデオＲＡＭ１５ｄから車両位置
を中心とする１画面分の画像を読み出し制御部１５ｅを
して読み出させる。
【００６１】若し、車両位置の変化でビデオＲＡＭ１５
ｄに描画された地図画像から自車位置を中心とする１画
面分の範囲が外れそうな場合、地図画像描画部１５ａは
ＣＤ−ＲＯＭ１１から自車位置周辺の新たな地図データ
をバッファメモリ１５ｂに読み出しながら、自車位置周
辺の９画面分の地図画像をビデオＲＡＭ１５ｄに描画す
る。一方、車両位置マーク発生部１５ｆは車両位置検出
部１３から入力した車両方位データに基づき、該データ
の示す方向に向けた車両位置マークを発生する。合成部
１５ｋにより、読み出し制御部１５ｅから読み出された
画像の中心に車両位置マークが合成され、ディスプレイ
装置１２へ出力されて強調誘導経路の表示を伴う車両位
置周辺の地図画像が車両位置マークとともに表示され
る。運転者は、画面に表示された誘導経路に沿って走行
することで、容易に目的地に到達することができる。
ｄに描画された地図画像から自車位置を中心とする１画
面分の範囲が外れそうな場合、地図画像描画部１５ａは
ＣＤ−ＲＯＭ１１から自車位置周辺の新たな地図データ
をバッファメモリ１５ｂに読み出しながら、自車位置周
辺の９画面分の地図画像をビデオＲＡＭ１５ｄに描画す
る。一方、車両位置マーク発生部１５ｆは車両位置検出
部１３から入力した車両方位データに基づき、該データ
の示す方向に向けた車両位置マークを発生する。合成部
１５ｋにより、読み出し制御部１５ｅから読み出された
画像の中心に車両位置マークが合成され、ディスプレイ
装置１２へ出力されて強調誘導経路の表示を伴う車両位
置周辺の地図画像が車両位置マークとともに表示され
る。運転者は、画面に表示された誘導経路に沿って走行
することで、容易に目的地に到達することができる。
【００６２】その後、目的地に到達したならば、地図表
示制御装置１５は経路誘導モードを解除して通常案内モ
ードに切り換える（ステップ５０２、５０３）。通常案
内モードでは、通常の地図画像表示処理がなされるが、
具体的には、地図画像描画部１５ａが車両位置検出部１
３から入力する車両位置データに基づき、車両位置を含
む上層図葉の地図データをＣＤ−ＲＯＭ１１からバッフ
ァメモリ１５ｂに読み出し、ビデオＲＡＭ１５ｄに描画
する。地図画像描画部１５ａの読み出し制御を受けて、
読み出し制御部１５ｅはビデオＲＡＭ１５ｄに描画され
た地図画像の内、車両位置を中心とする１画面分の地図
画像を切り出し、合成部１５ｋへ出力する。また、車両
位置マーク発生部１５ｆも所定の車両位置マークを発生
して合成部１５ｋへ出力する。合成部１５ｋは強調誘導
経路を含まない地図画像に車両位置マークを合成し、デ
ィスプレイ装置１２へ出力して、通常の地図画像を車両
位置マークとともに画面に表示させる（図３のステップ
１０３）。なお、休憩などのため車載ナビゲータの電源
がオフされたときは、経路探索メモリ１５ｉ、誘導経路
記憶部１５ｊをバッテリバックアップして、データを電
源オフ中も保持するようにし、次に、電源がオンされた
とき電源オフ直前の状態を再現できるようにしたのち、
所定のパワーオフ処理を行うようにしてある（図８のス
テップ６０１、６０２）。
示制御装置１５は経路誘導モードを解除して通常案内モ
ードに切り換える（ステップ５０２、５０３）。通常案
内モードでは、通常の地図画像表示処理がなされるが、
具体的には、地図画像描画部１５ａが車両位置検出部１
３から入力する車両位置データに基づき、車両位置を含
む上層図葉の地図データをＣＤ−ＲＯＭ１１からバッフ
ァメモリ１５ｂに読み出し、ビデオＲＡＭ１５ｄに描画
する。地図画像描画部１５ａの読み出し制御を受けて、
読み出し制御部１５ｅはビデオＲＡＭ１５ｄに描画され
た地図画像の内、車両位置を中心とする１画面分の地図
画像を切り出し、合成部１５ｋへ出力する。また、車両
位置マーク発生部１５ｆも所定の車両位置マークを発生
して合成部１５ｋへ出力する。合成部１５ｋは強調誘導
経路を含まない地図画像に車両位置マークを合成し、デ
ィスプレイ装置１２へ出力して、通常の地図画像を車両
位置マークとともに画面に表示させる（図３のステップ
１０３）。なお、休憩などのため車載ナビゲータの電源
がオフされたときは、経路探索メモリ１５ｉ、誘導経路
記憶部１５ｊをバッテリバックアップして、データを電
源オフ中も保持するようにし、次に、電源がオンされた
とき電源オフ直前の状態を再現できるようにしたのち、
所定のパワーオフ処理を行うようにしてある（図８のス
テップ６０１、６０２）。
【００６３】この実施例によれば、経路探索を開始する
前に、探索対象範囲が都市部か郊外か判別し、都市部で
あれば、最適経路の探索途中、逐次、第ｉ次交差点から
或る隣接交差点へ向かう経路の方位が出発地から見た目
的地の方位よりθC 以上ずれているかチェックし、ずれ
ている場合、当該経路を枝刈りしてそれより先へ探索が
進まないようにしたので、不要な経路の探索を省くこと
ができ、また、目的地に到達しないまま累計距離がＬ
LMT を越えた場合も、それより先へ探索が進まないの
で、目的地から外れるような経路の探索が省かれる。こ
のようなヒューリスティック探索の結果、都市部におけ
る最適経路の探索を迅速に行うことができる。即ち、ヒ
ューリスティック探索によれば、本来の経路探索対象範
囲（ＢＵ11〜ＢＵ33）の中で、目的地に近づくような経
路に限定して探索が実行される。なお、都市部では、道
路密度が高いので、ヒューリスティック探索をしても、
目的地に到る最適経路が見出せないという事態は起きな
い。一方、探索対象範囲が郊外の場合は、ヒューリステ
ィックでない通常の横型探索を行うので、道路密度が低
く、例え、目的地に至るのに回り込むような道路しかな
くても、本来の経路探索対象範囲（ＢＵ11〜ＢＵ33）の
中を洩れなく探索することで、確実に出発地から目的地
までの最適経路を探索することができる。
前に、探索対象範囲が都市部か郊外か判別し、都市部で
あれば、最適経路の探索途中、逐次、第ｉ次交差点から
或る隣接交差点へ向かう経路の方位が出発地から見た目
的地の方位よりθC 以上ずれているかチェックし、ずれ
ている場合、当該経路を枝刈りしてそれより先へ探索が
進まないようにしたので、不要な経路の探索を省くこと
ができ、また、目的地に到達しないまま累計距離がＬ
LMT を越えた場合も、それより先へ探索が進まないの
で、目的地から外れるような経路の探索が省かれる。こ
のようなヒューリスティック探索の結果、都市部におけ
る最適経路の探索を迅速に行うことができる。即ち、ヒ
ューリスティック探索によれば、本来の経路探索対象範
囲（ＢＵ11〜ＢＵ33）の中で、目的地に近づくような経
路に限定して探索が実行される。なお、都市部では、道
路密度が高いので、ヒューリスティック探索をしても、
目的地に到る最適経路が見出せないという事態は起きな
い。一方、探索対象範囲が郊外の場合は、ヒューリステ
ィックでない通常の横型探索を行うので、道路密度が低
く、例え、目的地に至るのに回り込むような道路しかな
くても、本来の経路探索対象範囲（ＢＵ11〜ＢＵ33）の
中を洩れなく探索することで、確実に出発地から目的地
までの最適経路を探索することができる。
【００６４】なお、上記した実施例では、第ｉ次交差点
から或る隣接交差点に向かう経路の方位θを、当該第ｉ
次交差点の座標と隣接交差点の座標から計算で求め、θ
0 との差の絶対値がθC 以内かチェックすることで、枝
刈りすべきか否か判断するようにしたが、計算等の処理
を簡単化するため、以下の様にしてもよい。即ち、各交
差点ネットリストには、交差点ネットリストの対象交差
点を原点とする経度方向と緯度方向の差分座標系で見た
各隣接交差点の差分座標（Ｘ，Ｙ）も登録しておく（図
１２参照）。そして、図４のステップ２１１では出発地
を基準とする目的地方位θ0 を求める代わりに、出発地
交差点を原点とする差分座標系での目的地交差点の存在
象限を求める。
から或る隣接交差点に向かう経路の方位θを、当該第ｉ
次交差点の座標と隣接交差点の座標から計算で求め、θ
0 との差の絶対値がθC 以内かチェックすることで、枝
刈りすべきか否か判断するようにしたが、計算等の処理
を簡単化するため、以下の様にしてもよい。即ち、各交
差点ネットリストには、交差点ネットリストの対象交差
点を原点とする経度方向と緯度方向の差分座標系で見た
各隣接交差点の差分座標（Ｘ，Ｙ）も登録しておく（図
１２参照）。そして、図４のステップ２１１では出発地
を基準とする目的地方位θ0 を求める代わりに、出発地
交差点を原点とする差分座標系での目的地交差点の存在
象限を求める。
【００６５】ここで、上記した図１２の（１２）等の差
分座標の項目について説明すると、今、道路データで表
現されている道路が図１３（１）の如くなっており、例
えば、交差点ネットリストの作成対象となっている交差
点ＣＰ1 の位置座標（経度，緯度）が（ｘ1 ，ｙ1 ）、
該交差点ＣＰ1 に対する各隣接交差点ＣＰ2 〜ＣＰ4の
位置座標（経度，緯度）が（ｘ2 ，ｙ2 ）〜（ｘ4 ，ｙ
4 ）であれば、各隣接交差点ＣＰ2 〜ＣＰ4 の差分座標
（Ｘ2 ，Ｙ2 ）〜（Ｘ4 ，Ｙ4 ）は、図１３（２）の差
分座標系Ｘ−Ｙに示す如く、 （Ｘ2 ，Ｙ2 ）＝（ｘ2 −ｘ1 ，ｙ2 −ｙ1 ） （Ｘ3 ，Ｙ3 ）＝（ｘ3 −ｘ1 ，ｙ3 −ｙ1 ） （Ｘ4 ，Ｙ4 ）＝（ｘ4 −ｘ1 ，ｙ4 −ｙ1 ） となる。即ち、隣接交差点ＣＰ2 〜ＣＰ4 の差分座標
は、着目している交差点ＣＰ1 から見た各隣接交差点Ｃ
Ｐ2 〜ＣＰ4 の相対的な経度方向（Ｘ方向）と緯度方向
（Ｙ方向）の位置座標である。交差点ネットリストの対
象交差点がＣＰ4 であれば、各隣接交差点ＣＰ1 、ＣＰ
5 、ＣＰ6 の差分座標（Ｘ1 ，Ｙ1 ）、（Ｘ5 ，
Ｙ5 ）、（Ｘ6 ，Ｙ6 ）は、 （Ｘ1 ，Ｙ1 ）＝（ｘ1 −ｘ4 ，ｙ1 −ｙ4 ） （Ｘ5 ，Ｙ5 ）＝（ｘ5 −ｘ4 ，ｙ5 −ｙ4 ） （Ｘ6 ，Ｙ6 ）＝（ｘ6 −ｘ4 ，ｙ6 −ｙ4 ） となる。他の交差点を対象とした交差点ネットリストに
ついても全く同様である。
分座標の項目について説明すると、今、道路データで表
現されている道路が図１３（１）の如くなっており、例
えば、交差点ネットリストの作成対象となっている交差
点ＣＰ1 の位置座標（経度，緯度）が（ｘ1 ，ｙ1 ）、
該交差点ＣＰ1 に対する各隣接交差点ＣＰ2 〜ＣＰ4の
位置座標（経度，緯度）が（ｘ2 ，ｙ2 ）〜（ｘ4 ，ｙ
4 ）であれば、各隣接交差点ＣＰ2 〜ＣＰ4 の差分座標
（Ｘ2 ，Ｙ2 ）〜（Ｘ4 ，Ｙ4 ）は、図１３（２）の差
分座標系Ｘ−Ｙに示す如く、 （Ｘ2 ，Ｙ2 ）＝（ｘ2 −ｘ1 ，ｙ2 −ｙ1 ） （Ｘ3 ，Ｙ3 ）＝（ｘ3 −ｘ1 ，ｙ3 −ｙ1 ） （Ｘ4 ，Ｙ4 ）＝（ｘ4 −ｘ1 ，ｙ4 −ｙ1 ） となる。即ち、隣接交差点ＣＰ2 〜ＣＰ4 の差分座標
は、着目している交差点ＣＰ1 から見た各隣接交差点Ｃ
Ｐ2 〜ＣＰ4 の相対的な経度方向（Ｘ方向）と緯度方向
（Ｙ方向）の位置座標である。交差点ネットリストの対
象交差点がＣＰ4 であれば、各隣接交差点ＣＰ1 、ＣＰ
5 、ＣＰ6 の差分座標（Ｘ1 ，Ｙ1 ）、（Ｘ5 ，
Ｙ5 ）、（Ｘ6 ，Ｙ6 ）は、 （Ｘ1 ，Ｙ1 ）＝（ｘ1 −ｘ4 ，ｙ1 −ｙ4 ） （Ｘ5 ，Ｙ5 ）＝（ｘ5 −ｘ4 ，ｙ5 −ｙ4 ） （Ｘ6 ，Ｙ6 ）＝（ｘ6 −ｘ4 ，ｙ6 −ｙ4 ） となる。他の交差点を対象とした交差点ネットリストに
ついても全く同様である。
【００６６】また、目的地交差点ＤＳＰの存在象限は、
具体的には、出発地交差点の経度，緯度座標を
（ｘSTP ，ｙSTP ）、目的地交差点の経度，緯度座標を
（ｘDSP ，ｙ DSP ）とすると、差分座標系Ｘ−Ｙでの象
限区分は、図１４に示す如く、 Ｘ＞０かつＹ≧０ ・・・第１象限 Ｘ≦０かつＹ＞０ ・・・第２象限 Ｘ＜０かつＹ≦０ ・・・第３象限 Ｘ≧０かつＹ＞０ ・・・第４象限 であるから、 ｘDSP −ｘSTP ＞０かつｙDSP −ｙSTP ≧０ ・・・第１象限 ｘDSP −ｘSTP ≦０かつｙDSP −ｙSTP ＞０ ・・・第２象限 ｘDSP −ｘSTP ＜０かつｙDSP −ｙSTP ≦０ ・・・第３象限 ｘDSP −ｘSTP ≧０かつｙDSP −ｙSTP ＜０ ・・・第４象限 として目的地交差点ＤＳＰの象限が求まる。図１０の場
合、第１象限となる。
具体的には、出発地交差点の経度，緯度座標を
（ｘSTP ，ｙSTP ）、目的地交差点の経度，緯度座標を
（ｘDSP ，ｙ DSP ）とすると、差分座標系Ｘ−Ｙでの象
限区分は、図１４に示す如く、 Ｘ＞０かつＹ≧０ ・・・第１象限 Ｘ≦０かつＹ＞０ ・・・第２象限 Ｘ＜０かつＹ≦０ ・・・第３象限 Ｘ≧０かつＹ＞０ ・・・第４象限 であるから、 ｘDSP −ｘSTP ＞０かつｙDSP −ｙSTP ≧０ ・・・第１象限 ｘDSP −ｘSTP ≦０かつｙDSP −ｙSTP ＞０ ・・・第２象限 ｘDSP −ｘSTP ＜０かつｙDSP −ｙSTP ≦０ ・・・第３象限 ｘDSP −ｘSTP ≧０かつｙDSP −ｙSTP ＜０ ・・・第４象限 として目的地交差点ＤＳＰの象限が求まる。図１０の場
合、第１象限となる。
【００６７】そして、図５のステップ３０３、３０４で
は方位の比較をする代わりに、現在着目している第ｉ次
交差点と該交差点の１つの隣接交差点に対し、第ｉ次交
差点の交差点ネットリストに登録された隣接交差点の差
分座標から、当該第ｉ次交差点を原点とする差分座標系
で見た隣接交差点の存在象限を求め、図４のステップ２
１１の代わりに求めた目的地の存在象限と一致するか判
断し、一致するときは、ステップ３０５以下の処理を行
い、不一致の時はステップ３０２に戻って枝刈りをする
（図１５（１）参照）。例えば、着目している交差点が
出発地交差点、隣接交差点がＡ1 であれば、出発地交差
点を原点とする差分座標系で見た交差点Ａ1 の存在象限
は第４象限であり、目的地の存在象限である第１象限と
は異なるので枝刈りし、隣接交差点がＡ 2 であれば、一
致するので、枝刈りせずステップ３０５以降に進み、累
計距離、１つ手前の交差点シーケンシャル番号、検索次
数の登録を行う。Ａ3 とＡ4 は存在象限が目的地と一致
しないのでステップ３０２に戻ることで枝刈りする。
は方位の比較をする代わりに、現在着目している第ｉ次
交差点と該交差点の１つの隣接交差点に対し、第ｉ次交
差点の交差点ネットリストに登録された隣接交差点の差
分座標から、当該第ｉ次交差点を原点とする差分座標系
で見た隣接交差点の存在象限を求め、図４のステップ２
１１の代わりに求めた目的地の存在象限と一致するか判
断し、一致するときは、ステップ３０５以下の処理を行
い、不一致の時はステップ３０２に戻って枝刈りをする
（図１５（１）参照）。例えば、着目している交差点が
出発地交差点、隣接交差点がＡ1 であれば、出発地交差
点を原点とする差分座標系で見た交差点Ａ1 の存在象限
は第４象限であり、目的地の存在象限である第１象限と
は異なるので枝刈りし、隣接交差点がＡ 2 であれば、一
致するので、枝刈りせずステップ３０５以降に進み、累
計距離、１つ手前の交差点シーケンシャル番号、検索次
数の登録を行う。Ａ3 とＡ4 は存在象限が目的地と一致
しないのでステップ３０２に戻ることで枝刈りする。
【００６８】このように、交差点ネットリストに対象交
差点を原点とする差分座標系で見た各隣接交差点の差分
座標を登録しておき、また、検索開始時に、出発地交差
点を原点とする差分座標系で見た目的地交差点の存在象
限を求めておき、経路探索中、第ｉ次交差点とこれに隣
接する或る隣接交差点を結ぶ経路を枝刈りするか否か判
断する際、着目している第ｉ次交差点の交差点ネットリ
ストの各隣接交差点毎に登録された差分座標を参照し
て、隣接交差点の存在象限が目的地の存在象限と一致す
るか否かで判断することにより、三角関数を用いて方位
計算する手間が省け、一層、早く最適経路の探索を行う
ことができる。なお、この差分座標を利用する場合、図
１５（２）に示す如く、着目している第ｉ次交差点から
見た或る隣接交差点の存在象限が目的地象限（ここでは
第１象限とする）と反対側の第４象限である場合のみ枝
刈りし、隣接する第２象限又は第４象限のときは、枝刈
りせずに、但し、図５のステップ３０５で出発地からの
累計距離を計算する際、着目している第ｉ次交差点と当
該隣接交差点間の距離ｄ 2 については交差点ネットリス
トに登録された距離をｋ（ｋ＞１）倍して重み付けした
のち、第ｉ次交差点の交差点ネットリストに出発地から
第ｉ次交差点までの累計距離として登録された値に加算
するようにして、第ｉ次交差点と当該隣接交差点を結ぶ
経路の優先度を下げるようにすることもできる。
差点を原点とする差分座標系で見た各隣接交差点の差分
座標を登録しておき、また、検索開始時に、出発地交差
点を原点とする差分座標系で見た目的地交差点の存在象
限を求めておき、経路探索中、第ｉ次交差点とこれに隣
接する或る隣接交差点を結ぶ経路を枝刈りするか否か判
断する際、着目している第ｉ次交差点の交差点ネットリ
ストの各隣接交差点毎に登録された差分座標を参照し
て、隣接交差点の存在象限が目的地の存在象限と一致す
るか否かで判断することにより、三角関数を用いて方位
計算する手間が省け、一層、早く最適経路の探索を行う
ことができる。なお、この差分座標を利用する場合、図
１５（２）に示す如く、着目している第ｉ次交差点から
見た或る隣接交差点の存在象限が目的地象限（ここでは
第１象限とする）と反対側の第４象限である場合のみ枝
刈りし、隣接する第２象限又は第４象限のときは、枝刈
りせずに、但し、図５のステップ３０５で出発地からの
累計距離を計算する際、着目している第ｉ次交差点と当
該隣接交差点間の距離ｄ 2 については交差点ネットリス
トに登録された距離をｋ（ｋ＞１）倍して重み付けした
のち、第ｉ次交差点の交差点ネットリストに出発地から
第ｉ次交差点までの累計距離として登録された値に加算
するようにして、第ｉ次交差点と当該隣接交差点を結ぶ
経路の優先度を下げるようにすることもできる。
【００６９】また、上記した実施例では、交差点ネット
リストは、ＣＤ−ＲＯＭに記憶された地図データより、
地図表示制御装置側で作成するようにしたが、予め、作
成したものをＣＤ−ＲＯＭの地図データのデータユニッ
ト内に記憶させておき、必要な交差点ネットリストをＣ
Ｄ−ＲＯＭから読み出して使用するようにしてもよい。
更に、θC は67.5°以外に、45°等の他の値としてよ
い。また、探索は横型探索法に代えてダイクストラ法で
行ってもよい。
リストは、ＣＤ−ＲＯＭに記憶された地図データより、
地図表示制御装置側で作成するようにしたが、予め、作
成したものをＣＤ−ＲＯＭの地図データのデータユニッ
ト内に記憶させておき、必要な交差点ネットリストをＣ
Ｄ−ＲＯＭから読み出して使用するようにしてもよい。
更に、θC は67.5°以外に、45°等の他の値としてよ
い。また、探索は横型探索法に代えてダイクストラ法で
行ってもよい。
【００７０】図１６と図１７は最適経路探索部１５ｇが
ダイクストラ法で最適経路を探索する場合の流れ図、図
１８はダイクストラ法の概略説明図であり、以下、これ
らの図に従って説明する。図１６は図４のステップ２０
９以降、図７のＤまでに対応している。また、交差点ネ
ットリストは図２と同一のものを用いるものとする（但
し、（２７）の検索次数の項目は用いない）。
ダイクストラ法で最適経路を探索する場合の流れ図、図
１８はダイクストラ法の概略説明図であり、以下、これ
らの図に従って説明する。図１６は図４のステップ２０
９以降、図７のＤまでに対応している。また、交差点ネ
ットリストは図２と同一のものを用いるものとする（但
し、（２７）の検索次数の項目は用いない）。
【００７１】経路探索（都市部） ダイクストラ法においては、地域判別部１５ｈが探索対
象範囲を都市部と判別したとき（図４のステップ２０
８、図１６のステップ７０１）、最適経路探索部１５ｇ
はまず出発地交差点ＳＴＰから見た目的地交差点ＤＳＰ
の方位θ0 を計算しておく（ステップ７０２）。次い
で、出発地交差点ＳＴＰを最初の探索枝先端ノードＣＰ
top とし、この際、出発地交差点ＳＴＰに係る交差点ネ
ットリストの累計距離を零としておく（ステップ７０
３、図１８（１）参照）。そして、ＣＰ top （＝ＳＴ
Ｐ）の交差点ネットリストを参照して、該ＣＰtop に隣
接した隣接交差点が残存するか調べる（ステップ７０
４）。ここでは、Ａ1 〜Ａ4 が残存するので、この内１
つ、Ａ4 について、ＣＰtop から見た方位θを計算し
（ステップ７０５）、出発地交差点ＳＴＰから見た目的
地方位θ0 との差の絶対値が一定値θC （ここでは67.5
°とする）以内か、換言すればＣＰtop から隣接交差点
に至る経路の方向が出発地交差点ＳＴＰから見た目的地
交差点ＤＳＰの方面を向いているかチェックする（ステ
ップ７０６）。
象範囲を都市部と判別したとき（図４のステップ２０
８、図１６のステップ７０１）、最適経路探索部１５ｇ
はまず出発地交差点ＳＴＰから見た目的地交差点ＤＳＰ
の方位θ0 を計算しておく（ステップ７０２）。次い
で、出発地交差点ＳＴＰを最初の探索枝先端ノードＣＰ
top とし、この際、出発地交差点ＳＴＰに係る交差点ネ
ットリストの累計距離を零としておく（ステップ７０
３、図１８（１）参照）。そして、ＣＰ top （＝ＳＴ
Ｐ）の交差点ネットリストを参照して、該ＣＰtop に隣
接した隣接交差点が残存するか調べる（ステップ７０
４）。ここでは、Ａ1 〜Ａ4 が残存するので、この内１
つ、Ａ4 について、ＣＰtop から見た方位θを計算し
（ステップ７０５）、出発地交差点ＳＴＰから見た目的
地方位θ0 との差の絶対値が一定値θC （ここでは67.5
°とする）以内か、換言すればＣＰtop から隣接交差点
に至る経路の方向が出発地交差点ＳＴＰから見た目的地
交差点ＤＳＰの方面を向いているかチェックする（ステ
ップ７０６）。
【００７２】ステップ７０６でＹＥＳとなったとき、最
適経路探索部１５ｇは現在のＣＰto p から隣接交差点Ａ
1 への経路は特に目的地方向から外れないので重み付け
係数ｋ＝１とし（ステップ７１３）、ＮＯとなったとき
は、目的地方向から外れるので重み付け係数ｋ＝５とす
る（ステップ７０５）。Ａ4 の場合、ｋ＝５となる（ス
テップ７０７）。そして、出発地交差点ＳＴＰからＣＰ
top までの累計距離ｄ1 と、ＣＰtop から隣接交差点Ａ
4 までの距離ｄ2 とから、出発地交差点から隣接交差点
Ａ4 までの累計距離Ａｄ4 を次式 ｄ1 ＋ｋｄ2 ＝Ａｄ4 で求める（ステップ７０８）。ｄ1 はＣＰtop の交差点
ネットリストに累計距離として登録されているが、ここ
では零である。また、ｄ2 はＣＰtop の交差点ネットリ
ストに隣接交差点Ａ4までの距離として登録されてい
る。次いで、Ａ4 の交差点ネットリストに既に累計距離
Ｄ´が登録済みかチェックし（ステップ７０９）、まだ
なので、隣接交差点Ａ4 の交差点ネットリスト中に、１
つ手前の交差点（現在のＣＰtop ）を特定する交差点シ
ーケンシャル番号とともに登録する（ステップ７１０、
図２の交差点ネットリストの（２５）と（２６））。次
いで、経路探索メモリ１５ｉ中に設けた探索枝先端バッ
ファに今回の隣接交差点Ａ4 を特定する交差点シーケン
シャル番号を登録する（ステップ７１１）。次いで、目
的地に到達したか、換言すれば今回の隣接交差点Ａ4 が
目的地交差点と一致するかチェックする（ステップ７１
２）。
適経路探索部１５ｇは現在のＣＰto p から隣接交差点Ａ
1 への経路は特に目的地方向から外れないので重み付け
係数ｋ＝１とし（ステップ７１３）、ＮＯとなったとき
は、目的地方向から外れるので重み付け係数ｋ＝５とす
る（ステップ７０５）。Ａ4 の場合、ｋ＝５となる（ス
テップ７０７）。そして、出発地交差点ＳＴＰからＣＰ
top までの累計距離ｄ1 と、ＣＰtop から隣接交差点Ａ
4 までの距離ｄ2 とから、出発地交差点から隣接交差点
Ａ4 までの累計距離Ａｄ4 を次式 ｄ1 ＋ｋｄ2 ＝Ａｄ4 で求める（ステップ７０８）。ｄ1 はＣＰtop の交差点
ネットリストに累計距離として登録されているが、ここ
では零である。また、ｄ2 はＣＰtop の交差点ネットリ
ストに隣接交差点Ａ4までの距離として登録されてい
る。次いで、Ａ4 の交差点ネットリストに既に累計距離
Ｄ´が登録済みかチェックし（ステップ７０９）、まだ
なので、隣接交差点Ａ4 の交差点ネットリスト中に、１
つ手前の交差点（現在のＣＰtop ）を特定する交差点シ
ーケンシャル番号とともに登録する（ステップ７１０、
図２の交差点ネットリストの（２５）と（２６））。次
いで、経路探索メモリ１５ｉ中に設けた探索枝先端バッ
ファに今回の隣接交差点Ａ4 を特定する交差点シーケン
シャル番号を登録する（ステップ７１１）。次いで、目
的地に到達したか、換言すれば今回の隣接交差点Ａ4 が
目的地交差点と一致するかチェックする（ステップ７１
２）。
【００７３】まだなのでステップ７０４に戻り、現在の
ＣＰtop に隣接する他の隣接交差点が残存するか調べ、
Ａ1 ，Ａ3 ，Ａ4 が残存するので、この内の１つ、Ａ1
について、ＣＰtop から見た方位θを計算し、θ0 との
差の絶対値がθC 以内かチェックする（ステップ７０
５、７０６）。今度は、ＹＥＳとなるので、ｋ＝１に設
定したのち（ステップ７１３）、出発地交差点ＳＴＰか
らの累計距離Ａｄ1 を、次式 ｄ1 ＋ｋｄ2 ＝Ａｄ1 で求め、Ａ1 の交差点ネットリストにはまだ累計距離が
登録されていないので、交差点Ａ1 に係る交差点ネット
リスト中に、ＣＰtop （１つ手前の交差点）を特定する
交差点シーケンシャル番号とともに登録し、探索枝先端
バッファにＡ1 の交差点シーケンシャル番号を追加登録
する（ステップ７０９〜７１１）。そして、目的地に到
達したかチェックし（ステップ７１２）、まだなのでス
テップ７０４に戻り同様の処理を行う。隣接交差点Ａ2
についてはθとθ0 の差の絶対値がθC 以内なのでｋ＝
１として累計距離Ａｄ2 を求め（ステップ７０５、７０
６、７１３、７０８）、隣接交差点Ａ3 についてはθと
θ0 の差の絶対値がθC を越えているのでｋ＝５として
累計距離Ａｄ2 を求め、それぞれ、Ａ2 とＡ3 に対応す
る交差点ネットリストにＣＰtop を特定する交差点シー
ケンシャル番号とともに登録したのち（ステップ７０
９、７１０）、Ａ2 とＡ3 の交差点シーケンシャル番号
を探索枝先端バッファに追加登録する（ステップ７１
１）。
ＣＰtop に隣接する他の隣接交差点が残存するか調べ、
Ａ1 ，Ａ3 ，Ａ4 が残存するので、この内の１つ、Ａ1
について、ＣＰtop から見た方位θを計算し、θ0 との
差の絶対値がθC 以内かチェックする（ステップ７０
５、７０６）。今度は、ＹＥＳとなるので、ｋ＝１に設
定したのち（ステップ７１３）、出発地交差点ＳＴＰか
らの累計距離Ａｄ1 を、次式 ｄ1 ＋ｋｄ2 ＝Ａｄ1 で求め、Ａ1 の交差点ネットリストにはまだ累計距離が
登録されていないので、交差点Ａ1 に係る交差点ネット
リスト中に、ＣＰtop （１つ手前の交差点）を特定する
交差点シーケンシャル番号とともに登録し、探索枝先端
バッファにＡ1 の交差点シーケンシャル番号を追加登録
する（ステップ７０９〜７１１）。そして、目的地に到
達したかチェックし（ステップ７１２）、まだなのでス
テップ７０４に戻り同様の処理を行う。隣接交差点Ａ2
についてはθとθ0 の差の絶対値がθC 以内なのでｋ＝
１として累計距離Ａｄ2 を求め（ステップ７０５、７０
６、７１３、７０８）、隣接交差点Ａ3 についてはθと
θ0 の差の絶対値がθC を越えているのでｋ＝５として
累計距離Ａｄ2 を求め、それぞれ、Ａ2 とＡ3 に対応す
る交差点ネットリストにＣＰtop を特定する交差点シー
ケンシャル番号とともに登録したのち（ステップ７０
９、７１０）、Ａ2 とＡ3 の交差点シーケンシャル番号
を探索枝先端バッファに追加登録する（ステップ７１
１）。
【００７４】このようにして、今回のＣＰtop ＝ＳＴＰ
につき残存する隣接交差点が無くなったなら、次に、探
索枝先端バッファに登録された交差点の中で、それまで
にＣＰtop とされたものを除いて、累計距離が最小とな
っているものを探し、これを新たなＣＰtop とする（ス
テップ７０４、７１４、図１８（２）の実線参照）。探
索枝先端バッファには、Ａ1 〜Ａ4 が登録されている
が、Ａｄ3 とＡｄ4 はｋ＝５とされたので値が大きく優
先度が下がり、Ａｄ1 とＡｄ2 はｋ＝１とされたので値
が小さく優先度が上がる。このうち、Ａｄ1 が最小であ
ったならば、ＣＰ top ＝Ａ1 となる。この場合、Ａ1 の
交差点ネットリストを参照してＡ1 に隣接した隣接交差
点の内の１つ、Ｂ14について、更新後のＣＰtop から見
た方位θを計算し、出発地交差点ＳＴＰから見た目的地
方位θ0 との差の絶対値が一定値θC 以内かチェックす
る（ステップ７０４〜７０６）。ここではＮＯなのでｋ
＝５とする（ステップ７０７）。そして、出発地交差点
ＳＴＰからＣＰtop までの累計距離ｄ1 と、ＣＰtop か
ら隣接交差点Ｂ14までの距離ｄ2 とから、出発地交差点
から隣接交差点Ｂ14までの累計距離Ｂｄ14を次式 ｄ1 ＋ｋｄ2 ＝Ｂｄ14 で求める（ステップ７０８）。ｄ1 はＣＰtop の交差点
ネットリストに累計距離として登録されており、ｄ2は
ＣＰtop の交差点ネットリストに隣接交差点Ｂ14までの
距離として登録されている。
につき残存する隣接交差点が無くなったなら、次に、探
索枝先端バッファに登録された交差点の中で、それまで
にＣＰtop とされたものを除いて、累計距離が最小とな
っているものを探し、これを新たなＣＰtop とする（ス
テップ７０４、７１４、図１８（２）の実線参照）。探
索枝先端バッファには、Ａ1 〜Ａ4 が登録されている
が、Ａｄ3 とＡｄ4 はｋ＝５とされたので値が大きく優
先度が下がり、Ａｄ1 とＡｄ2 はｋ＝１とされたので値
が小さく優先度が上がる。このうち、Ａｄ1 が最小であ
ったならば、ＣＰ top ＝Ａ1 となる。この場合、Ａ1 の
交差点ネットリストを参照してＡ1 に隣接した隣接交差
点の内の１つ、Ｂ14について、更新後のＣＰtop から見
た方位θを計算し、出発地交差点ＳＴＰから見た目的地
方位θ0 との差の絶対値が一定値θC 以内かチェックす
る（ステップ７０４〜７０６）。ここではＮＯなのでｋ
＝５とする（ステップ７０７）。そして、出発地交差点
ＳＴＰからＣＰtop までの累計距離ｄ1 と、ＣＰtop か
ら隣接交差点Ｂ14までの距離ｄ2 とから、出発地交差点
から隣接交差点Ｂ14までの累計距離Ｂｄ14を次式 ｄ1 ＋ｋｄ2 ＝Ｂｄ14 で求める（ステップ７０８）。ｄ1 はＣＰtop の交差点
ネットリストに累計距離として登録されており、ｄ2は
ＣＰtop の交差点ネットリストに隣接交差点Ｂ14までの
距離として登録されている。
【００７５】そして、Ｂ14の交差点ネットリストに既に
累計距離Ｄ´が登録済みかチェックし（ステップ７０
９）、まだなので、Ｂ14に係る交差点ネットリスト中
に、１つ手前の交差点（現在のＣＰtop ＝Ａ1 ）を特定
する交差点シーケンシャル番号とともに登録する（ステ
ップ７１０、図２の交差点ネットリストの（２５）と
（２６））。次いで、探索枝先端バッファに今回の隣接
交差点Ｂ14を特定する交差点シーケンシャル番号を登録
する（ステップ７１１）。次に、目的地に到達したかチ
ェックし（ステップ７１２）、まだであればステップ７
０４に戻り、現在のＣＰtop に隣接する他の隣接交差点
が残存するか調べ、まだ、Ｂ11〜Ｂ13が残存するので、
この内の１つＢ11について、ＣＰtop から見た方位θを
計算し、出発地交差点ＳＴＰから見た目的地方位θ0 と
の差の絶対値がθC 以内かチェックする（ステップ７０
５、７０６）。今度は、ＹＥＳとなるので、ｋ＝１に設
定したのち（ステップ７１３）、出発地交差点ＳＴＰか
ら交差点Ａ1 を経由して交差点Ｂ11に至るまでの累計距
離Ｂｄ11を求め、Ｂ11の交差点ネットリストにはまだ累
計距離が登録されていないので、交差点Ｂ11に係る交差
点ネットリスト中に、ＣＰtop の交差点シーケンシャル
番号とともに登録し、探索枝先端バッファにＢ11の交差
点シーケンシャル番号を追加登録する（ステップ７０８
〜７１１）。そして、目的地に到達したかチェックし
（ステップ７１２）、まだであればステップ７０４に戻
り同様の処理を行う。同様にして、隣接交差点Ｂ12につ
いてはθとθ0 の差の絶対値がθC 以内なのでｋ＝１と
して累計距離Ｂｄ12を求め、Ｂ12に対応する交差点ネッ
トリストにＣＰtop を特定する交差点シーケンシャル番
号とともに登録したのち（ステップ７０５、７０６、７
１３、７０８〜７１０）、Ｂ12を特定する交差点シーケ
ンシャル番号を探索枝先端バッファに追加登録する（ス
テップ７１１）。
累計距離Ｄ´が登録済みかチェックし（ステップ７０
９）、まだなので、Ｂ14に係る交差点ネットリスト中
に、１つ手前の交差点（現在のＣＰtop ＝Ａ1 ）を特定
する交差点シーケンシャル番号とともに登録する（ステ
ップ７１０、図２の交差点ネットリストの（２５）と
（２６））。次いで、探索枝先端バッファに今回の隣接
交差点Ｂ14を特定する交差点シーケンシャル番号を登録
する（ステップ７１１）。次に、目的地に到達したかチ
ェックし（ステップ７１２）、まだであればステップ７
０４に戻り、現在のＣＰtop に隣接する他の隣接交差点
が残存するか調べ、まだ、Ｂ11〜Ｂ13が残存するので、
この内の１つＢ11について、ＣＰtop から見た方位θを
計算し、出発地交差点ＳＴＰから見た目的地方位θ0 と
の差の絶対値がθC 以内かチェックする（ステップ７０
５、７０６）。今度は、ＹＥＳとなるので、ｋ＝１に設
定したのち（ステップ７１３）、出発地交差点ＳＴＰか
ら交差点Ａ1 を経由して交差点Ｂ11に至るまでの累計距
離Ｂｄ11を求め、Ｂ11の交差点ネットリストにはまだ累
計距離が登録されていないので、交差点Ｂ11に係る交差
点ネットリスト中に、ＣＰtop の交差点シーケンシャル
番号とともに登録し、探索枝先端バッファにＢ11の交差
点シーケンシャル番号を追加登録する（ステップ７０８
〜７１１）。そして、目的地に到達したかチェックし
（ステップ７１２）、まだであればステップ７０４に戻
り同様の処理を行う。同様にして、隣接交差点Ｂ12につ
いてはθとθ0 の差の絶対値がθC 以内なのでｋ＝１と
して累計距離Ｂｄ12を求め、Ｂ12に対応する交差点ネッ
トリストにＣＰtop を特定する交差点シーケンシャル番
号とともに登録したのち（ステップ７０５、７０６、７
１３、７０８〜７１０）、Ｂ12を特定する交差点シーケ
ンシャル番号を探索枝先端バッファに追加登録する（ス
テップ７１１）。
【００７６】隣接交差点Ｂ13についてはθとθ0 の差の
絶対値がθC を越えているのでｋ＝５として累計距離Ｄ
＝Ｂｄ13を求める。ＳＴＰ−Ａ2 間の累計距離ｄ1 は既
に交差点Ａ1 の交差点ネットリストに累計距離Ａｄ1 と
して登録されており（図２の交差点ネットリストの（２
６））、Ａ1 −Ｂ13間の距離ｄ2 は交差点ネットリスト
に当該交差点Ａ1 から隣接交差点Ｂ13までの距離として
登録されているので、 ｄ1 ＋ｋｄ2 ＝Ｂｄ13 として累計距離Ｂｄ13が求まる。但し、交差点Ｂ13は、
出発地交差点ＳＴＰと同一であり、該出発地交差点ＳＴ
Ｐの交差点ネットリストには既に累計距離＝零が登録さ
れており、かつ、Ｂｄ13より必ず小さいことから、ステ
ップ７１５でＮＯとなる。このとき、Ｂ13に関しては交
差点ネットリストへの累計距離、交差点シーケンシャル
番号の登録はせず、また、探索枝先端バッファへの登録
もしない。これにより、それまでにＣＰto p とされた交
差点における交差点ネットリストの累計距離等は書き換
えられないことになる。
絶対値がθC を越えているのでｋ＝５として累計距離Ｄ
＝Ｂｄ13を求める。ＳＴＰ−Ａ2 間の累計距離ｄ1 は既
に交差点Ａ1 の交差点ネットリストに累計距離Ａｄ1 と
して登録されており（図２の交差点ネットリストの（２
６））、Ａ1 −Ｂ13間の距離ｄ2 は交差点ネットリスト
に当該交差点Ａ1 から隣接交差点Ｂ13までの距離として
登録されているので、 ｄ1 ＋ｋｄ2 ＝Ｂｄ13 として累計距離Ｂｄ13が求まる。但し、交差点Ｂ13は、
出発地交差点ＳＴＰと同一であり、該出発地交差点ＳＴ
Ｐの交差点ネットリストには既に累計距離＝零が登録さ
れており、かつ、Ｂｄ13より必ず小さいことから、ステ
ップ７１５でＮＯとなる。このとき、Ｂ13に関しては交
差点ネットリストへの累計距離、交差点シーケンシャル
番号の登録はせず、また、探索枝先端バッファへの登録
もしない。これにより、それまでにＣＰto p とされた交
差点における交差点ネットリストの累計距離等は書き換
えられないことになる。
【００７７】このようにして、今回のＣＰtop ＝Ａ1 に
ついて処理し終えたならば（ステップ７０４でＮＯ）、
探索枝先端バッファに登録された交差点の中で、それま
でにＣＰtop とされたものを除いて、累計距離が最小と
なっているものを探し、これを新たなＣＰtop とする
（ステップ７１４、図１８（２）破線参照）。探索枝先
端バッファには、Ａ1 〜Ａ4 、Ｂ11，Ｂ12，Ｂ14が登録
されているが、Ａ1 は除外される。また、Ａｄ4 ，Ａｄ
3 ，Ｂｄ11は大きく、Ａｄ2 ，Ｂｄ11，Ｂｄ12の中で、
Ａｄ2 が最小であったならば、ＣＰtop ＝Ａ2 となる。
この場合、Ａ2 に隣接する交差点の内の１つ、Ｂ24につ
いては出発地交差点ＳＴＰと同一であり、Ｂ24に関して
交差点ネットリストへの累計距離、交差点シーケンシャ
ル番号の登録はされず、また、探索枝先端バッファへの
登録もされない（ステップ７０４〜７０９、７１５でＮ
Ｏ）。
ついて処理し終えたならば（ステップ７０４でＮＯ）、
探索枝先端バッファに登録された交差点の中で、それま
でにＣＰtop とされたものを除いて、累計距離が最小と
なっているものを探し、これを新たなＣＰtop とする
（ステップ７１４、図１８（２）破線参照）。探索枝先
端バッファには、Ａ1 〜Ａ4 、Ｂ11，Ｂ12，Ｂ14が登録
されているが、Ａ1 は除外される。また、Ａｄ4 ，Ａｄ
3 ，Ｂｄ11は大きく、Ａｄ2 ，Ｂｄ11，Ｂｄ12の中で、
Ａｄ2 が最小であったならば、ＣＰtop ＝Ａ2 となる。
この場合、Ａ2 に隣接する交差点の内の１つ、Ｂ24につ
いては出発地交差点ＳＴＰと同一であり、Ｂ24に関して
交差点ネットリストへの累計距離、交差点シーケンシャ
ル番号の登録はされず、また、探索枝先端バッファへの
登録もされない（ステップ７０４〜７０９、７１５でＮ
Ｏ）。
【００７８】まだ、ＣＰtop ＝Ａ2 について他の隣接交
差点Ｂ21〜Ｂ23が残存しているので（ステップ７０４て
ＹＥＳ）、この内１つＢ21について、θとθ0 の差の絶
対値がθC 以内かチェックし（ステップ７０５、７０
６）、ＹＥＳなので、ｋ＝１として（ステップ７１
３）、出発地交差点ＳＴＰから交差点Ａ2 を経由してＢ
21までの累計距離Ｄ＝Ｂｄ21を求める（ステップ７０
８）。次いで、交差点Ｂ21の交差点ネットリストに既に
累計距離Ｄ´が登録済みかチェックし（ステップ７１
５）、ここではＢｄ13が登録済みなので、今回求めた累
計距離Ｄ＝Ｂｄ21と大小比較をし、Ｄの方が小さけれ
ば、Ｂ13（＝Ｂ21）の交差点ネットリストに累計距離Ｂ
ｄ21とＡ2 の交差点シーケンシャル番号を書き換え登録
し、探索枝先端バッファにＢ21の交差点シーケンシャル
番号を追加登録する。若し、Ｂｄ21の方が大きい場合
は、Ｂｄ21とＡ2 の書き換え登録はせず、探索枝先端バ
ッファへのＢ21の追加もせず、ステップ７０４に戻る。
差点Ｂ21〜Ｂ23が残存しているので（ステップ７０４て
ＹＥＳ）、この内１つＢ21について、θとθ0 の差の絶
対値がθC 以内かチェックし（ステップ７０５、７０
６）、ＹＥＳなので、ｋ＝１として（ステップ７１
３）、出発地交差点ＳＴＰから交差点Ａ2 を経由してＢ
21までの累計距離Ｄ＝Ｂｄ21を求める（ステップ７０
８）。次いで、交差点Ｂ21の交差点ネットリストに既に
累計距離Ｄ´が登録済みかチェックし（ステップ７１
５）、ここではＢｄ13が登録済みなので、今回求めた累
計距離Ｄ＝Ｂｄ21と大小比較をし、Ｄの方が小さけれ
ば、Ｂ13（＝Ｂ21）の交差点ネットリストに累計距離Ｂ
ｄ21とＡ2 の交差点シーケンシャル番号を書き換え登録
し、探索枝先端バッファにＢ21の交差点シーケンシャル
番号を追加登録する。若し、Ｂｄ21の方が大きい場合
は、Ｂｄ21とＡ2 の書き換え登録はせず、探索枝先端バ
ッファへのＢ21の追加もせず、ステップ７０４に戻る。
【００７９】ＣＰtop に隣接する残りの隣接交差点の
内、Ｂ22については、θとθ0 の差の絶対値がθC 以内
なので、ｋ＝１として累計距離Ｂｄ22を求め、かつ、Ｂ
22の交差点ネットリストにはまだ累計距離が登録されて
いないので、Ｂｄ22をＣＰtop＝Ａ2 の交差点シーケン
シャル番号とともに登録し、探索枝先端バッファへＢ22
を追加登録する。Ｂ23については、θとθ0 の差の絶対
値がθC 以内なので、ｋ＝５として累計距離Ｂｄ23を求
め、かつ、Ｂ23の交差点ネットリストにはまだ累計距離
が登録されていないので、Ｂｄ23をＣＰtop ＝Ａ2 の交
差点シーケンシャル番号とともに登録し、探索枝先端バ
ッファへＢ23を追加登録する。以下、同様の処理を繰り
返していく。
内、Ｂ22については、θとθ0 の差の絶対値がθC 以内
なので、ｋ＝１として累計距離Ｂｄ22を求め、かつ、Ｂ
22の交差点ネットリストにはまだ累計距離が登録されて
いないので、Ｂｄ22をＣＰtop＝Ａ2 の交差点シーケン
シャル番号とともに登録し、探索枝先端バッファへＢ22
を追加登録する。Ｂ23については、θとθ0 の差の絶対
値がθC 以内なので、ｋ＝５として累計距離Ｂｄ23を求
め、かつ、Ｂ23の交差点ネットリストにはまだ累計距離
が登録されていないので、Ｂｄ23をＣＰtop ＝Ａ2 の交
差点シーケンシャル番号とともに登録し、探索枝先端バ
ッファへＢ23を追加登録する。以下、同様の処理を繰り
返していく。
【００８０】この結果、ＣＰtop から或る隣接交差点へ
向かう経路の方向が出発地から見た目的地の方向よりθ
C 以上ずれている場合、当該経路は探索の優先度が下が
り、それより先への探索が後回しとなるので、出発地と
目的地を結ぶ直線の周辺に存在する経路につき優先的に
探索が実行する。即ち、ヒューリスティック探索によれ
ば、本来の経路探索対象範囲であるＢＵ11〜ＢＵ33の中
で、更に、狭い範囲で目的地に向けた探索が進行する。
向かう経路の方向が出発地から見た目的地の方向よりθ
C 以上ずれている場合、当該経路は探索の優先度が下が
り、それより先への探索が後回しとなるので、出発地と
目的地を結ぶ直線の周辺に存在する経路につき優先的に
探索が実行する。即ち、ヒューリスティック探索によれ
ば、本来の経路探索対象範囲であるＢＵ11〜ＢＵ33の中
で、更に、狭い範囲で目的地に向けた探索が進行する。
【００８１】その後、探索枝の先端が目的地に到達する
と、ステップ７１２でＹＥＳとなり、このとき、ＣＰ
top は、常に、累計距離の最小距離のものが選択されて
いるので、目的地交差点ＤＳＰ（ｍ次の交差点とす
る）、該ＤＳＰの交差点ネットリストに累計距離ととも
に記憶してある交差点シーケンシャル番号（図２の交差
点ネットリストの（２５））の示す（ｍ−１）次交差
点、該（ｍ−１）次の交差点の交差点ネットリストに記
憶してある（ｍ−２）次の交差点、・・・、２次の交差
点の交差点ネットリストに記憶してある１次交差点、該
１次交差点に対応させて交差点ネットリストに記憶して
ある０次の交差点（出発地交差点ＳＴＰ）を、順次、０
次の出発地側から目的地側に向けた順序で結んでなる経
路を最短の最適経路と決定し、該最適経路を構成するノ
ード列を誘導経路記憶部１５ｊに記憶し経路探索を終え
る（ステップ７１７、７１８）。
と、ステップ７１２でＹＥＳとなり、このとき、ＣＰ
top は、常に、累計距離の最小距離のものが選択されて
いるので、目的地交差点ＤＳＰ（ｍ次の交差点とす
る）、該ＤＳＰの交差点ネットリストに累計距離ととも
に記憶してある交差点シーケンシャル番号（図２の交差
点ネットリストの（２５））の示す（ｍ−１）次交差
点、該（ｍ−１）次の交差点の交差点ネットリストに記
憶してある（ｍ−２）次の交差点、・・・、２次の交差
点の交差点ネットリストに記憶してある１次交差点、該
１次交差点に対応させて交差点ネットリストに記憶して
ある０次の交差点（出発地交差点ＳＴＰ）を、順次、０
次の出発地側から目的地側に向けた順序で結んでなる経
路を最短の最適経路と決定し、該最適経路を構成するノ
ード列を誘導経路記憶部１５ｊに記憶し経路探索を終え
る（ステップ７１７、７１８）。
【００８２】経路探索（郊外） これと異なり、地域判別部１５ｈが最適経路の探索対象
範囲を都市部と判別したとき（図４のステップ２０８、
図１６のステップ７０１）、最適経路探索部１５ｇは、
まず、出発地交差点ＳＴＰを最初の探索枝先端ノードＣ
Ｐtop とし、この際、出発地交差点ＳＴＰに係る交差点
ネットリストの累計距離を零とする（図１７のステップ
８０１、図２４（１）参照）。そして、ＣＰtop （＝Ｓ
ＴＰ）の交差点ネットリストを参照して、該ＣＰtop に
隣接した隣接交差点が残存するか調べる（ステップ８０
２）。Ａ1 〜Ａ4 が残存するので、この内の１つＡ4 に
ついて、出発地交差点ＳＴＰからＣＰtop までの累計距
離ｄ1 と、ＣＰtop から隣接交差点Ａ4 までの距離ｄ2
とから、出発地交差点から隣接交差点Ａ4 までの累計距
離Ａｄ4 を次式 ｄ1 ＋ｄ2 ＝Ａｄ4 で求める（ステップ８０３）。ｄ1 はＣＰtop の交差点
ネットリストに累計距離として登録されているが、最初
はＣＰtop ＝ＳＴＰなので零である。また、ｄ2 はＣＰ
top の交差点ネットリストに隣接交差点Ａ4 までの距離
として登録されている。
範囲を都市部と判別したとき（図４のステップ２０８、
図１６のステップ７０１）、最適経路探索部１５ｇは、
まず、出発地交差点ＳＴＰを最初の探索枝先端ノードＣ
Ｐtop とし、この際、出発地交差点ＳＴＰに係る交差点
ネットリストの累計距離を零とする（図１７のステップ
８０１、図２４（１）参照）。そして、ＣＰtop （＝Ｓ
ＴＰ）の交差点ネットリストを参照して、該ＣＰtop に
隣接した隣接交差点が残存するか調べる（ステップ８０
２）。Ａ1 〜Ａ4 が残存するので、この内の１つＡ4 に
ついて、出発地交差点ＳＴＰからＣＰtop までの累計距
離ｄ1 と、ＣＰtop から隣接交差点Ａ4 までの距離ｄ2
とから、出発地交差点から隣接交差点Ａ4 までの累計距
離Ａｄ4 を次式 ｄ1 ＋ｄ2 ＝Ａｄ4 で求める（ステップ８０３）。ｄ1 はＣＰtop の交差点
ネットリストに累計距離として登録されているが、最初
はＣＰtop ＝ＳＴＰなので零である。また、ｄ2 はＣＰ
top の交差点ネットリストに隣接交差点Ａ4 までの距離
として登録されている。
【００８３】そして、Ａ4 の交差点ネットリストに既に
累計距離Ｄ´が登録済みかチェックし（ステップ８０
４）、まだなので、隣接交差点Ａ4 に係る交差点ネット
リスト中に、１つ手前の交差点（現在のＣＰtop ＝ＳＴ
Ｐ）を特定する交差点シーケンシャル番号とともに累計
距離Ａｄ4 を登録する（ステップ８０５、図２の交差点
ネットリストの（２５）と（２６））。次いで、経路探
索メモリ１５ｉ中に設けた探索枝先端バッファに今回の
隣接交差点Ａ4 を特定する交差点シーケンシャル番号を
登録する（ステップ８０６）。次いで、目的地に到達し
たかチェックする（ステップ８０７）。
累計距離Ｄ´が登録済みかチェックし（ステップ８０
４）、まだなので、隣接交差点Ａ4 に係る交差点ネット
リスト中に、１つ手前の交差点（現在のＣＰtop ＝ＳＴ
Ｐ）を特定する交差点シーケンシャル番号とともに累計
距離Ａｄ4 を登録する（ステップ８０５、図２の交差点
ネットリストの（２５）と（２６））。次いで、経路探
索メモリ１５ｉ中に設けた探索枝先端バッファに今回の
隣接交差点Ａ4 を特定する交差点シーケンシャル番号を
登録する（ステップ８０６）。次いで、目的地に到達し
たかチェックする（ステップ８０７）。
【００８４】まだなのでステップ８０２に戻り、現在の
ＣＰtop に隣接する他の隣接交差点が残存するか調べ、
Ａ1 〜Ａ3 が残存するので、この内、１つＡ1 につい
て、出発地交差点ＳＴＰからの累計距離Ａｄ1 を求め、
Ａ1 の交差点ネットリストにはまだ累計距離が登録され
ていないので、交差点Ａ1 に係る交差点ネットリスト中
に、１つ手前の交差点を特定する交差点シーケンシャル
番号とともに登録し、探索枝先端バッファにＡ1 の交差
点シーケンシャル番号を追加登録する（ステップ８０３
〜８０６）。そして、目的地に到達したかチェックし
（ステップ８０７）、まだなのでステップ８０２に戻
り、Ａ2 とＡ3 についても同様の処理を行う。
ＣＰtop に隣接する他の隣接交差点が残存するか調べ、
Ａ1 〜Ａ3 が残存するので、この内、１つＡ1 につい
て、出発地交差点ＳＴＰからの累計距離Ａｄ1 を求め、
Ａ1 の交差点ネットリストにはまだ累計距離が登録され
ていないので、交差点Ａ1 に係る交差点ネットリスト中
に、１つ手前の交差点を特定する交差点シーケンシャル
番号とともに登録し、探索枝先端バッファにＡ1 の交差
点シーケンシャル番号を追加登録する（ステップ８０３
〜８０６）。そして、目的地に到達したかチェックし
（ステップ８０７）、まだなのでステップ８０２に戻
り、Ａ2 とＡ3 についても同様の処理を行う。
【００８５】このようにして、今回のＣＰtop ＝ＳＴＰ
につき残存する隣接交差点が無くなったなら（ステップ
８０２）、次に、探索枝先端バッファに登録された交差
点の中で、それまでにＣＰtop とされたものを除いて、
累計距離が最小となっているものを探し、これを新たな
ＣＰtop とする（ステップ８０８）。探索枝先端バッフ
ァには、Ａ1 〜Ａ4 が登録されており、このうち、Ａｄ
1 が最小であったならば、ＣＰtop ＝Ａ1 となる（図２
４（２）の実線参照）。この場合、Ａ1 の交差点ネット
リストを参照してＡ1 に隣接した隣接交差点の内の１
つ、Ｂ14について、出発地交差点ＳＴＰからＣＰtop ま
での累計距離ｄ1と、ＣＰtop から隣接交差点Ｂ14まで
の距離ｄ2 とから、出発地交差点から隣接交差点Ｂ14ま
での累計距離Ｂｄ14を次式 ｄ1 ＋ｄ2 ＝Ｂｄ14 で求める（ステップ８０３）。ｄ1 はＣＰtop の交差点
ネットリストに累計距離として登録されており、ｄ2は
ＣＰtop の交差点ネットリストに隣接交差点Ｂ14までの
距離として登録されている。
につき残存する隣接交差点が無くなったなら（ステップ
８０２）、次に、探索枝先端バッファに登録された交差
点の中で、それまでにＣＰtop とされたものを除いて、
累計距離が最小となっているものを探し、これを新たな
ＣＰtop とする（ステップ８０８）。探索枝先端バッフ
ァには、Ａ1 〜Ａ4 が登録されており、このうち、Ａｄ
1 が最小であったならば、ＣＰtop ＝Ａ1 となる（図２
４（２）の実線参照）。この場合、Ａ1 の交差点ネット
リストを参照してＡ1 に隣接した隣接交差点の内の１
つ、Ｂ14について、出発地交差点ＳＴＰからＣＰtop ま
での累計距離ｄ1と、ＣＰtop から隣接交差点Ｂ14まで
の距離ｄ2 とから、出発地交差点から隣接交差点Ｂ14ま
での累計距離Ｂｄ14を次式 ｄ1 ＋ｄ2 ＝Ｂｄ14 で求める（ステップ８０３）。ｄ1 はＣＰtop の交差点
ネットリストに累計距離として登録されており、ｄ2は
ＣＰtop の交差点ネットリストに隣接交差点Ｂ14までの
距離として登録されている。
【００８６】そして、Ｂ14の交差点ネットリストに既に
累計距離Ｄ´が登録済みかチェックし（ステップ８０
４）、まだなので、Ｂ14に係る交差点ネットリスト中
に、１つ手前の交差点（現在のＣＰtop ＝Ａ1 ）を特定
する交差点シーケンシャル番号とともに登録する（ステ
ップ８０５、図２の交差点ネットリストの（２５）と
（２６））。次いで、探索枝先端バッファに今回の隣接
交差点Ｂ14を特定する交差点シーケンシャル番号を登録
する（ステップ８０６）。次に、目的地に到達したかチ
ェックし（ステップ８０７）、まだであればステップ８
０２に戻り、現在のＣＰtop に隣接する他の隣接交差点
が残存するか調べ、まだ、Ｂ11〜Ｂ13が残存するので、
この内、１つＢ11について、出発地交差点ＳＴＰから交
差点Ａ1 を経由して交差点Ｂ11に至るまでの累計距離Ｂ
ｄ11を求め、Ｂ11の交差点ネットリストにはまだ累計距
離が登録されていないので、交差点Ｂ11に係る交差点ネ
ットリスト中に、１つ手前の交差点を特定する交差点シ
ーケンシャル番号とともに登録し、探索枝先端バッファ
にＢ11の交差点シーケンシャル番号を追加登録する（ス
テップ８０３〜８０６）。そして、目的地に到達したか
チェックし（ステップ８０７）、まだであればステップ
８０２に戻り同様の処理を行う。同様にして、隣接交差
点Ｂ12について累計距離Ｂｄ12を求め、Ｂ12に対応する
交差点ネットリストにＡ1 の交差点シーケンシャル番号
とともに登録したのち（ステップ８０３〜８０５）、Ｂ
12の交差点シーケンシャル番号を探索枝先端バッファに
追加登録する（ステップ８０６）。
累計距離Ｄ´が登録済みかチェックし（ステップ８０
４）、まだなので、Ｂ14に係る交差点ネットリスト中
に、１つ手前の交差点（現在のＣＰtop ＝Ａ1 ）を特定
する交差点シーケンシャル番号とともに登録する（ステ
ップ８０５、図２の交差点ネットリストの（２５）と
（２６））。次いで、探索枝先端バッファに今回の隣接
交差点Ｂ14を特定する交差点シーケンシャル番号を登録
する（ステップ８０６）。次に、目的地に到達したかチ
ェックし（ステップ８０７）、まだであればステップ８
０２に戻り、現在のＣＰtop に隣接する他の隣接交差点
が残存するか調べ、まだ、Ｂ11〜Ｂ13が残存するので、
この内、１つＢ11について、出発地交差点ＳＴＰから交
差点Ａ1 を経由して交差点Ｂ11に至るまでの累計距離Ｂ
ｄ11を求め、Ｂ11の交差点ネットリストにはまだ累計距
離が登録されていないので、交差点Ｂ11に係る交差点ネ
ットリスト中に、１つ手前の交差点を特定する交差点シ
ーケンシャル番号とともに登録し、探索枝先端バッファ
にＢ11の交差点シーケンシャル番号を追加登録する（ス
テップ８０３〜８０６）。そして、目的地に到達したか
チェックし（ステップ８０７）、まだであればステップ
８０２に戻り同様の処理を行う。同様にして、隣接交差
点Ｂ12について累計距離Ｂｄ12を求め、Ｂ12に対応する
交差点ネットリストにＡ1 の交差点シーケンシャル番号
とともに登録したのち（ステップ８０３〜８０５）、Ｂ
12の交差点シーケンシャル番号を探索枝先端バッファに
追加登録する（ステップ８０６）。
【００８７】隣接交差点Ｂ13については出発地交差点Ｓ
ＴＰと同一であり、該出発地交差点ＳＴＰの交差点ネッ
トリストには既に累計距離＝零が登録されており、か
つ、隣接交差点Ｂ13までの累計距離Ｂｄ13より必ず小さ
いことから、Ｂ13に関して交差点ネットリストへの累計
距離、交差点シーケンシャル番号の登録はせず、また、
探索枝先端バッファへの登録もしない（ステップ８０
３、８０４、８０９でＮＯ）。このようにして、今回の
ＣＰtop ＝Ａ1 について処理し終えたならば、探索枝先
端バッファに登録された交差点の中で、それまでにＣＰ
top とされたものを除いて、累計距離が最小となってい
るものを探し、これを新たなＣＰtop とする。探索枝先
端バッファには、Ａ1 〜Ａ4 、Ｂ11，Ｂ12，Ｂ14が登録
されているが、Ａ1 は除外される。残りの中でＡｄ2 が
最小であったならば、ＣＰtop ＝Ａ2 となる（ステップ
８０２、８０８、図２４（２）の破線参照）。
ＴＰと同一であり、該出発地交差点ＳＴＰの交差点ネッ
トリストには既に累計距離＝零が登録されており、か
つ、隣接交差点Ｂ13までの累計距離Ｂｄ13より必ず小さ
いことから、Ｂ13に関して交差点ネットリストへの累計
距離、交差点シーケンシャル番号の登録はせず、また、
探索枝先端バッファへの登録もしない（ステップ８０
３、８０４、８０９でＮＯ）。このようにして、今回の
ＣＰtop ＝Ａ1 について処理し終えたならば、探索枝先
端バッファに登録された交差点の中で、それまでにＣＰ
top とされたものを除いて、累計距離が最小となってい
るものを探し、これを新たなＣＰtop とする。探索枝先
端バッファには、Ａ1 〜Ａ4 、Ｂ11，Ｂ12，Ｂ14が登録
されているが、Ａ1 は除外される。残りの中でＡｄ2 が
最小であったならば、ＣＰtop ＝Ａ2 となる（ステップ
８０２、８０８、図２４（２）の破線参照）。
【００８８】この場合、Ａ2 に隣接する交差点の内の１
つ、Ｂ21について、出発地交差点からＣＰtop ＝Ａ2 を
経由して隣接交差点Ｂ21までの累計距離Ｄ＝Ｂｄ21を求
める（ステップ８０３）。ＳＴＰ−Ａ2 間の累計距離ｄ
1 は既に交差点Ａ2 に係る交差点ネットリストに累計距
離Ａｄ2 として登録されており（図２の交差点ネットリ
ストの（２６））、Ａ2 −Ｂ21間の距離ｄ2 は交差点Ａ
2 の交差点ネットリストに当該交差点Ａ2から隣接交差
点Ｂ21までの距離として登録されているので、 ｄ1 ＋ｄ2 ＝Ｂｄ21 として累計距離Ｂｄ21が求まる。但し、隣接交差点Ｂ21
は、隣接交差点Ｂ12と同一であり、該交差点Ｂ12の交差
点ネットリストには既に累計距離Ｄ´＝Ｂｄ12が登録さ
れている。この場合、今回求めた累計距離Ｄ＝Ｂｄ21と
大小比較をし、Ｄの方が小さければ、Ｂ12（＝Ｂ 21）の
交差点ネットリストに累計距離Ｂｄ21とＡ2 の交差点シ
ーケンシャル番号を書き換え登録し、探索枝先端バッフ
ァにＢ21の交差点シーケンシャル番号を追加登録する
（ステップ８０４、８０９、８１０）。若し、Ｂｄ12の
方が大きい場合は、Ｂｄ21とＡ2 の書き換え登録はせ
ず、探索枝先端バッファへのＢ21の追加もせず、ステッ
プ８０２に戻る。
つ、Ｂ21について、出発地交差点からＣＰtop ＝Ａ2 を
経由して隣接交差点Ｂ21までの累計距離Ｄ＝Ｂｄ21を求
める（ステップ８０３）。ＳＴＰ−Ａ2 間の累計距離ｄ
1 は既に交差点Ａ2 に係る交差点ネットリストに累計距
離Ａｄ2 として登録されており（図２の交差点ネットリ
ストの（２６））、Ａ2 −Ｂ21間の距離ｄ2 は交差点Ａ
2 の交差点ネットリストに当該交差点Ａ2から隣接交差
点Ｂ21までの距離として登録されているので、 ｄ1 ＋ｄ2 ＝Ｂｄ21 として累計距離Ｂｄ21が求まる。但し、隣接交差点Ｂ21
は、隣接交差点Ｂ12と同一であり、該交差点Ｂ12の交差
点ネットリストには既に累計距離Ｄ´＝Ｂｄ12が登録さ
れている。この場合、今回求めた累計距離Ｄ＝Ｂｄ21と
大小比較をし、Ｄの方が小さければ、Ｂ12（＝Ｂ 21）の
交差点ネットリストに累計距離Ｂｄ21とＡ2 の交差点シ
ーケンシャル番号を書き換え登録し、探索枝先端バッフ
ァにＢ21の交差点シーケンシャル番号を追加登録する
（ステップ８０４、８０９、８１０）。若し、Ｂｄ12の
方が大きい場合は、Ｂｄ21とＡ2 の書き換え登録はせ
ず、探索枝先端バッファへのＢ21の追加もせず、ステッ
プ８０２に戻る。
【００８９】ＣＰtop に隣接する残りの隣接交差点の
内、Ｂ22については、Ｂ22の交差点ネットリストにまだ
累計距離が登録されていないので、Ｂｄ22をＣＰtop ＝
Ａ2 の交差点シーケンシャル番号とともに登録し、探索
枝先端バッファへＢ22を追加登録する。Ｂ23についても
同様である。Ｂ24については、出発地交差点と同じなの
で、累計距離等の登録はしない。このようにして、今回
のＣＰtop ＝Ａ2 につき残存する隣接交差点が無くなっ
たなら、次に、探索枝先端バッファに登録された交差点
の中で、それまでにＣＰ top とされたものを除いて、累
計距離が最小となっているものを探し、これを新たなＣ
Ｐtop とする（ステップ８０２、８０８）。以下、同様
の処理を繰り返していく。
内、Ｂ22については、Ｂ22の交差点ネットリストにまだ
累計距離が登録されていないので、Ｂｄ22をＣＰtop ＝
Ａ2 の交差点シーケンシャル番号とともに登録し、探索
枝先端バッファへＢ22を追加登録する。Ｂ23についても
同様である。Ｂ24については、出発地交差点と同じなの
で、累計距離等の登録はしない。このようにして、今回
のＣＰtop ＝Ａ2 につき残存する隣接交差点が無くなっ
たなら、次に、探索枝先端バッファに登録された交差点
の中で、それまでにＣＰ top とされたものを除いて、累
計距離が最小となっているものを探し、これを新たなＣ
Ｐtop とする（ステップ８０２、８０８）。以下、同様
の処理を繰り返していく。
【００９０】その後、探索枝の先端が目的地に到達する
と、ステップ８０７でＹＥＳとなり、このとき、ＣＰ
top は、常に、累計距離の最小距離のものが選択されて
いるので、目的地交差点ＤＳＰ（ｍ次の交差点とす
る）、該ＤＳＰの交差点ネットリストに累計距離ととも
に記憶してある交差点シーケンシャル番号（図２の交差
点ネットリストの（２５））の示す（ｍ−１）次交差
点、該（ｍ−１）次の交差点の交差点ネットリストに記
憶してある（ｍ−２）次の交差点、・・・、２次の交差
点の交差点ネットリストに記憶してある１次交差点、該
１次交差点に対応させて交差点ネットリストに記憶して
ある０次の交差点（出発地交差点ＳＴＰ）を、順次、０
次の出発地側から目的地側に向けた順序で結んでなる経
路を最短の最適経路として決定し、該最適経路を構成す
るノード列を誘導経路記憶部１５ｊに記憶し経路探索を
終える（ステップ８１１、８１２）。
と、ステップ８０７でＹＥＳとなり、このとき、ＣＰ
top は、常に、累計距離の最小距離のものが選択されて
いるので、目的地交差点ＤＳＰ（ｍ次の交差点とす
る）、該ＤＳＰの交差点ネットリストに累計距離ととも
に記憶してある交差点シーケンシャル番号（図２の交差
点ネットリストの（２５））の示す（ｍ−１）次交差
点、該（ｍ−１）次の交差点の交差点ネットリストに記
憶してある（ｍ−２）次の交差点、・・・、２次の交差
点の交差点ネットリストに記憶してある１次交差点、該
１次交差点に対応させて交差点ネットリストに記憶して
ある０次の交差点（出発地交差点ＳＴＰ）を、順次、０
次の出発地側から目的地側に向けた順序で結んでなる経
路を最短の最適経路として決定し、該最適経路を構成す
るノード列を誘導経路記憶部１５ｊに記憶し経路探索を
終える（ステップ８１１、８１２）。
【００９１】このように、ダイクストラ法によれば、横
型探索法より的確に最短の経路を探索できる上、都市部
で道路密度の高い場合、最適経路の探索途中、逐次、探
索枝先端から或る隣接交差点へ向かう経路の方位が出発
地から見た目的地の方位よりθC 以上ずれているかチェ
ックし、ずれている場合、当該経路の距離を重付けして
優先度を落とし、それより先の経路が後から探索される
ようにしたので、出発地と目的地を結ぶ直線の周辺に存
在する経路を優先して探索を進行させることができ、こ
のようなヒューリスティック探索の結果、都市部におけ
る最適経路の探索を迅速に行うことができる。即ち、ヒ
ューリスティック探索によれば、本来の経路探索対象範
囲（ＢＵ11〜ＢＵ33）の中で、更に、狭い範囲を優先し
て探索が実行されることで、ダイクストラ法の持つ時間
が掛かるという欠点を改善できる。なお、都市部では、
道路密度が高いので、ヒューリスティック探索をして
も、目的地に至る最適経路が見出せないという事態は起
きない。一方、探索対象範囲が郊外の場合は、ヒューリ
スティックでない通常のダイクストラ探索を行うので、
道路密度が低く、例え、目的地に至るのに回り込むよう
な道路しかなくても、本来の経路探索対象範囲（ＢＵ11
〜ＢＵ33）の中を洩れなく探索することで、確実に出発
地から目的地までの最適経路を探索することができる。
型探索法より的確に最短の経路を探索できる上、都市部
で道路密度の高い場合、最適経路の探索途中、逐次、探
索枝先端から或る隣接交差点へ向かう経路の方位が出発
地から見た目的地の方位よりθC 以上ずれているかチェ
ックし、ずれている場合、当該経路の距離を重付けして
優先度を落とし、それより先の経路が後から探索される
ようにしたので、出発地と目的地を結ぶ直線の周辺に存
在する経路を優先して探索を進行させることができ、こ
のようなヒューリスティック探索の結果、都市部におけ
る最適経路の探索を迅速に行うことができる。即ち、ヒ
ューリスティック探索によれば、本来の経路探索対象範
囲（ＢＵ11〜ＢＵ33）の中で、更に、狭い範囲を優先し
て探索が実行されることで、ダイクストラ法の持つ時間
が掛かるという欠点を改善できる。なお、都市部では、
道路密度が高いので、ヒューリスティック探索をして
も、目的地に至る最適経路が見出せないという事態は起
きない。一方、探索対象範囲が郊外の場合は、ヒューリ
スティックでない通常のダイクストラ探索を行うので、
道路密度が低く、例え、目的地に至るのに回り込むよう
な道路しかなくても、本来の経路探索対象範囲（ＢＵ11
〜ＢＵ33）の中を洩れなく探索することで、確実に出発
地から目的地までの最適経路を探索することができる。
【００９２】なお、図１６のステップ７０７ではｋ＝５
としたが、これは１より大きければ３、１０等他の値で
あってもよく、ｋ＝無限大とすれば枝刈りしたのと等価
になる（ステップ７０６でＮＯのとき、ステップ７０４
に戻るようにして、本来の枝刈りを行ってもよい）。ま
た、ダイクストラ法で探索する場合も、交差点ネットリ
ストに当該交差点を原点とする差分座標系での隣接交差
点の位置（差分座標）を追加しておき、探索開始時、ス
テップ７０２では目的地方位を求める代わりに出発地を
原点とする差分座標系で見た目的地の存在象限を求め、
また、探索中、ステップ７０５、７０６では方位の比較
をする代わりに、現在着目している探索枝先端と該交差
点の１つの隣接交差点に対し、探索枝先端の交差点ネッ
トリストに登録された隣接交差点の差分座標から、当該
探索枝先端を原点とする差分座標系で見た隣接交差点の
存在象限を求め、ステップ７０２で求めた目的地の存在
象限と一致するか判断し、一致するときは、ｋ＝１と
し、不一致の時はｋ＝５としたあと、ステップ７０８以
降の処理へ進むようにしてもよい。また、探索枝先端か
ら見た隣接交差点の存在象限が目的地の存在象限と同一
のときはｋ＝１とし、目的地の象限の隣のとき（目的地
の存在象限が第１象限のときは第２，第４象限）はｋ＝
３とし、目的地の象限と反対のとき（目的地の存在象限
が第１象限のときは第３象限）はｋ＝５とするようにし
てもよい。更に、交差点ネットリストを予め、ＣＤ−Ｒ
ＯＭの地図データに道路データの一部として含めてお
き、経路探索時、必要なエリアのデータを他の道路デー
タとともに読み出すようにしてもよい。
としたが、これは１より大きければ３、１０等他の値で
あってもよく、ｋ＝無限大とすれば枝刈りしたのと等価
になる（ステップ７０６でＮＯのとき、ステップ７０４
に戻るようにして、本来の枝刈りを行ってもよい）。ま
た、ダイクストラ法で探索する場合も、交差点ネットリ
ストに当該交差点を原点とする差分座標系での隣接交差
点の位置（差分座標）を追加しておき、探索開始時、ス
テップ７０２では目的地方位を求める代わりに出発地を
原点とする差分座標系で見た目的地の存在象限を求め、
また、探索中、ステップ７０５、７０６では方位の比較
をする代わりに、現在着目している探索枝先端と該交差
点の１つの隣接交差点に対し、探索枝先端の交差点ネッ
トリストに登録された隣接交差点の差分座標から、当該
探索枝先端を原点とする差分座標系で見た隣接交差点の
存在象限を求め、ステップ７０２で求めた目的地の存在
象限と一致するか判断し、一致するときは、ｋ＝１と
し、不一致の時はｋ＝５としたあと、ステップ７０８以
降の処理へ進むようにしてもよい。また、探索枝先端か
ら見た隣接交差点の存在象限が目的地の存在象限と同一
のときはｋ＝１とし、目的地の象限の隣のとき（目的地
の存在象限が第１象限のときは第２，第４象限）はｋ＝
３とし、目的地の象限と反対のとき（目的地の存在象限
が第１象限のときは第３象限）はｋ＝５とするようにし
てもよい。更に、交差点ネットリストを予め、ＣＤ−Ｒ
ＯＭの地図データに道路データの一部として含めてお
き、経路探索時、必要なエリアのデータを他の道路デー
タとともに読み出すようにしてもよい。
【００９３】
【発明の効果】以上本発明によれば、道路データから探
索対象範囲が都市部に存在するか郊外に存在するか判別
し、都市部に存在するときは、出発地と目的地を結ぶ直
線の方向から外れる経路を枝刈りしたり優先度を下げる
などしてヒューリスティック探索し、郊外に存在すると
きは、ヒューリスティックでない通常の探索をするよう
に構成したから、探索対象範囲が道路密度の高い都市部
であれば、ヒューリスティック探索によって短時間に最
適経路の探索を行え、また、探索対象範囲が道路密度の
低い郊外であっても確実に最適経路の探索を行えるの
で、探索不能という事態が生じたり、経路探索に時間が
掛かったりしない。
索対象範囲が都市部に存在するか郊外に存在するか判別
し、都市部に存在するときは、出発地と目的地を結ぶ直
線の方向から外れる経路を枝刈りしたり優先度を下げる
などしてヒューリスティック探索し、郊外に存在すると
きは、ヒューリスティックでない通常の探索をするよう
に構成したから、探索対象範囲が道路密度の高い都市部
であれば、ヒューリスティック探索によって短時間に最
適経路の探索を行え、また、探索対象範囲が道路密度の
低い郊外であっても確実に最適経路の探索を行えるの
で、探索不能という事態が生じたり、経路探索に時間が
掛かったりしない。
【００９４】また、道路データに、予め、該道路データ
の対象エリアが都市部か郊外かを示す地域判別データを
含めておき、該地域判別データを参照して、探索対象範
囲が都市部に存在するか郊外に存在するか判別するよう
にしたから、都市部か郊外かの判別を簡単かつ迅速に行
える。
の対象エリアが都市部か郊外かを示す地域判別データを
含めておき、該地域判別データを参照して、探索対象範
囲が都市部に存在するか郊外に存在するか判別するよう
にしたから、都市部か郊外かの判別を簡単かつ迅速に行
える。
【図１】本発明の経路探索方法を具現した車載ナビゲー
タの全体構成図である。
タの全体構成図である。
【図２】交差点ネットリストの説明図である。
【図３】地図表示制御装置の動作を示す第１の流れ図で
ある。
ある。
【図４】地図表示制御装置の動作を示す第２の流れ図で
ある。
ある。
【図５】地図表示制御装置の動作を示す第３の流れ図で
ある。
ある。
【図６】地図表示制御装置の動作を示す第４の流れ図で
ある。
ある。
【図７】地図表示制御装置の動作を示す第５の流れ図で
ある。
ある。
【図８】地図表示制御装置の動作を示す第６の流れ図で
ある。
ある。
【図９】交差点ネットリストの作成対象図葉の説明図で
ある。
ある。
【図１０】横型探索法による経路探索方法の説明図であ
る。
る。
【図１１】枝刈りの説明図である。
【図１２】本発明の変形例に係る交差点ネットリストの
説明図である。
説明図である。
【図１３】差分座標の説明図である。
【図１４】Ｘ−Ｙ差分座標系の象限区分を示す説明図で
ある。
ある。
【図１５】本発明の変形例に係る枝刈りの説明図であ
る。
る。
【図１６】ダイクストラ法による経路探索動作を示す第
１の流れ図である。
１の流れ図である。
【図１７】ダイクストラ法による経路探索動作を示す第
２の流れ図である。
２の流れ図である。
【図１８】ダイクストラ法による経路探索方法の説明図
である。
である。
【図１９】ＣＤ−ＲＯＭでの地図データの持ち方の説明
図である。
図である。
【図２０】道路レイヤのデータ構造を示す説明図であ
る。
る。
【図２１】隣接ノードの説明図である。
【図２２】交差点ネットリストの作成対象図葉の説明図
である。
である。
【図２３】横型探索法による経路探索方法の説明図であ
る。
る。
【図２４】ダイクストラ法による経路探索方法の説明図
である。
である。
【図２５】従来のヒューリスティック探索の問題点を示
す説明図である。
す説明図である。
１１ 地図情報記憶部（ＣＤ−ＲＯＭ） １２ ディスプレイ装置 １３ 車両位置検出部 １４ 操作部 １５ 地図表示制御装置 １５ｃ 誘導経路描画部 １５ｇ 最適経路探索部 １５ｈ 地域判別部 １５ｉ 経路探索メモリ １５ｊ 誘導経路記憶部
───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.6，ＤＢ名) G08G 1/0969 G01C 21/00 G09B 29/10 ＪＩＣＳＴファイル（ＪＯＩＳ)
Claims (2)
- 【請求項１】 交差点ネットリストを含む道路データを
参照して出発地から目的地までを結ぶ最適経路を探索す
る経路探索方法において、 道路データから探索対象範囲が都市部に存在するか郊外
に存在するか判別し、 都市部に存在するときは、出発地と目的地を結ぶ直線の
方向から外れる経路を枝刈りしたり優先度を下げるなど
してヒューリスティック探索し、 郊外に存在するときは、ヒューリスティックでない通常
の探索をするようにしたこと、 を特徴とする経路探索方法。 - 【請求項２】 道路データに、予め、該道路データの対
象エリアが都市部か郊外かを示す地域判別データを含め
ておき、 該地域判別データを参照して、探索対象範囲が都市部に
存在するか郊外に存在するか判別するようにしたこと、 を特徴とする請求項１記載の経路探索方法。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP28426392A JP2834952B2 (ja) | 1992-10-22 | 1992-10-22 | 経路探索方法 |
| US08/139,595 US5410485A (en) | 1992-10-22 | 1993-10-19 | Navigation apparatus and method for exploring an optimal route based on characteristics of an exploration object zone |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP28426392A JP2834952B2 (ja) | 1992-10-22 | 1992-10-22 | 経路探索方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH06131592A JPH06131592A (ja) | 1994-05-13 |
| JP2834952B2 true JP2834952B2 (ja) | 1998-12-14 |
Family
ID=17676267
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP28426392A Expired - Fee Related JP2834952B2 (ja) | 1992-10-22 | 1992-10-22 | 経路探索方法 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5410485A (ja) |
| JP (1) | JP2834952B2 (ja) |
Families Citing this family (59)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| TW371334B (en) * | 1994-03-18 | 1999-10-01 | Hitachi Ltd | Method for retrieving database with image information |
| JP3341955B2 (ja) * | 1994-09-01 | 2002-11-05 | アイシン・エィ・ダブリュ株式会社 | ナビゲーション装置 |
| DE69531188T2 (de) * | 1994-12-28 | 2004-04-22 | Aisin AW Co., Ltd., Anjo | Navigationsvorrichtung |
| JP3414873B2 (ja) * | 1995-01-20 | 2003-06-09 | 三菱電機株式会社 | 車載用ナビゲーション装置 |
| US5938720A (en) * | 1995-02-09 | 1999-08-17 | Visteon Technologies, Llc | Route generation in a vehicle navigation system |
| US5712788A (en) * | 1995-02-09 | 1998-01-27 | Zexel Corporation | Incremental route calculation |
| JP3384172B2 (ja) * | 1995-02-28 | 2003-03-10 | 株式会社デンソー | 車両用走行案内装置 |
| JP2826079B2 (ja) * | 1995-04-21 | 1998-11-18 | 株式会社ザナヴィ・インフォマティクス | 車載用地図データベース装置 |
| US5919245A (en) * | 1995-04-21 | 1999-07-06 | Xanavi Informatics Corporation | Map database apparatus |
| JP3381459B2 (ja) * | 1995-05-30 | 2003-02-24 | 株式会社デンソー | 車両用走行案内装置 |
| US5893898A (en) * | 1996-07-30 | 1999-04-13 | Alpine Electronics, Inc. | Navigation system having intersection routing using a road segment based database |
| US5819201A (en) * | 1996-09-13 | 1998-10-06 | Magellan Dis, Inc. | Navigation system with vehicle service information |
| JP3474380B2 (ja) * | 1996-12-12 | 2003-12-08 | 株式会社ザナヴィ・インフォマティクス | ナビゲーション装置および地図データベース装置 |
| JP3905136B2 (ja) * | 1996-12-16 | 2007-04-18 | 株式会社ザナヴィ・インフォマティクス | ナビゲーション装置 |
| JP3603927B2 (ja) * | 1997-08-08 | 2004-12-22 | アイシン・エィ・ダブリュ株式会社 | 車両用ナビゲーション装置及びナビゲーション方法 |
| US6035299A (en) * | 1997-08-26 | 2000-03-07 | Alpine Electronics, Inc. | Mapping system with house number representation |
| US6212472B1 (en) | 1997-09-04 | 2001-04-03 | Visteon Technologies, Llc | Method and apparatus for displaying current vehicle position |
| US6192314B1 (en) | 1998-03-25 | 2001-02-20 | Navigation Technologies Corp. | Method and system for route calculation in a navigation application |
| US6144919A (en) * | 1998-03-27 | 2000-11-07 | Visteon Technologies, Llc | Method and apparatus for using non-digitized cities for route calculation |
| US6097316A (en) * | 1998-04-20 | 2000-08-01 | Visteon Technologies, Llc | Communication protocol for a vehicle navigation system |
| US6175801B1 (en) * | 1998-06-19 | 2001-01-16 | Magelan Dts, Inc. | Navigation system map panning directional indicator |
| US6298305B1 (en) | 1998-07-15 | 2001-10-02 | Visteon Technologies, Llc | Methods and apparatus for providing voice guidance in a vehicle navigation system |
| US6088649A (en) * | 1998-08-05 | 2000-07-11 | Visteon Technologies, Llc | Methods and apparatus for selecting a destination in a vehicle navigation system |
| US6108650A (en) * | 1998-08-21 | 2000-08-22 | Myway.Com Corporation | Method and apparatus for an accelerated radius search |
| US6349257B1 (en) | 1999-09-15 | 2002-02-19 | International Business Machines Corporation | System for personalized mobile navigation information |
| US6360165B1 (en) | 1999-10-21 | 2002-03-19 | Visteon Technologies, Llc | Method and apparatus for improving dead reckoning distance calculation in vehicle navigation system |
| JP2001124579A (ja) * | 1999-10-27 | 2001-05-11 | Nippon Seiki Co Ltd | ナビゲーション装置 |
| US6282496B1 (en) | 1999-10-29 | 2001-08-28 | Visteon Technologies, Llc | Method and apparatus for inertial guidance for an automobile navigation system |
| US6393360B1 (en) | 1999-11-17 | 2002-05-21 | Erjian Ma | System for automatically locating and directing a vehicle |
| US6456935B1 (en) | 2000-03-28 | 2002-09-24 | Horizon Navigation, Inc. | Voice guidance intonation in a vehicle navigation system |
| US6735516B1 (en) | 2000-09-06 | 2004-05-11 | Horizon Navigation, Inc. | Methods and apparatus for telephoning a destination in vehicle navigation |
| JP2002091417A (ja) * | 2000-09-12 | 2002-03-27 | Fujitsu Ltd | 画像表示装置 |
| NL1019606C2 (nl) * | 2001-12-19 | 2003-06-20 | And Products B V | Routeplannermodule. |
| US6909965B1 (en) | 2001-12-28 | 2005-06-21 | Garmin Ltd. | System and method for creating and organizing node records for a cartographic data map |
| US6873905B2 (en) * | 2002-03-19 | 2005-03-29 | Opnext Japan, Inc. | Communications type navigation device |
| US20040204836A1 (en) * | 2003-01-03 | 2004-10-14 | Riney Terrance Patrick | System and method for using a map-based computer navigation system to perform geosearches |
| JP2006522317A (ja) * | 2003-02-26 | 2006-09-28 | トム トム べスローテン フエンノートシャップ | タッチスクリーン付きナビゲーション装置。 |
| DE10324961A1 (de) * | 2003-06-03 | 2004-12-23 | Robert Bosch Gmbh | System und Verfahren zum Berechnen und/oder zum Ermitteln von Routen |
| US7251561B2 (en) * | 2004-07-28 | 2007-07-31 | Telmap Ltd. | Selective download of corridor map data |
| US20080189029A1 (en) * | 2004-10-18 | 2008-08-07 | Pierre Hayot | Route Calculation Method and Device with Progressive Elimination of Data Corresponding to the Road Network |
| DE102004061636A1 (de) * | 2004-12-17 | 2006-07-06 | Eads Deutschland Gmbh | Zur Implementierung in ein Computersystem vorgesehenes Verfahren zur Ermittlung optimierter Bahnen eines Fahrzeugs sowie System zur Ermittlung optimierter Soll-Bahnen |
| FR2881862B1 (fr) * | 2005-02-07 | 2007-04-13 | Michelin Soc Tech | Procede et dispositif de determination d'itineraire avec points d'interet |
| US7418339B2 (en) * | 2005-02-14 | 2008-08-26 | Motorola, Inc. | Method for initiating navigation guidance in a distributed communications system |
| JP4714484B2 (ja) * | 2005-03-03 | 2011-06-29 | クラリオン株式会社 | ナビゲーション装置 |
| US8340889B2 (en) * | 2006-03-30 | 2012-12-25 | GM Global Technology Operations LLC | System and method for aggregating probe vehicle data |
| US8554475B2 (en) | 2007-10-01 | 2013-10-08 | Mitac International Corporation | Static and dynamic contours |
| US7483786B1 (en) | 2008-05-15 | 2009-01-27 | International Business Machines Corporation | Method and system for selective route search on satellite navigators |
| JP5345374B2 (ja) * | 2008-12-01 | 2013-11-20 | アルパイン株式会社 | ナビゲーション装置および経路情報提示方法 |
| US8818727B2 (en) * | 2009-11-04 | 2014-08-26 | Mitac International Corp. | Method of assisting a user of a personal navigation device with parking nearby a destination location and related personal navigation device |
| TWI426238B (zh) * | 2009-11-26 | 2014-02-11 | Mitac Int Corp | 協助個人導航裝置之使用者於目的地附近停車的方法及相關導航裝置 |
| US9146133B2 (en) * | 2011-06-06 | 2015-09-29 | Honeywell International Inc. | Methods and systems for displaying procedure information on an aircraft display |
| US8388427B2 (en) * | 2011-06-16 | 2013-03-05 | Microsoft Corporation | Promoting exploration |
| US10033624B2 (en) * | 2013-11-14 | 2018-07-24 | Here Global B.V. | Method and apparatus for probe-based routing |
| US9718558B2 (en) | 2014-02-26 | 2017-08-01 | Honeywell International Inc. | Pilot centered system and method for decluttering aircraft displays |
| CN103837154B (zh) * | 2014-03-14 | 2017-01-04 | 北京工商大学 | 路径规划的方法及系统 |
| CN103994768B (zh) * | 2014-05-23 | 2017-01-25 | 北京交通大学 | 动态时变环境下寻求全局时间最优路径的方法及系统 |
| WO2016034918A1 (en) | 2014-09-04 | 2016-03-10 | Audi Ag | Method and system for creating at least one digital map |
| US20170350714A1 (en) * | 2016-06-06 | 2017-12-07 | International Business Machines Corporation | Route planning based on connectivity of nodes |
| CN117968712B (zh) * | 2023-12-25 | 2024-10-22 | 浪潮智慧科技有限公司 | 一种面向农村旅游资源的导览路径规划方法、设备及介质 |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0346492B1 (en) * | 1987-12-28 | 1995-05-03 | Aisin Aw Co., Ltd. | Route search method for navigation system |
| WO1989006341A1 (en) * | 1987-12-28 | 1989-07-13 | Aisin Aw Co., Ltd. | A display unit of navigation system |
| US5272638A (en) * | 1991-05-31 | 1993-12-21 | Texas Instruments Incorporated | Systems and methods for planning the scheduling travel routes |
| US5187667A (en) * | 1991-06-12 | 1993-02-16 | Hughes Simulation Systems, Inc. | Tactical route planning method for use in simulated tactical engagements |
| US5285391A (en) * | 1991-08-05 | 1994-02-08 | Motorola, Inc. | Multiple layer road memory storage device and route planning system |
-
1992
- 1992-10-22 JP JP28426392A patent/JP2834952B2/ja not_active Expired - Fee Related
-
1993
- 1993-10-19 US US08/139,595 patent/US5410485A/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPH06131592A (ja) | 1994-05-13 |
| US5410485A (en) | 1995-04-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2834952B2 (ja) | 経路探索方法 | |
| JP3474380B2 (ja) | ナビゲーション装置および地図データベース装置 | |
| JP2917825B2 (ja) | 経路選出方法およびシステム | |
| JP3412164B2 (ja) | 経路表示装置 | |
| JP3566503B2 (ja) | リンク旅行時間補間方法 | |
| JP3349839B2 (ja) | 車載用ナビゲーション装置 | |
| JP3340857B2 (ja) | 車載用ナビゲーション装置 | |
| JPH0553501A (ja) | 経路テーブルを用いた最適経路決定方法 | |
| JP3193479B2 (ja) | 経路誘導方法 | |
| JP4133265B2 (ja) | ナビゲーション装置 | |
| JP3012096B2 (ja) | 経路探索方法 | |
| JP3069202B2 (ja) | 経路探索方法 | |
| JP2902209B2 (ja) | 経路探索方法 | |
| JP3270549B2 (ja) | 経路誘導方法 | |
| JP3510964B2 (ja) | 車載用ナビゲーション装置の誘導経路探索方法 | |
| JP3429923B2 (ja) | 車載用ナビゲーション装置 | |
| JP3406449B2 (ja) | 車載用ナビゲーション装置及び誘導経路探索方法 | |
| JP3445833B2 (ja) | 車載用ナビゲーション装置 | |
| JP2902208B2 (ja) | 経路探索方法 | |
| JPH06186049A (ja) | 経路誘導方法 | |
| JP2798828B2 (ja) | 車載ナビゲータ | |
| JP2806149B2 (ja) | 経路計算機能を有するナビゲーション装置 | |
| JPH07103773A (ja) | 経路計算方法及び装置 | |
| JP2892881B2 (ja) | 車載ナビゲータの誘導経路探索方法 | |
| JP2905491B2 (ja) | ナビゲーション装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 19980922 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20091002 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20091002 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101002 Year of fee payment: 12 |
|
| LAPS | Cancellation because of no payment of annual fees |