JPH1089987A

JPH1089987A - 道路セグメントデータベースを使った交差点ルーチング用ナビゲーションシステム

Info

Publication number: JPH1089987A
Application number: JP9217149A
Authority: JP
Inventors: Satoshi Tanimoto; 敏谷本
Original assignee: Alpine Electronics Inc
Current assignee: Alpine Electronics Inc
Priority date: 1996-07-30
Filing date: 1997-07-28
Publication date: 1998-04-10
Anticipated expiration: 2017-07-28
Also published as: US5893898A; JP3769104B2

Abstract

(57)【要約】【課題】【解決手段】道路網データベースが道路セグメントで
構成され、かつ、目的地が道路交差点である時に好適な
車両ナビゲーションシステムの経路探索システムであ
る。案内経路の目的道路セグメントとして目的交差点か
ら進入できるセグメントを選択する。これにより目的交
差点へ向けてのみの一方通行を許す道路セグメントが目
的道路セグメントとして選択されなくなる。すなわち、
目的交差点へ向けてのみの一方通行を許す道路セグメン
トを通らない最適経路の選択ができるようになる。別の
改善は目的道路セグメントフィルタリングであり、移動
距離が零の目的道路セグメントを選択したことが判明す
ると、該目的道路セグメントを案内経路から削除し、代
わりに、案内経路における直前の道路セグメントの端点
を目的地として指示する。これにより、目的地に到着し
た際に、不必要な指示がドライバに与えられなくなる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はナビゲーションシス
テムに係わり、特に、道路やハイウェイ上のルート（経
路）を選択する車載ナビゲーションシステムに係わり、
更に、２つの道路交差点上の目的地へルーチングする道
路セグメントデータベースを使った経路誘導に関する。

【０００２】

【従来の技術】車載ナビゲーションシステムは周知であ
り、例えば、道路交差点などの道路情報を記述するデー
タベースを使用した経路探索システムに関するYamada
の米国特許4,926,336を参照されたい。又、道路地図座
標における車両位置を決定するために、道路地図データ
メモリに格納されている道路セグメントを探索する車載
ナビゲーション/位置決めシステムに関するLink et al.
の米国特許5,270,937号を参照されたい。

【０００３】車載ナビゲーションシステムはデータベー
スに格納されている道路情報を必要とする。道路情報
は、しばしば、セグメントの形式を有し、かかる形式に
おいて道路セグメントは２つのノード間の道路の長さで
ある。典型的には、ノードは他の道路との交差点あるい
は州境、国境のような人的境界線との交差点である。デ
ータベースに格納されている情報は、経路案内や道路を
示す地図を描画する目的のために地理的エリア内の各道
路を記述している。データベースに道路情報を格納する
ために２つのフォーマットが使用される。第１のフォー
マットは、例えば、合衆国において好ましいもので、道
路セグメントに基づいたデータベース（道路セグメント
基本データベース）で、道路情報は道路セグメントに関
係する。

