JPH1026535A

JPH1026535A - 最適経路探索方法

Info

Publication number: JPH1026535A
Application number: JP18182196A
Authority: JP
Inventors: Kazuhiro Sato; 和浩佐藤; Hiroshi Iwata; 浩志岩田
Original assignee: Fujitsu Social Science Labs Ltd
Current assignee: Fujitsu Social Science Labs Ltd
Priority date: 1996-07-11
Filing date: 1996-07-11
Publication date: 1998-01-27
Anticipated expiration: 2016-07-11
Also published as: JP4116681B2

Abstract

(57)【要約】【課題】道路データに基づいて出発地点から目的地点
に至る経路を探索し，最適経路を求める最適経路探索方
法に関し，目的地点に至るまでの最短時間の経路を求め
ることを目的とする。【解決手段】目的地点および出発地点となる地点を入
力する入力部と，道路データを保持する道路データ保持
部と，道路データをもとに出発地点から目的地点に至る
経路を探索して最適経路を求める経路探索部と，道路の
属性に応じて走行速度を定める速度テーブル保持部と，
経路情報を出力する出力部とを備えた経路探索装置にお
ける最適経路探索方法において，経路について速度テー
ブルを参照して所要時間を求め，所要時間により求めた
経路を評価し，出発地点から目的地点に至る最短所要時
間の経路を最適経路としてその経路情報を出力する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は，道路データに基づ
いて出発地点から目的地点に至る経路を探索し，経路を
求める経路探索装置における最適経路探索方法に関す
る。

【０００２】

【従来の技術】経路探索装置は，複数地点を経由して商
品の配達経路を求めるような場合に，道路データを基に
その最適経路を求めるものである。

【０００３】従来の経路探索装置は，ダイクストラ法等
により出発地点から開始して接続される道路区間を求
め，区間の距離を評価して最小距離の区間を最適道路区
間として選択し，順次目的地点まで最短距離の区間を求
め，そのようにして求めた出発地点から目的地点までの
経路を最適経路として出力していた。そして，従来は主
要道路のみの主要道路地図もしくは主要道路から分かれ
る枝道等の幅の狭い道まで含めた全道路の詳細道路地図
に基づいて最適経路を求めていた。

【０００４】

【発明が解決しようとする課題】実際の道路では道路の
幅員，交通渋滞等で法定の最高速度で移動することがで
きない場合があり，最短距離の経路であっても，実際に
は最短時間で目的地点に到達することができるとは限ら
ず，距離は長くても高速に移動できて所要時間の短い経
路も実際には存在する。そのため，出発地点から目的地
点までの最短距離の経路を最適経路とする従来の経路探
索装置で求められた経路が実際の運用での最適経路であ
るとは限らなかった。また，道路の幅員等を考慮して目
的地までの所要時間を推定し，求めた最短経路に補足的
情報として表示するものもあるが，その所要時間はあく
までも補足的な情報であり，所要最短時間の経路を最適
経路として出力するものではない。

【０００５】また，従来の経路探索装置で，処理を高速
化するために主要道路地図に基づいて経路探索した場合
には，目的地が主要道路上にない条件では，目的地まで
到達する経路を求めることができなかった。そのため，
目的地付近は詳細道路地図で補完する必要があるが，目
的地，出発地を地点とし多数の地点間最短経路を求める
ような場合には，それぞれの出発地点，目的地点毎に詳
細道路データにより補完する必要があり，長時間を必要
とした。

【０００６】本発明は，目的地点に至るまでの最適時間
の経路を求める最適経路探索方法を提供することを目的
とする。また，本発明は，出発地点，目的地点となる地
点が多数あり，各地点間の最適経路を全て求めるような
場合に高速に処理することのできる最適経路探索方法を
提供することを目的とする。

【０００７】

【課題を解決するための手段】本発明の基本構成(1)
は，目的地点および出発地点となる地点を入力する入力
部と，道路データを保持する道路データ保持部と，道路
データをもとに出発地点から目的地点に至る経路を探索
して最適経路を求める経路探索部と，道路の属性に応じ
て走行速度を定める速度テーブル保持部と，経路情報を
出力する出力部とを備えた経路探索装置における最適経
路探索方法において，経路について速度テーブルを参照
して所要時間を求め，所要時間により求めた経路を評価
し，出発地点から目的地点に至る最短所要時間の経路を
最適経路としてその経路情報を出力する構成を持つ。

【０００８】本発明の基本構成(2) は，目的地点および
出発地点となる地点を入力する入力部と，道路データを
保持する道路データ保持部と，道路データをもとに出発
地点から目的地点に至る経路を探索して最適経路を求め
る経路探索部と，最適経路の経路情報を出力する出力部
とを備えた経路探索装置における最適経路探索方法にお
いて，詳細道路データに基づいて該地点からその付近の
主要道路に至る経路を探索する周辺探索部と，詳細道路
データおよび主要道路データのうちの選択された道路デ
ータで経路探索をすることのできる全経路探索部とを備
え，経路探索部は，該周辺探索部により目的地の周辺の
主要道路上の道路点のうちから選択された道路点である
サテライトを求め，全経路探索部により出発地点からそ
の周辺の主要道路に至る経路を詳細道路データにより探
索し，そのようにして求められた主要道路上の道路点か
ら該サテライトもしくは目的地点が主要道路上ある場合
には目的地点に至る経路を主要道路データにより探索し
て最適経路を求める構成を持つ。

