|
Abstract:
|
This dissertation examines two discrete location problems and their bi-
objective variants. The first problem under consideration is the maximal covering
location problem with user preferences and budget constraints imposed on facility
opening. This variant of the maximal covering problem has not been previously
studied in the literature. Unlike the classical maximal covering problem, the variant
proposed in this dissertation includes user preferences for locations, where users are
assigned to the location with opened facility that they prefer the most. Additionally,
different locations have different costs for establishing facilities, and the available
budget for opening facilities is limited. This problem is solved using the Variable
Neighborhood Search (VNS) method, and the results were compared with the ones
obtained by an exact solver on modified instances from the literature. Furthermore,
an existing variant of the maximal covering problem is also addressed, which imposes
the limit on the number of opened facilities instead of limiting the budget for opening
facilities.
The second problem examined is the regenerator placement in optical networks.
In optical networks, signal quality degrades with distance, necessitating the place-
ment of costly devices to restore the signal. This dissertation studies an existing
model where the set of possible regenerator locations and the set of user nodes are
different, defining the problem as generalized. The generalized regenerator place-
ment problem in optical networks is also solved using the Variable Neighborhood
Search method, with results compared to the best available solutions from the lit-
erature.
Bi-objective variants of these problems are defined as well. For the maximal
covering location problem, user preferences are included as weighted factors in the
total covered demand, forming the first objective function. The second objective
function represents the number of uncovered users and aims to ensure fairness in
the model. In the regenerator placement problem for optical networks, it is assumed
that, due to budget constraints, uninterrupted communication between all pairs of
user nodes may not be feasible. Each pair is assigned a weight, and the sum of the
weights of connected pairs constitutes the first objective function, while the second
objective function represents the cost of placing regenerators. These bi-objective
variants are solved using an adapted multi-objective version of the Variable Neigh-
borhood Search method, and the results are compared with general evolutionary
algorithms. |