JPH07243860A - 車両用経路誘導装置 - Google Patents

Abstract

(57)【要約】 【目的】 車両用経路誘導装置の経路探索時間を短縮す
る。 【構成】 指向性の高い経路探索を行って現在地から目
的地までの一次経路を探索し、道路地図上に探索した一
次経路を表示するとともに、その一次経路上に仮出発地
を設定し、一次経路探索時よりも指向性の低い経路探索
を行って仮出発地から目的地までの二次経路を探索し、
車両が仮出発地に到達したら表示中の経路を一次経路か
ら二次経路に切り換える。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、目的地までの最適経路
を探索して乗員を誘導する車両用経路誘導装置に関す
る。

【０００２】

【従来の技術とその問題点】目的地を設定すると現在地
から目的地までの最適な経路を探索し、その最適経路と
車両の現在地を道路地図上に表示して乗員を目的地まで
誘導する車両用経路誘導装置が知られている。この目的
地までの最適経路の探索は、膨大な交差点ネットワーク
データを検索して形成される目的地までの無数の経路の
中から、例えば道程が最小の経路や所要走行時間が最小
の経路を最適経路に選定しているので、探索時間がかか
るという問題がある。

【０００３】この問題を解決するために、探索アルゴリ
ズムを改良したり（特開平２−１８４９９８号公報参
照）、探索対象のエリアを限定したり（特開平２−３０
６４００号公報参照）、交差点ネットワークデータを階
層化構造にする（特開平２−５６５９１号公報参照）な
どして、探索時間を短縮する提案がなされているが、そ
れでも最適経路探索に数分を要している。

【０００４】本発明の目的は車両用経路誘導装置の経路
探索時間を短縮することにある。

【０００５】

【課題を解決するための手段】一実施例を示す図１およ
び図２に対応づけて請求項１発明を説明すると、請求項
１の発明は、地図を記憶する地図記憶手段１６と、目的
地を設定する目的地設定手段８と、車両の現在地を検出
する現在地検出手段１、３、７、１２、１４、１５と、
指向性の高い経路探索を行って現在地から目的地までの
一次経路を探索する一次経路探索手段１と、この一次経
路探索手段１により探索された一次経路上に仮出発地を
設定する仮出発地設定手段１と、一次経路探索手段１よ
りも指向性の低い経路探索を行って仮出発地から目的地
までの二次経路を探索する二次経路探索手段１と、地図
記憶手段１６から読み出した道路地図上に一次経路を表
示し、車両が仮出発地に到達したら表示中の経路を一次
経路から二次経路に切り換える表示手段１８とを備え、
これにより、上記目的を達成する。請求項２の車両用経
路誘導装置の仮出発地設定手段１は、二次経路探索手段
１による二次経路の探索時間を予想し、二次経路の探索
が終了する時点で到達する一次経路上の地点を仮出発地
として設定するようにしたものである。請求項３の車両
用経路誘導装置の仮出発地設定手段１は、現在地から目
的地までの直線距離と両地点間に存在する交差点数に基
づいて二次経路の探索時間を予想するようにしたもので
ある。請求項４の車両用経路誘導装置の仮出発地設定手
段１は、二次経路の予想探索時間に所定時間を設定する
ようにしたものである。一実施例の一次経路と二次経路
の探索範囲を説明する図８に対応づけて、請求項５の発
明を説明すると、請求項５の車両用経路誘導装置の一次
経路探索手段は、現在地から探索を開始し、現在地周辺
の出発交差点からの道程ｇと目的地周辺の目的交差点ま
での直線距離ｈのｋ倍（ただし、ｋ＞０）との合計値
（ｇ＋ｋ・ｈ）が小さい交差点を順次検索して目的交差
点に達するまで探索を行うようにしたものである。一実
施例の変形例の一次経路と二次経路の探索範囲を説明す
る図１７に対応づけて、請求項６の発明を説明すると、
請求項６の車両用経路誘導装置の一次経路探索手段は、
目的地から探索を開始し、目的地周辺の目的交差点から
の道程ｇと現在地周辺の出発交差点までの直線距離ｈの
ｋ倍（ただし、ｋ＞０）との合計値（ｇ＋ｋ・ｈ）が小
さい交差点を順次検索して出発交差点に達するまで探索
を行うようにしたものである。請求項７の車両用経路誘
導装置の一次経路探索手段１は、二次経路探索時のｋの
値よりも大きな値を設定するようにしたものである。

【０００６】

