Three improved variants of simulated annealing for optimising dorm room assignments. (16th May 2011) - Anh, Duong Tuan; Trung, Nguyen Thanh
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.