JP3027899B2 - 推奨経路案内装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、車両がある地点から別
の地点へ効率的に移動するために、その地点までの経路
を自動的に選定して案内をする推奨経路案内装置に関す
る。

【０００２】

【従来の技術】従来の経路探索装置の地点設定手段とし
ては、例えばユーザーが設定した地点に一番距離的に近
い主要交差点を出発地または目的地としたり、特公平5ー
6238で開示されているように複数の候補交差点の中から
ユーザーに選択させる方法があった。

【０００３】

【発明が解決しようとする課題】しかしながら、探索開
始点および探索終了点を単純に出発地あるいは目的地に
距離的に一番近い交差点に設定すると、ユーザーの意図
しない地点から（あるいはユーザーの意図しない地点ま
で）経路を導出する可能性がある。ここで、その例を示
す。図１５（ａ）は従来の地点設定法では希望する経路
が求められない場合の道路網の例（目的地側）を示す
図、図１５（ｂ）は従来の地点設定法を用いて求めた選
択経路の例を示す図である。図１５（ａ）において、出
発地はＰ（Ｓ）の方向にあり、ユーザーは網掛けの地点
に行きたくて地点Ｐ（Ｕ）に目的地設定したとする。ま
た、このとき地点Ｐ（Ｕ）から交差点N0、N1、N2への距
離はそれぞれ次の関係があるとする。

【０００４】P(U)・N0間の距離 ＜ P(U)・N2間の距離
＜ P(U)・N1間の距離 これらの条件において、探索終了点を地点Ｐ（Ｕ）に一
番近い交差点とすると、交差点N0が探索終了点として選
択され図１５（ｂ）の点線で示したような経路が選出さ
れる。このように目的地の前を通り過ぎて裏に誘導して
しまうような経路を選出する可能性がある。また、地点
設定とは別に複数の候補交差点から一つの交差点をユー
ザーに選択させることは、ユーザーが必ずしも入力地点
付近の状況に詳しいとは限らないし、実際の入力手順と
して非常に煩わしいものとなる。そこで、新たな入力作
業を伴うことなく、行き過ぎ等の不適切な経路を選出し
ないことを第１の目的とする。

【０００５】また、第１の目的を満たした上で、地点設
定した位置に近い交差点が選択されることを第２の目的
とする。

【０００６】また、ユーザーが設定した位置の近傍の道
路上から離れた交差点に探索開始点または探索終了点が
設定されることを防ぐことを第３の目的とする。

【０００７】また、第３の目的を満たした上で、目的地
に到達するために最も効率的な方向へ誘導する経路を選
出することを第４の目的とする。

【０００８】

【課題を解決するための手段】上記の問題を解決するた
めに本発明は、第１の手段として前記地点設定手段で設
定した出発地または目的地の情報から複数個の探索開始
点または探索終了点を設定し、それぞれに固有の探索開
始時の初期コストまたは探索終了点到達時の加算コスト
を与える探索開始終了点設定手段を備えたことを特徴と
する。

【０００９】また、第２の手段は前記地点設定手段にお
いて設定された出発地または目的地から前記探索開始終
了点設定手段において設定された探索開始点または探索
終了点までの距離の関数で探索開始時の初期コストまた
は探索終了点到達時の加算コストを設定する処理を第１
の手段における探索開始終了点設定手段に加えたことを
特徴とする。

【００１０】また、第３の手段は前記地点設定手段で設
定された出発地・目的地の位置情報から１本以上の道路
を選択し、その両端の交差点のうち交通規制情報に従っ
て到達できる交差点を選択する前記探索開始終了点設定
手段を備えたことを特徴とする。

【００１１】また、第４の手段は前記地点設定手段であ
げられた出発地または目的地から各道路上の最も近い点
を求め、出発地または目的地から最も近い点までの距離
の関数で与えられるコストとその点から道路の両端の交
差点に対する距離の関数で与えられるコストの和で探索
開始時の初期コストまたは探索終了点到達時の加算コス
トを与える処理を第３の手段における前記探索開始終了
点設定手段に加えたことを特徴とする。

【００１２】

【作用】本発明は、第１の手段によると、探索開始終了
点設定手段において地点設定手段で設定した出発地また
は目的地の情報から、固有の探索開始時の初期コストま
たは探索終了点到達時の加算コストを与えた複数個の探
索開始点または探索終了点を設定して、出発地近傍の目
的地方向側に探索開始点を、目的地近傍の出発地方向に
探索終了点を作成することにより、順序づけられた複数
の探索開始点および探索終了点の中から合理的な探索開
始点および探索終了点を選択でき、かつ、出発地後方を
経路の開始点にしたり目的地を行き過ぎるような経路を
選出することを防ぐことができる。

【００１３】また第２の手段によると、第１の手段によ
り実現された機能を満たした上で、出発地または目的地
からの距離の関数で探索開始時の初期コストおよび探索
終了点到達時の加算コストを与えることにより、遠く離
れた探索開始点および探索終了点は大きなコストを持つ
ことになるので、経路の開始点または終了点がそれぞれ
出発地または目的地の位置から遠く離れることを防ぐこ
とができる。

【００１４】また第３の手段によると、探索開始終了点
設定手段において地点設定手段で入力された出発地また
は目的地の位置情報から近傍の１本以上の道路を選出
し、その両端の交差点のうち交通規制情報に従って到達
できる全ての交差点を探索開始点または探索終了点に設
定することにより、ユーザーが設定した出発地または目
的地に最も近い道路が長いリンクで近くに交差点がない
場合でも他の道路上の交差点に探索開始点または探索終
了点が設定されることを防ぐことができる。

【００１５】また第４の手段によると、第３の手段によ
り実現された機能を満たした上で、出発地または目的地
から最も近い各道路上の点を求め、出発地または目的地
から最も近い点までの距離の関数で与えられるコストと
その点から道路の両端の交差点に対する距離の関数で与
えられるコストの和で探索開始時の初期コストまたは探
索終了点到達時の加算コストを与えることにより、出発
地から目的地へ到達するために不適切な探索開始点およ
び探索終了点は大きなコストを持つことになるので、出
発地から目的地へ向かうために適切な経路を選出するこ
とができる。

【００１６】

