Neighborhood Analysis on the University Timetabling Problem

Metaheuristics define and explore a set of different neighborhoods, in general, adapted to specific characteristics of a problem. The quality of the solution found relies on the efficiency of the neighborhood used on the local search phase, therefore it is very important to research about the movements or combination of them which compose the neighborhood structure. This paper is based on a recent work reported on literature that deals with four standard movements for the university timetabling problem. This work complements the analysis already done so far, adding five new movements widely known in the literature. Two of then are specific for the restrictions adopted by the curriculum-based formulation proposed on the Second International Timetabling Competition (ITC-2007). The Steepest Descent (SD) algorithm was implemented to study each movement separately and combined. This analysis shows that the quality of the solutions is highly affected by the movements chosen, since the ratio between the worst and best solution (in terms of objective function value), can be up to 13.5.