連結制約と被覆制約を持つ施設配置問題に対する発見的解法
M2012MM049 山之内亮介
指導教員：佐々木美裕

1

はじめに

all
EC = {e ∈ EC
| l(e) ≤ L},(3)
本研究では，連結制約と被覆制約を持つ施設配置問題
all
ED = {e ∈ ED | l(e) ≤ L/2},(4)(CCFLP) をネットワーク上で考える．この問題では，配allΠ = {(u, v) ∈ Π | dGL (u, v) ≤ L/2}
(5)
置される p 個の施設によってすべての需要点が被覆されること (被覆制約) に加え，任意の需要点間 (OD ペア) がとすれば，CCFLP は EV 専用急速充電器の配置問題 [7]
施設を経由して連結となること (連結制約) が要求される．
と等価となる．ただし，GL は，需要点集合 VD と枝集合
目的は，OD ペア間の距離の総和を最小化することであ{(u, v)|u ∈ VD , v ∈ VD } で定義される無向グラフである．
る．施設を電気自動車 (EV) の急速充電器と考えると，対3 解法
象地域内のすべての OD ペア間を EV で往来可能となる
本研究では，2 段階に分けて問題を解く．第 1 段階では，
ように p 個の急速充電器を配置する問題となる [7]．他の貪欲算法とけちけち法に基づく発見的解法を用いて，連応用例として，センサネットワーク構築の最適化などが結制約と被覆制約を満たす解を生成する．第 2 段階では，挙げられる [1, 2, 5, 6]．
同様の問題に対して，山之内，保田 [7] は最適化ソフト 第 1 段階で求めた解を初期解として近傍探索，アニーリ
ウェアを用いて厳密な最適解を求めた．しかし，大規模 ング法を行い，改善解を算出する．
な問題の解を求めることはできていない．そこで，本研 3.1 初期解の生成
本節では，初期解の生成方法として，貪欲算法とけちけ
ち法に基づく発見的解法を提案する．これらの解法において，W に追加および削除する u ∈ VC を選択する順番
2 モデルの説明を決定するために，各点の「重要度」を最短経路数え上げ
VC ，VD を VC ∩ VD = ∅ を満たす点集合，2 つの枝集合問題 [4] を用いて設定する．最短経路数え上げ問題は，最
all
all
all
all
EC
と ED
を EC
= {(u, v)|u ∈ VC , v ∈ VC }，ED=
短経路として使用される枝の回数を数え上げるものであallall{(u, v)|u ∈ VC , v ∈ VD } とし，EC ⊆ EC
，ED ⊆ EDるが，本研究では点の使用回数を求めるものとする．最と定義する．V = VC ∪ VD と E = EC ∪ ED に対し，無向
短経路数え上げ問題によって求めた使用回数が多い点ほ
グラフ G = (V, E) を考える．W ⊆ VC に対し，W ∪ VD
ど，OD ペア間の距離の総和が小さくできると考えられるによる G の誘導部分グラフを GW = (W ∪ VD ，EW ) とので，これを点の「重要度」として定める．N = (V, E)
する．任意の無向グラフ G = (V, E) と G の各枝の長さ上において，対象とする OD ペア (u, v) の数は (5) より，
l : E → R で定義されるネットワーク N = (V, E) 上にお|Π| であるので，最短経路は全部で |Π| 本存在する．このいて，dG (u, v)(u ∈ V, v ∈ V ) を N = (V, E) 上の最短経とき，u ∈ VC ⊆ V がこれら |Π| 本の最短経路を構成する路の長さとする．ただし，u から v へ到達不可能な場合は，点として使われた回数を w(u) とし，これを施設配置の選
dG (u, v) = ∞ と仮定する．また，すべての OD ペアの集択基準として使用する．最短経路の算出にはダイクスト合 Πall を Πall = {(u, v)|u ∈ VD , v ∈ VD } とする．OD
ラ法を用いる．
ペアの集合 Π ⊆ Πall に対して，Π ⊆ Πall = {(u, v)|u ∈3.1.1 貪欲算法
VD , v ∈ VD } とすると，CCFLP は次のように定式化できこの解法では，すべての u ∈ VC の中で，重要度 w(u) のる．
高い順に
W に追加し，連結制約，被覆制約および |W | ≥ p[CCFLP]∑を満たすまで W を更新する．
minimizedGW (u, v)(1)
3.1.2 けちけち法
究では，この配置問題に対する発見的解法を提案し，大規模な問題の解を求めることを目的とする．

