JPH04177119A - 最適経路決定装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〈産業上の利用分野〉 本発明は、運転者による目的地点などの設定に応じて、
道路地図メモリに記憶されている道路地図データから出
発地点と目的地点とを含む範囲の道路地図データを読出
し、この道路地図データに基いて出発地点から目的地点
に至る最適経路を決定する最適経路決定装置に関するも
のである。

〈従来の技術〉 従来より画面上に車両の位置方位などを表示し、見知ら
ぬ土地や夜間などにおける走行の便宜を図るために開発
された経路誘導装置が知られている。

上記経路誘導装置は、デイスプレィ、方位センサ、距離
センサ、道路地図メモリ、コンピュータを車両に搭載し
、方位センサから入力される方位データ、距離センサか
ら入力される走行距離データ、および道路地図メモリに
格納されている道路のパターンとの一致に基いて車両位
置を検出し、この車両位置および目的地点を道路地図と
共にデイスプレィに表示するものである。

この場合、出発地点から目的地点に至る走行経路を運転
者自身に判断させていた。

しかし、ごく最近においては、運転者による目的地点設
定入力に応じて出発地点から目的地点までの経路をコン
ピュータにより自動的に算出し、走行前あるいは走行中
に道路地図上に経路を重畳して表示することが提案され
ている。

上記出発地点から目的地点に至る経路の計算方法として
は、いわゆるダイクストラ法がある（緊急車両走行誘導
システムの開発研究報告書　財団法人　日本交通管理技
術協会　昭和６１年３月、Ｄｌｒｃｋ　Ｙｏｎ　Ｖｌｉ
ｅｔ、　”ＩＩＩｐｒｏｖｅｄ　５ｈｏｒｔｅｓｔ　Ｐ
ａｔｈＡＩｇＯｒｉｔｈｆｆｉ　　ｒｏｒ　　Ｔｒａｎ
ｓｐｏｒｔａｔｉｏｎ　　Ｎｅｔｖｏｒｋ−、Ｔｒａｎ
ｓ−ｐｏｒｔａｔｉｏｎ　Ｒｅ５ｅａｒｃｈ、　Ｖｏｌ
、１２．１９７８）　、この方法は計算の対象となる道
路を幾つも区切って、区切った点をノードとし、ノード
とノードとを結ぶ経路をリンクとし、出発地点に最も近
いノードまたはリンクを始点とし、目的地に最も近いノ
ードまたはリンクを終点とし、始点から終点に至るリン
クのツリーを想定し、ツリーを構成する全ての経路のリ
ンクコストを順次加算して、目的地点に到達する最もリ
ンクコストの少ない経路を算出する方法である。ここで
リンクコストを見積もるときに考慮すべき事項として、
走行距離、走行時間、高速道路の利用の有無、右折左折
回数、幹線道路の走行確率、事故多発地帯回避、その他
運転者の好みに応して設定した事項がある。

この方法で経路を計算すれば、出発地点から目的地点に
至る経路が存在する限り、確実に目的地点に到達する。

〈発明が解決しようとする課題〉 しかしながら、上記グイラストラ法は、計算の対象とな
る領域にあるノードの数、リンクの数に応じて計算時間
が決まるものであり、ノード、すンクは、計算の対象と
なる領域に相当数存在するのであるから、通常かなりの
時間をかけて計算を行うものである。

したがって、目的地点を設定してから最適経路が計算さ
れるまで、運転者はじっと待つ必要があり、急いでいる
ときの実用性に問題が残る。

本発明は、上記の問題に鑑みてなされたもので、運転者
による目的地点の設定に応じて道路地図メモリから道路
地図データを読出して、出発地点から目的地点までの経
路を算出する場合において、その場で経路計算をしなく
とも迅速に最適経路を得ることができる最適経路決定装
置を提供することを目的とする。

く課題を解決するための手段〉 上記の目的を達成するための本発明の最適経路決定装置
は、 道路地図データを構成する地点の中から、一定の基準に
従って特定の地点を選定しておき、各特定の地点を出発
地として各目的地点に至る最適経路をあらかじめ計算し
、この最適経路のうち、上記特定の地点から、この最適
経路が通る少なくとも次の特定の地点に至るまでの初期
経路を、当該目的地点および当該出発地となる特定の地
点に対応させて記憶した経路テーブルと、 目的地点を設定するとともに、車両の現在位置に近い特
定の地点または最適経路に沿った特定の地点を設定する
初期設定手段と、 上記初期設定手段による目的地点の設定および特定の地
点の設定に応じて経路テーブルを検索し、初期経路を求
める初期経路取得手段とを含み、上記経路テーブルは、
異なった目的地点に対して同一の初期経路に関する情報
を記憶する場合、当該具なった目的地点を含む集合に対
応させて、当該初期経路に関する情報を記憶している（
請求項１）。

