2003 | OriginalPaper | Chapter
Multi-neighbourhood Local Search with Application to Course Timetabling
Authors : Luca Di Gaspero, Andrea Schaerf
Published in: Practice and Theory of Automated Timetabling IV
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A recent trend in local search concerns the exploitation of several different neighbourhood functions so as to increase the ability of the algorithm to navigate the search space.In this paper we investigate the use of local search techniques based on various combinations of neighbourhood functions, and we apply this to a timetabling problem. In particular, we propose a set of generic operators that automatically compose neighbourhood functions, giving rise to more complex ones. In the exploration of large neighbourhoods, we rely on constraint techniques to prune the list of candidates. In this way, we are able to select the most effective search technique through a systematic analysis of all possible combinations built upon a set of basic, human-defined, neighbourhood functions.The proposed ideas are applied to a practical problem, namely the Course Timetabling problem. Our algorithms are systematically tested and compared on real-world instances. The experimental analysis shows that neighbourhood composition leads to much better results than traditional local search techniques.