【作用】請求項１の車両用経路誘導装置では、指向性の
高い経路探索を行って現在地から目的地までの一次経路
を探索し、道路地図上に探索した一次経路を表示すると
ともに、その一次経路上に仮出発地を設定し、一次経路
探索時よりも指向性の低い経路探索を行って仮出発地か
ら目的地までの二次経路を探索し、車両が仮出発地に到
達したら表示中の経路を一次経路から二次経路に切り換
える。これにより、指向性の高い探索方法により短時間
で一次経路の探索が完了し、乗員が車両に搭乗後、経路
探索のために長時間待たされることなく、すぐに一次経
路が表示され経路誘導が開始される。また、二次経路は
一次経路よりも指向性の低い探索方法により探索される
ので最適な経路が探索され、仮出発地からは表示経路が
一次経路から二次経路に切り換えられて最適な二次経路
に沿って目的地までの経路誘導が行われる。請求項２の
車両用経路誘導装置では、二次経路の探索時間を予想
し、二次経路の探索が終了する時点で到達する一次経路
上の地点を仮出発地として設定する。これにより、一次
経路による誘導は必要最小限の範囲に制限され、最適な
二次経路による誘導範囲が広くなって適切な経路誘導が
行われる。請求項３の車両用経路誘導装置では、現在地
から目的地までの直線距離と両地点間に存在する交差点
数に基づいて二次経路の探索時間を予想する。二次経路
は仮出発地から目的地までの経路であるから、仮出発地
から目的地までの経路探索時間を予想すべきであるが、
仮出発地自体が決定していないので、仮出発地から目的
地までの経路に代えて現在地から目的地までの経路の探
索時間を、現在地から目的地までの直線距離と両地点間
に存在する交差点数とに基づいて予想する。こうすると
予想探索時間が現在地から仮出発地までの探索時間だけ
長くなるが、二次経路の探索時間は現在地から目的地ま
での走行時間に比べて無視できるほど短いので、仮出発
地は現在地近くに存在すると考えられ、合理的に二次経
路の探索時間を予想することができる。請求項４の車両
用経路誘導装置では、二次経路の予想探索時間に所定時
間を設定する。通常の経路誘導における二次経路の探索
時間は５〜１０分以内に終了するので、二次経路の予想
探索時間をそれ以上の所定時間に設定すれば、短時間に
探索時間を予想できる。予想探索時間を例えば１５分に
設定しても、この予想時間は通常の現在地から目的地ま
での走行時間に比べて充分小さいので、問題にならな
い。請求項５の車両用経路誘導装置では、一次経路の探
索時に、現在地から探索を開始し、現在地周辺の出発交
差点からの道程ｇと目的地周辺の目的交差点までの直線
距離ｈのｋ倍との合計値（ｇ＋ｋ・ｈ）が小さい交差点
を順次検索して目的交差点に達するまで探索を行う。こ
れにより、現在地周辺では広い範囲において経路探索が
行われ、最適な経路が探索される。つまり、仮出発地は
現在地に近いので、現在地から仮出発地まで最適な一次
経路が探索され、一方、仮出発地から目的地までは最適
な二次経路が探索されるので、乗員が車両に搭乗後、直
ちに経路誘導が開始される上に、現在地から目的地まで
最適な経路に沿って誘導が行われる。請求項６の車両用
経路誘導装置では、一次経路の探索時に、目的地から探
索を開始し、目的地周辺の目的交差点からの道程ｇと現
在地周辺の出発交差点までの直線距離ｈのｋ倍との合計
値（ｇ＋ｋ・ｈ）が小さい交差点を順次検索して出発交
差点に達するまで探索を行う。これにより、指向性の高
い経路探索が行われ、目的地周辺の正確な経路を探索で
きる。請求項７の車両用経路誘導装置では、一次経路探
索時のｋの値に二次経路探索時の値よりも大きな値を設
定する。これにより、一次経路探索は二次経路探索に比
べて指向性が高くなり、短時間で探索が完了し、経路誘
導が開始されるまでの乗員の待ち時間が短縮される。

【０００７】なお、本発明の構成を説明する上記課題を
解決するための手段および作用の項では、本発明を分り
やすくするために実施例の図を用いたが、これにより本
発明が実施例に限定されるものではない。

【０００８】

【実施例】図１および図２は第１の実施例の構成を示す
ブロック図である。この車両用経路誘導装置１００は、
図に示すようにＰＵ１とその周辺部品から成るマイクロ
コンピューターを中心に構成される。ＣＰＵ１は、シス
テムバス２を介して各種機器とデータの授受を行ない、
後述する制御プログラムを実行して車両の現在地を演算
し、現在地から目的地までの最適経路を探索する。方位
センサー３は車両の進行方位を検出するセンサーであ
り、増幅器４、Ａ／Ｄ変換器５およびＩ／Ｏコントロー
ラー６を介してシステムバス２へ接続される。また、車
速センサー７は例えばトランスミッションに取り付けら
れ、スピードメーターピニオン１回転当り所定数のパル
ス信号を発生する。この車速センサー７はＩ／Ｏコント
ローラー６を介してシステムバス２へ接続される。ＣＰ
Ｕ１は、車速センサー７から出力される単位時間当りの
パルス数またはパルス周期を検出することにより車両の
走行速度を検出するとともに、パルス数をカウントする
ことにより車両の走行距離を検出する。キー８は、装置
へ種々の指令や目的地などのデータを入力するための操
作部材であり、Ｉ／Ｏコントローラー９を介してシステ
ムバス２へ接続される。音声出力用スピーカー１０はサ
ウンドジェネレーター１１およびＩ／Ｏコントローラー
９を介してシステムバス２へ接続される。ＧＰＳレシー
バー１２は、衛星から送信されるＧＰＳ信号を受信し、
ＧＰＳ測位演算を行なって車両の現在地や進行方位を検
出する。

【０００９】また、図２において、ＣＤ−ＲＯＭ１６は
交差点ネットワークデータを含む道路地図データを記憶
する記憶装置であり、インタフェース用ＳＣＳＩコント
ローラー１７を介してシステムバス２へ接続される。Ｃ
ＲＴ１８はＶＤＴ（VisualDisplay Terminal）として機
能するディスプレイであり、グラフィックコントローラ
ー１９を介してシステムバス２へ接続される。このＣＲ
Ｔ１８に車両の現在地周辺の道路地図を表示するととも
に、その道路地図上に車両の現在地と目的地までの最適
経路を表示する。なお、システムバス２には、ＣＲＴ１
８の画像記憶用Ｖ−ＲＡＭ２０、後述する制御プログラ
ムなどを格納するＲＯＭ２１、目的地から現在地への経
路探索結果を記憶するＤ−ＲＡＭ２２、漢字ＲＯＭ２
３、不揮発性のＳ−ＲＡＭ２４が接続される。このＳ−
ＲＡＭ２４は２つの電源系統を備えており、この経路誘
導装置１００の不図示のメインスイッチが投入されてい
る間は、ＣＰＵ１などの機器と同様に不図示の車載バッ
テリーから電力が供給され、メインスイッチが釈放され
て車載バッテリーからの電力の供給が停止されても不図
示の補助バッテリーから電力が供給され、記憶内容を保
持する。なお、この補助バッテリーは車載バッテリーに
接続されて常時充電可能とされる。

