Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art

Two ant algorithms solving a simplified version of a typical university course timetabling problem are presented -- the Ant Colony System and MAX-MIN Ant System. The algorithms are tested over a set of instances from three classes of the problem. Results obtained are compared with recent results obtained with several metaheuristics using the same local search routine (or neighborhood definition). Further, both ant algorithms are compared on additional set of instances. The conclusions are drawn about the performance of ant algorithms on timetabling problems in comparison to other metaheuristics. Also the design, implementation, and parameters of ant algorithms solving university course timetabling problem are discussed. It is shown that the particular implementation of an ant algorithm has large influence on the actual algorithm performance.

Software:

The algorithms were implemented in C++. We used the GNU compiler gcc version 2.95.3. The following files contain the source code of the implemented algorithms:

MAX-MIN Ant System (MMAS)
Ant Colony System (ACS)
Random Restart Local Search (RRLS)

Other algorithms used as a reference in the comparison, may be found here.

The files contain the source code and a makefile. The executable can be generated by simply typing make. All algorithms use the same following command line arguments:

<algorithm> -i <instance> -t <time limit in seconds per try> -n <number of trials> [-s <seed for random number generator> -o <output file>]

Additionally to the parameters specified above, the mmas uses the following command line parameters:
-ant <number of ants> -evp <evaporation coefficient (rho)> -min <minimal pheromone level (tau_min)>

Note: The values of these parameters that need to be set to recreate the results, are presented in the paper.

The acs in turn uses the following additional command line parameters:
-p <type of problem being solved: 2 - medium problem, 3 - hard problem.>

Note: Although there is a large number of parameters possible to set for ACS, specifying the parameter -p will allow to recreate the results. For medium and competition instances p=2, for hard instances p=3.

Data sets:

We tested the algorithms on some of the instances available for testing several metaheuristics on UCTP problem (Metaheuristic Network). They are available here. Additional 10 competition instances, which we used, were taken from the International Timetabling Competition.

Results:

Boxplot comparing MMAS and ACS with SA, ILS, and RRLS for the medium instances (eps-format available here):
Boxplot Medium

Boxplot comparing MMAS and ACS with SA, ILS, and RRLS for the large instances (eps-format available here):
Boxplot Large

Boxplot comparing MMAS and ACS with and also the NEW MMAS and NEW ACS for the competition instances (eps-format available here):
Boxplot Competition

Supporting material for the paper: