|
Abstract:
|
In this dissertation, three NP-hard min-max discrete optimization
problems are considered. The rst considered problem is multi-period
emergency service location problem, the second one is dynamic maximal covering
location problem with multiple covering radii, and the third one is
uncapacitated multiple allocation p-hub center problem. In many practical
situations, input parameters (such as user demands, transportation time or
cost) often vary with unknown distributions. Therefore, it is necessary to
involve these uncertainties in the deterministic variants of the problems by
applying robust optimization approach. Mathematical models for the deterministic
and non-deterministic variants of all three problems are developed,
except for the deterministic uncapacitated multiple allocation p-hub center
problem, which has already been addressed in the literature. In addition,
for the rst time in the literature, it was proven that the emergency service
location problem is NP-hard.
The considered problems and their robust variants have numerous applications,
due to the fact that in real-life situations input parameters are
often subject to uncertainty. Multi-period emergency service location problem
may be used when determining optimal locations for police stations,
re brigades, ambulances, and other emergency units in the given region.
The dynamic maximal covering location problem with multiple covering radii
is useful when choosing the optimal strategy for establishing resources
(service centers, suppliers, facilities, etc.) with maximal satisfaction of customer
demands in a certain region, by assuming that the service e ciency
directly depends on the distance between customer and service center (i.e.,
the selected coverage radius). The uncapacitated multiple allocation p-hub
center problem has signi cant applications in designing telecommunication
and transportation networks, postal delivery systems, emergency systems,
supply networks, etc.
Since exact methods provide optimal solutions only for problem instances
of small dimensions, hybrid metaheuristic algorithms are developed to solve
both deterministic and robust variants of the considered problems. The
proposed hybrid algorithms are obtained by combining particle swarm optimization,
with local search heuristic { classical local search or variable neighborhood
search method. For dynamic maximal covering location problem
with multiple covering radii, a hybridization of metaheuristic algorithm with
exact method based on linear programming is developed. All elements of
the proposed algorithms are adopted to the problems under consideration.
Di erent strategies are implemented for improving the e ciency of proposed
algorithms, especially for the calculation of the objective function value
and the local search part. The in
uence of di erent parameters of hybrid
algorithms on the solution quality is analyzed in detail. All parameters are
adjusted by using analysis of variance.
For all considered problems (both deterministic and robust variant), the
performance of the proposed hybrid algorithms is evaluated on adequate test
data sets. The proposed algorithms are compared with existing heuristic
from the literature and exact methods incorporated in commercial CPLEX
solver. The obtained experimental results indicate the e ciency of proposed
algorithms in obtaining high quality solutions for all considered test instances.
The presented comparative analysis indicates the advantages of the
proposed hybrid algorithms over existing methods in the sense of solution
quality and/or required computational time, especially in the case of large
problem dimensions.
The results presented in this paper represent a contribution to the eld
of discrete optimization, robust optimization and metaheuristic methods. |