【実施例】以下、本発明の実施例を図面を用いて詳細に
説明する。

【００１７】（実施例１）図１は本発明の第１の実施例
を示す推奨経路案内装置のブロック図である。図１にお
いて、101は交差点や道路の接続状況や座標・形状・属
性など道路ネットワークに関する情報を地図データとし
て記録しておく道路ネットワーク記録手段、102は出発
地および目的地の位置を入力する地点設定手段、103は
前記地点設定手段102で入力された出発地および目的地
の位置から地図データ上の探索開始点および探索終了点
を設定する探索開始終了点設定手段、104は前記探索開
始終了点設定手段103で設定された探索開始点から探索
終了点までの経路を前記道路ネットワーク記録手段101
に記憶された地図データを利用して選出する探索手段、
105は前記探索手段104で求められた経路を画像や音声で
出力する出力手段である。

【００１８】以上のように構成された第１の実施例の推
奨経路案内装置について以下にその動作を説明する。図
２（ａ）は第１の実施例における道路網の例を示す図、
図２（ｂ）は本道路網においてノード情報の例を示す
図、図２（ｃ）は本道路網においてリンク情報の例を示
す図である。また、図３は本発明の第１の実施例におけ
る推奨経路案内装置の全体動作を示すフローチャート、
図４は本発明の第１の実施例における地点設定処理のフ
ローチャートである。

【００１９】図２（ａ）に示されるようにN1〜N10まで
の１０個のノードとL1〜L9までの９本のリンクで表され
る道路網において、道路ネットワーク記録手段101には
図２（ｂ）に示されるように少なくともノードの位置情
報「経度・緯度」とそのノードが接続するリンクの情報
「接続リンク」を持ったノード情報と、図２（ｃ）に示
されるように少なくともリンクの両端のノードの情報
「接続ノード１・接続ノード２」とリンクの形状情報
「リンク形状差分データ」を持ったリンク情報が記憶さ
れている。ここで、図２（ａ）において、△（Ｓ）は出
発地、▽（Ｄ）は目的地、○はノード、実線はリンク
（太さは重要度を表す）を示すものとする。また、（??
km/h）の速度表記はその道路における平均走行速度であ
る。ここでもう少し詳しく図２（ｂ）のノード情報と図
２（ｃ）のリンク情報について説明しておく。まず、図
２（ｂ）のノード情報について述べる。「経度・緯度」
情報は各ノードが実際に位置する座標の情報である。
「隣接ノード」情報は地図を分割して持つ場合、道路が
地図の境界上を横切るところに双方の地図内においてノ
ードを作成するが、実際には同一のノードである隣の地
図内のノードの情報を記録する。ただし、図２（ａ）の
道路網の場合、簡単のため１地図としているので「隣接
ノード」の情報は使用しない。「接続リンク」情報はそ
のノードがどのリンクにつながっているかを示す情報で
ある。次に、図２（ｃ）のリンク情報について述べる。
「距離」情報は実際の道路上の距離を記録し、ここでは
例えばメートル単位で示している。この情報は後述する
リンク形状データから計算することもできるが計算時間
の関係からデータとして持っておくことが望ましい。
「コスト」情報は経路を選出する際の評価基準により異
なる。ここでは、例えば旅行時間を最小にする経路を求
めるものとして、そのリンクにおける旅行時間を0.1秒
単位で持つものとする。（??km/h）はそのリンクにおけ
る平均走行速度（時速）を示している。距離と時速から
このコストは計算できるが計算時間の関係から記録して
おくことが望ましい。「接続ノード１、接続ノード２」
はリンクの両端がどのノードにつながっているかを示し
ている。「一方通行」情報は一方通行規制があればその
規制を示す。図中、「N3→N2」という表記はノードN3か
らノードN2方向のみ通行可ということである。「リンク
形状差分データ」情報は該当リンクが「接続ノード１」
から「接続ノード２」の間でどのような形状をしている
のかを「接続ノード１」の位置からの差分データで記録
する。ここで、ユーザーは図２（ａ）の出発地△から目
的地▽へ到達する経路を知りたいものと仮定する。この
ときの処理の詳細を図３、図４のフローチャートに従っ
て以下に説明する。

【００２０】まず、図３のステップ301においてユーザ
ーが出発地側地点設定処理を行う。この処理の詳細を図
４に示してある。図４のステップ401においてユーザー
は出発地の位置を例えばＣＲＴに映し出された地図上に
カーソルを表示し、カーソルを移動させることにより位
置を決定し、所望の座標系に変換し位置情報を取得す
る。ステップ402では、設定した出発地の座標を中心に
半径limit_distの円の範囲（図２の点線の円：例えば５
０ｍの範囲）の地図情報を読み込むが、この場合は簡単
のため１枚の地図内としている。ステップ403では、各
ノード（N1〜N12）への距離を図２（ｂ）の経度・緯度
情報とステップ401で得た出発地の位置情報から順次算
出し、距離の小さい順にＮ個（例えば４個）を選択して
記録する。図２（ａ）のような場合、円の範囲内にノー
ドN3しか存在しないので、ノードN3とそこまでの距離Ｄ
N3を記憶する。次にステップ404にて出発地側かどうか
判定し、出発地側であればステップ405に進み、ノードN
3に探索開始点フラグを立てる。さらにステップ406にお
いて探索開始時の初期コストを一定値（例えば０）とす
る。以上でステップ301の処理を終了する。

【００２１】次に、ステップ302においてステップ301の
処理と同様に目的地側地点設定処理を行う。出発地側と
違う点は、ステップ404において目的地側であると判定
されると、ステップ407に進み選択したノードに探索終
了点フラグを立てる処理を行うことのみである。ステッ
プ302の処理により、図２（ａ）の例では探索終了点と
してノードN5、N7、N8の３点が選択される。

