最適経路探索方法
【課題】道路データに基づいて出発地点から目的地点に至る最適経路を探索する最適経路探索方法に関し，出発地点，目的地点となる地点が多数あり，各地点間の最適経路を全て求めるような場合でも高速に処理することを目的とする。
【解決手段】経路探索部１５において，周辺探索部５１は，詳細道路データに基づいて，目的地の周辺の主要道路上の道路点のうちから選択された道路点であるサテライトを求める。全経路探索部５２は，出発地点からその周辺の主要道路に至る経路を詳細道路データにより探索し，そのようにして求められた主要道路上の道路点から，周辺探索部５１により求められたサテライト，もしくは目的地点が主要道路上ある場合には目的地点に至る経路を主要道路データにより探索し，最適経路を求める。
【解決手段】経路探索部１５において，周辺探索部５１は，詳細道路データに基づいて，目的地の周辺の主要道路上の道路点のうちから選択された道路点であるサテライトを求める。全経路探索部５２は，出発地点からその周辺の主要道路に至る経路を詳細道路データにより探索し，そのようにして求められた主要道路上の道路点から，周辺探索部５１により求められたサテライト，もしくは目的地点が主要道路上ある場合には目的地点に至る経路を主要道路データにより探索し，最適経路を求める。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，道路データに基づいて出発地点から目的地点に至る経路を探索し，経路を求める経路探索装置における最適経路探索方法に関する。
【背景技術】
【０００２】
経路探索装置は，複数地点を経由して商品の配達経路を求めるような場合に，道路データを基にその最適経路を求めるものである。
【０００３】
従来の経路探索装置は，ダイクストラ法等により出発地点から開始して接続される道路区間を求め，区間の距離を評価して最小距離の区間を最適道路区間として選択し，順次目的地点まで最短距離の区間を求め，そのようにして求めた出発地点から目的地点までの経路を最適経路として出力していた。そして，従来は主要道路のみの主要道路地図もしくは主要道路から分かれる枝道等の幅の狭い道まで含めた全道路の詳細道路地図に基づいて最適経路を求めていた。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来の経路探索装置で，処理を高速化するために主要道路地図に基づいて経路探索した場合には，目的地が主要道路上にない条件では，目的地まで到達する経路を求めることができなかった。そのため，目的地付近は詳細道路地図で補完する必要があるが，目的地，出発地を地点とし多数の地点間最短経路を求めるような場合には，それぞれの出発地点，目的地点毎に詳細道路データにより補完する必要があり，長時間を必要とした。
【０００５】
また，実際の道路では道路の幅員，交通渋滞等で法定の最高速度で移動することができない場合があり，最短距離の経路であっても，実際には最短時間で目的地点に到達することができるとは限らず，距離は長くても高速に移動できて所要時間の短い経路も実際には存在する。そのため，出発地点から目的地点までの最短距離の経路を最適経路とする従来の経路探索装置で求められた経路が実際の運用での最適経路であるとは限らなかった。また，道路の幅員等を考慮して目的地までの所要時間を推定し，求めた最短経路に補足的情報として表示するものもあるが，その所要時間はあくまでも補足的な情報であり，所要最短時間の経路を最適経路として出力するものではない。
【０００６】
本発明は，出発地点から目的地点に至るまでの経路を高速に求めることができる最適経路探索方法を提供することを目的とする。また，本発明は，出発地点，目的地点となる地点が多数あり，各地点間の最適経路を全て求めるような場合に高速に処理することができるようにすることを目的とする。
【課題を解決するための手段】
【０００７】
本発明の基本構成は，目的地点および出発地点となる地点を入力する入力部と，道路データを保持する道路データ保持部と，道路データをもとに出発地点から目的地点に至る経路を探索して最適経路を求める経路探索部と，最適経路の経路情報を出力する出力部とを備えた経路探索装置における最適経路探索方法において，詳細道路データに基づいて該地点からその付近の主要道路に至る経路を探索する周辺探索部と，詳細道路データおよび主要道路データのうちの選択された道路データで経路探索をすることのできる全経路探索部とを備え，経路探索部は，該周辺探索部により目的地の周辺の主要道路上の道路点のうちから選択された道路点であるサテライトを求め，全経路探索部により出発地点からその周辺の主要道路に至る経路を詳細道路データにより探索し，そのようにして求められた主要道路上の道路点から該サテライトもしくは目的地点が主要道路上にある場合には目的地点に至る経路を主要道路データにより探索して最適経路を求める構成を持つ。
【０００８】
本発明に関連する技術の構成は，目的地点および出発地点となる地点を入力する入力部と，道路データを保持する道路データ保持部と，道路データをもとに出発地点から目的地点に至る経路を探索して最適経路を求める経路探索部と，道路の属性に応じて走行速度を定める速度テーブル保持部と，経路情報を出力する出力部とを備えた経路探索装置における最適経路探索方法において，経路について速度テーブルを参照して所要時間を求め，所要時間により求めた経路を評価し，出発地点から目的地点に至る最短所要時間の経路を最適経路としてその経路情報を出力する構成を持つ。
【０００９】
図１は本発明に関連する技術の構成を示す図である。
【００１０】
図１において，１は道路データ保持部であって，道路データを保持するものである。２は区間データであって，道路を区間に分割したデータであり，区間の距離，区間の属性（道路種別（国道，一般道路等），道路の幅員等），走行速度の調整係数を保持するものである。調整係数は通常は１であり，渋滞等の道路状況に応じてユーザが設定できるものである。３は属性，調整係数である。４は道路点データであって，道路上の点について接続区間を対応付けたデータである。１０は速度テーブル保持部であって，道路種別，幅員に対応した走行速度を保持するものである。１１は速度テーブルである。１５は経路探索部であって，出発地点から目的地点までの経路を探索し所要時間の短い経路を求めるものである。
【００１１】
２１は出発地点から目的地点までの経路を探索する処理を表す。２２は探索した経路について，所要時間を算出する処理を表す。２３は所要時間で経路を評価し，最短時間の経路を求める処理を表す。２４は求めた経路を最適経路として表示部に出力する処理を表す。２５は表示部である。２６は入力部である。
【００１２】
経路探索部１５は，入力された出発地点と目的地点を基に，道路データ保持部１から与えられる道路データを参照して，出発地点から目的地点までの経路と求めた経路の距離を求める。そして，速度テーブル保持部１０から与えられる区間データの属性に対応する走行速度および調整係数を基に求めた出発地点から目的地点までの所要時間を求め，所要時間の短い経路を表示部２５に出力する。例えば，ダイクストラ法により最適経路を求める場合，出発地点から始まって，出発地点に接続される区間の他方の道路点を求める。そして，出発地点に接続される各区間の属性により速度テーブルを参照して，実際に移動可能な走行速度を求める。また，そのようにして求めた走行速度に調整係数を掛けて実際に近い走行速度を求める。そして，その走行速度を基に区間を移動する所要時間で区間を求めて経路毎に評価し，最短所要時間の経路を最適区間として選択する。次に，このようにして求めた道路点について同様に区間と区間を移動する時間を求めて，各区間について評価し，最短時間で移動できる区間を求める。この処理を繰り返し目的地点に最短時間で至る経路を求める。
【００１３】
上記の速度テーブルは，例えば，道路の法定最高速度に道路の幅員を考慮して予めきめておくものであるが，速度テーブル変更手段を備えていて，ユーザが，道路の渋滞状況，経験等に基づいて変更できるものである。速度テーブルの変更は表示部２５に速度テーブルを表示し，その表示画面上でユーザが設定値を変更する。また，調整係数は，例えば，製品の出荷時点では全て１に設定されていて，道路の渋滞等の状況に応じてユーザが設定できるものである。あるいは，移動速度と移動地点についての履歴をとることができる場合には，その履歴情報を基に調整係数を変更するようにしても良い。
【００１４】
また，以上の構成によれば，出発地点から目的地点まで最短時間で移動できる経路を出力し，現実に最も有効な経路を出力することができる。また，調整係数によりきめ細かく所要時間を変更できるので，実際の移動時間に近い条件で経路探索行うことができる。また，速度テーブルもユーザが容易に変更できるので，実際の道路状況に柔軟に対応することができる。
【００１５】
図２は，本発明の基本構成を示す。
【００１６】
図２において，１は道路データ保持部であって，主要道路と主要道路から分かれる枝道等の全道路の詳細道路データ部と，主要道路だけの主要道路データ部を階層的に保持するものである。１５は経路探索部であって、目的地から目的地周辺の主要道路に至る経路を探索し，目的地周辺の主要道路上の地点（サテライト）および目的地とサテライトとの間の経路を求める周辺探索部および，出発地点からサテライトもしくは目的地（目的地が主要道路上にあった場合）までの経路を詳細道路データおよび主要道路データを基に経路を求めるものである。
１０は速度テーブル保持部である（探索した経路を所要時間で評価する場合に必要とし，距離で評価する場合には不要である）。２５は表示部である。２６は入力部である。
【００１７】
道路データ保持部１において，４２は主要道路データ部である。４３は詳細道路データ部である。経路探索部１５において，５１は周辺探索部であって，詳細道路データにより目的地周辺を探索し，目的地周辺の主要道路上の道路点（サテライト）および目的地とサテライト間の経路を求めるものである。５２は全経路探索部であって，出発地点から詳細道路データを基に出発地点近くの主要道路上の道路点まで探索し，その道路点からは主要道路データに従って，サテライトもしくは目的地（目的地が主要道路上にある場合）までの経路を探索するものである。
【００１８】
５３は詳細道路データに基づく経路探索の処理であって，出発地点からその周辺の主要道路上の道路点（Ｘ）までの経路を求める処理である。５４は主要道路データに基づく経路探索の処理であって，出発地点近くの主要道路上の道路点（Ｘ）からサテライト（Ｓ）もしくは目的地（目的地が主要道路上にある場合）までの経路を主要道路データに従って探索する処理である。５５は探索経路を最短経路もしくは最短時間で評価し最適経路を求める処理である。５６は求めた最適経路を表示部に出力する処理である。
【００１９】
図２の構成の動作を説明する。経路探索部１５は，入力された出発地点および目的地点をもとに，周辺探索部５１により，目的地点からその周辺の主要道路上の道路点に至る経路を探索する。そして，例えば，一定距離以内にあるその主要道路上の道路点のうちから選択された道路点，例えば早く見つかった順で全個数の３０％以内等をサテライトとして保持する。さらに，全経路探索部により出発地点から目的地点までの経路を詳細道路データもしくは主要道路データに基づいて経路探索をする。その際，出発地点から探索を始めて，主要道路の道路点（Ｘ）に到達するまでは詳細道路データをもとに経路探索をする。次にその道路点（Ｘ）から目的地までは主要道路地図を基に探索経路を評価しながら最短距離もしくは最短所要時間の経路探索をする。そして，サテライトもしくは目的地点（目的地点が主要道路上にある場合）に到達したら，その経路を求める経路とする。さらに，サテライトから目的地までは予め周辺探索で求めておいた経路を採用する。最適経路は探索した経路について最短距離もしくは最短所要時間の経路とする。なお，この周辺探索および全経路探索は，例えば，前述のダイクストラ法等により行うものであり，前述したと同様に道路点に接続する区間を一つずつ延ばしながら延ばした区間のうちの最短距離の区間もしくは区間を通過するのに要する時間が最短の区間を求めながら経路を探索する方法により行うものである。
【発明の効果】
【００２０】
本発明の基本構成によれば，出発地点から目的地点までの最短経路もしくは最小所要時間の経路に近い経路を高速に求めることができる。特に，出発地点および目的地点となる地点が複数あり，それぞれの地点を出発地点および目的地点としてそれぞれの地点間の最適経路を求める場合には，それぞれの目的地周辺のサテライトおよびその経路を求めてあるので，目的地周辺の詳細道路データによる探索時間を大幅に減らすことができ，目的地点までの経路探索を高速に行うことができる。
【発明を実施するための最良の形態】
【００２１】
図３は本発明に関連する技術の構成のシステム構成の実施例を示す。図３において，６１は速度テーブル保持部であって，速度テーブルを保持する磁気ディスク装置等である。６２は速度テーブルのデータを表す。６３は道路データ保持部であって，道路データを保持するＣＤＲＯＭ等である。６４は道路点データである。６５は区間データである。６６は地点データ保持部であって，目的地点，出発地点となる地点の道路点およびその名称（商店名等）等をデータとしてもつものであり，磁気ディスク装置等である（地点データはユーザが指定するものである）。６７は地点データを表す。
【００２２】
また，７１は評価テーブル保持部であって，求めた経路の評価値（最短所要時間）を保持するものである。７２は経路探索プログラムであって，出発地点から道路点データと区間データに従って経路を求め，区間毎に距離およびその区間を通過する所要時間（出発地点からの区間毎の累積時間）を求め，所要時間で経路を評価しながら最短時間で通過できる区間を選択して目的地に至るまでの経路を求めるものである。７３は経路探索部であって，出発地点から目的地点までの経路を探索するものである。７４は所要時間算出部であって，求めた区間の距離と速度テーブルを参照して求めた区間を通過する所要時間を算出するものである。７５は所要時間評価部であって，求めた区間の所要時間を評価し，最短時間で通過できる区間を求めるものである。７７は経路情報保持部であって，最適経路として選択された区間データを保持するものである。
【００２３】
また，８１はＣＰＵである。８２はメモリである。８３はディスプレイである。８４はキーボードである。８５はマウスである。また，９１は走行履歴情報であって，自動車の車載装置で獲得された自動車の走行記録を保持する磁気ディクス装置，メモリカード等であり，自動車の走行日時，走行した位置（緯度，経度），走行速度等のデータを保持するものである。自動車の走行記録から速度テーブルの調整係数を変更する場合に使用するものである。９２は調整係数変更手段であって，自動車の走行履歴から速度テーブルの調整係数を変更する手段である。９３は速度テーブル変更手段であって，ユーザが速度テーブルを変更する時に使用するものである。以上の図３のシステム構成の動作は後述する。
【００２４】
図４は，道路の区間データ，道路点データ，地点データの実施例であり，区間データ，道路点データはＣＤＲＯＭ等に保持されているものである。但し，道路区間データの内，調整係数については変更することもあるため，道路区間データ全体または調整係数のみは更新可能な媒体に保持する必要がある。また，地点データはユーザが設定するものである。
【００２５】
図４ (a)は，道路区間データの例である。区間データは，道路を区間に分割したデータであり，区間番号をもち，区間の両端の接続道路点番号１，接続道路点番号２，区間長，属性（高速道路，国道等の道路種別，道路の幅員等），道路の走行速度の調整係数を保持するものである。調整係数は，デフォルト値として１をもつが，渋滞情報，工事情報もしくは経験等によりユーザが自由に変更できるものである（例えば，道路状況に応じて０．９，０．６５等の値を設定する）。あるいは自動車の走行履歴を基に，区間の過去の走行履歴を基に調整係数を変更することもできる。
【００２６】
図４ (b)は，道路点データの例である。道路点データは，道路点番号を持ち，道路点に接続する区間データ（接続区間番号）を持つものである。
図４ (c)は，地点データの例である。地点データは，出発地点，目的地点の道路点番号，名称（商店名等）等により構成されるものであり，ユーザが設定するものである。
図５は，速度テーブルの例である。道路種別毎に道路の幅員等を考慮して走行速度を定めたものである。
【００２７】
例えば，道路が一般国道で法定最高速度が時速６０ｋｍの道路の場合，道路の幅員が１３．０ｍ以上あれば，走行速度は時速６０ｋｍとする。幅員が１３．０ｍ未満〜５．５ｍ以上では時速５５ｋｍ，幅員が５．５ｍ未満〜３．０ｍ以上では時速５０ｋｍ，３．０ｍ未満では４０ｋｍ，未調査の道路では３０ｋｍとする。また，このテーブルは画面に表示でき，ユーザにより変更可能なものである。この速度テーブルを基に，ある道路区間の「平均速度＝区間の走行速度×調整係数」により区間の平均速度を算出する。前述したように，調整係数は区間データの属性として持つものであり，デフォルト値が１であって，道路の渋滞，あるいは走行履歴等により変更可能なものである。
【００２８】
図６は，評価テーブルと経路情報の例を示す図である。図６ (a)は，評価テーブルの例であって，道路点毎の評価値と直前の道路点番号をもつものである。評価値は，区間の平均速度を基に算出した平均速度を基に区間を通過するのに要する時間の最小値であり，評価値は出発地点から各道路点を通過することにより得られる累積値である。
【００２９】
図６ (b)は，経路情報の例であって，出発地点と到達地点毎にその経路情報のあるポインタとポインタで指定された位置に通過道路点数，通過道路点番号をもつものである。最初に全ての道路点の評価値に最大値（例えば，９９９９９９）を設定し，出発地点に対応する道路点の評価値には０を設定する。全道路点の中で評価値の最小の道路点（仮にＡとする）を求めて，その道路点に接続される区間データを基に，その距離，属性によりその区間を通過する所要時間を求め，その道路点の評価値との合計（累積所要時間）を得る。求めた累積所要時間が，その区間によって接続される他方の道路点（仮にＢとする）の評価値がより小さければ，Ｂの評価値を累積所要時間とし，直前の道路点番号はＡとなる。これをＡから接続される全道路区間について行った後に，同様に全道路点の中で評価値の最小の道路点を求めて，探索作業を繰り返す。評価テーブルはその時点での各道路点までの最小累積所要時間であり，直前の道路点番号をトレースしていくと，出発地点までの経路が分かる。このようにして，目的地点に至るまで評価テーブルを作成するとともに，図６ (b)に示すように経路情報を作成する。出発地点から目的地点に至るまでに選択した道路点番号（通過道路点番号０，通過道路点番号１等）を経路情報に記録する。
【００３０】
図７は，本発明に関連する技術の構成をダイクストラ法に適用する場合の実施例である。
・Ｓ１： 評価テーブルの全ての道路点の評価値に最大値を設定する（初期値）。
・Ｓ２： 出発地点となる道路点の評価値を０とする（初期値）。
・Ｓ３： 価値の最小の道路点を調べる（これをカレント道路点と呼ぶ）。
・Ｓ４： カレント道路点は目的地点か判定する（目的地点であるかないかは地点データを参照する）。目的地点でなければＳ５以後の処理を行い，目的地点であればＳ１１の処理をする。
・Ｓ５： 評価対象を接続区間番号１とする。
・Ｓ６： 接続区間を通ってカレント道路点でない方の接続道路点の評価値を求める。評価値は，「評価値＝カレント道路点の評価値＋（接続区間の区間長／走行速度×接続区間の調整係数）」で算出する。走行速度は接続区間の道路種別，幅員に応じて速度テーブルから求める。
・Ｓ７： 評価値は既に設定されている値より小さいか判定する。小さければＳ８の処理を行い，小さくなければＳ９の処理をする。
・Ｓ８： 評価テーブルの接続道路点の評価値と直前の道路点番号を設定する。直前の道路点＝カレント道路点である。
・Ｓ９： カレント道路点の接続道路はまだあるか判定する。あればＳ１０以後の処理を行い，なければＳ３以後の処理を繰り返す。
・Ｓ１０： 評価対象を次の接続区間として，Ｓ６以後の処理を繰り返す。
・Ｓ１１： カレント道路点の評価値を所要時間とする。カレント道路点から直前の道路点を順にトレースして経路情報を求め，出力する。
【００３１】
図８は，実施例２の説明図であって，本発明の基本構成の実施例の説明図である。
【００３２】
商品の配達先が多数あって最適な配達経路を求めるような時，目的地点が複数地点あり，最短経路もしくは最短時間で各地点を通過して出発地点に戻る経路を求める必要がある。このような場合に，各地点間（地点がＡ，Ｂ，Ｃの３箇所あるとすると，Ａを出発地点としてＢ，Ｃを目的地点とし，地点Ｂを出発地点としてＣを目的地点とする）を最短距離もしくは最短時間で移動することのできる経路を求めておくと，目的地点を経由する順番，経路を求めるのに都合が良い。本実施例２はそのような場合に，各地点間の最短経路に近い経路を高速に求めることができるようにしたものである。
【００３３】
図８ (a)は，主要道路の道路データと詳細道路データの道路データを重ねたイメージである。太線は主要道路であり，細線は主要道路から分かれた枝道を表す。地点ｉは出発地点もしくは目的地点を表す。
図８ (b)は，主要道路の道路データを表す。図８ (c)は，全道路の詳細道路データであって，主要道路と主要道路から分かれた枝道を含む全道路データである。
図８ (c)において，Ａ，Ｂ，Ｃは地点であって，ＡＢ間の最短経路，ＡＣ間の最短経路を求める場合には，Ａを出発地点，Ｂ，Ｃは目的地点とする。またＢＣ間の最短経路を求める場合にはＢを出発地点，Ｃを目的地点とする。Ｂを出発地点としてＡを目的地点とする場合は，Ａを出発地点としてＢを目的地点とする場合に同じ経路とする。同様にＣを出発地点としてＡ，Ｂを目的地点とする場合も同様にＡもくしはＢを出発地点としてＣを目的地点とした場合と同じ経路を最短経路とする。
【００３４】
図９は，実施例２の目的地点周辺の探索と出発地点周辺の探索の説明図である。図９ (a)は，目的地点周辺の探索の説明図である。地点Ａを目的地点とする（図８ (c)とは地図が異なる）。詳細道路データにより地点Ａから始めて，主要道路に至る経路を求める。そして，一定の距離以内の主要道路上の道路点（Ａ1 ，Ａ2 ，Ａ3 ）をサテライトとしてその道路点および地点Ａからサテライトに至る経路を保持する。
【００３５】
図９ (b)は，出発地点の周辺の経路探索の説明図である。Ｂは出発地点である（図８の地点Ｂに対応していない）。地点Ｂから開始して，詳細道路データにより経路探索を開始し，一定の距離以内の主要道路上の道路点（Ｘ（複数点あっても良い），Ｂ自身のサテライト）を通過後は，主要道路データにより目的地点（目的地点が主要道路上にある場合）もしくはサテライトまでの最短経路を求める。
【００３６】
図９ (c)は，そのようにして求めた，図８のＡ，Ｂ，Ｃの各地点間の最短経路情報（この実施例２では最短距離）の表示の例である。表示する情報は経路情報であって，出発地点から目的地点までの道路点の通過情報等も出力することができる。
【００３７】
図１０は，実施例２のシステム構成である。図１０において，６３は道路データ保持部であって，道路データを保持するＣＤＲＯＭ等であり，詳細道路データ部１１０と主要道路データ部１１１を階層構造に構成したものである。６６は地点データ保持部であって，地点データ（目的地点，出発地点となる地点の道路点，その名称，および自身が目的地となった場合のサテライト数等）を保持するものである。６７は地点データを表す。
【００３８】
また，７１は評価テーブル保持部であって，求めた経路の評価値（この実施例２では最短経路）を保持するものである。７２は経路探索プログラムであって，出発地点から目的地点に至る最短経路を求めるものである。７７は経路情報保持部であって，選択した最適経路（区間データ）を保持するものである。
【００３９】
また，８１はＣＰＵである。８２はメモリである。８３はディスプレイである。８４はキーボードである。８５はマウスである。道路データ保持部６３において，１１０は詳細道路データ部である。１１１は主要道路データ部である。
【００４０】
経路探索プログラム７２において，１２１は周辺探索部であって，目的地周辺のサテライトを求めるものである。１２２は全経路探索部であって，出発地点から目的地点もしくはサテライトに至る最短経路を求めるものである。１２３は経路評価部であって，最短経路を求めるものである。１３１は道路点付随データ保持部であって，道路地点毎のサテライト元の地点番号等の情報を保持するものである。
【００４１】
道路データ保持部の詳細道路データ部，主要道路データ部は道路点データ，区間データにより構成されるがその構成は，図４と同様であるので説明は省略する。また，評価テーブル，経路情報保持部の構成も，図６と同様であるので説明は省略する（但し，実施例２では評価値は最短距離である）。
【００４２】
図１１は，道路点付随データ，地点データの例を示す。図１１ (a)は，道路点付随データの例であって，周辺探索を行って得られたサテライトおよびその時に生成された目的地点からサテライトまでの経路を保持するものである。道路点付随データは，道路点番号毎に地点番号，サテライト個数，各サテライト元地点番号，その経路情報を持つ位置を指定する経路情報へのポインタをもつものである（例えば，図９ (a)でサテライトＡ2 に対応する道路点番号に対しては地点そのものはここにはないため，地点番号には無を意味する−１を持ち，地点ＡとサテライトＡ3 の間の経路情報をもつ。また，目的地点Ａに対応する道路点番号に対しては地点番号に地点Ａを持ち，サテライトはないため，サテライト個数は０となる）。経路情報ポインタ指定された場所に経路の通過点の個数，通過道路点の番号が記録される。また，求めたサテライトは，次回に同じ目的地点を探索する場合に再使用することができる。
【００４３】
図１１ (b)は，地点データの例であって，地点番号毎に対応する道路点番号，自身のもつサテライト数，名称（商店名等）を保持するものである。自サテライト数は，周辺探索により求められたサテライトに基づいて記録されるものである（図９ (a)の地点Ａの場合，自サテライト数は３である）。また，地点の名称（商店名等）はユーザが書き込むものである。
【００４４】
本実施例において，探索は，出発地点から始めるが，あらかじめ求めてある出発地点のサテライトから出発しないのは，目的地点が出発地点のサテライトより出発地点に近い半径内にある場合，最適経路が求められなくなるのを防ぐためである。
【００４５】
図１２は，実施例２の経路探索プログラムの全体的処理のフローチャートである。
【００４６】
経路探索の対象となる地点（図８のＡ，Ｂ，Ｃ等）は地点０〜地点（ｎ−１）のｎ個あり，ｎ個の地点間の経路探索を行うとする。Ｓ１〜Ｓ４は目的地点周辺のサテライトを求める処理であり，Ｓ５〜Ｓ８は出発地点からサテライトもしくは目的地点までの全経路探索の処理である。
・Ｓ１： ｉを０とする（初期値）。
・Ｓ２： ｎ個の地点について周辺探索を行ったか判定する。全て行っていれば（ｉ≧ｎであれば）Ｓ５の処理を行う。全て行っていなければ（ｉ≧ｎでなければ）Ｓ３の処理を行う。
・Ｓ３： 周辺探索プログラムにより地点ｉの周辺の探索をする（この処理を（１）とする）。
・Ｓ４： ｉをｉ＋１としてＳ２以後の処理を繰り返す。
・Ｓ５： ｉを０にクリアして，Ｓ６以後の処理をする。
・Ｓ６： ｎ個の地点について全て全経路探索を行ったか判定する（（ｉ≧ｎか判定する）。ｉ≧ｎでなければ全ての地点について行っていないのでＳ７の処理を行う。ｉ≧ｎであれば全ての地点について行ったので処理を終了する。
・Ｓ７： 地点ｉを出発地点として経路探索を行い，他の全地点（目的地点）との経路を求める。
・Ｓ８： ｉをｉ＋１としてＳ６以後の処理を繰り返す。
【００４７】
図１３は，周辺道路探索のフローチャートであって，図１２の（１）の処理の詳細である。本処理は詳細道路データに対して行う。
・Ｓ１： 地点ｉの対応する道路点の道路点付随データに地点番号を設定する。
・Ｓ２： 全道路点の評価値を最大にする。
・Ｓ３： 地点ｉに対応する道路点の評価値を最小にする。
・Ｓ４： 評価値の最小の道路点を調べ，これをカレント道路点とする。
・Ｓ５： 周辺探索は終了したか判定する。終了していなければＳ６の処理をする。終了していれば，処理を終了する。終了の判断条件は，例えば，サテライトが６箇所見つかった場合等による。
・Ｓ６： カレント道路点に対応する主要道路があるか判定し，あればＳ７の処理を行い，なければＳ８の処理を行う。
・Ｓ７： カレント道路点の道路点付随データにサテライト情報を設定する。即ち，サテライト元地点番号に地点番号を設定する。地点ｉの対応する道路点からカレント道路点までの通過道路点番号を設定する。
・Ｓ８： カレント道路点から接続されている道路区間を評価し，評価テーブルに評価値を設定し，Ｓ４以後の処理を繰り返す。
【００４８】
図１４および図１５は，実施例２の全経路探索のフローチャートであって，図１２の（２）の処理の詳細である。
・Ｓ１： 詳細道路および主要道路（全道路）の評価値を最大にする。
・Ｓ２： 地点ｉに対応する評価値を最小にする。
・Ｓ３： 評価値の最小の道路点を調べ，これをカレント道路点とする。
・Ｓ４： カレント道路点に地点ｉはあるか判定し，あればＳ５の処理を行い，なければＳ７の処理をする。
・Ｓ５： 地点ｉからカレント道路点までの通過道路の情報を経路として出力する。
・Ｓ６： 地点ｉからの経路が求まっていない地点（目的地点）はあるか判定し，あればＳ７の処理を行い，なければ処理を終了する。
・Ｓ７： カレント道路点にサテライト（目的地点のサテライト）はあるか判定し，あればＳ８の処理を行い，なければＳ１１の処理を行う。
・Ｓ８： サテライト元の地点が求まっているか判定し，求まっていればＳ１０’の処理を行い，求まっていなければＳ９の処理を行う。
・Ｓ９： 地点ｉからのカレント道路点までの通過道路点の情報とサテライトの通過道路点の情報を連結してサテライト元地点までの経路とする。
・Ｓ１０： 地点ｉからの経路が求まっていない地点があるか判定し，なければ処理を終了し，あればＳ１０’の処理を行う。
・Ｓ１０’： カレント道路点にはまだサテライトはあるか判定し，あればＳ８以降の処理を繰り返し，なければＳ１１以後の処理をする。
・Ｓ１１： カレント道路点から接続されている道路区間を評価し，評価テーブルに評価値を設定する。
・Ｓ１２： 主要道路の探索に切り換えるか判定し，主要道路に切り換えるならば，Ｓ１３の処理をし，切り換えない場合にはＳ３以後の処理を繰り返す。主要道路に切り換えるか切り換えないかの条件は，例えば，地点ｉ（出発地点）のサテライト（（１）の処理で求めたサテライト）を全て通過したか等の条件で判定する。
・Ｓ１３： 詳細道路の道路点で対応主要道路があるものは評価値を主要道路にコピーする。これ以降の探索対象は主要道路とし，Ｓ３以降の処理を繰り返す。
【００４９】
図１６は，実施例３のシステム構成であって，本発明の基本構成の評価を最短時間で行う場合のシステム構成である。
【００５０】
図１６において，図１０と共通部分は共通番号である。６１は速度テーブル保持部であって，図３の実施例１の速度テーブル保持部と同じものである。７１は評価テーブル保持部であって，評価値が最短時間である点で図１０の場合と異なるのみである。７２は経路探索プログラムであって，経路評価部が経路を最短時間で評価する点でのみ図１０と異なる。９１’は走行履歴情報保持部であって，図３の走行履歴と同様である。９２は調整係数変更手段であって，図３の調整係数変更手段と同様である。９３は速度テーブル変更手段であって，図３の速度テーブル変更手段と同様である。
【００５１】
図１６のシステム構成の動作のフローチャートは，経路の評価を最短時間で行う点を除いて，図１２，図１３，図１４，図１５のフローチャートと同様である。
【００５２】
図１７は，速度テーブルの変更方法と調整係数の変更方法の実施例である。図１７ (a)は，速度テーブルの変更方法である。速度テーブルを速度テーブル表示手段９３’によりディスプレイ８３に表示する。ディスプレイ８３の画面上で走行速度を変更する欄を入力手段８４’（マウス，キーボード等）によりカーソルで指定し，変更する走行速度を入力する。速度テーブル変更手段９３は，速度テーブルのカーソルで指定された欄の走行速度を指定された速度に変更する。
【００５３】
図１７ (b)は，調整係数の変更方法(1) である。道路データ保持部６３に保持されている区間データを道路データ表示手段９３”によりディスプレイ８３に表示する。ディスプレイ８３の画面上で変更する調整係数を入力手段８４’によりカーソルで指定し，変更する調整係数を入力する。調整係数変更手段９２は，道路データ保持部６３の指定された区間データの調整係数を指定された値に変更する。
【００５４】
図１８は，調整係数の変更方法の実施例である。調整係数の変更方法(2) であって，走行履歴情報保持部９１’に記録されている走行履歴情報を基に調整係数を変更する方法を示す。
【００５５】
調整係数変更手段９２は速度テーブルから調整係数を変更する区間の走行速度を求める（Ｓ１）。走行履歴情報保持部９１’から走行履歴情報を入力する（Ｓ２）。走行履歴情報の走行した位置の緯度，経度と道路データの区間の緯度，経度データを比較し，調整係数を変更する区間を実際に走行した速度を求め，その平均速度を求める（走行履歴情報が道路データの区間ＩＤと共通のＩＤをもっていれば区間ＩＤにより実際の走行速度を求める）（Ｓ３）。そして速度テーブルから求めた走行速度と走行履歴情報から求めた走行速度を比較し調整係数を求める（例えば比をとる）（Ｓ４）。そして，調整係数変更手段９２は道路データ保持部６３のその区間の調整係数を求めた調整係数で変更する（Ｓ５）。
【図面の簡単な説明】
【００５６】
【図１】本発明に関連する技術の構成を示す図である。
【図２】本発明の基本構成を示す図である。
【図３】本発明に関連する技術の構成のシステム構成の実施例を示す図である。
【図４】道路区間のデータ，道路点データ，地点データの実施例を示す図である。
【図５】速度テーブルの例を示す図である。
【図６】評価テーブルと経路情報の例を示す図である。
【図７】実施例１のフローチャート（ダイクストラ法）を示す図である。
【図８】実施例２の説明図である。
【図９】実施例２の説明図である。
【図１０】実施例２のシステム構成を示す図である。
【図１１】道路点付随データと地点データの例を示す図である。
【図１２】実施例２の全体的フローチャートを示す図である。
【図１３】目的地点周辺の経路探索のフローチャートを示す図である。
【図１４】実施例２の全経路探索のフローチャート（その１）を示す図である。
【図１５】実施例２の全経路探索のフローチャート（その２）を示す図である。
【図１６】システム構成の実施例３を示す図である。
【図１７】速度テーブルの変更方法と調整係数の変更方法の実施例を示す図である。
【図１８】調整係数の変更方法の実施例を示す図である。
【符号の説明】
【００５７】
１：道路データ保持部
２：区間データ
３：属性，調整係数
４：道路点データ
１０：速度テーブル保持部
１１：速度テーブル
１５：経路探索部
２５：表示部
２６：入力部
４２：主要道路データ部
４３：詳細道路データ部
【技術分野】
【０００１】
本発明は，道路データに基づいて出発地点から目的地点に至る経路を探索し，経路を求める経路探索装置における最適経路探索方法に関する。
【背景技術】
【０００２】
経路探索装置は，複数地点を経由して商品の配達経路を求めるような場合に，道路データを基にその最適経路を求めるものである。
【０００３】
従来の経路探索装置は，ダイクストラ法等により出発地点から開始して接続される道路区間を求め，区間の距離を評価して最小距離の区間を最適道路区間として選択し，順次目的地点まで最短距離の区間を求め，そのようにして求めた出発地点から目的地点までの経路を最適経路として出力していた。そして，従来は主要道路のみの主要道路地図もしくは主要道路から分かれる枝道等の幅の狭い道まで含めた全道路の詳細道路地図に基づいて最適経路を求めていた。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来の経路探索装置で，処理を高速化するために主要道路地図に基づいて経路探索した場合には，目的地が主要道路上にない条件では，目的地まで到達する経路を求めることができなかった。そのため，目的地付近は詳細道路地図で補完する必要があるが，目的地，出発地を地点とし多数の地点間最短経路を求めるような場合には，それぞれの出発地点，目的地点毎に詳細道路データにより補完する必要があり，長時間を必要とした。
【０００５】
また，実際の道路では道路の幅員，交通渋滞等で法定の最高速度で移動することができない場合があり，最短距離の経路であっても，実際には最短時間で目的地点に到達することができるとは限らず，距離は長くても高速に移動できて所要時間の短い経路も実際には存在する。そのため，出発地点から目的地点までの最短距離の経路を最適経路とする従来の経路探索装置で求められた経路が実際の運用での最適経路であるとは限らなかった。また，道路の幅員等を考慮して目的地までの所要時間を推定し，求めた最短経路に補足的情報として表示するものもあるが，その所要時間はあくまでも補足的な情報であり，所要最短時間の経路を最適経路として出力するものではない。
【０００６】
本発明は，出発地点から目的地点に至るまでの経路を高速に求めることができる最適経路探索方法を提供することを目的とする。また，本発明は，出発地点，目的地点となる地点が多数あり，各地点間の最適経路を全て求めるような場合に高速に処理することができるようにすることを目的とする。
【課題を解決するための手段】
【０００７】
本発明の基本構成は，目的地点および出発地点となる地点を入力する入力部と，道路データを保持する道路データ保持部と，道路データをもとに出発地点から目的地点に至る経路を探索して最適経路を求める経路探索部と，最適経路の経路情報を出力する出力部とを備えた経路探索装置における最適経路探索方法において，詳細道路データに基づいて該地点からその付近の主要道路に至る経路を探索する周辺探索部と，詳細道路データおよび主要道路データのうちの選択された道路データで経路探索をすることのできる全経路探索部とを備え，経路探索部は，該周辺探索部により目的地の周辺の主要道路上の道路点のうちから選択された道路点であるサテライトを求め，全経路探索部により出発地点からその周辺の主要道路に至る経路を詳細道路データにより探索し，そのようにして求められた主要道路上の道路点から該サテライトもしくは目的地点が主要道路上にある場合には目的地点に至る経路を主要道路データにより探索して最適経路を求める構成を持つ。
【０００８】
本発明に関連する技術の構成は，目的地点および出発地点となる地点を入力する入力部と，道路データを保持する道路データ保持部と，道路データをもとに出発地点から目的地点に至る経路を探索して最適経路を求める経路探索部と，道路の属性に応じて走行速度を定める速度テーブル保持部と，経路情報を出力する出力部とを備えた経路探索装置における最適経路探索方法において，経路について速度テーブルを参照して所要時間を求め，所要時間により求めた経路を評価し，出発地点から目的地点に至る最短所要時間の経路を最適経路としてその経路情報を出力する構成を持つ。
【０００９】
図１は本発明に関連する技術の構成を示す図である。
【００１０】
図１において，１は道路データ保持部であって，道路データを保持するものである。２は区間データであって，道路を区間に分割したデータであり，区間の距離，区間の属性（道路種別（国道，一般道路等），道路の幅員等），走行速度の調整係数を保持するものである。調整係数は通常は１であり，渋滞等の道路状況に応じてユーザが設定できるものである。３は属性，調整係数である。４は道路点データであって，道路上の点について接続区間を対応付けたデータである。１０は速度テーブル保持部であって，道路種別，幅員に対応した走行速度を保持するものである。１１は速度テーブルである。１５は経路探索部であって，出発地点から目的地点までの経路を探索し所要時間の短い経路を求めるものである。
【００１１】
２１は出発地点から目的地点までの経路を探索する処理を表す。２２は探索した経路について，所要時間を算出する処理を表す。２３は所要時間で経路を評価し，最短時間の経路を求める処理を表す。２４は求めた経路を最適経路として表示部に出力する処理を表す。２５は表示部である。２６は入力部である。
【００１２】
経路探索部１５は，入力された出発地点と目的地点を基に，道路データ保持部１から与えられる道路データを参照して，出発地点から目的地点までの経路と求めた経路の距離を求める。そして，速度テーブル保持部１０から与えられる区間データの属性に対応する走行速度および調整係数を基に求めた出発地点から目的地点までの所要時間を求め，所要時間の短い経路を表示部２５に出力する。例えば，ダイクストラ法により最適経路を求める場合，出発地点から始まって，出発地点に接続される区間の他方の道路点を求める。そして，出発地点に接続される各区間の属性により速度テーブルを参照して，実際に移動可能な走行速度を求める。また，そのようにして求めた走行速度に調整係数を掛けて実際に近い走行速度を求める。そして，その走行速度を基に区間を移動する所要時間で区間を求めて経路毎に評価し，最短所要時間の経路を最適区間として選択する。次に，このようにして求めた道路点について同様に区間と区間を移動する時間を求めて，各区間について評価し，最短時間で移動できる区間を求める。この処理を繰り返し目的地点に最短時間で至る経路を求める。
【００１３】
上記の速度テーブルは，例えば，道路の法定最高速度に道路の幅員を考慮して予めきめておくものであるが，速度テーブル変更手段を備えていて，ユーザが，道路の渋滞状況，経験等に基づいて変更できるものである。速度テーブルの変更は表示部２５に速度テーブルを表示し，その表示画面上でユーザが設定値を変更する。また，調整係数は，例えば，製品の出荷時点では全て１に設定されていて，道路の渋滞等の状況に応じてユーザが設定できるものである。あるいは，移動速度と移動地点についての履歴をとることができる場合には，その履歴情報を基に調整係数を変更するようにしても良い。
【００１４】
また，以上の構成によれば，出発地点から目的地点まで最短時間で移動できる経路を出力し，現実に最も有効な経路を出力することができる。また，調整係数によりきめ細かく所要時間を変更できるので，実際の移動時間に近い条件で経路探索行うことができる。また，速度テーブルもユーザが容易に変更できるので，実際の道路状況に柔軟に対応することができる。
【００１５】
図２は，本発明の基本構成を示す。
【００１６】
図２において，１は道路データ保持部であって，主要道路と主要道路から分かれる枝道等の全道路の詳細道路データ部と，主要道路だけの主要道路データ部を階層的に保持するものである。１５は経路探索部であって、目的地から目的地周辺の主要道路に至る経路を探索し，目的地周辺の主要道路上の地点（サテライト）および目的地とサテライトとの間の経路を求める周辺探索部および，出発地点からサテライトもしくは目的地（目的地が主要道路上にあった場合）までの経路を詳細道路データおよび主要道路データを基に経路を求めるものである。
１０は速度テーブル保持部である（探索した経路を所要時間で評価する場合に必要とし，距離で評価する場合には不要である）。２５は表示部である。２６は入力部である。
【００１７】
道路データ保持部１において，４２は主要道路データ部である。４３は詳細道路データ部である。経路探索部１５において，５１は周辺探索部であって，詳細道路データにより目的地周辺を探索し，目的地周辺の主要道路上の道路点（サテライト）および目的地とサテライト間の経路を求めるものである。５２は全経路探索部であって，出発地点から詳細道路データを基に出発地点近くの主要道路上の道路点まで探索し，その道路点からは主要道路データに従って，サテライトもしくは目的地（目的地が主要道路上にある場合）までの経路を探索するものである。
【００１８】
５３は詳細道路データに基づく経路探索の処理であって，出発地点からその周辺の主要道路上の道路点（Ｘ）までの経路を求める処理である。５４は主要道路データに基づく経路探索の処理であって，出発地点近くの主要道路上の道路点（Ｘ）からサテライト（Ｓ）もしくは目的地（目的地が主要道路上にある場合）までの経路を主要道路データに従って探索する処理である。５５は探索経路を最短経路もしくは最短時間で評価し最適経路を求める処理である。５６は求めた最適経路を表示部に出力する処理である。
【００１９】
図２の構成の動作を説明する。経路探索部１５は，入力された出発地点および目的地点をもとに，周辺探索部５１により，目的地点からその周辺の主要道路上の道路点に至る経路を探索する。そして，例えば，一定距離以内にあるその主要道路上の道路点のうちから選択された道路点，例えば早く見つかった順で全個数の３０％以内等をサテライトとして保持する。さらに，全経路探索部により出発地点から目的地点までの経路を詳細道路データもしくは主要道路データに基づいて経路探索をする。その際，出発地点から探索を始めて，主要道路の道路点（Ｘ）に到達するまでは詳細道路データをもとに経路探索をする。次にその道路点（Ｘ）から目的地までは主要道路地図を基に探索経路を評価しながら最短距離もしくは最短所要時間の経路探索をする。そして，サテライトもしくは目的地点（目的地点が主要道路上にある場合）に到達したら，その経路を求める経路とする。さらに，サテライトから目的地までは予め周辺探索で求めておいた経路を採用する。最適経路は探索した経路について最短距離もしくは最短所要時間の経路とする。なお，この周辺探索および全経路探索は，例えば，前述のダイクストラ法等により行うものであり，前述したと同様に道路点に接続する区間を一つずつ延ばしながら延ばした区間のうちの最短距離の区間もしくは区間を通過するのに要する時間が最短の区間を求めながら経路を探索する方法により行うものである。
【発明の効果】
【００２０】
本発明の基本構成によれば，出発地点から目的地点までの最短経路もしくは最小所要時間の経路に近い経路を高速に求めることができる。特に，出発地点および目的地点となる地点が複数あり，それぞれの地点を出発地点および目的地点としてそれぞれの地点間の最適経路を求める場合には，それぞれの目的地周辺のサテライトおよびその経路を求めてあるので，目的地周辺の詳細道路データによる探索時間を大幅に減らすことができ，目的地点までの経路探索を高速に行うことができる。
【発明を実施するための最良の形態】
【００２１】
図３は本発明に関連する技術の構成のシステム構成の実施例を示す。図３において，６１は速度テーブル保持部であって，速度テーブルを保持する磁気ディスク装置等である。６２は速度テーブルのデータを表す。６３は道路データ保持部であって，道路データを保持するＣＤＲＯＭ等である。６４は道路点データである。６５は区間データである。６６は地点データ保持部であって，目的地点，出発地点となる地点の道路点およびその名称（商店名等）等をデータとしてもつものであり，磁気ディスク装置等である（地点データはユーザが指定するものである）。６７は地点データを表す。
【００２２】
また，７１は評価テーブル保持部であって，求めた経路の評価値（最短所要時間）を保持するものである。７２は経路探索プログラムであって，出発地点から道路点データと区間データに従って経路を求め，区間毎に距離およびその区間を通過する所要時間（出発地点からの区間毎の累積時間）を求め，所要時間で経路を評価しながら最短時間で通過できる区間を選択して目的地に至るまでの経路を求めるものである。７３は経路探索部であって，出発地点から目的地点までの経路を探索するものである。７４は所要時間算出部であって，求めた区間の距離と速度テーブルを参照して求めた区間を通過する所要時間を算出するものである。７５は所要時間評価部であって，求めた区間の所要時間を評価し，最短時間で通過できる区間を求めるものである。７７は経路情報保持部であって，最適経路として選択された区間データを保持するものである。
【００２３】
また，８１はＣＰＵである。８２はメモリである。８３はディスプレイである。８４はキーボードである。８５はマウスである。また，９１は走行履歴情報であって，自動車の車載装置で獲得された自動車の走行記録を保持する磁気ディクス装置，メモリカード等であり，自動車の走行日時，走行した位置（緯度，経度），走行速度等のデータを保持するものである。自動車の走行記録から速度テーブルの調整係数を変更する場合に使用するものである。９２は調整係数変更手段であって，自動車の走行履歴から速度テーブルの調整係数を変更する手段である。９３は速度テーブル変更手段であって，ユーザが速度テーブルを変更する時に使用するものである。以上の図３のシステム構成の動作は後述する。
【００２４】
図４は，道路の区間データ，道路点データ，地点データの実施例であり，区間データ，道路点データはＣＤＲＯＭ等に保持されているものである。但し，道路区間データの内，調整係数については変更することもあるため，道路区間データ全体または調整係数のみは更新可能な媒体に保持する必要がある。また，地点データはユーザが設定するものである。
【００２５】
図４ (a)は，道路区間データの例である。区間データは，道路を区間に分割したデータであり，区間番号をもち，区間の両端の接続道路点番号１，接続道路点番号２，区間長，属性（高速道路，国道等の道路種別，道路の幅員等），道路の走行速度の調整係数を保持するものである。調整係数は，デフォルト値として１をもつが，渋滞情報，工事情報もしくは経験等によりユーザが自由に変更できるものである（例えば，道路状況に応じて０．９，０．６５等の値を設定する）。あるいは自動車の走行履歴を基に，区間の過去の走行履歴を基に調整係数を変更することもできる。
【００２６】
図４ (b)は，道路点データの例である。道路点データは，道路点番号を持ち，道路点に接続する区間データ（接続区間番号）を持つものである。
図４ (c)は，地点データの例である。地点データは，出発地点，目的地点の道路点番号，名称（商店名等）等により構成されるものであり，ユーザが設定するものである。
図５は，速度テーブルの例である。道路種別毎に道路の幅員等を考慮して走行速度を定めたものである。
【００２７】
例えば，道路が一般国道で法定最高速度が時速６０ｋｍの道路の場合，道路の幅員が１３．０ｍ以上あれば，走行速度は時速６０ｋｍとする。幅員が１３．０ｍ未満〜５．５ｍ以上では時速５５ｋｍ，幅員が５．５ｍ未満〜３．０ｍ以上では時速５０ｋｍ，３．０ｍ未満では４０ｋｍ，未調査の道路では３０ｋｍとする。また，このテーブルは画面に表示でき，ユーザにより変更可能なものである。この速度テーブルを基に，ある道路区間の「平均速度＝区間の走行速度×調整係数」により区間の平均速度を算出する。前述したように，調整係数は区間データの属性として持つものであり，デフォルト値が１であって，道路の渋滞，あるいは走行履歴等により変更可能なものである。
【００２８】
図６は，評価テーブルと経路情報の例を示す図である。図６ (a)は，評価テーブルの例であって，道路点毎の評価値と直前の道路点番号をもつものである。評価値は，区間の平均速度を基に算出した平均速度を基に区間を通過するのに要する時間の最小値であり，評価値は出発地点から各道路点を通過することにより得られる累積値である。
【００２９】
図６ (b)は，経路情報の例であって，出発地点と到達地点毎にその経路情報のあるポインタとポインタで指定された位置に通過道路点数，通過道路点番号をもつものである。最初に全ての道路点の評価値に最大値（例えば，９９９９９９）を設定し，出発地点に対応する道路点の評価値には０を設定する。全道路点の中で評価値の最小の道路点（仮にＡとする）を求めて，その道路点に接続される区間データを基に，その距離，属性によりその区間を通過する所要時間を求め，その道路点の評価値との合計（累積所要時間）を得る。求めた累積所要時間が，その区間によって接続される他方の道路点（仮にＢとする）の評価値がより小さければ，Ｂの評価値を累積所要時間とし，直前の道路点番号はＡとなる。これをＡから接続される全道路区間について行った後に，同様に全道路点の中で評価値の最小の道路点を求めて，探索作業を繰り返す。評価テーブルはその時点での各道路点までの最小累積所要時間であり，直前の道路点番号をトレースしていくと，出発地点までの経路が分かる。このようにして，目的地点に至るまで評価テーブルを作成するとともに，図６ (b)に示すように経路情報を作成する。出発地点から目的地点に至るまでに選択した道路点番号（通過道路点番号０，通過道路点番号１等）を経路情報に記録する。
【００３０】
図７は，本発明に関連する技術の構成をダイクストラ法に適用する場合の実施例である。
・Ｓ１： 評価テーブルの全ての道路点の評価値に最大値を設定する（初期値）。
・Ｓ２： 出発地点となる道路点の評価値を０とする（初期値）。
・Ｓ３： 価値の最小の道路点を調べる（これをカレント道路点と呼ぶ）。
・Ｓ４： カレント道路点は目的地点か判定する（目的地点であるかないかは地点データを参照する）。目的地点でなければＳ５以後の処理を行い，目的地点であればＳ１１の処理をする。
・Ｓ５： 評価対象を接続区間番号１とする。
・Ｓ６： 接続区間を通ってカレント道路点でない方の接続道路点の評価値を求める。評価値は，「評価値＝カレント道路点の評価値＋（接続区間の区間長／走行速度×接続区間の調整係数）」で算出する。走行速度は接続区間の道路種別，幅員に応じて速度テーブルから求める。
・Ｓ７： 評価値は既に設定されている値より小さいか判定する。小さければＳ８の処理を行い，小さくなければＳ９の処理をする。
・Ｓ８： 評価テーブルの接続道路点の評価値と直前の道路点番号を設定する。直前の道路点＝カレント道路点である。
・Ｓ９： カレント道路点の接続道路はまだあるか判定する。あればＳ１０以後の処理を行い，なければＳ３以後の処理を繰り返す。
・Ｓ１０： 評価対象を次の接続区間として，Ｓ６以後の処理を繰り返す。
・Ｓ１１： カレント道路点の評価値を所要時間とする。カレント道路点から直前の道路点を順にトレースして経路情報を求め，出力する。
【００３１】
図８は，実施例２の説明図であって，本発明の基本構成の実施例の説明図である。
【００３２】
商品の配達先が多数あって最適な配達経路を求めるような時，目的地点が複数地点あり，最短経路もしくは最短時間で各地点を通過して出発地点に戻る経路を求める必要がある。このような場合に，各地点間（地点がＡ，Ｂ，Ｃの３箇所あるとすると，Ａを出発地点としてＢ，Ｃを目的地点とし，地点Ｂを出発地点としてＣを目的地点とする）を最短距離もしくは最短時間で移動することのできる経路を求めておくと，目的地点を経由する順番，経路を求めるのに都合が良い。本実施例２はそのような場合に，各地点間の最短経路に近い経路を高速に求めることができるようにしたものである。
【００３３】
図８ (a)は，主要道路の道路データと詳細道路データの道路データを重ねたイメージである。太線は主要道路であり，細線は主要道路から分かれた枝道を表す。地点ｉは出発地点もしくは目的地点を表す。
図８ (b)は，主要道路の道路データを表す。図８ (c)は，全道路の詳細道路データであって，主要道路と主要道路から分かれた枝道を含む全道路データである。
図８ (c)において，Ａ，Ｂ，Ｃは地点であって，ＡＢ間の最短経路，ＡＣ間の最短経路を求める場合には，Ａを出発地点，Ｂ，Ｃは目的地点とする。またＢＣ間の最短経路を求める場合にはＢを出発地点，Ｃを目的地点とする。Ｂを出発地点としてＡを目的地点とする場合は，Ａを出発地点としてＢを目的地点とする場合に同じ経路とする。同様にＣを出発地点としてＡ，Ｂを目的地点とする場合も同様にＡもくしはＢを出発地点としてＣを目的地点とした場合と同じ経路を最短経路とする。
【００３４】
図９は，実施例２の目的地点周辺の探索と出発地点周辺の探索の説明図である。図９ (a)は，目的地点周辺の探索の説明図である。地点Ａを目的地点とする（図８ (c)とは地図が異なる）。詳細道路データにより地点Ａから始めて，主要道路に至る経路を求める。そして，一定の距離以内の主要道路上の道路点（Ａ1 ，Ａ2 ，Ａ3 ）をサテライトとしてその道路点および地点Ａからサテライトに至る経路を保持する。
【００３５】
図９ (b)は，出発地点の周辺の経路探索の説明図である。Ｂは出発地点である（図８の地点Ｂに対応していない）。地点Ｂから開始して，詳細道路データにより経路探索を開始し，一定の距離以内の主要道路上の道路点（Ｘ（複数点あっても良い），Ｂ自身のサテライト）を通過後は，主要道路データにより目的地点（目的地点が主要道路上にある場合）もしくはサテライトまでの最短経路を求める。
【００３６】
図９ (c)は，そのようにして求めた，図８のＡ，Ｂ，Ｃの各地点間の最短経路情報（この実施例２では最短距離）の表示の例である。表示する情報は経路情報であって，出発地点から目的地点までの道路点の通過情報等も出力することができる。
【００３７】
図１０は，実施例２のシステム構成である。図１０において，６３は道路データ保持部であって，道路データを保持するＣＤＲＯＭ等であり，詳細道路データ部１１０と主要道路データ部１１１を階層構造に構成したものである。６６は地点データ保持部であって，地点データ（目的地点，出発地点となる地点の道路点，その名称，および自身が目的地となった場合のサテライト数等）を保持するものである。６７は地点データを表す。
【００３８】
また，７１は評価テーブル保持部であって，求めた経路の評価値（この実施例２では最短経路）を保持するものである。７２は経路探索プログラムであって，出発地点から目的地点に至る最短経路を求めるものである。７７は経路情報保持部であって，選択した最適経路（区間データ）を保持するものである。
【００３９】
また，８１はＣＰＵである。８２はメモリである。８３はディスプレイである。８４はキーボードである。８５はマウスである。道路データ保持部６３において，１１０は詳細道路データ部である。１１１は主要道路データ部である。
【００４０】
経路探索プログラム７２において，１２１は周辺探索部であって，目的地周辺のサテライトを求めるものである。１２２は全経路探索部であって，出発地点から目的地点もしくはサテライトに至る最短経路を求めるものである。１２３は経路評価部であって，最短経路を求めるものである。１３１は道路点付随データ保持部であって，道路地点毎のサテライト元の地点番号等の情報を保持するものである。
【００４１】
道路データ保持部の詳細道路データ部，主要道路データ部は道路点データ，区間データにより構成されるがその構成は，図４と同様であるので説明は省略する。また，評価テーブル，経路情報保持部の構成も，図６と同様であるので説明は省略する（但し，実施例２では評価値は最短距離である）。
【００４２】
図１１は，道路点付随データ，地点データの例を示す。図１１ (a)は，道路点付随データの例であって，周辺探索を行って得られたサテライトおよびその時に生成された目的地点からサテライトまでの経路を保持するものである。道路点付随データは，道路点番号毎に地点番号，サテライト個数，各サテライト元地点番号，その経路情報を持つ位置を指定する経路情報へのポインタをもつものである（例えば，図９ (a)でサテライトＡ2 に対応する道路点番号に対しては地点そのものはここにはないため，地点番号には無を意味する−１を持ち，地点ＡとサテライトＡ3 の間の経路情報をもつ。また，目的地点Ａに対応する道路点番号に対しては地点番号に地点Ａを持ち，サテライトはないため，サテライト個数は０となる）。経路情報ポインタ指定された場所に経路の通過点の個数，通過道路点の番号が記録される。また，求めたサテライトは，次回に同じ目的地点を探索する場合に再使用することができる。
【００４３】
図１１ (b)は，地点データの例であって，地点番号毎に対応する道路点番号，自身のもつサテライト数，名称（商店名等）を保持するものである。自サテライト数は，周辺探索により求められたサテライトに基づいて記録されるものである（図９ (a)の地点Ａの場合，自サテライト数は３である）。また，地点の名称（商店名等）はユーザが書き込むものである。
【００４４】
本実施例において，探索は，出発地点から始めるが，あらかじめ求めてある出発地点のサテライトから出発しないのは，目的地点が出発地点のサテライトより出発地点に近い半径内にある場合，最適経路が求められなくなるのを防ぐためである。
【００４５】
図１２は，実施例２の経路探索プログラムの全体的処理のフローチャートである。
【００４６】
経路探索の対象となる地点（図８のＡ，Ｂ，Ｃ等）は地点０〜地点（ｎ−１）のｎ個あり，ｎ個の地点間の経路探索を行うとする。Ｓ１〜Ｓ４は目的地点周辺のサテライトを求める処理であり，Ｓ５〜Ｓ８は出発地点からサテライトもしくは目的地点までの全経路探索の処理である。
・Ｓ１： ｉを０とする（初期値）。
・Ｓ２： ｎ個の地点について周辺探索を行ったか判定する。全て行っていれば（ｉ≧ｎであれば）Ｓ５の処理を行う。全て行っていなければ（ｉ≧ｎでなければ）Ｓ３の処理を行う。
・Ｓ３： 周辺探索プログラムにより地点ｉの周辺の探索をする（この処理を（１）とする）。
・Ｓ４： ｉをｉ＋１としてＳ２以後の処理を繰り返す。
・Ｓ５： ｉを０にクリアして，Ｓ６以後の処理をする。
・Ｓ６： ｎ個の地点について全て全経路探索を行ったか判定する（（ｉ≧ｎか判定する）。ｉ≧ｎでなければ全ての地点について行っていないのでＳ７の処理を行う。ｉ≧ｎであれば全ての地点について行ったので処理を終了する。
・Ｓ７： 地点ｉを出発地点として経路探索を行い，他の全地点（目的地点）との経路を求める。
・Ｓ８： ｉをｉ＋１としてＳ６以後の処理を繰り返す。
【００４７】
図１３は，周辺道路探索のフローチャートであって，図１２の（１）の処理の詳細である。本処理は詳細道路データに対して行う。
・Ｓ１： 地点ｉの対応する道路点の道路点付随データに地点番号を設定する。
・Ｓ２： 全道路点の評価値を最大にする。
・Ｓ３： 地点ｉに対応する道路点の評価値を最小にする。
・Ｓ４： 評価値の最小の道路点を調べ，これをカレント道路点とする。
・Ｓ５： 周辺探索は終了したか判定する。終了していなければＳ６の処理をする。終了していれば，処理を終了する。終了の判断条件は，例えば，サテライトが６箇所見つかった場合等による。
・Ｓ６： カレント道路点に対応する主要道路があるか判定し，あればＳ７の処理を行い，なければＳ８の処理を行う。
・Ｓ７： カレント道路点の道路点付随データにサテライト情報を設定する。即ち，サテライト元地点番号に地点番号を設定する。地点ｉの対応する道路点からカレント道路点までの通過道路点番号を設定する。
・Ｓ８： カレント道路点から接続されている道路区間を評価し，評価テーブルに評価値を設定し，Ｓ４以後の処理を繰り返す。
【００４８】
図１４および図１５は，実施例２の全経路探索のフローチャートであって，図１２の（２）の処理の詳細である。
・Ｓ１： 詳細道路および主要道路（全道路）の評価値を最大にする。
・Ｓ２： 地点ｉに対応する評価値を最小にする。
・Ｓ３： 評価値の最小の道路点を調べ，これをカレント道路点とする。
・Ｓ４： カレント道路点に地点ｉはあるか判定し，あればＳ５の処理を行い，なければＳ７の処理をする。
・Ｓ５： 地点ｉからカレント道路点までの通過道路の情報を経路として出力する。
・Ｓ６： 地点ｉからの経路が求まっていない地点（目的地点）はあるか判定し，あればＳ７の処理を行い，なければ処理を終了する。
・Ｓ７： カレント道路点にサテライト（目的地点のサテライト）はあるか判定し，あればＳ８の処理を行い，なければＳ１１の処理を行う。
・Ｓ８： サテライト元の地点が求まっているか判定し，求まっていればＳ１０’の処理を行い，求まっていなければＳ９の処理を行う。
・Ｓ９： 地点ｉからのカレント道路点までの通過道路点の情報とサテライトの通過道路点の情報を連結してサテライト元地点までの経路とする。
・Ｓ１０： 地点ｉからの経路が求まっていない地点があるか判定し，なければ処理を終了し，あればＳ１０’の処理を行う。
・Ｓ１０’： カレント道路点にはまだサテライトはあるか判定し，あればＳ８以降の処理を繰り返し，なければＳ１１以後の処理をする。
・Ｓ１１： カレント道路点から接続されている道路区間を評価し，評価テーブルに評価値を設定する。
・Ｓ１２： 主要道路の探索に切り換えるか判定し，主要道路に切り換えるならば，Ｓ１３の処理をし，切り換えない場合にはＳ３以後の処理を繰り返す。主要道路に切り換えるか切り換えないかの条件は，例えば，地点ｉ（出発地点）のサテライト（（１）の処理で求めたサテライト）を全て通過したか等の条件で判定する。
・Ｓ１３： 詳細道路の道路点で対応主要道路があるものは評価値を主要道路にコピーする。これ以降の探索対象は主要道路とし，Ｓ３以降の処理を繰り返す。
【００４９】
図１６は，実施例３のシステム構成であって，本発明の基本構成の評価を最短時間で行う場合のシステム構成である。
【００５０】
図１６において，図１０と共通部分は共通番号である。６１は速度テーブル保持部であって，図３の実施例１の速度テーブル保持部と同じものである。７１は評価テーブル保持部であって，評価値が最短時間である点で図１０の場合と異なるのみである。７２は経路探索プログラムであって，経路評価部が経路を最短時間で評価する点でのみ図１０と異なる。９１’は走行履歴情報保持部であって，図３の走行履歴と同様である。９２は調整係数変更手段であって，図３の調整係数変更手段と同様である。９３は速度テーブル変更手段であって，図３の速度テーブル変更手段と同様である。
【００５１】
図１６のシステム構成の動作のフローチャートは，経路の評価を最短時間で行う点を除いて，図１２，図１３，図１４，図１５のフローチャートと同様である。
【００５２】
図１７は，速度テーブルの変更方法と調整係数の変更方法の実施例である。図１７ (a)は，速度テーブルの変更方法である。速度テーブルを速度テーブル表示手段９３’によりディスプレイ８３に表示する。ディスプレイ８３の画面上で走行速度を変更する欄を入力手段８４’（マウス，キーボード等）によりカーソルで指定し，変更する走行速度を入力する。速度テーブル変更手段９３は，速度テーブルのカーソルで指定された欄の走行速度を指定された速度に変更する。
【００５３】
図１７ (b)は，調整係数の変更方法(1) である。道路データ保持部６３に保持されている区間データを道路データ表示手段９３”によりディスプレイ８３に表示する。ディスプレイ８３の画面上で変更する調整係数を入力手段８４’によりカーソルで指定し，変更する調整係数を入力する。調整係数変更手段９２は，道路データ保持部６３の指定された区間データの調整係数を指定された値に変更する。
【００５４】
図１８は，調整係数の変更方法の実施例である。調整係数の変更方法(2) であって，走行履歴情報保持部９１’に記録されている走行履歴情報を基に調整係数を変更する方法を示す。
【００５５】
調整係数変更手段９２は速度テーブルから調整係数を変更する区間の走行速度を求める（Ｓ１）。走行履歴情報保持部９１’から走行履歴情報を入力する（Ｓ２）。走行履歴情報の走行した位置の緯度，経度と道路データの区間の緯度，経度データを比較し，調整係数を変更する区間を実際に走行した速度を求め，その平均速度を求める（走行履歴情報が道路データの区間ＩＤと共通のＩＤをもっていれば区間ＩＤにより実際の走行速度を求める）（Ｓ３）。そして速度テーブルから求めた走行速度と走行履歴情報から求めた走行速度を比較し調整係数を求める（例えば比をとる）（Ｓ４）。そして，調整係数変更手段９２は道路データ保持部６３のその区間の調整係数を求めた調整係数で変更する（Ｓ５）。
【図面の簡単な説明】
【００５６】
【図１】本発明に関連する技術の構成を示す図である。
【図２】本発明の基本構成を示す図である。
【図３】本発明に関連する技術の構成のシステム構成の実施例を示す図である。
【図４】道路区間のデータ，道路点データ，地点データの実施例を示す図である。
【図５】速度テーブルの例を示す図である。
【図６】評価テーブルと経路情報の例を示す図である。
【図７】実施例１のフローチャート（ダイクストラ法）を示す図である。
【図８】実施例２の説明図である。
【図９】実施例２の説明図である。
【図１０】実施例２のシステム構成を示す図である。
【図１１】道路点付随データと地点データの例を示す図である。
【図１２】実施例２の全体的フローチャートを示す図である。
【図１３】目的地点周辺の経路探索のフローチャートを示す図である。
【図１４】実施例２の全経路探索のフローチャート（その１）を示す図である。
【図１５】実施例２の全経路探索のフローチャート（その２）を示す図である。
【図１６】システム構成の実施例３を示す図である。
【図１７】速度テーブルの変更方法と調整係数の変更方法の実施例を示す図である。
【図１８】調整係数の変更方法の実施例を示す図である。
【符号の説明】
【００５７】
１：道路データ保持部
２：区間データ
３：属性，調整係数
４：道路点データ
１０：速度テーブル保持部
１１：速度テーブル
１５：経路探索部
２５：表示部
２６：入力部
４２：主要道路データ部
４３：詳細道路データ部
【特許請求の範囲】
【請求項１】
目的地点および出発地点となる地点を入力する入力部と，道路データを保持する道路データ保持部と，道路データをもとに出発地点から目的地点に至る経路を探索して最適経路を求める経路探索部と，最適経路の経路情報を出力する出力部とを備えた経路探索装置における最適経路探索方法において，
前記経路探索部は，
詳細道路データに基づいて着目地点からその付近の主要道路に至る経路を探索する周辺探索部と，
詳細道路データおよび主要道路データのうちの選択された道路データで経路探索をすることのできる全経路探索部とを有し，
前記経路探索部は，
前記周辺探索部により目的地の周辺の主要道路上の道路点のうちから選択された道路点であるサテライトを求め，
前記全経路探索部により出発地点からその周辺の主要道路に至る経路を詳細道路データにより探索し，そのようにして求められた主要道路上の道路点から該サテライトもしくは目的地点が主要道路上ある場合には目的地点に至る経路を主要道路データにより探索して最適経路を求める
ことを特徴とする最適経路探索方法。
【請求項２】
前記経路探索部は，
最適経路を経路の距離により評価し，最短距離に近い経路を最適経路とする
ことを特徴とする請求項１に記載の最適経路探索方法。
【請求項３】
前記経路探索装置は，
経路を移動する速度を表す速度テーブルを備え，
前記経路探索部は，
前記速度テーブルを用いた算出した最適経路を移動する時間により経路を評価し，最短時間に近い経路を最適経路とする
ことを特徴とする請求項１に記載の最適経路探索方法。
【請求項４】
前記経路探索部は，
出発地点および目的地点となる地点が複数ある場合に，それぞれの地点を出発地点および目的地点としてそれぞれの地点間の最適経路を求め，
前記出力部は，
求められたそれぞれの地点間の最適経路情報を出力する
ことを特徴とする請求項１，２または３に記載の最適経路探索方法。
【請求項５】
前記経路探索部は，
求めたサテライトを保存しておき，次回の探索時に再使用する
ことを特徴とする請求項１，２，３または４に記載の最適経路探索方法。
【請求項１】
目的地点および出発地点となる地点を入力する入力部と，道路データを保持する道路データ保持部と，道路データをもとに出発地点から目的地点に至る経路を探索して最適経路を求める経路探索部と，最適経路の経路情報を出力する出力部とを備えた経路探索装置における最適経路探索方法において，
前記経路探索部は，
詳細道路データに基づいて着目地点からその付近の主要道路に至る経路を探索する周辺探索部と，
詳細道路データおよび主要道路データのうちの選択された道路データで経路探索をすることのできる全経路探索部とを有し，
前記経路探索部は，
前記周辺探索部により目的地の周辺の主要道路上の道路点のうちから選択された道路点であるサテライトを求め，
前記全経路探索部により出発地点からその周辺の主要道路に至る経路を詳細道路データにより探索し，そのようにして求められた主要道路上の道路点から該サテライトもしくは目的地点が主要道路上ある場合には目的地点に至る経路を主要道路データにより探索して最適経路を求める
ことを特徴とする最適経路探索方法。
【請求項２】
前記経路探索部は，
最適経路を経路の距離により評価し，最短距離に近い経路を最適経路とする
ことを特徴とする請求項１に記載の最適経路探索方法。
【請求項３】
前記経路探索装置は，
経路を移動する速度を表す速度テーブルを備え，
前記経路探索部は，
前記速度テーブルを用いた算出した最適経路を移動する時間により経路を評価し，最短時間に近い経路を最適経路とする
ことを特徴とする請求項１に記載の最適経路探索方法。
【請求項４】
前記経路探索部は，
出発地点および目的地点となる地点が複数ある場合に，それぞれの地点を出発地点および目的地点としてそれぞれの地点間の最適経路を求め，
前記出力部は，
求められたそれぞれの地点間の最適経路情報を出力する
ことを特徴とする請求項１，２または３に記載の最適経路探索方法。
【請求項５】
前記経路探索部は，
求めたサテライトを保存しておき，次回の探索時に再使用する
ことを特徴とする請求項１，２，３または４に記載の最適経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２００７−１７１２１１（Ｐ２００７−１７１２１１Ａ）
【公開日】平成１９年７月５日（２００７．７．５）
【国際特許分類】
【出願番号】特願２００７−２７４３４（Ｐ２００７−２７４３４）
【出願日】平成１９年２月７日（２００７．２．７）
【分割の表示】特願平８−１８１８２１の分割
【原出願日】平成８年７月１１日（１９９６．７．１１）
【出願人】（５９１１２８７６３）株式会社富士通ソーシアルサイエンスラボラトリ (57)
【Ｆターム（参考）】
【公開日】平成１９年７月５日（２００７．７．５）
【国際特許分類】
【出願日】平成１９年２月７日（２００７．２．７）
【分割の表示】特願平８−１８１８２１の分割
【原出願日】平成８年７月１１日（１９９６．７．１１）
【出願人】（５９１１２８７６３）株式会社富士通ソーシアルサイエンスラボラトリ (57)
【Ｆターム（参考）】
[ Back to top ]