上記目的地点は、道路地図データを構成する全ての地点
から選ばれるものであってもよく、運転者がしばしば旅
行する目的地に対応して一定の基準で設定されたいくつ
かの地点から選ばれるものであってもよい。

上記特定の地点は道路地図の主要地点から選ばれたもの
であることが好ましいが、道路地図上の全ての地点に対
応するものであってもよい。

また、経路テーブルは、出発地となる特定の地点から次
の特定の地点までの初期経路を記憶させるのみならず、
次の特定の地点より先の経路も同時に記憶させてもよい
。

上記最適経路決定装置は、各特定の地点を経路起点とし
て各目的地点までの経路を計算の対象としていたが、逆
に特定の地点を経路終点として各出発地点までの経路を
計算の対象とし、経路テーブルは、異なった出発地点に
対して、同一の終期経路に関する情報を記憶する場合、
当該出発地点の集合に対応させて、当該同一の終期経路
に関する情報をまとめて記憶しているものでもよい（請
求項２）。

また、道路地図データがノードとリンクとの組み合わせ
からなるものであり、道路地図上の地点をノードまたは
リンクにより特定するものであってもよい（請求項３）
。

また、経路テーブルは、目的地点、出発地点間の距離が
一定の基準値よりも長い場合にのみ、上記初期経路また
は終期経路に関する情報を記憶しているものであっても
よい（請求項４）。

く作用〉 上記請求項１の最適経路決定装置によれば、運転者の操
作などにより目的地点が設定され、車両の現在位置に近
い特定の地点が設定されると、初期経路取得手段は、経
路テーブルを検索して、上記車両の現在位置に近い特定
の地点から始まる初期経路を取得することができる。

この初期経路は、目的地点に至る最適経路の一部であり
、上記出発地となる特定の地点から最適経路が通る少な
くとも次の特定の地点まで続いているので、運転者を、
上記特定の地点から次の特定の地点まで誘導できる。

さらに初期設定手段により、最適経路に沿った次の特定
の地点を設定すると、初期経路取得手段は、この次の特
定の地点を起点とし、目的地点に至る最適経路の一部で
ある次の初期経路を取得することかできる。

したがって、運転者に対して、次の特定の地点から始ま
る次の初期経路を示すことができる。

以下、同様の手順により、運転者に対して、連続した初
期経路を示すことができ、ついには目的地に至る全ての
最適経路を示すことができる。

また、上記経路テーブルが、異なった目的地点に対応す
る地点に対して、同一の初期経路に関する情報を記憶す
る場合、当該具なった目的地点を含む集合（これを地域
と呼ぶこともできる）に対応させて、当該１つの初期経
路に関する情報を記憶している。このように目的地か異
なっていても初期経路を共通にする場合かあるのは、同
一方面にある目的地であれば、最初は同一の経路を走行
するという経験則にあてはめても理解できることである
。したがって、異なった目的地点であっても、初期経路
を同一にするものであれば、当該目的地同士をまとめ、
このまとめた１つの集合に対して、１つの初期経路に関
する情報を記憶させ記憶容量の節約を図るようにしたの
である。

上記請求項２の最適経路決定装置においても、計算の順
序を目的地側から行うとともに、同一の終期経路に関す
る情報を、当該出発地点の集合（地域）に対応させてま
とめて記憶している点て相違するのみであり、連続した
終期経路を示すことにより、ついには目的地点から出発
地点までの最適経路を示すことができるとともに、同一
の終期経路に関する情報をまとめて記憶して記憶容量の
節約を図る点では、請求項１の最適経路決定装置と同様
である。したがって、以下の説明および実施例の説明で
は、請求項１記載のとおり、出発地側から経路を取得し
ていく場合を想定するものとする。

なお、上記経路テーブルに記憶する初期経路に関する情
報の形態としては、運転者にどのように経路情報を示す
のかにより異なってくる。例えば、上記道路地図データ
をノードとリンクとの組み合わせから構成し、道路地図
上の地点をノートまたはリンクにより特定できるものと
すると、初期経路にそった矢印の列、すなわちリンク列
を表示するならば、経路テーブルにはそのリンク列を記
憶させる必要かある。初期経路に沿って地点を表示する
のなら経路テーブルにはノード列を記憶させる必要があ
る。初期経路に沿った交差点のみを表示するのなら交差
点に対応するリンク列またはノードの列を記憶させれば
よい。

また、目的地点および出発地となる特定の地点間の距離
が一定の基準値よりも長い場合にのみ、経路テーブルに
、上記初期経路に関する情報を記憶させるならば、出発
地と目的地とが比較的近い場合には、経路テーブルを使
わず、直接最適経路の計算等を行わせることにして、経
路テーブルのメモリの容量を節約することができる。

