JP2746604B2 - ナビゲーション装置 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、車両を目的地まで確実に誘導、案内するた
めのナビゲーション装置に係わり、特に案内コースの設
定に特徴を有するナビゲーション装置に関する。

〔従来の技術〕

目的地へ行くための案内情報を出力する車両用ナビゲ
ーション装置は、ディスプレイ上に目的地へ行くための
種々の案内情報を表示させ、地理の不案内な運転者に対
して目的地までコース案内を行うものであり、近年、こ
のナビゲーション装置の開発が盛んに行われている。

従来のナビゲーション方式としては、大別してロケー
ション方式とルート固定方式が挙げられる。

ロケーション方式は、例えば特開昭58-115600号公報
に見られるように、マイクロコンピュータで構成される
演算装置を用いて外部メモリに記憶した地図を読出し、
画像メモリに書き込むと共に、方位、距離センサから車
両の走行軌跡を演算し、地図および走行軌跡をディスプ
レイ上に表示させる方式である。この方式において、経
路の設定は、例えば特開昭57-152100号公報に提案され
ているように、ディスプレイ上に表示された地図上で走
行を予定する道路に沿ってライトペンを移動することに
より行っている。第111図は制御のフローを示してい
る。

また、ルート固定方式は、第112図に示すように、目
的地、現在地を入力すると経路探索を行って（ステップ
801〜803）、ルートを固定し現在位置および経路を表示
させ（ステップ804、805）、次いで自車位置を検出する
センサ信号を入力して現在位置を計算し（ステップ80
6、807）、ステップ808において目的地に着くまで上記
処理を繰り返してナビゲーションを行っている。

この方式における経路の設定は、例えば特開昭60-209
900号公報においては、通過交差点を画面上でタッチ選
択により順次指定すると、該当交差点間の路線データ
（距離、方位等）によりコースが設定される。また、特
開昭61-198016号公報においては、ディスプレイ上に表
示された地図から希望の経路に沿う交差点や主要な目標
物をライトペンで順次指定入力すると、交差点間の距
離、角度によりコースが設定されるようにしている。

〔発明が解決しようとする課題〕

上記従来のロケーション方式或いはルート固定方式に
共通する欠点は、まず目的地に至る経路に存在する交差
点或いはコースを順次入力する必要があるため、使用者
はコース設定時に具体的で詳細な走行予定コースを熟知
している必要があるという点である。また、目的地まで
が遠距離であればある程、入力しなければならないデー
タ数が多くなり、コース設定作業の効率が悪く面倒な作
業となる。また、コース設定作業を簡略化すれば、本来
入力しなければならない交差点やコースの入力を怠るこ
とになり、適切なコース設定が困難になる。さらに、入
力ミスまたは計画変更等による設定コースの変更、或い
は走行中に道に迷ったときのコースの再設定の際には、
入力作業を最初からやりなおす場合もあり作業が面倒で
あった。

さらに詳述すると、ロケーション方式においては、走
行距離や方位の測定誤差が累積されるため、表示手段に
示された地図上の交差点を曲がる必要が生じた場合、目
前に迫った交差点がその地図上の交差点と同一かどうか
の判断ができないことがあり、従って、曲がるべき交差
点を通りすぎてしまったり、また、地図上の自己の位置
が地図上の道路からはみ出してしまう恐れが生じる。す
なわち上記特開昭61-198016号公報においては、設定コ
ースの距離、方位情報が重要であるため、表示されてい
る地図上の道路を忠実にトレースする必要があり、コー
スの指定入力に際して慎重さと熟練を要し手間がかかる
という欠点を有している。

また、ルート固定方式においては、予め走行前に出発
地から目的地までのコースを設定させ、その設定された
コースに従ってコース案内を行うものであるため、目的
地の変更が困難でありまた、例えば交差点等の判断を誤
ってコースから外れた場合には、走行が続行できないと
いう欠点があり、さらに、コース案内どおりに所定の交
差点を通過したか否かは、距離センサーや舵角センサー
により走行距離や右折、左折等の検出を行うことを前提
としているが、現実にはこれらの検出誤差が大きく判断
ミスを誘発しやすいという欠点もある。例えば、上記特
開昭60-209900号公報においては、通過する交差点名を
知らないとコース設定ができないという欠点があり、ま
た、特開昭61-198016号公報においては、例えば一方通
行等の道路事情を知らないでコースの入力指定を行った
場合、誤ったコースに従って案内されてしまう。

一方、本出願人は複数の地点の座標を設定し、その地
点毎に目的地に行くための案内情報を持たせることによ
り、１つの出発地と目的地を入力するとこれら２点間に
最適コースを自動設定することができるナビゲーション
装置を既に出願している（特願昭62-307805号）。本方
式（以下、座標原点方式という）においては、目的地の
変更が可能であり、また、どの地点からも目的地までの
経路探索が可能である。しかしながら、本方式において
は、コース設定は簡単で効率がよいものの、コースが一
義的に決定され途中の寄り道、回り道或いは通過コース
の指定ができなため、希望通りのコース設定が困難であ
るという課題を有している。

本発明は、上記の問題点および課題を解決するため、
コース設定時、使用者の希望通過場所を簡単に入力可能
にするものであって、具体的なコース経路を熟知或いは
計画しなくても、概略の曖昧な情報だけで簡単にコース
設定を行うことができ、使用者のニーズにマッチしたコ
ースを自動的に設定することができる理想的なナビゲー
ション装置を提供することを目的とする。

［課題を解決するための手段］ そのために本発明の請求項１記載のナビゲーション装
置は、地図に関する情報を記憶する記憶装置と、出発
地、目的地及び地図上の任意の点としての１つの通過希
望場所を入力する入力装置と、前記記憶装置に記憶され
た地図に関する情報に基づき案内情報を表示する表示装
置と、前記地図に関する情報と前記入力された各地点に
基づき、出発地から目的地に至る最適経路を探索し、該
経路を前記表示装置に出力して経路案内を行う演算処理
装置とを備え、該演算処理装置は、入力された通過希望
場所に対する道路上の点を設定する手段と、出発地から
該設定された通過希望場所に対する道路上の点及び該道
路上の点から目的地に至る最適経路を探索する手段とを
有することを特徴とする。

また、本発明の請求項２記載のナビゲーション装置
は、地図に関する情報を記憶する記憶装置と、出発地、
目的地、地図上の任意の点としての少なくとも２つの通
過希望場所及び通過順位を入力する入力装置と、前記記
憶装置に記憶された地図に関する情報に基づき案内情報
を表示する表示装置と、前記地図に関する情報と前記入
力された各地点に基づき、出発地から目的地に至る最適
経路を探索し、該経路を前記表示装置に出力して経路案
内を行う演算処理装置とを備え、該演算処理装置は、入
力された各通過希望場所に対する道路上の点を設定する
手段と、通過希望場所の通過順位を最適に設定して出発
地から該設定された各通過希望場所に対する道路上の点
を通過希望場所の通過順に通り目的地に至る最適経路を
探索する手段とを有することを特徴とする。

また、本発明の請求項３記載のナビゲーション装置
は、地図に関する情報を記憶する記憶装置と、出発地、
目的地及び地図上の任意の点としての少なくとも２つの
通過希望場所を入力する入力装置と、前記記憶装置に記
憶された地図に関する情報に基づき案内情報を表示する
表示装置と、前記地図に関する情報と前記入力された各
地点に基づき、出発地から目的地に至る最適経路を探索
し、該経路を前記表示装置に出力して経路案内を行う演
算処理装置とを備え、該演算処理装置は、入力された通
過希望場所に対する道路上の点を設定する手段と、通過
希望場所の通過順位を最適に設定して出発地から該設定
された各通過希望場所に対する道路上の点を通過希望場
所の通過順に通り目的地に至る最適経路を探索する手段
とを有することを特徴とする。

また、本発明の請求項８記載のナビゲーション装置
は、地図に関する情報を記憶する記憶装置と、出発地、
目的地及び地図上の通過ラインとしての通過希望場所を
入力する入力装置と、前記記憶装置に記憶された地図に
関する情報に基づき案内情報を表示する表示装置と、前
記地図に関する情報と前記入力された各地点と通過ライ
ンに基づき、出発地から目的地に至る最適経路を探索
し、該経路を前記表示装置に出力して経路案内を行う演
算処理装置とを備え、該演算処理装置は、入力された通
過ラインに対応して道路上の通過すべき点を設定する手
段と、出発地から該設定された道路上の通過すべき点を
通り目的地に至る最適経路を探索する手段とを有するこ
とを特徴とする。

また、本発明の請求項13記載のナビゲーション装置
は、地図に関する情報を記憶する記憶装置と、出発地、
目的地及び地図上の経路探索領域としての通過希望場所
を入力する入力装置と、前記記憶装置に記憶された地図
に関する情報に基づき案内情報を表示する表示装置と、
前記地図に関する情報と前記入力された各地点と経路探
索領域に基づき、出発地から目的地に至る最適経路を探
索し、該経路を前記表示装置に出力して経路案内を行う
演算処理装置とを備え、該演算処理装置は、入力された
経路探索領域内に存在する道路上の通過すべき地点を設
定する手段と、出発地から該設定された道路上の通過す
べき地点を通り目的地に至る経路を探索する手段とを有
することを特徴とする。

