Solving the post enrolment course timetabling problem by ant colony optimization |
| |
Authors: | Clemens Nothegger Alfred Mayer Andreas Chwatal Günther R. Raidl |
| |
Affiliation: | (1) Institute of Photogrammetry and Remote Sensing, Vienna University of Technology, Gusshausstr. 27-29, 1040 Vienna, Austria;(2) Institute of Computer Graphics and Algorithms, Vienna University of Technology, Favoritenstr. 9-11, Vienna, Austria |
| |
Abstract: | In this work we present a new approach to tackle the problem of Post Enrolment Course Timetabling as specified for the International Timetabling Competition 2007 (ITC2007), competition track 2. The heuristic procedure is based on Ant Colony Optimization (ACO) where artificial ants successively construct solutions based on pheromones (stigmergy) and local information. The key feature of our algorithm is the use of two distinct but simplified pheromone matrices in order to improve convergence but still provide enough flexibility for effectively guiding the solution construction process. We show that by parallelizing the algorithm we can improve the solution quality significantly. We applied our algorithm to the instances used for the ITC2007. The results document that our approach is among the leading algorithms for this problem; in all cases the optimal solution could be found. Furthermore we discuss the characteristics of the instances where the algorithm performs especially well. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|