数値実験による評価

91

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

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

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

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

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

92

提案法1： , 10 3

1

3 2

1w w  h

w

1点削減，提案法2：

3 1

3 2

1w w 

w

数値実験は，同一ノード数にてCase 1とCase 2でそれぞれ5種類のネットワ ークを作成し行った．また，ネットワークのノード数パターンが各Caseで10種 類なので，合計100種類 (=2×5×10) のネットワークに対し，3つの方法でパレ ート最適解を求め，各ノード数パターン及び各 Case 別に計算時間とラベル数の 平均を求めた．

表4-1と表4-2はノード数1000でCase 1の時の計算時間とラベル数について，

表4-3と表4-4はノード数1000でCase 2の時の計算時間とラベル数について比 較した結果である．1点削減と提案法では，計算時間とラベル総数で拡張ダイク ストラ法の結果に対する比率を求めた．また，図4-6と図4-7にノード数100か ら1000まで (100刻み) のネットワークでの計算時間の比較を表した．図4-8と 図4-9には，計算時間と同様のネットワークにおいて，計算過程で生成されたラ ベル数の比較を表している．

表 4-1 Case 1の計算時間の比較(ノード数：1000) アルゴリズム 平均計算時間

時間(秒) 比率 標準偏差 変動係数

拡張ダイクストラ 276.65 - 26.11 0.09

1点削減 59.23 21.41% 14.50 0.24

提案法1 30.14 10.90% 12.37 0.41 提案法2 55.00 19.88% 18.10 0.33

93

表 4-2 Case 1のラベル数の比較(ノード数：1000) アルゴリズム 平均ラベル数

ラベル数 比率 標準偏差 変動係数

拡張ダイクストラ 117183600.00 - 6152184.92 0.05

1点削減 20824091.00 17.77% 5977498.17 0.29

提案法1 5033228.00 4.30% 3354404.69 0.67 提案法2 16028169.00 13.68% 7011363.94 0.44

表 4-3 Case 2の計算時間の比較(ノード数：1000) アルゴリズム 平均計算時間

時間(秒) 比率 標準偏差 変動係数

拡張ダイクストラ 636.13 - 49.80 0.08

1点削減 404.83 63.64% 81.74 0.20

提案法1 148.69 23.37% 66.43 0.45 提案法2 296.28 46.57% 106.42 0.36

表 4-4 Case 2のラベル数の比較(ノード数：1000) アルゴリズム 平均ラベル数

ラベル数 比率 標準偏差 変動係数

拡張ダイクストラ 193660000.00 - 7015081.33 0.04

1点削減 129834090.60 67.04% 23209018.41 0.18

提案法1 43390560.20 22.41% 23391449.77 0.54 提案法2 88747708.80 45.83% 34226711.33 0.39

94

図4-6 Case 1の計算時間比較

図4-7 Case 2の計算時間比較

95

図4-8 Case 1のラベル数比較

図4-9 Case 2のラベル数比較

96

拡張ダイクストラ法の計算時間と比較すると，提案法1はCase 1の場合は拡張ダ イクストラ法の10-30%の計算時間，Case 2では20-40%の計算時間へ減少した．ま た，提案法2ではCase 1のときは拡張ダイクストラ法の20-40%の計算時間，Case 2 では30-60%の計算時間へ減少した．ラベル数に関しても，ほぼ同様な減少傾向が 見られた．複数の経路で探索空間を削減する効果は，エッジコストの設定条件に より変化するが，2つの提案法を比較すると，実験した範囲内では全体的に提案 法2より提案法1の方が計算時間が大きく短縮され有効であった．実際，提案法1 と提案法2の計算時間に対し，ノード数のパターン別およびコストのCase別の結 果について有意水準5%で検定を行い，その結果，20個 (ノード数パターン(10)

×コストCase(2) = 20) 中，11個で，提案法1の方が提案法2より計算時間が短い との結論を得た．ラベル数に関しても，11個で提案法1の方が提案法2よりもラベ ル数が少ないと判定された．

Case 1とCase 2の場合で，ともに提案法1が優位な結果であったことから，提

案法1の基準経路で削減した空間が目的関数値の偏りがある空間まで及んでいた と考えられる．また，提案法2の効果が小さかった理由としては，生成したネッ トワークにおいて座標軸付近に存在する経路が少なかったためと思われる．特に

Case 2の場合において，非優越となる経路があまり存在しない空間で基準経路が

探索された可能性が高い．