また、本発明の請求項15記載のナビゲーション装置
は、地図に関する情報を記憶する記憶装置と、出発地、
地図上の任意の点としての少なくとも２つの目的地及び
目的地の案内順位を入力する入力装置と、前記記憶装置
に記憶された地図に関する情報に基づき案内情報を表示
する表示装置と、前記地図に関する情報と前記入力され
た各地点に基づき、出発地から目的地に至る最適経路を
探索し、該経路を前記表示装置に出力して経路案内を行
う演算処理装置とを備え、該演算処理装置は、入力され
た各目的地に対する道路上の点を設定する手段と、目的
地の案内順位を最適に設定して出発地から該設定された
各目的地に対する道路上の点を目的地の案内順に通る最
適経路を探索する手段とを有することを特徴とする。

［作用及び発明の効果］ 使用者はナビゲーション装置を使用して、出発地から
目的地までの経路により誘導されることにより道路上を
車両走行させるが、当然のことながら、探索され案内さ
れる経路は、道路に沿ったものであることが必要であ
る。しかしながら、使用者の通過希望場所の入力の状態
により、その通過希望場所が必ずしも道路上にあるとは
限らず、例えば、通過希望場所を入力する場合、使用者
が地図上の任意の位置を選択する場合があるが、その入
力された位置が大体この辺りであろうとか、この辺りを
通りたいという曖昧性を含んだ情報である場合、道路上
にはない点を入力することが多いし、また、公園や広い
施設を通過希望場所として入力する場合、予めそれらが
登録地点として記憶装置にその公園や施設の代表位置座
標が記憶され、その公園や施設の名称を使用者が選択入
力することにより、通過希望場所として選択されるが、
この記憶装置に記憶された公園や施設の代表位置座標が
道路上にない場合もある。

請求項１、４、５、６記載の発明によれば、入力され
る通過希望場所の情報が、大体この辺りであろうとか、
この辺りを通りたいという曖昧性を含んだ入力を行った
場合にも、車両が走行可能であり、経路案内可能である
道路に通過する点を自動的に設定可能とし、経路の設定
時、使用者の通過希望場所を簡単に入力可能にし、その
入力情報に基づいて経路探索を行い、最適経路を設定す
るので、具体的な経路を熟知或いは計画しなくても、概
略の曖昧な情報だけで簡単に経路設定を行うことができ
る。すなわち、使用者がこの辺りを通りたいという情報
しか持ち得ていない場合であっても、或は道路上の地点
を指示選択せず道路外の地点を選択した場合であって
も、出発地から通過希望場所に対応する道路上の点を通
り、目的地まで連続的に案内することができる。

また、請求項２、４記載の発明によれば、１項発明の
効果に加えて、使用者が通過順位を希望するというニー
ズに対応して最適な経路を自動的に簡単な操作で設定す
ることができる。また、請求項３、４、７記載の発明に
よれば、１項発明の効果に加えて、使用者が通過順位を
入力しなくても最適な通過順で廻りたいというニーズに
対応して最適な経路を自動的に簡単な操作で設定でき
る。また、請求項８〜12記載の発明によれば、１項発明
の効果に加えて、使用者が地図上の通過ラインで入力し
たいというニーズに対応して最適な経路を自動的に簡単
な操作で設定できる。また、請求項13、14記載の発明に
よれば、１項発明と同様の効果に加えて、より概略の曖
昧な情報だけで簡単に経路設定を行うことができる。ま
た、請求項15〜19記載の発明によれば、１項発明と同様
の効果に加えて、使用者が目的地の案内順位を希望とす
るというニーズに対応して最適な経路を自動的に簡単な
操作で設定できる。

〔実施例〕

以下、図面を参照しつつ本発明の実施例について説明
する。

第１図は本発明のナビゲーション装置の１実施例を示
す全体構成図である。装置は、本発明の必須構成である
入力装置１、表示装置２、記憶装置３および演算処理装
置４と、付加装置である現在位置確認装置５、通信装置
６および情報センタ７から構成されている。

上記各装置の詳細について説明する。

（入力装置１） タッチパネル８は、第２図に示すように表示装置２上
でスーパーインポーズされる透明操作パネルのようなも
のであり、該透明操作パネルを介して表示装置２に表示
されたメニュー或いは任意の点にタッチすることにより
入力できるものである。例えば、（イ）図で「レジャ
ー、宿」を選択し、（ロ）図で「ゴルフ場」を選択し、
（ハ）図でゴルフ場名を選択するというように希望の目
標物を入力可能とする。また、タッチパネル５の代わり
に、ライトペン９、マウス10、キーボード11等を使用し
て入力することも可能である。

また、第３図に示すように、入力制御装置39において
表示装置２に地図を表示させタッチ入力するようにして
もよいし、タッチパネル５の代わりに、ライトペン９、
マウス10、キーボード11を使用して地図上で指定するこ
とも可能である。この場合に、入力制御ボタン40〜41に
より地図の拡大、縮小を可能にする。

また、表示装置２に表示されている情報とは別に、第
４図（イ）に示すように、目的地名等がハードコピーさ
れた地図、ガイドブック43を利用して入力する手段、例
えばガイドブック43上のメニューがバーコードで示され
ておりこれを読取り、第４図（ロ）に示すように、バー
コードリーダー12（45）により入力制御装置44に入力す
るようにしてもよい。また、バーコードリーダーの代わ
りに文字スキャナー13により、ガイドブック上の文字を
直接読取り入力するようにしてもよい。

また、第５図に示すように、デジタイザー14（49）上
に地図、ガイドブック47をセットした装置上で、入力ペ
ン48で目的地等を直接指示（クリック操作）することに
より、クリックされた点の座標データを入力制御装置46
に入力するようにしてもよい。

また、上記入力手段の他に、ナビゲーション装置の一
部或いは全部の機能を有する別のナビゲーション装置を
用意し、これをテレビ、パソコン等に接続し、上記入力
手段のいずれかを用いて指定した通過場所、目的地デー
タをコンパクトディスク（CD）15、フロッピィディスク
16、ICカード17に記憶させ、そのデータを該ナビゲーシ
ョン装置で再生することによってコースの指定を行うよ
うにしてもよい。例えば第６図に示すように、ICカード
ドライバー51にICカード52をセットすることにより、入
力制御装置50にコースを入力する。

（表示装置２） 入力装置１に入力される情報として案内コース設定に
必要な情報を表示するものであり、後述の演算処理装置
４で演算処理された後、案内情報として例えば目的地へ
行く経路を出力するものであり、CRT18、液晶ディスプ
レイ19等が採用される。

（記憶装置３） 記憶装置３は、例えばフロッピィディスク、CD-ROM、
光ディスク、磁気テープ、ICカード、光カードが用いら
れる。

第７図ないし第15図は本発明の車両用ナビゲーション
装置に使用される記憶装置３に格納されるデータ構造を
示している。

第７図は地域名リスト20を示し、（イ）は、比較的広
範囲でまとめられた地域名例えば都道府県名リストを示
し、例えば県番号01は「愛知県」であり、データとして
漢字、ひらがなおよびローマ字の県名、市名リスト格納
番地（先頭番地）、市名リストデータ数、代表交差点特
徴物番号等を有している。第７図（ロ）は、地域名の下
位情報である例えば区名或いは市名リストを示し、デー
タとして漢字、ひらがなおよびローマ字の市名、町名リ
スト格納番地（先頭番地）、町名リストデータ数、代表
交差点特徴物番号等を有している。第７図（ハ）は、地
域名のさらに下位情報である町名リストを示し、データ
として漢字、ひらがなおよびローマ字の町名、交差点リ
スト格納番地（先頭番地）、交差点リストデータ数、目
的地リスト格納番地、目的地リストデータ数、特徴物リ
スト格納番地、特徴物リストデータ数、代表交差点特徴
物番号等を有している。このような階層構造のデータを
持つことにより、出発地、現在地或いは目的地の入力を
県名から町名へと検索可能にし、また、代表交差点や特
徴物も県単位、市単位、町単位で設定可能にしている。

第８図（イ）、（ロ）、（ハ）は各町に属する交差点
リスト21、目的地リスト22、特徴物リスト23を示し、そ
れぞれ交差点番号、目的地番号、特徴物番号がリストさ
れている。第８図（ニ）、（ホ）はローマ字およびひら
がなのソート用ファイル29、30を示している。地名をア
ルファベット或いは50音順に並べそれに対応するデータ
格納番地を持つことにより、地名のソートを可能にし検
索時間を短縮させるものである。

第９図は地図上の道路および交差点を定義するための
番号の割り振りの１例を示している。交差点番号は３つ
の町間に１〜21まであり、道路番号は各交差点間に１〜
46（○付番号）まで付けられている。１つの道路で往復
可能なものはそれぞれに道路番号が付けられ、片道通行
には１つの道路番号が付けられている。また、目的地番
号101〜103が付けられ、特徴物番号201〜206が付けられ
ている。

