JPH05340762A - 経路計算機能を有するナビゲーション装置 - Google Patents

Abstract

(57)【要約】 【目的】市街地等道路が密集した地域では、出発地点か
ら目的地点までの道路地図データの量が膨大になり、最
適経路計算を一度にできない。 【構成】データ量の少ない、計算開始リンクと中間点と
を含む中間領域に相当する道路地図データに基づいて、
前記計算開始リンクから初めて、前記中間領域の端に存
在する各リンクａ，ｂ，ｃに到る経路のリンクコストを
求めていく。そしてこの端に存在する各リンクのうち所
定の基準で選ばれた１つのリンクを新たな計算開始リン
クとして、前記の処理を繰り返して経路を求めていき、
これらの経路をつないでいくことにより、計算終了リン
クＭ₀ までの最適経路を求める。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、指定された２点間を走
行する場合の最適経路を計算する機能を備えたナビゲー
ション装置に関するものである。

【０００２】

【従来の技術】車両に搭載されて車両の現在地を表示す
ることにより、車両の走行支援を行わせるようにしたナ
ビゲーション装置が各種実現されている。従来のナビゲ
ーション装置は、例えば方位センサ及び車速センサ等か
らの出力に基づいて車両の現在地を検出する。一方、検
出した現在地を含む道路地図をＣＤ−ＲＯＭ等で構成さ
れた地図メモリから読出して電子的に表示する。そして
表示される道路地図上に検出した車両現在地を重ねて表
示する仕組みになっている。

【０００３】また、経路計算機能を備えたナビゲーショ
ン装置も実用化されている。経路計算機能を備えた装置
では、一般に、目的地を設定すると、車両現在地を計算
開始リンクとし、目的地を計算終了リンクとして、計算
開始リンクから計算終了リンクまでを含む道路地図デー
タが道路地図メモリから読出され、この道路地図データ
の範囲内で最適経路が自動的に計算され、表示器に表示
される。車両運転者は、表示された最適経路に沿って、
迷うことなく安全な運転を行える。

【０００４】

【発明が解決しようとする課題】ナビゲーション装置に
おいて経路計算を実行するためには、道路地図メモリに
記憶された道路地図データを読出して作業領域に移し、
作業領域においてダイクストラ法等に基づいて経路計算
を行う。ところで、市街地等道路が密集した地域で、高
速道路を使用しない場合は、計算開始リンクから計算終
了リンクまで道路地図データの量が膨大になり、作業領
域に一度に格納することができないという問題がある。

【０００５】経由地点をドライバに設定させて分割計算
をするという手法も考えられるが、出発地から目的地ま
での計算をするのに人間の判断を強いることになり、最
適経路を自動的に計算するというナビゲーション装置の
目的にそぐわない。そこで、作業領域の容量を増大させ
ることなく、短時間で最適経路を計算することのできる
ナビゲーション装置が求められている。

【０００６】

【課題を解決するための手段】請求項１記載の発明は、
指定された２点間を走行する場合の最適経路を計算する
経路計算機能を有するナビゲーション装置であって、出
発地及び設定された目的地にそれぞれ近い２つのリンク
のいずれかを計算開始リンク、他方を計算終了リンクと
して、計算開始リンク及び計算終了リンクを含む道路地
図データのデータ量を推定し、そのメモリ容量が作業領
域の容量を超えると見込まれるときには、計算開始リン
クと中間点とを含む領域に相当する道路地図データのデ
ータ量が作業領域の容量を超えないような中間点を特定
し、計算開始リンクと前記特定された中間点とを含む中
間領域に相当する道路地図データに基づいて、前記計算
開始リンクから初めて、前記中間領域の端に存在する各
リンクに到る経路のリンクコストを求めていき、前記中
間領域の端に存在する各リンクのうち所定の基準で選ば
れた１つのリンクを決定して、計算開始リンクからこの
リンクまでの経路を中間経路とし、このリンクを新たな
計算開始リンクとして、この新たな計算開始リンクと前
記計算終了リンクとに対して必要により前記の処理を繰
り返して中間経路を求めていき、前記のようにして求め
られた新たな計算開始リンクと計算終了リンクとを含む
領域に相当する道路地図データが作業領域のメモリ容量
を超えないと見込まれるときには、この領域に相当する
道路地図データに基づいて、計算開始リンクから計算終
了リンクに到るまでの最終経路を計算し、前記のように
求められた中間経路及び最終経路を連結することによっ
て最適経路を求めるものである。