【００１０】図３〜図７、図９〜図１０は、ＣＰＵ１で
実行される制御プログラムを示すフローチャートであ
る。これらのフローチャートにより、実施例の動作を説
明する。図３はメインプログラムを示すフローチャート
である。経路誘導装置１００のキー８のメインスイッチ
が投入されると、ＣＰＵ１は図３に示す制御プログラム
の実行を開始する。実行開始後のステップＳ１１０にお
いて入出力条件の設定などのイニシャライズ処理を行
い、続くステップＳ１２０で初期位置情報を入力する。
この初期位置情報は、乗員がキー８を操作して入力した
初期位置情報と方位センサ３により検出された車両の進
行方位が含まれる。なお、ＧＰＳ測位により検出された
車両の現在位置と進行方位を初期位置情報として利用し
てもよい。ステップＳ１３０で、ＣＲＴ１８上に表示さ
れている道路地図上に、上記ステップで入力した初期位
置と進行方位にしたがって現在位置マークを表示する。
さらに、ステップＳ１４０で割り込みを許可してステッ
プＳ１５０へ進み、ウォッチドックタイマーによるＣＰ
Ｕ１の暴走の監視などのバックグラウンドジョブを行い
ながら、後述する現在位置計算割り込み処理、経路計算
処理および目的地設定処理の発生を待機する。

【００１１】図４は現在位置計算割り込み処理ルーチン
を示すフローチャートである。車速センサ７からのパル
ス信号に基づいて検出された走行距離が所定値に達する
ごとに、ＣＰＵ１にこの現在位置計算割り込みがかか
り、ＣＰＵ１はこの割り込みルーチンを実行する。実行
開始直後のステップＳ２１０で割り込みを禁止してから
ステップＳ２２０へ進み、車速センサ７からのパルス信
号に基づいて検出された走行距離と、方位センサ３によ
り検出された進行方位とに基づいて車両の走行軌跡を求
め、道路地図データとのマップマッチングにより車両の
現在位置と進行方位を計算する。なおこの時、ＧＰＳ測
位により検出された現在位置と進行方位を利用してもよ
い。ステップＳ２３０で、現在位置および進行方位が前
回検出された位置および方位から変化したか否かを判別
し、変化していればステップＳ２４０へ進み、変化して
いなければステップＳ２５０へ進む。現在位置および進
行方位が変化した時は、ステップＳ２４０で新たに検出
された現在位置および進行方位にしたがって現在位置マ
ークを表示し直す。その後、ステップＳ２５０で割り込
みを許可してリターンする。

【００１２】図５は目的地設定処理ルーチンを示すフロ
ーチャートである。乗員がキー８により目的地を設定し
た時に、ＣＰＵ１はこの目的地設定処理ルーチンを実行
する。なお、後述する経路計算処理ルーチンにおいて、
目的地が設定されていない場合は乗員に対して目的地の
設定要求が発っせられる。ステップＳ３１０で割り込み
を禁止してステップＳ３２０へ進み、設定された目的地
を入力した後、ステップＳ３３０で割り込みを許可して
リターンする。

【００１３】ここで、この実施例の現在地から目的地ま
での経路探索方法について説明する。乗員が車両に搭乗
後、直ちに目的地に出発することを希望している時は、
検出された現在地から乗員が設定した目的地までの”一
次経路”を探索する。この一次経路とは、乗員が直ちに
出発することを希望しているので短時間で探索できる経
路であって、最適でなくてもとりあえず目的地に到達で
きる経路をいう。しかし、出発地付近だけはできる限り
正確に探索を行って最適な経路を求めることが望まし
い。この実施例では後述する指向性の高い探索方法によ
り一次経路を計算する。また、現在地から目的地までの
最適経路には、道程が最小の経路（以下、最短経路と呼
ぶ）や、所要時間が最小の経路などがあるが、この実施
例では最短経路を探索する場合を例に上げて説明する。
一次経路が計算されたら、一次経路をＣＲＴ１８に表示
して乗員の誘導を開始する。上述したように、一次経路
は短時間で計算されるので、乗員は経路探索のために長
時間待たされることがなく、搭乗後まもなくＣＲＴ１８
に表示された一次経路に沿って目的地へ出発することが
できる。

【００１４】一方、一次経路を表示して乗員の誘導を開
始すると同時に”二次経路”を探索する。この二次経路
とは、現在地から目的地までの途中にある地点と目的地
との間の最適経路、すなわち最短経路であって、上記一
次経路探索よりも低い指向性の経路探索を行って正確に
計算した経路である。ところで、乗員はすでに一次経路
による誘導に従って目的地へ走行中であり、二次経路が
計算された時点で誘導経路を一次経路から最適な二次経
路へ切り換える必要がある。この誘導経路の切り換え
は、二次経路の探索が終了する時点で到達する一次経路
上の地点で行えばよい。この地点を以下では仮出発地と
呼び、二次経路をこの仮出発地から目的地までの最短経
路とする。

【００１５】この仮出発地は次のようにして決定する。
まず、二次経路の探索時間を予想する。二次経路は仮出
発地から目的地までの経路であるが、まだ仮出発地が決
定していないので、仮出発地から目的地までの代りに現
在地から目的地までの二次経路の探索時間を予想する。
この場合、現在地から仮出発地までの探索時間だけ予想
探索時間が長くなるが、通常、二次経路の探索時間は現
在地から目的地までの走行時間に比べて無視できる程度
に短いので問題はない。この実施例では、二次経路の予
想探索時間を現在地と目的地の２点間の直線距離や、読
み込んだ道路地図データ内の現在地と目的地との間に存
在する交差点数などに基づいて決定する。なお、二次経
路の予想探索時間は上述した予想方法に限定されず、所
定時間（例えば１５分）を設定してもよい。二次経路の
予想探索時間が算出されたら、渋滞に巻き込まれず、規
制速度を守って一次経路上を円滑に走行したと仮定し
て、上記の予想探索時間でどこまで行けるかを計算し、
この到達地点後に通過する交差点を仮出発地に設定す
る。つまり、この仮出発地に到達した時点では二次経
路、すなわち目的地までの正確な最短経路の探索が完了
しており、この仮出発地で誘導経路を一次経路から二次
経路に切り換え、二次経路をＣＲＴ１８に表示して乗員
を目的地まで誘導すればよい。