第10図ば交差点データ25の１例を示し、交差点番号に
対応した交差点名、座標（北緯、東経）、交差点が始点
または終点となっている道路のうち一番番号の小さな道
路番号（第９図参照）、信号の有無、交差点のレベル
（重要度）が記憶されており、これにより経路探索およ
びディスプレイ上に各種のナビゲイション情報を表示さ
せるものである。

第11図（イ）は目的地データ26の１例を示し、目的地
番号（第９図参照）に対して、目的地名、座標、その目
的地の両側にある連絡交差点番号１、２が設けられ、ま
た第11図（ロ）は特徴物データ27を示し、特徴物番号に
対して、特徴物名（例えば川の名、建物名、橋名等）、
座標、その特徴物の両側にある連絡交差点番号が記憶さ
れている。

第12図は道路データ28の１例を示している。第９図に
示したように道路には道路番号が付けられており、この
道路番号毎に、始点および終点（交差点番号）、同じ始
点を持つ道路番号のうち番号が次のもの、同じ終点を持
つ道路番号のうち番号が次のもの、道路の太さ、通行禁
止（左折、右折禁止）情報、案内不要情報（例えばか
らに行くときは案内情報を出さない）、交差点の写真
番号、一方通行か否か及び道路名の情報が記憶されてい
る。また、第13図に示すように、各道路番号は座標（緯
度、経度）データを有している。

第14図は地図データベース24を示し、日本全国或いは
世界中の地域毎の主要な地図および案内情報が階層構造
として例えばCD、ICカード毎に用意され、さらに最下位
情報として、ICカードには、その地域の例えばホテル、
ガソリンスタンド、レンタカー営業所等を中心とした地
図および案内情報が入力される。

第15図（イ）は地図データベース24内に記憶させる地
形データの構成を示し、地名に対する最大、最小の緯
度、経度、（ロ）に示す隣接画面G1〜G8、（ハ）および
（ニ）に示す画面データと色の種類との関係、本領域を
含む広域図番号（縮小図情報）、本領域内に含まれる拡
大図情報が格納され、画面データa₁₁、a_mnは陸、海、河
川等をビットマップ方式で持ち色データを備えている。

（演算処理装置４） 入力手段１により目的地等の案内コース設定に必要な
情報が入力指定されると、演算処理装置４のROM33に格
納されているナビゲーションプログラムに従って、外部
記憶装置３に記憶されている地図および案内情報データ
を呼び出し、これらをCPU31で演算処理してRAM32に格納
するものである。

（現在位置確認装置５） 人工衛星を利用して位置を測定するGPS（GLOBAL POSI
TIONING SISTEM）受信装置34、路上に配置したビーコン
の位置情報を受信するビーコン受信装置36、地磁気セン
サ35、距離センサ37、ステアリングセンサ38のいずれか
を用いる。ただし、GPS受信装置34とピーコン受信装置3
6は単独で位置測定が可能であるが、その他の場合には
距離センサ37と地磁気センサ35または距離センサ37とス
テアリングセンサ38の組み合わせにより位置を測定す
る。

（通信装置６および情報センタ７） 前記記憶装置３の代わりに、情報センタ７にそのデー
タを用意し、自動車電話等の通信装置６により電話回線
を介してデータを入力し、モデムを経てCPU31のRAM32に
格納するようにしてもよい。また、記憶装置３のデータ
のみならず、入力装置１のコース設定情報および現在位
置確認装置５の情報を送るようにしてもよい。この場
合、情報センタ７としては、その地域のホテル、ガソリ
ンスタンド、レンタカー営業所等が適し、また、地域圏
或いは首都圏の中央に統一してサービスすることも考え
られる。

次に本発明のナビゲーション装置の制御の処理につい
て説明する。

先ず、本発明を前述した座標原点方式に適用した実施
例について説明する。

第16図において、まず、ステップ53−１において、運
転者が案内コースを設定する場合には、ステップ53−２
の案内コース設定ルーチン（後述）に進み、目的地等の
案内コースを設定し、ICカード等に記憶されたコースデ
ータを用いる場合には、設定コースロード（53−３）に
進む。ステップ53−２においては、運転者により目的地
等が入力されると、経路探索モードになり、目的地以外
の全ての地点について目的地へ行くための情報を設定
し、その地点における進行方向を出力する（ステップ5
4）。

そして、スタートを入力すると次の交差点情報を出力
し（ステップ56）、次のステップ57において、自動的に
或いは運転者により交差点確認トリガーが入力される
と、ステップ56に戻り次の交差点での目的地へ行くため
の情報を出力し、また、再スタートを行う場合にはステ
ップ53−２に戻り上記ルーチンを実行する。つまり、こ
のシステムでは、案内通り走行している場合には、交差
点を確認するごとにトリガーが入力されるが、案内する
コースから外れ、他の交差点まで走行してしまったこと
に気付いた場合には、案内コース設定のルーチンを実行
することになる。

第17図は上記案内コース設定ルーチンの処理を示して
いる。先ず、目的地、出発地、途中の通過点を入力する
と、ステップ61において経路探索が行われる。なお、出
発地は車両の現在位置や希望する場所である。次いでス
テップ62〜67においてコース設定モードが選択される。
すなわち、通過点を入力した順位で最適コースを設定す
るモード65と、通過点順位を最適にして最適コースを設
定するモード66と、通過点が指定された順位（入力した
ときの通過点順位を並べ変える）で最適コースを設定す
るモード67が選択される。そして、ステップ68において
設定コースが表示され、ステップ69〜73において所望に
よりコース変更の処理を可能とし、コース設定が終了す
れば設定コースをICカード等に記憶する（ステップ7
4）。

第18図ないし第20図により上記ステップ58の目的地入
力処理について説明する。

第18図は入力画面例を示し、運転者は拡大、縮小ボタ
ンを操作して所望の画面を表示して、タッチパネル上で
目的地をタッチ入力したときに、画面上に目的地が表示
される。このとき目的地点を点滅表示してもよい。

第19図、第20図によりその処理を説明すると、先ず、
ステップ75において入力地点の座標データPOを得た後、
ステップ76において第20図に示されるように、POから検
定距離r₀（ｍ）以内で第11図記載の目的地データを探索
し、ステップ77において目的地があるか否かが判断され
る。目的地がなければステップ75に戻って入力をやりな
おし、目的地があれば、POに一番近い目的地を選択、表
示し（ステップ78〜80）、目的地を１つ探して当該目的
地の連絡交差点（例えば第20図の103）を目的地点とす
る（ステップ82）。

第21図ないし第23図は、第17図のステップ59の出発地
入力処理を示しているが、その内容は、入力地点に一番
近い交差点を選択する他は、前記目的地入力の処理と同
様なので説明を省略する。

次に第24図ないし第32図により第17図のステップ60の
通過点入力の処理について説明する。

第24図は、入力画面の１例を示し、目的地付近、特徴
物付近、地域、交差点、道路等の選択入力ボタンを押し
た後、タッチパネル上で通過点近傍をタッチ入力する。

第25図は、上記目的地付近、特徴物付近、地域、交差
点、道路等の選択入力により通過点を設定するフローを
示している。

第26図および第27図は、第25図においてステップ97の
目的地付近の通過点設定処理を示している。また、第28
図は、第25図においてステップ98の特徴物付近の通過点
設定処理を示している。いずれも内容は第19図の処理と
同様であるので説明を省略する。

第29図は、第25図におけるステップ99の指定地域の通
過点設定の処理を示している。先ず、ステップ120にお
いて入力地点の座標データＰを得た後、ステップ121に
おいて点Ｐから検定距離r_a（ｍ）以内の地域で代表交差
点を探索し、ステップ122、123において１つの代表交差
点があるか否かが判断される。なければステップ120に
戻って入力をやりなおし、１つの代表交差点があれば、
その地域名を表示後確認し（ステップ123〜125）、当該
代表交差点を通過点P_iとする（ステップ126）。

第30図および第31図（ａ）は、第25図におけるステッ
プ100の指定交差点を通過点に設定する処理を示してい
る。先ず、ステップ127において入力地点の座標データ
Ｐを得た後、ステップ128において点Ｐから検定距離r_p
（ｍ）以内の地域で交差点を探索し、ステップ129〜130
において交差点のレベル（わかりやすさ）を判断して、
レベルの高い交差点を選択し、ステップ132〜134におい
て点Ｐに一番近い交差点を表示後確認し、該当交差点を
通過点P_iとする（ステップ136）。

第31図（ｂ）に交差点レベルの１例を示す。この場
合、交差点に信号があり名称があれば、レベル２とし、
そのいずれかがあればレベル１とし、いずれもなければ
レベル０とする。

第32図は、第25図におけるステップ101の指定道路上
に通過点を設定する処理を示している。

先ず、ステップ137において入力地点の座標データＰ
を得た後、ステップ138において点Ｐから検定距離r
_d（ｍ）以内の範囲で一番近い道路を探索し、次いで、
ステップ139において一方通行か否かを判断し、YESであ
ればこれを表示してステップ137に戻り、NOであれば該
当道路を表示後確認し（ステップ141、142）、始点交差
点を通過点P_iとし、終点交差点を通過点P_i+1とすると共
に、該当道路の太さデータを２にする（ステップ143〜1
45）。この太さデータを２にするのは後述する経路探索
でこのデータを使用するためである。次いで、始点をP
_i+1終点をP_iとする道路を検出し該当道路の太さデータ
を２にする（ステップ146〜147）。そしてステップ148
において上記処理を繰り返す。

