多目的ネットワークシステムの評価指標算出方法 に関する研究

博士（工学）学位論文

多目的ネットワークシステムの評価指標算出方法 に関する研究

首都大学東京大学院 システムデザイン研究科 経営システムデザイン学域

髙橋 奈津美

i

目次

第

1

1

1.1 緒言 1

1.2 ネットワークシステムの表現方法 3

1.3 単目的ネットワーク最適化問題 7

1.3.1 信頼度問題の概要 8

1.3.2 経路探索問題 13

1.3.3 最大流量問題 15

1.4 多目的最適化問題への展開 17

1.4.1 パレート最適解の定義 18

1.4.2 全点間信頼度を考慮した最適化問題 19

1.4.3 最適経路探索問題 21

1.5 本論文の目的・構成 24

第

2

2

設計問題

26

2.1 緒言 26

2.2 問題定義 26

2.2.1 記号定義と仮定 26

2.2.2 全点間信頼度を考慮した多目的ネットワーク設計問題 27

2.2.3 全点間信頼度と構築コストを考慮したパレート最適解の定義 28

2.3 提案アルゴリズムの概要 28

2.4 ネットワークの性質 30

2.4.1 パレートフロントを構成する解の傾向 30

2.4.2 計算対象部分ネットワークの選択基準 32

2.4.3 追加するエッジの選択指標 36

2.5 提案アルゴリズム 37

2.5.1 解のランクを用いるアルゴリズム 38

2.5.2 パレート最適解の傾きを用いるアルゴリズム 40

2.6 数値実験による評価 41

ii

2.6.1

41

2.6.2

43

2.7

45

第

3

47

3.1 緒言 47

3.2 問題定義 48

3.3 ネットワーク構造の分類 49

3.3.1 分類の基準 49

3.3.2 ネットワークの分類 52

3.3.3 ファクタリング法 56

3.3.4 ファクタリング法を用いた信頼度比較 58

3.3.5 全点間信頼度最大の構成 62

3.4 数値実験による評価 69

3.5 結言 73

第

4

74

4.1 緒言 74

4.2 問題定義 75

4.2.1 多目的最適経路問題 75

4.2.2 多目的最適経路問題におけるパレート最適解の定義 76

4.3 拡張ダイクストラ法 77

4.4 提案アルゴリズム 84

4.4.1 探索空間削減の基準経路 84

4.4.2 探索空間の削減方法 84

4.4.3 合成単目的最適経路による探索空間削減 87

4.4.4 目的関数値に基づく探索空間削減 89

4.5 数値実験による評価 91

4.6 結言 96

iii

第

5

98

参考文献

101

謝辞

109

1

第

1

1.1

近年，我々の生活基盤や社会基盤を支える多くのシステムが複雑化・大規模化 し，システムの信頼性，可用性，安全性を確保することが急務となっている．そ れらシステムの多くはネットワーク構造を有する．例として，物理的な構造がネ ットワークとなっている鉄道や道路[69,80]などの，主に大都市圏のように複数の 路線が複数の都市や駅を連結するように構築されているネットワークがある．

また，電話などの通信網や電力網，水道網のように，交換局や変電所のような 集約・拡散を行う設備が張り巡らされ，様々な社会基盤を下支えしているものも，

同様にネットワーク構造を持つ．更には，無線

LAN

一方，システムの評価指標は，一般的に，対象となるシステム，および，評価 者側の都合やそれらを取り巻く環境により異なる．道路交通網や鉄道網では目的 地への距離や時間，電力網や水道網，都市ガス網などでは輸送量，そして通信網 などでは接続回線の通信容量などが評価指標として考えられる．さらに社会基盤 を構築するシステムにおいて，周くすべての設備が安定して故障せずに接続され る信頼性の確保も重要な評価指標である．信頼性は「アイテム（部品・デバイス など）が与えられた条件の下で，与えられた期間，要求機能を遂行できる能力

(JIS

Z8115

)」と定義されるが，社会基盤を構築するシステムが要求機能を遂行で

きなくなった場合に社会に与える影響の大きさは，

2011

3

以上のようにネットワーク構造を持つシステムの問題は，ネットワーク理論と して古くから研究が進められている[2,12,16,19,22-24,42,59]．同時に，有限のシス テムないしは離散的なシステム内における対象の数え上げを考えるネットワー ク理論は，組み合わせ論の

1