【００１６】なお、乗員が車両に搭乗後に急いで出発す
ることを希望しない時は、少なくとも二次経路の探索時
間だけ乗員を待たせてもよいと判断して、最初から現在
地から目的地までの二次経路、すなわち最短経路を探索
し、探索が終了したら二次経路をＣＲＴ１８に表示して
誘導を開始する。

【００１７】図６は経路計算処理ルーチンを示すフロー
チャートである。乗員がキー８により経路計算のための
操作を行うと、ＣＰＵ１はこの経路計算処理ルーチンの
実行を開始する。実行開始直後のステップＳ４１０で割
り込みを禁止してからステップＳ４１５へ進み、目的地
が設定されているか否かを判別する。目的地が設定され
ていない時は、ステップＳ４２０へ進んで乗員に目的地
の設定を促す注意表示をＣＲＴ１８に表示するととも
に、図５に示す目的地設定処理ルーチンを実行して設定
された目的地を入力する。すでに目的地が設定されてい
る時、または上記ステップＳ４２０で目的地が設定され
た時は、ステップＳ４２５でキー８からの設定情報によ
り乗員が直ちに出発することを希望しているか否かを判
別し、直ちに出発することを希望していればステップＳ
４３０へ進み、そうでなければステップＳ４５０へ進
む。

【００１８】乗員が車両に搭乗後、直ちに出発すること
を希望している時は、ステップＳ４３０で上述した一次
経路計算処理を行い、現在地と目的地の２点間の一次経
路を探索する。一次経路の探索が終了したら、ステップ
Ｓ４３５で後述する経路誘導処理ルーチンを平行して実
行し、探索された一次経路に従って経路誘導処理を開始
する。上述したように、一次経路は短時間で探索される
ので、乗員は経路探索のために長時間待たされることが
なく、搭乗後まもなくＣＲＴ１８に表示された一次経路
に沿って目的地へ出発することができる。ステップＳ４
４０で上述した方法で二次経路の探索時間を予想し、続
くステップＳ４４５で上述した方法で仮出発地を計算す
る。

【００１９】ステップＳ４５０において、乗員が搭乗後
に直ちに出発することを希望した場合は、上記仮出発地
から目的地までの二次経路を探索する。一方、搭乗後、
直ちに出発することを希望しなかった場合は、当初の出
発地から目的地までの二次経路を探索する。二次経路の
探索が終了したら、ステップＳ４５５で割り込みを許可
し、続くステップＳ４６０で後述する経路誘導処理ルー
チンを実行し、二次経路に沿って乗員を目的地まで誘導
する。なお、乗員が搭乗後に直ちに出発することを希望
するしないに拘わらず、常に一次経路の探索を行い、探
索した一次経路を表示して経路誘導を開始し、その後、
仮出発地から目的地までの二次経路を探索し、仮出発地
で誘導経路を一次経路から二次経路に切り換えるように
してもよい。

【００２０】図７は経路誘導処理ルーチンを示すフロー
チャートである。ステップＳ５１０において割り込みを
禁止し、続くステップＳ５２０で、車速センサ７からの
パルス信号に基づいて検出された走行距離と、方位セン
サ３により検出された進行方位とに基づいて車両の走行
軌跡を求め、道路地図データとのマップマッチングによ
り車両の現在位置と進行方位を検出する。なおこの時、
ＧＰＳ測位演算により検出された現在位置と進行方位を
利用してもよい。ステップＳ５３０で、新しく検出され
た最新の現在位置と進行方位にしたがって現在位置マー
クを表示し、ステップＳ５４０へ進む。ステップＳ５４
０では、探索された一次または二次経路と、検出された
現在地と、道路地図データとに基づいて誘導が必要か否
かを判別する。例えば、車両の現在位置が探索経路上の
交差点の直前（例えば、３００Ｍ手前）であれば、次の
交差点で直進すべきか、右折または左折すべきかを表示
して乗員を誘導すべきであり、このような誘導が必要な
時はステップＳ５５０へ進み、そうでなければステップ
Ｓ５５０をスキップする。ステップＳ５５０では、ＣＲ
Ｔ１８に進行方向を指示する交差点拡大図を表示した
り、スピーカー１０により音声で誘導を行う。その後、
ステップＳ５６０で割り込みを許可し、続くステップＳ
５７０で目的地に到着したか否かを判別し、目的地に到
着したらリターンし、そうでなければステップＳ５１０
へ戻って上述した処理を繰り返す。

【００２１】次に、一次経路および二次経路の探索方法
を説明する。なお以下では、現在地近くの交差点の中か
ら所定の条件を満たす交差点を出発交差点と呼び、目的
地近くの交差点の中から所定の条件を満たす交差点を目
的交差点と呼ぶ。例えば、現在地周辺の交差点の中か
ら、現在地を中心とする所定半径の円外に存在し、且つ
最も現在地に近い交差点を出発交差点に選定し、目的地
周辺の交差点の中から、目的地を中心とする所定半径の
円外に存在し、且つ最も目的地に近い交差点を目的交差
点に選定する。また、経路演算を行うために順次検索す
る交差点を中心交差点と呼び、その中心交差点に隣接す
る交差点を隣接交差点と呼ぶ。さらに、出発交差点から
各交差点に至る最適経路上の各交差点の手前にある交差
点を直前交差点と呼ぶ。