〈実施例〉 以下本発明の実施例を示す添付図面に基づいて詳細に説
明する。

本実施例の最適経路決定装置は、最適経路を画面表示し
たり、音声出力したりして車両を誘導する経路誘導装置
に組み込まれたものである。

上記経路誘導装置は、第１図に示すように、表示器１と
、コンソール２と、方位センサ１０と、距離センサ９と
、道路地図データを格納している道路地図メモリ３Ａと
、経路テーブルを格納した経路メモリ３Ｂと、各メモリ
３Ａ、３Ｂから記憶データを読出すメモリドライブ４と
、距離センサ９により検出される走行距離および方位セ
ンサ１０により検出される走行方向変化量をそれぞれ積
算し、この積算データとメモリドライブ４により読出し
た道路地図データとの比較に基いて車両位置を検出する
ロケータ１１と、初期経路の検索・取得、所定範囲の道
路地図の続出、車両の誘導をするための表示用データの
生成、音声出力装置１５の制御、およびロケータ１１の
制御などの種々の制御を行う処理部７（この処理部７は
初期経路取得手段としても機能する。）と、処理部７か
ら出力される表示用データを記憶する主メモリ８と、表
示器１の制御を行う出力コントローラ１２と、コンソー
ル２から入力される初期データを設定する初期設定部６
とを有する。

さらに詳細に説明すればコンソール２は、この装置の起
動・停止や画面上のカーソル移動、目的地点などの初期
データの設定、画面上に表示されている道路地図のスク
ロール等をさせるキー人力ボード（図示せず）を有して
いる。

方位センサ１０は、車両の走行に伴なう方位の変化を検
出するものであり、地磁気センサ、ジャイロなどを使用
することが可能である。

距離センサ９は、車両の速度、あるいは、車輪の回転数
などに基づいて走行距離を検出するものであり、車輪速
センサ、車速センサなどが使用可能である。

ロケータ１１は、距離センサ９により検出される距離デ
ータ、および方位センサ１０により検出される方位変化
データをそれぞれ積算して走行軌跡データを算出し、走
行軌跡データと道路地図メモリ３Ａに格納されている道
路のパターンとの比較（いわゆるマツプマツチング法、
特開昭６４−５３１１２号公報参照）に基いて車両位置
を検出している。

なお、位置検出の精度をあげるためにビーコン受信機や
ＧＰＳ受信機を付加してもよい。

表示器１には、ＣＲＴ、液晶パネルなどの画面上に透明
のタッチパネル５が取付けられている。

各メモリ３Ａ、３Ｂは、大容量記憶媒体であるＣＤ−１
？ＯＮ、ＩＣメモリカード、磁気テープなどのメモリな
どから構成されている。

道路地図メモリ３Ａは、道路地図（高速自動車国道、都
市高速道路、一般国道、主要地方道、−般都道府県道、
指定都市の一般市道、その他の生活道路を含む）をメツ
シュ状に分割し、各メツシュ単位でノードとリンクとを
組み合わせたデータを記憶している。その他、鉄道、川
、地名欄、有名施設、運転者が予め登録した地点、等高
線などの表示用の背景データを含んでいてもよい。

上記メツシュは、日本道路地図を経度差１度、緯度差４
０分て分割し、縦横の距離を約８０に＋ａＸ　８０Ｋｍ
とした第１次メツシュと、この第１次メツシュを縦横８
等分し、縦横の距離を約１０ＫｍＸ　ＩＯＫｍとする第
２次メツシュ（第２図参照）との二重構造を持っている
。

ノードとは、一般に、道路の分岐点や折曲点を特定する
ための座標位置のことであり、分岐点を表わすノードを
分岐点ノード、道路の折曲点（分岐点を除く）を表わす
ノードを補間点ノードということがある。ノードデータ
は、ノード番号、当該ノードに対応する隣接メツシュの
ノードのアドレス、ノードに接続されるリンクのアドレ
スなどからなる。

各分岐点ノードを繋いだものがリンクである。

リンクデータはリンク番号、リンクの始点ノードおよび
終点ノードのアドレス、リンクの距離、リンクを通過す
る方向、その方向における所要時間データ、道路種別、
道路幅、一方通行や有料道路などの通行規制データから
なる。

このように、リンクデータの中にリンクの始点ノードお
よび終点ノードのアドレスが入っていることから、リン
クのみによっても地点を特定できる。なお、リンクによ
ってリンクの始点を特定する場合そのリンクを「退出リ
ンク」といい、リンクの終点を特定する場合そのリンク
を「進入リンク」という。さらに、リンクデータにはリ
ンクを通過する方向か入っているので、１つのリンクを
特定することにより、車両の進行方向も特定することが
できる。第４図は十字路を特定する４つの退出リンクを
、第５図は十字路を特定する４つの進入リンクを例示し
ている。