【０００９】図１は本発明の基本構成(1) を示す図であ
る。図１において，１は道路データ保持部であって，道
路データを保持するものである。

【００１０】２は区間データであって，道路を区間に分
割したデータであり，区間の距離，区間の属性（道路種
別（国道，一般道路等），道路の幅員等），走行速度の
調整係数を保持するものである。調整係数は通常は１で
あり，渋滞等の道路状況に応じてユーザが設定できるも
のである。

【００１１】３は属性，調整係数である。４は道路点デ
ータであって，道路上の点について接続区間を対応付け
たデータである。

【００１２】１０は速度テーブル保持部であって，道路
種別，幅員に対応した走行速度を保持するものである。
１１は速度テーブルである。

【００１３】１５は経路探索部であって，出発地点から
目的地点までの経路を探索し所要時間の短い経路を求め
るものである。２１は出発地点から目的地点までの経路
を探索する処理を表す。

【００１４】２２は探索した経路について，所要時間を
算出する処理を表す。２３は所要時間で経路を評価し，
最短時間の経路を求める処理を表す。２４は求めた経路
を最適経路として表示部に出力する処理を表す。

【００１５】２５は表示部である。２６は入力部であ
る。経路探索部１５は，入力された出発地点と目的地点
を基に，道路データ保持部１から与えられる道路データ
を参照して，出発地点から目的地点までの経路と求めた
経路の距離を求める。そして，速度テーブル保持部１０
から与えられる区間データの属性に対応する走行速度お
よび調整係数を基に求めた出発地点から目的地点までの
所要時間を求め，所要時間の短い経路を表示部２５に出
力する。例えば，ダイクストラ法により本発明の基本構
成(1) の最適経路を求める場合，出発地点から始まっ
て，出発地点に接続される区間の他方の道路点を求め
る。そして，出発地点に接続される各区間の属性により
速度テーブルを参照して，実際に移動可能な走行速度を
求める。また，そのようにして求めた走行速度に調整係
数を掛けて実際に近い走行速度を求める。そして，その
走行速度を基に区間を移動する所要時間で区間を求めて
経路毎に評価し，最短所要時間の経路を最適区間として
選択する。次に，このようにして求めた道路点について
同様に区間と区間を移動する時間を求めて，各区間につ
いて評価し，最短時間で移動できる区間を求める。この
処理を繰り返し目的地点に最短時間で至る経路を求め
る。

【００１６】本発明の基本構成(1) の速度テーブルは，
例えば，道路の法定最高速度に道路の幅員を考慮して予
めきめておくものであるが，速度テーブル変更手段を備
えていて，ユーザが，道路の渋滞状況，経験等に基づい
て変更できるものである。速度テーブルの変更は表示部
２５に速度テーブルを表示し，その表示画面上でユーザ
が設定地を変更する。また，調整係数は，例えば，製品
の出荷時点では全て１に設定されていて，道路の渋滞等
の状況に応じてユーザが設定できるものである。あるい
は，移動速度と移動地点についての履歴をとることがで
きる場合には，その履歴情報を基に調整係数を変更する
ようにしても良い。

【００１７】図２は，本発明の基本構成(2) を示す。図
２において，１は道路データ保持部であって，主要道路
と主要道路から分かれる枝道等の全道路の詳細道路デー
タ部と，主要道路だけの主要道路データ部を階層的に保
持するものである。

【００１８】１５は経路探索部であって、目的地から目
的地周辺の主要道路に至る経路を探索し，目的地周辺の
主要道路上の地点（サテライト）および目的地とサテラ
イトとの間の経路を求める周辺探索部および，出発地点
からサテライトもしくは目的地（目的地が主要道路上に
あった場合）までの経路を詳細道路データおよび主要道
路データを基に経路を求めるものである。

【００１９】１０は速度テーブル保持部である（探索し
た経路を所要時間で評価する場合に必要とし，距離で評
価する場合には不要である）。２５は表示部である。

【００２０】２６は入力部である。道路データ保持部１
において，４２は主要道路データ部である。

【００２１】４３は詳細道路データ部である。経路探索
部１５において，５１は周辺探索部であって，詳細道路
データにより目的地周辺を探索し，目的地周辺の主要道
路上の道路点（サテライト）および目的地とサテライト
間の経路を求めるものである。

【００２２】５２は全経路探索部であって，出発地点か
ら詳細道路データを基に出発地点近くの主要道路上の道
路点まで探索し，その道路点からは主要道路データに従
って，サテライトもしくは目的地（目的地が主要道路上
にある場合）までの経路を探索するものである。

【００２３】５３は詳細道路データに基づく経路探索の
処理であって，出発地点からその周辺の主要道路上の道
路点（Ｘ）までの経路を求める処理である。５４は主要
道路データに基づく経路探索の処理であって，出発地点
近くの主要道路上の道路点（Ｘ）からサテライト（Ｓ）
もしくは目的地（目的地が主要道路上にある場合）まで
の経路を主要道路データに従って探索する処理である。