【０００７】

【作用】請求項１記載の発明では、計算開始リンク及び
計算終了リンクを含む道路地図データのデータ量が作業
領域の容量を超えると見込まれるときには、データ量の
少ない、計算開始リンクと中間点とを含む中間領域に相
当する道路地図データに基づいて、前記計算開始リンク
から初めて、前記中間領域の端に存在する各リンクに到
る経路のリンクコストを求めていく。そしてこの端に存
在する各リンクのうち所定の基準で選ばれた１つのリン
クを新たな計算開始リンクとして、前記の処理を繰り返
して経路を求めていき、これらの経路をつないでいくこ
とにより、計算終了リンクまでの最適経路を求めること
ができる。

【０００８】

【実施例】以下、図面を参照して、本発明の一実施例に
ついて詳細に説明をする。図１は、本発明の一実施例に
係るナビゲーション装置の構成を示すブロック図であ
る。このナビゲーション装置は、車両に搭載されて車両
での走行を支援するために用いられるものである。この
装置には、センサとして、方位を検出するための地磁気
センサ１、車両の速度を検出するための車速センサ２、
及び、車両が前進しているか後退しているかを検出する
ためのシフトセンサ３が備えられている。これら３つの
センサ１，２，３の検出出力は、ナビゲーションＥＣＵ
４内のロケータ５へ与えられる。また、ナビゲーション
ＥＣＵ４内には、車両の旋回角度を検出するための振動
ジャイロセンサ６が設けられており、振動ジャイロセン
サ６の検出出力もロケータ５へ与えられる。

【０００９】ロケータ５は、車両の現在地を算出するた
めのもので、地磁気センサ１で検出された方位と、振動
ジャイロセンサ６で検出された車両の旋回角度とに基づ
いて車両の方位変化量を求め、また、車速センサ２で検
出された車両速度を積算し、シフトセンサ３から与えら
れる車両の前進又は後退を加味して、車両の移動距離を
求める。したがって、例えば車両が発進する前に、車両
の正確な初期位置データをロケータ５に与えておけば、
ロケータ５によってその後の車両の現在地が算出され
る。

【００１０】ロケータ５で算出された車両の現在地を表
わすデータは、ＥＣＵ４内のＭＩＣ(Multi Information
Controller) ７へ与えられる。ＭＩＣ７は、このナビ
ゲーションＥＣＵ４の制御中枢で、ＣＰＵ、ＲＯＭ、Ｒ
ＡＭ等を含んでいる。ＭＩＣ７はナビゲーションＥＣＵ
４内に備えられた上述のロケータ５及びＣＤドライブ８
に接続されているとともに、ナビゲーションＥＣＵ４外
に設けられたグラフィックジェネレータ１０に接続され
ている。グラフィックジェネレータ１０には、モニタ制
御部１１が接続されており、モニタ制御部１１にはＣＲ
Ｔ等の表示部１２、複数のタッチスイッチ１３及び複数
のメカスイッチ１４が備えられている。