以下の実施例では、地点を特定するのに進入リンクを用
いるものとする。

経路メモリ３Ｂには、主要交差点、レジャー施設、駅、
駐車場、高速道路のオンランプまたはオフランプ、サー
ビスエリア、路側ビーコンなどに対応する特定のリンク
から、目的地点に対応する全てのリンクに至る最適経路
をそれぞれ設定された経路計算条件（最短時間経路、最
短距離経路、右左折の少ない経路、道路幅の広い経路な
ど）に応じてあらかじめ（例えば最適経路決定装置を工
場から出荷する前に）計算し、この最適経路のうち、上
記特定のリンクから、この最適経路が通る少なくとも次
の特定のリンクに至るまでの初期経路を構成するリンク
列を、当該特定のリンクおよび当該目的地点の属するメ
ツシュに対応させて記憶している。

さらに経路メモリ３Ｂの構造を図面および表を用いて詳
説する。第２図は１次メツシュＭ１およびこれに隣接す
る１次メツシュＭ２．Ｍ３を示す図である。道路に沿っ
た特定の地点は太い矢印で示す進入リンクＰ　ｉ　（ｉ
−０，Ｌ、２．・・・）により定義されている。１次メ
ツシュＭ１の中の１つの２次メツシュｍ１に出発地リン
クＰＯ（出発地点から最も近い特定のリンク）かある。

２次メツシュｍ１に隣接する２次メツシュをｍ２〜ｍ９
とし、２次メツシュｍ１に隣接しない２次メツシュを例
えばｍｌＯとする。また他の１次メツシュＭ２の中の任
意の２次メツシュをｍ２１、ｍ２２とする。

２次メツシュｍ１〜ｍ９を、第３図に拡大して示す。第
３図では、前述した特定のリンクＰｌのほか、特定のリ
ンクでない一般のリンクを小文字のｐ　１ｋ（ｋ−１，
２，・・・）で表わしている。

第３図を参照して、目的地が隣接２次メツシュ例えば２
次メツシュｍ２にある場合、各目的地（３つの目的地に
対応するリンクＱ　１．Ｑ　２．Ｑ　３のみ示す）まで
の最適経路Ｌ１を図示している。最適経路Ｌ１は、出発
地リンクＰｏおよびこれに続くリンクｐ　１１．　ｐ　
１２．　Ｐ　１からなる初期経路Ｊ１を共有している。

この場合、経路テーブルは、異なった目的地リンクＱｌ
、Ｑ２．Ｑ３ごとに一つの初期経路Ｊ１をそれぞれ記憶
している。

次に第２図を参照して、目的地が同一１次メツシュＭ１
にあるが隣接しない２次メツシュ例えば２次メツシュｍ
ｌｏにある場合、各目的地（２つの目的地に対応するリ
ンクＱ４．Ｑ５のみ示す）までの最適経路Ｌ２が出発地
リンクＰｏおよびこれに続くリンクり２１．　ｐ２２．
　ｐ２３．　Ｐ２からなる初期経路ｊ２を共有している
とする。この場合、経路テーブルは、当該２次メツシュ
ｍｌＯにある全ての目的地リンクＱ４．Ｑ５などをひと
まとめにして取扱い、これに対応して初期経路ｉ２を記
憶している。

目的地が他の１次メツシュ例えば１次メツシュＭ２にあ
る場合、各目的地（２つの目的地リンクＱ　６．Ｑ　７
のみ示す）までの最適経路Ｌ３が出発地リンクＰｏおよ
びこれに続くリンクｐ３１．　ｐ３２゜ｐ３３．　ｐ３
４．　Ｐ３からなる初期経路ｊ３を共有する場合、経路
テーブルは、当該１次メツシュＭ２にある全ての目的地
リンクをひとまとめにして取扱い、これに対応して初期
経路Ｊ３を記憶している。

以下経路テーブルの構成を説明する。経路テーブルは、
出発地リンクごとに定義される４種類のブロックを持っ
ている。この４種類のブロックは、１次メツシュブロッ
ク、２次メツシュブロック、リンクブロック、初期経路
ブロックである。１次メツシュブロックの数は１つの出
発地リンクに対して１つ、２次メツシュブロックの数は
１次メツシュの数だけ、リンクブロックの数は出発地リ
ンクを含む２次メツシュとこれに隣接する２次メツシュ
との数だけある。初期経路ブロックの数は１つであるが
、そこには、出発地リンクを始点とする全ての初期経路
のデータが入っている。