また、後述の第68図ステップ342〜344に示すように、
道路上に仮交差点を設定することも可能である。

なお、上記した目的地、出発地、通過点での探索にお
いては、入力座標を基点にある検定距離内の該当点を検
出したが、後述のコース指定入力のように、ブロックデ
ータを持ち、入力座標が存在するブロックを検出し、そ
こに含まれる目的地、交差点、道路等を対象に通過点の
設定を行うことも可能である。だだし、この場合にはブ
ロックデータに目的地データ、道路データを追加する必
要がある。

また、第２図、第４図に示すようなメニュー入力によ
って目標物を選択すれば、第11図に示すデータ構造から
目的物の座標または交差点を入力点として得ることが可
能であり、得られた点を基点に前述の通過点設定を行う
或いは得られた交差点そのものを通過点とすることが可
能である。

次に第33図ないし第39図により、第17図におけるステ
ップ61の経路探索Ａの処理について説明する。

第33図（イ）は全体のフローを示し、先ず、経路探索
領域設定Ａの処理を行った後、経路探索データ設定Ａの
処理を行う。経路探索領域設定Ａの処理は、第33図
（ロ）および第34図に示すように、目的地点、通過点の
中から出発地点より一番遠い点PFを得（ステップ15
1）、次に出発地点と点PFの直線距離Ｌを得て、出発地
点を中心として半径ｋ×Ｌ（ｋは１以上の係数）の円内
を経路探索領域SAAとして記憶する（ステップ152、15
3）。

第35図は、第33図（イ）における経路探索データ設定
Ａの処理を示している。ステップ154において経路探索
領域SAA内の全ての交差点データを検出し、ステップ156
〜160において、各通過点P_iを経路終点として経路探索
領域SAA内の各交差点で通過点P_iへ至るための方向を探
索して経路探索データを作成し（第37図で詳述）、ステ
ップ161〜163において、最後の通過点から目的地点まで
の経路探索データを作成する。

第36図は目的地を経路終点とした時の経路探索データ
を図化した例である。

第37図は第35図のステップ157の経路探索データ作成
の処理を示している。

先ず、ステップ164において全ての交差点について出
発地からの距離Ｌ（ｃ）をFFとおき、探索フラグＦ
（ｃ）を０（未探索）とおく（初期設定）。ステップ16
5において出発地の両隣の交差点番号を出発地からの距
離を入力すると共に、両隣の交差点番号に探索フラグ１
（探索中）を入れる。また、出発地から通ってきた道路
番号を入力する。ステップ166においては、探索フラグ
が２（探索終了）でなくかつ距離Ｌ（ｃ）が最小となる
交差点番号C₀を見つける。ステップ167、168において周
囲道路（第９図参照）を検索し周囲道路があれば、最適
な経路条件設定サブルーチンを実行し（ステップ16
9）、ステップ170においてその道路の終点の交差点番号
C₁、この道路の長さをＬとする。次いでステップ171で
出発地からの距離Ｌ（c₀）距離Ｌを加算し、ステップ17
2でその距離Ｐが出発地からの距離Ｌ（c₁）以上であれ
ば、これを出発地からの距離とし、探索フラグを１（探
索中）としその道路番号を入力する（ステップ173）。
このステップ167〜173の処理を実行し、ステップ168で
周囲道路がないと判定されると、探索フラグが２と置か
れ、終了条件確認サブルーチンが実行され終了となる
（ステップ174〜176）。このようにして出発地から目的
地までの最短経路が設定される。

第38図は第37図におけるステップ168の周囲道路探索
サブルーチンの処理を示している。先ず、ステップ177
で周囲道路の検索が一回目であるか否かが判断され、一
回目であればステップ178において、交差点データから
現在いる交差点が始点となっている道路番号を取り出し
記憶する。次いでステップ179において道路データから
この交差点にくる道路に対応する禁止道路を取り出し、
ステップ180において今回取り出した道路が第12図で説
明した禁止道路であるか否かを判断し、YESであればス
テップ182に進み、NOであれば今回取り出した道路を周
囲道路として記憶する。ステップ177で周囲道路の検索
が一回目でないとき及びステップ180でYESのときは、ス
テップ182において道路データから前に探索した道路と
同じ始点を持ち番号が次の道路番号を取り出し、ステッ
プ183において最初に検索した道路と今回取り出した道
路が一致しているか否かを判断し、一致していなければ
ステップ179に進み、一致していればステップ184におい
て周囲道路なしとする。

第39図は第37図におけるステップ169の最適経路条件
設定サブルーチンの処理を示している。先ず、道路デー
タから周囲道路の太さおよび長さを読み込み、太さが例
えば1m以下であるか否かを判断する（ステップ185、18
6）。太さが1mを越えればそのままステップ188に進み、
太さが1m以下であればその道路の長さを例えば２倍とし
て、道路データから現在探索中の交差点へ来た道路の案
内不要データを読み込む（ステップ187、188）。次い
で、ステップ189で案内不要データが周囲道路にあるか
否かが判断され、あればステップ191に進み、なければ
その道路の長さに例えば100mを加え、該距離をステップ
191において出発地から現在探索中の交差点の仮想距離
Ｐ′に加えることにより、周囲道路の先の交差点の仮想
距離Ｐとする。

次に第40図ないし第45図により、第17図の最適コース
設定処理65、66、67について説明する。

第40図ないし第42図は通過点が入力された順位で最適
コースを設定する処理65を示している。ステップ192に
おいて出発地点を最初の経路始点とした後、ステップ19
4において１番目の通過点までの最適コース設定の処理
を行い〔第42図（ａ）（イ）〕、この後１番目の通過点
を経路始点として２番目の通過点までの最適コースを設
定する（ステップ195〜197）〔第42図（ｂ）（ロ）〕。
以下これを繰り返し通過点がなくなったら、ステップ19
8にて最後の通過点を経路始点として目的地までの最適
コースを設定し〔第42図（ｂ）（ハ）〕、ステップ199
において全ての最適コースを作成順に合成して出発地か
ら目的地までの最適コースを設定する〔第42図（ｂ）
（ニ）〕。

第41図は第40図の最適コーズ設定Ａの処理を示し、先
ず、ステップ200でワークエリア内に経路探索データRS
（ｊ）（第35図参照）をロードした後、経路始点をワー
クエリア内に設定し、経路始点から経路終点まで各交差
点での進行方向に沿って最適コースを設定し、そして、
設定コースデータをＫ（ｊ）として記憶する。第42図
（ａ）、（ｂ）に示すように、（イ）、（ロ）、（ハ）
で設定されたコースが合成され（ニ）の最適コースが設
定されることになる。

第43図は、第17図における通過点順位を最適にして最
適コースを設定する処理66を示している。ステップ204
において、通過点順位を順列にして順列組み合わせで記
憶し、ステップ205〜216において、全ての組み合わせに
ついて最適コース設定の処理（ステップ209、214）を行
い、この後、行程距離が最短のコースを１つ選択して最
適コースとして出力するものである。第44図（ａ）、
（ｂ）は出発地、通過点（２）、通過点（１）、目的地
の通過順で合成、設定された最適コースであり、第42図
の例と比較して行程距離は長い。従って、第42図の例が
最適順位の最適コースとして選択されることになる。

第45図は、第17図における使用者により指定された通
過点順位で最適コースを設定する処理67を示している。
指定順に通過点順位を記憶した後（ステップ221）、第4
0図の例と同様に最適コースを設定することになる。

次に、第46図ないし第52図により本発明の他の実施例
について説明する。本実施例は、１つの出発地と複数の
目的地および希望コース上の通過点を入力し案内コース
を設定するものである。

第46図は案内コース設定の処理であり、基本的な目的
地および通過点の入力は、第19図、第25図に示される例
と同様である。

第47図は第46図におけるステップ232の処理内容を示
し、複数の目的地および通過点を順次入力し、それぞれ
の目的地点および通過地点をOP（ｉ）、PP（ｉ）に記憶
し（ステップ250、253）、また、該当入力地点をＰ
（ｉ）に記憶する。

第48図および第49図は、第46図におけるステップ234
の経路探索AAの処理を示している。第48図においてステ
ップ256の経路探索領域Ａは、第33図（ロ）で述べたの
で説明を省略する。ステップ257の処理は、第49図に示
されている。本処理は第35図と類似するが、本実施例の
場合には、目的地点および通過点が入力順に記憶されて
いるために、入力順に経路探索データを作成する点で相
違している。

第50図は第46図のステップ240における使用者により
指定された目的地、通過点順位で最適コースを設定する
処理を示し、第45図の処理と同様である。第51図は同図
ステップ239の目的地、通過点順位を最適にして最適コ
ースを設定する処理を示し、目的地が複数のため、出発
地点と１つの目的地が同一、すなわち出発地にもどる場
合とそうでない場合に分け（ステップ274〜276）ること
を特徴としている。第52図は同図ステップ238の目的
地、通過点が入力された順位で最適コースを設定する処
理を示している。その内容は、第40図の処理と同様であ
るので説明を省略する。

