経路探索方法、経路探索システム及び経路探索サーバ装置
【課題】出発地から目的地までの探索距離の長さ、道路形状の複雑さに関係なく、細街路まで含めた詳細な探索を行うことができるナビゲーション装置等の経路探索方法を提供すること。
【解決手段】地図データを分割したエリア毎に経路探索サーバ装置を有する。経路探索サーバ装置は、探索開始地点側に隣接するエリアの経路探索サーバ装置から第１の探索情報を受信するステップと、第１の探索情報に基づいて、自エリア内の経路を探索するステップと、経路探索の探索結果に従って第１の探索情報を更新した第２の探索情報を探索終了地点側に隣接するエリアの経路探索サーバ装置に送信するステップとを備えることにより、出発地から目的地までの詳細な経路探索を行う。
【解決手段】地図データを分割したエリア毎に経路探索サーバ装置を有する。経路探索サーバ装置は、探索開始地点側に隣接するエリアの経路探索サーバ装置から第１の探索情報を受信するステップと、第１の探索情報に基づいて、自エリア内の経路を探索するステップと、経路探索の探索結果に従って第１の探索情報を更新した第２の探索情報を探索終了地点側に隣接するエリアの経路探索サーバ装置に送信するステップとを備えることにより、出発地から目的地までの詳細な経路探索を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地から目的地までの経路を探索する経路探索方法、経路探索システム及び経路探索サーバ装置に関するものである。
【背景技術】
【０００２】
従来のナビゲーション装置等の経路探索方法は、地図データを分割し、道路種別に従って階層化して、探索する経路数を減らすことにより、探索の効率化を図っている。この方法は、各階層の地図データをブロックに分割して、出発地と目的地とのブロックの位置関係に応じて、経路探索を行っている。すなわち、はじめに、出発地と目的地とを含む最詳細なブロックにおいて、そのブロック同士が隣接しない場合は、上位階層のブロックに連結する連結交差点までの経路を探索する。次に、上位階層のブロックに移行して、この連結交差点を出発点としてブロック内を探索する。この探索を繰り返すことにより、最終的に出発地側からの探索と目的地側からの探索とが、同一ブロック、又は隣接ブロックとなった時点で、両者の経路を連結させて経路探索を終了する。
【０００３】
以上のように、地図データを階層構造にブロック分割し、出発地と目的地とを含むブロックの階層から上位階層のブロックに順次移行して探索を行うことで、探索時間が短縮され、効率のよい経路探索を行っている（例えば、特許文献１）。
【特許文献１】特開平２−５６５９１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の経路探索方法においては、出発地と目的地との探索距離が長くなるに伴って、主要幹線道路や高速道路等の上位階層の道路を通る経路探索が行われる。また、市街地等の複雑な道路形状の場合も同様に、上位階層の地図を用いた経路探索へ移行される。このため、細街路まで含めた詳細な経路探索を行うことが困難であった。
【０００５】
本発明は、従来の問題を解決するためになされたもので、出発地から目的地までの探索距離の長さ、道路形状の複雑さに関係なく、細街路まで含めた詳細な経路探索を行うことができる経路探索方法、経路探索システム及び経路探索サーバ装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の経路探索方法は、地図データを分割したエリア毎に経路探索サーバ装置を有し、前記経路探索サーバ装置が、自エリアに隣接する第１のエリアの経路探索サーバ装置から第１の探索情報を受信する受信ステップと、前記第１の探索情報に基づいて、自エリア内の経路を探索するステップと、経路探索の探索結果に従って前記第１の探索情報を更新した第２の探索情報を、自エリアに隣接する第２のエリアの経路探索サーバ装置に送信するステップとを備えた構成を有する。
【０００７】
この構成により、受信した探索情報に基づいた探索結果を隣接するエリアを担当する経路探索サーバ装置に順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。
【０００８】
また、本発明の経路探索方法は、前記経路探索ステップが、前記第１の探索情報に含まれる探索開始地点の通過予定時刻が、自経路探索サーバ装置に登録されている前記探索開始地点の通過予定時刻より早いか否かを判定し、早いとの判定がなされたときに、自エリア内の経路を探索する構成を有する。
【０００９】
この構成により、経路探索サーバ装置の経路探索に必要な記憶容量を削減することができ、且つ探索時間の短縮化を図ることができる。
【００１０】
また、本発明の経路探索方法は、前記送信ステップが、自エリアの探索終了地点、出発地から自エリアの探索終了地点までの経路及び探索終了地点の通過予定時刻を隣接するエリアの経路探索サーバ装置に送信する構成を有する。
【００１１】
この構成により、受信した探索情報に基づいた探索結果を隣接するエリアを担当する経路探索サーバ装置に順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。
【００１２】
また、本発明の経路探索システムは、地図データを分割したエリア毎に経路探索サーバ装置を有し、前記経路探索サーバ装置は、自エリアに隣接する第１のエリアの経路探索サーバ装置から第１の探索情報を受信する受信手段と、前記第１の探索情報に基づいて、自エリア内の経路を探索する経路探索手段と、前記経路探索手段の探索結果に従って前記第１の探索情報を更新した第２の探索情報を、自エリアに隣接する第２のエリアの経路探索サーバ装置に送信する送信手段とを備えた構成を有する。
【００１３】
この構成により、受信した探索情報に基づいた探索結果を隣接するエリアを担当する経路探索サーバ装置に順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。さらに、詳細な経路探索をエリア毎の経路探索サーバ装置で協調分散して行うため、各経路探索サーバ装置の経路探索に必要な記憶容量を削減することができ、且つ探索時間の短縮化を図ることができる。
【００１４】
本発明の経路探索サーバ装置は、自エリアに隣接する第１のエリアの通信装置から第１の探索情報を受信する受信手段と、前記第１の探索情報に基づいて自エリア内の経路を探索する経路探索手段と、前記経路探索手段の探索結果に従って前記第１の探索情報を更新した第２の探索情報を、自エリアに隣接する第２のエリアの通信装置に送信する送信手段とを備えた構成を有する。
【００１５】
この構成により、受信した探索情報に基づいた探索結果を隣接するエリアを担当する経路探索サーバ装置に順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。
【００１６】
本発明の経路探索サーバ装置は、前記経路探索手段が、前記第１の探索情報に含まれる探索開始地点の通過予定時刻が、自経路探索サーバ装置に登録されている前記探索開始地点の通過予定時刻より早いか否かを判定し、早いとの判定がなされたときに、自エリア内の経路を探索する構成を有する。
【００１７】
この構成により、経路探索サーバ装置の経路探索に必要な記憶容量を削減することができ、且つ探索時間の短縮化を図ることができる。
【００１８】
本発明の経路探索サーバ装置は、前記送信手段が、自エリアの探索終了地点、出発地から自エリアの探索終了地点までの経路及び探索終了地点の通過予定時刻を隣接するエリアの通信装置に送信する構成を有する。
【００１９】
この構成により、受信した探索情報に基づいた探索結果を隣接するエリアを担当する経路探索サーバ装置に順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。
【発明の効果】
【００２０】
本発明は、出発地から目的地までの探索距離の長さ、道路形状の複雑さに関係なく、細街路まで含めた詳細な経路探索を行うことができる経路探索方法、経路探索システム及び経路探索サーバ装置を提供することができるものである。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の実施の形態について、図面を用いて説明する。
【００２２】
（実施の形態１）
図１は、本発明の実施の形態１の経路探索システムの構成を示すブロック図である。図２は、本発明の実施の形態１の経路探索システムにおける地図の分割例を説明する図である。
【００２３】
図１に示すように、本実施の形態１の経路探索システムは、地図を複数に分割したエリア毎に、予め決められたエリア内を経路探索する経路探索サーバ装置（以下、サーバという）ＳＶ１、ＳＶ２、ＳＶ３を有している。
【００２４】
サーバＳＶ１は、図２に示す予め決められたエリアＡ１を担当し、エリアＡ１内の経路探索を行う経路探索手段１２と、エリアＡ１に隣接するエリアＡ２、Ａ３をそれぞれ担当するサーバＳＶ２、ＳＶ３の各々の送信手段２３、３３から探索情報をそれぞれ受信する受信手段１１と、サーバＳＶ２、ＳＶ３の各々の受信手段２１、３１に探索情報をそれぞれ送信する送信手段１３とを有している。
【００２５】
サーバＳＶ２は、前述のように、図２に示す予め決められたエリアＡ２を担当し、エリアＡ２内の経路探索を行う経路探索手段２２と、エリアＡ２に隣接するエリアＡ１、Ａ３をそれぞれ担当するサーバＳＶ１、ＳＶ３の各々の送信手段１３、３３から探索情報をそれぞれ受信する受信手段２１と、サーバＳＶ１、ＳＶ３の各々の受信手段１１、３１に探索情報をそれぞれ送信する送信手段２３とを有している。
【００２６】
サーバＳＶ３は、前述のように、図２に示す予め決められたエリアＡ３を担当し、エリアＡ３内の経路探索を行う経路探索手段３２と、エリアＡ３と隣接するエリアＡ１、Ａ２をそれぞれ担当するサーバＳＶ１、ＳＶ２の各々の送信手段１３、２３から探索情報をそれぞれ受信する受信手段３１と、サーバＳＶ１、ＳＶ２に探索情報をそれぞれ送信する送信手段３３とを有している。
【００２７】
図２において、太い実線は道路、網点部の領域はエリアＡ１、斜線部の領域はエリアＡ２、格子部の領域はエリアＡ３を示す。各エリア内の四角形は、サーバＳＶ１、ＳＶ２、ＳＶ３を示す。また、楕円は、エリアＡ１とエリアＡ２との境界、エリアＡ１とエリアＡ３との境界及びエリアＡ２とエリアＡ３との境界における道路の交差点であって、隣接点Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９を示す。エリアＡ１の三角形は、経路探索を開始する出発地Ｐ０を示し、エリアＡ３の逆三角形は、経路探索を終了する目的地ＰＮを示す。
【００２８】
次に、図３（ａ）〜図３（ｃ）及び図４（ａ）〜図４（ｃ）を用いて、サーバＳＶ１〜ＳＶ３に登録する情報テーブルについて説明する。
【００２９】
図３（ａ）は、サーバＳＶ１に事前登録されているエリアＡ１内の各隣接点Ｐ１〜Ｐ５と、これらの隣接点で隣接するエリアを担当するサーバとを予め関連付けた隣接点テーブルを示す。
【００３０】
図３（ｂ）は、前述のように、サーバＳＶ２に事前登録されているエリアＡ２内の各隣接点Ｐ１、Ｐ２及びＰ５〜Ｐ９と、これらの隣接点で隣接するエリアを担当するサーバとを予め関連付けた隣接点テーブルを示す。
【００３１】
図３（ｃ）は、前述のように、サーバＳＶ３に事前登録されているエリアＡ３内の各隣接点Ｐ３〜Ｐ９と、これらの隣接点で隣接するエリアを担当するサーバとを予め関連付けた隣接点テーブルを示す。
【００３２】
図４（ａ）、図４（ｂ）及び図４（ｃ）は、経路探索を行う過程において、サーバＳＶ１〜ＳＶ３に登録される、探索ＩＤと、エリア内の探索開始地点（出発地又は隣接点）又は探索終了地点（隣接点又は目的地）と、その地点の出発時刻（出発地）、通過予定時刻（隣接点）又は到着予定時刻（目的地）とを関連付けた探索結果テーブルを示す。探索結果テーブルに登録する各情報については、後述の動作説明にて具体例を示し説明する。
【００３３】
上記経路探索システムの動作について、図５及び図６に示すフローチャートを用いて説明する。
【００３４】
図５において、サーバは、カーナビゲーション等の経路探索クライアント装置（図示せず）又は隣接するエリアを担当するサーバから送信された探索情報を受信手段にて受信することで処理を開始する（ステップＳ６１）。
【００３５】
サーバは、経路情報を受信すると、まず、受信した経路情報に含まれる検索ＩＤと検索開始地点を取り出し、検索ＩＤに関連付けられた、探索開始地点が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００３６】
探索ＩＤと関連付けられた、探索開始地点（隣接点）が探索結果テーブルに登録されていない場合（ステップＳ６５、Ｎｏ）、その探索ＩＤと、探索情報に含まれる探索開始地点（隣接点）と、探索情報に含まれている同点の通過予定時刻とを探索結果テーブルに新規登録し（ステップＳ６３）、その探索開始地点（隣接点）から探索終了地点（自エリアの他の隣接点又は目的地）までの経路探索を経路探索手段にて開始する（ステップＳ６４）。
【００３７】
一方、探索ＩＤと関連付けられた、探索開始地点（隣接点）が探索結果テーブルに登録されている場合（ステップＳ６５、Ｙｅｓ）、サーバは、受信した探索情報に含まれている探索開始地点（隣接点）の通過予定時刻ｔ２が、既に探索結果テーブルに登録されている同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ６６）。これは、同一の探索開始地点（隣接点）を通過する通過予定時刻が早い経路についてのみ、同点から探索終了地点（自エリアの他の隣接点又は目的地）まで経路探索を行い、通過予定時刻が遅い経路については経路探索を行わないようにするためのものである。
【００３８】
受信した探索情報に含まれる探索開始地点（隣接点）の通過予定時刻ｔ２が、既に探索結果テーブルに登録されている同点の通過予定時刻ｔ１より早い場合（ステップＳ６６、Ｙｅｓ）、探索結果テーブルの通過予定時刻を通過予定時刻ｔ２に更新し（ステップＳ６３）、その探索開始地点（隣接点）から探索終了地点（自エリアの他の隣接点又は目的地）までの経路探索を経路探索手段にて開始する（ステップＳ６４）。
【００３９】
一方、受信した探索情報に含まれる探索開始地点（隣接点）の通過予定時刻ｔ２が、既に探索テーブルに登録されている同点の通過予定時刻ｔ１より遅い場合（ステップＳ６６、Ｎｏ）、サーバは経路探索を行うことなく、処理を終了する。
【００４０】
次に、図６において、サーバが経路探索を開始した後の動作について説明する。
【００４１】
まず、経路探索を開始すると、サーバは、目的地が自エリア内に存在するか否かを判定する（ステップＳ６７）。目的地が自エリア内に存在する場合（ステップＳ６７、ＹＥＳ）、探索開始地点（出発地又は隣接点）から目的地までの経路を探索する（ステップＳ６８）。
【００４２】
さらに、ステップＳ６８で経路の探索を行った結果、目的地の到着予定時刻ｔ４が、探索結果テーブルに既に登録されている、探索情報に含まれている探索ＩＤと同じ探索ＩＤで関連付けられた目的地の到着予定時刻ｔ３より早いか否かを判定する（ステップＳ６９）。目的地の到着予定時刻ｔ４が、探索結果テーブルに既に登録されている目的地の到着予定時刻ｔ３より早い場合（ステップＳ６９、ＹＥＳ）、探索結果テーブルの到着予定時刻を到着予定時刻ｔ４に更新する（ステップＳ７０）。なお、探索情報に含まれている探索ＩＤと同じ探索ＩＤで関連付けられた目的地の到着予定時刻が、探索結果テーブルに登録されていない場合は、探索ＩＤと、探索終了地点（目的地）と、到着予定時刻ｔ４とを探索結果テーブルに新規登録する（ステップＳ７０）。
【００４３】
一方、ステップＳ６８で経路探索を行った結果、目的地の到着予定時刻ｔ４が、探索結果テーブルに既に登録されている目的地の到着予定時刻ｔ３より遅い場合（ステップＳ６９、ＮＯ）、サーバは、探索結果テーブルに新規登録又は更新を行うことなく、処理を終了する。
【００４４】
次に、目的地が自エリア外の場合（ステップＳ６７、ＮＯ）、サーバは、隣接点テーブルから登録順に隣接点を一つ取り出し（ステップＳ７１）、探索開始地点（出発地又は隣接点）から取り出した隣接点までの経路を探索する（ステップＳ７２）。なお、隣接点を取り出す順番は隣接点テーブルの登録順に限定されるものではなく、目的地に距離が近い順番等でもよい。目的地に距離が近い順番に隣接点を取り出すことにより、探索順序をコントロールできるため、無駄な探索を行うことが少なくなり、効率的な探索を行うことができる。
【００４５】
次に、サーバは、ステップＳ７２で経路の探索を行った結果、その探索終了地点（隣接点）の通過予定時刻ｔ２が、探索結果テーブルに既に登録されている、探索情報に含まれている探索ＩＤと同じ探索ＩＤで関連付けられた同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ７３）。通過予定時刻ｔ２が通過予定時刻ｔ１より早い場合（ステップＳ７３、Ｙｅｓ）、探索結果テーブルの通過予定時刻を通過予定時刻ｔ２に更新する（ステップＳ７４）。なお、探索情報に含まれている探索ＩＤと同じ探索ＩＤで関連付けられた通過予定時刻が、探索結果テーブルに登録されていない場合は、探索ＩＤと、探索終了地点（隣接点）と、同点の通過予定時刻ｔ２とを探索結果テーブルに新規登録する（ステップＳ７４）。
【００４６】
さらに、サーバは、探索結果テーブルへ各情報の新規登録又は更新を行った後、隣接点テーブルから探索終了地点（隣接点）で隣接するエリアを担当する隣接エリアのサーバを特定する。そして、そのサーバに対して、探索ＩＤ、出発地、出発時刻、目的地、自エリアの探索終了地点（同点を担当する隣接エリアのサーバにとっては、探索開始地点となる）、出発地から自エリアの探索終了地点（隣接点）までの経路及び探索終了地点（隣接点）の通過予定時刻を送信手段にて送信する（ステップＳ７５）。
【００４７】
一方、通過予定時刻ｔ２が通過予定時刻ｔ１より遅い場合（ステップＳ７３、Ｎｏ）、又はステップＳ７５で探索情報を送信した後、自エリア内に経路の探索を行っていない隣接点が他にあるか否かを隣接点テーブルを用いて判定する（ステップＳ７６）。
【００４８】
隣接点テーブルに経路の探索を行っていない隣接点が他にある場合（ステップＳ７６、Ｙｅｓ）、上述と同様に隣接点を一つ取り出し、ステップＳ７２〜Ｓ７６を繰り返す。これにより、探索開始地点（出発地又は隣接点）から自エリア内の全ての探索終了地点（隣接点）まで経路の探索を行い、各探索終了地点（隣接点）を担当する隣接エリアのサーバに対して、探索結果を順次引継いでいく。
【００４９】
一方、隣接点テーブルに経路探索を行っていない隣接点がない場合（ステップＳ７６、Ｎｏ）、サーバは、処理を終了する。
【００５０】
次に、図２に示す出発地P０から目的地ＰＮまでの経路探索を行う場合を例にとって、上述の動作を具体的に説明する。
【００５１】
まず、サーバＳＶ１は、カーナビゲーション等の経路探索クライアント装置（図示せず）から送信された、出発地Ｐ０、目的地ＰＮ及び出発時刻を含む探索情報を受信手段１１にて受信することで処理を開始する（ステップＳ６１）。
【００５２】
サーバＳＶ１は、経路情報を受信すると、まず、受信した経路情報に含まれる検索ＩＤ(この例では、１とする)と検索開始地点（出発地Ｐ０）を取り出し、検索ＩＤ(１)に関連付けられた、探索開始地点(出発地Ｐ０)が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００５３】
ここでは、探索ＩＤ（１）と関連付けられた、探索開始地点（出発地Ｐ０）が探索結果テーブルに登録されていないため（ステップＳ６５、Ｎｏ）、図４（ａ）に示すように、その探索ＩＤ（１）と探索開始地点（出発地Ｐ０）と、受信した出発時刻（この例では、１５：３０：００とする）とを探索結果テーブルに新規登録し（ステップＳ６３）、経路探索手段１２にて経路探索を開始する（ステップＳ６４）。
【００５４】
次に、経路探索を開始すると、サーバＳＶ１は、目的地ＰＮが自エリアＡ１内に存在するか否かを判定する（ステップＳ６７）。ここでは、目的地ＰＮが自エリアＡ１内に存在しないため（ステップＳ６７、ＮＯ）、隣接点テーブルから登録されている順序で隣接点Ｐ１を取り出し（ステップＳ７１）、探索開始地点（出発地Ｐ０）から探索終了地点（隣接点Ｐ１）までの経路を探索する（ステップＳ７２）。
【００５５】
サーバＳＶ１は、探索開始地点（出発地Ｐ０）から探索終了地点（隣接点Ｐ１）までの経路探索の結果、探索終了地点（隣接点Ｐ１）の通過予定時刻ｔ２が、探索結果テーブルに既に登録されている、探索情報に含まれている探索ＩＤと同じ探索ＩＤで関連付けられた同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ７３）。ここでは、探索終了地点（隣接点Ｐ１）の通過予定時刻ｔ１が、探索結果テーブルに登録されていないため、探索ＩＤ（１）と、探索終了地点（隣接点Ｐ１）と、同点の通過予定時刻（１５：３２：００）を図４（ａ）に示すように、探索結果テーブルに新規登録する（ステップＳ７４）。
【００５６】
さらに、サーバＳＶ１は、探索終了地点（隣接点Ｐ１）で隣接するエリアを担当する隣接エリアのサーバＳＶ２を隣接点テーブルにて特定する。そして、サーバＳＶ１は、サーバＳＶ２に対して、探索ＩＤ（１）、出発地Ｐ０、出発時刻（１５：３０：００）、目的地ＰＮ、自エリアの探索終了地点（隣接点Ｐ１）、出発地Ｐ０から自エリアの探索終了地点（隣接点Ｐ１）までの経路及び探索終了地点（隣接点Ｐ１）の通過予定時刻（１５：３２：００）を送信手段１３から送信する（ステップＳ７５）。
【００５７】
次に、エリアＡ１内に経路探索を行っていない隣接点が他にあるか否かを隣接点テーブルを用いて判定する（ステップＳ７６）。ここでは、経路探索を行っていない隣接点Ｐ２〜Ｐ５があるため、（ステップＳ７６、Ｙｅｓ）、上述と同様に隣接点を一つずつ取り出し、ステップＳ７２〜Ｓ７６を繰り返す。これにより、図４（ａ）に示すように、探索開始地点（出発地Ｐ０）から探索終了地点（隣接点Ｐ１〜Ｐ５）までの探索結果を探索結果テーブルへ新規登録する。また、隣接点Ｐ１及びＰ２に関する探索情報は、サーバＳＶ２に送信し、隣接点Ｐ３〜Ｐ４に関する探索情報は、サーバＳＶ３に送信し、隣接点Ｐ５に関する探索情報は、サーバＳＶ２およびサーバＳＶ３の両方に送信する。
【００５８】
サーバＳＶ１は、全ての隣接点について経路探索を行った場合（ステップＳ７６、Ｎｏ）、処理を終了する。
【００５９】
次に、サーバＳＶ１から探索情報を受信したサーバＳＶ２の動作について説明する。
【００６０】
まず、サーバＳＶ２は、サーバＳＶ１から送信された、隣接点Ｐ１に関する探索情報を受信手段２１で受信することで処理を開始する（ステップＳ６１）。
【００６１】
サーバＳＶ２は、経路情報を受信すると、まず、受信した経路情報に含まれる検索ＩＤ(１)と検索開始地点（隣接点Ｐ１）を取り出し、検索ＩＤ(１)に関連付けられた、探索開始地点(隣接点Ｐ１)が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００６２】
ここでは、探索ＩＤ（１）に関連付けられた、検索開始地点(隣接点Ｐ１)が探索結果テーブルに登録されていないため（ステップＳ６５、Ｎｏ）、図４（ｂ）に示すように、探索ＩＤ（１）と、探索情報に含まれる探索開始地点（隣接点Ｐ１）と、同点の通過予定時刻（１５：３２：００）とを探索結果テーブルに新規登録し（ステップＳ６３）、経路探索手段２２により経路探索を開始する（ステップＳ６４）。
【００６３】
次に、経路探索を開始すると、まず、サーバＳＶ２は、目的地ＰＮがエリアＡ２内に存在するか否かを判定する（ステップＳ６７）。ここでは、目的地ＰＮがエリアＡ２内に存在しないため（ステップＳ６７、Ｎｏ）、隣接点テーブルから登録されている順序で隣接点Ｐ２を取り出し（ステップＳ７１）、探索開始地点（隣接点Ｐ１）から探索終了地点（隣接点Ｐ２）までの経路探索を行う（ステップＳ７２）。ここで、サーバは、探索開始地点と探索終了地点が同一の場合の経路探索は行わないものとするため、隣接点テーブルから隣接点Ｐ１ではなく、隣接点Ｐ２を取り出す。
【００６４】
次に、サーバＳＶ２は、探索開始地点（隣接点Ｐ１）から探索終了地点（隣接点Ｐ２）までの経路探索の結果、探索終了地点（隣接点Ｐ２）の通過予定時刻ｔ２が、探索結果テーブルに既に登録されている、探索情報に含まれている探索ＩＤと同じ探索ＩＤで関連付けられた同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ７３）。ここでは、探索終了地点（隣接点Ｐ２）の通過予定時刻ｔ１が探索結果テーブルに登録されていないため、探索ＩＤ（１）と、探索終了地点（隣接点Ｐ２）と、同点の通過予定時刻（１５：３４：００）を図４（ｂ）に示すように、探索結果テーブルに新規登録する（ステップＳ７４）。
【００６５】
さらに、サーバＳＶ２は、探索終了地点（隣接点Ｐ２）で隣接するエリアを担当する隣接エリアのサーバＳＶ１を隣接点テーブルにて特定する。そして、サーバＳＶ２は、サーバＳＶ１に対して、探索ＩＤ（１）、出発地Ｐ０、出発時刻（１５：３０：００）、目的地ＰＮ、自エリアの探索終了地点（隣接点Ｐ２）、出発地Ｐ０から自エリアの探索終了地点（隣接点Ｐ２）までの経路及び探索終了地点（隣接点Ｐ２）の通過予定時刻（１５：３４：００）を送信手段２３から送信する（ステップＳ７５）。
【００６６】
次に、自エリアＡ２内に経路探索を行っていない隣接点が他にあるか否かを隣接点テーブルを用いて判定する（ステップＳ７６）。ここでは、経路探索を行っていない隣接点Ｐ５〜Ｐ９があるため（ステップＳ７６、Ｙｅｓ）、上述と同様に隣接点Ｐ５を取り出し（ステップＳ７１）、探索開始地点（隣接点Ｐ１）から探索終了地点（隣接点Ｐ５）までの経路を探索する（ステップＳ７２）。
【００６７】
探索開始地点（隣接点Ｐ１）から探索終了地点（隣接点Ｐ５）までの経路探索の結果、探索終了地点（隣接点Ｐ５）の通過予定時刻ｔ２が、探索結果テーブルに既に登録されている、同じ探索ＩＤで関連付けられた同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ７３）。ここでは、通過予定時刻ｔ１が探索結果テーブルに登録されていないため、探索ＩＤ（１）と、探索終了地点（隣接点Ｐ５）と、同点の通過予定時刻（１５：３６：００）を図４（ｂ）に示すように、探索結果テーブルに新規登録する（ステップＳ７４）。
【００６８】
さらに、サーバＳＶ２は、探索終了地点（隣接点Ｐ５）で隣接するエリアを担当する隣接エリアのサーバＳＶ１とサーバＳＶ３を隣接点テーブルにて特定する。そして、サーバＳＶ２は、サーバＳＶ１とサーバＳＶ３に対して、探索ＩＤ（１）、出発地Ｐ０、出発時刻（１５：３０：００）、目的地ＰＮ、自エリアの探索終了地点（隣接点Ｐ５）、出発地Ｐ０から自エリアの探索終了地点（隣接点Ｐ５）までの経路及び探索終了地点（隣接点Ｐ５）の通過予定時刻（１５：３６：００）を送信手段２３から送信する（ステップＳ７５）。
【００６９】
上述と同様に、探索開始地点（隣接点Ｐ１）から探索終了地点（隣接点Ｐ６〜Ｐ９）までの経路探索を行い、探索終了地点（隣接点Ｐ６〜Ｐ９）の通過予定時刻を図４（ｂ）に示すように探索結果テーブルに新規登録し（ステップＳ７４）、隣接点Ｐ６〜Ｐ９を担当するサーバＳＶ３に対して、探索情報を送信手段２３にて送信する（ステップＳ７５）。サーバＳＶ２は、全ての隣接点について経路の探索を行った後、処理を終了する。
【００７０】
次に、サーバＳＶ２は、サーバＳＶ１から送信された、隣接点Ｐ２に関する探索情報を受信手段２１で受信することで処理を開始する（ステップＳ６１）。
【００７１】
サーバＳＶ２は、まず、受信した経路情報に含まれる検索ＩＤ(１)と検索開始地点（隣接点Ｐ２）を取り出し、検索ＩＤ(１)に関連付けられた、探索開始地点(隣接点Ｐ２)が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００７２】
ここでは、探索ＩＤ（１）と関連付けられた、探索開始地点（隣接点Ｐ２）が探索結果テーブルに登録されているため（ステップＳ６５、Ｙｅｓ）、受信した探索情報に含まれている探索開始地点（隣接点）の通過予定時刻ｔ２が、既に探索結果テーブルに登録されている同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ６６）。ここでは、受信した探索情報に含まれる探索開始地点（隣接点Ｐ２）の通過予定時刻ｔ２（１５：３３：００）が、既に探索結果テーブルに登録されている同点の通過予定時刻ｔ１（１５：３４：００）より早いため（ステップＳ６６、Ｙｅｓ）、図７に示すように探索開始地点（隣接点Ｐ２）の通過予定時刻を通過予定時刻ｔ２（１５：３３：００）に更新し（ステップＳ６３）、経路探索手段２２により経路探索を開始する（ステップＳ６４）。
【００７３】
次に、経路探索を開始すると、サーバＳＶ２は、目的地ＰＮがエリアＡ２内に存在するか否かを判定する（ステップＳ６７）。ここでは、目的地ＰＮがエリアＡ２内に存在しないため（ステップＳ６７、Ｎｏ）、隣接点テーブルから登録されている順序で隣接点Ｐ１を取り出し（ステップＳ７１）、探索開始地点（隣接点Ｐ２）から探索終了地点（隣接点Ｐ１）までの経路の探索を行う（ステップＳ７２）。
【００７４】
次に、サーバＳＶ２は、探索開始地点（隣接点Ｐ２）から探索終了地点（隣接点Ｐ１）までの経路探索の結果、探索終了地点（隣接点Ｐ１）の通過予定時刻ｔ２が、探索結果テーブルに既に登録されている同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ７３）。ここでは、探索終了地点（隣接点Ｐ１）の通過予定時刻ｔ２（１５：３５：００）が、探索結果テーブルに登録されている同点の通過予定時刻ｔ１（１５：３２：００）より遅いため（ステップＳ７３、Ｎｏ）、次に、自エリアＡ２内に経路探索を行っていない隣接点が他にあるか否かを隣接点テーブルを用いて判定する（ステップＳ７６）。ここでは、経路探索を行っていない隣接点Ｐ５〜Ｐ９があるため、（ステップＳ７６、Ｙｅｓ）、上述と同様に隣接点Ｐ５を取り出し（ステップＳ７１）、探索開始地点（隣接点Ｐ２）から探索終了地点（隣接点Ｐ５）までの経路を探索する（ステップＳ７２）。
【００７５】
探索開始地点（隣接点Ｐ２）から探索終了地点（隣接点Ｐ５）までの経路探索の結果、探索終了地点（隣接点Ｐ５）の通過予定時刻ｔ２が、探索結果テーブルに既に登録されている同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ７３）。ここでは、探索終了地点（隣接点Ｐ５）の通過予定時刻ｔ２（１５：３４：４５）が、探索結果テーブルに既に登録されている同点の通過予定時刻ｔ１（１５：３６：００）より早いため（ステップＳ７３、Ｙｅｓ）、探索結果テーブルにおける探索終了地点（隣接点Ｐ５）の通過予定時刻を図７に示すように更新する（ステップＳ７４）。
【００７６】
さらに、サーバＳＶ２は、探索終了地点（隣接点Ｐ５）で隣接するエリアを担当する隣接エリアのサーバＳＶ１とサーバＳＶ３を隣接点テーブルにて特定する。そして、サーバＳＶ２は、サーバＳＶ１とサーバＳＶ３に対して、探索ＩＤ（１）、出発地Ｐ０、出発時刻（１５：３０：００）、目的地ＰＮ、自エリアの探索終了地点（隣接点Ｐ５）、出発地Ｐ０から自エリアの探索終了地点（隣接点Ｐ５）までの経路及び探索終了地点（隣接点Ｐ５）の通過予定時刻（１５：３４：４５）を送信手段２３にて送信する（ステップＳ７５）。
【００７７】
上述と同様に、探索開始地点（隣接点Ｐ２）から探索終了地点（隣接点Ｐ６〜Ｐ９）までの経路探索を行い、探索終了地点（隣接点Ｐ６〜Ｐ９）の通過予定時刻について、図７に示すように探索結果テーブルを更新し（ステップＳ７４）、隣接点Ｐ６〜Ｐ９を担当するサーバＳＶ３に探索情報を送信手段２３にて送信する（ステップＳ７５）。サーバＳＶ２は、全ての隣接点について経路の探索を行った後、処理を終了する。
【００７８】
次に、サーバＳＶ１から探索情報を受信したサーバＳＶ３の動作について説明する。
【００７９】
サーバＳＶ３は、サーバＳＶ１から送信された、隣接点Ｐ３に関する探索情報を受信手段３１で受信することで処理を開始する（ステップＳ６１）。
【００８０】
サーバＳＶ３は、まず、受信した経路情報に含まれる検索ＩＤ(１)と検索開始地点（隣接点Ｐ３）を取り出し、検索ＩＤ(１)に関連付けられた、探索開始地点(隣接点Ｐ３)が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００８１】
ここでは、探索ＩＤ（１）が、探索結果テーブルに登録されていないため（ステップＳ６５、Ｎｏ）、図４（ｃ）に示すように、探索ＩＤ（１）と、受信した探索開始地点（隣接点Ｐ３）と、同点の通過予定時刻（１５：３５：００）とを探索テーブルに新規登録し（ステップＳ６３）、経路探索手段３２により経路探索を開始する（ステップＳ６４）。
【００８２】
次に、経路探索を開始すると、サーバＳＶ３は、目的地ＰＮがエリアＡ３内に存在するか否かを判定する（ステップＳ６７）。ここでは、目的地ＰＮがエリアＡ３内に存在するため（ステップＳ６７、Ｙｅｓ）、探索開始地点（隣接点Ｐ３）から探索終了地点（目的地ＰＮ）までの経路の探索を行う（ステップＳ６８）。
【００８３】
次に、サーバＳＶ３は、探索開始地点（隣接点Ｐ３）から探索終了地点（目的地ＰＮ）までの経路探索の結果、探索終了地点（目的地ＰＮ）の到着予定時刻ｔ４が、探索結果テーブルに既に登録されている同点の到着予定時刻ｔ３より早いか否かを判定する（ステップＳ６９）。ここでは、目的地ＰＮの到着予定時刻ｔ３が探索結果テーブルに登録されていないため、探索ＩＤ（１）と、探索終了地点（目的地ＰＮ）と、同点の到着予定時刻（１５：４８：００）とを探索結果テーブルに新規登録する（ステップＳ７０）。そして、サーバＳＶ３は処理を終了する。
【００８４】
次に、サーバＳＶ３は、サーバＳＶ１から送信された、隣接点Ｐ４に関する探索情報を受信手段３１で受信することで処理を開始する（ステップＳ６１）。
【００８５】
サーバＳＶ３は、まず、受信した経路情報に含まれる検索ＩＤ(１)と検索開始地点（隣接点Ｐ４）を取り出し、検索ＩＤ(１)に関連付けられた、探索開始地点(隣接点Ｐ４)が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００８６】
探索ＩＤ（１）と関連付けられた、探索開始地点（隣接点Ｐ４）が探索テーブルに登録されていないため（ステップＳ６５、Ｎｏ）、その探索ＩＤ（１）と、探索開始地点（隣接点Ｐ４）と、同点の通過予定時刻（１５：３３：００）とを図４（ｃ）に示すように、探索結果テーブルに新規登録し（ステップＳ６３）、経路探索手段３２により経路探索を開始する（ステップＳ６４）。
【００８７】
次に、経路探索を開始すると、サーバＳＶ３は、目的地ＰＮが自エリアＡ３内に存在するか否かを判定する（ステップＳ６７）。ここでは、目的地ＰＮが自エリアＡ３内に存在するため（ステップＳ６７、Ｙｅｓ）、探索開始地点（隣接点Ｐ４）から探索終了地点（目的地ＰＮ）までの経路の探索を行う（ステップＳ６８）。
【００８８】
次に、サーバＳＶ３は、探索開始地点（隣接点Ｐ４）から探索終了地点（目的地ＰＮ）までの経路探索の結果、探索終了地点（目的地ＰＮ）の到着予定時刻ｔ４が、探索結果テーブルに既に登録されている同点の到着予定時刻ｔ３より早いか否かを判定する（ステップＳ６９）。ここでは、到着予定時刻ｔ４（１５：４３：００）が到着予定時刻ｔ３（１５：４８：００）より早いため（ステップＳ６９、Ｙｅｓ）、探索結果テーブルの探索終了地点（目的地ＰＮ）の到着予定時刻を到着予定時刻ｔ４（１５：４３：００）に更新する（ステップＳ７０）。そして、サーバＳＶ３は処理を終了する。
【００８９】
上述と同様に、サーバＳＶ３は、サーバＳＶ１から送信された、隣接点Ｐ５に関する探索情報をもとに、探索結果テーブルの探索開始地点（隣接点Ｐ５）の通過予定時刻（１５：３５：００）を図４（ｃ）に示すように、新規登録する（ステップＳ６３）。また、探索開始地点（隣接点Ｐ５）から探索終了地点（目的地ＰＮ）までの経路探索を行い、図４（ｃ）に示すように、探索終了地点（目的地ＰＮ）の到着予定時刻を到着予定時刻ｔ４（１５：４２：００）に更新する（ステップＳ７０）。そして、サーバＳＶ３は処理を終了する。
【００９０】
次に、サーバＳＶ２から探索情報を受信したサーバＳＶ３の動作について説明する。
【００９１】
サーバＳＶ３は、サーバＳＶ２から送信された、隣接点Ｐ５に関する探索情報を受信手段３１で受信することで処理を開始する（ステップＳ６１）。
【００９２】
サーバＳＶ３は、まず、受信した経路情報に含まれる検索ＩＤ(１)と検索開始地点（隣接点Ｐ５）を取り出し、検索ＩＤ(１)に関連付けられた、探索開始地点(隣接点Ｐ５)が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００９３】
探索ＩＤ（１）と関連付けられた、探索開始地点（隣接点Ｐ５）が探索テーブルに登録されているため（ステップＳ６５、Ｙｅｓ）、受信した探索情報に含まれる探索開始点（隣接点Ｐ５）の通過予定時刻ｔ２が、探索テーブルに既に登録されている同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ６６）。
【００９４】
ここでは、通過予定時刻ｔ２（１５：３４：４５）が通過予定時刻ｔ１（１５：３５：００）より早いため（ステップＳ６６、Ｙｅｓ）、図８に示すように、探索結果テーブルの探索開始地点（隣接点Ｐ５）の通過予定時刻を１５：３４：４５に更新し（ステップＳ６３）、経路探索を開始する（ステップＳ６４）。
【００９５】
次に、経路探索を開始すると、サーバＳＶ３は、目的地ＰＮがエリアＡ３内に存在するか否かを判定する（ステップＳ６７）。ここでは、目的地ＰＮがエリアＡ３内に存在するため（ステップＳ６７、Ｙｅｓ）、探索開始地点（隣接点Ｐ５）から探索終了地点（目的地ＰＮ）までの経路の探索を行う（ステップＳ６８）。
【００９６】
次に、サーバＳＶ３は、探索開始地点（隣接点Ｐ５）から探索終了地点（目的地ＰＮ）までの経路探索の結果、探索終了地点（目的地ＰＮ）の到着予定時刻ｔ４が、探索結果テーブルに既に登録されている到着予定時刻ｔ３より早いか否かを判定する（ステップＳ６９）。ここでは、到着予定時刻ｔ４（１５：４３：３０）が到着予定時刻ｔ３（１５：４３：００）より遅いため（ステップＳ６９、Ｎｏ）、探索結果テーブルの更新を行うことなく、サーバＳＶ３は処理を終了する。
【００９７】
上述と同様に、サーバＳＶ３は、サーバＳＶ２から送信された、隣接点Ｐ６〜Ｐ９に関する探索情報を受信し、経路探索を行った結果に従って、図８に示すように探索結果テーブルを更新する（ステップＳ７０）。サーバＳＶ３は、目的地ＰＮまでの経路探索を全て終了すると、経路探索クライアント装置に対して、出発地Ｐ０から目的地ＰＮまでの最適な経路（この例では、出発地Ｐ０、隣接点Ｐ２、隣接点Ｐ８及び目的地ＰＮの経路）と目的地ＰＮの到着予定時刻（１５：４１：００）とを送信して、処理を終了する。経路探索が全て終了したか否かの判断は、ここでは例として、通信バッファに同じ探索ＩＤの探索要求がなくなったことを条件に経路探索が全て終了したものと判断する。
【００９８】
以上のように、本実施の形態１の経路探索システムによれば、出発地から目的地までのエリア毎にサーバを設け、受信した探索情報に基づいた探索結果を隣接するエリアを担当するサーバに順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。
【００９９】
また、詳細な経路探索をエリア毎のサーバで協調分散して行うため、各サーバの経路探索に必要な記憶容量を削減することができ、且つ探索時間の短縮化を図ることができる。
【０１００】
（実施の形態２）
本発明の実施の形態２は、地図データを分割したエリアが重複する場合を例として説明する。
【０１０１】
図９において、前述の図２と同様、太い実線は道路、網点部の領域はエリアＡ１、斜線部の領域はエリアＡ２、格子部の領域はエリアＡ３を示す。各エリア内の四角形は、サーバＳＶ１、ＳＶ２、ＳＶ３を示す。また、楕円は、エリアＡ１とエリアＡ２との境界、エリアＡ１とエリアＡ３との境界及びエリアＡ２とエリアＡ３との境界における道路の交差点であって、隣接点Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９を示す。エリアＡ１の三角形は、経路探索を開始する出発地Ｐ０を示し、エリアＡ３の逆三角形は、経路探索を終了する目的地ＰＮを示す。また、隣接点Ｐ２、Ｐ５、Ｐ６、Ｐ７及びＰ８で囲まれた領域が、エリアＡ２とエリアＡ３が重複している箇所である。
【０１０２】
この場合、例として、エリアＡ２を担当するサーバＳＶ２は、重複する隣接点Ｐ５〜Ｐ８を隣接点テーブルに登録し、エリアＡ３を担当するサーバＳＶ３は、重複する隣接点Ｐ２とＰ８を隣接点テーブルに登録する。すなわち、サーバＳＶ２とサーバＳＶ３との間でエリアの領域調整を行う必要はなく、各サーバは道路形状に合わせてエリアを自由に設定することができる。
【０１０３】
前述の本実施の形態１と同様の経路探索システムによれば、図９に示すエリアが重複する場合でも、出発地から目的地までのエリア毎にサーバを設け、受信した探索情報に基づいた探索結果を隣接するエリアを担当するサーバに順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。
【０１０４】
また、詳細な経路探索をエリア毎のサーバで協調分散して行うため、各サーバの経路探索に必要な記憶容量を削減することができ、且つ探索時間の短縮化を図ることができる。
【０１０５】
さらに、目的地がエリア内にある場合でも、目的地までの探索終了後、隣接点までの探索を行い、その探索結果を隣接エリアを担当するサーバに送信することも可能である。例えば、エリアの境界が複雑に入り組んでいる場合や隣接エリアに目的地への近道がある場合にも対応が可能となり、エリア選択の自由度は更に増すこととなる。
【０１０６】
なお、上記本実施の形態では、隣接点の通過予定時刻を用いた経路探索システムについて説明を行ったが、隣接点までの経路距離等の単調増加の要素を使用することも可能である。
【０１０７】
また、上記本実施の形態では、目的地又は隣接点を取り出して、探索開始地点から目的地又は隣接点までの経路探索を順次行うように記載しているが、ダイクストラ法を用いれば、通過予定時刻の早い地点から順次経路を求めることができる。
【０１０８】
本実施の形態において、探索開始地点からダイクストラ法を用いる手順について、図１０に示すフローチャートを用いて説明する。
【０１０９】
まず、図１１に示す展開点リストに探索開始地点を追加する(ステップＳ８１)。展開点リストには、展開点と、通過予定時刻と、展開済みか否かを示す展開済みフラグとが登録される。展開点リストに展開点を新規登録するときは、通過予定時刻を登録し、展開済みフラグは未展開として登録する。
【０１１０】
次に、展開済みフラグが未展開である点が、展開点リストにあるかどうかを判定する(ステップＳ８２)。展開済みフラグが未展開である点が、展開点リストにない場合（ステップＳ８２、Ｎｏ）、処理を終了する。
【０１１１】
一方、展開済みフラグが未展開である点が、展開点リストにある場合（ステップＳ８２、Ｙｅｓ）、未展開の点のうち、通過予定時刻が一番早い点を取り出し(ステップＳ８３)、展開済みにする(ステップＳ８４)。
【０１１２】
次に、取り出した点が、目的地か否かを判定する(ステップＳ８５)。取り出した点が、目的地の場合（ステップＳ８５、Ｙｅｓ）、到着予定時刻ｔ４が、既に探索結果テーブルに登録されている到着予定時刻ｔ３より早いかどうかを判定する(ステップＳ８６)。到着予定時刻ｔ４が、既に探索結果テーブルに登録されている到着予定時刻ｔ３より早い場合（ステップＳ８６、Ｙｅｓ）、探索結果テーブルを更新し(ステップＳ８７)し、展開済みフラグが未展開である点が、展開点リストにあるかどうかを再度判定する(ステップＳ８２)。一方、到着予定時刻ｔ４が、既に探索結果テーブルに登録されている到着予定時刻ｔ３より遅い場合（ステップＳ８６、Ｎｏ）、探索結果テーブルを更新せずに、展開済みフラグが未展開である点が、展開点リストにあるかどうかを再度判定する(ステップＳ８２)。
【０１１３】
一方、取り出した点が、目的地ではない場合（ステップＳ８５、Ｙｅｓ）、取り出した点が、隣接点か否かを判定する(ステップＳ８８)。
【０１１４】
取り出した点が、隣接点である場合（ステップＳ８８、Ｙｅｓ）、通過予定時刻ｔ２が、既に探索結果テーブルに登録されている通過予定時刻ｔ１よりも早いか否かを判定する(ステップＳ８９)。通過予定時刻ｔ２が、既に探索結果テーブルに登録されている通過予定時刻ｔ１よりも早い場合（ステップＳ８９、Ｙｅｓ）、探索結果テーブルを更新し(ステップＳ９０)、探索情報を隣接サーバに送信する(ステップＳ９１）。そして、展開済みフラグが未展開である点が、展開点リストにあるかどうかを再度判定する(ステップＳ８２)。一方、通過予定時刻ｔ２が、既に探索結果テーブルに登録されている通過予定時刻ｔ１よりも遅い場合（ステップＳ８９、Ｎｏ）、展開済みフラグが未展開である点が、展開点リストにあるかどうかを再度判定する(ステップＳ８２)。
【０１１５】
一方、取り出した点が、隣接点ではない場合（ステップＳ８８、Ｎｏ）、その点を展開する(ステップＳ９２)。すなわち、その点の回りの点を取り出だす。ここで、回りの点とは、他の点を通らなくても行ける点のことをいう。図１２に示す点P１０の場合は、点Ｐ１１〜Ｐ１５が回りの点となる。次に、展開点リストを調べ、取り出した回りの点が、登録されていない場合は通過予定時刻とともに展開点リストに追加する。一方、取り出した回りの点が、登録されている場合、通過予定時刻が既に登録されている通過時刻より早いか否かを判定する。
【０１１６】
通過予定時刻が展開点リストに既に登録されている通過予定時刻より早い場合は、展開点リストの通過予定時刻を変更し、展開済みフラグを未展開にする。一方、通過予定時刻が展開点リストに既に登録されている通過予定時刻より遅い場合は何も処理を行わない。そして、展開済みフラグが未展開である点が、展開点リストにあるかどうかを再度判定する(ステップＳ８２)。
【０１１７】
この手順を用いることにより、同じ経路を隣接点毎に探索する必要がなく、効率的に経路探索を行うことができる。
【産業上の利用可能性】
【０１１８】
以上のように、本発明にかかる経路探索方法、経路探索システム及び経路探索サーバ装置は、出発地から目的地までの探索距離の長さ、道路形状の複雑さに関係なく、細街路まで含めた詳細な経路探索を行うことができるという効果を有し、ナビゲーション装置等の経路探索方法等として有用である。
【図面の簡単な説明】
【０１１９】
【図１】本発明の実施の形態１における経路探索システムの構成を示すブロック図
【図２】本発明の実施の形態１における経路探索システムの地図データの分割例を示す図
【図３】（ａ）本発明の実施の形態１における経路探索サーバ装置ＳＶ１の隣接点テーブルを示す図（ｂ）本発明の実施の形態１における経路探索サーバ装置ＳＶ２の隣接点テーブルを示す図（ｃ）本発明の実施の形態１における経路探索サーバ装置ＳＶ３の隣接点テーブルを示す図
【図４】（ａ）本発明の実施の形態１における経路探索サーバ装置ＳＶ１の探索結果テーブルを示す図（ｂ）本発明の実施の形態１における経路探索サーバ装置ＳＶ２の探索結果テーブルを示す図（ｃ）本発明の実施の形態１における経路探索サーバ装置ＳＶ３の探索結果テーブルを示す図
【図５】本発明の実施の形態１における経路探索サーバ装置の経路探索動作を示すフローチャート
【図６】本発明の実施の形態１における経路探索サーバ装置の経路探索動作を示すフローチャート
【図７】本発明の実施の形態１における経路探索サーバ装置ＳＶ２の更新後の探索結果テーブルを示す図
【図８】本発明の実施の形態１における経路探索サーバ装置ＳＶ３の更新後の探索結果テーブルを示す図
【図９】本発明の実施の形態２における経路探索システムの地図データの分割例を示す図
【図１０】本発明の実施の形態における経路探索サーバ装置のダイクストラ法を用いた経路探索動作を示すフローチャート
【図１１】本発明の実施の形態における経路探索サーバ装置の展開点の例を示す図
【図１２】本発明の実施の形態における経路探索サーバ装置の展開点リストを示す図
【符号の説明】
【０１２０】
１１、２１、３１ 受信手段
１２、２２、３２ 経路探索手段
１３、２３、３３ 送信手段
Ａ１、Ａ２、Ａ３ エリア
ＳＶ１、ＳＶ２、ＳＶ３ 経路探索サーバ装置
Ｐ０ 出発地
ＰＮ 目的地
Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９ 隣接点
Ｐ１０、Ｐ１１、Ｐ１２、Ｐ１３、Ｐ１４ 点
【技術分野】
【０００１】
本発明は、出発地から目的地までの経路を探索する経路探索方法、経路探索システム及び経路探索サーバ装置に関するものである。
【背景技術】
【０００２】
従来のナビゲーション装置等の経路探索方法は、地図データを分割し、道路種別に従って階層化して、探索する経路数を減らすことにより、探索の効率化を図っている。この方法は、各階層の地図データをブロックに分割して、出発地と目的地とのブロックの位置関係に応じて、経路探索を行っている。すなわち、はじめに、出発地と目的地とを含む最詳細なブロックにおいて、そのブロック同士が隣接しない場合は、上位階層のブロックに連結する連結交差点までの経路を探索する。次に、上位階層のブロックに移行して、この連結交差点を出発点としてブロック内を探索する。この探索を繰り返すことにより、最終的に出発地側からの探索と目的地側からの探索とが、同一ブロック、又は隣接ブロックとなった時点で、両者の経路を連結させて経路探索を終了する。
【０００３】
以上のように、地図データを階層構造にブロック分割し、出発地と目的地とを含むブロックの階層から上位階層のブロックに順次移行して探索を行うことで、探索時間が短縮され、効率のよい経路探索を行っている（例えば、特許文献１）。
【特許文献１】特開平２−５６５９１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の経路探索方法においては、出発地と目的地との探索距離が長くなるに伴って、主要幹線道路や高速道路等の上位階層の道路を通る経路探索が行われる。また、市街地等の複雑な道路形状の場合も同様に、上位階層の地図を用いた経路探索へ移行される。このため、細街路まで含めた詳細な経路探索を行うことが困難であった。
【０００５】
本発明は、従来の問題を解決するためになされたもので、出発地から目的地までの探索距離の長さ、道路形状の複雑さに関係なく、細街路まで含めた詳細な経路探索を行うことができる経路探索方法、経路探索システム及び経路探索サーバ装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の経路探索方法は、地図データを分割したエリア毎に経路探索サーバ装置を有し、前記経路探索サーバ装置が、自エリアに隣接する第１のエリアの経路探索サーバ装置から第１の探索情報を受信する受信ステップと、前記第１の探索情報に基づいて、自エリア内の経路を探索するステップと、経路探索の探索結果に従って前記第１の探索情報を更新した第２の探索情報を、自エリアに隣接する第２のエリアの経路探索サーバ装置に送信するステップとを備えた構成を有する。
【０００７】
この構成により、受信した探索情報に基づいた探索結果を隣接するエリアを担当する経路探索サーバ装置に順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。
【０００８】
また、本発明の経路探索方法は、前記経路探索ステップが、前記第１の探索情報に含まれる探索開始地点の通過予定時刻が、自経路探索サーバ装置に登録されている前記探索開始地点の通過予定時刻より早いか否かを判定し、早いとの判定がなされたときに、自エリア内の経路を探索する構成を有する。
【０００９】
この構成により、経路探索サーバ装置の経路探索に必要な記憶容量を削減することができ、且つ探索時間の短縮化を図ることができる。
【００１０】
また、本発明の経路探索方法は、前記送信ステップが、自エリアの探索終了地点、出発地から自エリアの探索終了地点までの経路及び探索終了地点の通過予定時刻を隣接するエリアの経路探索サーバ装置に送信する構成を有する。
【００１１】
この構成により、受信した探索情報に基づいた探索結果を隣接するエリアを担当する経路探索サーバ装置に順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。
【００１２】
また、本発明の経路探索システムは、地図データを分割したエリア毎に経路探索サーバ装置を有し、前記経路探索サーバ装置は、自エリアに隣接する第１のエリアの経路探索サーバ装置から第１の探索情報を受信する受信手段と、前記第１の探索情報に基づいて、自エリア内の経路を探索する経路探索手段と、前記経路探索手段の探索結果に従って前記第１の探索情報を更新した第２の探索情報を、自エリアに隣接する第２のエリアの経路探索サーバ装置に送信する送信手段とを備えた構成を有する。
【００１３】
この構成により、受信した探索情報に基づいた探索結果を隣接するエリアを担当する経路探索サーバ装置に順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。さらに、詳細な経路探索をエリア毎の経路探索サーバ装置で協調分散して行うため、各経路探索サーバ装置の経路探索に必要な記憶容量を削減することができ、且つ探索時間の短縮化を図ることができる。
【００１４】
本発明の経路探索サーバ装置は、自エリアに隣接する第１のエリアの通信装置から第１の探索情報を受信する受信手段と、前記第１の探索情報に基づいて自エリア内の経路を探索する経路探索手段と、前記経路探索手段の探索結果に従って前記第１の探索情報を更新した第２の探索情報を、自エリアに隣接する第２のエリアの通信装置に送信する送信手段とを備えた構成を有する。
【００１５】
この構成により、受信した探索情報に基づいた探索結果を隣接するエリアを担当する経路探索サーバ装置に順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。
【００１６】
本発明の経路探索サーバ装置は、前記経路探索手段が、前記第１の探索情報に含まれる探索開始地点の通過予定時刻が、自経路探索サーバ装置に登録されている前記探索開始地点の通過予定時刻より早いか否かを判定し、早いとの判定がなされたときに、自エリア内の経路を探索する構成を有する。
【００１７】
この構成により、経路探索サーバ装置の経路探索に必要な記憶容量を削減することができ、且つ探索時間の短縮化を図ることができる。
【００１８】
本発明の経路探索サーバ装置は、前記送信手段が、自エリアの探索終了地点、出発地から自エリアの探索終了地点までの経路及び探索終了地点の通過予定時刻を隣接するエリアの通信装置に送信する構成を有する。
【００１９】
この構成により、受信した探索情報に基づいた探索結果を隣接するエリアを担当する経路探索サーバ装置に順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。
【発明の効果】
【００２０】
本発明は、出発地から目的地までの探索距離の長さ、道路形状の複雑さに関係なく、細街路まで含めた詳細な経路探索を行うことができる経路探索方法、経路探索システム及び経路探索サーバ装置を提供することができるものである。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の実施の形態について、図面を用いて説明する。
【００２２】
（実施の形態１）
図１は、本発明の実施の形態１の経路探索システムの構成を示すブロック図である。図２は、本発明の実施の形態１の経路探索システムにおける地図の分割例を説明する図である。
【００２３】
図１に示すように、本実施の形態１の経路探索システムは、地図を複数に分割したエリア毎に、予め決められたエリア内を経路探索する経路探索サーバ装置（以下、サーバという）ＳＶ１、ＳＶ２、ＳＶ３を有している。
【００２４】
サーバＳＶ１は、図２に示す予め決められたエリアＡ１を担当し、エリアＡ１内の経路探索を行う経路探索手段１２と、エリアＡ１に隣接するエリアＡ２、Ａ３をそれぞれ担当するサーバＳＶ２、ＳＶ３の各々の送信手段２３、３３から探索情報をそれぞれ受信する受信手段１１と、サーバＳＶ２、ＳＶ３の各々の受信手段２１、３１に探索情報をそれぞれ送信する送信手段１３とを有している。
【００２５】
サーバＳＶ２は、前述のように、図２に示す予め決められたエリアＡ２を担当し、エリアＡ２内の経路探索を行う経路探索手段２２と、エリアＡ２に隣接するエリアＡ１、Ａ３をそれぞれ担当するサーバＳＶ１、ＳＶ３の各々の送信手段１３、３３から探索情報をそれぞれ受信する受信手段２１と、サーバＳＶ１、ＳＶ３の各々の受信手段１１、３１に探索情報をそれぞれ送信する送信手段２３とを有している。
【００２６】
サーバＳＶ３は、前述のように、図２に示す予め決められたエリアＡ３を担当し、エリアＡ３内の経路探索を行う経路探索手段３２と、エリアＡ３と隣接するエリアＡ１、Ａ２をそれぞれ担当するサーバＳＶ１、ＳＶ２の各々の送信手段１３、２３から探索情報をそれぞれ受信する受信手段３１と、サーバＳＶ１、ＳＶ２に探索情報をそれぞれ送信する送信手段３３とを有している。
【００２７】
図２において、太い実線は道路、網点部の領域はエリアＡ１、斜線部の領域はエリアＡ２、格子部の領域はエリアＡ３を示す。各エリア内の四角形は、サーバＳＶ１、ＳＶ２、ＳＶ３を示す。また、楕円は、エリアＡ１とエリアＡ２との境界、エリアＡ１とエリアＡ３との境界及びエリアＡ２とエリアＡ３との境界における道路の交差点であって、隣接点Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９を示す。エリアＡ１の三角形は、経路探索を開始する出発地Ｐ０を示し、エリアＡ３の逆三角形は、経路探索を終了する目的地ＰＮを示す。
【００２８】
次に、図３（ａ）〜図３（ｃ）及び図４（ａ）〜図４（ｃ）を用いて、サーバＳＶ１〜ＳＶ３に登録する情報テーブルについて説明する。
【００２９】
図３（ａ）は、サーバＳＶ１に事前登録されているエリアＡ１内の各隣接点Ｐ１〜Ｐ５と、これらの隣接点で隣接するエリアを担当するサーバとを予め関連付けた隣接点テーブルを示す。
【００３０】
図３（ｂ）は、前述のように、サーバＳＶ２に事前登録されているエリアＡ２内の各隣接点Ｐ１、Ｐ２及びＰ５〜Ｐ９と、これらの隣接点で隣接するエリアを担当するサーバとを予め関連付けた隣接点テーブルを示す。
【００３１】
図３（ｃ）は、前述のように、サーバＳＶ３に事前登録されているエリアＡ３内の各隣接点Ｐ３〜Ｐ９と、これらの隣接点で隣接するエリアを担当するサーバとを予め関連付けた隣接点テーブルを示す。
【００３２】
図４（ａ）、図４（ｂ）及び図４（ｃ）は、経路探索を行う過程において、サーバＳＶ１〜ＳＶ３に登録される、探索ＩＤと、エリア内の探索開始地点（出発地又は隣接点）又は探索終了地点（隣接点又は目的地）と、その地点の出発時刻（出発地）、通過予定時刻（隣接点）又は到着予定時刻（目的地）とを関連付けた探索結果テーブルを示す。探索結果テーブルに登録する各情報については、後述の動作説明にて具体例を示し説明する。
【００３３】
上記経路探索システムの動作について、図５及び図６に示すフローチャートを用いて説明する。
【００３４】
図５において、サーバは、カーナビゲーション等の経路探索クライアント装置（図示せず）又は隣接するエリアを担当するサーバから送信された探索情報を受信手段にて受信することで処理を開始する（ステップＳ６１）。
【００３５】
サーバは、経路情報を受信すると、まず、受信した経路情報に含まれる検索ＩＤと検索開始地点を取り出し、検索ＩＤに関連付けられた、探索開始地点が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００３６】
探索ＩＤと関連付けられた、探索開始地点（隣接点）が探索結果テーブルに登録されていない場合（ステップＳ６５、Ｎｏ）、その探索ＩＤと、探索情報に含まれる探索開始地点（隣接点）と、探索情報に含まれている同点の通過予定時刻とを探索結果テーブルに新規登録し（ステップＳ６３）、その探索開始地点（隣接点）から探索終了地点（自エリアの他の隣接点又は目的地）までの経路探索を経路探索手段にて開始する（ステップＳ６４）。
【００３７】
一方、探索ＩＤと関連付けられた、探索開始地点（隣接点）が探索結果テーブルに登録されている場合（ステップＳ６５、Ｙｅｓ）、サーバは、受信した探索情報に含まれている探索開始地点（隣接点）の通過予定時刻ｔ２が、既に探索結果テーブルに登録されている同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ６６）。これは、同一の探索開始地点（隣接点）を通過する通過予定時刻が早い経路についてのみ、同点から探索終了地点（自エリアの他の隣接点又は目的地）まで経路探索を行い、通過予定時刻が遅い経路については経路探索を行わないようにするためのものである。
【００３８】
受信した探索情報に含まれる探索開始地点（隣接点）の通過予定時刻ｔ２が、既に探索結果テーブルに登録されている同点の通過予定時刻ｔ１より早い場合（ステップＳ６６、Ｙｅｓ）、探索結果テーブルの通過予定時刻を通過予定時刻ｔ２に更新し（ステップＳ６３）、その探索開始地点（隣接点）から探索終了地点（自エリアの他の隣接点又は目的地）までの経路探索を経路探索手段にて開始する（ステップＳ６４）。
【００３９】
一方、受信した探索情報に含まれる探索開始地点（隣接点）の通過予定時刻ｔ２が、既に探索テーブルに登録されている同点の通過予定時刻ｔ１より遅い場合（ステップＳ６６、Ｎｏ）、サーバは経路探索を行うことなく、処理を終了する。
【００４０】
次に、図６において、サーバが経路探索を開始した後の動作について説明する。
【００４１】
まず、経路探索を開始すると、サーバは、目的地が自エリア内に存在するか否かを判定する（ステップＳ６７）。目的地が自エリア内に存在する場合（ステップＳ６７、ＹＥＳ）、探索開始地点（出発地又は隣接点）から目的地までの経路を探索する（ステップＳ６８）。
【００４２】
さらに、ステップＳ６８で経路の探索を行った結果、目的地の到着予定時刻ｔ４が、探索結果テーブルに既に登録されている、探索情報に含まれている探索ＩＤと同じ探索ＩＤで関連付けられた目的地の到着予定時刻ｔ３より早いか否かを判定する（ステップＳ６９）。目的地の到着予定時刻ｔ４が、探索結果テーブルに既に登録されている目的地の到着予定時刻ｔ３より早い場合（ステップＳ６９、ＹＥＳ）、探索結果テーブルの到着予定時刻を到着予定時刻ｔ４に更新する（ステップＳ７０）。なお、探索情報に含まれている探索ＩＤと同じ探索ＩＤで関連付けられた目的地の到着予定時刻が、探索結果テーブルに登録されていない場合は、探索ＩＤと、探索終了地点（目的地）と、到着予定時刻ｔ４とを探索結果テーブルに新規登録する（ステップＳ７０）。
【００４３】
一方、ステップＳ６８で経路探索を行った結果、目的地の到着予定時刻ｔ４が、探索結果テーブルに既に登録されている目的地の到着予定時刻ｔ３より遅い場合（ステップＳ６９、ＮＯ）、サーバは、探索結果テーブルに新規登録又は更新を行うことなく、処理を終了する。
【００４４】
次に、目的地が自エリア外の場合（ステップＳ６７、ＮＯ）、サーバは、隣接点テーブルから登録順に隣接点を一つ取り出し（ステップＳ７１）、探索開始地点（出発地又は隣接点）から取り出した隣接点までの経路を探索する（ステップＳ７２）。なお、隣接点を取り出す順番は隣接点テーブルの登録順に限定されるものではなく、目的地に距離が近い順番等でもよい。目的地に距離が近い順番に隣接点を取り出すことにより、探索順序をコントロールできるため、無駄な探索を行うことが少なくなり、効率的な探索を行うことができる。
【００４５】
次に、サーバは、ステップＳ７２で経路の探索を行った結果、その探索終了地点（隣接点）の通過予定時刻ｔ２が、探索結果テーブルに既に登録されている、探索情報に含まれている探索ＩＤと同じ探索ＩＤで関連付けられた同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ７３）。通過予定時刻ｔ２が通過予定時刻ｔ１より早い場合（ステップＳ７３、Ｙｅｓ）、探索結果テーブルの通過予定時刻を通過予定時刻ｔ２に更新する（ステップＳ７４）。なお、探索情報に含まれている探索ＩＤと同じ探索ＩＤで関連付けられた通過予定時刻が、探索結果テーブルに登録されていない場合は、探索ＩＤと、探索終了地点（隣接点）と、同点の通過予定時刻ｔ２とを探索結果テーブルに新規登録する（ステップＳ７４）。
【００４６】
さらに、サーバは、探索結果テーブルへ各情報の新規登録又は更新を行った後、隣接点テーブルから探索終了地点（隣接点）で隣接するエリアを担当する隣接エリアのサーバを特定する。そして、そのサーバに対して、探索ＩＤ、出発地、出発時刻、目的地、自エリアの探索終了地点（同点を担当する隣接エリアのサーバにとっては、探索開始地点となる）、出発地から自エリアの探索終了地点（隣接点）までの経路及び探索終了地点（隣接点）の通過予定時刻を送信手段にて送信する（ステップＳ７５）。
【００４７】
一方、通過予定時刻ｔ２が通過予定時刻ｔ１より遅い場合（ステップＳ７３、Ｎｏ）、又はステップＳ７５で探索情報を送信した後、自エリア内に経路の探索を行っていない隣接点が他にあるか否かを隣接点テーブルを用いて判定する（ステップＳ７６）。
【００４８】
隣接点テーブルに経路の探索を行っていない隣接点が他にある場合（ステップＳ７６、Ｙｅｓ）、上述と同様に隣接点を一つ取り出し、ステップＳ７２〜Ｓ７６を繰り返す。これにより、探索開始地点（出発地又は隣接点）から自エリア内の全ての探索終了地点（隣接点）まで経路の探索を行い、各探索終了地点（隣接点）を担当する隣接エリアのサーバに対して、探索結果を順次引継いでいく。
【００４９】
一方、隣接点テーブルに経路探索を行っていない隣接点がない場合（ステップＳ７６、Ｎｏ）、サーバは、処理を終了する。
【００５０】
次に、図２に示す出発地P０から目的地ＰＮまでの経路探索を行う場合を例にとって、上述の動作を具体的に説明する。
【００５１】
まず、サーバＳＶ１は、カーナビゲーション等の経路探索クライアント装置（図示せず）から送信された、出発地Ｐ０、目的地ＰＮ及び出発時刻を含む探索情報を受信手段１１にて受信することで処理を開始する（ステップＳ６１）。
【００５２】
サーバＳＶ１は、経路情報を受信すると、まず、受信した経路情報に含まれる検索ＩＤ(この例では、１とする)と検索開始地点（出発地Ｐ０）を取り出し、検索ＩＤ(１)に関連付けられた、探索開始地点(出発地Ｐ０)が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００５３】
ここでは、探索ＩＤ（１）と関連付けられた、探索開始地点（出発地Ｐ０）が探索結果テーブルに登録されていないため（ステップＳ６５、Ｎｏ）、図４（ａ）に示すように、その探索ＩＤ（１）と探索開始地点（出発地Ｐ０）と、受信した出発時刻（この例では、１５：３０：００とする）とを探索結果テーブルに新規登録し（ステップＳ６３）、経路探索手段１２にて経路探索を開始する（ステップＳ６４）。
【００５４】
次に、経路探索を開始すると、サーバＳＶ１は、目的地ＰＮが自エリアＡ１内に存在するか否かを判定する（ステップＳ６７）。ここでは、目的地ＰＮが自エリアＡ１内に存在しないため（ステップＳ６７、ＮＯ）、隣接点テーブルから登録されている順序で隣接点Ｐ１を取り出し（ステップＳ７１）、探索開始地点（出発地Ｐ０）から探索終了地点（隣接点Ｐ１）までの経路を探索する（ステップＳ７２）。
【００５５】
サーバＳＶ１は、探索開始地点（出発地Ｐ０）から探索終了地点（隣接点Ｐ１）までの経路探索の結果、探索終了地点（隣接点Ｐ１）の通過予定時刻ｔ２が、探索結果テーブルに既に登録されている、探索情報に含まれている探索ＩＤと同じ探索ＩＤで関連付けられた同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ７３）。ここでは、探索終了地点（隣接点Ｐ１）の通過予定時刻ｔ１が、探索結果テーブルに登録されていないため、探索ＩＤ（１）と、探索終了地点（隣接点Ｐ１）と、同点の通過予定時刻（１５：３２：００）を図４（ａ）に示すように、探索結果テーブルに新規登録する（ステップＳ７４）。
【００５６】
さらに、サーバＳＶ１は、探索終了地点（隣接点Ｐ１）で隣接するエリアを担当する隣接エリアのサーバＳＶ２を隣接点テーブルにて特定する。そして、サーバＳＶ１は、サーバＳＶ２に対して、探索ＩＤ（１）、出発地Ｐ０、出発時刻（１５：３０：００）、目的地ＰＮ、自エリアの探索終了地点（隣接点Ｐ１）、出発地Ｐ０から自エリアの探索終了地点（隣接点Ｐ１）までの経路及び探索終了地点（隣接点Ｐ１）の通過予定時刻（１５：３２：００）を送信手段１３から送信する（ステップＳ７５）。
【００５７】
次に、エリアＡ１内に経路探索を行っていない隣接点が他にあるか否かを隣接点テーブルを用いて判定する（ステップＳ７６）。ここでは、経路探索を行っていない隣接点Ｐ２〜Ｐ５があるため、（ステップＳ７６、Ｙｅｓ）、上述と同様に隣接点を一つずつ取り出し、ステップＳ７２〜Ｓ７６を繰り返す。これにより、図４（ａ）に示すように、探索開始地点（出発地Ｐ０）から探索終了地点（隣接点Ｐ１〜Ｐ５）までの探索結果を探索結果テーブルへ新規登録する。また、隣接点Ｐ１及びＰ２に関する探索情報は、サーバＳＶ２に送信し、隣接点Ｐ３〜Ｐ４に関する探索情報は、サーバＳＶ３に送信し、隣接点Ｐ５に関する探索情報は、サーバＳＶ２およびサーバＳＶ３の両方に送信する。
【００５８】
サーバＳＶ１は、全ての隣接点について経路探索を行った場合（ステップＳ７６、Ｎｏ）、処理を終了する。
【００５９】
次に、サーバＳＶ１から探索情報を受信したサーバＳＶ２の動作について説明する。
【００６０】
まず、サーバＳＶ２は、サーバＳＶ１から送信された、隣接点Ｐ１に関する探索情報を受信手段２１で受信することで処理を開始する（ステップＳ６１）。
【００６１】
サーバＳＶ２は、経路情報を受信すると、まず、受信した経路情報に含まれる検索ＩＤ(１)と検索開始地点（隣接点Ｐ１）を取り出し、検索ＩＤ(１)に関連付けられた、探索開始地点(隣接点Ｐ１)が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００６２】
ここでは、探索ＩＤ（１）に関連付けられた、検索開始地点(隣接点Ｐ１)が探索結果テーブルに登録されていないため（ステップＳ６５、Ｎｏ）、図４（ｂ）に示すように、探索ＩＤ（１）と、探索情報に含まれる探索開始地点（隣接点Ｐ１）と、同点の通過予定時刻（１５：３２：００）とを探索結果テーブルに新規登録し（ステップＳ６３）、経路探索手段２２により経路探索を開始する（ステップＳ６４）。
【００６３】
次に、経路探索を開始すると、まず、サーバＳＶ２は、目的地ＰＮがエリアＡ２内に存在するか否かを判定する（ステップＳ６７）。ここでは、目的地ＰＮがエリアＡ２内に存在しないため（ステップＳ６７、Ｎｏ）、隣接点テーブルから登録されている順序で隣接点Ｐ２を取り出し（ステップＳ７１）、探索開始地点（隣接点Ｐ１）から探索終了地点（隣接点Ｐ２）までの経路探索を行う（ステップＳ７２）。ここで、サーバは、探索開始地点と探索終了地点が同一の場合の経路探索は行わないものとするため、隣接点テーブルから隣接点Ｐ１ではなく、隣接点Ｐ２を取り出す。
【００６４】
次に、サーバＳＶ２は、探索開始地点（隣接点Ｐ１）から探索終了地点（隣接点Ｐ２）までの経路探索の結果、探索終了地点（隣接点Ｐ２）の通過予定時刻ｔ２が、探索結果テーブルに既に登録されている、探索情報に含まれている探索ＩＤと同じ探索ＩＤで関連付けられた同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ７３）。ここでは、探索終了地点（隣接点Ｐ２）の通過予定時刻ｔ１が探索結果テーブルに登録されていないため、探索ＩＤ（１）と、探索終了地点（隣接点Ｐ２）と、同点の通過予定時刻（１５：３４：００）を図４（ｂ）に示すように、探索結果テーブルに新規登録する（ステップＳ７４）。
【００６５】
さらに、サーバＳＶ２は、探索終了地点（隣接点Ｐ２）で隣接するエリアを担当する隣接エリアのサーバＳＶ１を隣接点テーブルにて特定する。そして、サーバＳＶ２は、サーバＳＶ１に対して、探索ＩＤ（１）、出発地Ｐ０、出発時刻（１５：３０：００）、目的地ＰＮ、自エリアの探索終了地点（隣接点Ｐ２）、出発地Ｐ０から自エリアの探索終了地点（隣接点Ｐ２）までの経路及び探索終了地点（隣接点Ｐ２）の通過予定時刻（１５：３４：００）を送信手段２３から送信する（ステップＳ７５）。
【００６６】
次に、自エリアＡ２内に経路探索を行っていない隣接点が他にあるか否かを隣接点テーブルを用いて判定する（ステップＳ７６）。ここでは、経路探索を行っていない隣接点Ｐ５〜Ｐ９があるため（ステップＳ７６、Ｙｅｓ）、上述と同様に隣接点Ｐ５を取り出し（ステップＳ７１）、探索開始地点（隣接点Ｐ１）から探索終了地点（隣接点Ｐ５）までの経路を探索する（ステップＳ７２）。
【００６７】
探索開始地点（隣接点Ｐ１）から探索終了地点（隣接点Ｐ５）までの経路探索の結果、探索終了地点（隣接点Ｐ５）の通過予定時刻ｔ２が、探索結果テーブルに既に登録されている、同じ探索ＩＤで関連付けられた同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ７３）。ここでは、通過予定時刻ｔ１が探索結果テーブルに登録されていないため、探索ＩＤ（１）と、探索終了地点（隣接点Ｐ５）と、同点の通過予定時刻（１５：３６：００）を図４（ｂ）に示すように、探索結果テーブルに新規登録する（ステップＳ７４）。
【００６８】
さらに、サーバＳＶ２は、探索終了地点（隣接点Ｐ５）で隣接するエリアを担当する隣接エリアのサーバＳＶ１とサーバＳＶ３を隣接点テーブルにて特定する。そして、サーバＳＶ２は、サーバＳＶ１とサーバＳＶ３に対して、探索ＩＤ（１）、出発地Ｐ０、出発時刻（１５：３０：００）、目的地ＰＮ、自エリアの探索終了地点（隣接点Ｐ５）、出発地Ｐ０から自エリアの探索終了地点（隣接点Ｐ５）までの経路及び探索終了地点（隣接点Ｐ５）の通過予定時刻（１５：３６：００）を送信手段２３から送信する（ステップＳ７５）。
【００６９】
上述と同様に、探索開始地点（隣接点Ｐ１）から探索終了地点（隣接点Ｐ６〜Ｐ９）までの経路探索を行い、探索終了地点（隣接点Ｐ６〜Ｐ９）の通過予定時刻を図４（ｂ）に示すように探索結果テーブルに新規登録し（ステップＳ７４）、隣接点Ｐ６〜Ｐ９を担当するサーバＳＶ３に対して、探索情報を送信手段２３にて送信する（ステップＳ７５）。サーバＳＶ２は、全ての隣接点について経路の探索を行った後、処理を終了する。
【００７０】
次に、サーバＳＶ２は、サーバＳＶ１から送信された、隣接点Ｐ２に関する探索情報を受信手段２１で受信することで処理を開始する（ステップＳ６１）。
【００７１】
サーバＳＶ２は、まず、受信した経路情報に含まれる検索ＩＤ(１)と検索開始地点（隣接点Ｐ２）を取り出し、検索ＩＤ(１)に関連付けられた、探索開始地点(隣接点Ｐ２)が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００７２】
ここでは、探索ＩＤ（１）と関連付けられた、探索開始地点（隣接点Ｐ２）が探索結果テーブルに登録されているため（ステップＳ６５、Ｙｅｓ）、受信した探索情報に含まれている探索開始地点（隣接点）の通過予定時刻ｔ２が、既に探索結果テーブルに登録されている同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ６６）。ここでは、受信した探索情報に含まれる探索開始地点（隣接点Ｐ２）の通過予定時刻ｔ２（１５：３３：００）が、既に探索結果テーブルに登録されている同点の通過予定時刻ｔ１（１５：３４：００）より早いため（ステップＳ６６、Ｙｅｓ）、図７に示すように探索開始地点（隣接点Ｐ２）の通過予定時刻を通過予定時刻ｔ２（１５：３３：００）に更新し（ステップＳ６３）、経路探索手段２２により経路探索を開始する（ステップＳ６４）。
【００７３】
次に、経路探索を開始すると、サーバＳＶ２は、目的地ＰＮがエリアＡ２内に存在するか否かを判定する（ステップＳ６７）。ここでは、目的地ＰＮがエリアＡ２内に存在しないため（ステップＳ６７、Ｎｏ）、隣接点テーブルから登録されている順序で隣接点Ｐ１を取り出し（ステップＳ７１）、探索開始地点（隣接点Ｐ２）から探索終了地点（隣接点Ｐ１）までの経路の探索を行う（ステップＳ７２）。
【００７４】
次に、サーバＳＶ２は、探索開始地点（隣接点Ｐ２）から探索終了地点（隣接点Ｐ１）までの経路探索の結果、探索終了地点（隣接点Ｐ１）の通過予定時刻ｔ２が、探索結果テーブルに既に登録されている同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ７３）。ここでは、探索終了地点（隣接点Ｐ１）の通過予定時刻ｔ２（１５：３５：００）が、探索結果テーブルに登録されている同点の通過予定時刻ｔ１（１５：３２：００）より遅いため（ステップＳ７３、Ｎｏ）、次に、自エリアＡ２内に経路探索を行っていない隣接点が他にあるか否かを隣接点テーブルを用いて判定する（ステップＳ７６）。ここでは、経路探索を行っていない隣接点Ｐ５〜Ｐ９があるため、（ステップＳ７６、Ｙｅｓ）、上述と同様に隣接点Ｐ５を取り出し（ステップＳ７１）、探索開始地点（隣接点Ｐ２）から探索終了地点（隣接点Ｐ５）までの経路を探索する（ステップＳ７２）。
【００７５】
探索開始地点（隣接点Ｐ２）から探索終了地点（隣接点Ｐ５）までの経路探索の結果、探索終了地点（隣接点Ｐ５）の通過予定時刻ｔ２が、探索結果テーブルに既に登録されている同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ７３）。ここでは、探索終了地点（隣接点Ｐ５）の通過予定時刻ｔ２（１５：３４：４５）が、探索結果テーブルに既に登録されている同点の通過予定時刻ｔ１（１５：３６：００）より早いため（ステップＳ７３、Ｙｅｓ）、探索結果テーブルにおける探索終了地点（隣接点Ｐ５）の通過予定時刻を図７に示すように更新する（ステップＳ７４）。
【００７６】
さらに、サーバＳＶ２は、探索終了地点（隣接点Ｐ５）で隣接するエリアを担当する隣接エリアのサーバＳＶ１とサーバＳＶ３を隣接点テーブルにて特定する。そして、サーバＳＶ２は、サーバＳＶ１とサーバＳＶ３に対して、探索ＩＤ（１）、出発地Ｐ０、出発時刻（１５：３０：００）、目的地ＰＮ、自エリアの探索終了地点（隣接点Ｐ５）、出発地Ｐ０から自エリアの探索終了地点（隣接点Ｐ５）までの経路及び探索終了地点（隣接点Ｐ５）の通過予定時刻（１５：３４：４５）を送信手段２３にて送信する（ステップＳ７５）。
【００７７】
上述と同様に、探索開始地点（隣接点Ｐ２）から探索終了地点（隣接点Ｐ６〜Ｐ９）までの経路探索を行い、探索終了地点（隣接点Ｐ６〜Ｐ９）の通過予定時刻について、図７に示すように探索結果テーブルを更新し（ステップＳ７４）、隣接点Ｐ６〜Ｐ９を担当するサーバＳＶ３に探索情報を送信手段２３にて送信する（ステップＳ７５）。サーバＳＶ２は、全ての隣接点について経路の探索を行った後、処理を終了する。
【００７８】
次に、サーバＳＶ１から探索情報を受信したサーバＳＶ３の動作について説明する。
【００７９】
サーバＳＶ３は、サーバＳＶ１から送信された、隣接点Ｐ３に関する探索情報を受信手段３１で受信することで処理を開始する（ステップＳ６１）。
【００８０】
サーバＳＶ３は、まず、受信した経路情報に含まれる検索ＩＤ(１)と検索開始地点（隣接点Ｐ３）を取り出し、検索ＩＤ(１)に関連付けられた、探索開始地点(隣接点Ｐ３)が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００８１】
ここでは、探索ＩＤ（１）が、探索結果テーブルに登録されていないため（ステップＳ６５、Ｎｏ）、図４（ｃ）に示すように、探索ＩＤ（１）と、受信した探索開始地点（隣接点Ｐ３）と、同点の通過予定時刻（１５：３５：００）とを探索テーブルに新規登録し（ステップＳ６３）、経路探索手段３２により経路探索を開始する（ステップＳ６４）。
【００８２】
次に、経路探索を開始すると、サーバＳＶ３は、目的地ＰＮがエリアＡ３内に存在するか否かを判定する（ステップＳ６７）。ここでは、目的地ＰＮがエリアＡ３内に存在するため（ステップＳ６７、Ｙｅｓ）、探索開始地点（隣接点Ｐ３）から探索終了地点（目的地ＰＮ）までの経路の探索を行う（ステップＳ６８）。
【００８３】
次に、サーバＳＶ３は、探索開始地点（隣接点Ｐ３）から探索終了地点（目的地ＰＮ）までの経路探索の結果、探索終了地点（目的地ＰＮ）の到着予定時刻ｔ４が、探索結果テーブルに既に登録されている同点の到着予定時刻ｔ３より早いか否かを判定する（ステップＳ６９）。ここでは、目的地ＰＮの到着予定時刻ｔ３が探索結果テーブルに登録されていないため、探索ＩＤ（１）と、探索終了地点（目的地ＰＮ）と、同点の到着予定時刻（１５：４８：００）とを探索結果テーブルに新規登録する（ステップＳ７０）。そして、サーバＳＶ３は処理を終了する。
【００８４】
次に、サーバＳＶ３は、サーバＳＶ１から送信された、隣接点Ｐ４に関する探索情報を受信手段３１で受信することで処理を開始する（ステップＳ６１）。
【００８５】
サーバＳＶ３は、まず、受信した経路情報に含まれる検索ＩＤ(１)と検索開始地点（隣接点Ｐ４）を取り出し、検索ＩＤ(１)に関連付けられた、探索開始地点(隣接点Ｐ４)が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００８６】
探索ＩＤ（１）と関連付けられた、探索開始地点（隣接点Ｐ４）が探索テーブルに登録されていないため（ステップＳ６５、Ｎｏ）、その探索ＩＤ（１）と、探索開始地点（隣接点Ｐ４）と、同点の通過予定時刻（１５：３３：００）とを図４（ｃ）に示すように、探索結果テーブルに新規登録し（ステップＳ６３）、経路探索手段３２により経路探索を開始する（ステップＳ６４）。
【００８７】
次に、経路探索を開始すると、サーバＳＶ３は、目的地ＰＮが自エリアＡ３内に存在するか否かを判定する（ステップＳ６７）。ここでは、目的地ＰＮが自エリアＡ３内に存在するため（ステップＳ６７、Ｙｅｓ）、探索開始地点（隣接点Ｐ４）から探索終了地点（目的地ＰＮ）までの経路の探索を行う（ステップＳ６８）。
【００８８】
次に、サーバＳＶ３は、探索開始地点（隣接点Ｐ４）から探索終了地点（目的地ＰＮ）までの経路探索の結果、探索終了地点（目的地ＰＮ）の到着予定時刻ｔ４が、探索結果テーブルに既に登録されている同点の到着予定時刻ｔ３より早いか否かを判定する（ステップＳ６９）。ここでは、到着予定時刻ｔ４（１５：４３：００）が到着予定時刻ｔ３（１５：４８：００）より早いため（ステップＳ６９、Ｙｅｓ）、探索結果テーブルの探索終了地点（目的地ＰＮ）の到着予定時刻を到着予定時刻ｔ４（１５：４３：００）に更新する（ステップＳ７０）。そして、サーバＳＶ３は処理を終了する。
【００８９】
上述と同様に、サーバＳＶ３は、サーバＳＶ１から送信された、隣接点Ｐ５に関する探索情報をもとに、探索結果テーブルの探索開始地点（隣接点Ｐ５）の通過予定時刻（１５：３５：００）を図４（ｃ）に示すように、新規登録する（ステップＳ６３）。また、探索開始地点（隣接点Ｐ５）から探索終了地点（目的地ＰＮ）までの経路探索を行い、図４（ｃ）に示すように、探索終了地点（目的地ＰＮ）の到着予定時刻を到着予定時刻ｔ４（１５：４２：００）に更新する（ステップＳ７０）。そして、サーバＳＶ３は処理を終了する。
【００９０】
次に、サーバＳＶ２から探索情報を受信したサーバＳＶ３の動作について説明する。
【００９１】
サーバＳＶ３は、サーバＳＶ２から送信された、隣接点Ｐ５に関する探索情報を受信手段３１で受信することで処理を開始する（ステップＳ６１）。
【００９２】
サーバＳＶ３は、まず、受信した経路情報に含まれる検索ＩＤ(１)と検索開始地点（隣接点Ｐ５）を取り出し、検索ＩＤ(１)に関連付けられた、探索開始地点(隣接点Ｐ５)が結果テーブルに登録されているかどうかを確認する(ステップＳ６５)。
【００９３】
探索ＩＤ（１）と関連付けられた、探索開始地点（隣接点Ｐ５）が探索テーブルに登録されているため（ステップＳ６５、Ｙｅｓ）、受信した探索情報に含まれる探索開始点（隣接点Ｐ５）の通過予定時刻ｔ２が、探索テーブルに既に登録されている同点の通過予定時刻ｔ１より早いか否かを判定する（ステップＳ６６）。
【００９４】
ここでは、通過予定時刻ｔ２（１５：３４：４５）が通過予定時刻ｔ１（１５：３５：００）より早いため（ステップＳ６６、Ｙｅｓ）、図８に示すように、探索結果テーブルの探索開始地点（隣接点Ｐ５）の通過予定時刻を１５：３４：４５に更新し（ステップＳ６３）、経路探索を開始する（ステップＳ６４）。
【００９５】
次に、経路探索を開始すると、サーバＳＶ３は、目的地ＰＮがエリアＡ３内に存在するか否かを判定する（ステップＳ６７）。ここでは、目的地ＰＮがエリアＡ３内に存在するため（ステップＳ６７、Ｙｅｓ）、探索開始地点（隣接点Ｐ５）から探索終了地点（目的地ＰＮ）までの経路の探索を行う（ステップＳ６８）。
【００９６】
次に、サーバＳＶ３は、探索開始地点（隣接点Ｐ５）から探索終了地点（目的地ＰＮ）までの経路探索の結果、探索終了地点（目的地ＰＮ）の到着予定時刻ｔ４が、探索結果テーブルに既に登録されている到着予定時刻ｔ３より早いか否かを判定する（ステップＳ６９）。ここでは、到着予定時刻ｔ４（１５：４３：３０）が到着予定時刻ｔ３（１５：４３：００）より遅いため（ステップＳ６９、Ｎｏ）、探索結果テーブルの更新を行うことなく、サーバＳＶ３は処理を終了する。
【００９７】
上述と同様に、サーバＳＶ３は、サーバＳＶ２から送信された、隣接点Ｐ６〜Ｐ９に関する探索情報を受信し、経路探索を行った結果に従って、図８に示すように探索結果テーブルを更新する（ステップＳ７０）。サーバＳＶ３は、目的地ＰＮまでの経路探索を全て終了すると、経路探索クライアント装置に対して、出発地Ｐ０から目的地ＰＮまでの最適な経路（この例では、出発地Ｐ０、隣接点Ｐ２、隣接点Ｐ８及び目的地ＰＮの経路）と目的地ＰＮの到着予定時刻（１５：４１：００）とを送信して、処理を終了する。経路探索が全て終了したか否かの判断は、ここでは例として、通信バッファに同じ探索ＩＤの探索要求がなくなったことを条件に経路探索が全て終了したものと判断する。
【００９８】
以上のように、本実施の形態１の経路探索システムによれば、出発地から目的地までのエリア毎にサーバを設け、受信した探索情報に基づいた探索結果を隣接するエリアを担当するサーバに順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。
【００９９】
また、詳細な経路探索をエリア毎のサーバで協調分散して行うため、各サーバの経路探索に必要な記憶容量を削減することができ、且つ探索時間の短縮化を図ることができる。
【０１００】
（実施の形態２）
本発明の実施の形態２は、地図データを分割したエリアが重複する場合を例として説明する。
【０１０１】
図９において、前述の図２と同様、太い実線は道路、網点部の領域はエリアＡ１、斜線部の領域はエリアＡ２、格子部の領域はエリアＡ３を示す。各エリア内の四角形は、サーバＳＶ１、ＳＶ２、ＳＶ３を示す。また、楕円は、エリアＡ１とエリアＡ２との境界、エリアＡ１とエリアＡ３との境界及びエリアＡ２とエリアＡ３との境界における道路の交差点であって、隣接点Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９を示す。エリアＡ１の三角形は、経路探索を開始する出発地Ｐ０を示し、エリアＡ３の逆三角形は、経路探索を終了する目的地ＰＮを示す。また、隣接点Ｐ２、Ｐ５、Ｐ６、Ｐ７及びＰ８で囲まれた領域が、エリアＡ２とエリアＡ３が重複している箇所である。
【０１０２】
この場合、例として、エリアＡ２を担当するサーバＳＶ２は、重複する隣接点Ｐ５〜Ｐ８を隣接点テーブルに登録し、エリアＡ３を担当するサーバＳＶ３は、重複する隣接点Ｐ２とＰ８を隣接点テーブルに登録する。すなわち、サーバＳＶ２とサーバＳＶ３との間でエリアの領域調整を行う必要はなく、各サーバは道路形状に合わせてエリアを自由に設定することができる。
【０１０３】
前述の本実施の形態１と同様の経路探索システムによれば、図９に示すエリアが重複する場合でも、出発地から目的地までのエリア毎にサーバを設け、受信した探索情報に基づいた探索結果を隣接するエリアを担当するサーバに順次引継ぐことにより、出発地から目的地までのエリアを連続して、詳細な経路探索を行うことができる。
【０１０４】
また、詳細な経路探索をエリア毎のサーバで協調分散して行うため、各サーバの経路探索に必要な記憶容量を削減することができ、且つ探索時間の短縮化を図ることができる。
【０１０５】
さらに、目的地がエリア内にある場合でも、目的地までの探索終了後、隣接点までの探索を行い、その探索結果を隣接エリアを担当するサーバに送信することも可能である。例えば、エリアの境界が複雑に入り組んでいる場合や隣接エリアに目的地への近道がある場合にも対応が可能となり、エリア選択の自由度は更に増すこととなる。
【０１０６】
なお、上記本実施の形態では、隣接点の通過予定時刻を用いた経路探索システムについて説明を行ったが、隣接点までの経路距離等の単調増加の要素を使用することも可能である。
【０１０７】
また、上記本実施の形態では、目的地又は隣接点を取り出して、探索開始地点から目的地又は隣接点までの経路探索を順次行うように記載しているが、ダイクストラ法を用いれば、通過予定時刻の早い地点から順次経路を求めることができる。
【０１０８】
本実施の形態において、探索開始地点からダイクストラ法を用いる手順について、図１０に示すフローチャートを用いて説明する。
【０１０９】
まず、図１１に示す展開点リストに探索開始地点を追加する(ステップＳ８１)。展開点リストには、展開点と、通過予定時刻と、展開済みか否かを示す展開済みフラグとが登録される。展開点リストに展開点を新規登録するときは、通過予定時刻を登録し、展開済みフラグは未展開として登録する。
【０１１０】
次に、展開済みフラグが未展開である点が、展開点リストにあるかどうかを判定する(ステップＳ８２)。展開済みフラグが未展開である点が、展開点リストにない場合（ステップＳ８２、Ｎｏ）、処理を終了する。
【０１１１】
一方、展開済みフラグが未展開である点が、展開点リストにある場合（ステップＳ８２、Ｙｅｓ）、未展開の点のうち、通過予定時刻が一番早い点を取り出し(ステップＳ８３)、展開済みにする(ステップＳ８４)。
【０１１２】
次に、取り出した点が、目的地か否かを判定する(ステップＳ８５)。取り出した点が、目的地の場合（ステップＳ８５、Ｙｅｓ）、到着予定時刻ｔ４が、既に探索結果テーブルに登録されている到着予定時刻ｔ３より早いかどうかを判定する(ステップＳ８６)。到着予定時刻ｔ４が、既に探索結果テーブルに登録されている到着予定時刻ｔ３より早い場合（ステップＳ８６、Ｙｅｓ）、探索結果テーブルを更新し(ステップＳ８７)し、展開済みフラグが未展開である点が、展開点リストにあるかどうかを再度判定する(ステップＳ８２)。一方、到着予定時刻ｔ４が、既に探索結果テーブルに登録されている到着予定時刻ｔ３より遅い場合（ステップＳ８６、Ｎｏ）、探索結果テーブルを更新せずに、展開済みフラグが未展開である点が、展開点リストにあるかどうかを再度判定する(ステップＳ８２)。
【０１１３】
一方、取り出した点が、目的地ではない場合（ステップＳ８５、Ｙｅｓ）、取り出した点が、隣接点か否かを判定する(ステップＳ８８)。
【０１１４】
取り出した点が、隣接点である場合（ステップＳ８８、Ｙｅｓ）、通過予定時刻ｔ２が、既に探索結果テーブルに登録されている通過予定時刻ｔ１よりも早いか否かを判定する(ステップＳ８９)。通過予定時刻ｔ２が、既に探索結果テーブルに登録されている通過予定時刻ｔ１よりも早い場合（ステップＳ８９、Ｙｅｓ）、探索結果テーブルを更新し(ステップＳ９０)、探索情報を隣接サーバに送信する(ステップＳ９１）。そして、展開済みフラグが未展開である点が、展開点リストにあるかどうかを再度判定する(ステップＳ８２)。一方、通過予定時刻ｔ２が、既に探索結果テーブルに登録されている通過予定時刻ｔ１よりも遅い場合（ステップＳ８９、Ｎｏ）、展開済みフラグが未展開である点が、展開点リストにあるかどうかを再度判定する(ステップＳ８２)。
【０１１５】
一方、取り出した点が、隣接点ではない場合（ステップＳ８８、Ｎｏ）、その点を展開する(ステップＳ９２)。すなわち、その点の回りの点を取り出だす。ここで、回りの点とは、他の点を通らなくても行ける点のことをいう。図１２に示す点P１０の場合は、点Ｐ１１〜Ｐ１５が回りの点となる。次に、展開点リストを調べ、取り出した回りの点が、登録されていない場合は通過予定時刻とともに展開点リストに追加する。一方、取り出した回りの点が、登録されている場合、通過予定時刻が既に登録されている通過時刻より早いか否かを判定する。
【０１１６】
通過予定時刻が展開点リストに既に登録されている通過予定時刻より早い場合は、展開点リストの通過予定時刻を変更し、展開済みフラグを未展開にする。一方、通過予定時刻が展開点リストに既に登録されている通過予定時刻より遅い場合は何も処理を行わない。そして、展開済みフラグが未展開である点が、展開点リストにあるかどうかを再度判定する(ステップＳ８２)。
【０１１７】
この手順を用いることにより、同じ経路を隣接点毎に探索する必要がなく、効率的に経路探索を行うことができる。
【産業上の利用可能性】
【０１１８】
以上のように、本発明にかかる経路探索方法、経路探索システム及び経路探索サーバ装置は、出発地から目的地までの探索距離の長さ、道路形状の複雑さに関係なく、細街路まで含めた詳細な経路探索を行うことができるという効果を有し、ナビゲーション装置等の経路探索方法等として有用である。
【図面の簡単な説明】
【０１１９】
【図１】本発明の実施の形態１における経路探索システムの構成を示すブロック図
【図２】本発明の実施の形態１における経路探索システムの地図データの分割例を示す図
【図３】（ａ）本発明の実施の形態１における経路探索サーバ装置ＳＶ１の隣接点テーブルを示す図（ｂ）本発明の実施の形態１における経路探索サーバ装置ＳＶ２の隣接点テーブルを示す図（ｃ）本発明の実施の形態１における経路探索サーバ装置ＳＶ３の隣接点テーブルを示す図
【図４】（ａ）本発明の実施の形態１における経路探索サーバ装置ＳＶ１の探索結果テーブルを示す図（ｂ）本発明の実施の形態１における経路探索サーバ装置ＳＶ２の探索結果テーブルを示す図（ｃ）本発明の実施の形態１における経路探索サーバ装置ＳＶ３の探索結果テーブルを示す図
【図５】本発明の実施の形態１における経路探索サーバ装置の経路探索動作を示すフローチャート
【図６】本発明の実施の形態１における経路探索サーバ装置の経路探索動作を示すフローチャート
【図７】本発明の実施の形態１における経路探索サーバ装置ＳＶ２の更新後の探索結果テーブルを示す図
【図８】本発明の実施の形態１における経路探索サーバ装置ＳＶ３の更新後の探索結果テーブルを示す図
【図９】本発明の実施の形態２における経路探索システムの地図データの分割例を示す図
【図１０】本発明の実施の形態における経路探索サーバ装置のダイクストラ法を用いた経路探索動作を示すフローチャート
【図１１】本発明の実施の形態における経路探索サーバ装置の展開点の例を示す図
【図１２】本発明の実施の形態における経路探索サーバ装置の展開点リストを示す図
【符号の説明】
【０１２０】
１１、２１、３１ 受信手段
１２、２２、３２ 経路探索手段
１３、２３、３３ 送信手段
Ａ１、Ａ２、Ａ３ エリア
ＳＶ１、ＳＶ２、ＳＶ３ 経路探索サーバ装置
Ｐ０ 出発地
ＰＮ 目的地
Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９ 隣接点
Ｐ１０、Ｐ１１、Ｐ１２、Ｐ１３、Ｐ１４ 点
【特許請求の範囲】
【請求項１】
地図データを分割したエリア毎に経路探索サーバ装置を有し、
前記経路探索サーバ装置は、
自エリアに隣接する第１のエリアの経路探索サーバ装置から第１の探索情報を受信する受信ステップと、
前記第１の探索情報に基づいて、自エリア内の経路を探索する経路探索ステップと、
経路探索の探索結果に従って前記第１の探索情報を更新した第２の探索情報を、自エリアに隣接する第２のエリアの経路探索サーバ装置に送信する送信ステップとを備えたことを特徴とする経路探索方法。
【請求項２】
前記経路探索ステップは、
前記第１の探索情報に含まれる探索開始地点の通過予定時刻が、自経路探索サーバ装置に登録されている前記探索開始地点の通過予定時刻より早いか否かを判定し、早いとの判定がなされたときに、自エリア内の経路を探索することを特徴とする請求項１記載の経路探索方法。
【請求項３】
前記送信ステップは、
自エリアの探索終了地点、出発地から自エリアの探索終了地点までの経路及び探索終了地点の通過予定時刻を隣接するエリアの経路探索サーバ装置に送信することを特徴とする請求項１又は２記載の経路探索方法。
【請求項４】
地図データを分割したエリア毎に経路探索サーバ装置を有し、
前記経路探索サーバ装置は、
自エリアに隣接する第１のエリアの経路探索サーバ装置から第１の探索情報を受信する受信手段と、
前記第１の探索情報に基づいて、自エリア内の経路を探索する経路探索手段と、
前記経路探索手段の探索結果に従って前記第１の探索情報を更新した第２の探索情報を、自エリアに隣接する第２のエリアの経路探索サーバ装置に送信する送信手段とを備えたことを特徴とする経路探索システム。
【請求項５】
自エリアに隣接する第１のエリアの通信装置から第１の探索情報を受信する受信手段と、
前記第１の探索情報に基づいて自エリア内の経路を探索する経路探索手段と、
前記経路探索手段の探索結果に従って前記第１の探索情報を更新した第２の探索情報を、自エリアに隣接する第２のエリアの通信装置に送信する送信手段とを備えたことを特徴とする経路探索サーバ装置。
【請求項６】
前記経路探索手段は、
前記第１の探索情報に含まれる探索開始地点の通過予定時刻が、自経路探索サーバ装置に登録されている前記探索開始地点の通過予定時刻より早いか否かを判定し、早いとの判定がなされたときに、自エリア内の経路を探索することを特徴とする請求項５記載の経路探索サーバ装置。
【請求項７】
前記送信手段は、
自エリアの探索終了地点、出発地から自エリアの探索終了地点までの経路及び探索終了地点の通過予定時刻を隣接するエリアの通信装置に送信することを特徴とする請求項５又は６記載の経路探索サーバ装置。
【請求項１】
地図データを分割したエリア毎に経路探索サーバ装置を有し、
前記経路探索サーバ装置は、
自エリアに隣接する第１のエリアの経路探索サーバ装置から第１の探索情報を受信する受信ステップと、
前記第１の探索情報に基づいて、自エリア内の経路を探索する経路探索ステップと、
経路探索の探索結果に従って前記第１の探索情報を更新した第２の探索情報を、自エリアに隣接する第２のエリアの経路探索サーバ装置に送信する送信ステップとを備えたことを特徴とする経路探索方法。
【請求項２】
前記経路探索ステップは、
前記第１の探索情報に含まれる探索開始地点の通過予定時刻が、自経路探索サーバ装置に登録されている前記探索開始地点の通過予定時刻より早いか否かを判定し、早いとの判定がなされたときに、自エリア内の経路を探索することを特徴とする請求項１記載の経路探索方法。
【請求項３】
前記送信ステップは、
自エリアの探索終了地点、出発地から自エリアの探索終了地点までの経路及び探索終了地点の通過予定時刻を隣接するエリアの経路探索サーバ装置に送信することを特徴とする請求項１又は２記載の経路探索方法。
【請求項４】
地図データを分割したエリア毎に経路探索サーバ装置を有し、
前記経路探索サーバ装置は、
自エリアに隣接する第１のエリアの経路探索サーバ装置から第１の探索情報を受信する受信手段と、
前記第１の探索情報に基づいて、自エリア内の経路を探索する経路探索手段と、
前記経路探索手段の探索結果に従って前記第１の探索情報を更新した第２の探索情報を、自エリアに隣接する第２のエリアの経路探索サーバ装置に送信する送信手段とを備えたことを特徴とする経路探索システム。
【請求項５】
自エリアに隣接する第１のエリアの通信装置から第１の探索情報を受信する受信手段と、
前記第１の探索情報に基づいて自エリア内の経路を探索する経路探索手段と、
前記経路探索手段の探索結果に従って前記第１の探索情報を更新した第２の探索情報を、自エリアに隣接する第２のエリアの通信装置に送信する送信手段とを備えたことを特徴とする経路探索サーバ装置。
【請求項６】
前記経路探索手段は、
前記第１の探索情報に含まれる探索開始地点の通過予定時刻が、自経路探索サーバ装置に登録されている前記探索開始地点の通過予定時刻より早いか否かを判定し、早いとの判定がなされたときに、自エリア内の経路を探索することを特徴とする請求項５記載の経路探索サーバ装置。
【請求項７】
前記送信手段は、
自エリアの探索終了地点、出発地から自エリアの探索終了地点までの経路及び探索終了地点の通過予定時刻を隣接するエリアの通信装置に送信することを特徴とする請求項５又は６記載の経路探索サーバ装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２００６−２９２６６７（Ｐ２００６−２９２６６７Ａ）
【公開日】平成１８年１０月２６日（２００６．１０．２６）
【国際特許分類】
【出願番号】特願２００５−１１６８８３（Ｐ２００５−１１６８８３）
【出願日】平成１７年４月１４日（２００５．４．１４）
【出願人】（０００００５８２１）松下電器産業株式会社 (73,050)
【Ｆターム（参考）】
【公開日】平成１８年１０月２６日（２００６．１０．２６）
【国際特許分類】
【出願日】平成１７年４月１４日（２００５．４．１４）
【出願人】（０００００５８２１）松下電器産業株式会社 (73,050)
【Ｆターム（参考）】
[ Back to top ]