「解」）が数え上げることができるならば，その選択肢の中で最善の解を求める 最適化の問題が存在する[20]．これは経済的な捉え方をすれば「最も安価な解」

を求めることが最適化となるが，前述の信頼性を考慮する場合には「最も高い信 頼性を得る解」を求めることも最適化となる．また，その他の展開として，冗長

2

系モデルの

1

[87]

Newman

[45]

また，システムの恩恵を受ける我々消費者の価値観も多様化している．例えば 高信頼性・高可用性，安全性などの基本的な要求を満たした上で，多くの場合で 利便性や低価格化を考慮に加えることが必要となっている．一般的にこれらの評 価指標を利用する意思決定者にとって，一つの解（案）を提示するよりは，代替 案として複数解を提示することが望ましい場合がある．しかも，それらは単一の 評価指標による案ではなく，同時に複数の評価指標を考慮した案を提示すること が重要となる．

ネットワークにおける最適化は，実規模問題をモデル化することにより，通信 ネットワーク，生産・流通システムなど多くの異なる分野のシステムで広く考え られている．例えば

GPS

OSPF

SCM

移動時間と移動コストと

CO

3

2

3

問題[71]として定式化される．

この背景の下，本論文では，ノードとエッジから構成されるグラフとして表現 されるシステムをネットワークシステムと呼び，多様な価値観に対応した（複数 の）評価指標を有するネットワークシステム（以下「多目的ネットワークシステ ム」と呼ぶ）に注目した．そして，上述の問題解決に有効な手法を提案するため に，多目的ネットワークシステムの評価指標について，特に，本論文では，シス テム故障の社会に与える影響の大きさを考えてシステム信頼度，また，意思決定 者にとって重要な指標としてコストを考えた．この性質の異なる評価指標の算出 方法を提案することで，上述の問題解決に有効な手法の

1

1.2

本論文で扱うネットワークシステムの表現方法について述べる．はじめに，ネ ットワークはグラフによって下記のように表される．

1)

グラフ

G (graph)

1-1

(

:vertex)

と，エッジ(辺:edge)またはアーク(弧:arc)と呼ばれる要素の集合から成る[16]．一 般的に，ノード間を連結する要素は，無向の場合はエッジ，有向の場合はアーク と呼ばれることがあるが，本論文においてはどちらの場合もエッジと呼ぶことと する．また，本論文ではこのノードの集合とエッジの集合から成るグラフを「ネ ットワーク」と呼ぶ．

図

1-1

4

ネットワーク中の

2

u

v

u

v

e

v

v

e

e

u

v

G

G

v

v

G

G

_r

G

_r

0

また，特徴的なグラフについて以下で述べる．

(1)

完全グラフとは，異なるノードの対の全てが

1

n

n  1

2 ) 1 ( n 

n

(2)

グラフ

G

G

そのすべてのエッジが

G

(3) 2

2

A

B

B

1-2

1-2

A

B

1

2

2

図

1-2 2

5

2)

ネットワークをグラフで表現すると，2つのネットワークの図が異なっている ように見えるが，同じネットワークを表現している場合や，異なるネットワーク であるが，2つのネットワークの図は同じように見える場合があり得る．この相 似性を言い表す表現として，これら

2

他方のネットワークを得ることが出来る．

2

G, H

G, H

G

H

G

H

G

H

1

1

[20,33]である．この 1

1

3)

ネットワーク

G

k

uv , vw ,  , yz

G

k

uvwx yz

u

_z

ネットワーク

G

G

次に，始点のノードと終点のノードが同じである歩道・小道に関して以下を定 義する．ネットワーク

G

uv , vw ,  , yz , zu

G

サイクルグラフとは図

1-3

n

2

n

6

図

1-3

4)

例えば，通信ネットワークや交通ネットワークにおいては，ある区間の接続が 不通となった場合においても，ネットワーク全体は機能していることが求められ る．このような問題は任意の

k

k  2 )

(1)

連結グラフ

G

 _{(G )}

 _{( G )  k}

G

k -辺連結であると

G

 _{(G )}

G

2

S

1

S

G

1

S

G

(2)

連結度は，取り除くノード数で考えることもできる．ノードを除くときには，

そのノードに接続するエッジも取り除くとする．連結グラフ