次に第53図ないし第89図により本発明のさらに他の実
施例について説明する。本実施例は、１つの出発地およ
び目的地と概略の通過コース（通過ライン）を入力し、
案内コースを設定するものである。

第53図は、全体の処理の流れを示している。先ず、ス
テップ288の初期設定の処理は、第54図においてデジタ
イザーの入力座標から地形座標を得るための処理であ
る。例えば、第55図（イ）に示すように、地図裏面に地
図の名称、番号、縮尺、基準点の地形、座標等のデータ
を表すバーコードを有した地図314を、当該バーコード
を読み取るバーコードリーダーを有するデジタイザー31
5上にセットし、地図データを読み込む（ステップ31
1）。次に、第56図に示すように入力ペン318により基準
点を指示入力し、基準点のデジタイザー座標を得る（ス
テップ312）。そして、基準点についてこれら地形座標
とデジタイザー座標を比較し、３座標間の相関係数を演
算する（ステップ313）。なお、ステップ802の初期設定
は、縮尺の異なる地図に変更した場合等に行う前述した
初期設定を表す。

第58図は、第53図におけるステップ292の全コース入
力の処理を示している。この場合、第57図に示すように
入力ペン318により通過予定コースに沿ってなぞるが、
特に忠実になぞる必要はない。この入力データは第59図
のように変換される。

第59図に示される入力データ列より、経路探索領域を
検出するために、第60図に示すようなブロックデータAI
101〜AI124を使用する。すなわち、第61図に示すよう
に、各ブロックは座標データとブロック内の交差点デー
タを有するため、入力データ列を該当ブロック中に検出
すると、経路探索対象の交差点として該当ブロック内の
交差点を割り当てることが可能となる。なお、第26図で
述べた通過点入力時の案内コース設定のように、入力デ
ータ一点毎にある検定距離内にある交差点を検索するよ
うにしてもよい。

第62図ないし第65図は、第53図におけるステップ293
の経路探索Ｂの処理を示している。

経路探索Ｂは、第62図に示すように、ステップ327の
経路探索領域設定Ｂの処理とステップ328の経路探索デ
ータ設定Ｂの処理を行う。

この経路探索領域設定Ｂの処理は、第63図に示すよう
に、ステップ329で入力データKD（１）をロードし、こ
の入力データを含む全てのブロック（第60図）を検出
し、当該ブロック名を領域データSABに記憶する。第64
図はこの様子を示している。

前記経路探索データ設定Ｂの処理は、第65図に示すよ
うに、ステップ332において、SABに記憶されているブロ
ックの全交差点データを検出し、ステップ333にて目的
地を経路終点とし、経路探索データ〔第67図（イ）〕を
作成した後（ステップ334）、このデータをRS（１）と
して記憶する。

第66図は、第53図における最適コース設定Ｂの処理を
示し、出発地点を経路始点とし、第67図（ロ）に示すよ
うな最適コースを設定するものである。

第68図ないし第74図は、第53図におけるステップ295
の一部の通過コース入力の処理を示している。その内容
は、一部コースの入力データより最初の入力点、最後の
入力点より該当ブロック内で道路座標を検出し、該当座
標を仮交差点とし、該当座標を含む道路データを仮交差
点が存在するように変更するものである。また、入力デ
ータが含まれるブロック全てを検出し、それらブロック
の中に出発地点および目的地点が含まれなければ、該当
領域を部分探索領域として記憶するものである。

第68図はそのメインフローを示し、これを第69図と共
に説明する。先ず、ステップ339でｋ＝１とし、ステッ
プ340で第69図の入力データを得る。ステップ341でこの
入力データより最初の入力点P1（ｋ）、最後の入力点P2
（ｋ）を得、点P1（ｋ）を探索中心点Ｐとして記憶する
（ステップ341、342）。次いで、道路座標データ検出の
処理を行った後、第69図に示すように、PDを仮交差点PS
（ｋ）、DNを道路番号DS（ｋ）として記憶する（ステッ
プ343、344）。また、点P2（ｋ）についても同様な処理
を行い（ステップ345〜347）、次いで、入力データを含
むブロックを全て検出し、該当ブロック名を領域データ
Ａに記憶する（ステップ348、349）。そして、領域Ａ内
に出発地、目的地があるかいなかの判定を行い（ステッ
プ350、351）、あればステップ340に戻り、なければデ
ータ登録・変更処理352を行い、ステップ354において次
のデータを読み込むための処理を行う。

第70図は第68図ステップ343、346の道路座標データ検
出の処理を示している。点Ｐから検定距離rd（ｍ）内で
点Ｐに一番近い道路座標を探索し（ステップ354）、道
路座標があれば、その座標データをPDとして記憶しPDを
含む道路を検出する（ステップ355〜357）。次いで、一
方通行か否かの判定を行い、NOであれば該当道路番号を
DNとして記憶する（ステップ358、359）。ステップ35
5、358でNOの場合には第68図のステップ340に戻る。

第71図は第68図のステップ352のデータ登録・変更処
理を示している。先ず、入力データをKD（ｋ）として記
憶し、第68図ステップ344における仮交差点PS（ｋ）を
道路座標データPDとし、道路番号DS（ｋ）を道路番号DN
とし（ステップ360、361）、ステップ362において道路
データ変更処理を行う。同様の処理を第68図のステップ
347における仮交差点PE（ｋ）、道路番号DE（ｋ）につ
いても行い（ステップ363、364）、ステップ365におい
て領域Ａを部分探索領域SAP（ｋ）に記憶する。

第72図および第73図は前図ステップ362、364の道路デ
ータ変更処理を示している。先ず、道路DNの始点交差点
NS、終点交差点NEを得（ステップ366）、道路DNのデー
タを始点をNS、終点PDとする道路DN−１に変更し、始点
をPD、終点をNEとする道路DN−２に変更する（ステップ
367）。次いで、始点をNE、終点をNSとする道路を検出
し、該当道路番号をCNとして記憶し（ステップ368、36
9）、道路CNのデータを始点をNE、終点をPDとする道路C
N−１に変更し、始点をPD、終点をNSとする道路CN−２
に変更する（ステップ370）。第74図は上記処理を説明
するための変更前の道路データ（イ）と変更後の道路デ
ータ（ロ）を示している。例えば道路番号26の道路上に
点P1を検出したとき、道路26、始点が13、終点がP1の道
路26−１と、始点がP1、終点が９の道路26−２に分割す
ることにより、案内コースの設定を可能にしている。

第75図は、第53図におけるステップ296の通過点登録
の処理を示している。先ず、ｋを１とし仮交差点PS
（ｋ）を通過点Ｐ（ｋ）として記憶し、仮交差点PE
（ｋ）を通過点Ｐ（ｋ＋１）として記憶し、ステップ37
4において次の仮交差点が有るか否かの判定を行い、有
ればｋ＝ｋ＋２として上記処理を繰り返して仮交差点が
なくなれば終了する。

第76図は、第53図におけるステップ297の経路探索Ｃ
の処理を示し、経路探索領域設定Ｃの処理と経路探索デ
ータ設定Ｃの処理を行う。

第77図および第78図は上記経路探索領域設定Ｃの処理
を示し、目的地点、通過地点の中から出発地点より一番
遠い点PFを得、出発地点と点PEの直線距離Ｌ（ｍ）を得
る（ステップ377、378）。次に、出発地点から検定距離
ｋ×Ｌ（ｍ）（ｋは１より大きい定数）以内に含まれる
ブロックを全て検出し、該当ブロック名を全般探索領域
データSACに記憶する（ステップ379、380）。

第79図は上記経路探索データ設定Ｃの処理を示してい
る。全般探索領域SAC内の全交差点データを得、該当交
差点データをTKDとして記憶する。次に、部分探索領域
内のデータ設定Ｃの処理を行った後（ステップ383）、
全般探索領域内のデータ設定Ｃの処理を行う（ステップ
384）。

第80図は前図ステップ383の部分探索領域内のデータ
設定Ｃの処理を示している。本処理は、それぞれの部分
探索領域内で該当部分探索領域内に含まれる通過点（２
箇所）を経路終点として経路探索データを得るもので、
先ずｋ、ｉを１とし、部分探索領域SAP（ｋ）内の全て
の交差点データを得る（ステップ385、386）。次に、通
過点Ｐ（ｉ）を経路終点とし、ステップ388において経
路探索データ作成の処理を行う。この処理は第37図ない
し第39図で説明した処理である。次に、経路探索データ
をRP（ｉ）として記憶し、部分探索領域SAP（ｋ）内の
交差点データから通過点Ｐ（ｉ）を消去する（ステップ
389、390）。次に、ステップ391でｉが奇数であれば、
ｉに１を加えてステップ387に戻り、偶数であれば全般
探索領域SAC内の全交差点データTKDからSAP（ｋ）内の
交差点データを消去する（ステップ393）。次いで、ス
テップ394において次の部分探索領域SAP（ｋ）があれ
ば、ｋおよびｉに１を加えてステップ386に戻る。