【００２４】５５は探索経路を最短経路もしくは最短時
間で評価し最適経路を求める処理である。５６は求めた
最適経路を表示部に出力する処理である。

【００２５】図２の構成の動作を説明する。経路探索部
１５は，入力された出発地点および目的地点をもとに，
周辺探索部５１により，目的地点からその周辺の主要道
路上の道路点に至る経路を探索する。そして，例えば，
一定距離以内にあるその主要道路上の道路点のうちから
選択された道路点，例えば早く見つかった順で全個数の
３０％以内等をサテライトとして保持する。さらに，全
経路探索部により出発地点から目的地点までの経路を詳
細道路データもしくは主要道路データに基づいて経路探
索をする。その際，出発地点から探索を始めて，主要道
路の道路点（Ｘ）に到達するまでは詳細道路データをも
とに経路探索をする。次にその道路点（Ｘ）から目的地
までは主要道路地図を基に探索経路を評価しながら最短
距離もしくは最短所要時間の経路探索をする。そして，
サテライトもしくは目的地点（目的地点が主要道路上に
ある場合）に到達したら，その経路を求める経路とす
る。さらに，サテライトから目的地までは予め周辺探索
で求めておいた経路を採用する。最適経路は探索した経
路について最短距離もしくは最短所要時間の経路とす
る。なお，この周辺探索および全経路探索は，例えば，
前述のダイクストラ法等により行うものであり，前述し
たと同様に道路点に接続する区間を一つずつ延ばしなが
ら延ばした区間のうちの最短距離の区間もしくは区間を
通過するのに要する時間が最短の区間を求めながら経路
を探索する方法により行うものである。

【００２６】本発明の基本構成(1) によれば，出発地点
から目的地点まで最短時間で移動できる経路を出力し，
現実に最も有効な経路を出力することができる。また，
調整係数によりきめ細かく所要時間を変更できるので，
実際の移動時間に近い条件で経路探索行うことができ
る。また，速度テーブルもユーザが容易に変更できるの
で，実際の道路状況に柔軟に対応することができる。

【００２７】また，本発明の基本構成(2) によれば，出
発地点から目的地点までの最短経路もしくは最小所要時
間の経路に近い経路を高速に求めることができる。特
に，出発地点および目的地点となる地点が複数あり，そ
れぞれの地点を出発地点および目的地点としてそれぞれ
の地点間の最適経路を求める場合には，それぞれの目的
地周辺のサテライトを求めてあるので，目的地周辺の詳
細道路データによる探索時間を大幅に減らすことがで
き，目的地点までの経路探索を高速に行うことができ
る。

【００２８】

【発明の実施の形態】図３は本発明の基本構成(1) のシ
ステム構成の実施例を示す。図３において，６１は速度
テーブル保持部であって，速度テーブルを保持する磁気
ディスク装置等である。

【００２９】６２は速度テーブルのデータを表す。６３
は道路データ保持部であって，道路データを保持するＣ
ＤＲＯＭ等である。

【００３０】６４は道路点データである。６５は区間デ
ータである。６６は地点データ保持部であって，目的地
点，出発地点となる地点の道路点およびその名称（商店
名等）等をデータとしてもつものであり，磁気ディスク
装置等である（地点データはユーザが指定するものであ
る）。

【００３１】６７は地点データを表す。７１は評価テー
ブル保持部であって，求めた経路の評価値（最短所要時
間）を保持するものである。

【００３２】７２は経路探索プログラムであって，出発
地点から道路点データと区間データに従って経路を求
め，区間毎に距離およびその区間を通過する所要時間
（出発地点からの区間毎の累積時間）を求め，所要時間
で経路を評価しながら最短時間で通過できる区間を選択
して目的地に至るまでの経路を求めるものである。

【００３３】７３は経路探索部であって，出発地点から
目的地点までの経路を探索するものである。７４は所要
時間算出部であって，求めた区間の距離と速度テーブル
を参照して求めた区間を通過する所要時間を算出するも
のである。

【００３４】７５は所要時間評価部であって，求めた区
間の所要時間を評価し，最短時間で通過できる区間を求
めるものである。７７は経路情報保持部であって，最適
経路として選択された区間データを保持するものであ
る。

【００３５】８１はＣＰＵである。８２はメモリであ
る。８３はディスプレイである。

【００３６】８４はキーボードである。８５はマウスで
ある。９１は走行履歴情報であって，自動車の車載装置
で獲得された自動車の走行記録を保持する磁気ディクス
装置，メモリカード等であり，自動車の走行日時，走行
した位置（緯度，経度），走行速度等のデータを保持す
るものである。自動車の走行記録から速度テーブルの調
整係数を変更する場合に使用するものである。

【００３７】９２は調整係数変更手段であって，自動車
の走行履歴から速度テーブルの調整係数を変更する手段
である。９３は速度テーブル変更手段であって，ユーザ
が速度テーブルを変更する時に使用するものである。

【００３８】図３のシステム構成の動作は後述する。図
４は，本発明の道路の区間データ，道路点データ，地点
データの実施例であり，区間データ，道路点データはＣ
ＤＲＯＭ等に保持されているものである。但し，道路区
間データの内，調整係数については変更することもある
ため，道路区間データ全体または調整係数のみは更新可
能な媒体に保持する必要がある。また，地点データはユ
ーザが設定するものである。