【００１１】ＭＩＣ７は、ロケータ５で算出された車両
の現在地データ等に基づいて、ＣＤドライブ８及びＣＤ
オートチェンジャ１５を制御する。ＣＤドライブ８は、
ＭＩＣ７から与えられる制御信号に応答して、事前に装
填されている地図専用ディスクＤ１から車両現在地に対
応する表示用道路地図データを読出し、ＭＩＣ７へ出力
する。ＭＩＣ７は、ロケータ５で算出された現在地デー
タと、ＣＤドライブ８から与えられる道路地図データと
をグラフィックジェネレータ１０へ与え、地図とその地
図上における車両現在地マークとを生成させる。グラフ
ィックジェネレータ１０で生成された地図及び車両の現
在地マークは、モニタ制御部１１へ与えられて、表示部
１２で表示される。

【００１２】また、ＣＤオートチェンジャ１５は、ＭＩ
Ｃ７から与えられる制御信号に応答して、事前に装填さ
れているルート計算ディスクＤ２から経路計算のための
ルート計算用地図データを読出し、ＭＩＣ７へ出力す
る。モニタ制御部１１にはタッチスイッチ１３及びメカ
スイッチ１４が操作されることにより、表示部１２の表
示が切換えられたり、所定の制御信号がＭＩＣ７へ与え
られたりする。

【００１３】ルート計算用地図データは、道路地図（高
速自動車国道、自動車専用道路、国道、都道府県道、指
定都市の市道、その他の生活道路を含む。）をメッシュ
状に分割し、各メッシュ単位でノードとリンクとの組み
合わせからなる経路を、高速道路対応地図と幹線道路対
応地図とに分けて記憶している。高速道路対応地図は主
として高速道路等（高速自動車国道、自動車専用道路、
高速道路間を結ぶ主要道路）を含み、幹線道路対応地図
は、高速道路とともに幹線道路（国道、都道府県道）を
も含んでいる。地図データベースの特性上、幹線道路の
うち国道以上の道路については全国的に閉じたネットワ
ークが形成されている。

【００１４】ここに、ノードとは、一般に、道路の交差
点、メッシュの境界、行き止まり点などを特定するため
の座標点のことであり、交差点を表わすノードを交差点
ノードということがある。各ノードを繋いだものがリン
クである。リンクデータはリンク番号、リンクの始点ノ
ード及び終点ノードのアドレス、リンクの距離、リンク
を通過する方向、その方向における所要時間データ、道
路種別、道路幅、一方通行、右折禁止、左折禁止や有料
道路などの交通規制データ等を含む。

【００１５】位置計算用道路地図データは、２５００分
の１の地図データベースから作成され、前記ルート計算
用地図データよりもさらに詳細で精密なデータであり、
ノードの位置情報と若干のリンク情報（道路幅など）か
らなる１層構造のデータである。リンク情報の種類が少
ないのは、位置検出に直接必要のない所要時間データや
交通規制データ等が含まれていないからである（ただ
し、道路幅は位置検出にも有用となることがあるので含
まれている）。

【００１６】このように位置検出用の道路地図データ
と、ルート計算用地図データとを分けたのは、前者は地
図マッチングのため詳細な精度が要求され、後者は精度
よりも経路計算に必要な各種データを付属させる必要が
あるからである。また、表示用道路地図データは、２５
００分の１の地図データベースから作成された、道路、
地名、有名施設、鉄道、川等を特定する地図データ等で
構成されている。

【００１７】ＭＩＣ７は、ルート計算ディスクＤ２から
読出されたルート計算用地図データに基づき、ダイクス
トラ法等（実施例では、ダイクストラ法の一種であるポ
テンシャル法を採用している）により現在地から目的地
までの最適経路の計算を行う。このポテンシャル法は、
目的地（出発地）に最も近いリンクを計算開始リンクＯ
とし、出発地（目的地）に最も近いリンクを計算終了リ
ンクＭ_O とし、計算開始リンクＯから計算終了リンクＭ
_O に至るリンクコストを順次加算してリンクのツリーを
構成していき、計算終了リンクＭ_O に到達する最もリン
クコストの少ない経路のみを選択する方法である。ここ
でリンクコストを見積もるときに考慮すべき事項とし
て、走行距離、走行時間、高速道路の利用の有無、右折
左折回数、幹線道路の走行確率、事故多発地帯回避、そ
の他ドライバの好みに応じて設定した事項がある。この
ポテンシャル法を実行する作業領域として、ナビゲーシ
ョンＥＣＵ４のＭＩＣ７は、ＲＡＭの上に５１２ｋバイ
トのバッファ領域を用意している。