【００２２】次にステップ303において経路探索処理を
実行する。図５に本発明の第１の実施例における経路探
索処理のフローチャート、図６に本発明の第１の実施例
における出発地側探索処理のフローチャート、図７に本
発明の第１の実施例における目的地側探索処理のフロー
チャートを示す。以下、これらを用いて詳述する。ステ
ップ501では、探索開始点フラグが立っているノードN3
を出発地側探索候補状態とし、探索終了点フラグが立っ
ているノードN5、N7、N8を目的地側探索候補状態とす
る。次にステップ502で、出発地側と目的地側探索候補
状態以外のノードを未探索状態にして初期コストを無限
大とし、初期化を行う。さらにステップ503において最
大探索範囲制限を探索コストの値で設定する。この最大
探索範囲制限は探索範囲に比べて十分大きいもの（例え
ば２００００ｍ）とする。ステップ504では、出発地側
探索処理を実行する。この処理の詳細は図６に示してあ
るので、本フローチャートに従って説明する。

【００２３】まず、ステップ601では出発地側探索候補
状態となっているノードで出発地側探索コストが一番小
さいノードを基準交差点とする。ここでは、出発地側探
索候補状態となっているノードはノードN3しかないの
で、ノードN3が基準交差点となる。ステップ602では目
的地側の探索に移行すべきかどうか判定する。すなわち
出発地側と目的地側探索範囲が接していない状態で、探
索範囲がステップ503で設定した値を越えた場合目的地
側探索に移行するため出発地側探索を終了する。また、
基準交差点がなかった場合も、探索続行不能として出発
地側探索処理を終了する。しかし、ここでは基準交差点
が存在し、かつ最大探索範囲制限は十分大きいとしてい
るのでステップ603に進む。ステップ603では、出発地側
探索コストが出発地側経路確定コスト（初期値：無限
大）を越えたかどうかで経路が確定したか判定する。最
終的には目的地側探索処理を行って経路を決定する。い
ま、出発地側経路確定コストは無限大（初期値）のまま
なのでステップ604の処理に進む。ステップ604では基準
交差点が隣の地図に接続したノード（隣接ノード）であ
るかどうか判定し、そうであればステップ614、615、61
6の処理を行い隣の地図の隣接ノードに基準交差点を移
す処理を行うが、ここでは図２（ａ）の道路網は簡単の
ため１地図内を対象にしているので隣接ノードは考慮し
ないものとする。次にステップ605では、基準交差点に
接続するリンクを順に調査対象リンクとする。ノードN3
に接続するリンクは、図２（ｂ）のノード情報よりL1、
L2、L3、L4の４本である。まず、リンクL1を調査対象リ
ンクとする。ステップ606でノードN3からノードN1へリ
ンクL1を使って進むことができるかどうか調べる。も
し、一方通行規制のためノードN3からノードN1へ進むこ
とができなかった場合にはステップ611に進む。しか
し、図２（ｃ）のリンク情報よりリンクL1は双方向通行
可のリンクであるので、ステップ607の処理に進む。ス
テップ607では、調査対象リンクの先のノードが目的地
側探索候補状態か判定する。調査対象リンクの先のノー
ドが目的地側探索候補状態であれば、ステップ617に進
み出発地側と目的地側が接続したものとしてこの経路を
記録するかどうか判定する。現在、調査対象リンクの先
のノードN1は未探索状態であるので、ステップ608に進
む。ステップ608では、ノードN1への到達コストを計算
する。ノードN3は出発地であり初期コストが０であるの
で、 ノードN1への到達コスト ← 基準交差点への到達コスト［初期コスト：０］ ＋ 調査対象リンクL1のコスト［４３］ より、ノードN1への到達コストは「４３」となる。次
に、ステップ609ではノードN3に今までの最小コストで
到達したか判定する。過去にもっと小さいコストで到達
したことがあれば、ステップ611に進みノードN1に今回
の探索結果を記憶しない。しかし、ノードN3は初期状態
なので今回到達するのが初めてである。故に、ステップ
610に進み、探索結果をノードN1に記憶する。記憶する
内容は、 前ノード ← ノードN3 前リンク ← リンクL1 出発地側探索コスト ← 「４３」 である。さらにノードN1を出発地側探索候補状態とす
る。次に、ステップ611において、ノードN3に接続する
全てのリンクを調査対象リンクに選択したか判定する。
まだ、リンクL2、L3、L4が残っているのでステップ605
の処理に戻る。ステップ605では次に調査対象リンクと
してリンクL2を選択する。ステップ606において、リン
クL2上をノードN3からノードN2に進めるかどうかチェッ
クされるが、図２（ｃ）のリンク情報よりこの方向への
進行は可能な一方通行規制であるのでステップ607の処
理に進む。ステップ607〜ステップ611までの処理を上記
と同様に繰り返し、ノードN2に次の探索結果を記憶す
る。

【００２４】前ノード ← ノードN3 前リンク ← リンクL2 出発地側探索コスト ← 「１８０」 さらに、ノードN2を出発地側探索候補状態とする。ステ
ップ611において、ノードN3に接続するリンクはリンクL
3、L4が残っているので、ステップ605に戻り調査対象リ
ンクをL3にする。しかし、ステップ606でリンクL3上は
ノードN3からノードN4へは一方通行規制により進めない
のでステップ611の処理に進む。ゆえに、ノードN4には
探索結果を記憶しない。ステップ611において、ノードN
3に接続するリンクはリンクL4が残っているので、ステ
ップ605に戻り調査対象リンクをL4にする。ステップ606
までは従来通りであるが、ステップ607で調査対象リン
クの先のノードN7は目的地側探索候補状態なので経路選
出判定を行うためステップ617に進む。ここでは、経路
の総コストを算出する。

【００２５】 経路総コスト←基準交差点N3への到達コスト［初期コスト：０］ ＋調査対象リンクのコスト［１７３］ ＋目的地側探索候補状態の交差点N7のコスト［初期コスト：０］ 故に、経路総コストは「１７３」と算出される。次に、
ステップ618において、算出した経路総コストは過去に
求められた経路の内、最小のコストであるかどうか判定
される。もし最小コストでなければ、もっと小さいコス
トで出発地から目的地まで到達できる経路が求められて
いたものとしてステップ611に進み、今回の探索結果を
記憶しない。しかし、今の場合、初めて出発地側と目的
地側が接続したのでステップ619に進み、経路接続地点
情報として次の情報を記憶する。