【００３９】図４ (a)は道路区間データの例である。区
間データは，道路を区間に分割したデータであり，区間
番号をもち，区間の両端の接続道路点番号１，接続道路
点番号２，区間長，属性（高速道路，国道等の道路種
別，道路の幅員等），道路の走行速度の調整係数を保持
するものである。調整係数は，デフォルト値として１を
もつが，渋滞情報，工事情報もしくは経験等によりユー
ザが自由に変更できるものである（例えば，道路状況に
応じて０．９，０．６５等の値を設定する）。あるいは
自動車の走行履歴を基に，区間の過去の走行履歴を基に
調整係数を変更することもできる。

【００４０】図４ (b)は道路点データの例である。道路
点データは，道路点番号を持ち，道路点に接続する区間
データ（接続区間番号）を持つものである。

【００４１】図４ (c)は地点データの例である。地点デ
ータは，出発地点，目的地点の道路点番号，名称（商店
名等）等により構成されるものであり，ユーザが設定す
るものである。

【００４２】図５は速度テーブルの例である。道路種別
毎に道路の幅員等を考慮して走行速度を定めたものであ
る。例えば，道路が一般国道で法定最高速度が時速６０
ｋｍの道路の場合，道路の幅員が１３．０ｍ以上あれ
ば，走行速度は時速６０ｋｍとする。幅員が１３．０ｍ
未満〜５．５ｍ以上では時速５５ｋｍ，幅員が５．５ｍ
未満〜３．０ｍ以上では時速５０ｋｍ，３．０ｍ未満で
は４０ｋｍ，未調査の道路では３０ｋｍとする。また，
このテーブルは画面に表示でき，ユーザにより変更可能
なものである。この速度テーブルを基に，ある道路区間
の「平均速度＝区間の走行速度×調整係数」により区間
の平均速度を算出する。前述したように，調整係数は区
間データの属性として持つものであり，デフォルト値が
１であって，道路の渋滞，あるいは走行履歴等により変
更可能なものである。

【００４３】図６は本発明の評価テーブルと経路情報の
例を示す図である。図６ (a)は評価テーブルの例であっ
て，道路点毎の評価値と直前の道路点番号をもつもので
ある。評価値は，区間の平均速度を基に算出した平均速
度を基に区間を通過するのに要する時間の最小値であ
り，評価値は出発地点から各道路点を通過することによ
り得られる累積値である。

【００４４】図６ (b)は，経路情報の例であって，出発
地点と到達地点毎にその経路情報のあるポインタとポイ
ンタで指定された位置に通過道路点数，通過道路点番号
をもつものである。最初に全ての道路点の評価値に最大
値（例えば，９９９９９９）を設定し，出発地点に対応
する道路点の評価値には０を設定する。全道路点の中で
評価値の最小の道路点（仮にＡとする）を求めて，その
道路点に接続される区間データを基に，その距離，属性
によりその区間を通過する所要時間を求め，その道路点
の評価値との合計（累積所要時間）を得る。求めた累積
所要時間が，その区間によって接続される他方の道路点
（仮にＢとする）の評価値がより小さければ，Ｂの評価
値を累積所要時間とし，直前の道路点番号はＡとなる。
これをＡから接続される全道路区間について行った後
に，同様に全道路点の中で評価値の最小の道路点を求め
て，探索作業を繰り返す。評価テーブルはその時点での
各道路点までの最小累積所要時間であり，直前の道路点
番号をトレースしていくと，出発地点までの経路が分か
る。このようにして，目的地点に至るまで評価テーブル
を作成するとともに，図６ (b)に示すように経路情報を
作成する。出発地点から目的地点に至るまでに選択した
道路点番号（通過道路点番号０，通過道路点番号１等）
を経路情報に記録する。

【００４５】図７は，本発明の基本構成(1) をダイクス
トラ法に適用する場合の実施例である。Ｓ１評価テーブルの全ての道路点の評価値に最大値を
設定する（初期値）。

【００４６】Ｓ２出発地点となる道路点の評価値を０
とする（初期値）。Ｓ３評価値の最小の道路点を調べる（これをカレント
道路点と呼ぶ）。Ｓ４カレント道路点は目的地点か判定する（目的地点
であるかないかは地点データを参照する）。目的地点で
なければＳ５以後の処理を行い，目的地点であればＳ１
１の処理をする。

【００４７】Ｓ５評価対象を接続区間番号１とする。Ｓ６接続区間を通ってカレント道路点でない方の接続
道路点の評価値を求める。評価値は，「評価値＝カレン
ト道路点の評価値＋（接続区間の区間長／走行速度×接
続区間の調整係数）」で算出する。走行速度は接続区間
の道路種別，幅員に応じて速度テーブルから求める。

【００４８】Ｓ７評価値は既に設定されている値より
小さいか判定する。小さければＳ８の処理を行い，小さ
くなければＳ９の処理をする。Ｓ８評価テーブルの接続道路点の評価値と直前の道路
点番号を設定する。直前の道路点＝カレント道路点であ
る。

