Page 243 - 《软件学报》2025年第8期

3666 软件学报 2025 年第 36 卷第 8 期

表 1 在 随机 UDG 实例上的实验结果

CPLEX MWCDS MA GRASP GRASP_impLS FPLS
Nodes R |E|
Solu Stat Best Avg Time Best Avg Best Avg Best Avg Best Avg
15 18 6 5.5 6 6.6 <0.01 6 6.0 6 6.0 6 6.0 6 6.0
16 22 6 4.42 6 6.0 <0.01 6 6.0 6 6.0 6 6.0 6 6.0
15 17 22 6 4.11 6 6.0 <0.01 6 6.0 6 6.0 6 6.0 6 6.0
(N=80) 18 19 6 3.54 6 6.0 <0.01 6 6.0 6 6.0 6 6.0 6 6.0
19 19 6 3.23 6 6.0 <0.01 6 6.0 6 6.0 6 6.0 6 6.0
20 22 4 0.69 5 5.5 <0.01 4 4.0 4 4.0 4 4.0 4 4.0
20 27 8 Feasible 8 8.5 <0.01 8 8.0 8 8.0 8 8.0 8 8.0
21 32 6 58.86 6 6.8 <0.01 6 6.0 6 6.0 6 6.0 6 6.0
20 22 35 5 6.46 5 6.6 <0.01 5 5.0 5 5.0 5 5.0 5 5.0
(N=100) 23 34 6 62.77 7 7.4 <0.01 6 6.0 7 7.0 6 6.0 6 6.0
24 29 6 47.91 6 7.3 <0.01 6 6.0 6 6.0 6 6.0 6 6.0
25 34 5 5.19 6 6.4 <0.01 5 5.0 5 5.0 5 5.0 5 5.0
20 44 7 Feasible 9 9.0 <0.01 7 7.0 8 8.0 7 7.0 7 7.0
21 47 7 Feasible 8 8.8 <0.01 7 7.0 8 8.0 7 7.0 7 7.0
25 22 49 6 753.01 8 8.8 <0.01 6 6.0 7 7.0 6 6.0 6 6.0
(N=100) 23 53 6 1 296.45 7 8.5 <0.01 6 6.0 6 6.0 6 6.0 6 6.0
24 59 6 2 240.62 7 7.8 <0.01 6 6.0 6 6.0 6 6.0 6 6.0
25 45 7 Feasible 8 8.7 <0.01 7 7.1 7 7.0 7 7.1 7 7.0
25 46 N/A N/A 12 12.3 <0.01 11 11.0 11 11.0 11 11.0 11 11.0
26 42 9 Feasible 10 12.0 <0.01 9 9.0 9 9.0 9 9.0 9 9.0
30 27 40 N/A N/A 11 12.6 <0.01 11 11.0 13 13.0 11 11.0 11 11.0
(N=150) 28 43 N/A N/A 10 11.9 <0.01 10 10.0 11 11.0 10 10.0 10 10.0
29 49 9 Feasible 9 10.6 <0.01 9 9.0 9 9.0 9 9.0 9 9.0
30 49 9 Feasible 9 10.6 <0.01 9 9.0 9 9.0 9 9.0 9 9.0
最小值 － － 5 5.5 － 4 4.0 4 4.0 4 4.0 4 4.0
最大值 － － 12 12.6 － 11 11.0 13 13.0 11 11.0 11 11.0
平均值 － － 7.54 8.36 － 7.00 7.00 7.29 7.29 7.00 7.00 7.00 7.00
标准差 － － 1.91 2.24 － 1.89 1.89 2.16 2.16 1.89 1.89 1.89 1.89
注: 加粗数值是对应算法找到的最优值

表 2 在 LPNMR’09 实例上的实验结果

CPLEX MWCDS MA GRASP GRASP_impLS FPLS
实例 |V| |E|
Solu Stat Best Avg Time Best Avg Best Avg Best Avg Best Avg
40 × 200 40 200 5 Feasible 8 9.4 <0.01 5 5.0 5 5.0 5 5.0 5 5.0
45 × 250 45 250 5 Feasible 8 9.2 <0.01 5 5.0 5 5.0 5 5.0 5 5.0
50 × 250(1) 50 236 N/A N/A 11 11.9 <0.01 7 7.0 7 7.0 7 7.0 7 7.0
50 × 250(2) 50 240 N/A N/A 9 11.3 <0.01 6 6.0 6 6.0 6 6.0 6 6.0
55 × 250 55 250 N/A N/A 10 12.3 <0.01 7 7.0 7 7.0 7 7.0 7 7.0
60 × 400 60 400 N/A N/A 10 11.0 <0.01 6 6.0 6 6.0 6 6.0 6 6.0
70 × 250 70 250 N/A N/A 17 19.4 <0.01 11 11.0 11 11.0 11 11.0 11 11.0
80 × 500 80 500 N/A N/A 14 15.9 <0.01 8 8.0 8 8.0 8 8.0 8 8.0
90 × 600 90 600 N/A N/A 16 17.8 <0.01 9 9.0 9 9.0 9 9.0 9 9.0
最小值 － － 8 9.2 0.00 5 5.0 5 5.0 5 5.0 5 5.0
最大值 － － 17 19.4 0.00 11 11.0 11 11.0 11 11.0 11 11.0
平均值 － － 11.44 13.13 0.00 7.11 7.11 7.11 7.11 7.11 7.11 7.11 7.11
标准差 － － 3.40 3.68 0.00 1.96 1.96 1.96 1.96 1.96 1.96 1.96 1.96
注: 加粗数值是对应算法找到的最优值