The main goal of this paper is to attempt an unbiased comparison of the peformance of straightforward implementation of five different metaheuristics on a university course timetabling problem. In particular the metaheuristics under consideration are Evolutionary Algorithms, Ant Colony Optimization, Iterated Local Search, Simulated Annealing, and Tabu Search. To attempt fairness the implementations of all the algorithms use a common solution representation, and a common neighbourhood structure or local search. The results show that no metaheuristic is best on all the timetabling instances considered. Moreover, even when instances are very similar, from the point of view of the instance generator, it is not possible to predict the best metaheuristic, even if some trends appear when focusing on particular instance classes. These results underline the difficulty of finding the best metaheuristics even for very restricted classes of timetabling problem.
Results of a Comparison of Metaheuristics for the Timetabling
Problem within the Metaheuristics
Network
The aim of this study is to compare basic and straightforward
Implementations of the metaheuristics Ant Colony Optimization, Genetic
Algorihtms, Iterated Local Search, Simulated Annealing, and Tabu
Search. All algorithms were restricted to use the same local search
technique or a common neighborhood structure on the solution space.
Looking at the results, these rather strict restrictions have to be taken in mind. Permitting more
freedom in using more efficient data structures, more heuristic
information, etc. the results might be different.
Problem instances
Algorithms
Diagrams of the comparisons
Pairwise Wilcoxon tests for the comparisons
Hardness analysis of the instance classes
Problem instances
The timetabling problem studied within the Metaheuristics Network was
defined by
Ben Paechter
. Details can be found in the paper "A local search for the timetabling
problem" (accepted at
PATAT
2002
). We studied three classes of problem instances, defined by the following
parameters.

small

medium

large

#events

100

400

400

#rooms

5

10

10 
#features

5

5

10

#features per room (approx)

3

3

5

percentage of features used

70

80

90

#students

80

200

400

maximum #events per student

20

20

20

maximum #students per event

20

50

100

The following instances were genetrated using Ben Paechter's problem
instance generator.
Algorithms
The metaheuristics were implemented in C++. We used the
GNU compiler gcc version 2.95.3
. The following files contain the source code of the implemented metaheuristics.
They contain a makefile and the executable can be generated by simply
typing make. All algorithms use the same command line arguments as follows:
<algorithm> i <instance> t <time limit in seconds
per try> n <number of trials> s <seed for random number generator>
p <instance class 1small 2medium 3large> [o <output file>]
Ant Colony Optimization (ACO)
Genetic Algorithm (GA)
Iterated Local Search (ILS)
Simulated Annealing (SA)
Tabu Search (TS)
Diagrams of the comparisons
The diagrams show the distribution of the valid solutions that were
found in independent trials of the implemented metaheuristics. The results
of all trials on a single instance are ordered by the quality of the solution
(#number of soft constraint violations) and the rank of the solution in
all solutions. An invalid solution (with hard constraint violations) is
considered to be worse than any valid solution. Thus it is ordered behind
them. The solutions are grouped by the metaheuristic used. In the boxplots
the median is represented by a bar; a box represents the range between
the 25 % and the 75 % quantile; and the whiskers extend to the most extreme
data point which is no more than 1.5 times the interquantile range from
the box; circles represent extreme points. The percentage of invalid solutions
produced by a metaheuristic is presented in a barplot. The format of the
diagrams is Encoded Postscript.
Small instances (running time 90 seconds, 500 independant trials per
metaheuristic per instance)
Diagram
for small01
Diagram
for small02
Diagram
for small03
Diagram
for small04
Diagram
for small05
Medium instances (running time 900 seconds, 50 independant trials per
metaheuristic per instance)
Diagram
for medium01
Diagram
for medium02
Diagram
for medium03
Diagram
for medium04
Diagram
for medium05
Large instances (running time 9000 seconds, 20 independant trials per
metaheuristic per instance)
Diagram
for large01
Diagram
for large02
Pairwise Wilcoxon tests for the comparisons
For each problem instance we checked whether the differences between
the solutions found by the algorithms are statistically significant. We
used a pairwise Wilcoxon test that was adjusted to pairwise testing by a
method of Holm. In the following tables, for each pair (A,B) of metaheuristics
the pvalue for the null hypothesis "The distribution of solutions generated
by A and the distribution of solutions generated by B are equal."
Small problem instances (running time 90 seconds)
Pairwise Wilcoxon test
for small01
Pairwise Wilcoxon test
for small02
Pairwise Wilcoxon test
for small03
Pairwise Wilcoxon test
for small04
Pairwise Wilcoxon test
for small05
Medium problem instances (running time 900 seconds)
Pairwise Wilcoxon test
for medium01
Pairwise Wilcoxon test
for medium02
Pairwise Wilcoxon test
for medium03
Pairwise Wilcoxon test
for medium04
Pairwise Wilcoxon test
for medium05
Large problem instances (running time 9000 seconds)
Pairwise Wilcoxon test
for hard01
Pairwise Wilcoxon test
for hard02
Hardness analysis of the instance classes
Marco Chiarandini, Thomas Stuetzle: Experimental Evaluation of Course
Timetabling Algorithms. Technical Report, University of Darmstadt. (
gziped Postscript)