１次メツシュブロックは、各１次メツシュに対応させて
、他のブロックへのアドレスを持っている。具体的には
、出発地リンクをＰＯとすると、当該リンクＰＯが属す
る１次メツシュＭ１には、その１次メツシュＭ１に対応
する２次メツシュブロックの相対アドレスを持ち、当該
リンクＰＯが属さない１次メツシュＭ２などには、その
１次メツシュＭ２などに対応する初期経路データ（初期
経路ブロックに入っている）の相対アドレスを持ってい
る。１次メツシュブロックの例を第１表に示す。（以下
余白） 第１表 １次メツシュブロック ２次メツシュブロックも、各２次メツシュに対応させて
、他のブロックへのアドレスを持っている。具体的には
、出発地リンクＰＯが属する２次メツシュｍ１とこれに
隣接する２次メツシュｍ２〜ｍ９とには、その２次メツ
シュｍ１〜ｍ９に対応するリンクブロックへの相対アド
レスが対応し、２次メツシュｍ１に隣接しない２次メツ
シュンｍ１０、・・・には、その２次メツシュｍ１０．
・・・に対応する初期経路データの相対アドレスが対応
している。２次メツシュブロックの例を第２表に示す。

（以下余白） 第２表 ２次メツシュブロック リンクブロックは、各２次メツシュごとに設定されるも
のであって、そのリンクブロックが属する２次メツシュ
内の各リンクに対応して、出発地リンクＰｏから当該各
リンクに至る初期経路ブロックのアドレスが入っている
。２次メツシュｍ２に対応するリンクブロックの例を第
３表に示す。

第３表 リンクブロック （特定の９２２２０１１次メツシュＭｌ。

初期経路ブロックは、出発地リンクＰｏを始点とする全
ての初期経路のデータｊ　１．ｊ　２．Ｊ　３．・・・
が入っている。初期経路ブロックの例を第４表に示す。

第４表 初期経路ブロック （出発地リンクＰＯ） 次に上記構゛成の最適経路決定装置の動作を第２図、第
３図を参照しながら説明する。

初期設定手順は、以下の通りである。すなわち、画面に
入力した条件に合致する出発地点Ｐを含む道路地図が表
示されると、運転者は、道路地図を必要によりスクロー
ルさせて目的地点を捜し、目的地点の表示位置にタッチ
する。タッチされた位置は、初期設定部６に入力される
。また、初期設定部６は、ロケータ１１から出力される
車両の現在位置Ｐを記憶しておく。

処理部７は、出発地点Ｐから目的地点までの最適経路を
求める場合、初期設定部６からの情報に基づいて出発地
点Ｐに最も近い特定のリンク（第６図の場合リンクＰＯ
）と、目的地点に対応する目的地リンクを設定する。

上記のようにして、初期設定入力がなされた後、処理部
７は出発地点Ｐの表示地図に戻すとともに、経路メモリ
３Ｂに記憶されている経路テーブルの検索を行う。以下
、場合に別けて説明する。

（１）目的地リンクが他の１次メ・ソシュ例えば１次メ
ツシュＭ２にあるときは、処理部７はまず、メモリドラ
イブ４を通して経路メモリ３Ｂの１次メ・ノシュブロッ
クにアクセスし、メ・ソシュ番号Ｍ２ζこ対応する初期
経路プロ・ツクのアドレス＃Ｊ３を見つける（第１表参
照）。次に初期経路プロ・ツクにアクセスしてアドレス
＃Ｊ３に対応するデータｐ　３１．　ｐ３２．　ｐ　３
３．　ｐ３４．　Ｐ　３を取得する（第４表参照）。そ
の結果、出発地リンクＰＯをスタート地とする経路ｐ３
ｔ−＊　ｐ　３２−　ｐ　３３→ｐ３４を初期経路とし
て特定することができる。この経路は、後に説明するよ
うに表示器１に表示される。

■目的地リンクが同一１次メツシュ内で、隣接しない２
次メツシュ例えばｍｌＯ内にあるときは、処理部７は１
次メツシュブロックにアクセスし、メツシュ番号Ｍ１、
および２次メツシュプロ・ツク＃ｍ１０を探し出す（第
１表参照）。そして、これを手掛かりに２次メツシュブ
ロックにアクセスし、メツシュ番号ｍｌＯに対応する初
期経路ブロックのアドレス＃Ｊ２を得る（第２表参照）
。さらに、初期経路ブロックにアクセスしてアドレス＃
Ｊ２に対応するデータｐ２１．　ｐ　２２．　ｐ　２３
．　Ｐ　２を取得する（第４表参照）。

