相互連関を持つモデルを対象としたスケジューリング問題の解法
理学専攻 情報科学コース 味方さやか

1

はじめに道路や上下水道，電気などの各生活設備 (‘ライフライン’ と呼ぶ) は，私たちの生活を根底から支えるものであり，災害が起きてしまった場合には可能な限り早急な復旧を行う復旧計画が求められる．しかし，復旧にあたることのできる人材には限りがあり，災害の状況によっては道路や複数のライフラインが同時に被害を受ける場合も予想されるため，復旧計画の作成は容易ではない．これまでに，災害時復旧計画についての研究は報告されているが [1][2]，これらの多くは水道やガスなど一つのライフラインを対象としており，ライフライン間の相互連関や各ライフラインがその他のライフラインに与える影響は考慮されていない．
そこで本研究では，これらの相互連関を基にライフライン間の機能の関係性について定義し，複数のライフラインが同時に被害を受けた場合において，早急な復旧を行うための災害復旧計画を作成することを目的とする．そのために，本研究ではこの問題を最適化問題としてとらえ，遺伝的アルゴリズム (GA) を利用し，ライフライン復旧の最適化を試みる．

2

災害復旧スケジュールの作成

2.1

災害モデルの GA へのコーディング

本研究では，交叉や突然変異が行い易く，かつ，スケジュールに変換しやすいよう遺伝子を二次元で表現した (図 1 参照)．

(指導教員：小林一郎)の復旧を終えてからでないと，リンク上のライフラインの復旧が行えないよう，復旧の順序関係を定義し，制約条件とする．

2.2

各ライフラインの復旧評価値

復旧の評価については各ライフラインごとに杉本らの研究 [2] により提案された方法を用いる．各ライフラインの復旧評価値は，各被災箇所の重要度と被害規模の積で表す．例えば道路の復旧評価値 Rr (t) は，被害を受けた道路の重要度 wi (i = 1, · · · , nr ) と被害を受けた道路の被害規模 di (i = 1, · · · , nr ) を用いて表す．
ここで，nr は道路の被災箇所総数である．復旧作業開始から t 日後の復旧評価値 Rr (t) は式 (1) のように表/∑される．
∑Rr (t) =wi d iwi d i(1)i∈Jrti∈Jr0

Jr0 は被害を受けたリンク番号の集合．Jrt は t 日までに開通したリンク番号の集合を表している．
同様にその他のライフラインについても，ガス Rg (t)，電気 Re (t)，通信 Rc (t)，下水道 Rsw (t)，上水道 Rtw (t)とし，復旧率を定義する．
2.3

相互影響係数

本研究では，ライフライン間に存在する相互連関による復旧率に対する影響度を定式化し，適応度関数に取り入れる．例えば上水道の使用には，下水道の整備と，一部の場合において電気が使用される．そこで上水道における相互影響係数 Idtw は下水道の復旧が完了したかどうかを示す Spsw と，電気の復旧が完了したかどうかを示す Spe ，上水道の使用にどの程度電気を利用しているかを示す電気使用依存度 Dde を用いて表す．

Idtw = Spsw × {Dde × Spe + (1 − Dde )}(2)

同様に，電気の相互影響係数を Ide ，通信の相互影響係数を Idc として定める．
図 1: 遺伝子モデル
図 1 において，各行は復旧班の分配を表す．そのため，行数 m は復旧班数と等しくなる．また，各列は復旧優先順位を表す．n 列数は復旧総日数と等しくなる．行列の要素は被害地番号を表す．交叉は行ごとに，Partially Matched Crossover(PMX) を用いる．また，突然変異については各行ごとにランダムに 2 つの遺伝子座を選択し，選択した遺伝子座の配列要素を交換するという方法を用いる．
災害復旧計画作成時の制約条件については，復旧人員の制限とライフラインの相互連関を基に定義する．
各復旧班には担当可能なライフラインの種類が決められており，その制約下で復旧する箇所を割り当てる．
また，道路は復旧時の移動に関する重要な要因となるため，全てのライフラインの復旧に大きな影響を及ぼす．そこで，被害を受けた道路リンクの上に復旧が必要なライフラインが存在する場合は，先に道路リンク

2.4

復旧の評価

2.3 節で表した相互影響係数を用い，復旧率と復旧日数に基づき累積非復旧率を算出し，適応度関数として扱う．累積復旧率は各ライフラインの総和として計算される．これに，上記に定式化した各ライフラインにおける相互連関により生じる復旧率の影響度を示す係数を考慮し，復旧開始後 t 日における復旧率を以下のように示す．
R(t) = Rr (t) + Idtw Rtw (t) + Rsw (t)+Ide Re (t) + Idc Rc (t) + Rg (t)(3)