【００２２】この経路探索では、出発交差点から各交差
点に至る道程ｇと、各交差点から目的交差点までの直線
距離ｈと、各交差点の直前交差点とを各交差点ごとに記
録しながら探索を進める。まず、出発交差点の道程ｇに
０を設定し、他の交差点の道程ｇに無限大相当の定数を
設定し、出発交差点を中心交差点に設定して探索を開始
する。次に、中心交差点の隣接交差点の中からいずれか
を１つを検索し、中心交差点に記録されている出発交差
点からの道程ｇに中心交差点からその隣接交差点までの
道程を加算して、その隣接交差点の出発交差点からの道
程ｇ＝ｇ１を求め、すでにその隣接交差点に記録されて
いる出発交差点からの道程ｇ＝ｇ２と比較する。今回算
出された道程ｇ１がすでに記録されている道程ｇ２より
も小さい場合は、その隣接交差点の道程ｇをｇ１に書き
換えるとともに、その隣接交差点の直前交差点に中心交
差点を設定する。また、その隣接交差点から目的交差点
までの直線距離をｈに設定する。中心交差点に隣接する
すべての隣接交差点に対して上記処理が終了したら、す
でに中心交差点として選択された交差点を除くすべての
交差点の中から、（ｇ＋ｋ・ｈ）が最小の交差点を次の
新しい中心交差点に設定する。ここで、ｋは指向性係数
で、係数ｋが大きいほど経路探索における指向性が強く
なる。この実施例では、例えば、ｋ＝１．７として一次
経路の探索を行い、ｋ＝１として二次経路の探索を行
う。以下、この新しい中心交差点の隣接交差点に対して
上記処理を行う。

【００２３】図８は一次経路探索と二次経路探索とを説
明する図である。ｋ＝１．７とした一次経路の探索範囲
（実線で示す）は、ｋ＝１とした二次経路の探索範囲
（破線で示す）に比べて狭く、その分だけ一次経路の探
索は二次経路の探索に比べて探索時間が短くてすむ。し
かしその反面、充分正確な最適経路が探索されるとは限
らない。指向性係数ｋを大きくすればするほど、探索範
囲は狭くなり、探索時間が短くなるが、探索結果の経路
の最適性は悪くなる。これに対し、二次経路は充分広い
範囲を探索するので、探索時間はかかるが、最適な経路
を探索できる。このように、（ｇ＋ｋ・ｈ）の小さい順
に新しい中心交差点を設定して経路探索を行い、中心交
差点が目的交差点に達したら探索を終了する。そして、
目的交差点から直前交差点を順にたどって行くと出発交
差点に到達し、その経路が出発交差点から目的交差点ま
での最小道程の最適経路である。

【００２４】図９および図１０は経路計算処理ルーチン
を示すフローチャートである。この経路計算処理ルーチ
ンは上述した一次経路と二次経路に対して共通の計算ル
ーチンであり、一次経路探索時はｋ＝１．７としてこの
ルーチンを実行し、二次経路探索時はｋ＝１としてこの
ルーチンを実行する。また、図１１は最適経路の探索方
法を説明するための交差点ネットワーク例を示す図であ
る。図１１において、円と円内の数字は交差点とその番
号を表わし、交差点と交差点を結ぶ線上の数字は交差点
から交差点までの道程を表わす。さらに、図１２〜１６
はＳ−ＲＡＭ２４に記録される経路探索結果である。こ
れらの図において、（ａ）は経路情報を記録するリスト
であり、この経路情報リストには現在地周辺の各交差
点、それらの交差点までの道程ｇ、各交差点へ至る経路
上の直前交差点、および各交差点から目的交差点までの
直線距離ｈが記録される。また、（ｂ）は中心交差点候
補の交差点を示すリストであり、この中心交差点候補リ
ストには中心交差点候補の交差点番号と（ｇ＋ｋ・ｈ）
が記録される。なお、図１２〜１６ではｋ＝１．７の一
次経路の場合の（ｇ＋ｋ・ｈ）を示す。これらの図によ
り、経路計算処理を説明する。

【００２５】ステップＳ６０５で上述したように出発交
差点と目的交差点を特定する。今、図１１に示すよう
に、交差点１が出発交差点として選択されたとする。次
に、ステップＳ６１０へ進んで出発交差点を中心交差点
に設定する。図１１の例では、出発交差点１を中心交差
点とする。続くステップＳ６１５では、Ｓ−ＲＡＭ２４
の経路情報リストの各種データを初期設定する。すなわ
ち、図１２（ａ）に示すように、出発交差点の道程ｇに
０を設定し、他の全ての交差点の道程ｇに非常に大きい
値＋∞を設定する。

【００２６】ステップＳ６２０で、中心交差点に隣接す
る交差点の中からいずれか１つを選択する。続くステッ
プＳ６２５において、中心交差点の道程ｇに中心交差点
から選択された隣接交差点までの道程を加えた値をＤ−
ＲＡＭ２２に道程Ａとして一時記憶し、ステップＳ６３
０へ進む。ステップＳ６３０では、この道程Ａと選択隣
接交差点の道程ｇとを比較し、前者が小さい場合はステ
ップＳ６３５へ進み、そうでなければステップＳ６５５
へ進む。道程Ａが選択隣接交差点の道程ｇよりも小さい
時は、ステップＳ６３５で、選択隣接交差点の道程ｇに
道程Ａを設定する。ステップＳ６２０〜Ｓ６３５の処理
過程を図１１の例で説明すると、中心交差点１には交差
点２〜５が隣接しており、これらの隣接交差点の中から
まず交差点２を選択する。そして、中心交差点１の道程
ｇ＝０（図１２（ａ）参照）に中心交差点１から選択さ
れた隣接交差点２までの道程２．５を加算した道程Ａ＝
２．５と、選択隣接交差点２の道程ｇ＝∞（図１２
（ａ）参照）とを比較し、前者の方が小さいので、図１
２（ａ）に示すように選択隣接交差点２の道程ｇ＝∞を
道程Ａ＝２．５に変更する。

【００２７】次にステップＳ６４０へ進み、選択隣接交
差点の直前交差点に中心交差点を設定する。図１１に示
す例では、図１２（ａ）に示すように経路情報リストの
選択交差点２の直前交差点の欄に中心交差点１の交差点
番号を記録する。ステップＳ６４５において、中心交差
点候補リストに現在選択されている隣接交差点が存在す
るか否かを判別し、存在しなければステップＳ６５０へ
進み、存在すればステップＳ６５０をスキップする。ス
テップＳ６５０では、現在選択されている隣接交差点を
中心交差点候補リストに追加する。図１１に示す例で
は、現在選択されている隣接交差点２はまだ中心交差点
候補リストに存在しないので、図１２（ｂ）に示す中心
交差点候補リストに隣接交差点２の番号を記録する。