（３）目的地リンクが同一１次メツシュ内で同一の２次
メツシュまたは隣接する２次メツシュ、例えばｍ２内に
あるときは、処理部７は１次メツシュブロックにアクセ
スし、メツシュ番号Ｍ１、および２次メツシュブロック
＃ｍ２を探し出す（第１表参照）。そして、これを手掛
かりに２次メツシュブロックにアクセスし、メツシュ番
号ｍ２に対応するリンクブロックを探し出す。そして、
このリンクブロックに入っている目的地リンク、例えば
Ｑ２にアクセスして初期経路プロ・ツクのアドレス＃Ｊ
１を得る（第３表参照）。さらに、初期経路ブロックに
アクセスしてアドレス＃Ｊ１に対応するデータｐＨ，ｐ
１２、Ｐｌを取得する（第４表参照）。

以上のようにして、遠近どの位置にある目的地に対して
も、経路テーブルを検索して初期経路データを取得する
ことができる。

さらに、同一１次メツシュ内で、隣接しない２次メツシ
ュにあるやや遠い目的地に対しては、第２表で示したよ
うに、２次メツシュごとに１つの初期経路を記憶させ、
異な９た１次メ・ソシュにある遠い目的地に対しては第
１表で示したように１次メツシュごとに１つの初期経路
を記憶させることとした。これにより、メモリの容量の
大幅な節約を図ることができる。

ただし、同一１次メツシュ内で、同一または隣接２次メ
ツシュにある近い目的地に対しては、初期経路をまとめ
て記憶させることはしなかったが（第３表から分かるよ
うに異なった目的地Ｑｌ。

Ｑ２．Ｑ３に対して同一の初期経路ブロックのアドレス
＃Ｊ１が重複して記憶されている）これは、同一または
隣接２次メツシュの範囲が限られているので記憶データ
量は少なくて済むと考えたからである。しかし、これら
の目的地に対して初期経路がまとまれば、遠い目的地に
対するのと同様に１つの情報にまとめることも勿論可能
である。

以上説明した実施例において、問題があるとすれば、果
たして他の１次メツシュ内の全ての目的地リンク、ある
いは他の隣接しない２次メツシュ内の全ての目的地リン
クが同一の初期経路を共有するとは限らないのではない
かということである。

しかし、この場合でも、最も多数の目的地リンクが共有
する初期経路を当該メツシュ内の全ての目的地リンクに
対応する初期経路とみなすこととする。このような多数
決原理を導入すれば、一部の目的地にとって、みなされ
た初期経路は最適経路の一部とはならないが、各目的地
が出発地から見て同一方面に位置している以上、上記多
数決で決定された初期経路が最適経路から大きく外れる
ことは有り得ないので実用上支障はないと考えられる。

なお、上記の場合、多数決以外にも、メツシュ内の代表
的な地点を定めて、この地点が持っている初期経路をそ
のメツシュに対応する初期経路としてもよい。また、初
期経路を一意的に決めることをせず、複数の初期経路を
表示して運転者に判断させることも考えられる。

以上のようにして特定のリンクを出発地とした初期経路
が得られたのであるが、この初期経路を走破するまでに
（例えば交差点の信号待ち時間を利用してもよく、出発
前の時間を利用してもよい）、処理部７は、当該初期経
路の終点となる次の特定のリンクを出発地リンクとして
同様の手順により初期経路データ読み出すことにより、
次の初期経路を得ることができる。以下、同様にして次
々と初期経路を取得し、最後には、目的地リンクまでの
すべての経路データを得ることができる。

なお、上記の場合において、車両の最初の位置Ｐから最
初の特定のリンクＰ１までの経路は、経路テーブルに入
っていないので、ただちに運転者に示すことは出来ない
が、通常短い距離なので従来どおりの方法で経路計算す
れば比較的短時間で最適経路を得ることができるので問
題ない。近くなので運転者が迷うおそれがなければ、経
路計算をしないで特定のリンクＰｉを示すだけでよいか
もしれない。

また、目的地点および出発地点間の距離が短い場合は、
経路テーブルに上記初期経路を記憶させず、直接経路計
算等をすることとしてもよい。目的地点および出発地点
間の距離が短い場合まで記憶するとメモリの容量が増大
し、かつ、目的地点および出発地点間の距離が短いと経
路計算時間はさほど長くならないからである。

第６図は車両を最適経路に沿って誘導する経路誘導フロ
ーを示す図である。ステップＳ１において、道路地図メ
モリ３Ａから車両の現在位置を中心とした表示すべき領
域内の表示地図を得、ステップＳ２において、上記表示
地図を所定の拡大率に従いフレームメモリの上に描画す
る。そしてステップＳ３において経路メモリ３Ｂから、
前述したような手順で初期経路のデータを取得する。