式 (3) を用い，T を復旧の総日数として，累積非復
旧率 T R を以下のように表し，これを適応度関数として利用する．
∫ T
TR =[1 − R(t)] dt(4)0

GA への局所探索手法の導入

3

近傍解の探索は十分に行えないという GA の短所を補うため，本研究では局所探索を導入する．本研究では，斉藤ら [3] が提案した Random Flip Model（以下，RF）を参考に，局所探索を取り入れる．RF は，入れ替え（フリップ）対象となる遺伝子の中から 2 つの遺伝子座をランダムに選択し，遺伝子座の要素を交換するという手順を踏む．適応度が現在の値以上になった時点で探索を終了する．RF は最も評価の高い個体に対して，ある一定間隔世代ごとに適用され，GA の評価とエリート選択の間に組み込む．
図 3: GA と RF のシミュレーション結果の比較

ケーススタディ4

図 2 に示す災害都市モデルを例として，本研究で提案した手法を用い，災害復旧計画の作成を行った．
また，各被災道路と各被災ライフラインには，あらかじめ被害規模と復旧重要度を付与する．与えた災害地データと復旧班に関するデータは表 1，2 に示す．

図 4: 出力結果の一例
また，復旧箇所 3 番の場所 (道路) は 2 班と 3 班が同時に復旧を行うスケジュールになっている．このことから，復旧班の協力を考慮されていることがわかる．また，復旧箇所 3 番 (道路) の修復後に，その場所に隣接する復旧箇所 10 番 (下水道) が 5 班によって修復されていることから，作成されたスケジュールには，ライフラインの相互連関が反映されていることがわかる．

図 2: 災害都市モデルの例

5表 1: 復旧班に関するデータ
ライフライン班

能力

ライフライン班

能力

道路123456354253

電気

789101112245341

水道ガス
通信

表 2: 被災地データ
場所
123
4
567
891011
12

被災箇所
road-5road-10road-26
road-29
road-31
road-34
road-47
road-60
a-t-2
a-s-26a-t-41a-s-49

被害規模
101020515
1320
3158510重要度
135332141523場所
131415161718192021222324

被災箇所
b-5b-19b-39b-54
c-10c-17c-47
c-57
d-7d-31d-33
d-34

被害規模
1512261020416102571410重要度
415213135314

また，GA に用いる各パラメータは個体数 10，50，100 とし，交叉率 0.6，突然変異率 0.1，世代数 500 として計算を行った．同じ設定条件で，RF を局所探索法として，GA の計算中，20 世代ごとに動作させる計算を行った．図 3 は個体数 100 での GA の計算結果と，個体数 50 で RF を適用した計算結果である．GA とRF の計算結果がほぼ同等の値に収束しているが，RFの方がより早い世代数で収束値に向かっている事がわ
かる．以上より，RF を用いる事によって早い段階で，良い結果を得る事ができると言える．
次に，計算結果に基づき作成された災害復旧計画の一例を図 4 に示す．スケジュールより，比較的重要度の高い復旧箇所が前半に復旧されていることがわかる．

おわりに相互連関を持つライフラインの災害復旧スケジューリング問題をモデル化し，GA と RF を用いた解法の検討を行った. その際，各ライフラインの相互影響度を考慮した係数を取り入れることでライフライン間の相互連関を考慮し，効率よく復旧されるような復旧計画を作成することができた．一方で，より優れた解の算出には，初期個体数，エリート保存，RF を行う個体数など，複数の要因が大きく関係していると考えられる．今後はより効果的な局所探索法導入の検討やモデルに適したパラメータの設定を行うことにより，より良いスケジュールを求める方法を検討していくつもりである．

参考文献[1] 佐藤忠信，一井康二，遺伝的アルゴリズムを用いたライフライン網の最適復旧過程に関する研究, 土木学会論文集，No.537,p.245-256,1996.
[2] 杉本博之，田村亨，有村幹治，斉藤和夫，復旧班の協力を考慮した被災ネットワーク復旧モデルの開発, 土木学会論文集 No.625,IV-44,135-148,1999.
[3] 斉藤宏樹，廣安知之，三木光範，遺伝的アルゴリズムに組み込んだローカルサーチのパラメータおよび実装の検討, ISDL Report 2002.