Studies of heuristics for hostel space allocation problem.
Loading...
Date
2013
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
M. Sc. University of KwaZulu-Natal, Durban 2013.
Keywords
Heuristic algorithms., Youth hostels--Nigeria., Youth--Dwellings., Space frame cultures., Combinatorial optimization., Combinatorial analysis., Theses--Computer science.