ステップＳ４では、表示すべき初期経路が取得されたか
どうか調べ、初期経路が取得されていないとき（このよ
うなことは前述したように目的地点および出発地点間の
距離が短く経路テーブルに初期経路が記憶されていない
時に起こる。）には、ステップＳ７に進み、車両の現在
位置マークのみをフレームメモリの上に描画し、ステッ
プＳ８においてフレームメそりの内容をデイスプレィに
表示する。この時、通常どおり経路計算を行って算出さ
れた経路を表示するようにしてもよい。

ステップＳ４で、表示すべき初期経路が求まっていれば
、ステップＳ５において現在描画されている道路表示用
地図の上に、初期経路をリンク列で描画する。そしてス
テップＳ６において、方向ベクトルを用いて、初期経路
を道路沿いに表示させる。

以上のようにして、道路地図データに主要交差点、レジ
ャー施設、駅、駐車場、高速道路のオンオフランプエリ
ア、サービスエリア、ビーコンなどに対応して設けられ
た特定地点を表わすリンクをそれぞれ出発地として、各
目的地リンクごとに、当該目的地リンクまでの最適経路
をあらかじめ計算し、その最適経路の全部ではなく一部
である初期経路のみをＣＤＲＯＭ、ＩＣカード、ＤＡＴ
あるいはカセットテープなどの経路メモリ３Ｂに記憶し
ておくことにより、運転者が目的地を入力して走行すれ
ば車両が特定地点を通過してから後は、この経路テーブ
ルを利用して即座に目的地に至る初期経路を検索して表
示することができる。そして、当該初期経路を完走する
までに、次の特定地点を始点とする初期経路を検索して
表示し、以下、同様の措置を繰返して、最終の目的地点
までの最適経路を画面に表示することができる。

さらに、初期経路を共通にする目的地同士をまとめ、こ
れらの目的地の集合（地域）に対して１つの初期経路を
記憶させたので、初期経路を記憶するメモリの容量は、
大幅に節約される。

以上実施例に基づいて本発明を説明してきたか、本発明
はこれに限定されるものではない。例えば、上記実施例
では、初期経路を共通にする目的地をまとめるのにメツ
シュ構造を用いたが、第７図に示すように、出発地であ
る特定のリンクからの直線距離ｒと方位θとを用いるこ
とも可能である。

例えば同図に示すようにｒｌ＜ｒ２＜ｒ３として、直線
距離ｒ≦ｒ１の場合は、初期経路をまとめることはせず
、ｒｌ＜ｒ≦ｒ２の場合は一定角度θ１ごとに区分した
扇形エリアとし、 ｒ２＜ｒ≦ｒ３の場合はθ１より大きな一定角度θ２ご
とに区分した扇形エリアとし、ｒ３＜ｒの場合はさらに
大きな一定角度θ３ごとに区分したすることも可能であ
る。

以上の実施例は、出発地リンクから遠方になるにつれて
、初期経路をまとめる地域を一定の法則扇形エリアとに
従って大きくしていく例であるが、目的地に到達するま
での経路が高速道路を含む場合、第８図に示すように、
高速道路のオフランプに着目して近傍の地域をまとめる
ことも可能である。この場合、地域をまとめる方法は、
実際の経路計算を行って、同じオフランプを利用する地
域を１つにまとめればよい。

また、上記各実施例では、地点を特定するのに、退出リ
ンクを用いていたが、退出リンクでなく進入リンクを用
いてもよい。またノードを用いてもよい。

また、道路地図データは大小全ての道路に関するリンク
またはノードで構成されているとしていたが、リンク数
、ノード数が多くて経路メモリ３Ｂの容量が不足すると
いううことになれば主要幹線道路だけのリンク、ノード
データで構成してもよい。

その池水発明の要旨を変更しない範囲内において、種々
の設計変更を施すことが可能である。

〈発明の効果〉 以上のように、本発明の請求項１の最適経路決定装置に
よれば、各特定の地点から、各目的地点に至る最適経路
をそれぞれあらかじめ計算し、その最適経路のうちの最
初の一部を初期経路として、各特定の地点および各目的
地点に対応して経路テーブルに記憶させているので、運
転者の目的地の設定に応じて、この初期経路を経路テー
ブルから検索して運転者に示すことができる。そして、
その後、上記初期経路の終点である特定の地点を始点と
する、次の初期経路も同様の手順で経路テーブルから検
索することができるので、結局１何ら計算を要すること
なく短時間で、最終目的地までの最適経路を決定して、
運転者に示すことができる。

また、上記経路テーブルが、異なった目的地点に対して
、同一の初期経路に関する情報を記憶する場合、当該具
なった目的地点を含む地域に対応させて、当該初期経路
に関する情報を記憶させているので、経路テーブルの容
量を大幅に節約することができる。