G

)

 (G

G

 ( G )  k

k -

k -

k -

k -

特に，完全グラフの連結度は

n  1

n  1  k

k -連結であるという．連

7

結グラフ

G

 (G )

G

2

S

S

G

1

S

G

(3)

連結グラフ

G

G

s, t

s, t

st 

st _

1

st _

s, t

1

次にグラフの分離の概念を述べる．ノード

s, t

G

1

s

t

st _

これより

st _

st _

1

st _

st _

st 



st

[42]として導出されている．

(4)

連結グラフ

G

k -辺連結であるのは， G

2

k

このエッジ形式のメンガーの定理を一般化したものが，最大フロー・最小カ ット定理であり，後述する最大流量問題の定理の

1

1.3

前述のようにノードとエッジから構成されるグラフとして表現できるネット ワークシステムにおける最適化問題は，ネットワーク理論として古くから研究が 進められている．本節では複数の実現可能な「解」が数え上げられる目的関数を 考慮し，その選択肢の中で最善の解を求める単目的最適化問題を紹介する．

8

1.3.1

ネットワークシステムの故障を考慮する問題として，ネットワークの信頼度問 題がある．これはノードやエッジ付与された稼働確率からネットワーク全体の信 頼度を評価する問題である．Aggarwal他[2]は通信ネットワークにおいてノード

（に当たる機器）とエッジ（に当たる結線）について，稼働状態と故障状態の2 状態を考慮した2状態ネットワークのモデルを考え，その信頼度評価方法を提案 した．Boesch[14]は，すべてのエッジ信頼度が同一の場合の信頼度算出方法をま とめた．信頼度は連結確率を算出する対象ノード数によって，2点間信頼度，k点 間信頼度，全点間信頼度のように複数に分類され，様々な研究が行われてきた

[13,47,80]．また，ネットワークの信頼度問題ではその問題の困難さから様々な派

Jan他[27]は分

及び，モンテカルロ法シミュレーションの応用による準最適配置導出方法が，

Dengiz他[17,18]やRamirez-Marqueza他[46]により提案されている．Li他[34]は，多

Zuo他[67]はこの多状態ネットワークの信頼度問題に対

厳密な信頼度の算出方法について，包除原理を用いた方法，

SDP(Sum of Disjoint Products)法，ファクタリング法が知られている．以下に，それぞれの信頼度算出

1)

ネットワークの信頼度の算出方法の

1

MP

( i  1 , 2 ,  , h )が列挙されているとする． P

MP

P

1

P

h  2

] Pr[

] Pr[

] Pr[

]

Pr[ P

 P

 P

 P

 P

 P

以上のことを拡張すると，

_{i  1 , 2 ,  , h}

G

_{R (G )}

_{R (G )}

9

] Pr[

) 1 ( ]

Pr[

] Pr[

] Pr[

)

(

1 2

1 h

h j

i

j i h

i i

h

P P P P P P

P P

P G

R      

   















  

によって計算される．

この展開式の項数は，

2

 1

2) SDP

SDP

i  1 , 2 ,  , h

MP

P

MP

P

P

i  1 , 2 ,  , h

O

 P

 P

   P

 P

それそれの

O

G

R (G )

] Pr[

] Pr[

] Pr[

] Pr[

)

(

1

h h h

i

i

P P P P P P P

O G

R      













 

で計算することができる．

3)

包除原理を用いた方法とSDP法では，事前に極小パスや極小カットを求めてお く必要があり，極小パスや極小カットの列挙法について多くの研究がされている

[49,50]．しかしファクタリング法は，極小パスや極小カットを算出することなく，

ネットワークの信頼度を計算することが出来る．ファクタリング法は特定エッジ の状態に注目して場合分けを行う方法で，

Moskowitz[43]により信頼性問題へその

4)

本論文では，ネットワークシステムの故障を考慮する評価指標として特に全点 間信頼度に注目する．以下に第

2

ノード数

n

^{n(n - 1)}

2

10

(

2 ) 1 ( 

 n n

m

_{i  1 , 2 ,  , m}

e

x

x

e

x  ( x

, x

,  , x

)

x

x

i  1 , 2 ,  , m

e

e

p

一定レベル以上の通信，交通等が実現される確率と解釈することもできる．この とき全点間信頼度は，ネットワークのノード全ての間で一定レベル以上の通信，

交通等が実現される確率に相当する．

小出[72]は部分ネットワーク

x

R (x )

エッジ

e

1

p

e

e

x  e

, x \ e

R (x )

補助定理

1-1 部分ネットワーク _x

e

 E

)

\ ( )

( ) 1 ( )

