|
Zusammenfassung:
|
Hub Location Problems (HLP) represent an important class of optimiza-
tion problems due to their numerous applications in many areas of real life. They
often arise from practical situations that require routing of the flow from origin node
(supplier) to the destination node (customer) under given conditions, such that the
value of considered objective function is optimal. Hubs are special objects (nodes
in the network) that represent centres for consolidation and flow collection between
two selected locations - suppliers and customers. As transportation costs (per unit
of flow) along the links that connect hub nodes are lower compared to other links
in the network, directing the flow to hubs may lead to significant reductions of
transportation cost in the network.
The subject of this doctoral dissertation is one class of hub location problems,
denoted as Hub Maximal Covering Problems (HMCPs) in the literature. The goal
of HMCPs is to determine optimal locations for establishing certain number of hubs
in order to maximize the total flow between all the covered origin-destination pairs,
under the assumption of binary or partial covering. Three variants of the hub
maximal covering problem are considered: uncapacitated single allocation
p
-hub
maximal covering problem (USApHMCP), uncapacitated multiple allocation
p
-hub
maximal covering problem (UMApHMCP) and uncapacitated
r
-allocation
p
-hub
maximal covering problem (UrApHMCP). Note that the UrApHMCP has not been
studied in the literature so far. All three considered problems are proven to be NP-
hard. In case of USApHMCP, for the given set of hubs, the obtained sub-problem
of optimal allocation of non-hub nodes by established hubs is also NP-hard.
In this dissertation, new mathematical models for USApHMCP with binary and
partial covering are proposed. The main advantage of the newly proposed models,
in respect to existing ones from the literature, is the fact that small modifications
of the new models enable their transformation to new models for
p
-hub maximal
covering problems with different allocation schemes. More precisely, new models
for UMApHMCP and UrApHMCP can be obtained from the newly proposed mod-
els for USApHMCP in both coverage cases. All proposed models for USApHMCP
and UMApHMCP are compared with the existing ones from the literature in the
terms of efficiency within the framework of exact CPLEX 12.6 solver. Several hub
data sets from the literature are used in numerical experiments when comparing
the formulations. The obtained experimental results indicate that new models for
UMApHMCP with both binary and partial coverage show the best performance in
terms of solutions’ quality and execution times. For UrApHMCP and both coverage
criteria, three mathematical models are proposed, and compared in terms of effi-
ciency using the exact CPLEX 12.6 solver. It turns out that the exact solver finds
optimal or feasible solutions only for small-size problem instances.
Having in mind the complexity of all three problems under consideration and
the results obtained by CPLEX 12.6 solver, the conclusion is that, in practice, exact
methods can not provide solutions for large problem dimensions. For this reason, it
was necessary to implement adequate heuristic or metaheuristic methods, in order
to obtain high-quality solutions in short execution times, even in the case of large
problem dimensions. Up to now, only simple but insufficiently effective heuris-
tic methods for solving USApHMCP and UMApHMCP with binary coverage have
been proposed in the literature, while the HMCP variants with partial coverage
have not been previosly solved by using metaheuristic methods. As UrApHMCP
with binary and partial coverage has not been previously considered in the litera-
ture, no solution methods suggested for this problem existed up to now. Inspired
by previous successful applications of variable neighborhood search method (VNS)
to other hub location problems from the literature, this metaheuristic approach is
applied to the considered HMCP problems. In this dissertation, several variants of
VNS metaheuristic are designed and implemented: General Variable Neighborhood
Search (GVNS) for USApHMCP, Basic Variable Neighborhood Search (BVNS) for
UMApHMCP and a variant of General Variable Neighborhood Search (GVNS-R)
for UrApHMCP. In the case of UrApHMCP, two additional metaheuristic meth-
ods are proposed: Greedy Randomized Adaptive Search Procedure with Variable
Neighborhood Descent (GRASP-VND) and Genetic Algorithm (GA). Constructive
components of all proposed metaheuristics are adapted to the characteristics of the
considered problems.
Experimental study was conducted on the existing hub data sets from the lit-
erature, which include instances with up to 1000 nodes in the network. The ob-
tained results show that the proposed metaheuristics for the considered problems
reach all known optimal solutions previously obtained by CPLEX 12.6 solver or
establish new best-known solutions in significantly shorter CPU time compared to
CPLEX 12.6. The proposed GVNS and BVNS metaheuristics quickly reach all
known optimal solutions on small-size problem instances when solving USApHMCP
and UMApHMCP, respectively. In the case of large-size problem instances, which
have not been previously used for testing purposes for these problems, the proposed
GVNS and BVNS return their best solutions in short execution times. The results
obtained by the proposed GVNS-R and GRASP-VND for UrApHMCP on large-size
problem instances indicate their effectiveness in both coverage cases. The proposed
GA method showed to be successful only for UrApHMCP in binary covering, on
instances up to 200 nodes.
The variants of hub maximal covering problems considered in this dissertation
are important from both theoretical and practical points of view. The new mathe-
matical models proposed in this dissertation for the considered variants of HMCP,
represent a scientific contribution to the theory of hub location problems, mathemat-
ical modeling and optimization. Designed and implemented metaheuristic methods
for solving the studied variants of HMCP are the scientific contribution to the field
of optimization methods for solving location problems, as well as the development
of software. The considered variants of HMCP have numerous applications in the
optimization of telecommunication and transport systems, air passenger and goods
transport, emergency services, postal and other delivery systems, so that the results
obtained in this doctoral dissertation can be applied in practice, partially or com-
pletely. |