【００４９】Ｓ９カレント道路点の接続道路はまだあ
るか判定する。あればＳ１０以後の処理を行い，なけれ
ばＳ３以後の処理を繰り返す。Ｓ１０評価対象を次の接続区間として，Ｓ６以後の処
理を繰り返す。

【００５０】Ｓ１１カレント道路点の評価値を所要時
間とする。カレント道路点から直前の道路点を順にトレ
ースして経路情報を求め，出力する。図８は本発明の実
施例２の説明図であって，本発明の基本構成(2) の実施
例の説明図である。

【００５１】商品の配達先が多数あって最適な配達経路
を求めるような時，目的地点が複数地点あり，最短経路
もしくは最短時間で各地点を通過して出発地点に戻る経
路を求める必要がある。このような場合に，各地点間
（地点がＡ，Ｂ，Ｃの３箇所あるとすると，Ａを出発地
点としてＢ，Ｃを目的地点とし，地点Ｂを出発地点とし
てＣを目的地点とする）を最短距離もしくは最短時間で
移動することのできる経路を求めておくと，目的地点を
経由する順番，経路を求めるのに都合が良い。本実施例
２はそのような場合に，各地点間の最短経路に近い経路
を高速に求めることができるようにしたものである。

【００５２】図８ (a)は主要道路の道路データと詳細道
路データの道路データを重ねたイメージである。太線は
主要道路であり，細線は主要道路から分かれた枝道を表
す。地点ｉは出発地点もしくは目的地点を表す。

【００５３】図８ (b)は主要道路の道路データを表す。
図８ (c)は全道路の詳細道路データであって，主要道路
と主要道路から分かれた枝道を含む全道路データであ
る。

【００５４】図８ (c)において，Ａ，Ｂ，Ｃは地点であ
って，ＡＢ間の最短経路，ＡＣ間の最短経路を求める場
合には，Ａを出発地点，Ｂ，Ｃは目的地点とする。また
ＢＣ間の最短経路を求める場合にはＢを出発地点，Ｃを
目的地点とする。Ｂを出発地点としてＡを目的地点とす
る場合は，Ａを出発地点としてＢを目的地点とする場合
に同じ経路とする。同様にＣを出発地点としてＡ，Ｂを
目的地点とする場合も同様にＡもくしはＢを出発地点と
してＣを目的地点とした場合と同じ経路を最短経路とす
る。

【００５５】図９は，本発明の実施例の目的地点周辺の
探索と出発地点周辺の探索の説明図である。図９ (a)
は，目的地点周辺の探索の説明図である。

【００５６】地点Ａを目的地点とする（図８ (c)とは地
図が異なる）。詳細道路データにより地点Ａから始め
て，主要道路に至る経路を求める。そして，一定の距離
以内の主要道路上の道路点（Ａ₁，Ａ₂，Ａ₃）をサテ
ライトとしてその道路点および地点Ａからサテライトに
至る経路を保持する。

【００５７】図９ (b)は出発地点の周辺の経路探索の説
明図である。Ｂは出発地点である（図８の地点Ｂに対応
していない）。地点Ｂから開始して，詳細道路データに
より経路探索を開始し，一定の距離以内の主要道路上の
道路点（Ｘ（複数点あっても良い），Ｂ自身のサテライ
ト）を通過後は，主要道路データにより目的地点（目的
地点が主要道路上にある場合）もしくはサテライトまで
の最短経路を求める。

【００５８】図９ (c)は，そのようにして求めた，図８
のＡ，Ｂ，Ｃの各地点間の最短経路情報（この実施例２
では最短距離）の表示の例である。表示する情報は経路
情報であって，出発地点から目的地点までの道路点の通
過情報等も出力することができる。

【００５９】図１０は，本発明の実施例２のシステム構
成である。図１０において，６３は道路データ保持部で
あって，道路データを保持するＣＤＲＯＭ等であり，詳
細道路データ部１１０と主要道路データ部１１１を階層
構造に構成したものてある。

【００６０】６６は地点データ保持部であって，地点デ
ータ（目的地点，出発地点となる地点の道路点，その名
称，および自身が目的地となった場合のサテライト数
等）を保持するものである。

【００６１】６７は地点データを表す。７１は評価テー
ブル保持部であって，求めた経路の評価値（この実施例
２では最短経路）を保持するものである。

【００６２】７２は経路探索プログラムであって，出発
地点から目的地点に至る最短経路を求めるものである。
７７は経路情報保持部であって，選択した最適経路（区
間データ）を保持するものである。

【００６３】８１はＣＰＵである。８２はメモリであ
る。８３はディスプレイである。

【００６４】８４はキーボードである。８５はマウスで
ある。道路データ保持部６３において，１１０は詳細道
路データ部である。

【００６５】１１１は主要道路データ部である。経路探
索プログラム７２において，１２１は周辺探索部であっ
て，目的地周辺のサテライトを求めるものである。

【００６６】１２２は全経路探索部であって，出発地点
から目的地点もしくはサテライトに至る最短経路を求め
るものである。１２３は経路評価部であって，最短経路
を求めるものである。