( p

R e

p

R e

R x    x    x

(1.1)

部分ネットワーク

_x

R (x )

1

例として図

1-4

3

図

1-4

1-4(a)は，エッジ e

e

x

の例を示している．

x

R ( x

)

(1.1)

3 2 2

1

) ( 1 ) 0

( p p p

R x     

と求められる．

x

x

(b)と(c)に示した2つの部分ネットワーク x

x

11

トワークに対しても同様の手順を繰り返す．実際に部分ネットワーク

x

R (x )

R ( x  e

)

R x ( \ e

)

ファクタリング法の効率化を図るために，ファクタリング法の再帰過程において 部分ネットワークの信頼度を参照するアルゴリズム(factmem法)を提案した．

図

1-4 全点間信頼度の計算手順

図1-4の(d)のネットワーク

x

e

x

そこで，ネットワーク

x

R ( x

)

} 1 )

1 {(

) ( ) 1 ( )

(

  p

 R

 p

  p

 p

 p



R x x

このとき，部分ネットワーク

x

R ( x

)

R ( x

)

R ( x

)

12

付加したファクタリング法による計算過程を示す．

X

k

E [x ]

_x

【信頼度の参照を付加したファクタリング法の計算過程】

STEP1： x  X

STEP2： e

 E [x ]

STEP3：

STEP3-1： e

x \ e

STEP3-2：エッジ数が 2

STEP2

STEP3-3：エッジ数が 1

R x ( \ e

)

STEP4：

STEP4-1：縮約した順番の逆順に e

x  e

STEP4-2： S

x  e

S

x  e

R ( x  e

)

x  e

R x (  e

)  0

STEP5： R ( x )  ( 1  p

) R ( x  e

)  p

R ( x \ e

)

STEP6：記憶対象であるネットワークならば， S  S  {( G , R ( x ))}

STEP7：STEP4-1

e

STEP4-1

STEP8：STEP1

x

k  k  1

STEP1

そうでなければ，STEP1に戻る．

Akiba

factmem

1

ワークなど，信頼度が自明な部分ネットワークに対して計算を排除し，効率化を 図った改良

factmem

補助定理1-2

エッジ数が

n-1

補助定理1-3

縮約の過程でノード数が1になった時点で全点間信頼度は1であり，それ以上の 縮約は必要ない．

13

本論文の第

2

3

factmem

1.3.2

システムの故障を考慮しない場合の問題の

1

2

地点やそれを繋ぐ道路によるネットワークは，地点をノード集合

V

E

_{G  ( V , E )}

s

t

s

t

Aida

(

)

最適経路問題を解くアルゴリズムについていくつかあるが，これらは，いずれ も以下の原理に基づいている．

G

1-5

1

2

2

_{s , w  V}

k

s, w

P

P

w

e

v

w

P

e

s, v

Bellman

以下に最短経路を解くアルゴリズムについて紹介する．ここでノード

v

l

e

c

14

1) Dijkstra

最短経路問題の多くは，エッジの重みが非負である．その場合に有効なアルゴ

リズムが

Dijkstra

1-5

Dijkstra

ード

s

v

l

V

Q

Q

l

v

v

u

e

l

 l

 c

e v

u

l c

l  

_{Q  Q \ { v }}

1-5

l

1

v

t

t

また

Dijkstra

経路問題を解くために，計算機のメモリ階層構造に注目し，Dijkstra 法の特徴で ある値記憶領域の参照が連続的に行われるようキューを待機させる高速化の提 案などのように，様々な提案がこれまでにされてきた．

図

1-5 Dijkstra

15

2) Bellman-Ford

エッジの距離の合計が負となるような閉路がある場合にも適用することがで きる．ノード

s

k

v

) (k

l

v

u

e

e v

u

k l k c

l (  1 )  ( ) 

l

( k  1 )  l

( k )  c

l

( n )  l

( n  1 )

v

Bellman-Ford

s

1.3.3

経路探索問題の他に，システムの故障を評価指標として考慮しない場合の問題 として，最大流問題が挙げられる．ネットワークの評価指標に「流量」を考慮し た最適化問題は，最大流量問題[33,84]として定式化されている．ここでは，一般 的な最大流量問題について述べる．はじめに基本ネットワークについて下記を仮 定する．

i.

G  ( V , E )

s

t

1

ii.

e

c

始点ノード

s

t

G

G

E

e



e

a

a

e

a

 c

1

s , t

v  V \ { s , t }

v

v

ノード

s

t

s

t

s

t

16

最大流量問題は，容量に対する流量の制約や，各ノード

_{v  V \ { s , t }}

v

v

s

t

 max

 



wt s

v

sv

a

a

を求める問題を最大流量問題という．ただし，

s

s

t

t

最大流量問題の代表的な解法としては，Ford-Fulkerson法などがある．

1)