また、請求項２の最適経路決定装置においても、各出発
地点から、各特定の地点に至る最適経路をそれぞれあら
かじめ計算し、その最適経路のうちの最後の一部を終期
経路として、各特定の地点および各出発地点に対応して
経路テーブルに記憶させているので、運転者の目的地等
の設定に応じて、この終期経路を経路テーブルから検索
して運転者に示すことができる。そして、その後、上記
終期経路の始点である特定の地点を終点とする、次の終
期経路も同様の手順で経路テーブルから検索することが
できるので、結局、何ら計算を要することなく短時間で
、最初の出発地からの最適経路を決定して、運転者に示
すことができる。

この場合、上記経路テーブルが、異なった出発地点に対
して、同一の終期経路に関する情報を記憶する場合、当
該具なった出発地点を含む地域に対応させて、当該終期
経路に関する情報をまとめて記憶させれば、経路テーブ
ルの容量を大幅に節約することができるのも請求項１の
発明と同様である。

【図面の簡単な説明】

第１図は本発明の最適経路決定装置を実施するための経
路誘導装置を示すブロック図、第２図は経路テーブルの
構造を説明するためのメツシュ地図、 第３図は部分拡大図、 第４図、第５図はそれぞれ十字路における退出リンク、
進入リンクの例を示す図、 第６図は車両誘導フローを示す図、 第７図はメツシュの代わりに極座標で区分した地図、 第８図は高速道路のオフランプ近傍の地域を示す地図で
ある。 Ｐ・・・出発地点、 Ｐｏ・・・出発地リンク、Ｑｊ・・・目的地リンク、３
Ａ・・・道路地図メモリ、３Ｂ・・・経路メモリ、６・
・・初期設定部、 ７・・・処理部（初期経路取得手段） 特許出願人　　住友電気工業株式会社 代　　理　　人　　　弁理士　　亀　　井　　弘　　勝
（ほか２名） 第３図 第４図 第５図 第６図 第７図 第８図 地域

Claims (4)

【特許請求の範囲】
1. １．運転者による目的地点などの設定に応じて、道路地
   図メモリから出発地点と目的地点とを含む範囲の道路地
   図データを読出し、この道路地図データに基づいて出発
   地点から目的地点に至る最適経路を決定する最適経路決
   定装置において、 上記道路地図において、一定の基準により選定された複
   数の特定の地点を出発地として各目的地点に至る最適経
   路をあらかじめ計算しておき、上記出発地となる特定の
   地点から、この最適経路が通る少なくとも次の特定の地
   点に至るまでの初期経路に関する情報を、当該目的地点
   および当該出発地となる特定の地点に対応させて記憶し
   た経路テーブルと、 目的地点を設定するとともに、車両の現在位置に近い特
   定の地点および最適経路に沿った特定の地点を設定する
   初期設定手段と、 上記初期設定手段による目的地点の設定および特定の地
   点の設定に応じて経路テーブルを検索し、初期経路に関
   する情報を取得する初期経路取得手段とを含み、 上記経路テーブルは、異なった目的地点に対して、同一
   の初期経路に関する情報を記憶する場合、当該目的地点
   の集合に対応させて、当該同一の初期経路に関する情報
   を記憶していることを特徴とする最適経路決定装置。
2. ２．運転者による目的地点などの設定に応じて、道路地
   図メモリから出発地点と目的地点とを含む範囲の道路地
   図データを読出し、この道路地図データに基づいて出発
   地点から目的地点に至る最適経路を決定する最適経路決
   定装置において、 上記道路地図において、一定の基準に基づいて選定され
   た複数の特定の地点を目的地として各出発地点からの最
   適経路をあらかじめ計算しておき、上記目的地となる特
   定の地点と、この最適経路が通る少なくとも次の特定の
   地点との間の終期経路に関する情報を、当該出発地点お
   よび当該目的地となる特定の地点に対応させて記憶した
   経路テーブルと、 出発地点を設定するとともに、旅行の目的地に近い特定
   の地点および最適経路に沿った特定の地点を設定する初
   期設定手段と、 上記初期設定手段による出発地点の設定および特定の地
   点の設定に応じて経路テーブルを検索し、終期経路に関
   する情報を取得する終期経路取得手段とを含み、 上記経路テーブルは、異なった出発地点に対して、同一
   の終期経路に関する情報を記憶する場合、当該出発地点
   の集合に対応させて、当該同一の終期経路に関する情報
   を記憶していることを特徴とする最適経路決定装置。
3. ３．道路地図データがノードとリンクとの組み合わせか
   らなるものであり、道路地図上の地点をノードまたはリ
   ンクにより特定することを特徴とする請求項１または２
   記載の最適経路決定装置。
4. ４．上記経路テーブルは、目的地点、出発地点間の距離
   が一定の基準値よりも長い場合にのみ、上記初期経路ま
   たは終期経路に関する情報を記憶していることを特徴と
   する請求項１または２記載の最適経路決定装置。