【００２６】出発地側接続交差点 ← ノードN3 目的地側接続交差点 ← ノードN7 出発地側経路確定コスト ← 「１７３」 目的地側経路確定コスト ← 「０」 経路接続総コスト ← 「１７３」 接続リンク ← リンクL4 次にステップ611に進み、基準交差点N3に接続するリン
クを全て調査対象リンクとしたか判定する。ここでは、
全て調査済みであるのでステップ612に進む。ステップ6
12では基準交差点N3を出発地側探索済み状態にして、ノ
ードN3を基準とした探索処理を終了する。再びステップ
601に戻り全てのノードを調査して、出発地側探索候補
状態で出発地側探索コストが最小のノードを捜す。現
在、ノードN3に接続している２つのノードN1、N2がそれ
ぞれ出発地側探索コスト「４３」、「１８０」を持ち出
発地側探索候補状態となっている。現時点で最小な出発
地側探索コストを持つ出発地側探索候補状態ノードはノ
ードN1となる。故に基準交差点としてノードN1が選択さ
れる。次にステップ602〜ステップ608までは上記と同様
に処理され（簡単のため探索対象地図は１地図のみと考
えて隣接ノードは考慮しない）、リンクL1が調査対象リ
ンクとなりノードN3への到達コストとして「４３」＋
「４３」が求められるが、ステップ610においてノードN
3は探索開始点として初期コスト「０」が与えられてい
るので今までの最小コストで到達していないと判定さ
れ、ステップ611へ進む。ステップ611ではノードN1につ
ながった全ての接続リンクが調査されたとしてステップ
612に進み、ノードN1を出発地側探索済み状態にする。
また、ステップ601に戻り同様に次の基準交差点をノー
ドN2とする。ここで、ステップ603においてノードN2の
出発地側探索コスト「１８０」は出発地側経路確定コス
ト「１７３」よりも大きいので、ステップ613に進み出
発地側経路探索処理で目的地側に接したことを示すフラ
グを立てる。以上でステップ504の出発地側探索処理を
終了する。

【００２７】次にステップ505に進み、目的地側探索処
理を実行する。この処理の詳細は図７に示してある。基
本的に出発地側探索処理と異なる点が２点ある。１点
は、ステップ706において基準交差点に接続する調査対
象リンクが走行できるかどうかチェックする時、目的地
側探索の場合は実際に車両が走行する向きとは逆の方向
に探索を広げているので一方通行規制を逆に考える点で
ある。もう１点は、ステップ707において目的地側探索
範囲と出発地側探索範囲が接した状態の判定を調査対象
リンクの先のノードが出発地側探索済み状態であること
により行う点である。これ以外は出発地側と同様の探索
処理を行う。この場合、ノードN6、N9、N10がそれぞれ
目的地側探索コスト「９０」、「９０」、「５８」を持
つ目的地側探索候補状態になり次の基準交差点としてノ
ードN10が選択されたところで、目的地側経路確定コス
トが「０」であり目的地側探索コストが「５８」となる
のでステップ703の判定でステップ713の処理に進む。こ
こで、目的地側経路確定判定がなされ全経路が確定した
ことを示すフラグを立てる。以上でステップ505の目的
地側探索処理を終了する。

【００２８】ステップ506では経路が確定したことを確
認し、もし経路が確定されていなければ、ステップ507
で探索失敗フラグを立てる。しかし、この場合ステップ
713において全経路が確定したフラグが立っているので
ステップ506で全経路確定したと判断されてステップ303
の経路探索処理を終了する。

【００２９】ステップ304では探索失敗フラグが立って
いるかどうかチェックする。探索成功と判定されればス
テップ305に進み、例えば求められた経路を走行順に地
図番号とリンク番号（方向性を含む）の列に直し経路構
成を行う。さらにステップ306で求められた経路をＣＲ
Ｔに写し出された地図に合わせて表示することにより経
路をユーザーに示す。ステップ304において、探索失敗
フラグが立っていると探索失敗と判定して、ステップ30
7で例えば経路が求められなかったことをユーザーに告
知するなどの探索失敗時の処理を行う。この場合、経路
地点接続情報から経路構成を行うとノードN3からノード
N7へリンクL4を使って到達する経路が得られる。故に次
の経路構成結果が残される。

【００３０】地図番号１ ← ＊（１地図なので不
要） リンク番号１ ← リンクL4 方向性 ← 「接続ノード１」から「接続ノード
２」へ 以上のように、第１の実施例によれば複数の地点を出発
地または目的地として選択することにより、例えば図２
（ａ）の道路網の例でノードN3−リンクL4−ノードN7−
リンクL7−ノードN8−リンクL5−ノードN5に至るような
目的地の前を行き過ぎるような経路を出さないようにす
ることができる。

【００３１】（実施例２）次に本発明の第２の実施例に
ついて説明する。本発明の第２の実施例を示す推奨経路
案内装置のブロック図は第１の実施例と同様である。

【００３２】以上のように構成された第２の実施例の推
奨経路案内装置について以下にその動作を説明する。図
８（ａ）は第２の実施例における道路網の例を示す図、
図８（ｂ）は本道路網においてノード情報の例を示す
図、図８（ｃ）は本道路網においてリンク情報の例を示
す図である。また、図９は本発明の第２の実施例におけ
る地点設定処理のフローチャートである。

【００３３】それでは、図８の道路網の例と図９の地点
設定処理のフローチャートを用いて第１の実施例との差
異を説明する。まず、図８（ａ）に示されるようにN1〜
N12までの１２個のノードとL1〜L11までの１１本のリン
クで表される道路網において、道路ネットワーク記録手
段101には図８（ｂ）に示されるようなノード情報と図
８（ｃ）に示されるようなリンク情報が記憶されてい
る。ここで、各種記号は図２の場合と同様である。

【００３４】このようなネットワークの場合、図４のス
テップ403で選択される交差点数Ｎを４として第１の実
施例と同様に経路を求めると、図８におけるノードN6が
探索終了点の１つに含まれてしまうので、最終的に選択
される経路は探索開始点群（ノードN3）と探索終了点群
（ノードN6、N7、N9、N10）を結ぶ組合せのうち一番コ
ストの小さい組合せの経路ノードN3−リンクL4−ノード
N6が選択されてしまう。ゆえに、ノードN6までの経路し
か求められないので目的地▽に到達するかなり手前まで
しか経路がわからない。そこで、第２の実施例として地
点設定処理を図９のような処理に変更することによりこ
の問題を解決する。

