Title: A simulated annealing algorithm for university course timetabling considering travelling distances

Authors: Shuang Zheng; Long Wang; Yueyue Liu; Rui Zhang

Addresses: School of Economics and Management, Nanchang University, Nanchang 330031, China ' Department of Automation, Tsinghua University, Beijing 100084, China ' School of Economics and Management, Nanchang University, Nanchang 330031, China ' School of Economics and Management, Nanchang University, Nanchang 330031, China

Abstract: This paper addresses the curriculum-based course timetabling problem (CB-CCT) with extra travelling distance constraints using an improved simulated annealing algorithm. The motivation of considering the new constraints is that the travelling distances between two consecutive lectures attended by the same group of students must be controlled into a certain range in order to facilitate on-campus transportation. We propose a two-stage solution method, which circumvents the hard constraints violations firstly, and minimises the soft constraints violations subsequently. To obtain satisfactory solutions, an improved simulated annealing algorithm with memory function (ISAM) is adopted, which incorporates a variety of space adjustment and time adjustment strategies as the local search module. We study the impact of the initial solution, the annealing strategy, and the search depth of ISAM on the final solution quality. The computational results show that the improved simulated annealing algorithm can solve the course timetabling problem effectively.

Keywords: university courses; course timetabling; simulated annealing; memory function; local search; travelling distance; higher education; on-campus transport; consecutive lectures.

DOI: 10.1504/IJCSM.2015.069461

International Journal of Computing Science and Mathematics, 2015 Vol.6 No.2, pp.139 - 151

Received: 15 Jul 2014
Accepted: 26 Aug 2014
Published online: 17 May 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article