Adaptation of Late Acceptance Hill Climbing Algorithm for Optimizing the Office-Space Allocation Problem

摘要

Office-space-allocation (OFA) problem is a category of a timetabling problem that involves the distribution of a set of limited entities to a set of resources subject to satisfying a set of given constraints. The constraints in OFA problem is of two types: hard and soft. The hard constraints are the one that must be satisfied for the solution to be feasible while the violation of soft constraints is allowed but it must be reduced as much as possible. The quality of the OFA solution is determined by the satisfaction of the soft constraints in a feasible solution. The complexity of the OFA problem motivated the researchers in the domain of AI and Operational research to develop numerous metaheuristic-based techniques. Among recently introduced local search-based metaheuristic techniques that have been successfully utilized to solve complex optimization problem is the Late Acceptance Hill Climbing (LAHC) algorithm. This paper presents an adaptation of LAHC algorithm to tackle the OFA problem in which three neighbourhood structures are embedded with the operators of the LAHC algorithm in order to explore the solution space of the OFA efficiently. The benchmark instances proposed by the University of Nottingham and University of Wolverhampton datasets are employed in the evaluation of the proposed algorithm. The LAHC algorithm is able to produced one new result, two best results and competitive results when compared with the state-of-the-art methods.