【００３５】第２の実施例における地点設定処理と第１
の実施例における地点設定処理の差異はステップ906の
初期コストの設定にある。第１の実施例ではステップ40
6に示すように一律同じ値（０）としていたが、第２の
実施例ではステップ906のように距離に比例した値を与
える。ここで、ステップ906における比例係数ｍは正の
実数である。なお、これは出発地ＳとノードN3間へ仮想
リンクVL1を、また目的地ＤとノードN6、N7、N9、N10間
へそれぞれ仮想リンクVL2、VL3、VL4、VL5を想定し、そ
れぞれの仮想リンクに初期コスト相当の仮想リンクコス
トを割り付け、出発地Ｓから目的地Ｄまで仮想リンクを
含んだ道路ネットワーク上で最小コスト経路を求めたと
きと同じ結果が地図データに処理を加えないで得られる
特徴を持つ。

【００３６】例えば図８（ａ）中のリンクの中で平均走
行速度が一番小さいものは時速１０ｋｍ／ｈであるが、
初期コストとして直線距離を時速５ｋｍ／ｈで走行した
事に等しい値を与える。ゆえに、ノードN3には次の初期
コストが与えられる。

【００３７】５（ｍ）／５（ｋｍ／ｈ）×３６ ＝ ３
６（１０-1秒） 同様に、各探索開始点・探索終了点とも以下の表１のよ
うな初期コストを持つ。

【００３８】

【表１】

【００３９】探索開始点の探索終了点の組合せは計４通
りある。以上の初期コストの基で全ての経路の組合せに
ついて、これらの経路の総コストを比較すると表２のよ
うになる。

【００４０】

【表２】

【００４１】この場合、最小コスト経路はノードN3〜ノ
ードN9までの経路となり、総コストは353となる。

【００４２】このように第２の実施例の特徴である地点
設定手法を用いて、第１の実施例と同様に経路探索処理
を行うことで探索開始点と探索終了点を結ぶ最短コスト
経路であるノードN3−リンクL4−リンクL6−ノードN9を
求めることができる。故に、第１の実施例の地点設定手
法を使用した場合のように、目的地のかなり手前までし
か経路が求められないという現象がなくなり、目的地に
対してなるべく近くまでの経路を求めることができる。

【００４３】なお、図９のステップ906では距離に対し
て比例して初期コストを与えたが、比例でなければなら
ない必要はない。図１０に別の初期コストの付与例を示
す。図１０（ａ）に示すように非連続的でもよいし、図
１０（ｂ）に示すように距離により比例乗数ｍを変更し
てもよい。

【００４４】（実施例３）次に本発明の第３の実施例に
ついて説明する。本発明の第３の実施例を示す推奨経路
案内装置のブロック図は第１の実施例と同様である。

【００４５】以上のように構成された第３の実施例の推
奨経路案内装置について以下にその動作を説明する。図
１１（ａ）は第３の実施例における道路網の例を示す
図、図１１（ｂ）は本道路網においてノード情報の例を
示す図、図１１（ｃ）は本道路網においてリンク情報の
例を示す図である。また、図１２は本発明の第３の実施
例における地点設定処理のフローチャートである。

【００４６】それでは、図１１の道路網の例と図１２の
地点設定処理のフローチャートを用いて第１の実施例と
の差異を説明する。まず、図１１（ａ）に示されるよう
にN1〜N13までの１３個のノードとL1〜L12までの１２本
のリンクで表される道路網において、道路ネットワーク
記録手段101には図１１（ｂ）に示されるようなノード
情報と図１１（ｃ）に示されるようなリンク情報が記憶
されている。ここで、各種記号は図２の場合と同様であ
る。

【００４７】このようなネットワークの場合、第１およ
び第２の実施例と同様に経路を求めると、図８における
ノードN5のみが探索終了点に選ばれてしまうので、最終
的に選択される経路はノードN3−リンクL4−ノードN5が
選択されてしまう。ゆえに、ノードN5までの経路しか求
められないので目的地▽に到達するかなり手前までしか
経路がわからない。そこで、第３の実施例として地点設
定処理を図１２のような処理に変更することによりこの
問題を解決する。

【００４８】第３の実施例における地点設定処理と第１
および第２の実施例における地点設定処理の差異は、探
索開始点および探索終了点の設定基準をリンク上に置く
かノード上に置くかにある。第１および第２の実施例で
は出発地または目的地の位置から近いノードを探索開始
点または探索終了点として選択していたが、第３の実施
例では出発地または目的地の位置から近いリンクを選択
してそのリンク上の端のノードを探索開始点または探索
終了点とする。以降に図１２のフローチャートを用いて
詳細に説明する。図１２のステップ1201においてユーザ
ーは出発地（目的地）の位置を例えばＣＲＴに映し出さ
れた地図上にカーソルを表示し、カーソルを移動させる
ことにより位置を決定して、所望の座標系に変換し位置
情報を取得する。ステップ1202では、設定した出発地の
座標を中心に半径limit_distの円の範囲（図２の点線の
円：例えば５０ｍの範囲）の地図情報を読み込むが、こ
の場合は簡単のため１枚の地図内としている。ステップ
1203では、各リンク（L1〜L12）への距離（各差分デー
タ成分への一番近い距離）を図１１（ｂ）の経度・緯度
情報および図１１（ｃ）のリンク形状差分データとステ
ップ1201で得た出発地（目的地）の位置情報から順次算
出し、距離の小さい順にＮ本（例えば２本）を選択して
垂線とリンクの交点の位置および距離を記録する。図１
２（ａ）のような場合、出発地側ではリンクL1上の点P1
の位置座標と距離DP1、およびリンクL3上の点P2の位置
座標と距離DP2が記録され、目的地側ではリンクL8上の
点P3の位置座標と距離DP3、およびリンクL11上の点P4の
位置座標と距離DP4が記録される。次にステップ1204に
て出発地側かどうか判定される。出発地側であればステ
ップ1205に進み、選択されたリンクL1上の点P1から一方
通行規制に従って到達できるノードN1、N3および選択さ
れたリンクL3上の点P2から一方通行規制に従って到達で
きるノードN3を探索開始点とする。ノードN1には交点P1
からノードN1までの距離を、ノードN3には交点P1からノ
ードN3までの距離または交点P2からノードN3までの距離
の短い方を記憶する。さらにステップ1206において選択
したノードN1、N3に探索開始点フラグをたてる。ステッ
プ1204において目的地側であればステップ1208に進み、
選択されたリンクL8上の点P3に一方通行規制に従って進
入できるノードN7および選択されたリンクL11上の点P4
に一方通行規制に従って進入できるノードN11を探索開
始点とする。ノードN7には交点P3からノードN7までの距
離を、ノードN11には交点P4からノードN11までの距離を
記録する。さらにステップ1209において選択したノード
N7、N11に探索終了点フラグをたてる。最後にステップ1
207において、探索開始点（ノードN1、N3）および探索
終了点（ノードN7、N11）に初期コストとして一定値
（例えば０）を付与する。以上で地点設定処理を終了す
る。

