航路の入力数に対する性質

本実験では航路を入力する数を変化させると(RAP)の結果がどのように変化するかを 見る. 入力するインスタンスとして short ^を利用し, ^{航路は先に}4000^{個 用意しておき}, それらのなかからランダムに指定個数選んで選んだものを入力として実験するということ を200^{個 から}4000^{個 まで}200個 ずつ大きくしながら行った. ^{この実験を}30^{回行ってそ} れぞれの平均を見た.

0 0.1 0.2 0.3 0.4 0.5

200 400 600 800 1000 1200 1400 1600 1800 2000 2200 2400 2600 2800 3000 3200 3400 3600 3800 4000

平均計算時間[s]

(RAP)へ入力した航路数[個]

(1) (2)

図5.2 ^{平均計算時間}(^単位は秒). (1)^は(RAP)^{の計算時間を}, (2)^は(SAP)^の計算 時間を表している.

0.18 0.19 0.2 0.21 0.22 0.23 0.24 0.25 0.26 0.27

0 500 1000 1500 2000 2500 3000 3500 4000

平均計算時間[s]

(RAP)へ入力した航路数[個]

図5.3 (SAP)^{の計算時間}. ^{縦軸が平均計算時間}(^単位は秒), ^横軸が(RAP)^へ入力し た航路数を表す. ⇥がそれぞれの航路数に対して得られた計算間を表している.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

200 400 600 800 1000 1200 1400 1600 1800 2000 2200 2400 2600 2800 3000 3200 3400 3600 3800 4000

正規化した平均目的関数値

入力航路数[個]

図5.4 入力航路数を増加させたときの(RAP)^{の目的関数値}

まず, ^{目的関数値を見る}. ^ここでは, それぞれの目的関数値は大きく異なるので, ^各実験 における最大値で割って正規化している. ^{得られた結果は 図} 5.4^{の通りである}. ^縦軸は正 規化した平均の目的関数値を, 横軸は入力した航路数を表している. ^{図を見ると入力する} 航路数が多くなると, 目的関数値が改善されていくのがわかる. ^特に, 200^{個 から}400^個 入力するあたりで大きく改善され, それ以降は比較的ゆっくりと改善されている様子を見 ることができる.

次に, 航路が各入力に対してどの程度の数割り当てられているのかを見る. ^{得られた結} 果は 図 5.5 ^{の通りである}. 縦軸は割り当てられた平均航路数を表し, ^{横軸は入力した航路} 数を示す. ここから航路数が多くなると割り当てられる航路数はより少なく済むというこ とがわかる.

以上から, ^{より候補が多くなると}, ^{目的関数値},選ばれる航路数がともに減少することが わかった. ^これは, より多くの候補があることで, ^{より少数で}, コストが少ないような航路 割り当てを行えることを示していると考えられる. 先程の計算時間の結果と合わせると, 計算時間は大きく増えることはないので, より航路をたくさん用意しても問題はなく, ^よ りコストを抑えるような航路割当を行うことはできるが, 大きく目的関数値を下げること はできないため, 航路を生成する手間などを勘案して, 問題に合った航路数を選択するこ とが提案モデルに重要となる.

12 12.5 13 13.5 14 14.5 15 15.5 16

200 400 600 800 1000 1200 1400 1600 1800 2000 2200 2400 2600 2800 3000 3200 3400 3600 3800 4000

割り当てられた平均航路数[個]

入力航路数[個]

図5.5 入力航路数を増加させたときの(RAP)^の航路数