【００２８】ステップＳ６５５で、中心交差点に隣接す
るすべての交差点について上記の検討を行なったか否か
を判別し、検討が完了していればステップＳ６６０へ進
み、そうでなければステップＳ６２０へ戻って上記処理
を繰り返す。図１２（ａ），（ｂ）は、中心交差点１の
隣接交差点２〜５に対して上述した処理が完了した時点
のＳ−ＲＡＭ２４の記憶内容を示す。経路情報リストに
は各隣接交差点２〜５の道程ｇと直前交差点１が設定さ
れ、中心交差点候補リストには中心交差点候補の交差点
２〜５が記録されている。

【００２９】中心交差点のすべての隣接交差点に対して
上記処理を終了した時は、ステップＳ６６０で中心交差
点候補リストの中で最小の（ｇ＋ｋ・ｈ）の交差点を新
しい中心交差点に設定し、ステップＳ６６５へ進む。ス
テップＳ６６５では、中心交差点候補リストから新しく
中心交差点として選択された交差点を削除する。次にス
テップＳ６７０において、新しく中心交差点に選択され
た交差点が目的交差点か否かを判別し、目的交差点であ
ればステップＳ６７５へ進み、そうでなければステップ
Ｓ６２０へ戻る。図１１に示す例では、指向性係数ｋ＝
１．７の一次検索時は、図１２（ｂ）の中心交差点候補
リストに記録されている隣接交差点２〜５の中で隣接交
差点５の（ｇ＋ｋ・ｈ）＝２１．５が最小であり、隣接
交差点５を新しい中心交差点に決定し、中心交差点候補
リストの中から交差点５を消去する。その状態における
Ｓ−ＲＡＭ２４の記憶内容を図１３に示す。

【００３０】次にステップＳ６２０へ戻り、新たに選択
された中心交差点に対して上記処理を行なう。図１１の
例では、新たに選択された中心交差点５の隣接交差点は
交差点１、４、６、７であり、これらの隣接交差点に対
して上述した処理を行うと、Ｓ−ＲＡＭ２４の経路情報
リストと中心交差点候補リストは図１４に示すようにな
る。図１４（ｂ）に示す中心交差点候補リストの中で、
ｋ＝１．７の一次経路探索時は交差点７の（ｇ＋ｋ・
ｈ）＝２０．２が最小であり、交差点７を新しい中心交
差点に選定する。この新しい中心交差点７は目的交差点
ではないのでステップＳ６７０からステップＳ６２０へ
戻り、中心交差点７の隣接交差点５、６、９に対して上
述した処理を行うと、Ｓ−ＲＡＭ２４の経路情報リスト
と中心交差点候補リストは図１５に示すようになる。図
１５（ｂ）に示す中心交差点候補リストの中で、ｋ＝
１．７の一次経路探索時は交差点９の（ｇ＋ｋ・ｈ）＝
２０．２が最小であり、交差点９を新しい中心交差点に
選定する。この新しい中心交差点９は目的交差点ではな
いのでステップＳ６７０からステップＳ６２０へ戻り、
中心交差点９の隣接交差点７、８、１０、１２に対して
上述した処理を行うと、Ｓ−ＲＡＭ２４の経路情報リス
トと中心交差点候補リストは図１６に示すようになる。
図１６（ｂ）に示す中心交差点候補リストの中で、ｋ＝
１．７の一次経路探索時は交差点１０の（ｇ＋ｋ・ｈ）
＝１５．５が最小であり、交差点１０を次の中心交差点
に選定する。ところが、新しく選定された中心交差点１
０は目的交差点であり、中心交差点が目的交差点に達し
たので経路計算処理を終了してステップＳ６７５へ進
む。

【００３１】ステップＳ６７５において、図１６（ａ）
に示すＳ−ＲＡＭ２４の経路情報リストを検索し、目的
交差点１０を起点として直前交差点を順にたどって行
く。すなわち、目的交差点１０の直前交差点は交差点９
であり、この交差点９の直前交差点は交差点７であり、
交差点７の直前交差点は交差点５であり、交差点５の直
前交差点は交差点１、すなわち出発交差点である。この
経路、１０→９→７→５→１が出発交差点１から目的交
差点１０までの一次経路である。

【００３２】二次経路の探索は、上述した図９および１
０に示す一次経路の計算処理と同様であるが、指向性係
数ｋが１になるので図８に示すように広い範囲から中心
交差点を選定することになり、中心交差点の選定結果、
すなわち探索経路が上述した一次経路と異なる。なお、
図１１に示す交差点ネットワークの例では、説明を分り
やすくするために交差点の数が少ない場合を説明したの
で、探索結果の一次経路と二次経路が同一になるが、実
際の経路探索ではこの交差点ネットワーク例のように交
差点数が少なくないので、一次経路探索と二次経路探索
では異なる探索結果が得られる。

【００３３】このように、車両に搭乗した乗員が直ちに
出発することを希望する場合は、現在地からの指向性係
数ｋ＝１．７による指向性の高い経路探索を行って一次
経路を探索し、道路地図上に探索した一次経路を表示し
て直ちに誘導を開始するとともに、一次経路上に仮出発
値を設定し、仮出発値から目的地までの、指向性係数ｋ
＝１の一次経路探索よりも指向性の低い経路探索を行っ
て最適な二次経路を探索し、仮出発値で表示中の一次経
路を二次経路に切り換えて誘導を継続するようにしたの
で、短時間で一次経路が探索され、乗員が車両に搭乗
後、経路探索のために長時間待たされることがなく、す
ぐに一次経路が表示され経路誘導が開始される。また、
二次経路は一次経路よりも指向性の低い探索方法により
探索されるので最適な経路が探索され、仮出発地からは
表示経路が一次経路から二次経路に切り換えられて最適
な二次経路に沿って目的地までの経路誘導が行われる。