【００４９】ここで、探索開始点の探索終了点の組合せ
は計４通りある。全ての経路の組合せについて、これら
の経路の総コストを比較すると表３のようになる。

【００５０】

【表３】

【００５１】この場合、最小コスト経路はノードN3〜ノ
ードN7までの経路となり、総コストは266となる。

【００５２】このように、第３の実施例の特徴である地
点設定手法を用いて、第１および第２の実施例と同様に
経路探索処理を行う事により、最小コスト経路としてノ
ードN3−リンクL4−リンクL6−ノードN7を求めることが
できる。故に、第１および第２の実施例の地点設定手法
を使用した場合のように、目的地付近の道路とは離れた
道路上の交差点までの経路を求めてしまう現象がなくな
り、目的地へ到達するために適した経路を求めることが
できる。

【００５３】なお、図１２のステップ1205ではノードN3
には交点P1からノードN3までの距離または交点P2からノ
ードN3までの距離の短い方を記録したが、出発地からの
総距離の短い方を記録しても良いし、リンクに出るまで
の距離の短い方を記録してもよい。また、予め出発地か
らリンク上に下ろした垂線との交点と探索開始点との間
の形状データおよび目的地からリンク上に下ろした垂線
との交点と探索終了点との間の形状データを保持して置
くことによりリンク途中までの経路表示や誘導を行って
もよい。また、リンク形状に垂線が下ろせない場合、各
形状データの曲折点への距離中、一番距離が小さい点を
リンクとの交点として採用してもよい。

【００５４】（実施例４）次に本発明の第４の実施例に
ついて説明する。本発明の第４の実施例を示す推奨経路
案内装置のブロック図は第１の実施例と同様である。

【００５５】以上のように構成された第４の実施例の推
奨経路案内装置について以下にその動作を説明する。図
１３（ａ）は第４の実施例における道路網の例を示す
図、図１３（ｂ）は本道路網においてノード情報の例を
示す図、図１３（ｃ）は本道路網においてリンク情報の
例を示す図である。また、図１４は本発明の第４の実施
例における地点設定処理のフローチャートである。

【００５６】それでは、図１３の道路網の例と図１４の
地点設定処理のフローチャートを用いて第３の実施例と
の差異を説明する。まず、図１３（ａ）に示されるよう
にN1〜N12までの１２個のノードとL1〜L11までの１１本
のリンクで表される道路網において、道路ネットワーク
記録手段101には図１３（ｂ）に示されるようなノード
情報と図１３（ｃ）に示されるようなリンク情報が記憶
されている。ここで、各種記号は図２の場合と同様であ
る。

【００５７】このようなネットワークの場合、第１およ
び第２の実施例と同様に経路を求めると、探索開始点と
してノードN3が、探索終了点としてノードN6がそれぞれ
選択されるので、最終的に選択される経路はノードN3と
ノードN6を結ぶ経路ノードN3−リンクL4−リンクL6−ノ
ードN6が選択されてしまう。ゆえに、ノードN6までの経
路しか求められないので目的地▽に到達するかなり手前
までしか経路がわからない。また、第３の実施例と同様
に経路を求めると、探索開始点としてノードN3が、探索
終了点としてノードN5,N8,N9,N12が選択されるので、最
終的に選択される経路は探索開始点群（ノードN3）と探
索終了点群（ノードN5,N8,N9,N12）を結ぶ最小コスト経
路である経路ノードN3−リンクL4−ノードN5が選択され
てしまう。ゆえに、ノードN5を通り地点P3に到達する経
路しか求められないので目的地▽に至るにふさわしい経
路が求められない。そこで、第４の実施例として地点設
定処理を図１４のような処理に変更することによりこの
問題を解決する。

【００５８】第４の実施例における地点設定処理と第３
の実施例における地点設定処理の差異はステップ1407の
初期コストの設定にある。第３の実施例ではステップ12
07に示すように一律同じ値（０）としていたが、第４の
実施例ではステップ1407のようにリンクに下ろした垂線
の距離に比例したコストとリンク上を走行するためのコ
ストの和で初期コストを与える。ここで、ステップ1407
における比例係数ｍ１、ｍ２は正の実数である。なお、
これは出発地ＳからリンクL1へ下ろした垂線を仮想リン
クVL1（リンクL1との交点をP1）、リンクL3に下ろした
垂線を仮想リンクVL2（リンクL3との交点をP2）、また
目的地ＤからリンクL5に下ろした垂線を仮想リンクVL3
（リンクL5との交点をP3）、リンクL10に下ろした垂線
を仮想リンクVL4（リンクL10との交点をP4）として、そ
れぞれの仮想リンクに初期コスト相当の仮想リンクコス
トを割り付け、出発地Ｓから目的地Ｄまで仮想リンクを
含んだ道路ネットワーク上で最小コスト経路を求めた場
合と同じ結果が地図データに処理を加えなくても得られ
る特徴を持つ。

