
| Table 5 Average results of the top five competitors of ITC 2007, track 3 Instance M¨uller Lu, Hao Atsuta, Geiger Clark, (USA) (France) Nonobe, (Germany) Henz, Love Ibaraki (Singapore) (Japan) Rank: 1 2 3 4 5 comp01.ctt 5.0 5.0 5.1 6.7 27.0 comp02.ctt 61.3 61.2 65.6 142.7 131.1 comp03.ctt 94.8 84.5 89.1 160.3 138.4 comp04.ctt 42.8 46.9 39.2 82.0 90.2 comp05.ctt 343.5 326.0 334.5 525.4 811.5 comp06.ctt 56.8 69.4 74.1 110.8 149.3 comp07.ctt 33.9 41.5 49.8 76.6 153.4 comp08.ctt 46.5 52.6 46.0 81.7 96.5 comp09.ctt 113.1 116.5 113.3 164.1 148.9 comp10.ctt 21.3 34.8 36.9 81.3 101.3 comp11.ctt 0.0 0.0 0.0 0.3 5.7 comp12.ctt 351.6 360.1 361.6 485.1 445.3 comp13.ctt 73.9 79.2 76.1 110.4 122.9 comp14.ctt 61.8 65.9 62.3 99.0 105.9 comp15.ctt 94.8 84.5 89.1 160.3 138.0 comp16.ctt 41.2 49.1 50.2 92.6 107.3 comp17.ctt 86.6 100.7 107.3 143.4 166.6 comp18.ctt 91.7 80.7 73.3 129.4 126.8 comp19.ctt 68.8 69.5 79.6 132.8 125.4 comp20.ctt 34.3 60.9 65.0 97.5 179.3 comp21.ctt 108.0 124.7 138.1 185.3 185.8   |
| |

## 4.4 Convergence In Longer Runs

In contrast to the optimization runs for the ITC 2007, we allow in the following experiments the evaluation of 100 million timetables before terminating the algorithm.

Again, 30 trials have been carried out, and Table 6 gives the best found solutions out of all test runs.

Obviously, the Threshold Accepting algorithm did not converge after only 375 seconds. Rather big improvements can be seen for most instances, sometimes improving the best solution by 25% (comp10.ctt**). For the instances with large values of** sc, comp05.ctt and comp12.ctt**, improvements are possible, but the absolute values remain rather high. We suspect that these instances possess properties that complicate**
the identification of timetables with small soft constraint **violations. Recalling that**
instance comp05.ctt **was problematic with respect to the identification of a feasible**
assignment in the initial experiments, this is however not surprising.

No improvements are possible for instance comp01.ctt**, and of course for instance**
comp11.ctt.

In comparison to the three top ranked finalists of ITC 2007, inferior overall results are found, even when allowing the execution of 100,000,000 evaluations. Independent from the personal programming skills of the competitors, which are unknown to us and difficult to assess, we suspect that the performance of the approaches is mainly due to the algorithms as such.

10