第81図は、第79図におけるステップ384の全般探索領
域のデータ設定Ｃの処理を示している。先ず、ステップ
395で全般探索領域SAC内の全交差点データTKDから交差
点データを得、ｉを１として通過点Ｐ（ｉ）を経路終点
として経路探索データ作成の処理を行う（ステップ395
〜398）。次に、経路探索データをRA（ｉ）として記憶
し、次の通過点があればｉに１を加えてステップ397に
戻り、次の通過点がなくなればステップ402に進み目的
地を経路終点として、ｉに１を加え経路探索データ作成
の処理を行い、経路探索データをRA（ｉ）として記憶す
る（ステップ403〜405）。

第82図は、第53図におけるステップ301の通過点が入
力された順位で最適コースを設定する処理を示してい
る。先ず、出発地点を経路始点とし、ｉを１として全般
領域の部分最適コース設定の処理を行った後、ｉに１を
加え部分領域の部分の最適コー設定の処理を行う。さら
にステップ411でｉに１を加え、次の通過点があるか否
かの判定を行い、有ればステップ408に戻り、通過点が
なくなれば、ステップ413において全般領域の最適コー
ス設定の処理を行った後、全ての設定コースデータＫ
（ｉ）をｉが１から順に合成して最適コースデータKFを
作成する。要するに、出発地点から１番目の通過点まで
は全般領域の経路探索データ、１番目の通過点から２番
目の通過点までは該当の部分探索領域の経路探索データ
という順序で、それぞれの区間で最適コースを設定し、
最後の通過点から目的地までは、全般領域の経路探索デ
ータより最適コースを設定するものである。

第83図は、前図におけるステップ408の全般領域の部
分最適コース設定の処理を示し、ワークエリアに経路探
索データRA（ｉ）をロードした後、部分最適コース設定
Ｃの処理を行う。

この部分最適コース設定Ｃの処理は、第84図に示すよ
うに、経路始点をワークエリアに設定し、経路始点から
経路終点まで各交差点での進行方向に沿って最適コース
を設定する。次いで、設定コースデータをＫ（ｉ）とし
て記憶し、経路終点を経路始点とする。

第85図は、第82図におけるステップ410の部分領域の
部分最適コース設定の処理を示し、ワークエリアに経路
探索データRP（ｉ）をロードした後、部分最適コース設
定Ｃの処理（第84図）を行うものである。

第86図は第82図〜第85図の処理により設定される最適
コースの過程を示している。

第87図および第88図は、第53図におけるステップ302
の通過点順位を最適にして最適コースを設定する処理を
示している。本処理は部分探索領域内の通過点（２箇
所）が常に隣なり合うように通過点の順列組み合わせで
最適コースを作成し、その後行程距離が最短になるコー
スを１つ選んで最適コースとして設定するものである。
詳細は第43図の処理と同様である。第88図は、出発地
点、通過点（２）、通過点（１）、目的地点の順番で最
適コースを設定したものであるが、第86図の例と比較し
て行程距離は長いので、第86図のコースが最適コースと
して選択されることになる。

第89図は、第53図におけるステップ303の指定された
通過点順位で最適コースを設定する処理を示している。
本処理は指定された通過点順位を記憶した後は、第82図
の処理と同様である。

また、第２図、第４図に示すようなメニュー選択入力
によって道路名入力が可能であるが、第12図に示す道路
データ構成により、入力された道路により該当道路の番
号および始点、終点の交差点番号が得られる。道路名が
複数の道路番号で共有される場合、前述の道路番号およ
び始点、終点の交差点番号は複数となる。これらの交差
点の中から前述の方法で、出発地の近傍で通過点
（１）、目的地の近傍で通過点（２）を選出し、これら
のデータを用いて第36図或いは第86図に示すように経路
設定を行うことが可能であり、道路名入力によっても希
望の道路を通過して目的地へ到着することが可能とな
る。

第90図ないし第95図は本発明のさらに他の実施例を示
し、１つの出発地、複数の目的地および概略の全通過コ
ースを入力する例を示している。

第90図は、メインフローを示しているが、第53図の実
施例と相違する点のみを説明する。ステップ441の目的
地入力Ａの処理は、第91図に示すとおり、複数の目的地
を入力し該当目的地Ｐ（ｉ）を記憶する。ステップ444
の経路探索BBの処理は第92図および第93図に示される。
先ず、経路探索領域設定Ｂの処理（第63図）を行い、次
に経路探索データ設定処理BBの処理を行う。先ず、経路
探索領域SAB内の全ての交差点データを得、ｉを１とし
て入力地点Ｐ（ｉ）を経路終点とする。次にステップ46
5において経路探索データ作成の処理（第37図）を行
い、この経路探索データをRS（ｉ）として記憶し、ｉが
入力地点数ｎに等しくなるまで上記処理を繰り返す。

第94図は、第90図におけるステップ446の入力された
目的地順位で最適コースを設定する処理を示している。
先ず、出発地点を経路始点とし、ｊを１として第41図の
最適コース設定処理を行い設定コースデータをＫ（ｊ）
として記憶する（ステップ469〜471）。次に、経路終点
を経路始点にした後、ｊが入力地点数ｎになるまでステ
ップ471に戻って処理を繰り返し、設定コースデータを
Ｋ（ｊ）を１から順に合成して最適コースデータを作成
する。

第95図は、第90図におけるステップ447の指定された
目的地順位で最適コースを設定する処理を示している。
先ず、ステップ476において指定順に入力地点番号をＡ
（ｉ）に記憶し、ｋを１として出発地点を経路終点とす
る。次にステップ479においてＡ（ｋ）をｊとして第41
図の最適コース設定処理を行い設定コースデータをＫ
（ｊ）として記憶する。次に、経路終点を経路始点とし
た後、ｋが入力地点数ｎになるまでステップ479に戻っ
て処理を繰り返し、設定コースデータをＫ（ｊ）を１か
ら順に合成して最適コースデータを作成する。

第96図ないし第104図は本発明のさらに他の実施例を
示し、１つの出発地、複数の目的地および概略の一部の
通過コースを入力する例を示している。第96図は、メイ
ンフローを示しているが、第53図の実施例と相違する点
のみを説明する。

第97図は、第96図におけるステップ485の目的地およ
び一部の通過コースを入力する処理を示している。先
ず、ｉ、ｊ、ｋを１とした後、目的地を入力する場合に
は、ステップ502において目的地入力の処理（第19図）
が行われ、該当目的地をOP（ｉ）に記憶し、ｉに１を加
えて該当入力地点をＰ（ｉ）に記憶する。ステップ501
でNOでかつ一部のコースを入力する場合には、ステップ
506で一部の通過コース入力の処理（第68図）が行わ
れ、仮交差点PS（ｊ）を通過点PP（ｊ）に記憶し、仮交
差点PE（ｊ）を通過点PP（ｊ＋１））に記憶し、ｊに２
を加える（ステップ505〜509）。そしてステップ510に
進み、終了でなければ、ｋに１を加えて上記処理を繰り
返す。

第98図ないし第101図は、第96図におけるステップ487
の経路探索CCの処理を示しているが、処理の内容は第76
図ないし第81図と同様であるので説明を省略する。

第102図は、第96図におけるステップ491の目的地、通
過点が入力された順位で最適コースを設定する処理を示
し、先ず、出発地点を経路始点としｉ、ｊ、ｋを１とし
た後、入力地点をＰ（ｉ）が目的地点か否かの判定が行
われる（ステップ534〜536）。目的地点であれば、ステ
ップ537において全般領域の部分最適コース設定の処理
（第83図、第84図）を行い、ｊに１を加えて設定コース
データをKC（ｉ）に記憶し、ステップ540において次の
入力地点をＰ（ｉ）があれば、ｉに１を加えてステップ
536に戻り、ここで目的地点でなければ、ｋが奇数か否
かが判定され、奇数であれば全般領域の部分最適コース
設定の処理（第83図、第84図）を行い、偶数であれば部
分領域の部分最適コース設定の処理（第85図、第84図）
を行い、ｋに１を加えてステップ539に進み、最終的に
ステップ546において全ての設定コースデータKC（ｉ）
をｉが１から順に合成して最適コースデータKFを作成す
る。

第103図は、第96図におけるステップ492の目的地、通
過コース順位を最適にして最適コースを設定する処理を
示している。詳細な説明は第87図の処理と同様であるの
で説明を省略する。

第104図は、第96図におけるステップ493の指定された
目的地、通過コース順位で最適コースを設定する処理を
示している。詳細な説明は第102図の処理と同様である
ので説明を省略する。

第105図ないし第110図は本発明のさらに他の実施例を
示し、第110図に示すように、１つの出発地および目的
地とコース領域（通過領域）を入力する例を示してい
る。第105図は、メインフローを示しているが、第53図
の実施例と相違する点のみを説明する。

第106図は、第105図におけるステップ583のコース領
域入力の処理を示し、全ての入力データを得た後、入力
データを表示させ（ステップ591〜593）、これら入力デ
ータをKDに記憶する。

