(57)【要約】【課題】境界を跨ぐ回数を低減可能である可能性を高める。【解決手段】地図を分割する複数の第１領域毎に割り当てられ、割り当てられた前記第１領域内の経路を探索する複数の第１経路探索サーバと、前記地図を分割する複数の領域であって前記第１領域の境界の一部を内部に含む第２領域毎に割り当てられ、割り当てられた前記第２領域内の経路を探索する複数の第２経路探索サーバと、前記第１経路探索サーバと前記第２経路探索サーバとのいずれかを選択して経路を探索させるサーバ決定部と、を備える経路探索システムを構成する。【選択図】図１
2018132322.tif 000002
【特許請求の範囲】
【請求項１】
地図を分割する複数の第１領域毎に割り当てられ、割り当てられた前記第１領域内の経路を探索する複数の第１経路探索サーバと、
前記地図を分割する複数の領域であって前記第１領域の境界の一部を内部に含む第２領域毎に割り当てられ、割り当てられた前記第２領域内の経路を探索する複数の第２経路探索サーバと、
前記第１経路探索サーバと前記第２経路探索サーバとのいずれかを選択して経路を探索させるサーバ決定部と、
を備える経路探索システム。
【請求項２】
前記サーバ決定部は、
前記第１経路探索サーバによって出発地から目的地まで経路が探索された場合に使用される前記第１経路探索サーバの数が、前記第２経路探索サーバによって前記出発地から前記目的地まで経路が探索された場合に使用される前記第２経路探索サーバの数よりも少ない場合に、前記第１経路探索サーバを選択し、多い場合に前記第２経路探索サーバを選択する、
請求項１に記載の経路探索システム。
【請求項３】
前記サーバ決定部は、
前記出発地と前記目的地との間に存在する前記第１領域の境界の数が前記第２領域よりも少ない場合に、前記第１経路探索サーバを選択し、多い場合に前記第２経路探索サーバを選択する、
請求項２に記載の経路探索システム。
【請求項４】
選択済のサーバによる探索が不可能である場合に、未選択のサーバが選択される、
請求項１〜請求項３のいずれかに記載の経路探索システム。
【請求項５】
前記第２領域の境界は、前記第１領域の境界から緯度方向と経度方向との少なくとも１方向にずれた位置に存在し、
前記第２領域は、複数の前記第１領域と重複している、
請求項１〜請求項４のいずれかに記載の経路探索システム。
【請求項６】
コンピュータを、
地図を分割する複数の第１領域毎に割り当てられ、割り当てられた前記第１領域内の経路を探索する複数の第１経路探索サーバと、前記地図を分割する複数の領域であって前記第１領域の境界の一部を内部に含む第２領域毎に割り当てられ、割り当てられた前記第２領域内の経路を探索する複数の第２経路探索サーバと、のいずれかを選択して経路を探索させるサーバ決定部、
として機能させる探索サーバ決定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索システムおよび探索サーバ決定プログラムに関する。
【背景技術】
【０００２】
従来、経路を探索する技術が知られている。経路の探索は種々の技術によって実現されており、例えば、特許文献１には、地図データを分割したエリア毎に経路探索サーバ装置を有し、各エリアの経路を各エリアの経路探索サーバ装置で探索する技術が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００６−２９２６６７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来の技術のように、複数の経路探索サーバ装置で異なるエリアを担当して経路探索をする場合、エリアの境界を跨ぐ経路が探索される際に、経路探索サーバ装置間での通信を介して探索済の経路や目的地等の情報の受け渡しを行う必要がある。従って、エリアの境界を跨ぐ回数が多いほど経路の探索以外の付加的な処理が多くなってしまう。
本発明は、上記課題にかんがみてなされたもので、境界を跨ぐ回数を低減可能である可能性を高めることを目的とする。
【課題を解決するための手段】
【０００５】
上記の目的を達成するため、経路探索システムは、地図を分割する複数の第１領域毎に割り当てられ、割り当てられた第１領域内の経路を探索する複数の第１経路探索サーバと、地図を分割する複数の領域であって第１領域の境界の一部を内部に含む第２領域毎に割り当てられ、割り当てられた第２領域内の経路を探索する複数の第２経路探索サーバと、第１経路探索サーバと第２経路探索サーバとのいずれかを選択して経路を探索させるサーバ決定部と、を備える。
【０００６】
さらに、上記の目的を達成するため、探索サーバ決定プログラムは、コンピュータを、地図を分割する複数の第１領域毎に割り当てられ、割り当てられた第１領域内の経路を探索する複数の第１経路探索サーバと、地図を分割する複数の領域であって第１領域の境界の一部を内部に含む第２領域毎に割り当てられ、割り当てられた第２領域内の経路を探索する複数の第２経路探索サーバと、のいずれかを選択して経路を探索させるサーバ決定部、として機能させる。
【０００７】
すなわち、経路探索システム、プログラムでは、地図が第１領域および第２領域に分割され、第１領域に第１経路探索サーバが割り当てられ、第２領域に第２経路探索サーバが割り当てられる。この構成においては、第１経路探索サーバが担当する第１領域と第２経路探索サーバが担当する第２領域とが異なるため、第１経路探索サーバで経路の探索が行われる場合と第２経路探索サーバで経路の探索が行われる場合とで、領域の境界を跨ぐ回数が異なる場合が多い。従って、第１経路探索サーバと第２経路探索サーバとのいずれか一方を選択することで、他方よりも領域の境界を跨ぐ回数を低減することが可能であることが多い。このため、経路探索システム、プログラムによれば、境界を跨ぐ回数を低減可能である可能性を高めることができる。
【図面の簡単な説明】
【０００８】
【図１】経路探索システムのブロック図である。
【図２】図２Ａは探索サーバ決定処理を示すフローチャートであり、図２Ｂは経路探索処理を示すフローチャートである。
【図３】引継処理を示すフローチャートである。
【図４】第１領域と第２領域の例を示す図である。
【発明を実施するための形態】
【０００９】
ここでは、下記の順序に従って本発明の実施の形態について説明する。
（１）経路探索システムの構成：
（１−１）経路探索管理サーバの構成：
（１−２）第１経路探索サーバおよび第２経路探索サーバの構成：
（２）探索サーバ決定処理：
（３）経路探索処理：
（４）引継処理：
（５）他の実施形態：
【００１０】
（１）経路探索システムの構成：
図１は、本発明にかかる経路探索システム１０の構成を示すブロック図である。本実施形態において、経路探索システム１０は、経路探索管理サーバ２０と、複数の第１経路探索サーバ２１と、複数の第２経路探索サーバ２２とを備えている。なお、本実施形態においては、複数の第１経路探索サーバ２１および複数の第２経路探索サーバ２２のいずれかを示す場合に、符号２１，２２にアルファベット文字（図１においてはＡ，Ｂ）を付する場合もある。
【００１１】
（１−１）経路探索管理サーバの構成：
経路探索管理サーバ２０は、通信部２０ａと記録媒体３０と図示しない制御部を備えている。制御部は、ＣＰＵ、ＲＡＭ、ＲＯＭ等のハードウェア資源を備えており、記録媒体３０やＲＯＭ等に記憶されたプログラムを実行することができる。本実施形態においてはこのプログラムとして図示しない探索サーバ決定プログラムが含まれており、制御部は、探索サーバ決定プログラムを実行することができる。探索サーバ決定プログラムが実行されると、制御部はサーバ決定部２０ｂとして機能する。
【００１２】
通信部２０ａは、外部のナビゲーションシステム５０と無線によって通信するための装置と、経路探索システム１０内の他のサーバ（第１経路探索サーバ２１および第２経路探索サーバ２２）と無線または有線によって通信するための装置とを備えている。従って、制御部は、通信部２０ａを介して、ナビゲーションシステム５０と情報の授受をすることができる。また、制御部は、通信部２０ａを介して、第１経路探索サーバ２１および第２経路探索サーバ２２と情報の授受をすることができる。
【００１３】
記録媒体３０には、領域情報３０ａが記録されている。領域情報３０ａは、複数の第１経路探索サーバ２１および複数の第２経路探索サーバ２２のそれぞれに対する領域の割り当てを示す情報である。本実施形態において、第１領域および第２領域は、地図を示す地図情報の区画（メッシュ）に基づいて定義されている。本実施形態において、地図情報は、道路上に設定されたノードの位置等を示すノードデータ，ノード間の道路の形状を特定するための形状補間点データ，ノード同士の連結を示すリンクデータ，道路やその周辺に存在する施設の位置、属性等を示す施設データ等を含んでいる。
【００１４】
本実施形態においては、地図が複数のメッシュ毎に定義されており、各リンクデータには、各リンクデータが示す道路区間が属するメッシュの識別情報（ＩＤ）が対応づけられている。なお、本実施形態におけるメッシュにおいて、メッシュの境界と道路の交点には必ずノードが設定されている。また、各リンクデータには各リンクデータが示す道路区間のコストが対応づけられている。
【００１５】
本実施形態においては、以上のように地図情報が定義されており、地図情報が示す地図は複数の領域に分割され、各領域が第１経路探索サーバ２１および第２経路探索サーバ２２に割り当てられる。領域情報３０ａは、当該割り当てを示しており、メッシュＩＤと割り当てられたサーバを示す情報とが対応づけられている。
【００１６】
図４は、領域の例を示す図である。本実施形態においては、第１経路探索サーバ２１に割り当てられた領域を第１領域、第２経路探索サーバ２２に割り当てられた領域を第２領域と呼ぶ。図４に示す例において、第１領域および第２領域は、４個のメッシュＭｓによって構成されており、同一形状かつ同一の大きさである。すなわち、図４においてメッシュＭｓは正方形であり、隣接する４個のメッシュＭｓで形成される正方形が第１領域Ｚ1および第２領域Ｚ2の形状および大きさとなる。
【００１７】
図４においては、メッシュＭｓの境界を破線、第１領域Ｚ1の境界を太い実線、第２領域Ｚ2の境界を太い一点鎖線で示している。また、図４においては、第１領域Ｚ1に割り当てられた第１経路探索サーバ２１Ａ〜２１Ｆと第２領域Ｚ2のそれぞれに割り当てられた第２経路探索サーバ２２Ａ〜２２Ｄを示している。例えば、図４の左上の４個のメッシュＭｓ（ＩＤ1〜ＩＤ4）で構成される第１領域Ｚ1は、第１経路探索サーバ２１Ａに割り当てられている。
【００１８】
本実施形態において第２領域は、第１領域と同一形状および同一の大きさであり、第２領域の境界は第１領域の境界から緯度方向（南北方向）および経度方向（東西方向）にメッシュＭｓ１個分ずれている。すなわち、第２領域の重心と第１領域の重心は、互いに緯度方向および経度方向にメッシュＭｓの１辺の長さ分ずれた位置に存在する。従って、第２領域の重心は第１領域の正方形の頂点に存在する。このように、本実施形態において第２領域の境界は、第１領域の境界から緯度方向と経度方向にずれた位置に存在し、第２領域は、複数の第１領域と重複している。
【００１９】
以上の構成により、１個のメッシュＭｓは、１個の第１経路探索サーバ２１に割り当てられ、かつ、１個の第２経路探索サーバ２２に割り当てられる。図４においては、ＩＤ4のメッシュＭｓが、第１経路探索サーバ２１Ａおよび第２経路探索サーバ２２Ａに割り当てられ、ＩＤ2のメッシュＭｓが、第１経路探索サーバ２１Ａおよび第２経路探索サーバ２２Ｃに割り当てられている。領域情報３０ａは、このようなメッシュＩＤとサーバとの対応関係を示している。表１は、図４に示す割り当てを含む領域情報３０ａの例である。
【表１】
2018132322.tif 000003
【００２０】
なお、領域情報３０ａには、各メッシュＩＤが示すメッシュの位置を特定するための情報も対応づけられている。当該情報は、種々の態様で定義可能である。本実施形態において、メッシュの２辺は緯度方向に平行、他の２辺は経度方向に平行であり、例えば北西側の頂点の位置と南東側の頂点の位置とによってメッシュの位置を既定可能である。いずれにしても、サーバ決定部２０ｂは、領域情報３０ａを参照することにより、任意のＩＤのメッシュの位置を特定することが可能であり、任意のメッシュに含まれる座標を特定することができる。また、本実施形態におけるメッシュにおいては、上述のようにメッシュの境界と道路の交点にノードが設定されている。従って、第１領域の境界および第２領域の境界と交差する道路は境界上にノードが設定されていることになる。
【００２１】
ナビゲーションシステム５０の利用者は、任意のタイミングでナビゲーションシステム５０を操作して目的地を設定し、出発地（例えば現在地）から目的地までの経路の探索要求を実行することができる。探索要求が行われると、出発地および目的地を示す情報が経路探索管理サーバ２０に送信される。サーバ決定部２０ｂは、出発地および目的地を含む探索要求を、通信部２０ａを介して受信する。探索要求が受信されると、サーバ決定部２０ｂは、第１経路探索サーバ２１と第２経路探索サーバ２２とのいずれかを選択し、出発地から目的地までの経路を探索させる。
【００２２】
本実施形態において、複数の領域に渡る経路が探索される場合には、複数のサーバによって探索が行われる。そこで、サーバ決定部２０ｂは、経路の探索が開始されてから完了するまでに使用されるサーバの数が最小化されるようにサーバを選択する。具体的には、サーバ決定部２０ｂは、領域情報３０ａに基づいて、第１経路探索サーバ２１によって出発地から目的地まで経路が探索された場合に使用される第１経路探索サーバ２１の数と、第２経路探索サーバ２２によって出発地から目的地まで経路が探索された場合に使用される第２経路探索サーバ２２の数とを見積もる。
【００２３】
本実施形態においてサーバ決定部２０ｂは、出発地と目的地との間に存在する第１領域の境界の数によって、第１経路探索サーバ２１によって出発地から目的地まで経路が探索された場合に使用される第１経路探索サーバ２１の数を見積もる。また、サーバ決定部２０ｂは、出発地と目的地との間に存在する第２領域の境界の数によって、第２経路探索サーバ２２によって出発地から目的地まで経路が探索された場合に使用される第２経路探索サーバ２２の数を見積もる。
【００２４】
すなわち、経路が境界を跨ぐ場合には経路を探索するサーバが変わるため、サーバ決定部２０ｂは、出発地と目的地との間に存在する領域の境界の数が、使用するサーバの数であると推定する。そして、サーバ決定部２０ｂは、出発地と目的地との間に存在する第１領域の境界の数が第２領域よりも少ない場合に、第１経路探索サーバ２１を選択し、多い場合に第２経路探索サーバ２２を選択する。すなわち、サーバ決定部２０ｂは、第１経路探索サーバ２１によって出発地から目的地まで経路が探索された場合に使用される第１経路探索サーバ２１の数が、第２経路探索サーバ２２によって出発地から目的地まで経路が探索された場合に使用される第２経路探索サーバ２２の数よりも少ない場合に、第１経路探索サーバ２１を選択し、多い場合に第２経路探索サーバ２２を選択する。
【００２５】
サーバが選択されると、サーバ決定部２０ｂは、選択したサーバに経路を探索させる。なお、本実施形態においては、サーバの障害等によって経路の探索が不可能にならない限り、最初に選択したサーバに経路を探索させる。例えば、最初に第１経路探索サーバ２１が選択された場合、出発地から目的地までの全経路を第１経路探索サーバ２１に探索させる。また、最初に第２経路探索サーバ２２が選択された場合、出発地から目的地までの全経路を第２経路探索サーバ２２に探索させる。
【００２６】
領域の境界を跨ぐ経路が探索される場合、経路の探索を行ったサーバから、境界を跨いだ先に存在する領域が割り当てられたサーバに経路の探索処理が引き継がれる。当該引継の際には、経路探索サーバ装置間での通信を介して探索済の経路や目的地等の情報の受け渡しを行う必要がある。従って、エリアの境界を跨ぐ回数が多いほど経路の探索以外の付加的な処理が多くなってしまう。
【００２７】
しかし、本実施形態においては、出発地と目的地との間に存在する境界の数（すなわち、サーバの引き継ぎ回数）が少なくなるように第１経路探索サーバ２１と第２経路探索サーバ２２とのいずれかが選択されるため、使用されるサーバの数を少なくすることができる。
【００２８】
さらに、本実施形態においては、第１経路探索サーバ２１が担当する第１領域と第２経路探索サーバ２２が担当する第２領域とが異なるため、第１経路探索サーバで経路の探索が行われる場合と第２経路探索サーバで経路の探索が行われる場合とで、領域の境界を跨ぐ回数が異なる場合が多い。従って、本実施形態のように、地図が第１領域と第２領域との２種類の領域に分類される構成によれば、サーバ決定部２０ｂが第１経路探索サーバ２１と第２経路探索サーバ２２とのいずれか一方を選択することで、他方よりも領域の境界を跨ぐ回数を低減することが可能であることが多い。このため、本実施形態のように、第１領域に割り当てられた第１経路探索サーバ２１と第２領域に割り当てられた第２経路探索サーバ２２との２種類のサーバを設ける構成によれば、境界を跨ぐ回数を低減可能である可能性を高めることができる。
【００２９】
（１−２）第１経路探索サーバおよび第２経路探索サーバの構成：
複数の第１経路探索サーバ２１および複数の第２経路探索サーバ２２は、ほぼ同様の構成を備えており、通信部と記録媒体と図示しない制御部とを備えている。図１においては、第１経路探索サーバ２１が備える通信部を通信部２１ａ、第１経路探索サーバ２１が備える記録媒体を記録媒体３１と表記し、第２経路探索サーバ２２が備える通信部を通信部２２ａ、第２経路探索サーバ２２が備える記録媒体を記録媒体３２と表記している。
【００３０】
制御部は、ＣＰＵ、ＲＡＭ、ＲＯＭ等のハードウェア資源を備えており、記録媒体３１，３２やＲＯＭ等に記憶されたプログラムを実行することができる。本実施形態においてはこのプログラムとして図示しない経路探索プログラムが含まれており、制御部は、経路探索プログラムを実行することができる。経路探索プログラムが実行されると、制御部は経路探索部２１ｂおよび引継部２１ｃや、経路探索部２２ｂおよび引継部２２ｃとして機能する。
【００３１】
本実施形態においては、記録媒体３１，３２に記録された情報を除き、第１経路探索サーバ２１および第２経路探索サーバ２２がほぼ同様の構成である。そこで、ここでは、主に第１経路探索サーバ２１に関して通信部２１ａ、経路探索部２１ｂ、引継部２１ｃの構成を説明するが、各部の機能は、第１経路探索サーバ２１Ａ，２１Ｂや第２経路探索サーバ２２Ａ，２２Ｂ等で同等である（参照する情報によって得られる動作の結果としては異なり得る）。
【００３２】
通信部２１ａは、他のサーバ（第１経路探索サーバ２１、第２経路探索サーバ２２）および経路探索管理サーバ２０と無線または有線によって通信するための装置を備えている。従って、制御部は、通信部２１ａを介して、第１経路探索サーバ２１および第２経路探索サーバ２２、経路探索管理サーバ２０と情報の授受をすることができる。
【００３３】
記録媒体３１には、境界情報３１ａと地図情報３１ｂが記録されている。地図情報３１ｂは、道路上に設定されたノードの位置等を示すノードデータ，ノード間の道路の形状を特定するための形状補間点データ，ノード同士の連結を示すリンクデータ，道路やその周辺に存在する施設の位置、属性等を示す施設データ等を含んでいる。また、各リンクデータには各リンクデータが示す道路区間のコストが対応づけられている。
【００３４】
本実施形態においては、地図が複数のメッシュ毎に定義されており、第１経路探索サーバに割り当てられた第１領域を構成する各メッシュについての地図情報と各メッシュの識別情報（ＩＤ）が地図情報３１ｂを構成する。例えば、図４に示す第１経路探索サーバ２１Ａであれば、ＩＤ1〜ＩＤ4のメッシュで構成された第１領域が割り当てられているため、第１経路探索サーバ２１Ａの記録媒体３１には、これらのメッシュ内の地図を示す地図情報３１ｂとメッシュＩＤが記録されている。第２経路探索サーバ２２Ａには、当該第２経路探索サーバ２２Ａに割り当てられた第２領域を構成するメッシュ内の地図を示す地図情報３２ｂとメッシュＩＤが記録されている。
【００３５】
境界情報３１ａは、第１経路探索サーバ２１に割り当てられた第１領域の外部まで経路の探索を続ける際に、引き継ぐべきサーバの優先順位を示す情報である。本実施形態においては、メッシュの境界上にノードが存在し、第１領域はメッシュで構成されるため、第１領域の地図を示す地図情報３１ｂを参照すれば、当該第１領域の境界上のノードまでの経路を探索することができる。
【００３６】
一方、目的地までの経路が探索される前に第１領域の境界上のノードまで経路が探索されると、当該第１領域の外部の経路を探索する必要が生じる。この場合、他のサーバが経路を探索することになるため、境界上のノードを示す地図情報３１ｂ，３２ｂを備えるサーバを選択して経路の探索を引き継ぐ必要がある。そこで、本実施形態においては、境界上のノードに引継先のサーバを示す情報が対応づけられ、境界情報３１ａとして定義されている。
【００３７】
なお、本実施形態においては、第１領域と第２領域で１個のノードを共有するため、当該ノードを含み、当該ノードの先の道路を示す地図情報３１ｂ，３２ｂが記録されたサーバのいずれにおいても経路の探索を引き継ぐことができる。
【００３８】
例えば、図４においては、各領域内にノードを黒丸、リンクを黒丸間の直線で模式的に示しており、ノードＮ1，Ｎ2は第２経路探索サーバ２２Ａ，２２Ｂに割り当てられた第２領域の境界上に存在し、第１経路探索サーバ２１Ｂに割り当てられた第１領域に含まれる。従って、第２経路探索サーバ２２ＡでノードＮ1までの経路の探索が行われた場合、第２経路探索サーバ２２Ｂと第１経路探索サーバ２１Ｂのいずれかに経路の探索を引き継ぐことができる。
【００３９】
そこで、本実施形態においては、使用するサーバの数が少なくなる可能性を高めるように、引継先のサーバの優先順位が予め決定されている。具体的には、引継前に経路を探索していたサーバが第１経路探索サーバ２１であれば、引継先のサーバとして第１経路探索サーバ２１の優先順位を第２経路探索サーバ２２の優先順位より高くする。引継前に経路を探索していたサーバが第２経路探索サーバ２２であれば、引継先のサーバとして第２経路探索サーバ２２の優先順位を第１経路探索サーバ２１の優先順位より高くする。
【００４０】
境界情報３１ａは、このように、各ノードについて引継可能な引継サーバと、優先順位とが示された情報であり、例えば、表２のような情報で構成される。
【表２】
2018132322.tif 000004
なお、表２に示す境界情報３１ａは、第２経路探索サーバ２２Ａの記録媒体３１に記録された境界情報３１ａの例である。この例においては、ノードＮ1に対して引継サーバとして第２経路探索サーバ２２Ｂと第１経路探索サーバ２１Ｂとが対応づけられており、第２経路探索サーバ２２Ｂの方が第１経路探索サーバ２１Ｂよりも優先順位が高いことが優先フラグ１によって示されている。
【００４１】
むろん、境界情報も、第１経路探索サーバ２１および第２経路探索サーバ２２に割り当てられた領域に対応した情報である。例えば、第１経路探索サーバ２１Ａの記録媒体３１に記録される境界情報３１ａは、第１経路探索サーバ２１Ａに割り当てられた第１領域の境界に存在するノードについての情報である。また、第２経路探索サーバ２２Ａの記録媒体３２に記録される境界情報３２ａは、第２経路探索サーバ２２Ａに割り当てられた第２領域の境界に存在するノードについての情報である。
【００４２】
経路探索管理サーバ２０が経路の探索開始を指示する際には、出発地を含む地図情報３１ｂ，３２ｂが記録された第１経路探索サーバ２１，第２経路探索サーバ２２のいずれかを選択し、探索開始を指示する。探索開始の指示が行われると、引継部２１ｃが当該指示を受け付ける。当該指示には探索の起点（探索開始段階では出発地、引継段階では領域境界上のノード）と目的地とが含まれており、引継部２１ｃは、当該起点と目的地を取得する。
【００４３】
起点と目的地とが取得されると、経路探索部２１ｂ（２２ｂ）は、地図情報３１ｂ（３２ｂ）を参照し、起点から目的地に向けた方向に延びる経路を探索する。すなわち、経路探索部２１ｂ（２２ｂ）は、地図情報３１ｂ（３２ｂ）が示すコストが最小化される経路をダイクストラ法等のアルゴリズムによって探索する。なお、地図情報３１ｂ（３２ｂ）が示す領域内に目的地が含まれない場合、種々の手法で探索が行われ得るが、例えば、起点から目的地の方向に存在する１以上のノードが経由地とされ、起点から経由地までの経路が探索される構成等が採用され得る。
【００４４】
地図情報３１ｂ（３２ｂ）が示す領域内に目的地が含まれない場合、探索済の経路が領域の境界に達すると、サーバの引継が行われる。すなわち、引継部２１ｃは、境界情報３１ａを参照し、探索された経路の目的地側の端点であるノードに対応づけられたサーバを特定する。そして、引継部２１ｃ（２２ｃ）は、通信部２１ａ（２２ａ）を制御し、当該サーバの中で優先順位が高いサーバに対して、探索された経路の目的地側の端点であり起点と目的地を示す情報を送信して探索開始の指示を行う。このようにして、必要に応じて引継が行われながら出発地から目的地までの経路の探索が行われる。
【００４５】
なお、引継部２１ｃが、優先順位が高いサーバに対して探索開始の指示を行ったが、当該サーバが探索を開始しなかった（探索が開始されたことに対する返信がなかった）場合、引継部２１ｃ（２２ｃ）は、優先順位が低いサーバに対して探索開始の指示を行う。すなわち、本実施形態においては、サーバ決定部２０ｂによって選択済のサーバによる探索が不可能である場合に、未選択のサーバが引継部２１ｃ（２２ｃ）によって選択される。従って、優先順位が高いサーバにおいて障害等によって探索開始が行われなかった場合であっても探索が完了する可能性を高めることができる。
【００４６】
（２）探索サーバ決定処理：
次に、経路探索管理サーバ２０が実行する探索サーバ決定処理を説明する。ナビゲーションシステム５０から経路の探索要求が行われると、経路探索管理サーバ２０のサーバ決定部２０ｂは、図２Ａに示す探索サーバ決定処理を開始する。探索サーバ決定処理において、サーバ決定部２０ｂは、ナビゲーションシステム５０が送信した探索要求を通信部２０ａによって取得し、出発地および目的地を取得する（ステップＳ１００）。
【００４７】
次に、サーバ決定部２０ｂは、第１経路探索サーバ２１および第２経路探索サーバ２２の跨ぎ回数を取得する（ステップＳ１０５）。ここで、第１経路探索サーバ２１の跨ぎ回数は、第１経路探索サーバ２１によって出発地から目的地までの経路が探索された場合に、経路と第１領域の境界とが交差する回数である。また、第２経路探索サーバ２２の跨ぎ回数は、第２経路探索サーバ２２によって出発地から目的地までの経路が探索された場合に、経路と第２領域の境界とが交差する回数である。
【００４８】
本実施形態において、当該跨ぎ回数は、出発地と目的地との間に存在する領域の境界の数によって推定される。すなわち、サーバ決定部２０ｂは、出発地と目的地との間に存在する第１領域の境界の数が、第１経路探索サーバ２１の跨ぎ回数であると推定し、出発地と目的地との間に存在する第２領域の境界の数が、第２経路探索サーバ２２の跨ぎ回数であると推定する。
【００４９】
具体的にはサーバ決定部２０ｂは、緯度方向の跨ぎ回数ｈlatと経度方向の跨ぎ回数ｈlonとの和が跨ぎ回数であると見なし、第１経路探索サーバ２１と第２経路探索サーバ２２とのそれぞれについて緯度方向の跨ぎ回数ｈlatと経度方向の跨ぎ回数ｈlonを算出し、和を算出する。本実施形態において緯度方向の跨ぎ回数ｈlatは、以下の式（１）にて定義される。
hlat＝|Floor((Dlat-Mlat)/Slat)-Floor((Olat-Mlat)/Slat)|  ・・・(1)
【００５０】
ここで、Dlatは目的地の緯度、Olatは出発地の緯度、Slatはサーバに割り当てられた領域の緯度方向の長さ、Mlatは基準の緯度であり、Floorは切り捨てを意味する。基準の緯度Mlatは最小の緯度等によって定義可能であり、例えば、北半球の地図に関して第１経路探索サーバ２１について緯度方向の跨ぎ回数が計算される場合、最も南に存在する第１領域の最南端緯度（最南端の辺の緯度）等が基準の緯度として採用可能である。この場合、第２経路探索サーバ２２についての基準の緯度は、最も南に存在する第２領域の最南端緯度（最南端の辺の緯度）である。
【００５１】
式（１）に示されるように、hlatの絶対値内の第１項は目的地の緯度と基準の緯度との差分が領域の長さの何個分に相当するのかを見積もる項であり、第２項は出発地の緯度と基準の緯度との差分が領域の長さの何個分に相当するのかを見積もる項である。従って、両項の切り捨ての差分は、出発地と目的地との間において緯度方向に存在する領域の境界（第１経路探索サーバ２１の場合は第１領域の境界、第２経路探索サーバ２２の場合は第２領域の境界）の数になる。
【００５２】
本実施形態において経度方向の跨ぎ回数ｈlonは、以下の式（２）にて定義される。
hlon＝|Floor((Dlon-Mlon)/Slon)-Floor((Olon-Mlon)/Slon)|  ・・・(2)
ここで、Dlonは目的地の経度、Olonは出発地の経度、Slonはサーバに割り当てられた領域の経度方向の長さ、Mlonは基準の経度であり、Floorは切り捨てを意味する。基準の経度Mlonは、最小の経度等によって定義可能であり、例えば、グリニッジ子午線から東経１８０度の範囲に存在する地図において、最も西に存在する第１領域の最西端経度（最西端の辺の経度）等が基準の経度として採用可能である。この場合、第２経路探索サーバ２２についての基準の経度は、最も西に存在する第２領域の最西端経度（最西端の辺の経度）である。
【００５３】
式（２）に示されるように、hlonの絶対値内の第１項は目的地の経度と基準の経度との差分が領域の長さの何個分に相当するのかを見積もる項であり、第２項は出発地の経度と基準の経度との差分が領域の長さの何個分に相当するのかを見積もる項である。従って、両項の切り捨ての差分は、出発地と目的地との間において経度方向に存在する領域の境界（第１経路探索サーバ２１の場合は第１領域の境界、第２経路探索サーバ２２の場合は第２領域の境界）の数になる。
【００５４】
例えば、図４に示す例において、出発地がＮｓ、目的地がＮｇであり、第１経路探索サーバ２１に割り当てられる第１領域の基準の緯度がMlat1、第２経路探索サーバ２２に割り当てられる第２領域の基準の緯度がMlat2である場合を想定する。この場合、目的地の緯度Dlatと基準の緯度Mlat1との差分は、第１領域の緯度方向の一辺の長さSlatの１個分より多く、２個分より少ない。従って、式（１）の第１項は１である。出発地の緯度Olatと基準の緯度Mlat1との差分は、第１領域の緯度方向の一辺の長さSlatの１個分より少ない。従って、式（１）の第２項は０である。この結果、緯度方向の跨ぎ回数ｈlatは１となり、出発地Ｎｓと目的地Ｎｇとの間において緯度方向に存在する第１領域の境界Ｂa1の数１と一致する。
【００５５】
さらに、図４に示す例において、第１経路探索サーバ２１に割り当てられる第１領域の基準の経度がMlon1、第２経路探索サーバ２２に割り当てられる第２領域の基準の経度がMlon2である場合を想定する。この場合、目的地の経度Dlonと基準の経度Mlon1との差分は、第１領域の経度方向の一辺の長さSlonの１個分より多く、２個分より少ない。従って、式（２）の第１項は１である。出発地の経度Olonと基準の経度Mlon1との差分は、第１領域の経度方向の一辺の長さSlonの１個分より少ない。従って、式（２）の第２項は０である。この結果、経度方向の跨ぎ回数ｈlonは１となり、出発地Ｎｓと目的地Ｎｇとの間において経度方向に存在する第１領域の境界Ｂo1の数１と一致する。以上の結果、第１経路探索サーバ２１の跨ぎ回数は２（＝hlat＋hlon）となる。
【００５６】
同様の計算を第２経路探索サーバ２２において実施する場合、目的地の緯度Dlatと基準の緯度Mlat2との差分は、第２領域の緯度方向の一辺の長さ（本実施形態においては第１領域の緯度方向の一辺の長さSlatと等しい）の１個分より少ない。従って、式（１）の第１項は０である。出発地の緯度Olatと基準の緯度Mlat2との差分は、第２領域の緯度方向の一辺の長さSlatの１個分より少ない。従って、式（１）の第２項は０である。この結果、緯度方向の跨ぎ回数ｈlatは０となり、出発地Ｎｓと目的地Ｎｇとの間において緯度方向に第２領域の境界が存在しない状況に整合する。
【００５７】
さらに、目的地の経度Dlonと基準の経度Mlon2との差分は、第２領域の経度方向の一辺の長さ（本実施形態においては第１領域の緯度方向の一辺の長さSlonと等しい）の１個分より多く、２個分より少ない。従って、式（２）の第１項は１である。出発地の経度Olonと基準の経度Mlon2との差分は、第２領域の経度方向の一辺の長さSlonの１個分より少ない。従って、式（２）の第２項は０である。この結果、経度方向の跨ぎ回数ｈlonは１となり、出発地Ｎｓと目的地Ｎｇとの間において経度方向に存在する第２領域の境界Ｂo2の数１と一致する。以上の結果、第２経路探索サーバ２２の跨ぎ回数は１（＝hlat＋hlon）となる。
【００５８】
第１経路探索サーバ２１および第２経路探索サーバ２２の跨ぎ回数が取得されると、サーバ決定部２０ｂは、最小の跨ぎ回数のサーバを選択する（ステップＳ１１０）。すなわち、サーバ決定部２０ｂは、ステップＳ１０５で取得された跨ぎ回数を参照し、少ない方のサーバを選択する。例えば、図４に示す例であれば、第１経路探索サーバ２１の跨ぎ回数が２，第２経路探索サーバ２２の跨ぎ回数が１であるため、サーバ決定部２０ｂは、第２経路探索サーバ２２を選択する。
【００５９】
次に、サーバ決定部２０ｂは、出発地が存在するメッシュを特定する（ステップＳ１１５）。すなわち、サーバ決定部２０ｂは、領域情報３０ａを参照し、ステップＳ１１０で選択されたサーバに関する情報の中から、出発地が含まれるメッシュを特定する。例えば、図４に示す例であれば、サーバ決定部２０ｂは出発地が含まれるメッシュＩＤ5を特定する。
【００６０】
次にサーバ決定部２０ｂは、特定されたメッシュが割り当てられたサーバに探索指示を送信する（ステップＳ１２０）。すなわち、サーバ決定部２０ｂは、ステップＳ１１５で特定されたメッシュが割り当てられたサーバを特定する。例えば、図４に示す例であれば、メッシュＩＤ5が割り当てられた第２経路探索サーバ２２Ａを特定する。そして、サーバ決定部２０ｂは、第２経路探索サーバ２２Ａに対し、ステップＳ１００で取得された出発地および目的地とともに探索指示を送信する。
【００６１】
（３）経路探索処理：
次に、第１経路探索サーバ２１と第２経路探索サーバ２２が実行する経路探索処理を説明する。経路探索管理サーバ２０または第１経路探索サーバ２１または第２経路探索サーバ２２が探索指示を送信すると、送信先の第１経路探索サーバ２１または第２経路探索サーバ２２が図２Ｂに示す経路探索処理を開始する。なお、ここでは、第１経路探索サーバ２１の経路探索部２１ｂ、引継部２１ｃが実行する処理として説明するが、第２経路探索サーバ２２の経路探索部２２ｂ、引継部２２ｃも同様の処理を実行し得る。
【００６２】
経路探索処理において、引継部２１ｃは、探索指示を受信する（ステップＳ２００）。すなわち、引継部２１ｃは、通信部２１ａを制御し、経路の探索の起点と目的地と探索済の経路を示す情報（リンクＩＤ等）を受信する。なお、探索指示を送信したサーバが経路探索管理サーバ２０である場合には探索済の経路が存在しないため、探索の起点が出発地であり、探索済の経路を示す情報は存在しない。探索指示を送信したサーバが第１経路探索サーバ２１または第２経路探索サーバ２２である場合には探索済の経路の目的地側の端点が探索の起点であり、直前までの探索で得られたリンクＩＤ等が探索済の経路を示す情報である。探索指示の受信が完了すると、引継部２１ｃは、受信が完了した旨の情報を返信する。
【００６３】
次に、経路探索部２１ｂは、起点から目的地までの経路を探索する（ステップＳ２０５）。すなわち、経路探索部２１ｂは、地図情報３１ｂが示すコストが最小化される経路をダイクストラ法等のアルゴリズムによって探索する。なお、地図情報３１ｂが示す領域内に目的地が含まれる場合、起点から目的地までの経路が探索され、地図情報３１ｂが示す領域内に目的地が含まれない場合、起点から経由地までの経路が探索される。
【００６４】
探索が終了すると、経路探索部２１ｂは、境界に到達したか否かを判定する（ステップＳ２１０）。すなわち、目的地までの経路が探索される前に、領域の境界上に存在するノード（経由地）までの経路の探索が行われた場合、経路探索部２１ｂは、境界に到達したと判定する。
【００６５】
ステップＳ２１０において、境界に到達したと判定された場合、引継部２１ｃは、境界上のノードに基づいて優先引継サーバを取得する（ステップＳ２２０）。すなわち、引継部２１ｃは、境界情報３１ａを参照し、探索済経路の目的地側の端点であるノードに対応づけられた引継サーバを特定する。さらに、引継部２１ｃは、引継サーバの中から、優先フラグ１が対応づけられたサーバを優先引継サーバとして特定する。例えば、図４に示す例において、境界上のノードがノードＮ1やＮ2である場合、引継部２１ｃは、第２経路探索サーバ２２Ｂを優先引継サーバとして取得する。
【００６６】
次に、引継部２１ｃは、優先引継サーバに探索指示を送信する（ステップＳ２２５）。すなわち、引継部２１ｃは、ステップＳ２０５における探索の終点となった境界上のノードを次の探索の起点とし、通信部２１ａを制御して優先引継サーバに対し、当該起点と目的地と探索済の経路を示す情報（リンクＩＤ等）を送信する。なお、探索済の経路を示す情報は、出発地から最新の探索の終点までの経路を示す情報である。
【００６７】
一方、ステップＳ２１０において、境界に到達したと判定されない場合、すなわち、出発地から目的地までの経路が探索された場合、引継部２１ｃは、経路探索管理サーバ２０に対して経路を送信する（ステップＳ２３０）。すなわち、引継部２１ｃは、通信部２１ａを制御し、出発地から目的地までの経路を示す情報を経路探索管理サーバ２０に対して送信する。経路探索管理サーバ２０が当該経路を示す情報を受信すると、経路探索管理サーバ２０は、通信部２０ａを介して、探索要求を行ったナビゲーションシステム５０に対して当該経路を示す情報を送信する。この結果、ナビゲーションシステム５０においては、出発地から目的地までの経路を、例えば、経路案内等に利用することが可能になる。
【００６８】
（４）引継処理：
以上のように、本実施形態においては、使用されるサーバの数が少なくなるようにサーバが選択され、経路探索が他のサーバに引き継がれる際には、境界情報３１ａが示す優先引継サーバに対して優先的に経路探索が引き継がれる。また、当該境界情報３１ａも使用されるサーバの数が少なくなるように定義されている。従って、通常であれば、最初に第１経路探索サーバ２１が選択された場合、第１経路探索サーバ２１に経路探索が引き継がれ、最初に第２経路探索サーバ２２が選択された場合、第２経路探索サーバ２２に経路探索が引き継がれる。
【００６９】
しかし、引継先のサーバとなる優先引継サーバに障害等が発生し、引継を行うことができない状況になることもあり得る。本実施形態においては、このような場合であっても経路の探索が実行できる可能性を高める構成が採用されている。すなわち、サーバ決定部２０ｂがステップＳ１２０を実行した場合と、引継部２１ｃ、引継部２２ｃがステップＳ２２５を実行した場合には、並行して図３に示す引継処理が実行される。ここでは、引継部２１ｃによって引継処理が行われる例を説明するが、当該引継処理はサーバ決定部２０ｂ、引継部２２ｃにおいても実行され得る。
【００７０】
引継処理が開始されると、引継部２１ｃは、引継が成功したか否かを判定する（ステップＳ３００）。すなわち、ステップＳ２２５において、探索指示が送信されたサーバは、探索指示を受信すると受信が完了した旨の情報を返信する。そこで、引継部２１ｃは、当該受信が完了した旨の情報を取得した場合に、引継が成功したと判定する。ステップＳ３００において、引継が成功したと判定された場合、引継部２１ｃは、引継処理を終了する。
【００７１】
一方、ステップＳ３００において、引継が成功したと判定されない場合、引継部２１ｃは、優先引継サーバ以外の引継サーバを取得する（ステップＳ３０５）。すなわち、引継部２１ｃは、境界情報３１ａを参照し、境界上のノードに基づいて特定された引継サーバの中から、優先フラグ０が対応づけられたサーバを引継サーバとして特定する。例えば、図４に示す例において、境界上のノードがノードＮ1やＮ2である場合、引継部２１ｃは、第１経路探索サーバ２１Ｂを引継サーバとして取得する。
【００７２】
次に、引継部２１ｃは、引継サーバに探索指示を送信する（ステップＳ３１０）。すなわち、引継部２１ｃは、ステップＳ２０５における探索の終点となった境界上のノードを次の探索の起点とし、通信部２１ａを制御して引継サーバに対し、当該起点と目的地と探索済の経路を示す情報（リンクＩＤ等）を送信する。
【００７３】
次に、引継部２１ｃは、引継が成功したか否かを判定する（ステップＳ３１５）。すなわち、ステップＳ３１０において、探索指示が送信された引継サーバは、探索指示を受信すると受信が完了した旨の情報を返信する。そこで、引継部２１ｃは、当該受信が完了した旨の情報を取得した場合に、引継が成功したと判定する。ステップＳ３００において、引継が成功したと判定された場合、引継部２１ｃは、引継処理を終了する。
【００７４】
一方、ステップＳ３１５において、引継が成功したと判定されない場合、引継部２１ｃは、経路探索が不可能であると見なし、経路探索管理サーバ２０に探索失敗を送信する（ステップＳ３２０）。経路探索管理サーバ２０が探索失敗を示す情報を受信すると、経路探索管理サーバ２０は、ナビゲーションシステム５０に対して探索の失敗を示す情報を送信する。
【００７５】
（５）他の実施形態：
以上の実施形態は本発明を実施するための一例であり、地図を複数の第１領域と、複数の第２領域に分割し、各領域に経路探索サーバを割り当てる限りにおいて、他にも種々の実施形態を採用可能である。なお、ナビゲーションシステム５０とともに移動する移動体は任意であり、車両であっても良いし、歩行者であっても良く、種々の例が想定される。また、経路探索システムは、固定的に設置される装置で構成されても良いし、可搬型の装置によって構成されても良いし、両者によって構成されても良い。
【００７６】
さらに、経路探索管理サーバ２０の少なくとも一部は、第１経路探索サーバ２１または第２経路探索サーバ２２の少なくとも一方に備えられていても良い。例えば、サーバ決定部２０ｂがある特定の第１経路探索サーバ２１に備えられている構成等を採用可能である。さらに、第１経路探索サーバ２１または第２経路探索サーバ２２の少なくとも一方の構成の一部が、経路探索管理サーバ２０に備えられていても良い。例えば、引継部２１ｃにおいて引継先のサーバを決定する機能が経路探索管理サーバ２０で実行されてもよい。また、地図情報が経路探索管理サーバ２０において集中的に管理されていても良い。
【００７７】
第１経路探索サーバは、地図を分割する複数の第１領域毎に割り当てられ、割り当てられた第１領域内の経路を探索する複数のサーバであればよい。すなわち、地図は、複数の第１経路探索サーバのそれぞれが担当する複数の第１領域に分割される。当該分割は、種々の手法によって行われて良く、上述のように、複数のメッシュを備える特定の形状の領域に分割されても良いし、第１経路探索サーバの費用等に応じた領域の大きさの決定や、第１経路探索サーバの１台あたりの負荷（担当する道路区間の数や経路探索の実行頻度等）の均等化が図られるような領域の決定等、種々の手法での分割が可能である。
【００７８】
むろん、複数の第１領域は、同一形状であってもよいし、異なる形状であっても良い。地図は経路の探索に利用されれば良いため、海岸線などの不定形を有する地域において第１領域の形状が例外的な形状であっても良い。また、第１領域は、上述の実施形態のように、境界を共有する複数の領域であっても良いし、第１領域同士が一部で重複していても良い。なお、経路探索対象の地図は第１領域で埋められることが好ましい。第１経路探索サーバは、割り当てられた第１領域の経路を探索することができればよく、割り当てられた第１領域の地図情報は、上述のように各第１経路探索サーバが備える記録媒体に記録されていても良いが、他の装置が備える記録媒体に記録されていても良い。後者の場合、地図情報を１カ所の装置など少ない数の装置に集約することが可能である。
【００７９】
第２経路探索サーバは、地図を分割する複数の第２領域毎に割り当てられ、割り当てられた第２領域内の経路を探索する複数のサーバであればよい。すなわち、地図は、複数の第１領域に分割され、かつ、第１領域の境界の一部を内部に含む領域となるように複数の第２領域にも分割される。第２領域の分割も、第１領域の分割と同様に、種々の手法によって行われて良い。むろん、複数の第２領域の形状も限定されないし、第２領域同士が一部で重複していても良いし、経路探索対象の地図は第２領域で埋められることが好ましい。
【００８０】
第２経路探索サーバも、割り当てられた第２領域の経路を探索することができればよく、第２領域の地図情報は、各第２経路探索サーバが備える記録媒体に記録されていても良いし、他の装置が備える記録媒体に記録されていても良い。後者の場合、地図情報を１カ所の装置など少ない数の装置に集約することが可能である。
【００８１】
第２領域は、第１領域の境界の一部を内部に含む領域であれば良い。すなわち、第１領域と第２領域とが異なるルールで分割されることにより、第１領域内に存在する道路と第２領域内に存在する道路が異なり、第１領域と第２領域のそれぞれの内部に含まれる道路から探索される経路が異なるように構成されていれば良い。なお、第２領域は第１領域の境界の一部を内部に含む領域であるが、ここでいう「一部」に「全部」は含まれない。従って、第１領域の全部が第２領域の内部に含まれることはない。
【００８２】
第１領域と第２領域とは、種々のルールで区別されて良く、例えば、第１領域の境界と第２領域の境界とが少なくとも一部で不一致である構成（境界の交差は一致と見なさない）であっても良い。また、第２領域の境界は、第１領域の境界からずれた位置に存在することが好ましい。このようなずれの方向や量は種々の態様を採用可能であり、上述の実施形態のように、２次元地図内の直交する２方向（例えば緯度方向および経度方向）にずれている態様に限定されない。
【００８３】
例えば、第２領域の境界が、第１領域の境界から緯度方向と経度方向とのいずれか１方向にずれた位置に存在し、１個の第２領域が複数の第１領域と重複している構成であっても良い。この構成によれば、第１領域に基づいて容易に第２領域を生成することができる。ずれの量としても種々の量を採用可能であり、例えば、第２領域の重心が第１領域の境界上や境界を形成する多角形の頂点に存在する構成等を採用可能である。
【００８４】
第１領域と第２領域との関係、例えば、形状や大きさの関係も種々の関係であって良く、上述の実施形態のように、第１領域と第２領域の形状および大きさが同一である構成以外にも種々の構成が採用されてよい。例えば、第１領域と第２領域の形状や大きさが互いに異なっていてもよい。なお、第１領域および第２領域のそれぞれは、１台のサーバに割り当てられる領域であるため、サーバ間で負荷が極端に変動しないように第１領域および第２領域のそれぞれが決められていてもよい。また、第２領域に含まれる第１領域の数や、第１領域に含まれる第２領域の数が、領域毎に極端に変動しないように決められていても良い。
【００８５】
なお、第１領域、第２領域という領域の名称は領域の相対的な関係に着目した名称である。従って、領域の分割ルールは２種類に限定されない。例えば、領域の分割ルールが３種類以上であり、３種類以上の領域に分割される構成が採用されてもよい。この場合、３種類の領域をＡ領域、Ｂ領域、Ｃ領域と呼ぶと、Ａ領域を第１領域とみなした場合にＢ領域が第２領域となり、Ｂ領域を第１領域とみなした場合にＣ領域が第２領域となる等の関係になり得る。
【００８６】
サーバ決定部は、第１経路探索サーバと第２経路探索サーバとのいずれかを選択して経路を探索させる構成であれば良い。すなわち、各サーバは、割り当てられた領域内の道路を示す地図情報に基づいて経路を探索することが可能であるが、第１領域と第２領域とは一部が重複し得る互いに異なる領域であるため、いずれか一方で経路を探索すれば、他方で経路を探索するよりも境界を跨ぐ回数を低減可能である可能性が高い。従って、少なくとも２種の領域（第１領域、第２領域）のそれぞれが割り当てられた第１経路探索サーバと第２経路探索サーバとを含むシステムにおいては、境界を跨ぐ回数がより少なくなるサーバを選択できる可能性を高めることができる。
【００８７】
サーバ決定部がサーバを選択する際には、境界を跨ぐ回数が少ないサーバを選択することが好ましい。当該サーバの選択は、上述の実施形態の構成以外にも種々の構成で実現可能である。例えば、出発地や目的地と第１領域、第２領域との関係に基づいてサーバが選択されてもよい。より具体的には、出発地や目的地、出発地から目的地まで結ぶ直線等に近い重心を有する領域が選択されても良いし、出発地や目的地、出発地から目的地まで結ぶ直線等が領域の境界から遠くなるように領域が選択されても良く、種々の構成を採用可能である。
【００８８】
第１経路探索サーバと第２経路探索サーバとの選択は、出発地から目的地までの全体の経路について１回実施されても良いし、出発地から目的地までの経路が探索されるまでの過程で複数回実施されてもよい。例えば、上述の実施形態においては、サーバに障害等がなければ、通常は最初に選択したサーバに引継が行われるので、最初の１回のみ選択が行われると見なすことができる。一方、障害等によって引継が失敗し、優先引継ではないサーバに引き継がれた場合、優先引継ではないサーバへの引き継ぎが行われるたびに最初の選択と異なる選択が行われると見なすことができる。
【００８９】
さらに、上述の実施形態のように、サーバ決定部が、出発地から目的地まで経路が探索された場合に使用されるサーバの数を見積もる構成において、領域が３種類以上存在するのであれば、使用されるサーバの数が最小となる領域が割り当てられたサーバが選択される。
【００９０】
さらに、本発明のように、地図を複数の第１領域と、複数の第２領域に分割し、各領域に経路探索サーバを割り当てる手法は、プログラムや方法としても適用可能である。また、以上のようなシステム、プログラム、方法は、単独の装置として実現される場合もあれば、各種のシステムと共有の部品を利用して実現される場合もあり、各種の態様を含むものである。また、一部がソフトウェアであり一部がハードウェアであったりするなど、適宜、変更可能である。さらに、システムを制御するプログラムの記録媒体としても発明は成立する。むろん、そのソフトウェアの記録媒体は、磁気記録媒体であってもよいし光磁気記録媒体であってもよいし、今後開発されるいかなる記録媒体においても全く同様に考えることができる。
【符号の説明】
【００９１】
１０…経路探索システム、２０…経路探索管理サーバ、２０ａ…通信部、２０ｂ…サーバ決定部、２１…第１経路探索サーバ、２１Ａ…第１経路探索サーバ、２１Ｂ…第１経路探索サーバ、２１ａ…通信部、２１ｂ…経路探索部、２１ｃ…引継部、２２…第２経路探索サーバ、２２Ａ…第２経路探索サーバ、２２Ｂ…第２経路探索サーバ、２２Ｃ…第２経路探索サーバ、２２ａ…通信部、２２ｂ…経路探索部、２２ｃ…引継部、３０…記録媒体、３０ａ…領域情報、３１…記録媒体、３１ａ…境界情報、３１ｂ…地図情報、３２…記録媒体、３２ａ…境界情報、３２ｂ…地図情報、５０…ナビゲーションシステム
【図１】
2018132322.tif 000005
【図２】
2018132322.tif 000006
【図３】
2018132322.tif 000007
【図４】
2018132322.tif 000008