【００１８】ＭＩＣ７には、さらに、ビーコンユニット
１６が接続され、ビーコンユニット１６にはビーコン受
信機１７が接続されていてもよい。ビーコン受信機１７
は、道路の路側等に設置されたビーコンアンテナから放
射される位置情報や道路情報（交差点名称，行き先案
内）等のデータを受信するためのものである。ビーコン
受信機１７で受信されたビーコンデータは、ビーコンユ
ニット１６を介してＭＩＣ７へ与えられ、最終的に表示
部１２に表示されて、運転者にビーコン情報を表示す
る。また、オプション装置として、ロケータ５にＧＰＳ
ユニット１８を介してＧＰＳ受信機１９が接続されてい
てもよい。ＧＰＳユニット１８及びＧＰＳ受信機１９を
設けると、ＧＰＳ衛星からの信号を受信して、絶対方位
を正確に検出したり、あるいは、移動体の現在地を直接
検出可能である。

【００１９】図２は、表示部１２及びメカスイッチ１４
等を有する表示器の具体的な一例を示す外観正面図であ
る。この表示器は、自動車の例えばフロントコンソール
ボックス内に組み込まれる。表示器は、その表面主要部
に表示部１２が配置されていて、後述するように、地
図、車両現在地、最適経路を始めとして、各種のデータ
を表示する。また、表示部１２の表面には透明な電極パ
ネルが配置されていて、表示部１２にスイッチ内容、す
なわち押圧すべき位置とスイッチ種類とが表示されてい
るときに、そのスイッチの操作が可能ないわゆるタッチ
スイッチ１３が備えられている。

【００２０】表示部１２の両側には、いくつかのメカス
イッチ１４が備えられている。この実施例では、地図表
示を行わせるためのナビスイッチ１４ａ、各種の案内情
報を表示させるための情報スイッチ１４ｂ、後述するメ
モ機能を行わせるためのメモスイッチ１４ｃ、表示内容
を１つ前の画面に戻すためのリターンスイッチ１４ｄ、
表示されたカーソルを移動したり、表示画面をスクロー
ルするためのカーソルキー１４ｅ、及び、データを設定
するために用いるセットスイッチ１４ｆが備えられてい
る。

【００２１】図３は、この実施例のナビゲーション装置
において経路計算を行う場合の概略制御手順を示すフロ
ーチャートである。図３の流れに従って説明すると目的
地が設定された後（ステップＳ１）、ＭＩＣ７は経路計
算の要求が入力されたか否かの判別をする（ステップＳ
２）。経路計算の要求入力は例えば図２に示す表示部１
２に表示された図示しないタッチスイッチ等の押圧によ
りなされる。

【００２２】経路計算の要求ありと判別されると、ＭＩ
Ｃ７はＣＤドライブ８を作動させ、ＣＤオートチェンジ
ャ１５に装填されたルート計算ディスクＤ２から経路計
算プログラムを読出し、その計算プログラムをＭＩＣ７
内の例えばＳＲＡＭにロードする（ステップＳ３）。次
いで、ロケータ５により検出された現在地を計算開始リ
ンクＯとし、設定された目的地を計算終了リンクＭ_O と
して、経路計算が行われる（ステップＳ４）。