第107図は第105図におけるステップ584の経路探索Ｄ
の処理を示している。先ず、経路探索領域設定Ｄの処理
が行われる。これは第108図に示すように、入力データK
Dをロードした後、入力データを含むブロックを全て検
出し、該当ブロックで囲まれる全てのブロックを検出
し、次いで検出した全てのブロック名を領域データKAD
に記憶する。次いで、第109図に示す経路探索データ設
定Ｄの処理が行われる。経路探索領域KAD内の全交差点
データを得、目的地を経路終点とした後、経路探索デー
タ作成の処理を行い、この経路探索データをRSとして記
憶する。

また、前記において、入力点が一点である時も該点を
基点とした検定距離内の領域、或いは該点が含まれるブ
ロックをコース領域として指定することも可能である。

さらに、第２図、第４図に示されるメニュー入力によ
って、目標物の座標或いは連絡交差点、代表交差点を得
ることが可能であるが、それらのいずれかの点を基点と
して前述のようなコース領域を指令することができる。

なお、上記各実施例は主として座標原点方式に適用し
た例を示しているが、データの内容を選択することによ
り、従来例において説明したルート固定方式或いはロケ
ーション方式に適用することも当然可能である。

【図面の簡単な説明】

第１図は本発明に係るナビゲーション装置の１実施例を
示す装置の構成図、第２図および第３図はタッチパネル
による入力例を説明する図で第２図はメニュー画面入力
を示し、第３図は地図画面入力を示している。第４図は
バーコードによる入力例を説明する図、第５図はデジタ
イザによる入力例を説明する図、第６図はICカードによ
る入力例を説明する図である。 第７図ないし第15図はデータ構造の１例を説明するため
の図であり、第７図は地域名リストを示す図、第８図は
交差点、目的地および特徴物リスト並びにソートファイ
ルを示す図、第９図は道路、交差点番号の割り振り例を
示す図、第10図は交差点データを示す図、第11図は目的
地および特徴物データを示す図、第12図および第13図は
道路データを示す図、第14図は地図データベース構造を
示す図、第15図は地図データを示す図である。 第16図ないし第45図は本発明のナビゲーション装置の１
実施例である制御系の処理の流れを説明するための図で
あり、第16図は基本フロー図、第17図は１つの出発地、
目的地および希望コース上の通過点を入力し案内コース
を設定する処理のフロー図、第18図は目的地入力を示す
図、第19図および第20図は目的地入力処理のフロー図お
よび説明図、第21図は出発地入力を示す図、第22図およ
び第23図は出発地入力処理のフロー図および説明図、第
24図は通過点入力を示す図、第25図は通過点入力処理の
フロー図、第26図および第27図は目的地付近の通過点設
定処理のフロー図および説明図、第28図は特徴物付近の
通過点設定処理のフロー図、第29図は指定地域の通過点
設定処理のフロー図、第30図は指定交差点を通過点に設
定する処理のフロー図、第31図（ａ）はその説明図、
（ｂ）交差点レベルの１例を説明するための図、第32図
は指定道路上に通過点を設定する処理のフロー図、第33
図は経路探索処理のフロー図、第34図は第33図のフロー
を説明するための図、第35図は第33図の経路探索データ
設定処理のフロー図、第36図は第35図のフローを説明す
るための図、第37図は第35図における経路探索データ作
成処理のフロー図、第38図は第37図における周囲道路検
索サブルーチンのフロー図、第39図は第37図における最
適経路条件設定サブルーチンのフロー図、第40図は第17
図における通過点が入力された順位で最適コースを設定
する処理のフロー図、第41図は第40図における最適コー
ス設定処理のフロー図、第42図は最適コース設定例を説
明するための図、第43図は第17図における通過点順位を
最適にして最適コースを設定する処理のフロー図、第44
図は最適コース設定例を説明するための図、第45図は指
定された通過点順位で最適コースを設定する処理のフロ
ー図である。 第46図ないし第52図は本発明のナビゲーション装置の他
の実施例である制御系の処理の流れを説明するための図
であり、第46図は１つの出発地、複数の目的地および希
望コース上の通過点を入力し案内コースを設定する処理
のフロー図、第47図は目的地および通過点入力処理のフ
ロー図、第48図は第46図における経路探索処理のフロー
図、第49図は第48図における経路探索データ設定処理の
フロー図、第50図は第46図における指定された目的地、
通過点順位で最適コースを設定する処理のフロー図、第
51図は、目的地、通過点順位を最適にして最適コースを
設定する処理のフロー図、第52図は入力された目的地、
通過点順位で最適コースを設定する処理のフロー図であ
る。 第53図ないし第89図は本発明のナビゲーション装置の他
の実施例である制御系の処理の流れを説明するための図
であり、第53図は１つの出発地、目的地および概略の通
過コースを入力し案内コースを設定する処理のフロー
図、第54図は第53図における初期設定のフロー図、第55
図、第56図および第57図はデジタイザーによる初期設定
を説明するための図、第58図は第53図における全通過コ
ース入力処理のフロー図、第59図は入力データの内容を
示す図、第60図および第61図はブロックデータの内容を
示す図、第62図は第53図における経路探索処理のフロー
図、第63図は第62図における経路探索領域設定処理のフ
ロー図、第64図は第63図の処理を説明するための図、第
65図は第62図における経路探索データ設定処理のフロー
図、第66図は第53図における最適コース設定処理のフロ
ー図、第67図は最適コース設定を説明するための図、第
68図は第53図における一部のコース入力処理のフロー
図、第69図はその説明図、第70図は第68図における道路
座標データ検出処理のフロー図、第71図は第68図におけ
るデータ登録変更処理のフロー図、第72図は第71図にお
ける道路データ変更処理のフロー図、第73図はその説明
図、第74図は道路データの変更内容を説明するための
図、第75図は第53図における通過点登録処理のフロー
図、第76図は第53図における経路探索処理のフロー図、
第77図は第76図における経路探索領域設定処理のフロー
図、第78図はその説明図、第79図は第76図における経路
探索データ設定処理のフロー図、第80図は第79図におけ
る部分領域内のデータ設定処理のフロー図、第81図は第
79図における全般領域のデータ設定処理のフロー図、第
82図は第53図における入力された通過点順位で最適コー
スを設定する処理のフロー図、第83図は第82図における
全般領域の最適コース設定処理のフロー図、第84図は第
83図における部分最適コース設定処理のフロー図、第85
図は第82図における部分領域の部分最適コース設定処理
のフロー図、第86図（ａ）、（ｂ）は最適コース設定を
説明するための図、第87図は第53図における通過点順位
を最適にして最適コースを設定する処理のフロー図、第
88図（ａ）、（ｂ）は最適コース設定を説明するための
図、第89図は第53図における指定された通過点順位で最
適コースを設定する処理のフロー図である。 第90図ないし第95図は本発明のナビゲーション装置の他
の実施例である制御系の処理の流れを説明するための図
であり、第90図は１つの出発地、複数の目的地および概
略の全通過コースを入力し案内コースを設定する処理の
フロー図、第91図は第90図における目的地入力処理のフ
ロー図、第92図は第90図における経路探索処理のフロー
図、第93図は第92図における経路探索データ設定処理の
フロー図、第94図は第90図における入力された目的地順
位で最適コースを設定する処理のフロー図、第95図は第
90図における指定された目的地順位で最適コースを設定
する処理のフロー図である。 第96図ないし第104図は本発明のナビゲーション装置の
他の実施例である制御系の処理の流れを説明するための
図であり、第96図は１つの出発地、複数の目的地および
概略の一部の通過コースを入力し案内コースを設定する
処理のフロー図、第97図は第96図における目的地および
一部の通過コースを入力する処理のフロー図、第98図は
第96図における経路探索処理のフロー図、第99図は第98
図における経路探索データ設定処理のフロー図、第100
図は第99図における部分探索領域内のデータ設定処理の
フロー図、第101図は第99図における全般探索領域内の
データ設定処理のフロー図、第102図は第96図における
入力された通過点順位で最適コースを設定する処理のフ
ロー図、第103図は第96図における目的地、通過コース
順位を最適にして最適コースを設定する処理のフロー
図、第104図は第96図における指定された目的地、通過
コース順位で最適コースを設定する処理のフロー図であ
る。 第105図ないし第110図は本発明のナビゲーション装置の
他の実施例である制御系の処理の流れを説明するための
図であり、第105図は１つの出発地、目的地およびコー
ス領域を入力し案内コースを設定する処理のフロー図、
第106図は第105図におけるコース入力処理のフロー図、
第107図は第105図における経路探索処理のフロー図、第
108図は第107図における経路探索領域設定処理のフロー
図、第109図は第107図における経路探索データ設定処理
のフロー図、第110図は上記処理を説明するための図で
ある。 第111図および第112図は従来のナビゲーション装置の処
理の流れを示すフロー図である。 １……入力装置、２……表示装置、３……記憶装置、４
……演算処理装置、５……現在位置確認装置、６……通
信装置、７……情報センタ。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 横山 昭二 愛知県安城市藤井町高根10番地 アイシ ン・エィ・ダブリュ株式会社内 (72)発明者 角谷 孝二 愛知県安城市藤井町高根10番地 アイシ ン・エィ・ダブリュ株式会社内 (56)参考文献 特開 昭58−70117（ＪＰ，Ａ) 特開 昭59−17577（ＪＰ，Ａ) 特開 昭59−126207（ＪＰ，Ａ) 特開 昭60−114999（ＪＰ，Ａ) 特開 昭60−209900（ＪＰ，Ａ) 特開 昭61−229197（ＪＰ，Ａ) 特開 昭62−95699（ＪＰ，Ａ) 特開 昭62−177604（ＪＰ，Ａ) 特開 昭62−214317（ＪＰ，Ａ) 特開 昭62−243029（ＪＰ，Ａ) 特開 昭62−289721（ＪＰ，Ａ) 特開 昭63−281013（ＪＰ，Ａ) 特開 平１−138409（ＪＰ，Ａ) 特表 昭61−502989（ＪＰ，Ａ) 実開 昭62−192499（ＪＰ，Ｕ) 実開 昭63−188517（ＪＰ，Ｕ) 日本経営工学会誌，Ｖｏｌ．38 Ｎ ｏ．５，1987，Ｐ320〜325 鈴木久敏, 野村重信，「訪問順序制約のある最短経 路問題，運搬経路計画問題に対する統一 的視点,

