[第1の実施形態]
 図1に、本発明の第1の実施形態のシステム� �成を示す。システム101において、マルチプ� �セッサ51は、入力データ5をもとに探索した� �路の情報を探索結果記憶部8へ格納し、その� ��から選択した情報を用いて出力経路9を編成 する。入力データ5には、経路探索に必要な� �図情報や、ユーザから指定された出発地及� �目的地といった情報が含まれる。

 マルチプロセッサ51は、プログラムの実� �により実現される機能として、中継点設定� �1,部分探索設定部2,経路探索部3(3-1,3-2)及び経 路編成部4を備える。中継点設定部1は、入力� ��ータ5から地図上の出発地及び目的地を認識 し、両者間に中継点6を設定する。本実施形� �では、出発地と目的地との間に単一の中継� �が設定される。

 部分探索設定部2は、中継点6に対する出� �地及び目的地からの経路を探索するための� �分探索データ7(7-1,7-2)を作成する。部分探索� ��ータ7には、出発地及び目的地ならびに中継 点を含む広域の探索範囲や、その範囲内での 探索対象となる部分領域の情報が含まれる。 本実施形態の部分探索データ7は、出発地か� �中継点6までの経路探索のための部分探索デ� ��タ7-1と、目的地から中継点6までの経路探索 のための部分探索データ7-2とから構成される 。

 経路探索部3(3-1,3-2)は、部分探索データ7(7 -1,7-2)を用いて、出発地から中継点への経路� �、目的地から中継点への経路とを並列処理� �より探索する。経路の探索にあたっては、� �離や所要時間など、経路の長短を評価する� �めの指標であるコストを用いる。経路探索� �3は、並列処理により得られた各部分領域の� ��索結果を探索結果記憶部8に格納する。

 経路編成部4は、探索結果記憶部8に格納� �れた情報から、出発地及び目的地間でコス� �が最小となる一連の経路を編成し、それを� �力経路9として出力する。

 図2に示すフローチャートに沿って、上記 機能を持つマルチプロセッサ51の動作につい� ��説明する。マルチプロセッサ51は、まず、� �図情報,出発地及び目的地などの情報が記述� ��れた入力データ5を読み込む(ステップS1)。

 図3に、入力データ5の例を示す。図示の� �力データ5には、地図上の各交差点33をノー� �として、ノード間の距離や走行の所要時間� �どに関する道路情報34が示されている。「S� �が記述された交差点は今回の出発地31であり 、「T」は目的地32である。また、道路情報34� ��付記されている円内の数値は、対応する2つ の交差点(33)間のコスト値を表す。

 中継点設定部1は、入力データ5から出発� �31及び目的地32を認識し、両者間の中継点6と しての交差点を選定する(ステップS2)。部分� �索設定部2は、中継点6,出発地31及び目的地32� ��含む広域の探索範囲について、出発地31及� �中継点6間の部分探索データ7-1と、目的地32� �び中継点6間の部分探索データ7-2とを作成す� ��(図2:ステップS3)。

 図4に、部分探索データ7の例を示す。図� �の出発地31及び目的地32は、それぞれ図3に示 すものに対応する。また、「R」が記述され� �交差点(46)は、中継点設定部1が設定した中継 点(6)に対応する。部分探索設定部2は、中継� �46,出発地31及び目的地32を含む広域の探索範� ��47cを設定する。そして、探索範囲47c内にお� ��て、出発地31及び中継点46間の経路探索のた めの部分領域47aと、目的地32及び中継点6間の ための部分領域47bとを設定し、設定した各領 域についての部分探索データを作成する。こ れにより、出発地31及び目的地32間に2つの探� ��領域が形成される。

 経路探索部3(3-1,3-2)は、部分探索データ7(7 -1,7-2)を用いて、すべての部分領域の経路を� �行処理で探索する(図2:ステップS4)。より具� �的には、図4の部分領域47a及び部分領域47bの� ��路探索を並列で行う。各部分領域での探索� ��果は、順次、探索結果記憶部8へ格納される 。

 経路編成部4は、すべての部分領域の探索 結果を探索結果記憶部8から読み出し、今回� �出発地及び目的地間の一連の経路を編成す� �(ステップS5)。このとき、コストが最小とな� ��ように経路を編成する。そして、編成した� ��路を出力する(ステップS6)。