【００２３】そして、得られた最適経路は、表示部１２
に表示される（ステップＳ５）。以下に、経路計算の手
順を詳細に説明する。まず、計算開始リンクＳと計算終
了リンクＭ_O との距離をＤとして、計算開始リンクＳと
計算終了リンクＭ_O を含む道路地図の長方形領域を特定
する。このために、長方形の短辺の長さに関連するパラ
メータＶと、長方形の長辺の長さに関連するパラメータ
Ｈを定義する（図４参照）。そして、距離Ｄを基にし
て、これらのパラメータＶ，Ｈと距離Ｄとの関係を示す
グラフ（図５，６）を用いてパラメータＶ，Ｈを求め、
長方形領域を特定する。

【００２４】なお、長方形の領域を選ぶのは、計算され
た最適経路の長さは、計算開始リンクＳと計算終了リン
クＭ_O との直線距離と比べて、極端に長くなることはな
いという経験則に基づいている。したがって、必ずしも
長方形に限られるものではなく、例えば計算開始リンク
Ｓと計算終了リンクＭ_O とを中心とする楕円であっても
よい。

【００２５】次に、ルート計算ディスクＤ２の管理領域
を検索して、前記長方形領域に含まれるメッシュのデー
タ容量が、作業領域のデータ容量より少ないかどうかを
見積もる。少ない場合、すなわちルート計算用地図デー
タの獲得が可能な場合には、その長方形領域に含まれる
メッシュのルート計算用地図データを読出し、ポテンシ
ャル法により計算終了リンクＭ_O までの最適経路の計算
を行う。

【００２６】多い場合は、計算開始リンクＳと計算終了
リンクＭ_O との１／２の地点を中間点Ｍ₁ として、計算
開始リンクＳと中間点Ｍ₁ を対象としてグラフ（図５，
６）を用いてパラメータＶ，Ｈを求めて中間領域Ｒ₁ を
特定し、この中間領域Ｒ₁ に含まれるメッシュのデータ
容量が、作業領域のデータ容量より少ないかどうかを判
定する。

【００２７】少なければ、図７に示すように計算終了リ
ンクＭ_O と中間点Ｍ₁ との１／２の地点を中間点Ｍ₂ と
して、計算開始リンクＳと中間点Ｍ₂ を対象として前記
と同様の判定を行う。このようにして、中間点Ｍ₃ ，Ｍ
₄ ，・・・・の決定とデータ容量の大小の判定を繰り返し、
中間領域Ｒ₃ ，Ｒ₄ ，・・・・に含まれるメッシュのデータ
容量が、作業領域のデータ容量を超える中間点Ｍ_i+1 を
決定して、その１つ前の中間点Ｍ_i における中間領域Ｒ
_i のルート計算用地図データを獲得する。

【００２８】また、中間領域Ｒ₁ に含まれるメッシュの
データ容量が、作業領域のデータ容量より多ければ、図
８に示すように計算開始リンクＳと中間点Ｍ₁ との１／
２の地点を中間点Ｍ₂ として、計算開始リンクＳと中間
点Ｍ₂ を対象として前記と同様の判定を行う。このよう
にして、作業領域のデータ容量を下回る１つ前の中間点
Ｍ_i における中間領域Ｒ_i のルート計算用地図データを
獲得する。

【００２９】そして前記獲得されたルート計算用地図デ
ータに基づいて、経路計算をする。経路計算は、計算開
始リンクＳから中間領域Ｒ_i に含まれるメッシュの端に
あるリンクまで行う。このような端リンクは、通常、図
９ａ，ｂ，ｃに示すように複数存在するので、一定の基
準に従って１つのリンクを決めなければならない。この
基準とは、例えば、 道路種別が国道である端リンクを優先すること、 計算終了リンクＭ_O との直線距離が最も近い端リンク
を優先すること、又は端リンクまでのリンクコストと、
計算終了リンクＭ_O との直線コストとの和が最も小さな
端リンクを優先すること、である。これらの基準のう
ち、のいずれかを採用してもよいし、両方を採用し
てもよい。両方を採用するときは、重みを付けて評価す
ることになるが、実施例の場合は、前述したように、地
図データベースの特性上、国道については全国的に閉じ
たネットワークが形成されているので、に重点をおい
て評価している。