(u,v)∈Πsubject toW ⊆ VC , |W | = p.

(2)

この解法では，はじめに W := VC とし，重要度 w(u)の低い順に，W から u ∈ W を削除し，|W | = p を満たすまで W を更新する．ただし，u ∈ W を W から削除す
ることにより誘導部分グラフ GW が非連結になる場合は削除しない．
3.1.3 貪欲算法の改良

GW が非連結の場合，目的関数値が ∞ となるので，GWが連結とならなければならない．よって，CCFLP は，W による GC = (VC , EC ) の誘導部分グラフが連結であること(連結制約) と，すべての v ∈ VD について {(u, v)|(u, v) ∈この解法では，施設を配置する u ∈ Vc を選ぶ基準とし
EW , u ∈ W } ̸= ∅ とすること (被覆制約) の制約を満たすて，重要度w(u) に加えて，ネットワーク上で u ∈ VC にW ⊆ VC の中で目的関数 (1) を最小化するものを見つけ隣接しているv ∈ VD の数 c(u) を用いる．この c(u) を，る問題となる．ここで，VC を急速充電器の配置候補点集
合，1 回の充電で EV が走行できる限界距離を L として， 本研究では u ∈ VC の被覆数と呼ぶ．
貪欲算法では評価値が最良である解を 1 つだけ保存するのが一般的であるが，ここでは，複数の解を保存し，より良い解を求める．解を生成する際に，u ∈ VC の被覆数
る．GW が連結で |W | < p であれば，ステップ 6 へ
c(u)，重要度 w(u) を評価基準とする貪欲算法を用いる．
進む．
[改良型貪欲算法]
ステップ 2: GW の連結成分を H j (Vj , Ej )(j = 1,· · · ,m)W

入力: N = (V, E); 出力: Wik ⊆ VC
ステップ 0: i := 1 とする．また，すべての v ∈ VD に対して d(v) := |{(u, v)|(u, v) ∈ ED , u ∈ VC }| を求め，
F := {u ∈ VC |(u, v ′ ) ∈ ED , d(v ′ ) = 1} とする．
ステップ 1: Wik := F (k = 1, · · · , σ), Ci′ := VC \F ,Di′ := VD \{v ∈ VD |(u′ , v) ∈ ED , u′ ∈ F } とする. また，すべての ui ∈ Ci′ に対して c(ui ) :=|{(ui , v)|(ui , v) ∈ ED , v ∈ Di′ }| を求める．
ステップ 2: すべての ui ∈ Ci′ を c(ui ) の大きい順に並べ替え，大きい順に σ 個だけ u1i , · · · , uσi とする．ただし，c(ui ) の値が同じ ui ∈ Ci′ が複数ある場合，w(ui )の値が大きいものを優先する．
ステップ 3: Wik := Wik ∪ {uki }, Cik := Ci′ \{uki },Dik := Di′ \{v ∈ Di′ |(uki , v) ∈ ED }(k = 1, · · · , σ) とする．
ステップ 4: k := 1 とする．
ステップ 5: (N , Wik , Cik , Dik ) を入力として，[被覆制約を満たす点集合の探索] へ．
ステップ 6: (GC , Wik ) を入力として，[連結制約を満たす点集合の探索] へ．
また，k = σ ならば，ステップ 7 へ進む．そうでなければ，k := k + 1 とし，ステップ 5 へ戻る．

jとする．連結成分 HW(j = 1, · · · , m) を 1 点 sj に縮約して得られるグラフを Ĝ(V̂C , ÊC ) とし，Ĝ と Ĝ の各枝の長さ l : e 7→ 1(e ∈ ÊC )，点の重み m : sj 7→|Vj |(j = 1, · · · , m) で定義されるネットワークを N̂ =(V̂C , ÊC ) とする．また，Ŝ = {sj |j = 1, · · · , m} とする．

