第 4 章 経年機器の最適更新順位づけ
4.3 分枝限定法による旧形遮断器更新順位の最適化
4.3.2 小規模モデルへの適用結果
第4章 経年機器の最適更新順位づけ
54
CBN= (保守コスト + 信頼度コスト) 1年目
+ (保守コスト + 信頼度コスト) 2年目×1/(1+r) ～
+ (取替えコスト) N年目 ×1/(1+r)(N－1)
●ステップ２：各遮断器群の取替え工事費を表4-3のように整理する
○取替え工事費はどの年度で実施しても同一とする。
○各年度の工事費は現在価値換算しない
●ステップ３：制約条件を設定する
○単年度予算に上限を設ける 例．一か所あたりの最大工事費
○取替え実施時期の時間制約を設ける 例．変電所毎に△年目～□年目
表4-3 取替えコスト
1年目 2年目 ～ N年目 取替え期間 制約
A変 CA CA ～ CA △~□年目
B 変 CB CB ～ CB
～ ～ ～ ～ ～
M 変 CM CM ～ CM ×~□年目
予算上限 CUpper CUpper CUpper
●ステップ４：分枝限定法により、表4-3の制約条件下で、表4-2における各変電所のコ ストの合計が最小となる取替え順位を決定する。
＜組合せの数＞
M箇所の変電所がタイムフレームN年の中のいずれかの年度で遮断器取替えする組合 せは、NのM乗通り。
（例）6箇所、タイムフレーム＝8年の場合 ⇒ 組合せの数＝8の6乗＝26万通り
第4章 経年機器の最適更新順位づけ
55 (1)入力データ
表4-4 累積コスト [105 円] 1年目 2年目 3年目 4年目 E 変 3885 4742 5616 6578 F 変 4000 4128 4127 4132
表4-5 取替えコスト [105 円] 1年目 2年目 3年目 4年目 E 変 3885 3885 3885 3885
Ｆ 変 4000 4000 4000 4000
制約条件：単年度の工事費上限は4000（105 円）とする。
(2)列挙法による解
表4-6は列挙法により16通りの組合せ全てについて算定したもので以下が読みとれる。
➤ 単年度予算の上限値制約から、1年に2か所の取替えはできないため、各年に2か所 同時取替えするケース1,6,11,16は実行可能解にならない。
➤ 計画期間である 4 年間のトータルコスト初年度現在価値が最小となるのは、E 変電 所を1年目に、F変電所を3年目に取替えるケースである。
表4-6 列挙法による実行可能解
1年目 2年目 3年目 4年目 コスト
[105 円]
順位
E F E F E F E F
1 ○ ○
2 ○ ○ 8013 2
3 ○ ○ 8012 1
4 ○ ○ 8017 3
5 ○ ○ 8742 4
6 ○ ○
7 ○ ○ 8869 5
8 ○ ○ 8874 6
9 ○ ○ 9666 7
10 ○ ○ 9794 8
11 ○ ○
12 ○ ○ 9798 9
13 ○ ○ 10578 10
14 ○ ○ 10706 12
15 ○ ○ 10705 11
16 ○ ○
第4章 経年機器の最適更新順位づけ
56 (3)分枝限定法による解
列挙法による実行可能解が、16 通りのうち、同一年に2か所取替える4 ケースを除く 12通りであるのに対し、分枝限定法は9通りの実行可能解（表4-6の網掛ケース）を見出 した。その理由は、当該分枝限定法では実行可能解の取得を頻繁に実施するものの、枝刈 り、乱択法の採用により、すべての実行可能解を発見していないためである。ただし、厳 密解法としてその必要性はなく、最適解については列挙法による解と一致している。
(4)列挙法と分枝限定法の比較（探索木による確認）
図 4-5 は、小規模問題の探索木の全てのノードを示している。ノード数は全部で 31
（1+2+4+8+16）、そして再下層には 16の組合せがある。×印のある組合せは同一年に2
か所の取替えを行う実行不可能解である。また、◎のついた9つの組合せは分枝限定法に より求められた実行可能解である。
図4-5 小規模モデルの探査木
点線で囲われた部分は分枝限定法によって探索されたノードであり、元問題＃0（取替 え時間枠TW:1-4,1-4）から出発して、子問題＃1、＃2、＃3、＃4の順に探索が進行し、最終 的に5つのノードで探索が完了したことを示している。
すなわち、全域上界値（実行可能解）はまず元問題＃0で8017として得られ、各子問題 でも上界値の取得が試行された結果、＃3で得られた8012が全域上界値の最適値であった。
UB: 8017
第4章 経年機器の最適更新順位づけ
57
局所下界値は各子問題で評価され、全域上界値との比較により分枝するか分枝完了とす るかの決定がなされる。その結果、子問題＃2で局所下界値≧全域上界値であったので分枝 完了（枝刈り）となった。
子問題＃3、＃4では、時間枠が固定されていない機器グループが 1 個であるので、一次 元問題として解かれた結果、列挙法と同じ最適解（Ｅ変電所を1年目に、Ｆ変電所を3年 目に取替える組合せで累積コストは8012）が求まった。
なお、分枝限定法による実行可能解のうち3つは、終端したノード＃2の下にあるが、
これは上界値を乱択法によって求めるプロセスにおいて求まったものである。
4.3.3 実規模モデルへの適用結果
小規模モデルで検証したアルゴリズムを6か所の変電所を今後8年間のうちに取替え完 了するという実規模モデルに適用した。
その際、遮断器群の取替え単位を「変電所」単位とするケース（6 変電所×8 年間モデ ル）ならびに「各変電所のユニット」単位にするケース（17ユニット×8年間モデル）の 2種のケーススタディを行った。
この場合、それぞれのケースにおける組合せは
・変電所単位ケース（6変電所×8年モデル） ：8の6乗 ＝26万通り ・ユニット単位ケース（17ユニット×8年ケース）：8の17乗 ＝2252兆通り
＊D変電所は、2ユニット（屋外変電所であり、甲乙2母線）であるのに対し、
残りの変電所は3ユニットであることから、合計のユニット数は17。 となり、後者では、いわゆる組合せ爆発が起きるため、通常の計算機を利用しても列挙法 の適用は不可能となることが予想された。
＜変電所単位ケース＞
(1)入力データ
表4-7に示すように、最終年度まで取替えをせずにいた際のトータルコストの大きい順 は、D変→B変→C変→E変→A変→F変となっている。コストの大きい変電所は、万一 の遮断器事故時の供給支障量が大きいため、コストの一要素である信頼度コストがかさむ 地点である。
第4章 経年機器の最適更新順位づけ
58
表4-7 累積コスト [105 円]
1年目 2年目 3年目 4年目 5年目 6年目 7年目 8年目 A 3520 3725 3916 4124 4318 4529 4733 4924 B 2412 10868 19265 27492 35614 43625 51549 59379 C 3840 4746 5661 6678 7533 8402 9242 10082 D 553 22864 40043 56878 73506 89908 106138 122184 E 3885 4742 5666 6578 7403 8181 8949 9743 F 4000 4128 4127 4132 4124 4145 4190 4306
表4-8 取替えコスト [105 円]
1年目 2年目 3年目 4年目 5年目 6年目 7年目 8年目
A 3520 3520 3520 3520 3520 3520 3520 3520 B 2412 2412 2412 2412 2412 2412 2412 2412 C 3840 3840 3840 3840 3840 3840 3840 3840 D 5535 5535 5535 5535 5535 5535 5535 5535 E 3885 3885 3885 3885 3885 3885 3885 3885 F 4000 4000 4000 4000 4000 4000 4000 4000
(2)列挙法による解
このモデルでは、組合せの数が 26 万通りであるため、まだ計算機による列挙法適用が 可能と考えられたため、以下の2ケースについて 実行した。
ケース１：単年度の工事費上限が 5535 [105円] ケース２： 〃 8000 [105円]
ケース１における最適解は、D変（1年目）→B変（2年目）→C変（3年目）→Ｅ変（4 年目）→A変（5年目）→F変（6年目）となっており、表4-7の最終年度でみた時のコス トの大きい順と符合している。また、ケース２は、単年度工事費上限を増額したケースで あり、ケース1と同様に、D変、B変、C変、E変を早いうちから取替える組合せが最適 となっている。
表4-9 列挙法による解（トップ3）取替え期間制約無し [105円]
1年目 2年目 3年目 4年目 5年目 6年目 7年目 8年目 コスト ケース
1
D B C E A F 37105
D B C E A F 37150
D B E C A F 37210
ケース 2
B,D C,E A F 25475
B,D C,E A,F 25478
B,D C,E A F 25483
第4章 経年機器の最適更新順位づけ
59
以上の 2 ケースはいずれも、取替え期間制約が無いことから、累積コストテーブルにお ける最終年度でみた時のコストの大きい変電所の優先順位が高くなった。すなわち、結果 の類推が可能であった。
そこで、追加ケーススタディとして、一部の変電所に対する取替え期間制約を与えた探 索を行った。
表4-10 取替えコストと取替え期間制約 [105円] 1年目 2年目 3年目 4年目 5年目 6年目 7年目 8年目 期間 A 3520 3520 3520 3520 3520 3520 3520 3520 1～5年 B 2412 2412 2412 2412 2412 2412 2412 2412
C 3840 3840 3840 3840 3840 3840 3840 3840
D 5535 5535 5535 5535 5535 5535 5535 5535 5～8年 E 3885 3885 3885 3885 3885 3885 3885 3885
F 4000 4000 4000 4000 4000 4000 4000 4000 3～5年
表4-11は、ケース1,2における取替え期間制約有りの場合の、トップ3の組合せを示した もので、列挙法でもこの程度の規模であれば、予算制約に加え、取替え期間制約も考慮し た探索が可能なことが明らかになった。
表4-11 列挙法による解（トップ3）取替え期間制約有り [105円] 1年目 2年目 3年目 4年目 5年目 6年目 7年目 8年目 コスト ケース
1
B C A F D E 96893
B C F A D E 97096
B E A F D C 97110
ケース 2
B,C A,E F D 92352
B,C A,E F D 92357
B,E A,C F D 92401
(3)分枝限定法による解
表 4-12 は分枝限定法による探索を列挙法と同じ2 ケースについて行った際の実行可能 解の上位3通りを示している。
ケース１：単年度の工事費上限が 5535 [105円] ケース２： 〃 8000 [105円]
第4章 経年機器の最適更新順位づけ
60
列挙法による場合と同様に、ケース1における最適解は、D変（1年目）→B変（2年目）
→C変（3年目）→E変（4年目）→A変（5年目）→F変（6年目）となっており、累積 コストテーブルの最終年度でみた時のコストの大きい順と符合している。
また、ケース2は、単年度工事費上限を増額したケースであり、ケース1と同様に、D 変、B変、C変、E変を早いうちから取替える組合せが最適となっている。
表4-12 分枝限定法による解（トップ3） 取替え期間制約無し [105円] 1年目 2年目 3年目 4年目 5年目 6年目 7年目 8年目 コスト ケース
1
D B C E A F 37105
D B C E A F 37150
D B E C A F 37210
ケース 2
B,D C,E A F 25475
B,D C,E A F 25483
B,D C,E F A 25884
表4-13 は、ケース１、２における取替え期間制約有りの場合の、トップ 3 の組合せを示 したもので、分枝限定法も予算制約に加え、取替え期間制約も考慮した探索が可能なこと が明らかになった。
表4-13 分枝限定法による解（トップ3） 取替え期間制約有り [105円] 1年目 2年目 3年目 4年目 5年目 6年目 7年目 8年目 コスト ケース
1
B C A F D E 96893
B C F A D E 97096
B E F A D C 97313
ケース 2
B,C A,E F D 92352
B,C A,E F D 92357
B A,C E F D 94187
表4-14および表4-15は、ケース１における取替え期間制約無しの場合、および取替え期 間制約有りの場合の最適順位を示したものである。
第4章 経年機器の最適更新順位づけ
61
表4-14 最適取替え順位（ケース1：取替え期間制約無し）
1年目 2年目 3年目 4年目 5年目 6年目 7年目 8年目 A 3520 3725 3916 4124 4318 4529 4733 4924 B 2412 10868 19265 27492 35614 43625 51549 59379 C 3840 4746 5661 6678 7533 8402 9242 10082 D 553 22864 40043 56878 73506 89908 106138 122184 E 3885 4742 5666 6578 740 8181 8949 9743 F 4000 4128 4127 4132 4124 4145 4190 4306
表4-15 最適取替え順位（ケース1：取替え期間制約有り）
1年目 2年目 3年目 4年目 5年目 6年目 7年目 8年目 A 3520 3725 3916 4124 4318 4529 4733 4924 B 2412 10868 19265 27492 35614 43625 51549 59379 C 3840 4746 5661 6678 7533 8402 9242 10082 D 553 22864 40043 56878 73506 89908 106138 122184 E 3885 4742 5666 6578 7403 8181 8949 9743 F 4000 4128 4127 4132 4124 4145 4190 4306
(4)列挙法と分枝限定法の比較
表4-16は、実規模モデルを列挙法で解いた場合と分枝限定法で解いた場合の比較を示し ている。
実規模モデルでは、探索ツリーのノード数は、30 万程度となるが、近年の計算機では、
短時間に大量の実行可能解を求めることができる。これに対し、分枝限定法は、枝刈りに よって探索ノードを限定することから、全ての実行可能解を求めることはできないが、列 挙法によるものと同じ最適解を効率的に求めることができることが分かる。
表4-16 列挙法と分枝限定法の比較（実規模モデル）
列挙法 分枝限定法
検索ノード数 実行可能解数 検索ノード数 実行可能解数
ケース１ 299593 20160 101 23
ケース２ 299593 130368 81 38
＊列挙法の検索ノード数 ： 299593 ＝ 1+8＋8２＋・・＋8６