【００３０】この基準に従って端リンクを決めると、計
算開始リンクＳと端リンクまでの中間経路が求まり、そ
の端リンクを計算開始リンクＳとし、計算終了リンクＭ
_O までの中間経路を前記と同様の手順を踏んで求めてい
く。中間経路をつないでいった経路が最適経路である。
以上のようにして決定された一連の中間領域及び最適経
路を図示すると、図１０に示すようになる。

【００３１】なお、本発明は前記実施例に限られるもの
ではない。前記実施例では、中間点を計算開始リンクと
計算終了リンクとの１／２の地点として決定していた
が、前記中間点は、計算開始リンクと計算終了リンクと
を結ぶ線分上にあればよく、１／２以外の点を採用して
もよい。

【００３２】

【発明の効果】請求項１記載の発明によれば、計算開始
リンク及び計算終了リンクを含む道路地図データのデー
タ量が作業領域の容量を超える場合であっても、中間領
域を自動的に決定して、その中間領域の端にある所定の
リンクまでの中間経路をそれぞれ計算し、これらの中間
経路をつないでいくことにより、計算終了リンクまでの
最適経路を求めることができる。したがって、作業領域
の容量を特に大きくしなくとも、計算開始リンクから計
算終了リンクまでの経路を自動的かつ速やかに計算する
ことができる。

【００３３】請求項２記載の発明によれば、前記中間領
域は、計算開始リンクと中間点とを結ぶ線分の方向をほ
ぼ長辺の方向とする長方形であるので、この領域で経路
計算をしていけば、正方形領域で経路計算を行う場合と
比較して、大回りの経路が計算されるということがなく
なり、より速やかに最適経路を計算することができる。

【００３４】請求項３記載の発明によれば、前記中間領
域は、計算開始リンクと中間点とを結ぶ線分の方向をほ
ぼ長軸の方向とする楕円であるので、この領域で経路計
算をしていけば、正方形領域で経路計算を行う場合と比
較して、大回りの経路が計算されるという可能性がなく
なり、より速やかに最適経路を計算することができる。

【００３５】請求項４記載の発明によれば、前記中間領
域の端に存在する各リンクのうち計算終了リンクとの直
線距離が最も短いリンクを選定することができるので、
効率よく最適経路を計算することができる。請求項５記
載の発明によれば、計算開始リンクから端に存在する各
リンクまでのリンクコスト及び存在する各リンクと計算
終了リンクとの直線距離の最も小さいリンクを選定する
ことができるので、さらに効率よく最適経路を計算する
ことができる。

【００３６】請求項６記載の発明では、前記中間領域の
端に存在する各リンクのうち道路種別が上位の道路を選
定することができるので、上位の道路の走行を優先した
い場合に好適である。請求項７記載の発明では、前記中
間点は、計算開始リンクと計算終了リンクとを結ぶ線分
上にあるので、中間点の決定を容易にすることができ
る。

【図面の簡単な説明】

【図１】本発明の一実施例にかかるナビゲーション装置
の構成を示すブロック図である。

【図２】本発明の一実施例にかかるナビゲーション装置
の表示器の具体的な一例を示す外観正面図である。

【図３】本発明の一実施例にかかるナビゲーション装置
における経路計算処理手順を説明するためのフローチャ
ートである。

【図４】計算開始リンクと計算終了リンクを含む長方形
領域を示す図である。

【図５】計算開始リンクと計算終了リンクとの距離Ｄを
基にして、長方形のパラメータＶとを決定するためのグ
ラフである。

【図６】計算開始リンクと計算終了リンクとの距離Ｄを
基にして、長方形のパラメータＨとを決定するためのグ
ラフである。

【図７】中間点の決定方法を説明するための図である。

【図８】中間点の決定方法を説明するための図である。

【図９】中間領域に含まれる端リンクの存在を示す図で
ある。