ステップ 3: N̂ = (V̂C , ÊC ) 上の Ŝ の中で dG (u, v)(u, v ∈Ŝ, u ̸= v) の長さが最短となる sj 間のみを数え上げ，
sj の重みを考慮した点の重要度 ŵ(u)(u ∈ VC \W ) を求める．
∪
ステップ 4: u∗ = argmax ŵ(u), W := W {u∗ } とする．
u∈VC \W

ステップ 5: Ĝ(V̂C , ÊC ) の連結成分の数が m より小さい
場合，ステップ 1 へ戻る．そうでなければ，ステッ
プ 4 へ戻る．
ステップ 6: Ĉ := VC \W とする．Ĉ のうちで w(u) が最∪大であるものを u∗ とし，W := W {u∗ } とする．
|W | = p ならば W を出力して終了する．そうでなけ
ればステップ 6 へ戻る．

3.2 近傍探索
本研究では，近傍 N (W ) を，v ∈ VD に対して，{(u1 , v)
∈ ED |u1 ∈/ W } と {(u2 , v) ∈ ED |u2 ∈ W } を満たす u1 ，u2 を W ∪ {u1 }\{u2 } とすることより得られる解とする．
式で表すと以下のようになる．

ステップ 7: Wik (k = 1, · · · , σ) の目的関数値をそれぞれ求める．目的関数値の 1 番の小さい Wik を保持し， N (W ) ={W ′ |W ′ = W ∪ {u1 }\{u2 }，u1 ∈/ W, u2 ∈ W,
F := F ∪ {uki } とする．i = p ならば Wik を出力し(u1 , v) ∈ ED ，(u2 , v) ∈ ED }.
て終了．そうでなければ，i := i + 1 とし，ステップ
1 へ戻る．
解の評価関数 f˜ は OD ペアの移動距離の総和である．探以下に被覆制約を満たす点集合の探索と，連結制約を満たす点集合の探索のアルゴリズムを記述する．
[被覆制約を満たす点集合の探索]

索空間は実行可能領域内とする．確率 ρ(0 ≤ ρ < 1) で現在の解よりも悪くなる遷移を許す．探索の終了条件は，あらかじめ定めた探索回数に達したときとする．

入力: N = (V, E), W0 ⊆ VC , C, D; 出力: W ⊇ W0

3.3 アニーリング法
アニーリング法 (SA 法) とは，近傍探索を実行する過程に確率的な振る舞いを加え局所最適解に陥らないようにした手法である．ある確率で現在の解よりも悪くなるよ
うな遷移も許し，その確率を温度と呼ばれるパラメータt で制御する．評価値が悪くならない解への遷移確率を 1とし，改悪解への遷移確率を改悪量を ∆ として e−∆/t とする．SA 法では初期温度，温度の更新方法，ループ (一定温度での反復) およびアルゴリズムの終了条件を決定する必要がある．これらの決定方法を以下に述べる．
本研究では，温度の更新方法について，Kirkpatrick ら[3] に従う．初期の採択割合は 1 に非常に近くなることが望ましいので，初期温度を高めに設定する必要がある．
ここでは初期温度 tmax を，探索の過程で初めて見つかった改悪解を W0′ ，そのときの暫定解を W0 としたとき，
tmax = −(f˜(W0′ ) − f˜(W0 ))/ ln(0.9) と定める．
温度の更新方法は，t := α・t(0 < α < 1) とする．また，暫定解が見つかった時点の温度 tfound を記憶し，その後，ステップ 0: W := W0 とする．
ステップ 1: すべての u ∈ C に対して c(u) := |{(u, v)|(u, v) ∈ ED , v ∈ D}| を求め，S := {u ∈ C | c(u) =max c(u)} とする．
u∈C

ステップ 2: u ∈ S のうちで w(u) が最大であるものを u∗とし，W := W ∪ {u∗ }, C := C\{u∗ }, D := D\{v ∈D|(u∗ , v) ∈ ED } とする．D = ∅ であれば，W を出力して終了する．D ̸= ∅ であれば，ステップ 1 へ
戻る．