フローを持ったネットワークには，ボトルネックが存在する．例えば水道やガ スのネットワークでは，ある区間のパイプの直径が極めて小さい場合などである．

ネットワーク全体の総フロー量は，ボトルネックのフローよって制約を受ける．

この概念を表すため，カットの考えを用いる．ノード

s , t

s

X

t

s

X

t

Y

2)

基本的な最大流量問題に対し，Fordと

Fulkerson

Ford-Fulkerson

[22]

s

_t

ネットワークの各エッジの容量の範囲内で，追加あるいは削減可能なフローを表 現したものである．また最大フローの総流量は，最小カットの容量に等しいとい う最大フロー・最小カット定理も

Ford

Fulkerson

他のネットワークの流量問題に関して，

Xue[63], Lin

[35], Yeh[64,65]

17

トワークのエッジの状態に注目し，始点ノード

s

t

流量が

d

d

Jane

Lin[37,38]

Lin[39-41]

はエッジとノードに複数の流量を定義した多状態フローネットワークに注目し，

ネットワーク全体の流量を求めるアルゴリズムを提案した．このモデルは複数の 荷室容量を考慮した都市間物流モデルなどに応用される．Assad[10] をはじめと した多くの研究者が，更に多品種流量問題へと拡張している．

1.4

電力供給網や通信網など社会インフラにおいて，対象点が連結していることや 部品が故障しないことは必須であり信頼性が最重要項目となる．しかし，建設時 であれば建設コストも当然考慮する必要があり，運用時には送配電ロスや部品の バッテリー消費量などもネットワークを維持・効率的に運用するためには重要な 要素として考えられる．このように同時に複数の評価指標を考慮する場合，複数 の目的関数を持つ多目的最適化問題として定式化される．

この多目的最適化問題に対し，古くから複数の目的関数を組み合わせにより単 一目的の問題に変換するスカラー化手法がとられていた．しかしながら，スカラ ー化による単一解を探索しても意思決定者の選好に沿った解が得られるとは言 い難く，そもそもスカラー化のための重み付パラメータの選定も困難である場合 が多い．そのため，目的関数間のトレード・オフをバランスさせた解としてパレ ート最適解を求めることが重要である．

多目的ネットワークに対して，多目的

GA

GA

Goldberg

Fonseca

GA

して挙げられる．また，並列選択と同時に，得られているパレート最適個体を保 存する手法のなどの提案も行われている．

一般的に，多目的最適化問題は，次のように定式化される[71]．

x

_{G  ( V , E )}

18 N

j  1 , 2 ,  ,

z

 g

(x )

j

f

(x )

)}

( ,

), ( ),

( {

min z

 g

x z

 g

x  z

 g

x 0

) ( .

. t f

x 

s ( k  1 , 2 ,  M )

ここで，最大化問題は表記を変換することで表現可能である．これらの各目的 関数は一般的に互いに競合しているため，各目的関数を同時に最適化することが できない．つまり，ある目的関数を改善させることは，他の目的関数を悪化させ ることとなり，トレード・オフの関係が存在する．従って，多目的最適化問題に おける合理的な解の概念として，パレート最適解が定義されている．

1.4.1

単一目的問題の場合には，すべての解候補の中で単純に最も優れた解を最適解 ということができる．しかし，多目的最適化問題では，各目的関数が互いに競合 するため，必ずしも最良な単一の完全最適解

[73]

多目的最適化問題においては，各解を単純に比較することができないため，通常 は他のどの解にも劣っていない解の集合を得ることになる．このような解をパレ ート最適解[82]と呼ぶ．

パレート最適解は，多目的最適化問題における解の優越関係により定義される．

多目的最適化問題における解の優越関係の定義は次のようになる．

【優越関係の定義】

2

x, x  _{ X}

全ての目的関数

(

j  1 , 2 ,  , N )

g

_{( x )}  g

_{( x}  ₎

_x

x

全ての目的関数

(

j  1 , 2 ,  , N )

g

( x )  g

( x  )

_x

x 

もし

_x

x

_x

x