【図１０】決定された一連の中間領域及び最適経路を示
す図である。

【符号の説明】

４ ナビゲーションＥＣＵ ５ ロケータ ７ ＭＩＣ ８ ＣＤドライブ １４ メカスイッチ １５ ＣＤオートチェンジャ Ｄ２ ルート計算ディスク

Claims (7)

【特許請求の範囲】
1. 【請求項１】道路地図データを記憶した道路地図記憶手
   段と、 経路計算要求信号を入力する入力手段と、 入力手段から経路計算要求信号が入力されたことに応じ
   て、道路地図記憶手段に記憶された道路地図データを読
   出して作業領域に移すロード手段と、 作業領域に移された道路地図データに基づいて、出発地
   及び設定された目的地にそれぞれ近い２つのリンク間を
   走行するときの最適経路を計算する経路計算手段とを含
   む、経路計算機能を有するナビゲーション装置におい
   て、 前記経路計算手段は、出発地及び設定された目的地にそ
   れぞれ近い２つのリンクのいずれかを計算開始リンク、
   他方を計算終了リンクとして、計算開始リンク及び計算
   終了リンクを含む道路地図データのデータ量を推定し、
   そのメモリ容量が経路計算作業領域の容量を超えると見
   込まれるときには、計算開始リンクと中間点とを含む領
   域に相当する道路地図データのデータ量が作業領域の容
   量を超えないような中間点を特定し、計算開始リンクと
   前記特定された中間点とを含む中間領域に相当する道路
   地図データに基づいて、前記計算開始リンクから初め
   て、前記中間領域の端に存在する各リンクに到る経路の
   リンクコストを求めていき、前記中間領域の端に存在す
   る各リンクのうち所定の基準で選ばれた１つのリンクを
   決定して、計算開始リンクからこのリンクまでの経路を
   中間経路とし、このリンクを新たな計算開始リンクとし
   て、この新たな計算開始リンクと前記計算終了リンクと
   に対して必要により前記の処理を繰り返して中間経路を
   求めていき、前記のようにして求められた新たな計算開
   始リンクと計算終了リンクとを含む領域に相当する道路
   地図データが作業領域のメモリ容量を超えないと見込ま
   れるときには、この領域に相当する道路地図データに基
   づいて、計算開始リンクから計算終了リンクに到るまで
   の最終経路を計算し、前記のように求められた中間経路
   及び最終経路を連結することによって最適経路を求める
   ものであることを特徴とする経路計算機能を有するナビ
   ゲーション装置。
2. 【請求項２】前記中間領域は、計算開始リンクと中間点
   とを結ぶ線分の方向をほぼ長辺の方向とする長方形であ
   る請求項１記載の経路計算機能を有するナビゲーション
   装置。
3. 【請求項３】前記中間領域は、計算開始リンクと中間点
   とを結ぶ線分の方向をほぼ長軸の方向とする楕円である
   請求項１記載の経路計算機能を有するナビゲーション装
   置。
4. 【請求項４】前記中間領域の端に存在する各リンクのう
   ち１つを決定する所定の基準は、計算終了リンクとの直
   線距離である請求項１記載の経路計算機能を有するナビ
   ゲーション装置。
5. 【請求項５】前記中間領域の端に存在する各リンクのう
   ち１つを決定する所定の基準は、計算開始リンクから端
   に存在する各リンクまでのリンクコスト及び存在する各
   リンクと計算終了リンクとの直線距離である請求項１記
   載の経路計算機能を有するナビゲーション装置。
6. 【請求項６】前記中間領域の端に存在する各リンクのう
   ち１つを決定する所定の基準は、リンクの道路種別であ
   る請求項１記載の経路計算機能を有するナビゲーション
   装置。
7. 【請求項７】前記中間点は、計算開始リンクと計算終了
   リンクとを結ぶ線分上にある請求項１記載の経路計算機
   能を有するナビゲーション装置。