## 5 Experimental Results
### Comparison of NewKLS_FVS with Other Algorithms
\begin{table}
\begin{tabular}{l c c c c c c c} \hline \hline
**Instance** & **Best** & **Worst** & **Average** & **Instance** & **Best** & **Worst** & **Average** \\ \hline anna.col & 126 & 126 & 126 & miles1000.col & 20 & 20 & 20 \\ david.col & 66 & 66 & 66 & miles1500.col & 10 & 10 & 10 \\ DSJC125.1.col & 58 & 57 & 57 & mulsol.i.1.col & 121 & 121 & 121 \\ DSJC125.5.col & 15 & 15 & 15 & mulsol.i.2.col & 133 & 133 & 133 \\ DSJC125.9.col & 6 & 6 & 6 & mulsol.i.3.col & 129 & 129 & 129 \\ fpsol2.i.1.col & 364 & 362 & 362 & mulsol.i.4.col & 130 & 130 & 130 \\ fpsol2.i.2.col & 370 & 369 & 369 & mulsol.i.5.col & 131 & 131 & 131 \\ fpsol2.i.3.col & 344 & 344 & 344 & myciel3.col & 8 & 8 & 8 \\ games120.col & 47 & 46 & 46 & myciel4.col & 16 & 16 & 16 \\ homer.col & 520 & 520 & 520 & myciel6.col & 61 & 61 & 61 \\ huck.col & 52 & 52 & 52 & myciel7.col & 122 & 121 & 121 \\ inithx.i.1.col & 601 & 554 & 566 & queen5.5.col & 7 & 7 & 7 \\ inithx.i.2.col & 548 & 546 & 547 & queen6.6.col & 9 & 9 & 9 \\ inithx.i.3.col & 529 & 528 & 528 & queen7.7.col & 11 & 11 & 11 \\ jean.col & 63 & 63 & 63 & queen8.8.col & 13 & 13 & 13 \\ latin\_square\_10.col & 13 & 12 & 12 & queen8.12.col & 16 & 16 & 16 \\ le450\_5a.col & 112 & 107 & 109 & queen9.9.col & 14 & 14 & 14 \\ le450\_5b.col & 111 & 106 & 108 & queen10.10.col & 16 & 16 & 16 \\ le450\_5c.col & 106 & 95 & 99 & queen11.11.col & 18 & 18 & 18 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Results for k-opt-LS and a CPU-time limit of 30 min for 15 runs. \begin{table}
\begin{tabular}{l c c c c c c} \hline \hline
**Instance** & **Best** & **Worst** & **Average** & **Instance** & **Best** & **Worst** & **Average** \\ \hline le450\_5a.col & 114 & 108 & 111 & queen9.9.col & 14 & 14 & 14 \\ le450\_5b.col & 114 & 109 & 111 & queen10.10.col & 16 & 16 & 16 \\ le450\_5c.col & 104 & 94 & 98 & queen11.11.col & 18 & 18 & 18 \\ le450\_5d.col & 104 & 97 & 101 & queen12.12.col & 20 & 19 & 19 \\ le450\_15b.col & 129 & 126 & 127 & queen13.13.col & 21 & 21 & 21 \\ le450\_15c.col & 66 & 63 & 64 & queen14.14.col & 23 & 22 & 22 \\ le450\_15d.col & 67 & 65 & 65 & queen15.15.col & 25 & 24 & 24 \\ le450\_25a.col & 157 & 154 & 155 & queen16.16.col & 26 & 25 & 25 \\ le450\_25b.col & 141 & 138 & 140 & school1.col & 77 & 75 & 75 \\ le450\_25c.col & 78 & 76 & 76 & school1\_nsh.col & 71 & 67 & 69 \\ le450\_25d.col & 72 & 70 & 70 & zeroin.i.1.col & 139 & 139 & 139 \\ miles250.col & 81 & 80 & 80 & zeroin.i.2.col & 160 & 160 & 160 \\ miles500.col & 43 & 43 & 43 & zeroin.i.3.col & 156 & 156 & 156 \\ miles750.col & 27 & 27 & 27 & & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 3: _Cont._ \begin{table}
\begin{tabular}{l c c c c c c c} \hline \hline
**Instance** & **Best** & **Worst** & **Average** & **Instance** & **Best** & **Worst** & **Average** \\ \hline \hline  & 111 & 107 & 108 & miles1000.col & 16 & 14 & 14 \\  & 57 & 55 & 56 & miles1500.col & 10 & 9 & 9 \\  & 42 & 40 & 41 & mulsol.i.1.col & 38 & 35 & 36 \\  & 12 & 11 & 11 & mulsol.i.2.col & 49 & 46 & 47 \\  & 6 & 6 & 6 & mulsol.i.3.col & 48 & 44 & 45 \\  & 76 & 72 & 74 & mulsol.i.4.col & 48 & 44 & 46 \\  & 120 & 113 & 116 & mulsol.i.5.col & 49 & 45 & 46 \\  & 114 & 108 & 110 & myciel3.col & 8 & 8 & 8 \\  & 37 & 36 & 36 & myciel4.col & 16 & 16 & 16 \\  & 327 & 319 & 322 & myciel6.col & 42 & 41 & 41 \\  & 48 & 46 & 46 & myciel7.col & 56 & 53 & 54 \\  & 125 & 118 & 121 & queen5\_5.col & 7 & 7 & 7 \\  & 136 & 126 & 131 & queen6\_6.col & 9 & 9 & 9 \\  & 131 & 123 & 127 & queen7\_7.col & 11 & 11 & 11 \\  & 58 & 56 & 57 & queen8\_8.col & 12 & 12 & 12 \\  & 7 & 6 & 6 & queen8\_12.col & 15 & 14 & 14 \\  & 1450\_5a.col & 62 & 58 & 59 & queen9\_9.col & 14 & 13 & 13 \\  & 61 & 58 & 59 & queen10\_10.col & 15 & 14 & 14 \\  & 41 & 38 & 39 & queen11\_11.col & 16 & 15 & 15 \\  & 153 & 14 & 39 & 39 & queen12\_12.col & 17 & 17 & 17 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Results for variable neighborhood search 1 (VNS1) with \(k_{max}=1\) and a CPU-time limit of 30 min for 15 runs.