[連結制約を満たす点集合の探索]
入力: GC = (VC , EC ), W0 ⊆ VC ; 出力: W ⊇ W0
ステップ 0: W := W0 とし，W による GC の誘導部分グ
ラフを GW とする．
ステップ 1: GW が非連結であればステップ 2 へ進む．GW
が連結で |W | ≥ p であれば，W を出力して終了す探索を |VD |2 回反復して暫定解が更新されなかった場合， の値が小さい場合，実行可能解を求めることができない
が，その他の解法では，p の値が小さい場合でも，実行可温度を t := tfound と一旦高くする．
ループの終了条件は，|VD | 回反復したときとする．探索 能解を求めることができた．
の終了条件はループの中で解の受理頻度が pfreeze 以下とな
表 2 初期解生成法の実行結果 (例題 1，2)
る反復が rfreeze 回続いたときとする．pfreeze と rfreeze (0 <実行可能解が得られる最小の p
実行時間 (秒)例題
厳密解法 貪欲算法 けちけち法 厳密解法 貪欲算法 けちけち法
pfreeze < 1 ≤ rfreeze ) はパラメータとする．
1
2[SA 法]
入力: N = (V, E), W ⊆ VC ; 出力: W ∗ ⊇ W

例題

ステップ 0: W ∗ := W とする．
ステップ 1: 以下のステップ a, b, c, d および e を, ルー
プの終了条件が満たされるまで反復する．

1
2

11
15

20
42

12
17

実行可能解が得られる最小の p
改良型貪欲算法(σ = 1)(σ = 3)(σ = 5)

12
16

11
15

11
15

3145.866632.8

0.1
0.1

0.1
0.1

実行時間 (秒)改良型貪欲算法(σ = 1)(σ = 3)(σ = 5)

0.1
0.1

0.8
4.1

1.4
7.8

提案解法 (けちけち法，改良型貪欲算法) で得られた値
a: N (W ) 内の解をランダムに 1 つ選び W ′ とする． と，厳密な最適値との相対誤差を，図 1，2 に示す．貪欲
b: W ′ ∪ VD による誘導部分グラフ GW ′ が非連結な 算法はで得られた値はすべてけちけち法で得られたもの
らばステップ a へ戻る．GW ′ が連結ならばス と同じとなった．
テップ c へ進む．

c: ∆ = f˜(W ′ ) − f˜(W ) とする．
d: ∆ ≤ 0 ならば確率 1 で，∆ > 0 ならば確率 e−∆/t
で W := W ′ とし，ステップ e へ進む．そうでなければ，ステップ a へ戻る．
e: f˜(W ) ≤ f˜(W ∗ ) ならば，W ∗ := W とし，ステッ
プ a へ戻る．
ステップ 2: 探索の終了条件を満たされれば，W ∗ を出力して終了する．そうでなければ，温度 t を更新した
後ステップ 1 へ戻る．

4

図 1 例題 1 の厳密な最適値との相対誤差

計算実験

4.1 準備
本節では，300km 四方の領域内に需要点と候補点をランダムに配置した 2 つの例題を用いて，3 節で述べた解法の評価を行う．各例題の需要点数，候補点数，OD ペア
数および閾値 L は表 1 の通りである．
表 1 実験に使用したデータ
例題

|VD |

|VC |

|Π|

枝の距離の閾値 L

1
2

30
50

50
80

403
1159

100km

図 2 例題 2 の厳密な最適値との相対誤差
提案解法は，Microsoft1 Visual C++1 2010 Express で実装した．厳密解を求めるための厳密解法として，山之図 1，2 より，p の値が，例題 1 ではおよそ 20，例題 4
内，保田 [7] のモデルを用いる．最適化計算には，最適化ソ ではおよそ 45 より大きくなると，どの解法でも相対誤差
フトウェア IBM2 ILOG1 CPLEX2 Optimization Studio が 1% よりも小さくなった．σ = 5 としたときの改良型
12.5 を使用する．使用した計算機に搭載されている CPU 貪欲算法は，各例題で精度の良い解を求めることができは Intel3 Core3 i7-960 Processor, メモリは 24GB である． るが，例題 1 の p = 11 の場合のように σ = 3 としたと