Claims (19)

(57)【特許請求の範囲】
1. 【請求項１】地図に関する情報を記憶する記憶装置と、 出発地、目的地及び地図上の任意の点としての１つの通
   過希望場所を入力する入力装置と、 前記記憶装置に記憶された地図に関する情報に基づき案
   内情報を表示する表示装置と、 前記地図に関する情報と前記入力された各地点に基づ
   き、出発地から目的地に至る最適経路を探索し、該経路
   を前記表示装置に出力して経路案内を行う演算処理装置
   とを備え、 該演算処理装置は、入力された通過希望場所に対する道
   路上の点を設定する手段と、出発地から該設定された通
   過希望場所に対する道路上の点及び該道路上の点から目
   的地に至る最適経路を探索する手段とを有することを特
   徴とするナビゲーション装置。
2. 【請求項２】地図に関する情報を記憶する記憶装置と、 出発地、目的地、地図上の任意の点としての少なくとも
   ２つの通過希望場所及び通過順位を入力する入力装置
   と、 前記記憶装置に記憶された地図に関する情報に基づき案
   内情報を表示する表示装置と、 前記地図に関する情報と前記入力された各地点に基づ
   き、出発地から目的地に至る最適経路を探索し、該経路
   を前記表示装置に出力して経路案内を行う演算処理装置
   とを備え、 該演算処理装置は、入力された各通過希望場所に対する
   道路上の点を設定する手段と、通過希望場所の通過順位
   を最適に設定して出発地から該設定された各通過希望場
   所に対する道路上の点を通過希望場所の通過順に通り目
   的地に至る最適経路を探索する手段とを有することを特
   徴とするナビゲーション装置。
3. 【請求項３】地図に関する情報を記憶する記憶装置と、 出発地、目的地及び地図上の任意の点としての少なくと
   も２つの通過希望場所を入力する入力装置と、 前記記憶装置に記憶された地図に関する情報に基づき案
   内情報を表示する表示装置と、 前記地図に関する情報と前記入力された各地点に基づ
   き、出発地から目的地に至る最適経路を探索し、該経路
   を前記表示装置に出力して経路案内を行う演算処理装置
   とを備え、 該演算処理装置は、入力された通過希望場所に対する道
   路上の点を設定する手段と、通過希望場所の通過順位を
   最適に設定して出発地から該設定された各通過希望場所
   に対する道路上の点を通過希望場所の通過順に通り目的
   地に至る最適経路を探索する手段とを有することを特徴
   とするナビゲーション装置。
4. 【請求項４】前記入力された通過希望場所に対する道路
   上の点は、入力された通過希望場所の位置座標に最も近
   い道路上の位置に基づいて設定されることを特徴とする
   請求項１ないし請求項３のいずれかに記載のナビゲーシ
   ョン装置。
5. 【請求項５】前記記憶装置は、交差点に関する位置情報
   とともに交差点のレベル情報を含み、前記入力装置によ
   り入力された通過希望場所の位置と交差点のレベル情報
   に基づき交差点を選択して通過希望場所に対する道路上
   の点を設定することを特徴とする請求項１記載のナビゲ
   ーション装置。
6. 【請求項６】前記記憶装置は、交差点に関する位置情報
   とともに代表交差点情報を含み、前記入力装置により入
   力された通過希望場所の位置と代表交差点情報に基づき
   交差点を選択して通過希望場所に対する道路上の点を設
   定することを特徴とする請求項１記載のナビゲーション
   装置。
7. 【請求項７】前記演算処理装置は、入力された通過希望
   場所の通過順位を順列にして順列組み合わせで記憶し、
   全ての組み合わせについて最適経路探索を行い、該探索
   された複数の最適経路のなかから最適な経路を１つ選択
   することを特徴とする請求項３記載のナビゲーション装
   置。
8. 【請求項８】地図に関する情報を記憶する記憶装置と、 出発地、目的地及び地図上の通過ラインとしての通過希
   望場所を入力する入力装置と、 前記記憶装置に記憶された地図に関する情報に基づき案
   内情報を表示する表示装置と、 前記地図に関する情報と前記入力された各地点と通過ラ
   インに基づき、出発地から目的地に至る最適経路を探索
   し、該経路を前記表示装置に出力して経路案内を行う演
   算処理装置とを備え、 該演算処理装置は、入力された通過ラインに対応して道
   路上の通過すべき点を設定する手段と、出発地から該設
   定された道路上の通過すべき点を通り目的地に至る最適
   経路を探索する手段とを有することを特徴とするナビゲ
   ーション装置。
9. 【請求項９】前記通過ラインは、通過希望の道路であり
   該通過希望の道路に基づき通過すべき地点を設定するこ
   とを特徴とする請求項８記載のナビゲーション装置。
10. 【請求項１０】前記通過希望の道路を道路名入力により
    入力することを特徴とする請求項９記載のナビゲーショ
    ン装置。
11. 【請求項１１】前記通過ラインを表示装置に表示される
    地図上でなぞり入力することにより入力することを特徴
    とする請求項８記載のナビゲーション装置。
12. 【請求項１２】なぞり入力により入力された入力データ
    の座標列を検出し、その座標列に対応する道路上の点を
    前記通過ラインに対応する道路上の通過すべき地点とし
    て設定することを特徴とする請求項11記載のナビゲーシ
    ョン装置。
13. 【請求項１３】地図に関する情報を記憶する記憶装置
    と、 出発地、目的地及び地図上の経路探索領域としての通過
    希望場所を入力する入力装置と、 前記記憶装置に記憶された地図に関する情報に基づき案
    内情報を表示する表示装置と、 前記地図に関する情報と前記入力された各地点と経路探
    索領域に基づき、出発地から目的地に至る最適経路を探
    索し、該経路を前記表示装置に出力して経路案内を行う
    演算処理装置とを備え、 該演算処理装置は、入力された経路探索領域内に存在す
    る道路上の通過すべき地点を設定する手段と、出発地か
    ら該設定された道路上の通過すべき地点を通り目的地に
    至る経路を探索する手段とを有することを特徴とするナ
    ビゲーション装置。
14. 【請求項１４】前記地図に関する情報は、ブロック分割
    されて記憶され、前記経路探索領域の設定はブロック分
    割された領域の単位で行われることを特徴とする請求項
    13記載のナビゲーション装置。
15. 【請求項１５】地図に関する情報を記憶する記憶装置
    と、 出発地、地図上の任意の点として少なくとも２つの目的
    地及び目的地の案内順位を入力する入力装置と、前記記
    憶装置に記憶された地図に関する情報に基づき案内情報
    を表示する表示装置と、 前記地図に関する情報と前記入力された各地点に基づ
    き、出発地から目的地に至る最適経路を探索し、該経路
    を前記表示装置に出力して経路案内を行う演算処理装置
    とを備え、 該演算処理装置は、入力された各目的地に対する道路上
    の点を設定する手段と、目的地の案内順位を最適に設定
    して出発地から該設定された各目的地に対する道路上の
    点を目的地の案内順に通る最適経路を探索する手段とを
    有することを特徴とするナビゲーション装置。
16. 【請求項１６】前記入力された目的地に対する道路上の
    点は、入力された目的地の位置座標に最も近い道路上の
    位置に基づいて設定されることを特徴とする請求項15記
    載のナビゲーション装置。
17. 【請求項１７】前記演算処理装置は、入力された目的地
    の案内順位を順列にして順列組み合わせで記憶し、全て
    の組み合わせについて最適経路探索を行い、該探索され
    た複数の最適経路のなかから最適な経路を１つ選択する
    ことを特徴とする請求項15記載のナビゲーション装置。
18. 【請求項１８】前記記憶装置は、交差点に関する位置情
    報とともに交差点のレベル情報を含み、前記入力装置に
    より入力された目的地の位置と交差点のレベル情報に基
    づき交差点を選択して目的地に対する道路上の点を設定
    することを特徴とする請求項15記載のナビゲーション装
    置。
19. 【請求項１９】前記記憶装置は、交差点に関する位置情
    報とともに代表交差点情報を含み、前記入力装置により
    入力された目的地の位置と代表交差点情報に基づき交差
    点を選択して目的地に対する道路上の点を設定すること
    を特徴とする請求項15記載のナビゲーション装置。