Iterated VND Versus Hyper-heuristics: Effective and General Approaches to Course Timetabling

Citation

Soria-Alcaraz JA, Ochoa G, Sotelo-Figeroa M, Carpio M & Puga H (2017) Iterated VND Versus Hyper-heuristics: Effective and General Approaches to Course Timetabling. In: Melin P, Castillo O & Kacprzyk J (eds.) Nature-Inspired Design of Hybrid Intelligent Systems. Studies in Computational Intelligence, 667. Cham, Switzerland: Springer, pp. 687-700. https://link.springer.com/chapter/10.1007/978-3-319-47054-2_45; https://doi.org/10.1007/978-3-319-47054-2_45

Abstract
The course timetabling problem is one of the most difficult combinatorial problems, it requires the assignment of a fixed number of subjects into a number of time slots minimizing the number of student conflicts. This article presents a comparison between state-of-the-art hyper-heuristics and a newly proposed iterated variable neighborhood descent algorithm when solving the course timetabling problem. Our formulation can be seen as an adaptive iterated local search algorithm that combines several move operators in the improvement stage. Our improvement stage not only uses several neighborhoods, but it also incorporates state-of-the-art reinforcement learning mechanisms to adaptively select them on the fly. Our approach substitutes the adaptive improvement stage by a variable neighborhood descent (VND) algorithm. VND is an ingredient of the more general variable neighborhood search (VNS), a powerful metaheuristic that systematically exploits the idea of neighborhood change. This leads to a more effective search process according course timetabling benchmark results.

Keywords
Course timetabling; Iterated local search; Variable neighborhood descend; Hyper-heuristics

People

Professor Gabriela Ochoa

Professor, Computing Science