Studies of heuristics for hostel space allocation problem.

Abstract

This research work focused on the performance of heuristics and metaheuristics for the recently defined Hostel Space Allocation Problem (HSAP), a new instance of the space allocation problem (SAP) in higher institutions of learning (HIL). SAP is a combinatorial optimisation problem that involves the distribution of spaces available amongst a set of deserving entities (rooms, bed spaces, and office spaces etc.), so that the available spaces are optimally utilized and complied with the given set of constraints. HSAP deals with the allocation of bed space in available but limited halls of residence to competing groups of students such that given requirements and constraints are satisfied as much as possible. The problem was recently introduced in literature and a preliminary, baseline solution using Genetic Algorithm (GA) was provided to show the viability of heuristics in solving the problem rather than recourse to the usual manual processing. Since the administration of hostel space allocation varies across institutions, countries and continents, the available instance is defined as obtained from a top institution in Nigeria. This instance identified is the point of focus for this research study. The main aim of this thesis is to study the strength and performance of some Local Search (LS) heuristics in solving this problem. In the process however, some hybrid techniques that combine both population-based and LS heuristics in providing solutions are derived. This enables one to carry out a comprehensive comparative study aimed at determining which heuristics and/or combination performs best for the given problem. HSAP is a multi-objective and multi-stage problem. Each stage of the allocation has different requirements and constraints. An attempt is made to provide a formulation of these problems as an optimisation problem and then provides various inter-related heuristics and meta-heuristics to solve it at different levels of the allocation process. Specifically, Hill Climbing (HC), Simulated Annealing (SA), Tabu Search (TS), Late Acceptance Hill Climbing (LAHC) and GA were applied to distribute the students at all the three levels of allocation. At each level, a comparison of the algorithms is presented. In addition, variants of the algorithms were performed from a multi-objective perspective with promising and better solutions compared to the results obtained from the manual method used by the administrators in the institutions. Comparisons and analyses of the results obtained from the above methods were done. Obtaining datasets for HSAP is a very difficult task as most institutions either do not keep proper records of past allocations or are not willing to make such records available for research purposes. The only dataset available which is also used for simulation in this study is the one recently reported in literature. However, to test the robustness of the algorithms, two new data sets that follow the pattern of the known dataset obtained from literature are randomly generated. Results obtained with these datasets further demonstrate the viability of applying tested operations research techniques efficiently to solve this new instance of SAP.