
## 4.2 Results

Table 3 shows the number of instances which have successfully been solved by the VNS algorithms in at least a single out of the 100 test runs.

| Table 3: Number of instances for which optimal/best known solutions have been found by VNS Algorithm n = 40 n = 50 n = 100 VNS-1 (EX→FSH→BSH) 121 114 108 VNS-2 (BSH→FSH→EX) 125 124 117   |
|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|

 2009 We can see that VNS-2 **is able to solve more instances than** VNS-1**. It can be suspected that this**
behavior originates from the relative order of neighborhood operators. VNS-2 **starts with the weak**
operator BSH**, and then continues to relatively better neighborhoods. Therefore, an improvement of**
solutions being locally optimal to the initially searched neighborhoods appears to be more likely as in the case of VNS-1**, where search is organized starting with relatively good operators.**
Again, the number of solved instances is decreasing with increasing n**. However, the results remain**
on a rather high level despite the growing difficulty of the benchmark instances. Only few instances remain unsolved.

| Table 4: Number of instances solved to optimality by VNS depending on RDD and T F VNS-1 VNS-2 T F: 0.2 0.4 0.6 0.8 1.0 0.2 0.4 0.6 0.8 1.0 RDD: 0.2 15 14 11 13 15 15 15 15 15 15 0.4 13 14 14 12 15 15 15 14 14 15 0.6 15 11 11 15 15 15 15 15 15 14 0.8 15 11 13 15 15 15 15 12 14 15 1.0 15 14 12 15 15 15 14 15 14 15   |
|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|

MIC
More detailed results are given in Table 4, which shows the number of solved instances with respect to the choices of RDD and T F**. In comparison to the results obtained by hillclimbing, a**
similar pattern arises in the investigation of VNS. Again, both small and high values of T F **lead**
to easy instances. In the light of the overall impressive results of VNS however, this pattern is less obvious. Knowing that VNS-2 successfully solved 97.6% of the benchmark instances, only few instances are left that can be considered to be 'difficult'.

Besides the best-case behavior of the algorithms, the average quality of the local optima over all 100 test runs is interesting. Table 5 gives the results with respect to this.

 $\begin{array}{c}\text{Table5:A}\\ \hline\text{Alg}\\ \hline\text{VMS}\end{array}$

| Table 5: Average deviation from the optimal/best known solution Algorithm n = 40 n = 50 n = 100 VNS-1 (EX→FSH→BSH) 2.59% 2.36% 2.10% VNS-2 (BSH→FSH→EX) 0.99% 1.45% 0.98%   |
|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------|

Also on an average level, VNS-2 **leads to better results than** VNS-1**. Moreover, the average**
Hamburg, Germany, June 13–16, 2009