[具体例]
 上記実施形態について具体例を挙げる。本� ��では、図5に示す状況を想定する。図示の状 況は、メッシュ状の道路34-1-1~34-7-5及び35-1-1~3 5-6-6と曲線状の高速道路39とを含む地図上の� �差点に、出発地31(「S」)及び目的地32(「T」)� ��らびに中継点46(「R」)が設定された状況で� �る。

 高速道路39を走行するための所要時間の� �積値は、メッシュの1区間当たり「1」である とする。図示の高速道路39は、6区間にわたる ことから、端から端までの所要時間は「6」� �ある。ジグザグが付された道路34-3-3~34-3-6及� ��34-4-3~34-4-6は、工事中の道路であり、1区間� �所要時間は「10」とする。その他の道路は、 1区間当たり「3」であるとする。

 図6に、図5の地図にて取り扱う交差点33-1- 1~33-7-6の配置を示す。各交差点には、経路の� ��算に使用する距離A,B,Cが順次設定される。� �示の例において、各交差点の下段左の距離A� ��は、出発地の交差点33-6-5Sからの距離が入力 され、その右隣の値Bには、目的地の交差点33 -2-5Tからの距離が入力される。上段の距離Cは 、下段の距離A,Bの合計である。

 マルチプロセッサ51は、中継点33-4-1Rを設� ��すると、出発地33-6-5Sから中継点33-4-1Rへの� �路探索のための部分探索データと、目的地33 -2-5Tから中継点33-4-1Rへの経路探索のための部 分探索データとを作成する。そして、2種類� �部分探索データを用いた探索処理を並列で� �行する。

 図7に、出発地33-6-5Sから中継点33-4-1Rへの� ��路探索の様子を示す。各交差点における合� ��値(上段)のうち、括弧付きの値は、見積段� �のもの、すなわち既知の情報をもとに推測� �た距離(下段)の合計を示す。また、見積段階 から後述の確定処理を終えた交差点の合計値 には、確定を表す「*」が設定されている。� �ルチプロセッサ51は、各交差点に対する設定 の内容を、順次、探索結果記憶部8へ格納す� �。

 見積から確定への遷移について例を挙げ� ��。まず、初めに出発地33-6-5Sの合計値「4」� �確定される。次に、出発地33-6-5Sから上下左� ��にある交差点(33-5-5,33-7-5,33-6-4,33-6-6)に、出� �地33-6-5Sからの見積値「3」が設定される(下� �左)。見積値を設定した交差点のうち、出発� ��33-6-5Sからの距離と、中継点33-4-1Rへの距離� �の合計が最小となる交差点を選択する。そ� �結果、図7において出発地33-6-5Sの左隣に位置 する交差点33-6-4が選択される。このような処 理の対象となった交差点(33-5-5,33-7-5,33-6-4,33-6- 6)の合計値(上段)に、確定を表す「*」が設定� ��れる。

 続いて、上記で選択された交差点33-6-4の� ��下左右の交差点(33-5-4,33-7-4,33-6-3,33-6-5)につ� �て、出発地33-6-5Sからの見積値「6」(下段左)� ��設定される。この見積値よりも小さい値が� ��でに設定されている場合は、その小さい値� ��維持する。例えば、出発地33-6-5Sの場合、そ の下段左に、「6」より小さい「0」がすでに� ��定されていることから、この「0」を維持す る。そして、上記手順と同様に、見積値を設 定した交差点のうち、出発地33-6-5Sからの距� �と、中継点33-4-1Rへの距離との合計が最小と� ��る交差点を選択する。ここでは、交差点33-6 -4の上下にある交差点33-5-4又は33-7-4が選択さ� ��る。また、今回の判定対象の交差点に、確� ��の「*」が設定される。以降、同様な手順で 、中継点33-4-1Rへ向けて処理を進める。

 図8に、目的地33-2-5Tから中継点33-4-1Rへの� ��路探索の様子を示す。ここでは、前述した� ��7の例と同様な処理を、目的地33-2-5Tから進� �る。なお、図8では、各交差点の合計値(上段 )のうち、確定したものには「**」が付記され ている。

 マルチプロセッサ51は、2つの探索領域に� ��いて得られた経路の情報を探索結果記憶部8 から順次読み出し、それらを統合する。図9� �、経路の情報が統合された様子を示す。図� �の各交差点において、下段左の値は、出発� �33-6-5Sから中継点33-4-1Rへの経路探索のもの(� �7)に対応し、下段右の値は、目的地33-2-5Tか� �中継点33-4-1Rへの経路探索のもの(図8)に対応� ��る。上段の値は、下段の2値の合計であり、 その交差点を経由した場合の出発地33-6-5S及� �目的地33-2-5T間の総距離を表す。

 図9において、交差点33-4-2の合計値には「 ***」が設定されている。これは、中継点33-4-1 Rに対する出発地33-6-5S及び目的地33-2-5Tの双方 からの経路探索において、交差点33-4-2の確定 処理が行われたことを表す。この交差点33-4-2 の合計「30」は、すなわち、出発地33-6-5Sから 交差点33-4-2を経由して目的地33-2-5Tへ至る経� �について確定された総距離である。

 マルチプロセッサ51は、確定された総距� �である「***」の値が、他の交差点の見積段� �の合計値よりも小さいことを検知したとき� �その「***」の交差点を経由することで最短� �路を編成できると判断する。見積段階の合� �値のうち、「***」よりも小さいものがある� �合は、その見積段階の交差点について、前� �と同様な確定処理を進める。

 より具体的には、例えば、図9の交差点33- 4-2は、前述したように、総距離「30」が確定� ��れている。一方で、この「30」よりも小さ� �見積段階の合計値を持つ交差点33-1-1,33-1-3,33- 4-5,33-7-1,33-7-3が存在する。そこで、マルチプ� ��セッサ51は、これらの交差点について、合� �値が小さいものから順に確定処理を進める� �すなわち、合計値「(20)」の交差点33-1-1,33-7-1 について、目的地33-2-5Tから中継点33-4-1Rへの� ��路探索で距離を確定した後、合計値「(24)」 の交差点33-1-3について、出発地33-6-5Sから中� �点33-4-1Rへの経路探索で距離を確定する。こ� ��により、交差点33-1-3の総距離が確定され、� ��***」が設定される。

 図10に、上記の交差点33-1-3の総距離「24」 が確定した時点の様子を示す。この時点で、 マルチプロセッサ51は、すべての交差点のな� ��で交差点33-1-3の「24」よりも小さい合計値� �持つものは存在しないことから、この交差� �33-1-3を経由する経路が最短であると認識す� �。その結果、マルチプロセッサ51は、出発地 33-6-5Sから目的地33-2-5Tへの最短の経路として� ��高速道路39を利用する図示の矢印の経路を� �成する。

 前述の例において、中継点33-4-1Rに対する 出発地33-6-5S及び目的地33-2-5Tからの経路探索� ��おいて、距離を確定した交差点の数は、そ� ��ぞれ18個(図7の「*」及び図8の「**」の数量)� ��ある。ここで、マルチプロセッサ51が双方� �経路探索を並列処理することから、経路探� �にかかる時間は、交差点18個分と考えること ができる。その後、出発地33-6-5Sから目的地33 -2-5Tまでの一連の経路を編成する際に、3つの 交差点(33-1-1,33-7-1,33-1-3)の確定処理が追加さ� �た。よって、本例によれば、最終的な経路� �決定するために必要な確定処理は、交差点21 個分(18+3=21)である。

 これに対し、従来知られた経路探索のア� ��ゴリズムの一つであるA*(A-star)アルゴリズム を用いた場合の処理例を図11に示す。図示の� ��#」付きの値は、出発地33-6-5Sから目的地33-2- 5Tへの経路探索で確定された距離であり、「# #」は目的地33-2-5Tについて確定した距離であ� ��。この場合、交差点33個分の確定処理を必� �とされ、本発明の上記具体例よりも手間が� �かることがわかる。

 以上説明したように、本実施形態のマル� ��プロセッサ51は、出発地及び目的地間に中� �点6を設定して2つの部分領域を形成し、各領 域の経路を並列処理により探索する。これに より、経路探索が効率化されることから、ユ ーザに対し、出発地から目的地までの一連の 経路を迅速に提示することが可能となる。

 なお、地図上の何れの領域を中継点(6)と� ��るかは任意であるが、効率的な経路として� ��用される可能性が高い領域を採用すること� ��望ましい。例えば、広域の探索範囲に、高� ��道路の出入口、主要道路の主要交差点、主� ��な橋梁などがある場合は、それを中継点と� ��て選択するよう設定しておく。これにより� ��高速道路や橋梁といった、コストの小さい� ��間が優先的に探索されることから、最短経� ��をより早く決定することができる。

 ここで、前述のメッシュ地図において、� ��速道路39の入口を中継点に設定した場合を� �に挙げる。本例の中継点(33-7-3R)は、高速道� �39の入口付近の交差点である。図12に、出発� ��33-6-5Sから中継点33-7-3Rへの経路探索の様子� �示す。これは、交差点33-4-1を中継点とした� �述の図7の経路探索と対照することができる� ��図示の探索では、中継点33-7-3Rの合計値(上� �)として、出発地33-6-5Sからの距離「9」が確� �されている。

 また、図13に、目的地33-2-5Tから中継点33-7 -3Rへの経路探索の様子を示す。これは、前述 の図8の経路探索と対照することができる。� �例では、中継点33-7-3Rの合計値として、目的� ��33-2-5Tからの距離「15」が確定されている。� ��って、中継点33-7-3Rの合計値について、図12� ��び図13の数値を統合すると、高速道路39を利 用して出発地33-6-5Sから目的地33-2-5Tへ至る経� ��の総距離として、前述の例と同じ「24」(9+15 =24)が得られる。

 本例において、確定処理の対象となる交� ��点の数(図12の「*」及び図13の「**」の数)は� ��交差点33-4-1を中継点とした前述の例での数( 図7の「*」及び図8の「**」の数)よりも少ない ことがわかる。従って、高速道路39の出入口� ��近を中継点に設定することにより、最短経� ��を一層効率よく求めることができる。

