Title: Three improved variants of simulated annealing for optimising dorm room assignments

Authors: Duong Tuan Anh, Nguyen Thanh Trung

Addresses: Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology, 268 Ly Thuong Kiet, Dist. 10, Ho Chi Minh City, Vietnam. ' Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology, 268 Ly Thuong Kiet, Dist. 10, Ho Chi Minh City, Vietnam

Abstract: Assigning dorm rooms to thousands of students with complex and interdependent preferences is a difficult constraint satisfaction optimisation problem. In this paper, we describe three methods that were developed to solve the whole dorm room assignment problem. They are three different improved variants of simulated annealing: informed simulated annealing, very fast simulated re-annealing and simulated annealing with non-monotonic reheating. We perform experiments of each of the algorithms on real datasets from the dormitory at HCMC University of Technology. Experimental results show that among the three selected improved variants of simulated annealing, simulated annealing with non-monotonic reheating is the most suitable algorithm to be applied to the dorm room assignment problem.

Keywords: dorm room assignments; DRAs; informed simulated annealing; ISA; very fast simulated re-annealing; VFSA; non-monotonic reheating; student dormitories; constraint satisfaction.

DOI: 10.1504/IJIIDS.2011.040090

International Journal of Intelligent Information and Database Systems, 2011 Vol.5 No.3, pp.296 - 312

Published online: 21 Oct 2014 *

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