(57)【要約】【課題】  移動の効率化を図るために、混雑具合（渋滞）以外の要因であるも考慮すること、すなわち、移動体の大きさや運搬物によって経路が限定されることがある（重量や車幅の問題で通行が制限される）ことも考慮することが必要である。【解決手段】  本発明では、複数の出発地から複数の目的地に至る経路をノード単位に分割し、各ノードのコストを考慮して経路を特定するものである。この際、他の移動体の移動も考慮して、コストを算出する。すなわち、優先する移動体の経路をまずは特定し、当該経路については、各ノードのコストを示す数値を上げ、該当ノード避ける方向で経路を探索する。【選択図】  図１
2017190964.tif 000002
【特許請求の範囲】
【請求項１】
複数の出発地から複数の目的地に至る経路をノード単位に分割して記録する手段と、
前記ノードのそれぞれについて、移動体の移動に対するコストを対応付けて記録する手段と、
複数の移動体の移動におけるコストが最小になるよう算出する手段であって、前記複数の移動体のうち優先される移動体の移動コストを算出し、当該移動体が移動する経路に含まれるノードのコストを補正して、前記複数の移動体うち他の移動体の移動コストを算出する手段とを有することを特徴とする経路探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動体（トラック等）の移動経路を計画するための経路探索技術に関する。
【背景技術】
【０００２】
現在、物流などで移動体が利用されていることが多い。移動体の移動をスムーズに行うために、経路探索を行うことで、物流の効率化が図られている。例えば、カーナビゲーションで混雑する経路を避けるなど。また、コストを最小にするよう経路を特定するものがある。
【０００３】
特許文献１においては、より精度の高い渋滞予測を行うために、路線バスのダイヤ情報も加味することが開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第3374678号
【発明の概要】
【発明が解決しようとする課題】
【０００５】
移動の効率化には、混雑具合（渋滞）だけを考慮するだけでは不十分である。経路によっては、その大きさや運搬物によって経路が限定されることがある（重量や車幅の問題で通行が制限される）。また、運搬物によっては、避けるべき道路が存在することがある。
【課題を解決するための手段】
【０００６】
そこで、本発明では、複数の出発地から複数の目的地に至る経路をノード単位に分割し、各ノードのコストを考慮して経路を特定するものである。この際、他の移動体の移動も考慮して、コストを算出する。すなわち、優先する移動体の経路をまずは特定し、当該経路については、各ノードのコストを示す数値を上げ、該当ノード避ける方向で経路を探索する。
【発明の効果】
【０００７】
本発明によれば、より精度よく効率的な経路を探索可能になる。
【図面の簡単な説明】
【０００８】
【図１】本発明の一実施形態における機能構成概略図
【図２】本発明の一実施形態における経路探索の前提1  (リンク名)を説明するための図
【図３】本発明の一実施形態における経路探索の前提2  (ノード名)を説明するための図
【図４】本発明の一実施形態における案内の状態遷移図
【図５】本発明の一実施形態における処理フロー１
【図６】本発明の一実施形態における処理フロー２
【図７】本発明の一実施形態における処理フロー３
【図８】本発明の一実施形態を適用した初回目的地A/Bからの最適経路を示す図
【図９】本発明の一実施形態を適用した初回目的地C/Dからの最適経路を示す図
【図１０】本発明の一実施形態を適用した第二フェーズ  目的地A/Bからの最適経路を示す図
【図１１】本発明の一実施形態を適用した第二フェーズ  目的地C/Dからの最適経路を示す図。
【図１２】本発明の一実施形態を適用した  第三フェーズ  目的地C/Dからの最適経路を示す図
【図１３】本発明の一実施形態で用いる表1「リンクテーブル」
【図１４】本発明の一実施形態で用いる表2「ノードテーブルA/B」
【図１５】本発明の一実施形態で用いる表３「ノードテーブルC/D」
【図１６】本発明の一実施形態で用いる表4「状態テーブル」
【図１７】本発明の一実施形態で用いる表5「処理値テーブル」
【図１８】本発明の一実施形態の目的地A/Bの探索後のリンクテーブル
【図１９】本発明の一実施形態の目的地A/Bの探索後のノードテーブルA/B
【図２０】本発明の一実施形態の目的地A/Bの探索後の状態テーブル
【図２１】本発明の一実施形態の目的地C/Dの探索後のリンクテーブル
【図２２】本発明の一実施形態の目的地C/Dの探索後のノードテーブルC/D
【図２３】本発明の一実施形態の目的地C/Dの探索後の状態テーブル
【図２４】本発明の一実施形態の案内Dの最適ルート採用後のリンクテーブル
【図２５】本発明の一実施形態の案内D採用直後の処理値テーブル
【図２６】本発明の一実施形態の案内D採用直後の状態テーブル
【図２７】本発明の一実施形態の案内A棄却直後の状態テーブル
【図２８】本発明の一実施形態の案内Bの最適ルート採用後のリンクテーブル
【図２９】本発明の一実施形態の案内B採用直後の状態テーブル
【図３０】本発明の一実施形態の案内B採用直後の処理値テーブル
【図３１】本発明の一実施形態の案内C棄却直後の状態テーブル
【図３２】本発明の一実施形態の重複補正後の各リンクのコスト
【図３３】本発明の一実施形態の初回S５２１実施直後の状態テーブル
【図３４】本発明の一実施形態の採用済みリンク探索直後のノードテーブルA/B
【図３５】本発明の一実施形態の初回S522処理後のノードテーブルA/B
【図３６】本発明の一実施形態の初回S522処理後のノードテーブルC/D
【図３７】本発明の一実施形態の初回S523該当行を示したノードテーブルA/B
【図３８】本発明の一実施形態の２回目S523該当行を示したノードテーブルA/B
【図３９】本発明の一実施形態の最終的なノードテーブルA/B
【図４０】本発明の一実施形態の最終的なノードテーブルC/D
【図４１】本発明の一実施形態の重複補正後の各リンクのコスト
【図４２】本発明の一実施形態の第二フェーズ  案内A探索後のリンクテーブル
【図４３】本発明の一実施形態の第二フェーズ  案内A探索後のノードテーブルA/B
【図４４】本発明の一実施形態の第二フェーズ  案内C探索後のリンクテーブル
【図４５】本発明の一実施形態の第二フェーズ  案内C探索後のノードテーブルC/D（１）
【図４６】本発明の一実施形態の第二フェーズ  案内C探索後の状態テーブル
【図４７】本発明の一実施形態の第二フェーズ  S510実施直後のリンクテーブル
【図４８】本発明の一実施形態の第二フェーズ  案内A採用後の状態テーブル
【図４９】本発明の一実施形態の第二フェーズ案内A採用直後の処理値テーブル
【図５０】本発明の一実施形態の第二フェーズ  案内Ｃ棄却後の状態テーブル
【図５１】本発明の一実施形態の第二フェーズ  S518実施直後のリンクテーブル
【図５２】本発明の一実施形態の第二フェーズ  S519直後の状態テーブル
【図５３】本発明の一実施形態の第二フェーズ  S５２１直後のノードテーブルC/D
【図５４】本発明の一実施形態の第二フェーズ  S522  No判定時のノードテーブルC/D
【図５５】本発明の一実施形態の第二フェーズ終了直後のリンクテーブル
【図５６】本発明の一実施形態の第三フェーズ  案内C探索後のリンクテーブル
【図５７】本発明の一実施形態の第三フェーズ  案内C探索直後のノードテーブルC/D
【図５８】本発明の一実施形態の第三フェーズ  S507直後の状態テーブル
【図５９】本発明の一実施形態の第三フェーズ  S５１０直後のリンクテーブル
【図６０】本発明の一実施形態の第三フェーズ  S511直後の状態テーブル
【図６１】本発明の一実施形態の第三フェーズ  S512直後の処理値テーブル
【発明を実施するための形態】
【０００９】
以下、本発明の一実施形態を、図面を用いて説明する。本実施形態は、複数の車両に対して、複数の出発地から複数の目的地に至る経路を特定するものであって、車両が一部区間で重複することによるロスを減らすことを可能にする経路探索を実行するものである。この際、渋滞も考慮して経路を探索する。図１は、本発明の一実施形態における経路探索システム100の機能構成概略図である。経路探索システム100は、処理部101、条件入力部102、出力部103で構成され、処理部101は、条件補正部104、道コスト算出部105、ルートコスト算出部106、地図データ107、ルート採用判定部108で構成される。経路探索システム100は、いわゆるコンピュータで実現され、処理部101が演算装置(CPU)であり、プログラムに従ってが各種処理を実行する。その内容は、以下説明する。
【００１０】
次に、図2、図3のような地図の概略図を例に、本実施形態における前提条件を説明する。本実施形態では、出発地から目的地へ走行するルートを特定し、実際に走行する車両に提案することを想定した例としている。そこで今回は、ルートを探索、確定すべき、ある出発地からある目的地までの走行を、便宜的に１つの「案内」と名づけることとする。ここでは、図2における出発地Aから目的地A/Bへ向う案内(以下、案内A)、出発地Bから目的地A/Bへ向う案内(以下、案内B)、出発地Cから目的地C/Dへ向う案内(以下、案内C)、出発地Dから目的地C/Dへ向う案内(以下、案内D)の4つの案内についてルートを探索する。図2、および図3では、それぞれの出発地と目的地を結ぶ道と交差点は、ノードとリンクによって表し、横方向に伸びるリンクの上、または縦方向に伸びるリンクの右に記載した文字列がそのリンク名である。また、各リンクにはそのリンクが表す道の距離や走りやすさなどを考慮した数字としてコストを定義し、表１にそれぞれのリンクのコストを記載した。また、図3では各ノードにもノード名を定義した。
【００１１】
なお、本実施形態では、リンクの方向に関わらず、コストは一定としている。例えば、図２のノードN２５１とノードN２５２の間のコストは２５であるが、これはノードN２５１からノードN２５２へ向う場合も、ノードN２５２からノードN２５１へ向う場合も同様にコストは２５となる。
【００１２】
また、本実施形態においては、各案内は図４の案内の状態遷移図に基づいて、状態が遷移する。本実施形態における状態は、４つの種類があり、各案内は、これら４つの状態のいずれか１つの状態に属している。それぞれの状態に関して、説明する。状態４０１「未探索」は、その状態にある案内が、そのフェーズにおいて最適ルートを探索されていない状態を示す。フェーズとは、各リンクにおけるコストが固定されている期間を表現する。
状態４０２「探索済」は、その状態にある案内が、そのフェーズにおいて最適ルートを探索済となっている状態を表す。
状態４０３「採用」は、その状態にある案内が、現状の最適ルートで確定となった状態を表す。
状態４０４「棄却」は、その状態にある案内が、現状の最適ルートでは、全体の最適化とはならないため、再度最適ルートを探索する必要がある状態を表す。
【００１３】
次に、本実施形態では、経路探索に用いるデータテーブルを、図１３〜１７を用いる。
図８は、各リンクに関する情報を示すリンクテーブルである。リンクテーブルにおける項目「リンク名」は、リンクの名称表す。例えば、交差点間の道路を示す。項目「ノード１」、「ノード２」は、それぞれそのリンクがつなぐノードを表す。ノードは例えば交差点を示す。今回は仮に、左、または上にあるノードを「ノード１」、他方のノードを「ノード２」とした。項目「コスト」は、そのリンクを通行するためのコストを表す。後に説明するが、フェーズが進むにつれて、状況に応じ項目「採用済み」は、そのリンクが、当該フェーズにおいて採用となった案内の、最適ルートに含まれるか否かを表す。項目「案内A」、「案内B」、「案内C」、「案内D」は、それぞれのリンクが、当該フェーズにおけるそれぞれの案内の最適ルートに含まれるか否かを表し、案内の数が増加した分の列が作成されることとなる。今回は、最適ルートに含まれるリンクには、該当するリンクの箇所にフラグを立てることとする。
【００１４】
図１４および図１５は、各ノードにおける、それぞれの目的地からの最適ルートのコスト、当該ノードの直前のリンクおよび直前のノードを表す。以降、目的地A/Bからの最適ルートを示す表である図１４を「ノードテーブルA/B」、目的地C/Dからの最適ルートを示す表である図１５を「ノードテーブルC/D」と呼ぶこととする。目的地A/Bから各ノードまでの最適ルートを表したのが図１４表２のノードテーブルA/B、目的地C/Dから各ノードまでの最適ルートを表したのが図１５のノードテーブルC/Dとなる。ここでは、図１４のノードテーブルA/Bの各項目に関して説明していく。項目「コスト」は、目的地A/Bから、最適ルートで各ノードに到達するまでにかかるコストを示す。項目「直前リンク」は、目的地A/Bから最適ルートで書くノードに到達する際に、直前に通行するリンクを示す。項目「直前ノード」は、目的地A/Bから最適ルートで書くノードに到達する際に、直前に通行するノードを示す。
なお、ここでは目的地ごとに別の表として定義したが、列を追加する形で１つの表としても問題ない。
【００１５】
図１６は、各案内の状態を示す状態テーブル」である。状態は図４の案内の状態遷移図に記載された４つの状態のいずれかとなる。以降の説明において、「案内の状態を遷移させる」との表現は、この表の該当する案内の項目の状態を書き換えることを意味する。
【００１６】
図１７は、今回の全体の処理における値を示す「処理値テーブル」である。項目「終了案内数」は、処理全体でいくつの案内の最適ルートを探索するかを示す。つまり、今回の例では、案内は４つあるが、この値を2にすれば、２つの案内の最適ルートを探索した段階で終了することも可能となる。項目「採用案内数」は、これまでに採用した案内数の累計を示す。初期値は０となる。また、以降の説明において、「採用案内数を増加させる」という表現は、この表の「採用案内数」の数を増加させることを意味する。項目「重複補正値」は、重複補正の際に、使用する値を示す。使用方法は、後に示すフローの解説の中で示す。
以上が、本実施形態の例における前提条件となる。
【００１７】
次に、図4の案内の状態遷移図、および図5、6、7の処理フロー図に基づいて、ルート探索を進めていく上でのフローを説明する。なお、本実施形態においては、案内を「未探索」４０１の状態として処理を開始する。
【００１８】
まず、ステップS５０１において、探索すべき案内に関して、状態が「未探索」４０１のものを特定し、そのうち任意の1つを選択する。ここでは例として、案内Aを選択したとして、以降の処理の説明を進める。
【００１９】
次に、ステップＳ５０２において、Ｓ５０１で選択した案内の目的地を探索の起点に設定する。なお、探索方法は、いわゆる一般的なダイクストラ法やA*法などを用いることを想定している。Ｓ５０１では例として案内Ａを選択したので、目的地A/Bを探索の起点として設定する。
【００２０】
次に、ステップＳ５０３において、Ｓ５０１で選択した案内の出発地を探索の終点に設定する。Ｓ５０１では例として案内Aを選択したので、出発地Aを探索の終点として設定する。
【００２１】
次に、ステップＳ５０４において、Ｓ５０１で選択した案内の目的地と同じ目的地を持つ「未探索」４０１状態の案内を検索し、S５０１で選択した案内と同じ目的地を持つ案内がある場合には、次は図５のS５０５を、ない場合には次は図５のS５０６実施する。Ｓ５０１では例として案内Ａを選択したので、案内Aの目的地である、目的地A/Bと同じ目的地を持つ案内があるかを判定する。目的地A/Bは、案内Bの目的地でもあり、案内Bは状態が「未探索」４０１であるため、案内Aと同じ目的地を持つ案内が存在することとなり、ここでは次に、S５０５を実施するように処理される。
【００２２】
次に、ステップS５０５において、S５０１で選択した案内と同一の目的地を持つ案内の出発地に関して、探索の終点に設定する。仮に該当する案内が複数ある場合には、複数の案内それぞれについて出発地を探索の終点に設定する。本実施形態では、S５０４で、S５０１で選択した案内Aと同一の目的地を持つ案内Bがあることが判明したため、案内Bの出発地である、出発地Bを探索の終点に設定する。
【００２３】
次に、ステップS５０６において、S５０２で設定した探索の起点から、S５０３、およびS５０５で設定した探索の終点までの最適ルートを探索する。本実施形態では、S５０２で探索の起点を目的地A/Bに、S５０３、およびS５０４で探索の終点を出発地A、および出発地Bと設定する。したがって、目的地A/Bを探索の起点として、出発地A、および出発地Bまでの最適ルートを探索する。探索の結果、図８に示すルートが、案内A、および案内Bにおける最適ルートとなった。すなわち、図中で矢印をつないだルートである。この結果を反映するため、リンクテーブルには図１８のように、各案内の最適ルートを構成するリンクにフラグを立てる。ノードテーブルA/Bには表７のように各ノードにおける最小コストと、最小コストとなるルートにおける直前のノード名を格納する。
【００２４】
次に、ステップS５０７において、S５０６でルート探索した全ての案内に関して、「未探索」４０１から「探索済」４０２に遷移させる。本実施形態では、S５０６で案内A、および案内Bのルートを探索したため、それら２つの案内に関して、状態を「探索済」４０２に遷移させる。
【００２５】
次に、ステップS５０８において、その時点で状態が「未探索」４０１の案内が存在するかを判定し、存在する場合には、次はS５０１を、存在しない場合には、S５０９を実施するよう処理する。本実施形態では、状態テーブルは図２０のようになっている。案内C、および案内Dの状態が「未探索」４０１であるため、S５０１が次に実施されることとなる。
【００２６】
本実施形態、ここからS５０１を再度実施する。S５０１からS５０８までの処理内容は説明済みであるため、今回の例における処理結果のみを述べる。S５０１にて、案内Cを選択したとする。S５０２にて、案内Cの目的地となる目的地C/Dを探索の起点に設定する。S５０３にて、案内Cの出発地となる出発地Cを探索の終点に設定する。S５０４にて、案内Cの目的地と同じ目的地を持つ案内Dがあるため、次にS５０５の処理を実施するよう判定される。S５０５にて、案内Dの出発地となる出発地Dを探索の終点に設定する。S５０６にて、案内C、および案内Dの最適ルートを探索する。探索結果は図９となる。
【００２７】
この結果を反映するため、図２１のようにリンクテーブルの案内C、案内Dの通行するリンクにフラグを立てる。また、図２２のようにノードテーブルC/Dの各ノードにおける最小コストと、最小コストとなるルートにおける直前のノード名を格納する。
【００２８】
S５０７にて、最適ルートを探索した案内C、および案内Dの状態を、「未探索」４０１から「探索済」４０２に遷移させる。  S５０８にて、各案内の状態は表１１のようになっている。案内A、案内B、案内C、案内Dの全ての状態が「探索済」４０２となっているため、状態が「未探索」４０１の案内は存在せず、次に図６のS５０９を実施するよう処理される。
【００２９】
ステップS５０９からは、再度処理内容を説明する。この処理では、状態が「探索済」４０２の案内のうち、最適ルートのコストが最小となっている案内を選択する。本実施形態では、案内Aのコストが「４５」、案内Bのコストが「５０」、案内Cのコストが「５３」、案内Dのコストが「４２」となる。そのため、案内Dを本実施形態では選択する。
【００３０】
次に、ステップS５１０では、選択した案内のリンクと、リンクテーブルの項目「採用済」とで論理和をとり、その結果をリンクテーブルの項目「採用済」に格納する。今回の例は、S５１０は初回となるため、選択した案内Dのリンクがそのままリンクテーブルの項目「採用済」に格納される。その結果は図２４のようになる。
【００３１】
次に、ステップS５１１において、現在選択している案内の状態を「探索済」４０２から「採用」４０３に遷移させる。本実施形態では、案内Dの状態を「採用」４０３に遷移されることになる。
【００３２】
次に、ステップS５１２において、採用案内数を１増加させる。今回の例では「採用案内数」は０であったので、この処理により１となる。次に、ステップS５１３において、下記（数１）が成立するかを判定する。
採用案内数  ＝  終了案内数…（数１）
（数１）が成立する場合には、各探索の完了、成立しない場合には、次にステップＳ５１４を実施するように処理される。本実施形態では、図２５のように、採用案内数は１、終了案内数は４となるため、（数１）は成立しない。従って、今回の例では、次にステップＳ５１４を実施するよう処理される。
【００３３】
次に、ステップＳ５１４において、状態が「探索済」４０２の案内が存在するか判定する。存在する場合にはステップＳ５１５を、存在しない場合にはステップＳ５１８を実施する。本実施形態では、図２６のように、案内A、案内B、案内Cの状態が「探索済」４０２の状態なので、次にステップＳ５１５を実施する。
【００３４】
次に、ステップＳ５１５において、状態が「探索済」４０２の案内のうち、最適ルートのコストが最小のものを選択する。本実施形態では、案内Aの最適ルートのコストが最小となるため、案内Aを選択する。
【００３５】
次にステップＳ５１６において、採用済リンクと選択済みリンクで重複があるかを判定する。重複がある場合にはステップＳ５１７、重複がない場合には次にステップS５１０に進む。本実施形態では、リンクテーブルにおける採用済みリンクと案内Aの最適ルートのリンクの重複の有無を判定する。ここでは図２４のようになっており、リンク１５が重複することが分かる。そこで、次にステップＳ５１７に進む。
【００３６】
次に、ステップＳ５１７において、選択した案内の状態を「棄却」４０４に遷移させる。本実施形態では、案内Aの状態を「棄却」４０４に遷移させる。本実施形態では、ここから再度Ｓ５１４からの処理を実施する。ここから再度ステップS５1４からステップＳ５１７までを実施するが、処理内容は説明済みであるため、処理結果のみを述べる。
【００３７】
Ｓ５１４において、各案内の状態は図２７のようになっており、案内B、および案内Cの状態が「探索済」４０２となっているため、次にＳ５１５の処理を実施されるよう判定する。そして、
Ｓ５１５において、案内Bを選択する。また、Ｓ５１６において、図２４を確認すると、採用済リンクと案内Bのリンクにおいては重複が無いため、次にS５１０に進む。  S５１０において、リンクテーブルにおいて、採用済みリンクと案内Bのリンクの論理和をとり、それをリンクテーブルの「採用済」に格納する。その結果は図２８のようになる。S５１１において、案内Bの状態を「採用」４０３に遷移させる。その結果は図２９のようになる。S５１２において、採用案内数を１増加させて２とする。その結果は図３０のようになる。S５１３において、（数１）を評価し、成立しないため、次にＳ５１４に進む。
【００３８】
Ｓ５１４において、各案内の状態は図29に示す内容であり、案内Cの状態が「探索済」４０２となっているため、次にＳ５１５に進む。次に、Ｓ５１５において、案内Cを選択する。Ｓ５１６において、現在のリンクテーブルは図２８に示す状態であり、採用済みリンクと案内Cのリンクにおいてリンク１２、１５、１８、１９、２０が重複するため、次にＳ５１７に進む。Ｓ５１７において、案内Cの状態を「棄却」４０３に遷移させる。結果は図３１のようになる。Ｓ５１４において、「探索済」４０２の状態となっている案内が存在していないため、次にステップＳ５１８に進む。
【００３９】
ステップＳ５１８からは、図７を用いて再度処理内容を説明する。この処理では、図１３の採用済に該当するリンクのコストを補正して、新たなコストを算出する。本実施形態では、補正する前のリンクのコストを「補正前リンクコスト」、補正した後のリンクのコストを「補正後リンクコスト」として、下記（数２）を採用済みリンクに該当する全てのリンクに対して実施する。補正前リンクコスト  x  重複補正値  ＝  補正後リンクコスト…（数２）
現在のリンクテーブルは図２８に示す状態であり、リンク７、８、１２、１３、１５、１８、１９、２０、２１、２４、２５、２６、２７が採用済みリンクに該当する。図３０より、重複補正値は２であると判断されるため、これら採用済みリンクのコストを2倍にし、それをこれ以降のコストとする。補正の結果は図３２のようになる。
【００４０】
次に、ステップＳ５１９において、状態について「棄却」４０４の案内を「未探索」４０１に遷移させる。本実施形態では、案内A、および案内Cの状態が「未探索」４０１に遷移されることとなる。ステップＳ５１９の処理の結果は図３３のようになる。
【００４１】
次に、ステップＳ５２０において、リンクテーブルの採用済みリンクと、状態が「未探索」４０１の案内のノードテーブルの直前リンクとで、一致する行を探索する。探索した結果、一致した行があれば、その行に格納された値を削除する。本実施形態では、状態が「未探索」４０１となっているのは、案内Aと案内Cになる。ここでは、案内Aを用いて説明する。案内Aは、目的地A/Bが目的となるため、ノードテーブルA/Bにおいて、採用済みリンクと一致する直前リンクを探索する。探索の結果、図３４において、太枠で囲まれた項目が採用済みリンクと一致する行となる。そのため、これらの行に格納された、項目「コスト」、項目「直前リンク」、項目「直前ノード」の値をクリアする。その結果は図３５のようになる。また、ノードテーブルC/Dでも同様の処理を行う。その結果は表２４のようになる。
【００４２】
次に、ステップＳ５２１において、各ノードテーブルにおいて、ステップＳ５２０、あるいはステップＳ５２２の処理でクリアした行のノードと、項目「直前ノード」が一致する行があるかを判定する。一致する行がある場合には、次にステップＳ５２２に進み、一致する行が無い場合には、次にステップＳ５２３に進む。本実施形態では、ノードテーブルA/Bで考える。このとき、ステップＳ５２０でクリアされた行のノードと、項目「直前ノード」が一致するノードは、図３７の太枠で囲まれた行となる。したがって、次にステップＳ５２２に進む。
【００４３】
次に、ステップＳ５２２において、ステップＳ５２１で該当すると判断された行をクリアする。本実施形態では、図３７において太枠で囲まれた行がクリアされる。
【００４４】
次に、再度ステップＳ５２１の処理を実施する。ここでは、ステップＳ５２２でクリアした行のノードと、項目「直前ノード」が一致する行があるかを判定する。本実施形態では、図３８において太枠に囲まれた行が該当する。次にステップＳ５２２の処理を実施するよう処理される。
【００４５】
これらステップＳ５２１とステップＳ５２２を該当行がなくなるまで繰り返す。その結果、最終的にノードテーブルA/Bは図３９、ノードテーブルC/Dは図４０のようになる。この状態になったところでステップＳ５２１において、該当する行が無くなり、次にステップＳ５２３を実施するよう処理される。
【００４６】
次に、ステップＳ５２３において、リンクテーブルにおいて、項目「採用済みリンク」、および状態が「未探索」４０１に該当する案内の列をクリアする。本実施形態では、「採用済みリンク」、案内Aの列、案内Cの列がクリアされる。その結果は図４１のようになる。なお、ステップS５０１から、このステップＳ５２３までの一連のフローを「フェーズ」と定義する。ステップＳ５２３の処理が完了することでそのフェーズが完了したこととなる。本実施形態では、第一フェーズがこの処理で完了したこととなる。ステップＳ５２３が完了した次には、再度ステップS５０１を実施するため、そこから次の第二フェーズが開始されることとなる。
【００４７】
次に、第二フェーズに入り、再度ステップS５０１から処理を実施する。ここからは第一フェーズとの違いに絞って各ステップを説明していく。本実施形態では、案内A、および案内Cの状態が「未探索」４０１である。ここでは、案内Aを選択したとする。
次に、ステップS５０２において、目的地A/Bを探索起点に設定する。
次に、ステップS５０３において、出発地Aを探索終点に設定する。
次に、ステップS５０４において、案内Aと同一の目的地を持つ、状態が「未探索」４０１の案内があるか検索する。今回、案内Aと同一の目的地を持つ案内Bは、状態４０４「採用」となっているため、該当しない。案内Cは目的地が異なるため、こちらも該当しない。したがって、今回の例では、同一の目的地を持つ、「未探索」状態の案内は存在しないため、次にステップS５０６に進む。
【００４８】
次に、ステップS５０６において、案内Aの最適ルートを探索する。第一フェーズから、各リンクのコストが変化しているため、変化している部分に関して、再度探索する。探索の結果は、図１０のようになる。また、それを反映したリンクテーブルは図４２、ノードテーブルA/Bは図４３のようになる。
【００４９】
次に、ステップS５０７において、案内Aの状態を「探索済」４０２に遷移させる。
次に、ステップS５０８において、状態が「未探索」４０１の案内が存在するか検索する。本実施形態では、案内Cの状態が「未探索」４０１であるため、次に再度ステップS５０１からステップS５０７までを実施する。処理内容は、案内Aと同様であるため、結果のみを示す。案内Cの探索の結果は、図１１のようになる。また、それを反映したリンクテーブルは図４４、ノードテーブルC/Dは図４５のようになる。
【００５０】
次に、ステップS５０８において、状態が「未探索」４０１の案内が存在するか検索する。現状の状態テーブルは図４６のようになり、状態が「未探索」４０１の案内は存在しないため、次にステップS５０９に進む。
【００５１】
次に、ステップS５０９において、状態が「探索済」４０２の案内のうち、コストが最小となる案内を選択する。本実施形態では、案内Aがそれに該当するため、案内Aを選択する。
【００５２】
次に、ステップS５１０において、リンクテーブルの項目「採用済みリンク」に格納する。結果は、図４７のようになる。
次に、ステップS５１１において、案内Aの状態を「採用」４０３に遷移させる。結果は、図４８のようになる。
次に、ステップS５１２において、採用案内数を1増加させ、３とする。結果は図４９のようになる。
次に、ステップＳ５１３において、（数１）が成立するかを判定する。終了案内数は４、採用案内数は３であるため、成立しない。したがって、次にステップＳ５１４に進む。
【００５３】
次に、ステップＳ５１４において、状態が「探索済」４０２の案内が存在するかを判定する。現状、案内Ｃの状態が「探索済」４０２であるため、次にステップＳ５１５に進む。
次に、ステップＳ５１５において、状態が「探索済」４０２である案内Ｃが選択される。
次に、ステップＳ５１６において、案内Ｃと採用済みリンクで重複があるかを判定する。現状リンクテーブルは図４７のようになっており、Ｌ１０、Ｌ１１において重複する。したがって、次にステップＳ５１７に進む。
【００５４】
次に、ステップＳ５１７において、案内Ｃの状態を「棄却」４０４に遷移させる。結果は、図５０のようになる。
次に、ステップＳ５１４において、状態が「探索済」４０２となっている案内は無いと判断し、次にステップＳ５１８に進む。
次に、ステップＳ５１８において、採用済みリンクに再度重複補正をかける。重複補正をかけるリンクは、図４７において採用済みリンクにフラグが立っている、Ｌ０１、０２、０５、１０、１１、１５、２１に対して（数２）を実施する。結果は、図５１のようになる。
次に、ステップＳ５１９において、案内Ｃの状態を「未探索」４０１に遷移させる。結果は、図５２のようになる。
【００５５】
次に、ステップS５２０において、採用済みリンクとノードテーブルC/Dの直前リンクが一致する行をクリアする。採用済みリンクはＬ０１、０２、０５、１０、１１、１５、２１であったので、結果は図５３のようになる。なお、案内A、および案内Bの状態が「未探索」４０１ではない。そのため、案内A、およびBの目的地からのコストを格納したノードテーブルA/Bにはこの処理は必要なく、ここでは実施しない。
次に、ステップS５２１とステップS５２２において、クリアしたノード行と直前ノードが一致した行をクリアしていく。最終的には、図５４のようになる。ここで、ノードN０３、N０８に関しては、クリアされなかったが、これはコスト補正後でも最適ルート、およびそのコストが変化しないノードになる。そのため、これらの値は次フェーズにおいても利用する。
【００５６】
次に、ステップ５２３において、リンクテーブルにおける採用済みリンクと、案内Cのフラグをクリアする。結果は図５５のようになる。ここで、第二フェーズ完了となる。
次に、第三フェーズに入り、ステップS５０１において、状態が「未探索」４０１である案内Cを選択する。
次に、ステップS５０２において、目的地C/Dを探索起点に設定する。
次に、ステップS５０３において、出発地Cを探索終点に設定する。
次に、ステップS５０４において、他に状態が「未探索」４０１かつ同じ目的地を持つ案内が存在しないと判断され、次にステップS５０６に進む。
【００５７】
次に、ステップS５０６において、案内Cの最適ルートを探索する。その結果、図12のようになる。また、それを反映したリンクテーブルは図５６、ノードテーブルC/Dは図５７のようになる。
【００５８】
次に、ステップS５０７において、案内Cの状態を「探索済」４０２に遷移させる。その結果、図５８のようになる。
次に、ステップS５０８において、状態が「未探索」４０１の案内は存在しないため、次にS５０９に進む。
次に、ステップS５０９において、案内Cを選択する。
次に、ステップS５１０において、案内Cで通行するリンクと採用済みリンクの論理和をとって、採用済みリンクに格納する。その結果、図５９のようになる。
次に、ステップS５１１において、案内Cの状態を「採用」４０３に遷移させる。その結果、図６０のようになる。
【００５９】
次に、ステップS５１２において、採用案内数を1増加させる。その結果、図６１のようになる。
次に、ステップS５１３において、（数１）が成立するか判断する。採用案内数が４、終了案内数が４となり、(数１)が成立するため、各案内の探索が完了となる。
以上が経路探索の全体のフローとなる。
【００６０】
なお、案内の状態遷移は一例であり、状態遷移の条件を変更することで、同じ案内に対して、別のルートを採用することも可能となる。
また、重複補正値を定数として説明したが、関数などで表すことで、状況に合わせた補正をかけることも可能となる。
【符号の説明】
【００６１】
１０１…処理部、１０２…条件入力部、１０３…出力部、１０４…条件補正部、１０５…道コスト算出部、１０６…ルートコスト算出部、１０７…地図データ、１０８…ルート作用判定部
【図１】
2017190964.tif 000003
【図２】
2017190964.tif 000004
【図３】
2017190964.tif 000005
【図４】
2017190964.tif 000006
【図５】
2017190964.tif 000007
【図６】
2017190964.tif 000008
【図７】
2017190964.tif 000009
【図８】
2017190964.tif 000010
【図９】
2017190964.tif 000011
【図１０】
2017190964.tif 000012
【図１１】
2017190964.tif 000013
【図１２】
2017190964.tif 000014
【図１３】
2017190964.tif 000015
【図１４】
2017190964.tif 000016
【図１５】
2017190964.tif 000017
【図１６】
2017190964.tif 000018
【図１７】
2017190964.tif 000019
【図１８】
2017190964.tif 000020
【図１９】
2017190964.tif 000021
【図２０】
2017190964.tif 000022
【図２１】
2017190964.tif 000023
【図２２】
2017190964.tif 000024
【図２３】
2017190964.tif 000025
【図２４】
2017190964.tif 000026
【図２５】
2017190964.tif 000027
【図２６】
2017190964.tif 000028
【図２７】
2017190964.tif 000029
【図２８】
2017190964.tif 000030
【図２９】
2017190964.tif 000031
【図３０】
2017190964.tif 000032
【図３１】
2017190964.tif 000033
【図３２】
2017190964.tif 000034
【図３３】
2017190964.tif 000035
【図３４】
2017190964.tif 000036
【図３５】
2017190964.tif 000037
【図３６】
2017190964.tif 000038
【図３７】
2017190964.tif 000039
【図３８】
2017190964.tif 000040
【図３９】
2017190964.tif 000041
【図４０】
2017190964.tif 000042
【図４１】
2017190964.tif 000043
【図４２】
2017190964.tif 000044
【図４３】
2017190964.tif 000045
【図４４】
2017190964.tif 000046
【図４５】
2017190964.tif 000047
【図４６】
2017190964.tif 000048
【図４７】
2017190964.tif 000049
【図４８】
2017190964.tif 000050
【図４９】
2017190964.tif 000051
【図５０】
2017190964.tif 000052
【図５１】
2017190964.tif 000053
【図５２】
2017190964.tif 000054
【図５３】
2017190964.tif 000055
【図５４】
2017190964.tif 000056
【図５５】
2017190964.tif 000057
【図５６】
2017190964.tif 000058
【図５７】
2017190964.tif 000059
【図５８】
2017190964.tif 000060
【図５９】
2017190964.tif 000061
【図６０】
2017190964.tif 000062
【図６１】
2017190964.tif 000063