【００６７】１３１は道路点付随データ保持部であっ
て，道路地点毎のサテライト元の地点番号等の情報を保
持するものである。道路データ保持部の詳細道路データ
部，主要道路データ部は道路点データ，区間データによ
り構成されるがその構成は図４と同様であるので説明は
省略する。また，評価テーブル，経路情報保持部の構成
も図６と同様であるので説明は省略する（但し，実施例
２では評価値は最短距離である）。

【００６８】図１１は道路点付随データ，地点データの
例を示す。図１１ (a)は道路点付随データの例であっ
て，周辺探索を行って得られたサテライトおよびその時
に生成された目的地点からサテライトまでの経路を保持
するものである。道路点付随データは，道路点番号毎に
地点番号，サテライト個数，各サテライト元地点番号，
その経路情報を持つ位置を指定する経路情報へのポイン
タをもつものである（例えば，図９ (a)でサテライトＡ
₂に対応する道路点番号に対しては地点そのものはここ
にはないため，地点番号には無を意味する−１を持ち，
地点ＡとサテライトＡ₃の間の経路情報をもつ。また，
目的地点Ａに対応する道路点番号に対しては地点番号に
地点Ａを持ち，サテライトはないため，サテライト個数
は０となる）。経路情報ポインタ指定された場所に経路
の通過点の個数，通過道路点の番号が記録される。ま
た，求めたサテライトは，次回に同じ目的地点を探索す
る場合に再使用することができる。

【００６９】図１１ (b)は地点データの例であって，地
点番号毎に対応する道路点番号，自身のもつサテライト
数，名称（商店名等）を保持するものである。自サテラ
イト数は，周辺探索により求められたサテライトに基づ
いて記録されるものである（図９ (a)の地点Ａの場合，
自サテライト数は３である）。また，地点の名称（商店
名等）はユーザが書き込むものである。

【００７０】本実施例において，探索は，出発地点から
始めるが，あらかじめ求めてある出発地点のサテライト
から出発しないのは，目的地点が出発地点のサテライト
より出発地点に近い半径内にある場合，最適経路が求め
られなくなるのを防ぐためである。

【００７１】図１２は本発明の実施例２の経路探索プロ
グラムの全体的処理のフローチャートである。経路探索
の対象となる地点（図８のＡ，Ｂ，Ｃ等）は地点０〜地
点（ｎ−１）のｎ個あり，ｎ個の地点間の経路探索を行
うとする。Ｓ１〜Ｓ４は目的地点周辺のサテライトを求
める処理であり，Ｓ５〜Ｓ８は出発地点からサテライト
もしくは目的地点までの全経路探索の処理である。

【００７２】Ｓ１ｉを０とする（初期値）。Ｓ２ｎ個の地点について周辺探索を行ったか判定す
る。全て行っていれば（ｉ≧ｎであれば）Ｓ５の処理を
行う。全て行っていなければ（ｉ≧ｎでなければ）Ｓ３
の処理を行う。

【００７３】Ｓ３周辺探索プログラムにより地点ｉの
周辺の探索をする（この処理をとする）。Ｓ４ｉをｉ＋１としてＳ２以後の処理を繰り返す。

【００７４】Ｓ５ｉを０にクリアして，Ｓ６以後の処
理をする。Ｓ６ｎ個の地点について全て全経路探索を行ったか判
定する（（ｉ≧ｎか判定する）。ｉ≧ｎでなければ全て
の地点について行っていないのでＳ７の処理を行う。ｉ
≧ｎであれば全ての地点について行ったので処理を終了
する。

【００７５】Ｓ７地点ｉを出発地点として経路探索を
行い，他の全地点（目的地点）との経路を求める。Ｓ８ｉをｉ＋１としてＳ６以後の処理を繰り返す。

【００７６】図１３は本発明の周辺道路探索のフローチ
ャートであって，図１２のの処理の詳細である。本処
理は詳細道路データに対して行う。Ｓ１地点ｉの対応する道路点の道路点付随データに地
点番号を設定する。

【００７７】Ｓ２全道路点の評価値を最大にする。Ｓ３地点ｉに対応する道路点の評価値を最小にする。Ｓ４評価値の最小の道路点を調べ，これをカレント道
路点とする。

【００７８】Ｓ５周辺探索は終了したか判定する。終
了していなければＳ６の処理をする。終了していれば，
処理を終了する。終了の判断条件は，例えば，サテライ
トが６箇所見つかった場合等による。

【００７９】Ｓ６カレント道路点に対応する主要道路
があるか判定し，あればＳ７の処理を行い，なければＳ
８の処理を行う。Ｓ７カレント道路点の道路点付随データにサテライト
情報を設定する。即ち，サテライト元地点番号に地点番
号を設定する。地点ｉの対応する道路点からカレント道
路点までの通過道路点番号を設定する。

【００８０】Ｓ８カレント道路点から接続されている
道路区間を評価し，評価テーブルに評価値を設定し，Ｓ
４以後の処理を繰り返す。図１４および図１５は本発明
の実施例２の全経路探索のフローチャートであって，図
１２のの処理の詳細である。

【００８１】Ｓ１詳細道路および主要道路（全道路）
の評価値を最大にする。Ｓ２地点ｉに対応する評価値を最小にする。Ｓ３評価値の最小の道路点を調べ，これをカレント道
路点とする。

