提案アルゴリズム

84

85

この問題の解について，以下の性質4-2が成立する[58,79]．

性質4-2

 X

x に 対 し て 式 (4.2) を 満 た す 経 路 を x_s と す る ． す な わ ち }

) ( {

min arg

1





  ^N

j

j X j

s w g x

x

x

である．このときx_sはパレート最適解である．

証明：x_sがパレート最適解でないならば，x_sを優越する他の経路_xが存在する．

パレート最適解の定義から，一般性を失うことなく，_{g1(x¢)<g1(xs)}，g₂(x)g₂(x_s)，

，g_N(x)g_N(x_s)とする．このとき，

 





  ^N

j

s j j N

j j

jg w g

w

1 1

) ( )

(x x ．これはx_sの

定義に反する．よって性質2は証明される．

性質 4-2 を満たす経路xを基準経路とすることで削減される探索空間を，

3 ,

2

N の場合を例に図4-4(a)と図4-4(b)を用いて示す．ただし，図中の点は終点 ノードtまでの経路に対応し，途中ノードまでの経路は示されていない．図4-4(a) と(b)において，g₁,g₂を軸とした2次元平面とg₁,g₂,g₃を軸とした3次元空間に，

それぞれw₁g₁w₂g₂ 0を満たす直線とw₁g₁w₂g₂ w₃g₃ 0を満たす平面を考 える．この平面をg_jが増加する方向へ移動させたとき，初めて解集合X の要素 と交点となる経路がx_sとなる．

図4-4(a) 性質4-2を満たす基準経路x_sの探索(N=2)

86

図4-4(b) 性質4-2を満たす基準経路x_sの探索(N=3)

ここで，s₁  g₁(x_s), s₂  g₂(x_s), s₃  g₃(x_s) とすると，経路x_sの座標は，

2次元平面上で(s₁,s₂)，3次元空間上で(s₁,s₂,s₃)となる．この基準経路 x_sによ り，g₁s₁^，g₂ s₂^, g₃ s₃を全て満たす空間{(g₁,g₂,g₃)}が探索空間から削減さ れる．

次に下記のパレート最適解の性質を考える．

性質4-3 N

j1,2,, に対し，g_j  g_j(x_s)を全て満たす空間には，パレート最適解は 存在しない．

本項では，上記から得られる基準経路 xs による空間削減方法を一点削減と呼 び，拡張ダイクストラ法に下記を追加することで実現する．

【一点削減】

(拡張ダイクストラ法に以下のSTEP 0を追加する) STEP 0：(x_s の探索)

STEP 0-1： に対して w_j 1 とし，ダイクストラ法により経路 x_s

を探索する．

STEP 0-2：経路 x_s からコストベクトル を得る．

87

(拡張ダイクストラ法のパレート最適解判定手順の STEP 1 と STEP 2 の間に 下記 STEP を追加する)

STEP： に対して l_k^*_ s_k を全て満たすならば，受け取ったラベ

ル のパレート最適解判定を終了する．それ以外は STEP 2 へ進む．

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

性質 4-3 で示した通り，事前に基準経路xを探索すると，探索空間を削減する ことができる．しかし基準経路xの違いにより，探索空間の削減効率が異なるこ とが予測される．実際に性質4-2を満たす基準経路x_sもw₁,w₂,,w_Nの値により，

異なった基準経路が選択されることになる．また，本論文では基準経路は1つで はなく複数の方がより広い探索空間が削減可能である点に注目する．基準経路の 探索方法として，各目的関数においてパレート最適解の中央値に近い経路を基準 経路とすることで，すべての目的関数に対し均等に経路探索を削減できると考え られる．こで，本論文では各軸方向に対するパレート最適解の分布の偏りに対応 するために，複数の性質4-2を満たす基準経路を探索する方法を考える．

4.4.2 項で提案した制約付き単目的最適経路問題においてw_jの値の違いにより

複数の平面を考える．ここで w_j の値が一つだけ異なる場合を以下のように考 える．

制約条件付き単目的最適経路問題2 N

h1,2,, に対し，以下を満たす x を求める．

min )

( )

( )

(

1 1

1











 





N

h j

j j h

h h

j j

jg w g w g

w x x x (4.3) s.t. xX ,



 N 

j

wj 1

1,

1 0

1 2

1       

 _{h h N}

h w w w w w

w   ，



 0 

1

0 ) (

j j jg

w x ．

88

このとき，_{h1,2,,N}に対して各関数が最小となる経路が N 個得られる．

} ) ( )

( )

