New bounds for Office Space Allocation using Tabu search

The Office Space Allocation problem is a combinatorial optimization problem which focuses into determining the way to assign spaces to entities in order to optimize the use of available space in an organization. This allocation process considers a set of preferences, constraints and requirements. In this paper we propose a metaheuristic approach that includes a construction step and an improvement step, based on Greedy and Tabu Search techniques respectively. Here, we propose a construction method specially designed to deal with the misused space and hard/soft constraints of the problem. Then, Tabu Search performs a fast analysis that allows it to find good quality neighborhoods to analyze. We used an automated tuning method to determine the best parameter values for the entire set of benchmarks. Results show that our approach was able to obtain new lower bounds for seven problem instances.