【００８２】Ｓ４カレント道路点に地点ｉはあるか判
定し，あればＳ５の処理を行い，なければＳ７の処理を
する。Ｓ５地点ｉからカレント道路点までの通過道路の情報
を経路として出力する。

【００８３】Ｓ６地点ｉからの経路が求まっていない
地点（目的地点）はあるか判定し，あればＳ７の処理を
行い，なければ処理を終了する。Ｓ７カレント道路点にサテライト（目的地点のサテラ
イト）はあるか判定し，あればＳ８の処理を行い，なけ
ればＳ１１の処理を行う。

【００８４】Ｓ８サテライト元の地点が求まっている
か判定し，求まっていればＳ１０’の処理を行い，求ま
っていなければＳ９の処理を行う。Ｓ９地点ｉからのカレント道路点までの通過道路点の
情報とサテライトの通過道路点の情報を連結してサテラ
イト元地点までの経路とする。

【００８５】Ｓ１０地点ｉからの経路が求まっていな
い地点があるか判定し，なければ処理を終了し，あれば
Ｓ１０’の処理を行う。Ｓ１０’カレント道路点にはまだサテライトはあるか判
定し，あればＳ８以降の処理を繰り返し，なければＳ１
１以後の処理をする。Ｓ１１カレント道路点から接続されている道路区間を
評価し，評価テーブルに評価値を設定する。

【００８６】Ｓ１２主要道路の探索に切り換えるか判
定し，主要道路に切り換えるならば，Ｓ１３の処理を
し，切り換えない場合にはＳ３以後の処理を繰り返す。
主要道路に切り換えるか切り換えないかの条件は，例え
ば，地点ｉ（出発地点）のサテライト（の処理で求め
たサテライト）を全て通過したか等の条件で判定する。

【００８７】Ｓ１３詳細道路の道路点で対応主要道路
があるものは評価値を主要道路にコピーする。これ以降
の探索対象は主要道路とし，Ｓ３以降の処理を繰り返
す。図１６は本発明の実施例３のシステム構成であっ
て，本発明の基本構成(2) の評価を最短時間で行う場合
のシステム構成である。

【００８８】図１６において，図１０と共通部分は共通
番号である。６１は速度テーブル保持部であって，図３
の本発明の実施例１の速度テーブル保持部と同じもので
ある。

【００８９】７１は評価テーブル保持部であって，評価
値が最短時間である点で図１０の場合と異なるのみであ
る。７２は経路探索プログラムであって，経路評価部が
経路を最短時間で評価する点でのみ図１０と異なる。

【００９０】９１’は走行履歴情報保持部であって，図
３の走行履歴と同様である。９２は調整係数変更手段で
あって，図３の調整係数変更手段と同様である。９３は
速度テーブル変更手段であって，図３の速度テーブル変
更手段と同様である。

【００９１】図１６のシステム構成の動作のフローチャ
ートは，経路の評価を最短時間で行う点を除いて，図１
２，図１３，図１４，図１５のフローチャートと同様で
ある。

【００９２】図１７は本発明の速度テーブルの変更方法
と調整係数の変更方法の実施例である。図１７ (a)は速
度テーブルの変更方法である。

【００９３】速度テーブルを速度テーブル表示手段９
３’によりディスプレイ８３に表示する。ディスプレイ
８３の画面上で走行速度を変更する欄を入力手段８４’
（マウス，キーボード等）によりカーソルで指定し，変
更する走行速度を入力する。速度テーブル変更手段９３
は，速度テーブルのカーソルで指定された欄の走行速度
を指定された速度に変更する。

【００９４】図１７ (b)は調整係数の変更方法(1) であ
る。道路データ保持部６３に保持されている区間データ
を道路データ表示手段９３”によりディスプレイ８３に
表示する。ディスプレイ８３の画面上で変更する調整係
数を入力手段８４’によりカーソルで指定し，変更する
調整係数を入力する。調整係数変更手段９２は，道路デ
ータ保持部６３の指定された区間データの調整係数を指
定された値に変更する。

【００９５】図１８は調整係数の変更方法の実施例であ
る。調整係数の変更方法(2) であって，走行履歴情報保
持部９１’に記録されている走行履歴情報を基に調整係
数を変更する方法を示す。

【００９６】調整係数変更手段９２は速度テーブルから
調整係数を変更する区間の走行速度を求める（Ｓ１）。
走行履歴情報保持部９１’から走行履歴情報を入力する
（Ｓ２）。走行履歴情報の走行した位置の緯度，経度と
道路データの区間の緯度，経度データを比較し，調整係
数を変更する区間を実際に走行した速度を求め，その平
均速度を求める（走行履歴情報が道路データの区間ＩＤ
と共通のＩＤをもっていれば区間ＩＤにより実際の走行
速度を求める）（Ｓ３）。そして速度テーブルから求め
た走行速度と走行履歴情報から求めた走行速度を比較し
調整係数を求める（例えば比をとる）。そして，調整係
数変更手段９２は道路データ保持部６３のその区間の調
整係数を求めた調整係数で変更する。

【００９７】

【発明の効果】本発明の基本構成(1) によれば，出発地
点から目的地点まで最短時間で移動できる経路を出力
し，現実に最も有効な経路を出力することができる。ま
た，調整係数によりきめ細かく所要時間を変更できるの
で，実際の移動時間に近い条件で経路探索行うことがで
きる。また，速度テーブルもユーザが容易に変更できる
ので，実際の道路状況に柔軟に対応することができる。

