(57)【要約】【課題】１以上の評価指標を持つ部分問題から得られる部分経路を組み合わせた経路を抽出する場合に、部分問題の適切な制約条件を少ない計算量で算出する。【解決手段】ネットワークにおける始点ノードから終点ノードまでの最短経路を探索する最短経路探索部と、前記最短経路探索部により探索された前記最短経路の第１のコストと、前記始点ノードと前記終点ノードとを結ぶ直線の第２のコストとを算出するコスト算出部と、前記コスト算出部により算出された前記第１のコストと前記第２のコストとに基づいて、所定の第１の近似式が妥当であるか否かを判定する判定部と、前記判定部により前記第１の近似式が妥当であると判定された場合、前記ネットワークに含まれる第１のノードと第２のノードとの間の経路を示す部分経路を探索するための部分問題であって、１以上の評価指標を持つ部分問題における制約条件を、前記第１の近似式を用いて決定する決定部とを有する。【選択図】図９
2018137724.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークにおける始点ノードから終点ノードまでの最短経路を探索する最短経路探索部と、
前記最短経路探索部により探索された前記最短経路の第１のコストと、前記始点ノードと前記終点ノードとを結ぶ直線の第２のコストとを算出するコスト算出部と、
前記コスト算出部により算出された前記第１のコストと前記第２のコストとに基づいて、所定の第１の近似式が妥当であるか否かを判定する判定部と、
前記判定部により前記第１の近似式が妥当であると判定された場合、前記ネットワークに含まれる第１のノードと第２のノードとの間の経路を示す部分経路を探索するための部分問題であって、１以上の評価指標を持つ部分問題における制約条件を、前記第１の近似式を用いて決定する決定部と、
を有する経路探索装置。
【請求項２】
前記決定部により決定された前記制約条件を用いた前記部分問題を解くことで前記部分経路を探索する部分経路探索部と、
前記部分経路探索部により探索された前記部分経路を組み合わせることで、前記始点ノードから前記終点ノードまでの経路を探索する経路探索部と、
を有する請求項１に記載の経路探索装置。
【請求項３】
前記経路探索部は、
前記始点ノードと前記終点ノードとの間の最短経路上のノードと、前記始点ノード及び前記終点ノードを結ぶ直線との距離に基づいて、前記決定部による決定に用いられる探索領域を定義し、
前記決定部は、
前記経路探索部により定義された前記探索領域に含まれる前記第１のノードと前記第２のノードとの間の前記部分経路を探索するための前記制約条件を決定する、請求項２に記載の経路探索装置。
【請求項４】
前記経路探索装置は、
前記経路探索部により前記探索領域を定義した場合、前記コスト算出部による前記第１のコスト及び前記第２のコストの算出と、前記判定部による前記第１の近似式が妥当であるか否かの判定とを行わず、
前記決定部は、
前記制約条件を前記第１の近似式を用いて決定する、請求項３に記載の経路探索装置。
【請求項５】
前記決定部は、
前記制約条件を、前記第１のノードと前記第２のノードとの間の直線距離を前記第１の近似式で近似した値に、予め設定された所定の設定コストを加算することで決定する、請求項１乃至４の何れか一項に記載の経路探索装置。
【請求項６】
前記設定コストは、前記部分経路の探索において遠回りをした場合に許容されるコストである、請求項５に記載の経路探索装置。
【請求項７】
前記決定部は、
前記判定部により前記第１の近似式が妥当でないと判定された場合、前記部分問題における制約条件を、前記第１の近似式とは異なる所定の第２の近似式を用いて決定する、請求項１乃至６の何れか一項に記載の経路探索装置。
【請求項８】
前記判定部は、
前記第２のコストを前記第１の近似式で近似した値から前記第１のコストを減算した値が、予め設定された基準値より大きいか否かを判定することで、前記第１の近似式が妥当であるか否かを判定する、請求項１乃至７の何れか一項に記載の経路探索装置。
【請求項９】
ネットワークにおける始点ノードから終点ノードまでの最短経路を探索する最短経路探索手順と、
前記最短経路探索手順により探索された前記最短経路の第１のコストと、前記始点ノードと前記終点ノードとを結ぶ直線の第２のコストとを算出するコスト算出手順と、
前記コスト算出手順により算出された前記第１のコストと前記第２のコストとに基づいて、所定の第１の近似式が妥当であるか否かを判定する判定手順と、
前記判定手順により前記第１の近似式が妥当であると判定された場合、前記ネットワークに含まれる第１のノードと第２のノードとの間の経路を示す部分経路を探索するための部分問題であって、１以上の評価指標を持つ部分問題における制約条件を、前記第１の近似式を用いて決定する決定手順と、
をコンピュータが実行する経路探索方法。
【請求項１０】
ネットワークにおける始点ノードから終点ノードまでの最短経路を探索する最短経路探索手順と、
前記最短経路探索手順により探索された前記最短経路の第１のコストと、前記始点ノードと前記終点ノードとを結ぶ直線の第２のコストとを算出するコスト算出手順と、
前記コスト算出手順により算出された前記第１のコストと前記第２のコストとに基づいて、所定の第１の近似式が妥当であるか否かを判定する判定手順と、
前記判定手順により前記第１の近似式が妥当であると判定された場合、前記ネットワークに含まれる第１のノードと第２のノードとの間の経路を示す部分経路を探索するための部分問題であって、１以上の評価指標を持つ部分問題における制約条件を、前記第１の近似式を用いて決定する決定手順と、
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索装置、経路探索方法、及びプログラムに関する。
【背景技術】
【０００２】
ネットワークに対して追加されるリンクについて、災害による影響が相対的に小さくなるような物理経路の選択を支援することができる経路探索手法が知られている（非特許文献１）。非特許文献１では、経路探索の対象となる始点と終点との間に適当な間隔で碁盤の目（格子）を設定し、各格子の頂点（格子点）付近の設備（ノード）を代表として選択する。そして、代表として選択したノード間について経路長が最小となる経路を探索する部分問題を設定し、これらの部分問題から得られた格子間の経路（部分経路）を複数組み合わせることで、全体の経路を探索している。
【０００３】
災害による影響は被災範囲に含まれる経路長の長さに依存するため、非特許文献１では、経路の経路長が短くなるほど災害の影響は相対的に小さくなるとしている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】P. N. Tran and H. Saito, "Enhancing Physical Network Robustness Against Earthquake Disasters With Additional Links," in Journal of Lightwave Technology, vol. 34, no. 22, pp. 5226-5238, Nov.15, 15 2016. doi: 10.1109/JLT.2016.2607171
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、非特許文献１では、経路の評価指標が経路長であるため、単一の地震や災害による直接的な影響しか考慮できていない。このため、実際の地震において特にネットワーク設備に対して甚大な影響を与える二次災害（例えば、地震による津波や土砂災害等）によって設備が故障した場合における復旧のし易さや二次災害の回避のし易さを考慮した経路抽出を行うことができなかった。
【０００６】
例えば、図１は、非特許文献１の経路探索手法により、始点ノードＳと代表ノードとの間の最小経路探索を行う部分問題１と、代表ノードと終点ノードＤとの間の最小経路探索を行う部分問題２とでそれぞれ得られた部分経路を組み合わせて、始点ノードＳと終点ノードＤとの間の経路を抽出した例を示している。非特許文献１の経路探索手法では、経路長のみで評価された経路が抽出されているため、例えば津波エリアを通過するか否かについての評価は行われていない。このため、図１に示すように、津波エリアを通過する経路が抽出される場合があり、二次災害を考慮した場合に必ずしも最適な経路が抽出されるとは限らない。
【０００７】
そのため、二次災害を考慮した場合、１以上の評価指標（例えば、津波エリアに含まれるリンク数やリンクの被災率等）を１以上の目的関数より算出して経路を探索できるような、１以上の目的関数に対応した経路探索アルゴリズムにより経路探索を行うことが好ましい。
【０００８】
経路長以外の評価指標に対応した経路探索アルゴリズムは、一般に、目的関数値の最良化を行い、経路長等のコストの多寡は考慮しない。このため、一般に、上限となる経路長等のコストを経路探索の制約条件として、評価指標を計算する目的関数とは別に与えることとなる。したがって、制約条件とは、目的関数を最良化するにあたって、どれだけコストを掛けても良いか（すなわち、どれだけ遠回りしても良いか等）を示す条件となる。
【０００９】
しかしながら、上記のような経路探索アルゴリズムを部分問題に適用する場合、部分問題に制約条件を設定する必要があるが、制約条件が大き過ぎると必要以上に遠回りする経路（長い経路やコストが高い経路等）が算出されてしまう。一方で、制約条件が小さ過ぎると制約条件により探索が打ち切られ、経路が発見できない場合がある。
【００１０】
このため、上記のような経路探索アルゴリズムを部分問題に適用する場合、適切な制約条件の設定が必要となる。また、当該部分問題は膨大数存在するため、実用的な計算時間で適切な制約条件を決定する必要がある。
【００１１】
本発明は、上記の点に鑑みてなされたものであって、１以上の評価指標を持つ部分問題から得られる部分経路を組み合わせた経路を抽出する場合に、部分問題の適切な制約条件を少ない計算量で算出することを目的とする。
【課題を解決するための手段】
【００１２】
上記課題を解決するため、ネットワークにおける始点ノードから終点ノードまでの最短経路を探索する最短経路探索部と、前記最短経路探索部により探索された前記最短経路の第１のコストと、前記始点ノードと前記終点ノードとを結ぶ直線の第２のコストとを算出するコスト算出部と、前記コスト算出部により算出された前記第１のコストと前記第２のコストとに基づいて、所定の第１の近似式が妥当であるか否かを判定する判定部と、前記判定部により前記第１の近似式が妥当であると判定された場合、前記ネットワークに含まれる第１のノードと第２のノードとの間の経路を示す部分経路を探索するための部分問題であって、１以上の評価指標を持つ部分問題における制約条件を、前記第１の近似式を用いて決定する決定部と、を有する。
【発明の効果】
【００１３】
１以上の評価指標を持つ部分問題から得られる部分経路を組み合わせた経路を抽出する場合に、部分問題の適切な制約条件を少ない計算量で算出することができる。
【図面の簡単な説明】
【００１４】
【図１】従来技術により抽出される経路の一例を説明する図である。
【図２】本発明の実施の形態における経路探索装置の構成の一例を示す図である。
【図３】本発明の実施の形態における経路探索装置のハードウェア構成の一例を示す図である。
【図４】本発明の実施の形態における演算部の機能構成の一例を示す図である。
【図５】第二近似式を用いる必要がある場合の一例を説明する図である。
【図６】本発明の実施の形態における第一近似式の妥当性判定処理の一例を示すフローチャートである。
【図７】本発明の実施の形態におけるコスト制約条件の決定処理の一例を示すフローチャートである。
【図８】本発明の実施の形態におけるコスト制約条件の決定処理の他の例を示すフローチャートである。
【図９】制約条件決定処理部により決定されるコスト制約条件を説明する図である。
【図１０】本発明の実施の形態における経路探索処理の一例を示すフローチャートである。
【図１１】探索対象外の設備を起点するノードの一例を示す図である。
【図１２】本発明の実施の形態における探索領域の定義処理の一例を示すフローチャートである。
【図１３】最短経路が通過するノードと、直線ＳＤとの距離の一例を示す図である。
【図１４】矩形領域の一例を示す図である。
【図１５】矩形領域の辺の長さを切り上げる補正の一例を示す図である。
【図１６】矩形領域の辺の長さに対してマージンＭを追加する補正の一例を示す図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００１６】
＜経路探索装置１０の構成＞
まず、本発明の実施の形態における経路探索装置１０の構成について、図２を参照しながら説明する。図２は、本発明の実施の形態における経路探索装置１０の構成の一例を示す図である。
【００１７】
図２に示す経路探索装置１０は、１以上の評価指標を持つ部分問題により部分経路を探索して、探索した部分経路を組み合わせることで、二次災害による影響も考慮した経路を出力する１以上のコンピュータである。また、経路探索装置１０は、当該部分問題毎に、上限となる経路長等のコストを示す制約条件（以降、「コスト制約条件」と表す。）Ｃを決定する。
【００１８】
図２に示す経路探索装置１０は、入力部１００と、演算部２００と、出力部３００とを有する。これら各部は、経路探索装置１０にインストールされた１以上のプログラムが、後述する（Central Processing Unit）５０７に実行させる処理により実現される。
【００１９】
また、図２に示す経路探索装置１０は、データ記憶部４００を有する。データ記憶部４００は、後述する補助記憶装置５０８やＲＡＭ（Random Access Memory）５０５等を用いて実現可能である。なお、データ記憶部４００は、例えば、経路探索装置１０とネットワークを介して接続される記憶装置等を用いて実現されていても良い。
【００２０】
入力部１００は、各種情報を入力する。入力部１００に入力される情報には、例えば、ネットワーク情報、始終点ノード情報、評価指標情報、優先度情報、第一近似式ｆ１、第二近似式ｆ２、安全係数Ｆｓ、及び遠回り許容量Ｒ等がある。これらの情報のうち、第一近似式ｆ１、第二近似式ｆ２、安全係数Ｆｓ、及び遠回り許容量Ｒについては後述する。
【００２１】
ネットワーク情報とは、ネットワークを構成するノード及びリンクに関する情報である。ノードには、例えば、ルータ、ビル、マンホール、電柱等が挙げられる。リンクには、ケーブル、とう道、共同溝、管路等が挙げられる。なお、ネットワークは、電気通信ネットワークの他、例えば、道路網、鉄道網、電力網、水道網、ガス網等の種々のネットワークであっても良い。
【００２２】
ネットワーク情報には、属性情報を付与することができる。属性情報には、例えば、位置情報（緯度及び経度情報）、リンクの長さ（ケーブルの長さ、とう道の長さ、共同溝の長さ、管路の長さ等）、設備（ビル、電柱、管路等）の被災率、災害（津波、土砂災害、洪水、液状化、雪崩、落雷、火山噴火等）エリアの有無等が挙げられる。
【００２３】
始終点ノード情報は、ネットワークの経路探索における始点及び終点となるノードを示す情報である。以降では、ネットワークの経路探索における始点ノードを「始点ノードＳ」、当該経路探索における終点ノードを「終点ノードＤ」と表す。
【００２４】
評価指標情報は、評価指標を算出する１以上の目的関数（多目的関数）に関する情報である。目的関数には、例えば、ネットワーク設備のコスト（設備自体のコスト、設置コスト、保守コスト等）、設備の被災率、災害エリアに含まれる設備の数や長さ等が挙げられる。優先度情報は、１以上の目的関数の優先度に関する情報である。
【００２５】
演算部２００は、コスト制約条件Ｃの決定と、決定されたコスト制約条件Ｃが設定された部分問題による部分経路の算出及び当該部分経路を組み合わせた経路（始点ノードＳから終点ノードＤまでの経路）の作成とを行う。演算部２００の詳細な機能構成については後述する。
【００２６】
出力部３００は、演算部２００により作成された経路を、例えば後述する表示装置５０２に出力する。
【００２７】
データ記憶部４００は、入力部１００が入力した各種情報を記憶する。また、データ記憶部４００は、例えば部分経路の探索途中における計算データやキャッシュ等の中間データも記憶する。
【００２８】
なお、図２に示す経路探索装置１０の構成は、一例であって、他の構成であっても良い。例えば、図２に示す経路探索装置１０は、複数台のコンピュータで構成されていても良い。
【００２９】
＜経路探索装置１０のハードウェア構成＞
次に、経路探索装置１０のハードウェア構成について、図３を参照しながら説明する。図３は、本発明の実施の形態における経路探索装置１０のハードウェア構成の一例を示す図である。
【００３０】
図３に示すように、経路探索装置１０は、入力装置５０１と、表示装置５０２と、外部Ｉ／Ｆ５０３と、通信Ｉ／Ｆ５０４と、ＲＡＭ５０５と、ＲＯＭ（Read Only Memory）５０６と、ＣＰＵ５０７と、補助記憶装置５０８とを有する。これら各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。
【００３１】
入力装置５０１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置５０２は、例えばディスプレイ等であり、経路探索装置１０の処理結果を表示する。なお、入力装置５０１及び表示装置５０２の少なくとも一方は、必要なときに経路探索装置１０に接続して利用する形態であっても良い。
【００３２】
外部Ｉ／Ｆ５０３は、外部装置とのインタフェースである。外部装置には、記録媒体５０３ａ等がある。経路探索装置１０は、外部Ｉ／Ｆ５０３を介して記録媒体５０３ａ等の読み取りや書き込みを行うことができる。
【００３３】
記録媒体５０３ａには、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等がある。
【００３４】
通信Ｉ／Ｆ５０４は、経路探索装置１０をネットワークに接続するためのインタフェースである。
【００３５】
ＲＡＭ５０５は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ５０６は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ５０６には、例えば、ＯＳ（Operating System）設定やネットワーク設定等が格納されている。
【００３６】
ＣＰＵ５０７は、ＲＯＭ５０６や補助記憶装置５０８等からプログラムやデータをＲＡＭ５０５上に読み出して処理を実行する演算装置である。
【００３７】
補助記憶装置５０８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置５０８に格納されているプログラムやデータには、例えば、ＯＳ、当該ＯＳ上において各種機能を実現するアプリケーションソフトウェア、本実施形態に係る各種処理を実現するプログラム等がある。
【００３８】
本実施形態に係る経路探索装置１０は、図３に示すハードウェア構成を有することにより、後述する各種処理を実現することができる。
【００３９】
＜演算部２００の機能構成＞
次に、演算部２００の機能構成について、図４を参照しながら説明する。図４は、本発明の実施の形態における演算部２００の機能構成の一例を示す図である。
【００４０】
図４に示すように、演算部２００は、制約条件決定処理部２１０と、経路探索処理部２２０とを有する。制約条件決定処理部２１０は、部分問題毎に、コスト制約条件Ｃを決定するための処理を行う。経路探索処理部２２０は、制約条件決定処理部２１０により部分問題毎に決定されたコスト制約条件Ｃを用いて、部分経路の算出及び当該部分経路を組み合わせた経路（始点ノードＳから終点ノードＤまでの経路）の作成を行う。
【００４１】
ここで、制約条件決定処理部２１０は、最短経路型経路探索部２１１と、コスト算出部２１２と、近似式妥当性判定部２１３と、部分ノード組直線距離算出部２１４と、制約条件決定部２１５とを有する。
【００４２】
最短経路型経路探索部２１１は、始点ノードＳと終点ノードＤとの間の最短経路を探索する。最短経路型経路探索部２１１は、例えば、ｋ−ｓｈｏｒｔｅｓｔ−ｐａｔｈアルゴリズム、経路長を目的関数としたダイクストラ法等を用いて、当該最短経路を探索する。
【００４３】
コスト算出部２１２は、最短経路型経路探索部２１１が探索した経路の最小コストＬｃを算出する。また、コスト算出部２１２は、始点ノードＳ及び終点ノードＤ間を地理空間的に直線で結んだ場合の直線コストＬｄを算出する。最小コストＬｃは、経路上における始点ノードＳから終点ノードＤまでの距離に限られず、例えば、経路上における始点ノードＳから終点ノードＤまでの費用等であっても良い。
【００４４】
近似式妥当性判定部２１３は、直線コストＬｄと、最小コストＬｃと、安全係数Ｆｓとに基づいて、第一近似式ｆ１が妥当であるか否かを判定する。
【００４５】
第一近似式ｆ１は、コスト制約条件Ｃを決定するための関数であり、経路の探索領域に依らずに、コスト制約条件Ｃを決定するために一般的に使用可能な近似式である。一方で、第一近似式ｆ１が妥当でない場合には、コスト制約条件Ｃを決定するために、第二近似式ｆ２が使用される。第二近似式ｆ２は、第一近似式ｆ１と同様に、コスト制約条件Ｃを決定するための関数である。
【００４６】
また、安全係数Ｆｓとは、第一近似式ｆ１の妥当性を判定する際の厳格さを設定するために任意に設定される０以上の値である。
【００４７】
更に、第一近似式ｆ１が妥当でない場合とは、始点ノードＳから終点ノードＤへの経路を探索するための探索領域内に、例えば、局所的な遠回りが発生するような場合である。一方で、第一近似式ｆ１が妥当である場合とは、上記のような局所的な遠回りが発生しないような場合である。
【００４８】
部分ノード組直線距離算出部２１４は、経路探索処理部２２０により選択されたノードの組（以降では、「部分ノード組」と表す。）に含まれるそれぞれのノード間を地理空間的に直線で結んだ場合の直線コストＬｐを算出する。部分問題の解は、部分ノード組のそれぞれのノード間の経路（部分経路）である。以降では、部分ノード組に含まれるノードのうち、部分経路の始点となるノードを「始点ノードｓ」、当該部分経路の終点となるノードを「終点ノードｄ」と表す。また、部分経路を探索する領域を「部分探索領域」と表す。部分探索領域は、始点ノードＳから終点ノードＤへの経路を探索するための探索領域に含まれる所定の領域である。
【００４９】
制約条件決定部２１５は、近似式妥当性判定部２１３による判定結果（第一近似式ｆ１妥当性）と、部分ノード組直線距離算出部２１４により算出された直線コストＬｐと、遠回り許容量Ｒとに基づいて、コスト制約条件Ｃを決定する。
【００５０】
制約条件決定部２１５は、第一近似式ｆ１妥当性が「妥当」である場合、第一近似式ｆ１を用いてコスト制約条件Ｃを決定する。一方で、制約条件決定部２１５は、第一近似式ｆ１妥当性が「妥当」でない場合、第二近似式ｆ２を用いてコスト制約条件Ｃを決定する。
【００５１】
遠回り許容量Ｒは、例えば、経路探索装置１０のユーザにより予め設定される値であり、二次災害による災害エリア（例えば津波エリアや土砂災害エリア等）を回避するために、どの程度の遠回りを許容するかを示す値である。遠回り許容量Ｒは、例えば、始終点ノード情報の入力前に決定される。遠回り許容量Ｒは、例えば、どのくらいコストを掛けて被災率を低減するか等を考慮して決定される。
【００５２】
＜第一近似式ｆ１及び第二近似式ｆ２＞
ここで、第一近似式ｆ１及び第二近似式ｆ２の具体例について説明する。
【００５３】
第一近似式ｆ１は、ｆ１（Ｌｐ）＝Ａ×Ｌｐ＋Ｂで表すことができる。ここで、Ａ及びＢは、例えば、Ａ＝１．６２８、Ｂ＝１０００．０である。ただし、Ａ及びＢの具体的な値は、ネットワークの特性等に応じて異なる。
【００５４】
また、第二近似式ｆ２は、ｆ２（Ｌｐ）＝Ａ×Ｌｐ＋Ｒｃで表すことができる。ここで、Ｒｃは、必要遠回り距離であり、例えば、局所的に山等があることにより最低限遠回りが必要となる距離のことである。Ｒｃは、Ｒｃ＝Ｌｃ−Ｌｄで表すことができる。
【００５５】
ここで、コスト制約条件Ｃの決定に第二近似式ｆ２を用いる必要がある場合について、図５を参照しながら説明する。図５は、第二近似式ｆ２を用いる必要がある場合の一例を説明する図である。
【００５６】
図５に示すように、始点ノードＳから終点ノードＤまでの探索領域内で経路を探索する場合について説明する。なお、探索領域内における長方形の各領域は部分探索領域である。
【００５７】
図５に示すように、当該探索領域内に山があるため、局所的な遠回りが発生する。この場合、第一近似式ｆ１では、各部分探索領域内で部分経路を探索できない（すなわち、部分問題の解が出ない）場合がある。この場合、第一近似式ｆ１における項ＢをＲｃに置き換えた第二近似式ｆ２を用いることで、部分問題の解を算出することができる。なお、Ｒｃは、上述したように、経路上の最小コストＬｃ（すなわち、例えば、経路上に沿った距離の合計）から直線コストＬｄ（すなわち、例えば、始点ノードＳから終点ノードＤまでの直線距離）を減算した値である。
【００５８】
＜第一近似式ｆ１の妥当性判定処理＞
まず、始点ノードＳから終点ノードＤまでの経路を探索するための探索領域において、第一近似式ｆ１を用いてコスト制約条件Ｃを決定することが妥当であるか否かを判定するための処理について、図６を参照しながら説明する。図６は、本発明の実施の形態における第一近似式ｆ１の妥当性判定処理の一例を示すフローチャートである。
【００５９】
まず、最短経路型経路探索部２１１は、始点ノードＳと終点ノードＤとをデータ記憶部４００から取得する（ステップＳ１０１）。なお、始点ノードＳ及び始点ノードＤは、入力部１００が入力した始終点ノード情報に含まれる。
【００６０】
次に、最短経路型経路探索部２１１は、始点ノードＳと終点ノードＤとの間で最短経路となる１以上の経路を探索する（ステップＳ１０２）。
【００６１】
次に、コスト算出部２１２は、最短経路型経路探索部２１１が探索した１以上の経路のうちの最小コストＬｃを算出する（ステップＳ１０３）。最小コストＬｃは、最短経路型経路探索部２１１が探索した１以上の経路それぞれのコストのうちの最小のコストである。
【００６２】
次に、コスト算出部２１２は、始点ノードＳ及び終点ノードＤ間を地理空間的に直線で結んだ場合の直線コストＬｄを算出する（ステップＳ１０４）。直線コストＬｄは、例えば、ユークリッド空間内における始点ノードＳ及び終点ノードＤ間のユークリッド距離である。
【００６３】
なお、上記のステップＳ１０３の処理と、上記のステップＳ１０４の処理とは、処理順序が逆であっても良い。
【００６４】
次に、近似式妥当性判定部２１３は、第一近似式ｆ１と、安全係数Ｆｓとをデータ記憶部４００から取得する（ステップＳ１０５）。なお、第一近似式ｆ１及び安全係数Ｆｓは、入力部１００により入力され、データ記憶部４００に記憶される。
【００６５】
次に、近似式妥当性判定部２１３は、第一近似式ｆ１が、ｆ１（Ｌｄ）−Ｌｃ＞Ｆｓを満たすか否かを判定する（ステップＳ１０６）。
【００６６】
ステップＳ１０５において、第一近似式ｆ１が、ｆ１（Ｌｄ）−Ｌｃ＞Ｆｓを満たすと判定された場合、近似式妥当性判定部２１３は、第一近似式ｆ１は妥当であると判定する（ステップＳ１０７）。この場合、近似式妥当性判定部２１３は、当該判定結果（すなわち、第一近似式ｆ１妥当性＝「妥当」）を制約条件決定部２１５に出力する。
【００６７】
一方、第一近似式ｆ１が、ｆ１（Ｌｄ）−Ｌｃ＞Ｆｓを満たさないと判定された場合、（すなわち、ｆ１（Ｌｄ）−Ｌｃ≦Ｆｓである場合）、近似式妥当性判定部２１３は、第一近似式ｆ１は妥当でないと判定する（ステップＳ１０８）。この場合、近似式妥当性判定部２１３は、当該判定結果（すなわち、第一近似式ｆ１妥当性＝「妥当でない」）を制約条件決定部２１５に出力する。
【００６８】
以上により、始点ノードＳから終点ノードＤまでの経路を探索するための探索領域において、第一近似式ｆ１を用いてコスト制約条件Ｃを決定することが妥当であるか否かが判定される。
【００６９】
＜コスト制約条件Ｃの決定処理＞
次に、ある部分問題におけるコスト制約条件Ｃ（すなわち、ある部分探索領域内のある始点ノードｓと、当該部分探索領域内のある終点ノードｄとの間で部分経路を探索する際に用いられるコスト制約条件Ｃ）を決定する処理について、図７を参照しながら説明する。図７は、本発明の実施の形態におけるコスト制約条件Ｃの決定処理の一例を示すフローチャートである。
【００７０】
まず、部分ノード組直線距離算出部２１４は、部分ノード組に含まれる始点ノードｓ及び終点ノードｄを取得する（ステップＳ２０１）。部分ノード組は、経路探索処理部２２０により出力される。
【００７１】
次に、部分ノード組直線距離算出部２１４は、始点ノードｓ及び終点ノードｄ間を地理空間的に直線で結んだ場合の直線コストＬｐを算出する（ステップＳ２０２）。
【００７２】
次に、制約条件決定部２１５は、近似式妥当性判定部２１３により出力された第一近似式ｆ１妥当性が「妥当」であるか否かを判定する（ステップＳ２０３）。
【００７３】
ステップＳ２０３において、第一近似式ｆ１妥当性が「妥当」であると判定された場合、制約条件決定部２１５は、第一近似式ｆ１と遠回り許容量Ｒとをデータ記憶部４００から取得する（ステップＳ２０４）。なお、第一近似式ｆ１及び遠回り許容量Ｒは、入力部１００により入力され、データ記憶部４００に記憶される。
【００７４】
次に、制約条件決定部２１５は、第一近似式ｆ１による近似値をＬとして、Ｌ＝ｆ１（Ｌｐ）とする（ステップＳ２０５）。
【００７５】
一方、ステップＳ２０３において、第一近似式ｆ１妥当性が「妥当」でないと判定された場合、制約条件決定部２１５は、第二近似式ｆ２と遠回り許容量Ｒとをデータ記憶部４００から取得する（ステップＳ２０６）。なお、第一近似式ｆ２及び遠回り許容量Ｒは、入力部１００により入力され、データ記憶部４００に記憶される。
【００７６】
次に、制約条件決定部２１５は、第二近似式ｆ２による近似値をＬとして、Ｌ＝ｆ２（Ｌｐ）とする（ステップＳ２０７）。
【００７７】
ステップＳ２０５又はステップＳ２０７に続いて、制約条件決定部２１５は、コスト制約条件Ｃを、Ｃ＝Ｌ＋Ｒとして、経路探索処理部２２０に出力する（ステップＳ２０８）。このように、制約条件決定部２１５は、第一近似式ｆ１が妥当である場合には、第一近似式ｆ１を用いてコスト制約条件Ｃを決定する。一方で、制約条件決定部２１５は、第一近似式ｆ１が妥当でない場合には、第二近似式ｆ２を用いてコスト制約条件Ｃを決定する。
【００７８】
＜コスト制約条件Ｃの決定処理の他の例＞
ここで、上記の図７のコスト制約条件Ｃの決定処理では、第一近似式ｆ１が妥当でない場合には、一律に、第二近似式ｆ２を用いたコスト制約条件Ｃを決定した。すなわち、第一近似式ｆ１が妥当でない場合には、全ての部分探索領域における部分経路の探索で第二近似式ｆ２により決定されたコスト制約条件Ｃが用いられる。
【００７９】
しかしながら、例えば、第一近似式ｆ１が妥当でない場合であっても、ある部分探索領域において遠回りが発生しないことが事前にわかっているようなときには、当該部分探索領域における部分経路の探索には、第一近似式ｆ１により決定されたコスト制約条件Ｃを用いても良いと考えられる。
【００８０】
したがって、以降では、第一近似式ｆ１が妥当でない場合に、部分探索領域が、遠回りが発生する「遠回り発生領域」であるか否かを判定した上で、コスト制約条件Ｃの決定に第一近似式ｆ１又は第二近似式ｆ２のいずれを用いるかを判定する処理について、図８を参照しながら説明する。図８は、本発明の実施の形態におけるコスト制約条件Ｃの決定処理の他の例を示すフローチャートである。なお、図８のステップＳ２０１〜ステップＳ２０５の処理は、図７と同様であるため、その説明を省略する。
【００８１】
ステップＳ２０３において、第一近似式ｆ１妥当性が「妥当」でないと判定された場合、制約条件決定部２１５は、部分探索領域が遠回り発生領域であるか否かを判定する（ステップＳ３０１）。部分探索領域が遠回り発生領域である否かは、例えば、入力部１００が入力した追加情報を用いて、部分ノード組の周辺の領域で遠回りが発生するか否かを判定する。追加情報には、例えば、ネットワーク情報に含まれる属性情報が挙げられる。
【００８２】
一般的に、電力網、水道網、通信網等のインフラのネットワーク情報では、ネットワークに含まれるノード（マンホールや電柱等）やリンク（ノードを結ぶ管路、とう道、架空ケーブル、パイプ等。エッジとも称される。）がどのような地理的状況にあるか等を示す属性情報が含まれる。属性情報の具体例としては、例えば、地上からの高さ、地表面からの深さ、河川付近であるか否か、市街地であるか否か、山間部であるか否か等が挙げられる。
【００８３】
制約条件決定部２１５は、上記の属性情報に基づいて、部分ノード組の周辺の領域がどの程度山間部や河川に属するかを算出し、その割合により当該部分探索領域が遠回り発生領域であるか否かを判定すれば良い。
【００８４】
また、制約条件決定部２１５は、追加情報として、地図情報を用いて、部分ノード組の周辺の領域に山間部や河川がどの程度の面積を占めるかを算出し、その割合により当該部分探索領域が遠回り発生領域であるか否かを判定しても良い。
【００８５】
上記以外にも、制約条件決定部２１５は、例えば、以下の（１）〜（７）に示す方法を用いて、部分探索領域が遠回り発生領域であるか否かを判定しても良い。
【００８６】
（１）地理情報、地図情報、国土数値情報等を用いて、部分探索領域において、山間部や森林（広葉樹林、針葉樹林、竹林等）が占める割合がＴ％以上である場合、当該部分探索領域を遠回り発生領域であると判定する。ここで、Ｔは任意の値である。
【００８７】
（２）地理情報、地図情報、国土数値情報等を用いて、部分探索領域において、河川部や水域が占める割合がＴ％以上である場合、当該部分探索領域を遠回り発生領域であると判定する。ここで、Ｔは任意の値である。
【００８８】
（３）地理情報、地図情報、国土数値情報等を用いて、部分探索領域において、傾斜角がＤ度以上となっている領域の面積がＴ％以上である場合、当該部分探索領域を遠回り発生領域であると判定する。ここで、Ｄ及びＴは任意の値である。
【００８９】
（４）部分探索領域に含まれるノードのＴ％以上が山間部又は水域に属する場合、当該部分探索領域を遠回り発生領域であると判定する。ここで、Ｔは任意の値である。
【００９０】
（５）部分探索領域に含まれるリンクのＴ％以上が山間部又は水域に属する場合、当該部分探索領域を遠回り発生領域であると判定する。ここで、Ｔは任意の値である。
【００９１】
（６）部分探索領域に含まれるノード及びリンクのＴ％以上が山間部又は水域に属する場合、当該部分探索領域を遠回り発生領域であると判定する。ここで、Ｔは任意の値である。
【００９２】
（７）上記の（１）〜（６）の方法による判定結果のうち、Ｎ以上の方法で遠回り発生領域であると判定された場合、当該部分探索領域を遠回り発生領域であると判定する。ここで、Ｎは任意の値である。
【００９３】
ステップＳ３０１において、部分探索領域が遠回り発生領域であると判定された場合、制約条件決定部２１５は、第二近似式ｆ２と遠回り許容量Ｒとをデータ記憶部４００から取得する（ステップＳ３０２）。
【００９４】
次に、制約条件決定部２１５は、第二近似式ｆ２による近似値をＬとして、Ｌ＝ｆ２（Ｌｐ）とする（ステップＳ３０３）。
【００９５】
一方、ステップＳ３０１において、部分探索領域が遠回り発生領域でないと判定された場合、制約条件決定部２１５は、第一近似式ｆ１と遠回り許容量Ｒとをデータ記憶部４００から取得する（ステップＳ３０４）。
【００９６】
次に、制約条件決定部２１５は、第一近似式ｆ１による近似値をＬとして、Ｌ＝ｆ１（Ｌｐ）とする（ステップＳ３０５）。
【００９７】
ステップＳ２０５、ステップＳ３０３、又はステップＳ３０５に続いて、制約条件決定部２１５は、コスト制約条件Ｃを、Ｃ＝Ｌ＋Ｒとして、経路探索処理部２２０に出力する（ステップＳ３０６）。このように、制約条件決定部２１５は、第一近似式ｆ１が妥当でない場合であっても、部分探索領域が遠回り発生領域でないときには、第一近似式ｆ１を用いてコスト制約条件Ｃを決定する。一方で、制約条件決定部２１５は、第一近似式ｆ１が妥当でなく、かつ、部分探索領域が遠回り発生領域である場合には、第二近似式ｆ２を用いてコスト制約条件Ｃを決定する。
【００９８】
＜コスト制約条件Ｃ＞
ここで、上記の図６又は図７のコスト制約条件の決定処理で決定されるコスト制約条件Ｃ（すなわち、制約条件決定処理部２１０により決定されるコスト制約条件Ｃ）について、図９を参照しながら説明する。図９は、制約条件決定処理部２１０により決定されるコスト制約条件を説明する図である。
【００９９】
コスト制約条件Ｃが大きすぎると必要以上に遠回りする部分経路（部分問題の解）が算出されたり、探索に時間が掛かったり一方で、コスト制約条件Ｃが小さすぎると探索が打ち切られ、部分経路が算出されない場合がある。
【０１００】
すなわち、図９に示すように、コスト制約条件Ｃが０以上、最小コストＬｃ未満である場合には、部分問題の解が得られない（すなわち、部分経路を探索することができない）。したがって、最小コストＬｃは、コスト制約条件Ｃの下限値となる。
【０１０１】
本発明の実施の形態では、第一近似式ｆ１をｆ１（Ｌｐ）＝Ａ×Ｌｐ＋Ｂ、第一近似式ｆ２をｆ２（Ｌｐ）＝Ａ×Ｌｐ＋Ｒｃで定義することにより、近似値Ｌは、Ｌｃを下回らないようにすることができる。
【０１０２】
また、本発明の実施の形態では、近似値Ｌに対して遠回り許容量Ｒを加算した値をコスト制約条件Ｃとすることで、二次災害エリアを迂回するために、ある程度の遠回りを許容したコスト制約条件Ｃを決定することができる。
【０１０３】
しかも、このようなコスト制約条件Ｃを決定するにあたり、本発明の実施の形態では、始点ノードＳと終点ノードＤとの間で最短経路の探索を１回のみ行う（図６のステップＳ１０２）。言い換えれば、部分ノード組に含まれる始点ノードｓと終点ノードｄとの間では最短経路の探索は行わない。したがって、本発明の実施の形態によれば、仮に部分問題数が膨大であっても、少ない計算量でコスト制約条件Ｃを決定することができる。
【０１０４】
＜経路探索処理＞
次に、始点ノードＳから終点ノードＤまでの経路を、部分問題による部分経路の算出した上で、これらの部分経路を組み合わせることにより作成する場合の処理について、図１０を参照しながら説明する。図１０は、本発明の実施の形態における経路探索処理の一例を示すフローチャートである。
【０１０５】
まず、入力部１００は、探索対象に関する各種情報を入力する（ステップＳ４０１）。
すなわち、入力部１００は、例えば、ネットワーク情報、始終点ノード情報、評価指標情報、優先度情報、第一近似式ｆ１、第二近似式ｆ２、安全係数Ｆｓ、及び遠回り許容量Ｒ等を入力する。
【０１０６】
次に、経路探索処理部２２０は、始終点ノード情報に含まれる始点ノードＳ及び終点ノードＤから、ネットワーク上に探索領域を定義する（ステップＳ４０２）。経路探索処理部２２０は、ネットワークにおいて、始点ノードＳと終点ノードＤとの間の任意の凸領域を探索領域とすれば良い。後述するように、探索領域に含まれる各部分探索領域内で部分問題が定義される。
【０１０７】
次に、制約条件決定処理部２１０は、図６の第一近似式ｆ１の妥当性判定処理を行う（ステップＳ４０３）。
【０１０８】
次に、経路探索処理部２２０は、探索領域を１以上の部分探索領域（部分探索領域は、「メッシュ」とも表される。）に分割する（ステップＳ４０４）。部分探索領域の大きさは任意である。部分探索領域は、縦横可変長の格子状が好ましいが、これに限られるものではない。
【０１０９】
次に、経路探索処理部２２０は、１以上のメッシュをひとつなぎに組み合わせた複数のメッシュ組を作成する（ステップＳ４０５）。メッシュの組み合わせは、経路探索及び計算効率の観点から、例えば、始点ノードＳから終点ノードＤに向かう方向に組み合わせることが好ましい。ただし、メッシュの組み合わせ方は、これに限られるものではない。また、メッシュ組を作成する数は、多いほど経路探索の精度が向上するため、始点ノードＳから終点ノードＤに向かう方向で組み合わせることができ得る全ての組み合わせのメッシュ組を作成することが好ましい。
【０１１０】
次に、経路探索処理部２２０は、上記のステップＳ４０５で作成された複数のメッシュ組から１つのメッシュ組を選択する（ステップＳ４０６）。
【０１１１】
次に、経路探索処理部２２０は、上記のステップＳ４０６で選択されたメッシュ組から２つのメッシュを選択して、選択した２つのメッシュを部分メッシュ組とする（ステップＳ４０７）。
【０１１２】
次に、経路探索処理部２２０は、部分メッシュ組のそれぞれのメッシュから１つずつノードを選択し、選択した２つのノードを部分ノード組とする（ステップＳ４０８）。部分ノード組は、制約条件決定処理部２１０に出力される。
【０１１３】
次に、制約条件決定処理部２１０は、当該部分ノード組に対して、図７又は図８のコスト制約条件Ｃの決定処理を行う（ステップＳ４０９）。これにより、上記のステップＳ４０８で作成された部分ノード組毎にコスト制約条件Ｃが決定される。
【０１１４】
次に、経路探索処理部２２０は、部分ノード組に含まれる始点ノードｓ及び終点ノードｄ間の経路（部分経路）を、多目的関数に応じた経路探索アルゴリズムにより探索する（ステップＳ４１０）。このとき、経路探索処理部２２０は、上記のステップＳ４０９で決定されたコスト制約条件Ｃを用いて経路探索を行う。
【０１１５】
次に、経路探索処理部２２０は、上記のステップＳ４０７で選択された部分メッシュ組に含まれる全てのノードの組み合わせ（すなわち、部分メッシュ組に含まれる全ての部分ノード組）に対して経路探索を行ったか否かを判定する（ステップＳ４１１）。
【０１１６】
ステップＳ４１１において、部分メッシュ組に含まれる部分ノード組のうち、経路探索が行われていない部分ノード組が存在する場合、経路探索処理部２２０は、ステップＳ４０８に戻る。
【０１１７】
一方、ステップＳ４１１において、部分メッシュ組に含まれる全ての部分ノード組に対して経路探索が行われた場合、経路探索処理部２２０は、上記のステップＳ４０６で選択された全ての部分メッシュ組に対して経路探索を行ったか否かを判定する（ステップＳ４１２）。
【０１１８】
ステップＳ４１２において、メッシュ組に含まれる部分メッシュ組のうち、経路探索が行われていない部分メッシュ組が存在する場合、経路探索処理部２２０は、ステップＳ４０７に戻る。
【０１１９】
一方、ステップＳ４１２において、メッシュ組に含まれる全ての部分メッシュ組に対して経路探索が行われた場合、経路探索処理部２２０は、部分経路を組み合わせて、始点ノードＳから終点ノードＤまでの経路の作成を実施する（ステップＳ４１３）。すなわち、経路探索処理部２２０は、あるメッシュ組に含まれる部分メッシュ組における部分経路を、隣り合う部分メッシュ組間で繋ぎ合わせることで、始点ノードＳから終点ノードＤまでの経路を作成する。なお、部分経路を繋ぎ合わせても始点ノードＳから終点ノードＤまで到達できない場合もあり得る。この場合、始点ノードＳから終点ノードＤまでの経路は作成されない。
【０１２０】
次に、経路探索処理部２２０は、上記のステップＳ４０５で作成された全てのメッシュ組で経路の作成を実施したか否かを判定する（ステップＳ４１４）。
【０１２１】
ステップＳ４１４において、複数のメッシュ組のうち、経路の作成が実施されていないメッシュ組が存在する場合、経路探索処理部２２０は、ステップＳ４０６に戻る。
【０１２２】
一方、全てのメッシュ組で経路の作成が実施された場合、出力部３００は、経路探索処理部２２０により作成された経路を出力する（ステップＳ４１５）。このとき、出力部３００は、例えば、１以上の評価指標（多目的関数値）に基づいて、例えば、評価指標が良い上記Ｍ件の経路のみを出力しても良い。
【０１２３】
＜探索領域の定義処理＞
図１０のステップＳ４０２で説明したように、経路探索処理部２２０は、始終点ノード情報に含まれる始点ノードＳ及び終点ノードＤから、ネットワーク上に探索領域を定義する。この際、探索領域が大きくなるにつれて、当該探索領域に含まれるノード、リンク、及び部分探索領域の数が増加し、制約条件決定処理部２１０に入力される部分ノード組は、直線コストＬｐが大きいものが多くなる。この結果、図１１に示すように、異なる代表的な設備（すなわち、探索対象外の設備（例えばビル等））を起点とした設備群のノードが部分ノード組として選択され易くなる。このため、第一近似式ｆ１、第二近似式ｆ２の近似精度が劣化してしまう場合がある。
【０１２４】
一方で、探索領域が小さくなるにつれて、部分ノード組の始点ノードｓから終点ノードｄに至る経路の数が減少し、災害に強い経路を発見できなくなる場合がある。
【０１２５】
したがって、経路探索の精度を向上させるためには、適切な大きさの探索領域を定義する必要がある。そこで、このような適切な大きさの探索領域を定義する処理について、図１２を参照しながら説明する。図１２は、本発明の実施の形態における探索領域の定義処理の一例を示すフローチャートである。
【０１２６】
まず、経路探索処理部２２０は、始点ノードＳと終点ノードＤとの間で最短経路となる経路を探索する（ステップＳ５０１）。
【０１２７】
次に、経路探索処理部２２０は、上記のステップＳ５０１で探索された最短経路が通過する全てのノードと、始点ノードＳ及び終点ノードＤを結ぶ直線ＳＤとの距離（当該ノードから直線ＳＤへの垂線の長さを示す垂線距離）をそれぞれ算出する（ステップＳ５０２）。
【０１２８】
例えば、図１３に示すように、始点ノードＳから終点ノードＤへの最短経路が通過するノードが「ノード１」〜「ノード７」であるとする。この場合、経路探索処理部２２０は、ノード１から直線ＳＤへの垂線距離１を算出する。同様に、経路探索処理部２２０は、ノード２から直線ＳＤへの垂線距離２を算出する。以降も同様に、経路探索処理部２２０は、ノード３〜ノード７について、直線ＳＤへの垂線距離３〜垂線距離７をそれぞれ算出する。
【０１２９】
次に、経路探索処理部２２０は、直線ＳＤの両側で垂線距離が最も大きい２つのノードと、始点ノードＳと、終点ノードＤとを含む最小の矩形領域を算出する（ステップＳ５０３）。
【０１３０】
例えば、図１３に示すように、直線ＳＤの一方の側における各垂線距離のうち、最大の垂線距離は、「垂線距離５」である。また、直線ＳＤの他方の側における各垂線距離のうち、最大の垂線距離は、「垂線距離１」である。したがって、図１４に示すように、経路探索処理部２２０は、ノード１と、ノード５と、始点ノードＳと、終点ノードＤとを含む最小の矩形領域を算出する。
【０１３１】
次に、経路探索処理部２２０は、上記のステップＳ５０３で算出した矩形領域について、メッシュ（部分探索領域）の整数倍となるように、当該矩形領域の辺の長さを切り上げる補正を行う（ステップＳ５０４）。
【０１３２】
すなわち、経路探索処理部２２０は、図１５に示すように、矩形領域の各辺のうち、直線ＳＤと垂直な２辺の長さについて、メッシュサイズの整数倍となるように、当該２辺の長さを切り上げる補正を行う。
【０１３３】
次に、経路探索処理部２２０は、上記のステップＳ５０４で補正された矩形領域について、マージンＭを追加する補正を行う（ステップＳ５０５）。
【０１３４】
すなわち、経路探索処理部２２０は、図１６に示すように、矩形領域の各辺のうち、直線ＳＤと垂直な２辺の長さについて、予め決められたマージンＭを追加する補正を行う。なお、マージンＭとしては、メッシュサイズの整数倍であることが好ましい。
【０１３５】
次に、経路探索処理部２２０は、上記のステップＳ５０５で補正された矩形領域を探索領域と定義する（ステップＳ５０６）。これにより、図１０のステップＳ４０３以降の処理では、上記のステップＳ５０６で定義された探索領域を用いて処理が実行される。
【０１３６】
なお、図１０のステップＳ４０２において上記のステップＳ５０１〜ステップＳ５０６の処理が実行された場合には、図１０のステップＳ４０３の処理（第一近似式の妥当性判定処理）を実行せずに、ステップＳ４０４以降の処理が実行されても良い。この場合、ステップＳ４０９の処理（コスト制約条件の決定処理）では、常に第一近似式ｆ１を用いてコスト制約条件Ｃを決定すれば良い。
【０１３７】
また、図１２では、矩形領域の辺の長さを切り上げる補正と、マージンＭを追加する補正との両方を実施する場合について説明したが、これに限られない。これらの補正はいずれか一方のみが行われても良い。また、これら両方の補正が行われなくても良い。
【０１３８】
＜まとめ＞
以上のように、本発明の実施の形態における経路探索装置１０は、１以上の評価指標を持つ部分問題から得られる部分経路を組み合わせた経路を抽出する場合に、当該部分経路を算出するための部分問題に用いるコスト制約条件Ｃを決定することができる。しかも、本発明の実施の形態における経路探索装置１０は、始点ノードＳと終点ノードＤとの間の最短経路の探索を１回のみ行うことで、部分問題毎のコスト制約条件Ｃを決定することができる。したがって、例えば、部分問題の数が膨大となるような場合であっても、実用的な時間内でコスト制約条件Ｃを決定することができる。
【０１３９】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【０１４０】
１０        経路探索装置
１００      入力部
２００      演算部
２１０      制約条件決定処理部
２１１      最短経路型経路探索部
２１２      コスト算出部
２１３      近似式妥当性判定部
２１４      部分ノード組直線距離算出部
２１５      制約条件決定部
２２０      経路探索処理部
３００      出力部
４００      データ記憶部
【図１】
2018137724.tif 000003
【図２】
2018137724.tif 000004
【図３】
2018137724.tif 000005
【図４】
2018137724.tif 000006
【図５】
2018137724.tif 000007
【図６】
2018137724.tif 000008
【図７】
2018137724.tif 000009
【図８】
2018137724.tif 000010
【図９】
2018137724.tif 000011
【図１０】
2018137724.tif 000012
【図１１】
2018137724.tif 000013
【図１２】
2018137724.tif 000014
【図１３】
2018137724.tif 000015
【図１４】
2018137724.tif 000016
【図１５】
2018137724.tif 000017
【図１６】
2018137724.tif 000018