【００５９】例えば図１３（ａ）中のリンクの中で平均
走行速度が一番小さいものは時速１０ｋｍ／ｈである
が、仮想リンクコストとして仮想リンク上を時速５ｋｍ
／ｈで走行した事に等しい値を与える。また、仮想リン
クから通常リンク上へ出た地点から次の交差点まで進む
コストとして、通常リンク全体のコストを走行した距離
の比で分配した値を与える。ゆえに、ノードN3には次の
初期コストが与えられる。 [1] ５（ｍ）／５（ｋｍ／ｈ）×３６ …仮想リンクコスト ＋ ４３（リンクL1のコスト）／６０（ｍ）×５（ｍ） …リンクL1上の分配コスト ≒ ４０ （１０-1秒） ［リンクL1経由の初期コスト］ [2] ５（ｍ）／５（ｋｍ／ｈ）×３６ …仮想リンクコスト ＋ ２５２（リンクL3のコスト）／１４０（ｍ）×５（ｍ）…リンクL3上の分配コス ト ≒ ４５ （１０-1秒） ［リンクL3経由の初期コスト］ リンクL1経由の方がリンクL3経由よりも初期コストが小
さいのでノードN3にはリンクL1経由の情報が残される。
故に初期コストは４０となる。

【００６０】同様に、各探索開始点・探索終了点とも以
下の表４のような初期コストを持つ。

【００６１】

【表４】

【００６２】探索開始点の探索終了点の組合せは計８通
りある。以上の初期コストの元で全ての経路の組合せに
ついて、これらの経路の総コストを比較すると表５のよ
うになる。

【００６３】

【表５】

【００６４】この場合、最小コスト経路はノードN3〜ノ
ードN8までの経路となり、総コストは436となる。

【００６５】このように第４の実施例の特徴である地点
設定手法を用いて、第１の実施例と同様に経路探索処理
を行うことで探索開始点と探索終了点を結ぶ最短コスト
経路であるノードN3−リンクL4−リンクL6−リンクL8−
ノードN8を求めることができる。故に、第１、第２、第
３の実施例の地点設定手法を使用した場合のように、目
的地へ到達するには不適切な経路を選択する現象がなく
なり、目的地に対して適切な経路を求めることができ
る。

【００６６】なお、図１４のステップ1407ではリンクま
での距離に対して比例して仮想リンクコストコストを与
えたが、図１０（ａ）に示すように非連続的でもよい
し、図１０（ｂ）に示すように距離により比例乗数ｍを
変更してもよい。また、リンクへの垂線との交点からリ
ンクの端ノードまでのコストとして、リンク全体のコス
トを距離で分配したが、特別な仮想走行速度を想定して
リンクコストを付与し直してもよい。また、ノードまで
の直線距離に比例して初期コストを与えてもよい。さら
にこの場合、ノードまでの直線距離に対して図１０
（ａ）に示すように非連続的でもよいし、図１０（ｂ）
に示すように直線距離により比例乗数を変更してもよ
い。また、目的地から垂線をおろしたリンクを基準にし
た位置関係、すなわち経路上を走行してそのリンクから
目的地へ向かう場合左右どちらに曲がるかによって決定
する右左折のペナルティコストを目的地側の初期コスト
に加えてもよい。

【００６７】さらに、第１から第４の実施例共に、車両
の現在位置と向きを取得して出発地側の探索開始点の設
定を行なってもよい。例えば、車両がリンク上に存在し
なければ取得した位置情報を基に上記実施例に従って出
発地側の探索開始点を設定してもよいし、車両がリンク
上に存在すれば車両の前方方向のリンクの行き先ノード
を出発地側の探索開始点に設定してもよい。また、探索
開始点にリンク走行分に相当する初期コストを持たせて
もよい。また、車両がリンク上に存在した場合で一方通
行規制に従って車両の前方方向と反対向きに進むことが
可能な場合は、そのリンクの行き先ノードとは反対側の
ノードを出発地側の探索開始点に加えてもよい。その場
合、リンク走行分に相当するリンクコストとＵターンペ
ナルティコストを加えたコストを初期コストとして与え
てもよい。さらに、リンク上に現在位置が存在しない場
合、車両の向きとリンクの向きがなす角度により初期コ
ストにペナルティコストを加えてもよい。

【００６８】最後に、探索時に交差点で曲がる角度や道
なりから外れることなどによりコストを加算してもよい
し、探索する評価基準（コストの対象）は例えば料金や
走り易さ等の概念を含んでもよい。また、探索法は出発
地と目的地双方から探索する双方向探索を用いたが、出
発地または目的地のいずれか一方から探索する一方向探
索でもよい。その場合、探索の終了点側の初期コストは
その点が探索候補状態になったとき到達コストに加算コ
ストとして加えられる。その結果、加算コストを含んだ
総コストが最小となる経路が選出される。さらに一方向
探索の場合、目的地側を探索開始点として出発地側へ向
かって探索を広げてもよい。また、探索法については階
層化された地図を用いて探索を行なってもよいし、ダイ
クストラ法でなくても最小コスト経路を求められる方法
であればよい。また、出力手段は経路を表示するだけで
なく、車両の現在位置を取得し曲がるべき交差点の手前
で音声により誘導案内を行ってもよい。また、出発地側
と目的地側の地点設定法は同一でなくてもよい。

【００６９】

【発明の効果】このように本発明の第１の手段によると
地点設定した位置近傍の複数の地点に固有の探索開始時
の初期コストまたは探索終了点到達時の加算コストを与
えた探索開始点または探索終了点を設定することによっ
て、新たな入力作業を伴うことなく、順序づけられた複
数の探索開始点および探索終了点の中から合理的な探索
開始点および探索終了点を選択でき、かつ、行き過ぎ等
の不適切な経路を選出することを防ぐことができる。

【００７０】また、第２の手段によると第１の手段で選
択した複数の交差点に地点設定した位置からの距離の関
数で初期コストを与えてやることにより、地点設定した
位置から遠くの交差点が経路の開始点や終了点となるこ
とを防ぐことができる。

【００７１】さらに、第３の手段によると地点設定した
位置近傍の１本以上の道路上の両端交差点のなかで通行
規制を遵守して通ることができる交差点を探索開始点・
探索終了点として設定することにより、地点設定位置の
近傍道路に接続していない交差点が経路の開始点や終了
点となることを防ぐことができる。

【００７２】最後に、第４の手段によると第３の手段で
選択した複数の交差点に、地点設定位置の近傍道路まで
の距離の関数で与えられたコストと前記近傍道路上の走
行距離の関数で与えられたコストの和で初期コストを与
えることにより、出発地から目的地まで到達するために
最も適切な経路を選択することができる。

