Ant Colony Optimization for University Course Timetabling: Implementation and Experimental Analysis

Анотація

The University Course Timetabling Problem (UCTP) is a complex NP-hard combinatorial optimization problem involving the assignment of courses to time slots and rooms under numerous hard and soft constraints. This paper presents an implementation and experimental evaluation of Ant Colony Optimization (ACO) for solving UCTP, incorporating problem-specific heuristics and an elite pheromone update strategy to guide the search process. A heuristic caching mechanism is introduced to reduce redundant computations and improve efficiency without affecting solution quality. The proposed approach is evaluated on datasets of varying sizes, enabling analysis of convergence, constraint satisfaction, and scalability. The results demonstrate that ACO is effective for small and medium-sized instances and maintains stable optimization of soft constraints as problem size increases, while also revealing scalability limitations and directions for further improvement. These findings provide practical insights into the application of ACO for automated timetabling systems.