## 3 Computational Experiments
### First Experimental Campaign: Small Instances
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Instance**} & \multicolumn{4}{c}{\(CHa\)} & \multicolumn{4}{c}{\(CH\_1 Pa\)} \\ \cline{2-7}  & \([-10,10]\) & \([-100,100]\) & \([-1K,1K]\) & \([-10,10]\) & \([-100,100]\) & \([-1K,1K]\) \\ \hline Grid\_100\_10 & 3.6 & 20.8 & 393.8 & 0.6 & 3.4 & 58.0 \\ Grid\_225\_15 & 4.2 & 57.2 & 506.0 & 0.4 & 4.4 & 53.2 \\ Grid\_400\_20 & 4.0 & 57.0 & 448.6 & 0.0 & 2.8 & 53.2 \\ \hline
**AVG** & **3.9** & **45.0** & **449.5** & **0.3** & **3.5** & **54.8** \\ \hline Rand\_100\_02 & 5.0 & 54.0 & 782.2 & 1.4 & 15.2 & 249.0 \\ Rand\_100\_03 & 4.0 & 40.8 & 253.6 & 2.0 & 5.6 & 62.6 \\ Rand\_100\_04 & 3.4 & 21.2 & 225.2 & 0.2 & 4.4 & 49.0 \\ Rand\_100\_05 & 0.8 & 12.0 & 239.6 & 0.6 & 4.0 & 64.4 \\ Rand\_100\_10 & 0.4 & 4.2 & 40.4 & 0.0 & 0.8 & 37.4 \\ Rand\_100\_20 & 0.0 & 5.2 & 41.2 & 0.0 & 1.2 & 12.8 \\ \hline
**AVG** & **2.3** & **22.9** & **263.7** & **0.7** & **5.2** & **79.2** \\ \hline Rand\_200\_02 & 2.0 & 30.2 & 314.4 & 0.6 & 6.6 & 41.6 \\ Rand\_200\_03 & 0.8 & 18.2 & 237.0 & 0.2 & 9.4 & 123.2 \\ Rand\_200\_04 & 2.2 & 17.0 & 128.2 & 0.0 & 2.2 & 10.4 \\ Rand\_200\_05 & 1.4 & 15.0 & 73.2 & 0.2 & 1.0 & 4.6 \\ Rand\_200\_10 & 0.2 & 3.0 & 31.0 & 0.0 & 1.2 & 12.6 \\ Rand\_200\_20 & 0.0 & 0.8 & 24.8 & 0.0 & 0.6 & 3.8 \\ \hline
**AVG** & **1.1** & **14.0** & **134.8** & **0.2** & **3.5** & **32.7** \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Absolute objective function values obtained—instances with random costs. Finally, by comparing the results shown in Table 2 with the optimal values, that is for all these instances equal to zero, we can note that the optimality gap is larger for instances with costs in \([-1K,1K]\). In further computational experimentation, we solved instances whose optimal value of the objective function is not zero. In particular, the costs associated with the arcs of the corresponding graph are obtained as follows: a random cost is associated with each node in the range [0,10,000]. Then, the cost of an arc is obtained by a 1% random perturbation of the displacement of the costs. We will refer to this cost structure as _P-EL_. For this type of instance, we noted that the proposed algorithm did not provide good solutions, even if it performs very quickly. The best case corresponds to the Rand_100_03 set of instances, for which the optimal value is 6005, while the solutions obtained at the end of \(CHa\) and \(CH\_1 Pa\), respectively, are 6557 and 5431, thus corresponding to an optimality gap of 7%. Unfortunately, in the worst case, we have a set of instances (Rand_200_20) with the average optimal function value equal to 74, while our algorithm is not able to go down 2605. Note that, also in these cases, the computational time is negligible. The above computational results suggest that the proposed algorithm can produce effective solutions in case of very large instances and when the cost of the arcs is generated uniformly. Instead, it appears that the algorithm cannot be used for instances with cost-structure _P-EL_. It also seems that as the size of the instances increases, the quality of the solution produced improves, as does the number of optimal solutions identified.