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 straight-forward 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.

Instance name	Data
small01	small01.tim
small02	small02.tim
small03	small03.tim
small04	small04.tim
small05	small05.tim
medium01	medium01.tim
medium02	medium02.tim
medium03	medium03.tim
medium04	medium04.tim
medium05	medium05.tim
large01	large01.tim
large02	large02.tim

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 1-small 2-medium 3-large> [-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 p-value 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)