4.2 初期解の生成
3.1 節で述べた解法により得られた値と厳密な最適値を比較する．各解法で，例題 1 に対し p の値を 1〜40，例
題 2 に対し p の値を 1〜66 と変えて実行した．厳密解法と各提案解法の実行可能解が得られる最小の p の値，最大の実行時間を表 2 に示す．
表 2 より，計算時間は，山之内，保田 [7] モデルでは pの値によって変化し，18 時間程度要するものも存在する
が，提案解法では全て 8 秒以内である．貪欲算法では，p

きよりも精度の悪い解を求める場合も存在する．よって，単純に σ の値を大きく設定するだけでは，精度の良い解を求めることができるわけではないことがわかる．
4.3 近傍探索

4.2 節で求めた解を初期解とし，近傍探索法と SA 法を用いて改善解を求める．近傍探索の終了条件となる探索
回数は，SA 法が終了条件を満たしたときの探索回数と同数とする．また，確率 ρ を 0 と 0.1 と変えて，各例題，各初期解で実験する．

SA 法のパラメータは α = 0.9，pfreeze = 0.05，rfreeze = けち法ではできた．また，実行時間も非常に短く，実用
20 とする．今回は，例題 1 の p = 12，14 と例題 2 の p = 16 的な解法である．改良型貪欲算法では，短時間で厳密解，18 のときの解のみを実験する．また，解法の精度を正 に近い解を求めることが可能だが，パラメータ σ の設定
確に評価するため，近傍 N (W ) 内の解をランダムに選択 が難しい．近傍探索，SA 法を用いることで，高速に高精する際に使用する計算機上のパラメータである乱数の種 度の解を求めることが可能であり，厳密な最適解を求め(seed) を変更し，各例題に対し 3 度の計算実験を行う． ることもできた．ただし，改良型貪欲算法と同様に，適各初期解から近傍探索，SA 法を用いて求めた解の相対 切なパラメータの設定が難しく，また，問題の規模が大誤差と実行時間を表 3，4 に示す．記述している値は 3 度 きいと解の評価値を計算する際に膨大な時間を費やしての計算実験で得られた値の平均である．また，けちけち しまう．
今後は，近傍探索と SA 法のパラメータの値や終了条件
法では，例題 2 の p = 16 とした場合に解を求めることがを変化させ，繰り返し実験を行うことで，CCFLP に対すできなかったので，N/A とする．
表 3，4 より，どの解法を用いても，各例題で大幅に解 る最適な戦略を見つけ出したい．また，解の評価値の計は改善され，厳密解を求めたものもあった．また，どの 算時間の短縮を考えていきたい．現在は探索解の評価を解法でも実行時間に差はあまりない．近傍探索の ρ を 0 行う度に，すべての OD ペア間の距離を算出しているたと 0.1 とした場合を比較すると，0.1 の場合の方が精度の め，OD ペアの数によって大きく時間が変化してしまう．
良い解を求める可能性が高いことがわかる．例題 1 では， よって，すべての OD ペア間の距離を算出するのではな
SA 法を用いたときに比較的精度の良い解を求めている く，暫定解と探索解の変更された要素によって，経由すが，例題 2 では ρ = 0.1 としたときの近傍探索の方が精 る施設が変化する OD ペア間のみの距離を算出することで計算時間の短縮ができると考える．
度の良い解を求めている．
表 3 例題 1 の近傍探索 (ρ = 0，0.1)，SA 法の実行結果
近傍探索法 (ρ = 0)

p
12
14

けちけち
法
0.62
3.66

相対誤差 (%)
改良型貪欲算法
σ=1 σ=3 σ=5
0.31
0.00
0.00
0.34
0.43
0.43

けちけち
法
1.8
2.7

実行時間 (秒)改良型貪欲算法
σ=1 σ=3 σ=5
2.4
2.0
2.1
3.2
3.1
3.0

