Paper Info
Title
Competition-guided multi-neighborhood local search algorithm for the university course timetabling problem
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. (C) 2021 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.asoc.2021.107624
APPLIED SOFT COMPUTING
Keywords
DocType
Volume
Course timetabling, Multi-neighborhood local search, Simulated annealing, Hybrid meta-heuristic
Journal
110
ISSN
Citations 
PageRank 
1568-4946
0
0.34
References 
Authors
0
6
Name
Order
Citations
PageRank
Ting Song1316.15
Mao Chen213.07
Yulong Xu300.34
Dong Wang400.34
Xuekun Song500.34
Xiangyang Tang61911.38