Solving University Timetabling Problems Using Constraint Programming with Adaptive Local Search and Elite Solution Memory

Анотація

University course timetabling is a complex combinatorial optimization problem that requires balancing hard feasibility requirements with diverse institutional and stakeholder preferences. This paper introduces a hybrid algorithm that integrates Constraint Programming (CP) with Adaptive Local Search (ALS) to effectively address both feasibility and solution quality. CP provides a rigorous mechanism for generating feasible initial solutions that satisfy strict requirements such as room capacities and conflict avoidance, while ALSadaptively explores neighborhoods to refine solution quality with respect to soft constraints. The approach incorporates adaptive neighborhood selection based on the pursuit algorithm, enabling the search to dynamically identify and prioritize effective operators. It further employs a multi-start framework enhanced by elite solution memory and path relinking strategies, ensuring robust intensification around promising solutions while maintaining diversification across the search space. To improve efficiency, the algorithm integrates constraint caching and incremental evaluation techniques that significantly reduce computational overhead. Experimental results on diverse datasets, demonstrate the method’s consistent ability to generate feasible, high-quality timetables. The proposed approach advances the state of the art by uniting guaranteed feasibility with adaptive optimization, offering a practical and scalable solution for real-world university scheduling systems.