近傍探索法 (ρ = 0.1)

p
12
14

相対誤差 (%)
けちけち
改良型貪欲算法
法
σ=1 σ=3 σ=5
0.00
0.00
0.00
0.00
0.68
1.06
0.32
0.46

けちけち
法
1.8
2.6

実行時間 (秒)改良型貪欲算法
σ=1 σ=3 σ=5
2.4
2.1
2.1
2.7
2.5
2.5

けちけち
法
3.8
4.7

実行時間 (秒)改良型貪欲算法
σ=1 σ=3 σ=5
5.1
4.5
4.5
5.8
4.9
5.0

SA 法
p
12
14

相対誤差 (%)
けちけち
改良型貪欲算法
法
σ=1 σ=3 σ=5
0.19
0.00
0.00
0.00
0.00
0.00
0.18
0.06

表 4 例題 2 の近傍探索 (ρ = 0，0.1)，SA 法の実行結果
近傍探索法 (ρ = 0)

p
16
18

けちけち
法
N/A
7.52

相対誤差 (%)
改良型貪欲算法
σ=1 σ=3 σ=5
6.90
6.90
3.63
1.25
0.26
0.26

けちけち
法
N/A
11.1

実行時間 (秒)改良型貪欲算法
σ=1 σ=3 σ=5
7.5
7.9
5.6
9.1
9.9
10.6

近傍探索法 (ρ = 0.1)

p
16
18

相対誤差 (%)
けちけち
改良型貪欲算法
法
σ=1 σ=3 σ=5
N/A
7.73
4.60
3.63
1.43
0.56
0.13
0.00

けちけち
法
N/A
10.0

実行時間 (秒)改良型貪欲算法
σ=1 σ=3 σ=5
19.1
21.2
14.4
8.6
9.5
10.2

けちけち
法
N/A
10.5

実行時間 (秒)改良型貪欲算法
σ=1 σ=3 σ=5
7.4
12.1
7.8
8.9
15.9
17.5

SA 法
p
16
18

5

相対誤差 (%)
けちけち
改良型貪欲算法
法
σ=1 σ=3 σ=5
N/A
4.60
6.90
3.63
0.37
1.26
0.31
0.18

おわりに

本研究では，CCFLP に対する発見的解法を複数提案した．初期解の生成において，p の値が小さい場合，貪欲算
法では実行可能解を求めることができなかったが，けち

参考文献[1] T. Furuta, M. Sasaki, F. Ishizaki, A. Suzuki, and
H. Miyazawa (2009) : A new clustering model ofwireless sensor network using location theory，
Journal of the Operations Research Society ofJapan，Vol. 52，pp. 366-376．
[2] W.B. Heinzelman, A.P. Chandrakasan, and H. Balakrishnan (2002) : An application-specific protocolarchitecture for wireless microsensor networks,
IEEE T ransactionson W ireless Communications
1，pp. 660-670．
[3] S. Kirkpatrick, C.D. Gelatt Jr., and M.P. Vecchi(1983) : Optimisation by simulated annealing，
Science，220，pp. 671-680．
[4] 大山達雄 (1998) :「最短経路数え上げ問題とその応用」，日本 OR 学会春季研究発表会アブストラクト集
1998，pp. 166-167．
[5] 佐々木美裕 (2007) :「センサネットワーク構築と最適化問題」，第 19 回 RAMP シンポジウム論文集，pp.
31-44．
[6] M. Sasaki, T. Furuta, F. Ishizaki, and A. Suzuki(2012): A mathematical programming approach tothe multi-round topology construction problem inwirless sensor networks，Journal of the Operations
Research Society of Japan，Vol. 55，pp. 199-208．
[7] 山之内亮介，保田将弘 (2012):「電気自動車専用急速充電器の最適配置問題」，南山大学数理情報学部 2011年度卒業論文．

——————–

1 Microsoft，Visual C++は米国 Microsoft Corporation の米国およびその他の国における登録商標です．
2 IBM，ILOG, CPLEX は IBM Corporation の登録商標です．
3 Intel, Core は Intel Corporation および子会社の米国およびその他の国における登録商標です．