【０００４】他のフォーマットは、交差点（ノード）に
基づいたデータベース（ノード基本データベース）であ
り、該データベースにおいて格納されている情報の重要
度はノード（交差点）にあり、道路はノード間のコネク
ション（結合）として定義されている。地理的エリアに
おいて、ただ１種類のデータベースしか利用できず、２
種類のデータベースを利用できないことは普通のことで
ある。なぜならば、そのようなデータベースは第三者の
商用的サービスによって提供され、特別の地理的エリア
に２種類のデータベース提供することは経済的に不可能
であるからである。ナビゲーションシステムのためのノ
ード基本データベースの例は、アルパイン株式会社に譲
渡されたIshikawa の米国特許 5,410,485号(図２０参
照）に開示されている。ナビゲーションシステムのため
のセグメント基本データベースの例は、ETAK 株式会社
に譲渡された Loughmiller, Jr et al の米国特許4,91
4,605号(第１２カラム、第４６行目以降及び図６Ａ参
照）に開示されている。

【０００５】それ故、ナビゲーションシステムにとっ
て、セグメント基本データベースで操作することが要求
されることは普通のことである。ほとんどの場合、その
ようなナビゲーションシステムは満足的に動作する。し
かし、目的地が道路交差点である時、そのようなセグメ
ント基本データベースの環境下では次善のパーフォーマ
ンスが与えられるだけであることがわかった。

【０００６】

【発明が解決しようとする課題】本願発明者は、目的地
が道路交差点上にある場合、道路セグメント基本データ
ベースを備えたナビゲーションシステムにおける経路探
索プロセスの第１の欠点を発見した。データは道路セグ
メントの形式で格納されているから、定義される目的地
は特別の道路セグメント上に、例えば道路セグメントの
端点に存在しなければならず、２つの道路セグメントの
端点として定義される交差点上には存在できない。これ
は、交差点がセグメント基本データベースでは認識でき
ないからである。

【０００７】目的交差点が幾つかの道路セグメントの交
差点であり、少なくとも１つの道路セグメントがその交
差点に対して一方通行である場合に問題が存在する。こ
の場合、もし、経路案内のために目的道路セグメントと
して一方通行の道路セグメントが選らばれると、この一
方通行道路セグメントを必ず通るように目的交差点への
経路を指示する。これは次善の経路選択に帰し、例え
ば、経路が長くなる。なぜならば、目的交差点に向けて
一方通行である目的道路セグメントは該目的交差点から
進入（アクセス）できず、このため目的交差点以外の端
点を通るように経路を決定しなけれなならないからであ
る。

【０００８】第２の問題は目的地が交差点であるときに
生じる。ユーザを目的交差点へ誘導するナビゲーション
システムは、ドライバが実際に目的交差点に向けて接近
しつつある道路セグメント以外の道路セグメントを目的
道路セグメントとして指示することがある。かかる場
合、経路案内は、ドライバが実際に目的地に到達し、か
つ、おそらくは最後の目的道路セグメント上をわずかな
距離移動した時に、彼が目的地に到達したことを示すだ
けである。かかる経路案内はドライバに不必要な操縦を
強い、ドライバをして実際に欲している交差点を余儀な
く通過させるかもしれない。換言すれば、システムは目
的道路セグメント上の運転距離が零であることを指示す
るであろうが、このことが交差点を横切る必要がないこ
とを意味しているとユーザに教えない。

【０００９】

【課題を解決するための手段】これらの欠点の認識と明
確な記述が解決に導く。目的セグメントが一方通行であ
る最初の問題の解決策は、経路探索において目的交差点
から進入可能（アクセス可能）な道路セグメント、すな
わち、目的交差点から進入することが可能な道路セグメ
ントを目的道路セグメントとして選択することである。
従って、目的交差点から進入可能な一方通行道路セグメ
ントと、目的交差点へ及び目的交差点からの両方向に移
動可能な道路セグメントが目的道路セグメントとして選
択可能であり、システムは目的交差点へ向けてのみ移動
可能な道路セグメントは目的道路セグメントから除外す
る。換言すれば、システムは、目的交差点で終端しなが
ら目的交差点からアクセスできない道路セグメントは目
的道路セグメントから除外する。上記方法は最適経路が
途中において問題にしている一方通行道路セグメント通
って目的セグメントに至ることを阻害しない。すなわ
ち、上記方法は経路を選択するために目的セグメントと
して一方通行道路を使用しないことをシステムに要求す
るだけである。

【００１０】第２の問題、すなわち、移動距離が零であ
るとする目的道路セグメント上の移動の問題は本発明に
よれば、目的道路セグメントの移動距離が実際に零であ
るか否かを決定することにより扱われる。もし、零であ
るならば、目的道路セグメントは案内経路から除外され
る。すなわち、案内経路リストから除去される。これら
２つの解決策は経路案内を簡潔化し、ナビゲーションシ
ステムのユーザに対してより明確な経路案内を提供し、
しかも、ユーザの混乱を軽減し、それゆえ、ナビゲーシ
ョンシステムをより有益なものにする。

【００１１】

【発明の実施の形態】図１は本発明により使用されるナ
ビゲーションシステムの簡単なブロック図であり、例え
ばLink 等に付与された米国特許5,270,937号に示されて
いるタイプのブロック図である。この図は単にナビゲー
ションシステムを説明するために企図されているだけで
あり、種々のそのようなナビゲーションシステムは技術
分野で周知であり、本発明は一般的に経路決定すなわち
経路案内の目的でそれらシステムに適用できる。そのよ
うなナビゲーションシステムは２つのメインの内部的に
関連付けられた機能を有することが理解される。その１
つの機能は現車両位置の周辺の地図をユーザに表示する
こと、及び、第２の機能は出発地から目的地までの経路
に関するガイダンス（案内）を与えることである。第２
の機能は一般に経路案内または経路選択と呼ばれてい
る。経路は種々のパラメータの１つ、例えば、最小移動
時間、最小移動距離、ハイウェイの最大使用数、道路ネ
ットワーク上の車両移動に関係するその他のパラメー
タ、の１つによって最適化される。

【００１２】図１のシステムは、中心要素としてナビゲ
ーション／位置付けコンピュータ１０を含んでいる。こ
のコンピュータ１０は典型的にマイクロプロセッサと、
ＲＡＭと、入出力回路等のプロセッサ関連回路を備えて
いる。コンピュータ１０には、車両に装着されたユーザ
制御パネル１２が接続されると共に、ＧＰＳシステム、
ジャイロスコープ、及び車両オドメータ／速度メータの
ような１組の距離／方向／位置センサー１６が接続され
ている。又、ハードディスクドライブまたは光学ディス
クドライブまたは不揮発性のコンピュータ読み込み可能
な媒体で構成される地図データ記憶媒体２０及びユーザ
のためのディスプレイ１８が設けられている。

【００１３】ナビゲーション／位置付けコンピュータ１
０はコンピュータプログラムにより動作する。このコン
ピュータプログラムは、例えば、コンピュータ内に常駐
し、かつ、一連の指令としてマイクロプロセッサ及びま
たはマイクロコントローラにより実行されるコンピュー
タソフトウェアである。本発明の方法及び装置はそのよ
うなコンピュータソフトウェアで実現される。本発明の
説明では実際のコンピュータコードを示さないけれど、
そのようなコンピュータコードは発明が属する技術分野
における通常の知識を有するものであれば本説明から書
くことができる。又、実際のナビゲーションシステムに
おいてコンピュータコードはコンピュータプログラムの
形式を備え、コンピュータ読み込み可能メモリ（例えば
ハードディスク、フロッピーディスク、光学ディスク）
に記憶され、記憶媒体２０に常駐してもよいし、しなく
てもよい。

【００１４】図２は道路セグメントが何を意味している
か示す。図２はそれぞれが他の道路と交差する直線とし
ての一組の道路群を示し、２つの水平道路Ａ，Ｂの各々
はそれぞれセグメント１０、１２、１３及びセグメント
６、１、３、８、１１である。又、州境、例えばカリフ
ォルニアとネバダの州境が示されており、該州境は道路
Ａ，Ｂによって横切られている。定義において、セグメ
ントは２つの交差点間あるいは１つの交差点と州境間の
道路部分であるから、道路Ａは州境のおのおのの側にセ
グメント１２、１３を含んでいる。更に、どのようにセ
グメント基本データベースが構成されるかが以下に記述
される。

【００１５】図２はリンクされた一連の道路セグメント
で道路Ａ，Ｂを定義し、道路セグメントでリンクされた
一連の交差点で道路Ａ，Ｂを定義していない。これが道
路セグメント基本データベースと交差点（ノード）基本
データベース間の相違点である。

【００１６】図３は本発明者により発見され、本発明に
より取り組まれる上記第１の問題を説明する。問題は交
差点型経路誘導、すなわち、交差点である目的地（目的
交差点）への車両の経路誘導が、特別のノードポイント
に車両を誘導することを要求することである。このこと
は、交差点基本データベースである地図データベースを
使用して交差点型経路誘導が実行されるとき、もちろん
問題ではない。しかしながら、セグメント基本データベ
ースの形式である道路データを使用して交差点型経路誘
導が実行される状況では問題であり、本発明はかかる問
題に取り組む。

【００１７】この場合、経路誘導の目的で、上記目的交
差点に接続する道路セグメントの１つを目的道路セグメ
ントとして選択しなければならない。図３に示すよう
に、目的交差点Ｎはそれに接続する４つの道路セグメン
ト１，２，３，４，５を有している。矢印は道路セグメ
ント１上において交差点Ｎ方向の一方通行が許されてい
ることを示し、道路セグメント３上では交差点Ｎから離
れる方向の一方通行が許されていることを示す。かかる
状況において、交差点型経路誘導及び道路セグメント基
本データベースを使用する場合において、ユーザが目的
交差点Ｎに移動することを望んだならば、ナビゲーショ
ンシステムは目的道路セグメントとして道路セグメント
１を選択すべきでない。

【００１８】道路データにおいて、一方通行道路セグメ
ントは一方通行ストリートのように通常考えられている
ものに限定されないことが理解されるべきである。セグ
メント基本データベースは、対向車線のセンターライン
が互いに十分に離れている場合、各車線は一方通行とみ
なす。それゆえ、ノース／サウス高速道路において、北
行きの車線は一方通行セグメントとしてみなされる。ま
た、中央に細長い土地をを有する大通りのような分割道
路において、各サイドは一方通行セグメントとみなされ
る。更に、両方向通行が可能な非分割道路であっても、
道路の両側が十分に離れていれば各サイドは一方通行と
みなされる。これは、道路情報が実際の道路網の航空写
真からデジタイジングプロセスにより得られるものであ
るからである。

【００１９】もし、ナビゲーションシステムがセグメン
ト１を案内経路の目的道路セグメント（最終道路セグメ
ント）として選択したならば、目的交差点Ｎへの接近方
向は１方向、すなわち、道路セグメント１の一方通行方
向に固定される。このため、セグメント基本データベー
スを使った交差点型経路誘導では、非最適ルートに沿っ
て経路誘導され、必要以上に長い距離で目的交差点Ｎに
経路誘導される場合がある。

【００２０】この問題は、交差点Ｎから該交差点と反対
方向への移動を許す道路セグメントを目的道路セグメン
トとして選択することにより解決される。これによれ
ば、目的交差点Ｎへの接近道路セグメントを限定しな
い。換言すれば、セグメント１は目的交差点Ｎから進入
できず、案内経路の目的道路セグメント（最終道路セグ
メント）として選択されない。それゆえ、図３は本発明
者により発見された第１の問題と、目的道路セグメント
としてセグメント２、３、４または５のいずれかを選択
すべきであるとする本発明の解決策の両方を説明してい
る。この方法及び関連する装置がより詳細に後述され
る。

【００２１】図３において明らかなように、交差点Ｎは
ノードポイントＮＤＰＴ２２，ＮＤＰＴ１２，ＮＤＰＴ
４１，ＮＤＰＴ３１，ＮＤＰＴ５１に対応し、各ノード
ポイントは対応する道路セグメントの端点におけるノー
ドである。すなわち、ＮＤＰＴ２２は交差点Ｎでのセグ
メント２の端点である（”ＮＤＰＴ”はノードポイント
を意味する）。交差点Ｎはそれ自身データベースに記入
されておらず、この位置を明確にすることは説明上の便
宜のために過ぎない。それゆえ、交差点Ｎで終端する各
道路セグメントに関連して１つのノードが指示される。
図３は、例えば道路１が道路セグメント２、４を含み、
道路２が道路セグメント１、３を含んでいることを示
す。

【００２２】図４はテーブル形式で、図３で示された幾
つかのエレメントに相当する道路セグメント基本データ
ベースの一部分を示すものである。最初のカラムは、デ
ータベースにおけるアルファベットオーダの道路名、例
えば、カリフォルニアの全道路（ほとんどは説明のため
に図示されていない）をりストアップする。カリフォル
ニアの道路の１つである道路２は、道路データである第
２のカラムにリストされたデータにより定義されてい
る。道路２の道路データカラムにおける最初の項目は道
路名称または道路識別名（”道路２”）である。これは
典型的に道路の共通名、例えば、政府機関により指定さ
れた名前である。道路データカラムにリストされた残り
の項目は通常の道路を構成する道路セグメントであり、
各道路は通常、１つの交差点から次の交差点あるいは州
境に延びる多数のセグメントを有している。道路データ
カラムにおける道路セグメント１は図４の第３カラムに
示されるデータによって定義される。図４より、道路セ
グメント１はノードポイントＮＤＰＴ１１からノードポ
イントＮＤＰＴ１２に延びる。道路セグメントデータリ
ストテーブルにおける次のデータは道路セグメントに沿
ってどの方向の移動が許されているかの指示であり、道
路セグメントデータリストにおける最後のデータはマイ
ルで表現された道路セグメントの長さである。尚、この
リストにおける"Only right"はＮＤＰＴ１１→ＮＤＰＴ
１２方向の一方通行を意味している。

【００２３】図５は図３で示した問題をより詳細に説明
しており、目的交差点ＮがノードＮＤＰＴ１２の道路セ
グメント１上に存在する。この場合、道路セグメント
１、３に沿って許される移動方向は再び矢印で示され
る。この場合、ひとたび道路セグメント１が目的道路セ
グメントとして指定されると、出発地から目的交差点Ｎ
までの認められた案内経路は出発地がどこにあるかに関
係なくセグメント１に沿って移動しなければならない。
それゆえ、案内経路は点線で示すように、明らかに距離
的には最適でない経路となる。従来例では、経路案内の
ための道路セグメントリストは図６に示される。図６に
おいて、道路セグメントリストの最終データはＮＤＰＴ
１１からＮＤＰＴ１２までのセグメント１に係り、(1)
セグメント１に沿って許される移動が一方通行移動（”
only right")であること、(2) 道路セグメント長が１．
５マイルであること、(3) セグメント１に沿ってＮＤＰ
Ｔ１２までの運転距離が１．５マイルであること、を有
している。尚、図６におけるセグメントリストは説明の
都合上実際に存在する他の道路セグメントを省略してい
る。

【００２４】明らかに、上述したように、案内経路は非
最適ルートであるため、不満足な案内経路である。それ
ゆえ、本発明者は上述したような解決策、すなわち、目
的地が存在する道路セグメント（目的セグメント）とし
て道路セグメント１以外の道路セグメントを選ぶ解決策
を提供した。

【００２５】本発明にしたがって経路案内を実行するた
めのコンピュータプログラムのためのフローチャートが
図７（Ａ），（Ｂ）に示される。このフローチャートは
図解的であるが限定されるものではない。更に、経路案
内の一般的な問題は周知であり、種々の解決策があるこ
と、並びに、全体の経路案内プロセスは図７（Ａ），
（Ｂ）に図解されておらず、発明の説明に関係する部分
のみ示されている。かくして、図７（Ａ），（Ｂ）に図
解されたプロセスは多くの複雑な、しかし、慣用的なス
テップで満たされており、例えば、(1) 最適経路の実際
の探索ステップ、(2) 最適経路の表示ステップを含んで
いる。これらのステップは技術分野で周知であるのでそ
れらを達成するための多くの異なった方法があり、ここ
では詳細には記述しない。

【００２６】交差点ルーチングプロセスはステップ３０
のスタートで始まる。ユーザは目的地を交差点またはア
ドレスまたはＰＯＩ（着目ポイント）により選択するこ
とができる。図７（Ａ）はユーザが交差点経路案内を選
択したと仮定している。ステップ３２において、システ
ムはディスプレイ１８を介してユーザ（車両ドライバ）
が目的地をcity(市)、またはストリート(street)で指定
することを望んでいるか質問する。尚、本発明は車両シ
ステムに限定しないが最もそれに適用可能である。

【００２７】ユーザは制御パネル１２を介してcity ま
たはstreet をステップ３２で応答する。もし、ユーザ
がcity を入力すれば、ステップ３４においてユーザは
望ましい市の名前を入力することを要求される。市名を
入力すれば、サーチ範囲が指示された市に狭められる。
さもなければ、州の全市がサーチ対象となる。もちろ
ん、サーチの範囲は、地図記憶媒体２０のデータベース
によってカバーされている地理的エリアに依存する。も
し、ステップ３２において、street が選択されるとス
テップ３６においてユーザはシステムにより第１、第２
のstreetを入力することが求められる。この第１、第２
のstreetは望ましい交差点で交わり、目的交差点を指示
する。ここで、ステップ３８においてシステムはそのよ
うな交差点のためにデータベースをサーチし（ステップ
４０）、もし、そのような交差点（入力された第１、第
２のstreetが交差する交差点）が存在すれば、システム
は該交差点を決定し、ステップ４２に進む。もし、その
ような交差点がなければ、ステップ４６において「有効
な目的地なし」をディスプレイ１８で表示してユーザに
通知し、これにより、ユーザは再びステップ３０から開
始することができる。

【００２８】もしそのような交差点が存在することをシ
ステムが決定したならば、ステップ４２において、シス
テムは前記第１、第２のストリート名の交差点が１つし
かないかチェックする。もし、１つしかなければ、ステ
ップ５０に進み、もし、２以上存在すれば、ステップ４
８において、ユーザに１つの交差点を選択するように求
める。かかる事態は、例えば同一ストリート名がデータ
ベース内で何回も発生するときに、生じる可能性があ
る。また、もしステップ３４において市を指定すること
をスキップすれば、多くの市をカバーするデータベース
をサーチし、そのような場合に異なった市に同一名称の
交差点が存在するかも知れない。

【００２９】ユーザがどの交差点を対象交差点とするか
ステップ４８で指示し、あるいは、ステップ４２におい
てシステムがそのような交差点が１つしかないと決定し
た後、ステップ５０に進む。システムはまだどの道路セ
グメントが最適経路上に存在するか決定してない。すな
わち、システムは最適経路をまだサーチしてない。そこ
で、ステップ５０において、システムは、目的交差点上
のノード（端点）を有する全道路セグメントを探索す
る。図３を参照すると、目的交差点である交差点Ｎは、
該交差点まで延びる５つのセグメント１、２、３、４、
５を有している。それゆえ、セグメント１、２、３、
４、５及び交差点Ｎに位置するそれらセグメントの関連
ノードについて目的道路セグメントリストが編集され
る。

【００３０】ついで、ステップ６０において、本発明の
目的セグメント選択プロセスが始まり、願わしくない道
路セグメントがステップ５０で編集されたリストから除
去される。すなわち、ステップ６０において示されるよ
うに、セグメントの除去は、ステップ５０で編集された
目的道路セグメントリストをサーチし、目的交差点Ｎか
ら進入できない（アクセスできない）セグメントを求め
ることにより行われる。例えば、セグメント１は一方通
行であり、目的交差点Ｎより進入できないため上記サー
チで求まり、リストから除去される。

【００３１】ステップ６０に対して補足的な次の処理は
ステップ６２であり、このステップにおいて、目的道路
セグメントリストの残りの道路セグメント、すなわち、
セグメント２、３、４、５のいずれか１つが任意に目的
道路セグメントとして選択される。それから、ステップ
６４において、１つのパラメータを使った周知の最適経
路探索が始まる。パラメータとしては、例えば、最短移
動時間あるいは最短距離、あるいは高速道路の最多使
用、その他効果のある道路移動の慣用的な手法等があ
る。もちろん、ステップ６４における探索経路はステッ
プ６２で決定された目的道路セグメントを有している。

【００３２】ステップ６８において、出発地から目的道
路セグメントまでの案内経路の道路セグメントリストが
発生し、最適経路が選択される。ステップ７０におい
て、システムは最適経路の目的道路セグメント（最終道
路セグメント）上の運転距離が零であるかチェックす
る。零でなければ、ステップ７６に進み、最適経路が表
示され、運転車は従来例と同様に目的地に向けて案内さ
れる。

【００３３】しかしながら、ステップ７０において、目
的道路セグメント（最終道路セグメント）上の運転距離
が零の場合には、システムは目的道路セグメント上にお
いて移動が必要でないと認識し、かつ、非効率性及び運
転における混乱を最小にするために、目的道路セグメン
トを道路セグメントリストから除去すべきであると認識
する。それゆえ、ステップ７４において、システムはこ
の最後の移動距離が零の目的道路セグメントを道路セグ
メントリストから削除する。それからステップ７６に進
んで最適経路が表示され、最終的にステップ８０におい
て処理が終了する。

【００３４】それゆえ、ステップ７０及びステップ７４
は目的セグメントフィルタリングまたはセグメント除去
と呼ばれる処理を示している。すなわち、不要な操縦、
例えば、経路案内による右折、左折運転を防止するため
に、もし目的道路セグメントが移動距離零であれば、道
路セグメントリストからフィルタリング、すなわち除去
する。例えば、目的道路セグメントがセグメント３であ
る図３の例において、もし、セグメント１、２、４、５
のいずれかにおいて目的交差点Ｎに接近するならば、目
的セグメント３上の実際の移動距離は零である。かかる
状況において、道路セグメントリストよりセグメント３
を除去することは、システムによりユーザが目的交差点
Ｎに到達したことを知らされる前にユーザが該交差点Ｎ
を誤って通過して運転することから防止できる。それゆ
え、不必要な動作がディスプレイ１８を通してユーザに
指示されることを防ぐことにより、この第２の改善は経
路案内を簡略化し、ユーザに対しより明確な経路案内を
提供する。目的セグメントフィルタリング処理は上述の
目的セグメントの選択を必要としない場合にも適用でき
る点に注目すべきである。

【００３５】目的セグメントフィルタリングは他の実施
例では図７のステップ７０及びステップ７４で示された
ものとはわずかに異なるステップで実施される。この他
の実施例では、システムはまずどのノードポイントが目
的交差点に対応するのかのチェックを行う。道路セグメ
ントリストはそれから、これらのノードポイントのどれ
かが該道路セグメントリストの最後のエントリー（記
入）にあるかを決定するためにサーチされる。もし、最
後のエントリーに存在すれば、目的セグメントフィルタ
リングの必要はなく、ステップ７６の処理が実行され
る。しかし、もし、最後のエントリーに存在しなけれ
ば、例えば、目的ノードポイントが道路セグメントリス
トの最後のエントリーから２番目のエントリーに存在す
れば、道路セグメントリストはその最後のエントリーを
削除して短縮され、これにより、目的地を含むそのリス
トにおける２番目のエントリーがそのリストの最終エン
トリーとなり、ステップ７６の処理が実行される。

【００３６】図８及び図９は図７のステップ７０及びス
テップ７４に適用される本発明の第１の例である。本発
明によれば、図７のステップ６０〜ステップ６４が実行
され、結果としてこの例では、道路セグメント２が目的
道路セグメントとして指定され、そして、最適経路が図
８のグラフ的に図示するようにセグメント５に沿って存
在する。尚、図８において破線は最適経路である。この
場合、道路セグメント２が目的道路セグメントとして選
択されても、目的地は交差点Ｎであるため、セグメント
２上の実際の移動は不要であり、目的道路セグメント２
に沿った移動距離は零である。それゆえ、これは従来の
ナビゲーションシステムに関して上述された問題を図示
し、そのため、目的地に到着したことをユーザに与える
案内指示が出される前に、車両は道路セグメント２に進
入し、あるいは、少なくとも、目的地Ｎに到着するであ
ろう。

【００３７】これは、車両が既に目的地Ｎを通過してし
まったことを意味するかも知れないから、望ましいこと
ではない。本発明によれば、車両がセグメント５を３マ
イル走行した後（ちょうど交差点Ｎに存在するとき）、
目的地に到達したことを示す案内指示が与えられる。こ
れは、例えば、丁度車両が交差点Ｎに到達する前に、す
なわち、交差点を通過する前に発生する。以上は図７の
ステップ７０、７４によるプロセスの例である。

【００３８】このプロセスは図９における経路案内道路
セグメントリストによって説明される。図９の左側カラ
ムは道路セグメントリストにより従来例において何が発
生するかを説明している。このセグメントリストの最後
の部分は、関連するデータを伴った道路セグメント５及
び関連するデータを伴った道路セグメント２を含んでお
り、道路セグメント２における運転距離は零である。

【００３９】図７（Ａ）のステップ７０及びステップ７
４によれば、システムは道路セグメント２上の移動距離
が零であるので、道路セグメント２がリストから削除す
べきであると決定する。この削除は択一的な上述したセ
グメント除去方法を使って行われる。セグメント除去に
より、セグメント２に関する全てのデータが削除され
て、図９左側カラムの従来例の道路セグメントリストは
図９の右側カラムに図解された道路セグメントリストに
なる。それゆえ、運転者がセグメント５上を３マイル運
転し、丁度交差点Ｎに到着すると、経路の終点が指示さ
れる。本発明による幾つかのシステムにおいて、指示が
別の形態で与えられるであろう。例えばＮＤＰＴ５２に
おいて、表示及びまたは音声アナウンスメントにより次
の交差点が目的地であることが通報される。

【００４０】わずかに異なる状況における第２の例が図
１０及び図１１で説明される。この場合、図７（Ａ），
（Ｂ）のステップ６０〜ステップ６４において、道路セ
グメント３が目的道路セグメントとして指定され、そし
て、最適経路が図１０においてグラフ的に図示するよう
にセグメント５に沿って存在する。

【００４１】従来例及び本発明の関連する経路案内道路
セグメントリストが図１１に示される。尚、従来のセグ
メントリストは図１１の左側カラムに示されている。こ
の従来の道路セグメントリストにより、車両はセグメン
ト５に沿って移動し、それから、セグメント３に左折し
なければならない。しかし、目的地点が交差点Ｎである
ためセグメント３上の運転距離は零である。かくして、
従来例において、車両が図１０において示されるポイン
ト１を通過後、システムはディスプレイを通してドライ
バに次の交差点で左折するように指示する。車両が指示
されたようにノードポイントＮＤＰＴ３１で左折により
道路セグメント３に進入後、やっと、それから、システ
ムは目的地に到達したことを指示する。それゆえ、目的
地が実際に交差点Ｎにも係らず、該交差点Ｎにおいて左
折するようにドライバに要求することになる。かくし
て、もし、ドライバが経路案内指示に素直に従う場合に
は、左折という余分の操縦運転を必要とする。

【００４２】本発明によれば、道路セグメントリストに
は、道路セグメント３に関係するデータが道路セグメン
トリストから削除され、車両がセグメント５に進入した
ときに「次の交差点は目的地である」旨の目的地指示が
与えられる。本発明に関連する道路セグメントリストは
図１１の右側カラムに示される。第３の例が図１２及び
図１３に示される。この場合、図７のステップ６０〜６
４において、道路セグメント５が目的道路セグメントと
して指示され、最適経路（点線参照）は道路セグメント
５に沿って存在する。

【００４３】対応する道路セグメントリストは図１３に
示される。図１３に示されるように、従来例及び本発明
共に、道路セグメントリストの最後のエントリーは運転
距離が３マイルであることを示す道路セグメント５に関
する。それゆえ、図１２に示すポイント１を通過後、
「次の交差点が目的地である」旨の指示がユーザに与え
られる。この場合には、従来例及び本発明とも、同一の
指示が与えられる。しかし、かかる場合はまれなケース
であり、換言すれば、上記説明したように、目的セグメ
ントフィルタリングによる改善が必要になる。本発明を
図に従って説明したが限定されるべきでない。また、技
術分野における技術者であれば変形が可能であるが、本
発明はこれらを排除するものではない。

【図面の簡単な説明】

【図１】図１はナビゲーションシステムのブロックダイ
アグラムである。

【図２】グラフ的に道路セグメントを表示する図であ
る。

【図３】問題と解法（本発明に従った目的セグメント選
択の方法）の両方をグラフ的に図解する説明図である。

【図４】図３に従ったセグメント基本データベースの構
成図である。

【図５】図３の付加的な詳細説明図である。

【図６】従来のナビゲーションシステムの欠点を説明す
る図５に応じたセグメントデータリストである。

【図７】道路セグメントを選択すると共に案内経路から
不要な道路セグメントを削除するコンピュータプログラ
ムのフローチャートである。

【図８】本発明の適用例をグラフ的に説明する第１実施
例である。

【図９】従来例の道路セグメントリスト及び図８の実施
例における本発明の道路セグメントリストである。

【図１０】グラフ的に示す第２実施例である。

【図１１】従来例の道路セグメントリスト及び図１０の
実施例における本発明の道路セグメントリストである。

【図１２】グラフ的に示す第３実施例である。

【図１３】従来例の道路セグメントリスト及び図１２の
実施例における本発明の道路セグメントリストである。

【符号の説明】

Claims

【特許請求の範囲】

【請求項１】それぞれの道路が１以上の道路セグメン
ト有する道路網に関して格納された情報に基づいて目的
地に向けてルーチングする方法において、目的地として少なくとも２つの道路の交差点を指示し、出発地を決定し、前記指示された交差点に延びる全ての道路セグメントを
求め、該指示された交差点から進入できない道路セグメントを
前記求めた道路セグメントから除外し、残りの前記求めた道路セグメントの１つを目的道路セグ
メントとして指定し、出発地から目的道路セグメントまでの道路セグメント網
上の経路であって、順序付けられた道路セグメントの集
まりである経路を探索し、該経路を示す、ことを特徴とするルーチング方法。
【請求項２】前記格納情報は、道路セグメントが一方
通行の道路セグメントであるかを示す情報を含み、前記道路セグメントを除外するステップにおいて、目的
地に向けて一方通行のみが許されている道路セグメント
を除外することを特徴とする請求項１記載のルーチング
方法。
【請求項３】前記探索ステップにおいて、最小移動時
間、最小移動距離、高速道路の最多使用のいずれかのパ
ラメータに基づいて最適経路を探索することを特徴とす
る請求項１記載のルーチング方法。
【請求項４】前記探索ステップにおいて、目的交差点
までの目的道路セグメント上における移動距離が零であ
るかチェックし、零であれば、目的道路セグメントを上
記順序付けられた道路セグメントの集まりから除外す
る、ことを特徴とする請求項１記載のルーチング方法。
【請求項５】前記経路を示すステップにおいて、該経
路の地図を表示することを特徴とする請求項１記載のル
ーチング方法。
【請求項６】前記経路を示すステップにおいて、該経
路を音声アナウンスメントで示すことを特徴とする請求
項１記載のルーチング方法。
【請求項７】目的地へルーチングする装置において、それぞれの道路が１以上の道路セグメント有する道路網
に関する情報を格納するメモリ、目的地として少なくとも２つの道路の交差点を指示する
手段、出発地を決定する手段、前記指示された交差点に延びる全ての道路セグメントを
求める手段、該指示された交差点から進入できない道路セグメントを
前記求めた道路セグメントから除外する手段、残りの前記求めた道路セグメントの１つを目的道路セグ
メントとして指定する手段、出発地から目的道路セグメントまでの道路セグメント網
上の経路であって、順序付けられた道路セグメントの集
まりである経路を探索する手段、該経路を示す手段、を有することを特徴とするルーチン
グ装置。
【請求項８】前記格納情報は、道路セグメントが一方
通行道路セグメントであるかを示す情報を含み、前記除外手段は、目的地に向けて一方通行のみが許され
ている道路セグメントを除外する手段を有することを特
徴とする請求項７記載のルーチング装置。
【請求項９】前記探索手段は、最小移動時間、最小移
動距離、高速道路の最多使用のいずれかのパラメータに
基づいて最適経路を探索する手段を有することを特徴と
する請求項７記載のルーチング装置。
【請求項１０】前記探索手段は、目的交差点までの目
的道路セグメント上における移動距離が零であるかチェ
ックする手段、零であれば、目的道路セグメントを上記
順序付けられた道路セグメントの集まりから除外する手
段を有することを特徴とする請求項７記載のルーチング
装置。
【請求項１１】前記経路を示す手段は、該経路の地図
を表示する手段を有することを特徴とする請求項７記載
のルーチング装置。
【請求項１２】前記経路を示す手段は、該経路を音声
アナウンスメントで示す手段を有することを特徴とする
請求項７記載のルーチング装置。
【請求項１３】それぞれが１以上の道路セグメント有
する道路よりなる道路網に関して格納された情報に基づ
いて目的地に向けてルーチングする方法において、目的地として少なくとも２つの道路の交差点を指示し、出発地を決定し、出発地から目的交差点までの道路セグメント網上の経路
であって、順序付けられた道路セグメントの集まりであ
る経路を探索し、前記順序付けられた道路セグメントの集まりにおける最
後の道路セグメントにおいて、目的交差点までの距離が
零であるかチェックし、距離が零であれば、最後の道路セグメントを上記道路セ
グメントの集まりから除外し、該順序付けられた道路セグメントの集まりである経路を
示す、ことを特徴とするルーチング方法。
【請求項１４】探索ステップにおいて、移動パラメー
タに基づいて最適経路を選択することを特徴とする請求
項１３記載のルーチング方法。
【請求項１５】前記経路を示すステップにおいて、該
経路の地図を表示することを特徴とする請求項１３記載
のルーチング方法。
【請求項１６】前記経路を示すステップにおいて、該
経路を音声アナウンスメントで示すことを特徴とする請
求項１３記載のルーチング方法。
【請求項１７】目的地へルーチングする装置におい
て、それぞれが１以上の道路セグメント有する道路よりなる
道路網に関する情報を記憶するメモリ、目的地として少なくとも２つの道路の交差点を指示する
手段、出発地を決定する手段、出発地から目的交差点までの道路セグメント網上の経路
であって、順序付けられた道路セグメントの集まりであ
る経路を探索する手段、前記順序付けられた道路セグメントの集まりにおける最
後の道路セグメントにおいて、目的交差点までの距離が
零であるかチェックする手段、距離が零であれば、最後の道路セグメントを上記道路セ
グメントの集まりから除外する手段、該順序付けられた道路セグメントの集まりである経路を
示す手段、を備えたことを特徴とするルーチング装置。
【請求項１８】前記探索手段は、移動パラメータに基
づいて最適経路を選択する手段を有することを特徴とす
る請求項１７記載のルーチング装置。
【請求項１９】前記経路を示す手段は、該経路の地図
を表示する手段を有することを特徴とする請求項１７記
載のルーチング装置。
【請求項２０】前記経路を示す手段は、該経路を音声
アナウンスメントで示す手段を有することを特徴とする
請求項１７記載のルーチング装置。