(57)【特許請求の範囲】
【請求項１】
ネットワークを構成する複数のノードのうちの隣接ノードごとに、前記ネットワークにおける当該隣接ノード間の候補経路の集合に含まれる各候補経路について、第１の指標値である経路長と、想定される所定の地震ごとに当該地震による影響の大きさを示す第２の指標値とを算出し、前記第１の指標値と前記地震ごとの前記第２の指標値とに基づいて、前記集合の中から部分集合を抽出する抽出部と、
前記各部分集合から１つずつ候補経路を選択することで生成される、候補経路の組み合わせ群の中から、各組み合わせに含まれる各候補経路の前記第１の指標値の総和と、前記ネットワークにおいて必ずしも隣接しないノード間ごとに、当該ノード間において前記各組み合わせに含まれる候補経路を用いて算出される第３の指標値と、に基づいて１つの組み合わせを選択する選択部と、
を有することを特徴とする経路選択装置。
【請求項２】
前記選択部は、前記組み合わせ群の中から、前記第１の指標値の総和が第１の閾値以下である組み合わせの中で、前記必ずしも隣接しないノード間ごと及び前記地震ごとの前記第３の指標値のうちの最大値が最小である組み合わせを選択する、又は前記組み合わせ群の中から、前記必ずしも隣接しないノード間ごと及び前記地震ごとの前記第３の指標値のうちの最大値が第２の閾値以下である組み合わせの中で、前記第１の指標値の総和が最小である組み合わせを選択する、
ことを特徴とする請求項１記載の経路選択装置。
【請求項３】
前記選択部は、前記組み合わせ群の中から、前記第1の指標値の総和が第１の閾値以下である組み合わせの中で、前記必ずしも隣接しないノード間ごと及び前記地震ごとの前記第２の指標値の各地震の発生確率を重みとする加重和が最小である組み合わせを選択する、又は前記組み合わせ群の中から、前記必ずしも隣接しないノード間ごと及び前記地震ごとの前記加重和が第３の閾値以下である組み合わせの中で、前記第１の指標値の総和が最小である組み合わせを選択する、
ことを特徴とする請求項１又は２記載の経路選択装置。
【請求項４】
前記抽出部は、前記部分集合ごとに、各候補経路の第１の指標値の最小化と、前記地震ごとの前記第２の指標値の最小化とを目的とする最適化問題のパレート最適解集合を得ることで、前記部分集合を抽出する、
ことを特徴とする請求項１乃至３いずれか一項記載の経路選択装置。
【請求項５】
コンピュータが、
ネットワークを構成する複数のノードのうちの隣接ノードごとに、前記ネットワークにおける当該隣接ノード間の候補経路の集合に含まれる各候補経路について、第１の指標値である経路長と、想定される所定の地震ごとに当該地震による影響の大きさを示す第２の指標値とを算出し、前記第１の指標値と前記地震ごとの前記第２の指標値とに基づいて、前記集合の中から部分集合を抽出する抽出手順と、
前記各部分集合から１つずつ候補経路を選択することで生成される、候補経路の組み合わせ群の中から、各組み合わせに含まれる各候補経路の前記第１の指標値の総和と、前記ネットワークにおいて必ずしも隣接しないノード間ごとに、当該ノード間において前記各組み合わせに含まれる候補経路を用いて算出される第３の指標値と、に基づいて１つの組み合わせを選択する選択手順と、
を実行することを特徴とする経路選択方法。
【請求項６】
前記選択手順は、前記組み合わせ群の中から、前記第１の指標値の総和が第１の閾値以下である組み合わせの中で、前記必ずしも隣接しないノード間ごと及び前記地震ごとの前記第３の指標値のうちの最大値が最小である組み合わせを選択する、又は前記組み合わせ群の中から、前記必ずしも隣接しないノード間ごと及び前記地震ごとの前記第３の指標値のうちの最大値が第２の閾値以下である組み合わせの中で、前記第１の指標値の総和が最小である組み合わせを選択する、
ことを特徴とする請求項５記載の経路選択方法。
【請求項７】
前記選択手順は、前記組み合わせ群の中から、前記第１の指標値の総和が第１の閾値以下である組み合わせの中で、前記必ずしも隣接しないノード間ごと及び前記地震ごとの前記第２の指標値の各地震の発生確率を重みとする加重和が最小である組み合わせを選択する、又は前記組み合わせ群の中から、前記必ずしも隣接しないノード間ごと及び前記地震ごとの前記加重和が第３の閾値以下である組み合わせの中で、前記第１の指標値の総和が最小である組み合わせを選択する、
ことを特徴とする請求項５又は６記載の経路選択方法。
【請求項８】
コンピュータを、請求項１乃至４いずれか一項記載の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路選択装置、経路選択方法、及びプログラムに関する。
【背景技術】
【０００２】
非特許文献１及び２では、被災エリア形状、又は被災パラメータに基づく、ネットワークを構成する設備に関する評価尺度について評価が行われている。評価結果により、現状のネットワークを構成する設備に対する被災時特性の評価を行うことができる。また、例えば、ネットワークを構成する設備を新たな設備に変更した場合に評価尺度値が改善するかどうかについて影響評価を行うことが可能であることから、被災時特性の点から、新たな設備への変更が有利であるかどうかを評価することができる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】斎藤洋，「ネットワーク」と「形」（その２）-面的被災に強いネットワークの形-，日本オペレーションズ・リサーチ学会，2014年秋季研究発表会，2014年8月
【非特許文献２】斎藤洋，面的被災時のネットワーク残存性，日本オペレーションズ・リサーチ学会，2014年秋季研究発表会，2014年8月
【非特許文献３】司、翠川、断層タイプおよび地盤条件を考慮した最大加速度・最大速度の距離減衰式、日本建築学会構造系論文集、第523号、1999．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、これから構築予定の設備について、発生が予期されている地震による影響をなるべく小さくしたい場合に、どのような経路を選択すべきかについて、上記各非特許文献では示唆が与えられていない。
【０００５】
本発明は、上記の点に鑑みてなされたものであって、設備の構築先について災害による影響が相対的に低い経路の選択を支援することを目的とする。
【課題を解決するための手段】
【０００６】
そこで上記課題を解決するため、経路選択装置は、ネットワークを構成する複数のノードのうちの隣接ノードごとに、前記ネットワークにおける当該隣接ノード間の候補経路の集合に含まれる各候補経路に関する第１の指標値と、想定される所定の地震ごとに当該地震による影響の大きさを示す第２の指標値とを算出し、前記第１の指標値と前記地震ごとの前記第２の指標値とに基づいて、前記集合の中から部分集合を抽出する抽出部と、前記各部分集合から１つずつ候補経路を選択することで生成される、候補経路の組み合わせ群の中から、各組み合わせに含まれる各候補経路の前記第１の指標値の総和と、前記ネットワークにおいて必ずしも隣接しないノード間ごとに、当該ノード間において前記各組み合わせに含まれる候補経路を用いて算出される第３の指標値と、に基づいて１つの組み合わせを選択する選択部と、を有する。
【発明の効果】
【０００７】
設備の構築先について災害による影響が相対的に低い経路の選択を支援することができる。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施の形態における経路選択装置のハードウェア構成例を示す図である。
【図２】候補経路集合を説明するための図である。
【図３】本発明の実施の形態における経路選択装置の機能構成例を示す図である。
【図４】経路選択処理の処理手順の一例を説明するためのフローチャートである。
【図５】隣接ノード間における碁盤の目の一例を示す図である。
【図６】或る格子点の近辺の道路網又は鉄道網を通る経路の探索結果の一例を示す図である。
【図７】１つの候補経路の１つの地震に関する切断確率の算出処理の処理手順の一例を説明するためのフローチャートである。
【発明を実施するための形態】
【０００９】
以下、図面に基づいて本発明の実施の形態を説明する。図１は、本発明の実施の形態における経路選択装置のハードウェア構成例を示す図である。図１の経路選択装置１０は、それぞれバスＢで相互に接続されているドライブ装置１００、補助記憶装置１０２、メモリ装置１０３、ＣＰＵ１０４、及びインタフェース装置１０５等を有する。
【００１０】
経路選択装置１０での処理を実現するプログラムは、ＣＤ−ＲＯＭ等の記録媒体１０１によって提供される。プログラムを記憶した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００１１】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムにしたがって経路選択装置１０に係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００１２】
本実施の形態において、経路選択装置１０は、予め決められたノードを通るネットワークを構成する設備について、地震による影響が相対的に低くなるような物理的な経路（以下、「物経経路」という。）を選択するための処理（以下、「経路選択処理」という。）を実行する。例えば、ネットワークを構成する設備とは、ネットワークケーブル、ネットワークケーブル間を接続する装置（ルータ等）等を含む設備である。また、ノードとは、ネットワークケーブルを接続する装置が収容される施設（建造物）等である。但し、ネットワークケーブルを接続する装置が、ノードとして把握されてもよい。更に、物理経路とは、ネットワークケーブル等が敷設又は構築される、一連の地理的位置（すなわち、地理的な位置が特定された経路）をいう。なお、ネットワークケーブルやルータ等、ネットワークを構成する設備の構成要素を、以下「設備要素」という。
【００１３】
本実施の形態では、隣接ノードi,j間に対する候補経路集合をR(i,j)、候補経路中の最短経路をWmin(i,j)、当該最短経路の経路長をLmin(i,j)、候補経路集合R(i,j)中のある１つの候補経路をW(i,j)、当該候補経路W(i,j)の経路長をL(W(i,j))、或る地震a（aは、想定されている地震名を示す。）による設備故障の影響で候補経路W(i,j)が切断される確率をd_a(W(i,j))と表記する。隣接ノードi,jとは、その間に他のノードが介在しない２つのノードをいう。また、隣接ノードi,j間の候補経路集合とは、ノードiとノードjとの間を接続する物理経路の候補として探索された経路の集合をいう。
【００１４】
図２は、候補経路集合を説明するための図である。図２では、ノードiとノードjとの間に３本の候補経路が存在することが示されている。各候補経路は、例えば、道路網や鉄道網等、ネットワークを構成する設備の構築先となりうる地理的要素上を通るように探索される。
【００１５】
なお、以下においては、構築対象のネットワークの全体の物理経路と、候補経路W(i,j)ごとの物理経路との混同を避けるために、前者を、「全体経路」という。
【００１６】
本実施の形態では、また、２つの必ずしも隣接でないノードu及びノードvを発着する通信に対して、地震aによる設備故障の影響でノードu及びノードv間が切断される確率（以下、「発着地点間切断確率」という。）を、d_a(u,v)と表記する。そして、全隣接ノード間で全地震に対して、全候補経路W(i,j)を与えたときの、最大の発着地点間切断確率を、最悪発着地点間切断確率d_A(W)という。すなわち、発着地点の組の集合S、想定する地震の集合Aに対して、
d_A(W)=max_{a∈A,(u,v)∈S}d_a(u,v)  ・・・（１）
である。
【００１７】
或る地震aと発着地点u,vに対する発着地点間切断確率d_a(u,v)が、最悪発着地点間切断確率d_A(W)となるわけである。この発着地点u,vを最悪発着地点といい、この地震aを最悪地震という。
【００１８】
本実施の形態において、切断確率及び最悪発着地点間切断確率d_A(W)は、ネットワークを構成する設備の対する地震による影響の大きさを示す指標値又は尺度の一例である。なお、単なる「切断確率」は、隣接ノード間の切断確率を意味する。すなわち、本実施の形態では、対象となるネットワーク全体に関して、最悪発着地点間切断確率d_A(W)が最小となるような物理経路が選択される。その結果、設備の構築先について災害による影響が相対的に低い経路の選択を支援することができる。なお、ノードu及びノードv間の切断とは、ノードu及びノードv間におけるネットワークを構成する設備のいずれかの部分の破損又は故障等により、ノードu及びノードv間におけてネットワーク通信が困難になる状況をいう。
【００１９】
したがって、本実施の形態において解くべき問題は、最悪発着地点間切断確率d_A(W)を用いた以下の最適化問題である。
min_{W(i,j)∈R(i,j),(i,j)∈E}d_A(W)  ・・・（２）
subj.Σ_{(i,j)∈E}L(W(i,j))≦(1+c)Σ_{(i,j)∈E}Lmin(i,j)  ・・・（３）
ここで、Eは、隣接ノード対の集合、式（３）は、各隣接ノード間の物理的経路の総和（以下、「総経路長」という。）が許容コストc以下であるという条件を意味する。許容コストcは、ネットワーク設計上、任意に設定される、全体経路の経路長（以下、「総経路長」という。）の上限を決める定数であり、例えば、０．０より大きい値である。本実施の形態では、各隣接ノード間の最短経路長の総和を基準として、許容コストcが定められる。
【００２０】
すなわち、本実施の形態では、総経路長が許容コストc以下の候補経路W(i,j)の組み合わせの中で、最悪発着地点間切断確率d_A(W)が最小となるような組み合わせが、最適な全体経路（以下、「最適経路」という。）として選択される。
【００２１】
なお、上記の式（２）、式（３）の役割を入れ替えた、以下の式（４）及び式（３）が解かれてもよい。
minΣ_{(i,j)∈E}L(W(i,j))  ・・・（４）
subj.d_A(W)≦c'  ・・・（５）
上記の最適化問題を解くべく、経路選択装置１０は、図３に示されるような機能構成を有する。図３は、本発明の実施の形態における経路選択装置の機能構成例を示す図である。図３において、経路選択装置１０は、問題分解部１１、多目的問題解法部１２、切断確率算出部１３、及び組み合わせ部１４等を有する。これら各部は、経路選択装置１０にインストールされた１以上のプログラムが、ＣＰＵ１０４に実行させる処理により実現される。経路選択装置１０は、また、接続情報記憶部１２１、地理情報記憶部１２２、設備情報記憶部１２３、及び地震情報記憶部１２４等を利用する。接続情報記憶部１２１、地理情報記憶部１２２、設備情報記憶部１２３、及び地震情報記憶部１２４は、例えば、図１の補助記憶装置１０２、又は経路選択装置１０にネットワークを介して接続可能な記憶装置等を用いて実現可能である。
【００２２】
問題分解部１１は、式（２）及び式（３）によって定義される最適化問題（以下、「親問題」という。）を、隣接ノードi,j対ごとの最適化問題（以下、「子問題C(i,j)」という。）に分解する。具体的には、問題分解部１１は、子問題C(i,j)ごとに、以下の式（６）によって示される、複数目的の最適化問題を生成する。
【００２３】
min_{W(i,j)∈R(i,j)}(L(W(i,j)),d_a1(W(i,j)),…,d_an(W(i,j)))  ・・・（６）
ここでA={a1,…,an}とする。すなわち、検討対象の地震は、ａ１，…，ａｎとする。
【００２４】
すなわち、子問題C(i,j)は、隣接ノードi,j間の物理経路について、経路長の最小化、及び地震aごとの切断確率の最小化を目的とする最適化問題である。
【００２５】
子問題C(i,j)の各目的関数は、親問題の目的関数あるいは条件の一部となっている。したがって、親問題の最適解は、子問題C(i,j)ごとに得られる各パレート最適解集合から１つずつ選択されるパレート最適解の組み合わせになる。パレート最適解とは、複数の目的がある問題に対して、すべての目的関数値がよくなるような解が無い解のことである。例えば、隣接ノードi,jの候補経路集合R(i,j)のうち、L(W(i,j)),d_a1(W(i,j)),…,d_an(W(i,j)のいずれかが最小となる候補経路W(i,j)、又はこれらの目的関数の値を総合した結果が相対的に小さい候補経路W(i,j)が、パレート最適解集合に含まれる。したがって、子問題C(i,j)のパレート最適解集合は、隣接ノードi,j間の候補経路集合R(i,j)の部分集合である。なお、最短経路Wmin(i,j)は、L(W(i,j))を最小化することから、子問題C(i,j)のパレート最適解集合に含まれる。
【００２６】
なお、各ノード間の接続関係（各ノードがいずれのノードと隣接するか）を示す情報は、接続情報記憶部１２１に記憶されている。また、地震集合Aに属する各地震aに関する情報は、地震情報記憶部１２４に記憶されている。例えば、地震情報記憶部１２４には、想定される各地震aの発生確率、震源域、深度（震源の深さ）、及び震源マグニチュードが記憶され、さらに、各地域の想定震度を計算するための評価式及び地表の構造に基づく増幅率等が記憶されている。又は地震情報記憶部１２４には、各地域の想定震度が予め記憶されていてもよい。
【００２７】
多目的問題解法部１２は、子問題C(i,j)ごとに、式（６）のパレート最適解集合を得るための処理を実行する。
【００２８】
切断確率算出部１３は、隣接ノードi,jごとの各候補経路W(i,j)について、地震aごとの切断確率d_a(W(i,j))を算出する。算出された各d_a(W(i,j))は、多目的問題解法部１２によって利用される。
【００２９】
組み合わせ部１４は、子問題C(i,j)ごとの各パレート最適解集合から１つずつパレート最適解（候補経路W(i,j)）を選択することで生成される、候補経路W(i,j)の各組み合わせについて、最悪発着地点間切断確率d_A(W)及び総経路長を評価して、親問題の解を得る。
【００３０】
地理情報記憶部１２２には、ネットワークを構成する設備の構築先となる地域の道路網や交通網等の地理的情報が記憶されている。設備情報記憶部１２３には、ネットワークを構成する設備に関する情報が記憶されている。例えば、設備情報記憶部１２３には、管路種別等、物理経路を構成する、あるいは、構成しようとする設備の情報が記憶されている。
【００３１】
以下、経路選択装置１０が実行する処理手順について説明する。図４は、経路選択処理の処理手順の一例を説明するためのフローチャートである。
【００３２】
ステップＳ１０１において、分解部は、接続情報記憶部１２１に記憶されている情報に基づいて各隣接ノード（ｉ，ｊ）を特定し、隣接ノード（ｉ，ｊ）ごとに、子問題C(i,j)を生成する。すなわち、隣接ノード（ｉ，ｊ）ごとに、式（６）が生成される。
【００３３】
続くステップＳ１０２〜Ｓ１０５は、子問題C(i,j)ごとに実行される。
【００３４】
ステップＳ１０２において、多目的問題解法部１２は、処理対象の子問題C(i,j)に関して、W(i,j)∈R(i,j)となる各候補経路W(i,j)を生成する（ステップＳ１０２）。候補経路集合R(i,j)は、道路網や鉄道網などネットワークを物理的に設置できる地理的要素によって構成される。なお、各候補経路W(i,j)は、例えば、以下のように生成されてもよい。
【００３５】
まず、多目的問題解法部１２は、ノードi及びノードjの中間点を中心に、適当な間隔で碁盤の目（格子）を生成する。
【００３６】
図５は、隣接ノード間における碁盤の目の一例を示す図である。碁盤の目の間隔は、隣接ノードi,j間の距離にもよるが、例えば、ノードiが東京の或る地点であり、ノードjが横浜の或る地点であるとすると、当該間隔は、５ｋｍ程度でもよい。また、碁盤の目において直交する一方の方向は、南北方向であり、他方の方向は、東西方向であってもよいし、他の方向同士が直交していてもよい。なお、各ノードの地理的な位置情報（例えば、緯度及び経度）は、例えば、設備情報記憶部１２３に記憶されている。
【００３７】
多目的問題解法部１２は、碁盤の目における格子点（直交する直線の交点）ごとに、当該格子点の近辺の道路網上又は鉄道網上の１点を通ることを制約条件として、隣接ノードi,j間について経路探索を行う。探索される経路は、道路網又は鉄道網等によって構成される経路である。ネットワークを構成する設備は、道路や鉄道に沿って施設されるのが一般的だからである。道路網及び鉄道網の地理的情報は、例えば、地理情報記憶部１２２に記憶されている。
【００３８】
図６は、或る格子点の近辺の道路網又は鉄道網を通る経路の探索結果の一例を示す図である。図６では、格子点Ｐ１が処理対象であり、格子点Ｐ１の近辺において、道路網上又は鉄道網上を通る１点がＰ２である場合の経路の探索結果の一例が示されている。当該探索結果が、１つの候補経路W(i,j)となる。なお、経路探索には、例えば、ナビゲーションシステム等における経路探索技術等が用いられてもよい。
【００３９】
このような経路探索が、格子点ごとに実行されることで、複数の探索結果、すなわち、複数の候補経路W(i,j)が生成される。各候補経路W(i,j)は、相互に異なる制約条件に基づいて探索されたものであるため、或る程度、相互に離れていることが期待できる。このことは、或る地点を震源とする地震に対する影響が、相互に異なる候補経路W(i,j)が探索されうることを意味する。なお、２つ以上の格子点に基づく制約条件のもとで、経路探索が行われてもよい。また、上記以外の方法によって、候補経路W(i,j)が生成されてもよい。
【００４０】
なお、碁盤の目は、際限なく生成可能であるが、実際には、最短経路Wmin(i,j)から乖離している候補経路W(i,j)の価値はほとんど認められない。これは、以下の理由による。
【００４１】
地震による設備故障は、例えば、震度５弱以下では生じにくい。したがって、仮に、震源から遠い経路によって当該経路上の設備故障を回避するとしても、震度５弱の領域まで迂回すれば、それ以上に迂遠な経路の探索の必要性は低い。震度５強以上の領域は、ある限定された範囲であるので、際限なく広がることは無い。また、巨大地震によって、例えば、震度５強の領域が非常に広い場合にも、以下の理由により、候補経路W(i,j)にとって対象とすべき領域は、更に限られる。
【００４２】
或る地震aによる切断確率d_a(W(i,j))は、第１近似としては、この地震aの各震度階の領域内の経路長の正の重み付き和で与えられる。最短経路Wmin(i,j)の切断確率d_a(Wmin(i,j)）も同様であるので、d_a(W(i,j))＜d_a(Wmin(i,j))となるためには（すなわち、最短経路よりも切断確率が小さくなるためには）、経路長L(W(i,j))は、あまり大きな値を取り得ない。
【００４３】
なお、各隣接ノードi,j間の候補経路W(i,j)は、入力情報として与えられてもよい。この場合、隣接ノードi,jごとに、当該隣接ノードi,jの候補経路W(i,j)を示す情報が、図４の開始時に入力されてもよいし、予め、補助記憶装置１０２等に記憶されていてもよい。
【００４４】
図４に戻る。ステップＳ１０２に続いて、多目的問題解法部１２は、各候補経路W(i,j)について、経路長L(W(i,j))を算出する（ステップＳ１０３）。なお、経路長L(W(i,j))は、候補経路W(i,j)の探索と共に算出されてもよい。
【００４５】
続いて、切断確率算出部１３は、各候補経路W(i,j)について、地震集合Aに含まれる地震aごとに切断確率d_a(W(i,j))を算出する（ステップＳ１０４）。すなわち、候補経路W(i,j)ごとに、d_a1(W(i,j)),…,d_an(W(i,j))が算出される。なお、切断確率d_a(W(i,j))の算出方法の詳細については後述される。
【００４６】
続いて、多目的問題解法部１２は、ステップＳ１０２において算出された各経路長L(W(i,j))、及びステップＳ１０３において算出された各切断確率d_a(W(i,j))に基づいて、式（６）を解くことで、処理対象の子問題C(i,j)に対するパレート最適解集合を得る（ステップＳ１０５）。
【００４７】
上記のステップＳ１０２〜Ｓ１０５が、各子問題C(i,j)に関して実行されることで、子問題C(i,j)ごとに（すなわち、隣接ノードi,j対ごとに）、パレート最適解集合が得られる。
【００４８】
続いて、組み合わせ部１４は、子問題C(i,j)ごとのパレート最適解集合のそれぞれから、１つずつ要素（以下、候補経路W*(i,j)と表記する。）を選択することによって生成される、候補経路W*(i,j)の組み合わせの全通りを生成する（ステップＳ１０６）。
【００４９】
続いて、組み合わせ部１４は、各組み合わせについて、当該組み合わせに属する各W*(i,j)の経路長の総和（すなわち、総経路長）を算出する（ステップＳ１０７）。
【００５０】
続いて、組み合わせ部１４は、総経路長の昇順に、各組み合わせを整列する（ステップＳ１０８）。すなわち、総経路長が最短の組み合わせが先頭となるように整列が行われる。
【００５１】
続いて、組み合わせ部１４は、変数ｋに１を代入し、変数ｍに定数ＭＡＸを代入し、変数Ｒｍｉｎに０を代入する（ステップＳ１０９）。変数ｋは、処理対象の組み合わせを識別するための変数である。変数ｍは、最悪発着地点間切断確率d_A(W)の最小値を記憶するための変数である。定数ＭＡＸは、最悪発着地点間切断確率d_A(W)の理論上の最大値である。変数Ｒｍｉｎは、最悪発着地点間切断確率d_A(W)の最小値に対応する組み合わせの順番（ｋの値）を記憶するための変数である。
【００５２】
続いて、組み合わせ部１４は、ｋ番目の組み合わせ（以下、「組み合わせ（ｋ）」という。）の総経路長（ｋ）が、許容コストc以下あるか否かを判定する（ステップＳ１１０）。許容コストcは、(1+c)Σ_{(i,j)∈E}Lmin(i,j)である。すなわち、ステップＳ１１０は、式（３）の条件に対応した処理である。
【００５３】
総経路長（ｋ）が、許容コストc以下である場合（ステップＳ１１０でＹｅｓ）、組み合わせ部１４は、組み合わせ（ｋ）の最悪発着地点間切断確率d_A(W)を、式（１）に基づいて算出する（ステップＳ１１１）。すなわち、組み合わせ（ｋ）に属する候補経路W*(i,j)ごとの、各地震aに関する切断確率d_a(W(i,j))に基づいて、最悪発着地点間切断確率d_A(W)が算出される。
【００５４】
続いて、組み合わせ部１４は、算出された最悪発着地点間切断確率d_A(W)が、変数ｍ未満であるか否かを判定する（ステップＳ１１２）。当該最悪発着地点間切断確率d_A(W)が、変数ｍ未満である場合（ステップＳ１１２でＹｅｓ）、組み合わせ部１４は、当該最悪発着地点間切断確率d_A(W)を変数ｍに代入し、変数ｋの値を変数Ｒｍｉｎに代入する（ステップＳ１１３）。なお、当該最悪発着地点間切断確率d_A(W)が、変数ｍ以上である場合（ステップＳ１１２でＮｏ）、ステップＳ１１３は実行されない。
【００５５】
続いて、組み合わせ部１４は、組み合わせ（ｋ）が最後の組み合わせであるか否かを判定する（ステップＳ１１４）。組み合わせ（ｋ）が最後の組み合わせでない場合（ステップＳ１１４でＮｏ）、組み合わせ部１４は、変数ｋに１を加算して（ステップＳ１１５）、ステップＳ１１０以降を繰り返す。組み合わせ（ｋ）が最後の組み合わせである場合（ステップＳ１１４でＹｅｓ）、組み合わせ部１４は、Ｒｍｉｎ番目の組み合わせに属する候補経路W*(i,j)群によって構成される全体経路を、最適経路として選択する（ステップＳ１１７）。すなわち、当該最適経路が、親問題である式（２）の解である。
【００５６】
また、組み合わせ（ｋ）の総経路長（ｋ）が、許容コストを超える場合（Ｓ１１０でＹｅｓ）、組み合わせ部１４は、変数ｋの値が１より大きいか否かを判定する（ステップＳ１１６）。変数ｋの値が１より大きい場合（ステップＳ１１６でＹｅｓ）、組み合わせ部１４は、ステップＳ１１７を実行する。変数ｋの値が１以下の場合（ステップＳ１１６でＮｏ）、組み合わせ部１４は、最適経路の選択を断念する。この場合、総経路長が許容コストc以下である全体経路が無いからである。
【００５７】
なお、子問題C(i,j)ごとのそれぞれのパレート最適解集合が、例えば、１０個の候補経路W(i,j)から構成され、隣接ノードi,j対の数が全部で１０ある場合には、全ての組み合わせは１０の１０乗となり、現実的に解を得るには困難な程、計算量は膨大となる。しかしながら、実際には、そこまで計算量は大きくならない。何故なら、多くの場合、各子問題C(i,j)のパレート最適解集合は、最短経路Wmin(i,j)のみから構成されるからであり、それ以外のパレート最適解が有る場合でも、パレート最適解集合の要素数はごく小数になる可能性が高いからである。その理由は以下の通りである。
【００５８】
巨大地震の場合、同一震度階の領域が大きい。同一震度階を通る経路では、近似的には、経路長が短いほど有利となる（切断確率が小さくなる）。ノードi若しくはノードj、又は経路の途中で低震度階領域に迂回できる候補経路W(i,j)のみが、C(i,j)のパレート最適解となり得る。局所的地震の場合、震源近くの領域では、最短経路Wmin(i,j)以外のパレート最適解が有り得るが、震源域近くの領域から少し離れると、すぐに低震度階領域となるため、設備故障が発生せず、最短経路Wmin(i,j)のみがパレート最適解となる。この結果、例えば、各隣接ノードi,j間について、各子問題C(i,j)のパレート最適解集合は、平均で２個程度の候補経路W(i,j)から構成されるようになる。この場合、隣接ノード間の数が全部で１０あれば、組み合わせの数は、２の１０乗であり、計算量は、現時的に計算可能な大きさとなる。
【００５９】
続いて、ステップＳ１０４の詳細について説明する。図７は、１つの候補経路の１つの地震に関する切断確率の算出処理の処理手順の一例を説明するためのフローチャートである。図７は、１つの候補経路W(i,j)の１つの地震aに関する切断確率の算出処理であるため、ステップＳ１０４では、図７の処理が、各候補経路(i,j)及び各地震a∈Aについて実行されればよい。
【００６０】
ステップＳ２０１において、切断確率算出部１３は、候補経路W(i,j)を、複数の部分（以下、「微小区間u」という。）に分割する。
【００６１】
続いて、切断確率算出部１３は、微小区間uごとに、地震aの震源域からの距離ｄを算出する（ステップＳ２０２）。例えば、微小区間uごとに、当該震源域の範囲内において、当該微小区間uに最も近い地点から当該微小区間uまでの距離ｄが算出されてもよい。なお、地震aの震源域の地理的位置を示す情報は、地震情報記憶部１２４に記憶されている。
【００６２】
続いて、切断確率算出部１３は、各微小区間uに関して、工学的基盤での地震の最大速度を算出する（ステップＳ２０３）。ステップＳ２０３では、地震の最大速度の距離減衰の計算式、当該計算式の補正方法、及び硬質地盤の最大速度から工学的基盤の最大速度への変換方法等が利用される。地震の最大速度の距離減衰の計算式、当該計算式の補正方法、及び硬質地盤の最大速度から工学的基盤の最大速度への変換方法は、例えば、http://dil-opac.bosai.go.jp/publication/nied_tech_note/pdf/n379_1.pdf（防災科学研究所資料）に示され、非特許文献１に記載されたものが参考とされてもよい。また、http://www.giroj.or.jp/disclosure/q_kenkyu/No20_7.pdfに記載された計算方法が参考とされてもよい。また、これらの計算式は、地震情報記憶部１２４に記憶されていてもよい。
【００６３】
具体的には、距離ｄと、地震aの震源マグニチュード及び深度（震源の深さ）とが、地震の最大速度の距離減衰の計算式に代入されることにより、微小区間uの硬質地盤での最大速度が算出される。この際、当該計算式の補正方法によって、当該計算式について補正が行われてもよい。続いて、硬質地盤の最大速度から工学的基盤の最大速度への変換方法に基づいて、微小区間uの硬質地盤での最大速度が、微小区間uの工学的基盤での最大速度に変換される。このような演算が、各微小区間uについて実行される。
【００６４】
続いて、切断確率算出部１３は、微小区間uごとに、当該微小区間uの位置に対応した表層地盤増幅率を取得し、当該微小区間uについて算出された工学的基盤の最大速度に当該表層地盤増幅率を乗じることにより、当該微小区間uの表層地盤（地表）での最大速度を得る（ステップＳ２０４）。表層地盤増幅率とは、工学的基盤（Ｖｓ＝４００ｍ／ｓ）から地表に至る最大速度の増幅率をいい、その値は場所によって異なる。表層地盤増幅率は、例えば、http://www.j-shis.bosai.go.jp/からダウンロードされてもよいし、地震情報記憶部１２４に記憶されていてもよい。場所ごとに異なる表層地盤増幅率が用いられることにより、各微小区間uの地質や地盤の影響を加味した最大速度（ひいては想定震度）を算出することができる。
【００６５】
続いて、切断確率算出部１３は、微小区間uごとに、当該微小区間uに関して算出された表層地盤での最大速度を、最大速度から震度への変換式に当てはめることにより、想定震度を算出する（ステップＳ２０５）。最大速度から震度への変換式は、例えば、http://dil-opac.bosai.go.jp/publication/nied_tech_note/pdf/n379_1.pdf（防災科学研究所資料）等が参考とされてもよい。また、非特許文献３が参考とされてもよい。
【００６６】
なお、地震情報記憶部１２４には、予め、地震aごとに、各地域の想定震度が記憶されていてもよい。この場合、各微小区間uの想定震度は、当該微小区間uが属する地域に対して地震情報記憶部１２４に記憶されている値が用いられてもよい。
【００６７】
続いて、切断確率算出部１３は、地震aが発生した場合の、各微小区間の故障確率p(u)を算出する（ステップＳ２０６）。具体的には、各微小区間uの想定震度と、設備情報記憶部１２３に記憶されている、震度ごとの経路故障率とに基づいて、各微小区間uの故障確率p(u)が算出される。経路故障率とは、基準長あたりの故障部分の長さの割合である。例えば、１００ｍあたりの故障部分が１箇所である場合、経路故障率は、０．０１［１／ｍ］である。例えば、切断確率算出部１３は、想定震度に対応する経路故障率に、微小区間uの長さを乗じることにより、当該微小区間uの故障確率p(u)を算出する。
【００６８】
なお、経路故障率は、地域ごとに異なっていてよい。また、微小区間uに対応する設備要素の属性（例えば、管路又は架空、ビニール管又は鋼管、製造年等）が考慮されてもよい。例えば、設備要素の属性ごとに、震度別の経路故障率が、設備情報記憶部１２３に記憶されていてもよい。この場合、各微小区間uに対応する設備要素の属性と、各微小区間uの想定震度と対応する経路故障率が用いられて、各微小区間uの故障確率p(u)が算出されてもよい。
【００６９】
続いて、切断確率算出部１３は、候補経路W(i,j)の切断確率d_a(i,j)を算出する（ステップＳ２０７）。具体的には、切断確率算出部１３は、微小区間uごとに、以下の式（７）に基づいて、稼動確率を算出する。
【００７０】
微小区間uの稼動確率＝１−当該微小区間uの故障確率p(u)  ・・・（７）
切断確率算出部１３は、また、候補経路W(i,j)に係る全ての微小区間uの稼動確率の積（1-(1-p(u_1))×・・・×(1-p(u_n))  但し、u_kは、ｋ番目の微小区間uを示す。）を算出する。当該積の算出結果は、候補経路W(i,j)の稼動確率である。したがって、切断確率算出部１３は、以下の式（８）に基づいて、切断確率d_a(i,j)を算出する。
【００７１】
切断確率d_a(W(i,j))＝１−候補経路W(i,j)の稼動確率  ・・・（８）
なお、微小区間uの長さは、故障確率p(u)が１．０以下となるように決定されるのが望ましい。すなわち、経路故障率が、０．０１であり、基準長が１００である場合に、微小区間uの長さが１０ｋｍを超えると、故障確率p(u)が１．０を超えてしまう。このようなことがないように、微小区間uの長さが決定されるとよい。例えば、各微小区間uの長さは、経路故障率の基準長よりも短い値とされてもよい。
【００７２】
なお、ネットワークを構成する設備の対する地震による影響の大きさを示す指標値又は尺度として、最悪発着地点間切断確率d_A(W)の代わりに、発着地点間切断確率総和の地震発生確率による期待値が用いられてもよい。発着地点間切断確率総和の地震発生確率による期待値とは、Σ_{a∈A,(u,v)∈S}p_a・d_a(u,v)で与えられる。ここで、p_aは、地震aが（今後のある期間内に）発生する確率であり、地震情報記憶部１２４に記憶されている。p_aは、例えば、http://www.j-shis.bosai.go.jp/において地震ごとに公表されているものが利用されてもよい。最悪発着地点間切断確率d_A(W)の代わりに、発着地点間切断確率総和の地震発生確率による期待値が用いられる場合、上記の最悪発着地点間切断確率d_A(W)が、発着地点間切断確率総和の地震発生確率による期待値に置き換えられればよい。したがって、この場合、発着地点間切断確率総和の地震発生確率による期待値が最小となる経路が、最適経路として選択されることになる。
【００７３】
上述したように、本実施の形態によれば、ネットワークを構成する設備の構築先について災害による影響が相対的に低い経路の選択を支援することができる。また、本実施の形態では、任意の発着地点間の切断確率等が考慮されて最適経路が選択されるため、複数の経路を確保することで発着地点間の通信が途絶しない経路が最適経路として選択される可能性を高めることができる。
【００７４】
また、本実施の形態によれば、親問題が子問題C(i,j)に分解され、子問題C(i,j)ごとにパレート最適解集合が獲得された後で、親問題の解が得られる。そして、子問題C(i,j)ごとに得られるパレート最適解集合は、実際には、多くの場合、最短経路Wmin(i,j)のみ、又は最短経路Wmin(i,j)＋α個のみによって構成される。その結果、計算量を大幅に削減することができる。したがって、ノード数が多くなる大規模なネットワークに関しても、現実的な計算量又は限られた計算量で、災害による影響が相対的に低い経路を選択することができる。
【００７５】
なお、本実施の形態において、多目的問題解法部１２は、抽出部の一例である。組み合わせ部１４は、選択部の一例である。経路長は、第１の指標値の一例である。許容コスト（式（３）のc）は、第１の閾値の一例である。式５のc'は、第２の閾値の一例である。切断確率は、地震による影響の大きさを示す第２の指標値の一例である。最悪発着地点間切断確率d_A(W)は、必ずしも隣接しないノード間ごと及び地震ごとの第３の指標値の一例である。発着地点間切断確率総和の地震発生確率による期待値も、必ずしも隣接しないノード間ごと及び地震ごとの、各地震の発生確率を重みとする加重和を用いた第３の指標値の一例である。式（５）に発着地点間切断確率総和が当てはめられる場合のc'は、第３の閾値の一例である。
【００７６】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００７７】
１０          経路選択装置
１１          問題分解部
１２          多目的問題解法部
１３          切断確率算出部
１４          組み合わせ部
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        ＣＰＵ
１０５        インタフェース装置
１２１        接続情報記憶部
１２２        地理情報記憶部
１２３        設備情報記憶部
１２４        地震情報記憶部
Ｂ            バス
【図１】
0006280082.tif 000002
【図２】
0006280082.tif 000003
【図３】
0006280082.tif 000004
【図４】
0006280082.tif 000005
【図５】
0006280082.tif 000006
【図６】
0006280082.tif 000007
【図７】
0006280082.tif 000008