【００３４】次いで、一次経路の探索において目的交差
点付近の経路を正確に探索するようにした上記実施例の
変形例を説明する。上述した実施例では、一次経路の探
索時に出発交差点から探索を開始して目的交差点へ達し
たら探索を終了した。そうすると、図８で説明したよう
に、探索範囲は現在地の近傍で最も広く、目的地に近く
なるほで狭くなっていく。つまり、目的地近くでは狭い
範囲しか探索しないので正確な経路が得られにくく、反
対に現在地近くでは広い範囲から探索するので正確な経
路が得られやすい。そこでこの変形例では、一次経路の
探索時に目的交差点から探索を開始して出発交差点に達
したら探索を終了する。これにより、探索範囲は図８の
出発地と目的地を入れ替えた図１７に示す範囲になり、
目的地に近くなるほど探索範囲が広くなる。つまり、目
的地近くでは広い範囲から探索が行われるので、正確な
経路が得られる。

【００３５】今、このような一次経路の探索方法によ
り、図１８に示す道路地図上の出発地から目的地まで一
次経路の探索を行う場合を説明する。出発地から目的地
へ向って経路探索を行う上記実施例の方法では、図１９
に太線で示すような一次経路が探索される。一方、目的
地から出発地へ向って経路探索を行う上記変形例の方法
では、図２０に太線で示すような一次経路が探索され
る。ちなみに、出発地から目的地までの最短経路は図２
１に示すような経路である。つまり、目的地から出発地
へ向って経路探索を行う変形例の探索結果は、目的地の
近くで最短経路が得られる。

【００３６】図２２、図２３は、目的地から出発地へ向
って経路探索を行う上記変形例の経路計算処理ルーチン
を示すフローチャートである。この処理ルーチンは図
９、図１０に示す実施例の処理ルーチンにおいて出発交
差点と目的交差点とを入れ替えたものであり、説明を省
略する。

【００３７】以上の実施例の構成において、ＣＤ−ＲＯ
Ｍ１６が地図記憶手段を、キー８が目的地設定手段を、
ＣＰＵ１、方位センサ３、車速センサ７、ＧＰＳレシー
バ１２、受信機１４およびアンテナ１５が現在地検出手
段を、ＣＰＵ１が一次経路探索手段および二次経路探索
手段を、ＣＲＴ１８が表示手段をそれぞれ構成する。

【００３８】

【発明の効果】以上説明したように請求項１の発明によ
れば、指向性の高い経路探索を行って現在地から目的地
までの一次経路を探索し、道路地図上に探索した一次経
路を表示するとともに、その一次経路上に仮出発地を設
定し、一次経路探索時よりも指向性の低い経路探索を行
って仮出発地から目的地までの二次経路を探索し、車両
が仮出発地に到達したら表示中の経路を一次経路から二
次経路に切り換えるようにしたので、一次経路の探索が
短時間で終了し、乗員が車両に搭乗後、経路探索のため
に長時間待たされることなく、すぐに一次経路が表示さ
れ経路誘導が開始される。また、仮出発値から目的地ま
での二次経路は最適な経路が探索され、仮出発地で表示
経路が一次経路から二次経路に切り換えられて最適な二
次経路に沿って目的地までの経路誘導が行われる。請求
項２の発明によれば、二次経路の探索時間を予想し、二
次経路の探索が終了する時点で到達する一次経路上の地
点を仮出発地として設定するようにしたので、一次経路
による誘導は必要最小限の範囲に制限され、最適な二次
経路による誘導範囲が広くなって適切な経路誘導が行わ
れる。請求項３の発明によれば、現在地から目的地まで
の直線距離と両地点間に存在する交差点数に基づいて二
次経路の探索時間を予想するようにした。二次経路は仮
出発地から目的地までの経路であるから、仮出発地から
目的地までの経路探索時間を予想すべきであるが、仮出
発地自体が決定していないので、仮出発地から目的地ま
での経路に代えて現在地から目的地までの経路の探索時
間を、現在地から目的地までの直線距離と両地点間に存
在する交差点数とに基づいて予想する。こうすると予想
探索時間が現在地から仮出発地までの探索時間だけ長く
なるが、二次経路の探索時間は現在地から目的地までの
走行時間に比べて無視できるほど短いので、仮出発地は
現在地近くに存在すると考えられ、合理的に二次経路の
探索時間を予想することができる。請求項４の発明によ
れば、二次経路の予想探索時間に所定時間を設定するよ
うにした。通常の経路誘導における二次経路の探索時間
は５〜１０分以内に終了するので、二次経路の予想探索
時間をそれ以上の所定時間に設定することにより、短時
間に探索時間を予想できる。請求項５の発明によれば、
一次経路の探索時に、現在地から探索を開始し、現在地
周辺の出発交差点からの道程ｇと目的地周辺の目的交差
点までの直線距離ｈのｋ倍との合計値（ｇ＋ｋ・ｈ）が
小さい交差点を順次検索して目的交差点に達するまで探
索を行うようにしたので、現在地周辺では広い範囲にお
いて経路探索が行われ、最適な経路が探索される。つま
り、仮出発地は現在地に近いので、現在地から仮出発地
まで最適な一次経路が探索され、一方、仮出発地から目
的地までは最適な二次経路が探索されるので、乗員が車
両に搭乗後、直ちに経路誘導が開始される上に、現在地
から目的地まで最適な経路に沿って誘導が行われる。請
求項６の発明によれば、一次経路の探索時に、目的地か
ら探索を開始し、目的地周辺の目的交差点からの道程ｇ
と現在地周辺の出発交差点までの直線距離ｈのｋ倍との
合計値（ｇ＋ｋ・ｈ）が小さい交差点を順次検索して出
発交差点に達するまで探索を行うようにしたので、指向
性の高い経路探索が行われ、目的地周辺の正確な経路を
探索できる。請求項７の発明によれば、一次経路探索時
のｋの値に二次経路探索時の値よりも大きな値を設定す
るようにしたので、一次経路探索は二次経路探索に比べ
て指向性が高くなり、短時間で探索が完了し、経路誘導
が開始されるまでの乗員の待ち時間が短縮される。