[第2の実施形態]
 図14に、本発明の第2の実施形態のシステム� ��成を示す。前述の実施形態では単一の中継� ��が設定されたが、本実施形態では複数の中� ��点を設定する。システム102において、中継� ��設定部1が複数の中継点6(6-1,…,6-L)を設定し� ��部分探索設定部2が、設定された中継点6に� �応した部分領域データ7(7-1,…,7-M)を作成する 。そして、経路探索部3(3-1,…,3-P)が、部分領� ��データ7を用いて経路を並列処理により探索 する。

 図15に、本実施形態における部分探索デ� �タの例を模式的に示す。図示の例において� �出発地31(「S」)及び目的地32(「T」)間には、4 つの中継点46-1(「R1」),46-2(「R2」),46-3(「R3」), 46-4(「R4」)が設定されている。部分探索設定� ��2は、これら4つの中継点に関する8個の部分� ��域を探索範囲47c内で設定する。すなわち、� ��継点46-1については、出発地31から中継点46-1 への経路探索のための部分領域47a-1と、目的� ��32から中継点46-1への経路探索のための部分� ��域47b-1とを設定する。また、同様に、中継� �46-2に関する部分領域47a-2,47b-2と、中継点46-3� ��関する部分領域47a-3,47b-3と、中継点46-4に関� ��る部分領域47a-4,47b-4とを設定する。

 図16に示すフローチャートに沿って、本� �施形態の動作を説明する。ここでは、前述� �た図15の例を想定する。マルチプロセッサ51� ��、入力データ5を読み込み(ステップS11)、地� ��上の出発地31及び目的地32間に複数の中継点 46-1~46-4を設定する(ステップS12)。そして、各� ��継点についての8個の部分領域47a-1~47a-4,47b-1~ 47b-4を探索するための部分探索データを作成� ��る(ステップS13)。

 経路探索部3-1,…,3-Pは、作成された部分� �索データを用いて、8個の部分領域の経路を� ��列処理により探索する(ステップS14)。これ� �より、8個の部分領域の処理を概ね1個分の所 要時間で処理することができる。

 経路編成部4は、4つの中継点R1~R4のそれぞ れについて、前述の実施形態と同様にして、 出発地Sから目的地Tへの最短経路を編成する( ステップS15)。そして、編成した4つの経路の� ��から、さらに最短のものを選択する(ステッ プS16)。より具体的には、4つの中継点R1~R4の� �で、例えば中継点R1に関する最短経路のコス トが最小である場合、この中継点R1の最短経� ��が選択される。経路編成部4は、選択した経 路を出力経路9として出力する(ステップS17)。

 本実施形態によれば、中継点を複数設定� ��ることから、より広い範囲の経路探索が可� ��となる。また、前述の実施形態と同様に、� ��数の部分領域の経路探索が並列で実行され� ��ことから、部分領域が増えても、理論上は1 つの部分領域の所要時間で済む。よって、本 実施形態でも経路探索の効率化が図られる。

 本発明の実施は、上記の形態に限らず、� ��求の範囲内において種々の形態が可能であ� ��。例えば、複数の中継点を設定する場合に� ��前述の実施形態のように中継点を並列的に� ��定すること(図15)に限らず、中継点を直列的 に設定する、あるいは、並列及び直列を併用 してもよい。

 図17に、2つの中継点を直列的に設定した� ��を示す。図示の例は、出発地31及び目的地32 間に、中継点46a(「Ra」)と中継点46b(「Rb」)と� ��設定したものである。この場合、出発地31� �らの部分領域47aと、目的地32からの部分領域 47bの他に、中継点46a,46b間の経路探索のため� �部分領域47abが設定される。そして、最終的� ��経路は、3つの部分領域(47a,47b,47ab)に関する� ��索結果から編成される。直列的な中継点を� ��定することで、出発地と目的地との間が極� ��て長距離である場合でも、探索時間が長引� ��ことを防ぐことができる。

 なお、上記のように2つの中継点のための 部分領域を設定した場合、その領域の経路探 索は、出発地及び目的地からの経路探索を終 えてから実行する。すなわち、図17の例では� ��部分領域47abの経路探索を、2つの部分領域47 a,47bの並列処理後に行う。中継点を4つ以上設 定した場合は、共通の中継点を含まない領域 同士であれば、それらの経路探索を並列処理 することができる。例えば、出発地及び目的 地間に直列の4つの中継点W,X,Y,Zがこの順序で� ��定された場合、中継点W,X間の経路探索と、� ��継点Y,Z間の経路探索とを並列処理すること� ��できる。

 本発明における中継点としては、上記の� ��体例のような交差点に限らず、公共施設や� ��など、地図上の任意の場所を設定してよい� ��また、中継点は、局所的な場所に限らず、� ��えば、近接する複数の道路や建物を集合化� ��た地域であってもよい。

 本発明は、Web上の地図検索サイトにおけ� ��経路探索に限らず、カーナビゲーションに� ��好適である。例えば、案内中の経路から外� ��て走行した場合、経路探索の再試行が発生� ��るが、このような場合でも、本発明によれ� ��、ユーザに対し新たな経路を迅速に提示す� ��ことができる。

 本発明は、上記各実施形態のマルチプロ� ��ッサ(51)の機能に対応したコンピュータプロ グラム、あるいは、そのプログラムを記憶し た記録媒体として実施することができる。こ の場合、複数の経路探索部(3)のそれぞれを別 個の演算手段に実行させることにより、複数 の部分領域の経路を並列処理で探索する。

 本出願は、2007年10月24日に日本出願された� �願2007-276527を基礎とする優先権を主張し、そ の開示の内容を全て本明細書に取り込むもの である。