【図面の簡単な説明】

【図１】本発明の第１から第４の実施例を示す推奨経路
案内装置のブロック図

【図２】（ａ）は本発明の第１の実施例における道路網
の例を示す図 （ｂ）は本発明の第１の実施例における道路網において
ノード情報データの例を示す図 （ｃ）は本発明の第１の実施例における道路網において
リンク情報データの例を示す図

【図３】本発明の第１から第４の実施例における推奨経
路案内装置の全体動作を示すフローチャート

【図４】本発明の第１の実施例における地点設定処理の
フローチャート

【図５】本発明の第１から第４の実施例における経路探
索処理のフローチャート

【図６】本発明の第１から第４の実施例における出発地
側探索処理のフローチャート

【図７】本発明の第１から第４の実施例における目的地
側探索処理のフローチャート

【図８】（ａ）は本発明の第２の実施例における道路網
の例を示す図 （ｂ）は本発明の第２の実施例における道路網において
ノード情報データの例を示す図 （ｃ）は本発明の第２の実施例における道路網において
リンク情報データの例を示す図

【図９】本発明の第２の実施例における地点設定処理の
フローチャート

【図１０】（ａ）は本発明の第２、第４の実施例とは別
の初期コストの付与例を示す図（１） （ｂ）は本発明の第２、第４の実施例とは別の初期コス
トの付与例を示す図（２）

【図１１】（ａ）は本発明の第３の実施例における道路
網の例を示す図 （ｂ）は本発明の第３の実施例における道路網において
ノード情報データの例を示す図 （ｃ）は本発明の第３の実施例における道路網において
リンク情報データの例を示す図

【図１２】本発明の第３の実施例における地点設定処理
のフローチャート

【図１３】（ａ）は本発明の第４の実施例における道路
網の例を示す図 （ｂ）は本発明の第４の実施例における道路網において
ノード情報データの例を示す図 （ｃ）は本発明の第４の実施例における道路網において
リンク情報データの例を示す図

【図１４】本発明の第４の実施例における地点設定処理
のフローチャート

【図１５】（ａ）は従来の地点設定法では希望する経路
が求められない場合の道路網の例（目的地側）を示す図 （ｂ）は従来の地点設定法を用いて求めた選択経路の例
を示す図

【符号の説明】

１０１ 道路ネットワーク記憶手段 １０２ 地点設定手段 １０３ 探索開始終了点設定手段 １０４ 探索手段 １０５ 出力手段

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 平６−288782（ＪＰ，Ａ) 特開 平５−164564（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) G01C 21/00 - 21/24

Claims (11)

(57)【特許請求の範囲】
1. 【請求項１】交差点および道路の位置および接続関係を
   記録した道路ネットワーク記録手段と、出発地と目的地
   を設定する地点設定手段と、前記地点設定手段で設定し
   た出発地または目的地の情報から複数個の探索開始点ま
   たは探索終了点を設定し、それぞれに固有の探索開始時
   の初期コストまたは探索終了点到達時の加算コストを与
   える探索開始終了点設定手段と、前記探索開始終了点設
   定手段で設定した探索開始点から探索終了点までの経路
   を前記道路ネットワーク記録手段の情報から探索する探
   索手段と、前記探索手段で得られた経路を出力する出力
   手段とを備えたことを特徴とする推奨経路案内装置。
2. 【請求項２】探索開始終了点設定手段は、選択された各
   交差点と出発地または目的地との距離に関する関数で探
   索開始時の初期コストまたは探索終了点到達時の加算コ
   ストを与えることを特徴とする請求項１記載の推奨経路
   案内装置。
3. 【請求項３】探索開始終了点設定手段は、出発地と目的
   地の位置情報から近傍の道路リンクを各々１本以上選出
   し、そのリンクの両端の交差点を選択することを特徴と
   する請求項１記載の推奨経路案内装置。
4. 【請求項４】探索開始終了点設定手段は、各道路リンク
   の両端の交差点のうち通行規制を遵守して到達可能な交
   差点のみを選択することを特徴とする請求項３記載の推
   奨経路案内装置。
5. 【請求項５】探索開始終了点設定手段は、出発地または
   目的地から各道路リンク上の最も近い点とその点までの
   距離を求め、この距離の関数で探索開始時の初期コスト
   または探索終了点到達時の加算コストを与えることを特
   徴とする請求項４記載の推奨経路案内装置。
6. 【請求項６】探索開始終了点設定手段は、出発地または
   目的地から各道路リンク上の最も近い点を求め、その点
   から道路リンクの両端の交差点までの距離の関数で探索
   開始時の初期コストまたは探索終了点到達時の加算コス
   トを与えることを特徴とする請求項４記載の推奨経路案
   内装置。
7. 【請求項７】探索開始終了点設定手段は、出発地または
   目的地から各道路リンク上の最も近い点とその点までの
   距離を求め、この距離の関数で与えられるコストとその
   点から道路リンクの両端の交差点までの距離の関数で与
   えられるコストの和で探索開始時の初期コストまたは探
   索終了点到達時の加算コストを与えることを特徴とする
   請求項４記載の推奨経路案内装置。
8. 【請求項８】探索開始終了点設定手段は、出発地および
   目的地から各探索開始点および探索終了点までの距離の
   関数で探索開始時の初期コストまたは探索終了点到達時
   の加算コストを与えることを特徴とする請求項４記載の
   推奨経路案内装置。
9. 【請求項９】探索開始終了点設定手段は、車両の位置と
   向きから出発地側の探索開始点または出発地側の探索終
   了点を決定することを特徴とする請求項４記載の推奨経
   路案内装置。
10. 【請求項１０】探索開始終了点設定手段は、車両の向き
    と道路リンクのなす角度によるペナルティコストを出発
    地側の探索開始時の初期コストまたは出発地側の探索終
    了点到達時の加算コストに加えることを特徴とする請求
    項４記載の推奨経路案内装置。
11. 【請求項１１】探索開始終了点設定手段は、目的地と道
    路リンクの位置関係により右左折のペナルティコストを
    目的地側の探索開始時の初期コストまたは目的地側の探
    索終了点到達時の加算コストに加えることを特徴とする
    請求項４記載の推奨経路案内装置。