【図面の簡単な説明】

【図１】一実施例の構成を示す機能ブロック図。

【図２】図１に続く、一実施例の構成を示す機能ブロッ
ク図。

【図３】マイクロコンピューターのメインプログラムを
示すフローチャート。

【図４】マイクロコンピューターの現在位置計算割り込
みルーチンを示すフローチャート。

【図５】マイクロコンピューターの目的地設定処理ルー
チンを示すフローチャート。

【図６】マイクロコンピューターの経路計算処理ルーチ
ンを示すフローチャート。

【図７】マイクロコンピューターの経路誘導処理ルーチ
ンを示すフローチャート。

【図８】一次経路と二次経路の探索範囲を説明する図。

【図９】マイクロコンピューターの経路計算処理ルーチ
ンを示すフローチャート。

【図１０】図９に続く、マイクロコンピューターの経路
計算処理ルーチンを示すフローチャート。

【図１１】交差点ネットワーク例を示す図。

【図１２】経路情報リストと中心交差点候補リストの記
録例を示す図。

【図１３】経路情報リストと中心交差点候補リストの他
の記録例を示す図。

【図１４】経路情報リストと中心交差点候補リストの他
の記録例を示す図。

【図１５】経路情報リストと中心交差点候補リストの他
の記録例を示す図。

【図１６】経路情報リストと中心交差点候補リストの他
の記録例を示す図。

【図１７】変形例の一次経路と二次経路の探索範囲を説
明する図。

【図１８】経路探索を行う道路地図を示す図。

【図１９】図１８に示す道路地図において実施例の探索
方法により一次経路を探索した場合の探索結果を示す
図。

【図２０】図１８に示す道路地図において実施例の変形
例の探索方法により一次経路を探索した場合の探索結果
を示す図。

【図２１】図１８に示す道路地図において出発地から目
的地までの最短経路を示す図。

【図２２】実施例の変形例の経路計算処理ルーチンを示
すフローチャート。

【図２３】図２２に続く、実施例の変形例の経路計算処
理ルーチンを示すフローチャート。

【符号の説明】

１ ＣＰＵ ２ システムバス ３ 方位センサー ４ 増幅器 ５ Ａ／Ｄ変換器 ６，９ Ｉ／Ｏコントローラー ７ 車速センサー ８ キー １０ スピーカー １１ サウンドジェネレーター １２ ＧＰＳレシーバー １３ 拡張Ｉ／Ｏ １４ 受信機 １５ アンテナ １６ ＣＤ−ＲＯＭ １７ ＳＣＳＩコントローラー １８ ＣＲＴ １９ グラフィックコントローラー ２０ Ｖ−ＲＡＭ ２１ ＲＯＭ ２２ Ｄ−ＲＡＭ ２３ 漢字ＲＯＭ ２４ Ｓ−ＲＡＭ １００ 車両用経路誘導装置

Claims (7)

【特許請求の範囲】
1. 【請求項１】 地図を記憶する地図記憶手段と、 目的地を設定する目的地設定手段と、 車両の現在地を検出する現在地検出手段と、 指向性の高い経路探索を行って前記現在地から前記目的
   地までの一次経路を探索する一次経路探索手段と、 この一次経路探索手段により探索された一次経路上に仮
   出発地を設定する仮出発地設定手段と、 前記一次経路探索手段よりも指向性の低い経路探索を行
   って前記仮出発地から前記目的地までの二次経路を探索
   する二次経路探索手段と、 前記地図記憶手段から読み出した道路地図上に前記一次
   経路を表示し、車両が前記仮出発地に到達したら表示中
   の経路を前記一次経路から前記二次経路に切り換える表
   示手段とを備えることを特徴とする車両用経路誘導装
   置。
2. 【請求項２】 請求項１に記載の車両用経路誘導装置に
   おいて、 前記仮出発地設定手段は、前記二次経路探索手段による
   二次経路の探索時間を予想し、二次経路の探索が終了す
   る時点で到達する前記一次経路上の地点を仮出発地とし
   て設定することを特徴とする車両用経路誘導装置。
3. 【請求項３】 請求項２に記載の車両用経路誘導装置に
   おいて、 前記仮出発地設定手段は、前記現在地から前記目的地ま
   での直線距離と両地点間に存在する交差点数に基づいて
   二次経路の探索時間を予想することを特徴とする車両用
   経路誘導装置。
4. 【請求項４】 請求項２に記載の車両用経路誘導装置に
   おいて、 前記仮出発地設定手段は、二次経路の予想探索時間に所
   定時間を設定することを特徴とする車両用経路誘導装
   置。
5. 【請求項５】 請求項１〜４のいずれかの項に記載の車
   両用経路誘導装置において、 前記一次経路探索手段は、前記現在地から探索を開始
   し、前記現在地周辺の出発交差点からの道程ｇと前記目
   的地周辺の目的交差点までの直線距離ｈのｋ倍（ただ
   し、ｋ＞０）との合計値（ｇ＋ｋ・ｈ）が小さい交差点
   を順次検索して、前記目的交差点に達するまで探索を行
   うことを特徴とする車両用経路誘導装置。
6. 【請求項６】 請求項１〜４のいずれかの項に記載の車
   両用経路誘導装置において、 前記一次経路探索手段は、前記目的地から探索を開始
   し、前記目的地周辺の目的交差点からの道程ｇと前記現
   在地周辺の出発交差点までの直線距離ｈのｋ倍（ただ
   し、ｋ＞０）との合計値（ｇ＋ｋ・ｈ）が小さい交差点
   を順次検索して、前記出発交差点に達するまで探索を行
   うことを特徴とする車両用経路誘導装置。
7. 【請求項７】 請求項５または請求項６に記載の車両用
   経路誘導装置において、 前記一次経路探索手段は、二次経路探索時のｋの値より
   も大きな値を設定することを特徴とする車両用経路誘導
   装置。