【００９８】また，本発明の基本構成(2) によれば，出
発地点から目的地点までの最短経路もしくは最小所要時
間の経路に近い経路を高速に求めることができる。特
に，目的地が多数ある場合には，それぞれの目的地周辺
のサテライトおよびその経路を求めてあるので，目的地
周辺の詳細道路データによる探索時間を大幅に減らすこ
とができ，目的地点までの経路探索を高速に行うことが
できる。

【図面の簡単な説明】

【図１】本発明の基本構成(1) を示す図である。

【図２】本発明の基本構成(2) を示す図である。

【図３】本発明の基本構成(1) のシステム構成の実施例
を示す図である。

【図４】本発明の道路区間のデータ，道路点データ，地
点データの実施例を示す図である。

【図５】本発明の速度テーブルの例を示す図である。

【図６】本発明の評価テーブルと経路情報の例を示す図
である。

【図７】本発明の実施例１のフローチャート（ダイクス
トラ法）を示す図である。

【図８】本発明の実施例２の説明図である。

【図９】本発明の実施例２の説明図である。

【図１０】本発明の実施例２のシステム構成を示す図で
ある。

【図１１】本発明の道路点付随データと地点データの例
を示す図である。

【図１２】本発明の実施例２の全体的フローチャートを
示す図である。

【図１３】本発明の目的地点周辺の経路探索のフローチ
ャートを示す図である。

【図１４】本発明の実施例２の全経路探索のフローチャ
ート（その１）を示す図である。

【図１５】本発明の実施例２の全経路探索のフローチャ
ート（その２）を示す図である。

【図１６】本発明のシステム構成の実施例３を示す図で
ある。

【図１７】本発明の速度テーブルの変更方法と調整係数
の変更方法の実施例を示す図である。

【図１８】本発明の調整係数の変更方法の実施例を示す
図である。

【符号の説明】

１：道路データ保持部２：区間データ３：属性，調整係数４：道路点データ１０：速度テーブル保持部１１：速度テーブル１５：経路探索部２５：表示部２６：入力部４２：主要道路データ部４３：詳細道路データ部

Claims

【特許請求の範囲】

【請求項１】目的地点および出発地点となる地点を入
力する入力部と，道路データを保持する道路データ保持
部と，道路データをもとに出発地点から目的地点に至る
経路を探索して最適経路を求める経路探索部と，道路の
属性に応じて走行速度を定める速度テーブル保持部と，
経路情報を出力する出力部とを備えた経路探索装置にお
ける最適経路探索方法において，経路について速度テー
ブルを参照して所要時間を求め，所要時間により求めた
経路を評価し，出発地点から目的地点に至る最短所要時
間の経路を最適経路としてその経路情報を出力すること
を特徴とする最適経路探索方法。
【請求項２】速度テーブルの変更手段を備え，速度テ
ーブルは表示画面上でユーザにより随時変更可能である
ことを特徴とする請求項１に記載の最適経路探索方法。
【請求項３】速度データは走行速度の調整係数を備
え，調整係数はユーザにより調整可能であって，速度テ
ーブルから求まる走行速度を調整係数により調整するこ
とを特徴とする請求項１に記載の最適経路探索方法。
【請求項４】目的地点および出発地点となる地点を入
力する入力部と，道路データを保持する道路データ保持
部と，道路データをもとに出発地点から目的地点に至る
経路を探索して最適経路を求める経路探索部と，最適経
路の経路情報を出力する出力部とを備えた経路探索装置
における最適経路探索方法において，詳細道路データに
基づいて該地点からその付近の主要道路に至る経路を探
索する周辺探索部と，詳細道路データおよび主要道路デ
ータのうちの選択された道路データで経路探索をするこ
とのできる全経路探索部とを備え，経路探索部は，該周
辺探索部により目的地の周辺の主要道路上の道路点のう
ちから選択された道路点であるサテライトを求め，全経
路探索部により出発地点からその周辺の主要道路に至る
経路を詳細道路データにより探索し，そのようにして求
められた主要道路上の道路点から該サテライトもしくは
目的地点が主要道路上ある場合には目的地点に至る経路
を主要道路データにより探索して最適経路を求めること
を特徴とする最適経路探索方法。
【請求項５】最適経路を経路の距離により評価し，最
短距離に近い経路を最適経路とすることを特徴とする請
求項４に記載の最適経路探索方法。
【請求項６】経路を移動する速度を表す速度テーブル
を備え，最適経路を移動する時間により経路を評価し，
最短時間に近い経路を最適経路とすることを特徴とする
請求項４に記載の最適経路探索方法。
【請求項７】出発地点および目的地点となる地点が複
数あり，それぞれの地点を出発地点および目的地点とし
てそれぞれの地点間の最適経路を求め，それぞれの地点
間の最適経路情報を出力することを特徴とする請求項
４，５もしくは６に記載の最適経路探索方法。
【請求項８】求めたサテライトを保存しておき，次回
の探索時に再使用することを特徴とする請求項４，５，
６もしくは７に記載の最適経路探索方法。