( {

min arg

1 1

1 )

(

 







   

 ^N

h j

j j h

h h

j j X j

h

u w g x w g x w g x

x

x

本項では，上記から得られる基準経路を用いて，目的関数値の分布に応じたパ レ ート最 適解の中央値の探索するために，_{h1,2,,N} に対して基準経路 と上記の基準経路 x_s による空間削減を提案する．N1点の基 準経路を生成する_wjは，それぞれ次の通りである．

基準経路 x_s：w_jが全て均衡な場合

の比で表される場合の制約条件付き単目的最適経路 問題の最適経路を _xs，その経路のコストベクトルを とする．

また，u1に対し次の基準経路を設定する．

基準経路 x_u(h)：w_jが不均衡な場合

, ,…,w₁:w₂::w_N 1:1::u の比とした場合の制約条件付き単目的最適経路問題の最適経路を，それぞれx_u(1),

) ( ) 2

( , , _{u N}

u x

x  とする．ここで , に対して y_hk g_k(x_u(h)) とすると，経路 x_u(h) のコストベクトルは で表される．

上記の基準経路 x_s,x_u(1),x_u(2),,x_u(N) で探索空間を削減する方法を提案法1と する． 提案法1では，次の探索空間削減過程を拡張ダイクストラ法に追加する．

【提案法1】

(拡張ダイクストラ法に以下のSTEP 0を追加する)

STEP 0：(x_s と の探索)

STEP 0-1： に対して w_j 1 とし，ダイクストラ法により経路 x_s

を探索する．

STEP 0-2：経路 x_s からコストベクトル を得る．

STEP 0-3：任意の値 u (u1) を決定し，h1 とする．

STEP 0-4：w_h u としてダイクストラ法により経路 _xu(h) を探索する．

STEP 0-5：経路 _xu(h) からコストベクトル (y_h1,y_h2,,y_hN) を得る．

STEP 0-6：h=N ならば STEP 1 へ進む．それ以外は w_h1, hh1 とし

89

STEP 0-4 に戻る．

(拡張ダイクストラ法のパレート最適解判定手順の STEP 1 と STEP 2 の間に 下記 STEP を追加する)

STEP： 次 の (a) (b) の い ず れ か を 満 た す な ら ば ， 受 け 取 っ た ラ ベ ル のパレート最適解判定を終了する．それ以外は STEP 2 へ進む．

(a) に対して l_k^*_ s_k を全て満たす．または，

(b) のいずれかにおいて， に対して l_k^*_  y_hk を 全て満たす．

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

各目的関数値の分布に大きな偏りがある場合，座標軸に近い空間に多くの経路 が存在する可能性がある．そこで座標軸付近の探索空間を削減するために，提案 法1の基準経路x_sと各目的関数のみで求められる最適経路による基準経路で，探 索空間を削減する方法を提案する．まず，下記の性質を考える．

性質4-4

目的関数 _j_1,2,,N に対して，集合 ^Xj ^{x^|gj⁽x⁾^mgj^,x^X} を考える．

ただし _{j1,2,,N} に対して，mg_jはg_j(x)の最小値である．このとき，任意の 経路 x_j X_jに対して，_gj  _gj(xj)を全て満たす空間にはパレート最適解は存在 しない．

N=3 ^{の場合で基準経路 x}₁,x₂,x₃ により削減される探索空間を図4-5に示す．

ここで経路 _xjXj が k 個存在する場合，すなわち，x_jiX_j (i1,2,,k)なら ば，求められた k 個の経路中でパレート最適解を求め，パレート最適解の中か ら任意の1点を選択して基準経路とする．

90

図4-5 基準経路 x₁,x₂,x₃ が削減する探索空間

性質4-4を満たす基準経路で探索空間を削減する方法を提案法 2とする．提案 法2では次の探索空間削減過程を拡張ダイクストラ法に追加する．

【提案法2】

(拡張ダイクストラ法に以下のSTEP 0を追加)

STEP 0：(x_s と の探索)

STEP 0-1： に対して w_j 1 とし，ダイクストラ法により経路 x_s

を探索する．

STEP 0-2：経路 x_s からコストベクトル を得る．

STEP 0-3：i1 とする．

STEP 0-4：ダイクストラ法により基準経路 x_i を探索する．

STEP 0-5：要素数 X_i 2 のとき，X_iにおいて解の優越が存在するならば，

被優越解 xij に対し ^{Xi  Xi \{xij}} とする．

STEP 0-6：経路 x_iX_i からコストベクトル(y_i1,y_i2,,y_iN) ))

( , ), ( ), (

(g₁ x_i g₂ x_i  g_N x_i

 を得る．

STEP 0-7：iN ならば STEP 1 へ進む．それ以外は ii1 としてSTEP 0-4 に戻る．

91

(拡張ダイクストラ法のパレート最適解判定の STEP 1 と STEP 2 の間に下記 STEPを追加)

STEP：次のいずれかを満たすならば，受け取ったラベル の

パレート最適解判定を終了する．それ以外は STEP 2 へ進む．

(a) に対して _lk^*_{ sk} を全て満たす．または，

(b) のいずれかにおいて， に対して _l^*_{k gk(xh)} を全て満たす．

ドキュメント内 多目的ネットワークシステムの評価指標算出方法 に関する研究 (ページ 88-95)