Research Area:  Metaheuristic Computing

Abstract:

This paper proposes a novel competition-guided multi-neighborhood local search (CMLS) algorithm for solving the curriculum-based course timetabling problem. In comparison with the classical metaheuristic methods in the literature, the proposed algorithm includes three main contributions. Firstly, a new way of combining multiple neighborhoods is presented, according to which, only one neighborhood is selected at each iteration to make a trade-off between large search space and high computational efficiency. Secondly, two heuristic rules are proposed to determine the probabilities of selecting the neighborhood. Thirdly, a competition-based restart strategy is proposed, i.e., two SA-based multi-neighborhood local search procedures are implemented during the search process, and the elite one is selected from the two results obtained by the two procedures as the initial solution for the next round of search. The proposed algorithm is evaluated on the well-known benchmark instances, and the computational results show that the proposed algorithm is highly competitive compared with 6 state-of-the-art algorithms in the literature. Analysis of the essential ingredients of the proposed algorithm is also presented.

Keywords:  
Competition-guided multi-neighborhood local search algorithm
course timetabling problem
search space
metaheuristic

Author(s) Name:  Ting Song, Mao Chen, Yulong Xu, Dong Wang, Xuekun Song, Xiangyang Tang

Publisher name:  Elsevier

DOI:  10.1016/j.asoc.2021.107624

Volume Information:  Volume 110, October 2021, 107624

Paper Link:   https://www.sciencedirect.com/science/article/abs/pii/S1568494621005457