|
Zusammenfassung:
|
This dissertation examines the p-next center problem (PNCP) and three of its
variants that have not previously been addressed in the literature. All the problems consi-
dered involve determining locations for establishing service centers, focusing on the user in
the most unfavorable position. In practice, this may be the user who is farthest from their
assigned health clinic, or the customer farthest from the local market. The objective is to
ensure that these users travel the shortest possible distance to a service center.
Since these are NP-hard problems, standard solvers such as CPLEX are unable to provide
optimal, or often even feasible, solutions for larger instances.
The p-next center problem reflects the realistic possibility that one or more centers may
suddenly fail. In such cases, users assigned to a closed center are redirected to the (nearest)
backup center, and the goal is to determine the locations for centers so as to minimize the
maximum of all total distances traveled by users. In this dissertation, a skewed variable
neighborhood search method (SVNS) is proposed for solving the p-next center problem,
which incorporates a fast interchange heuristic within the local search phase. The method
is tested on the well-known OR-LIB set of instances containing up to 900 nodes, and the
results are compared with the best results from the literature.
As an extension of the previous problem, the concept of facilitated communication be-
tween centers is considered, and the p-next center problem with a discount factor (ωPNCP)
is defined to incorporate this idea. A mathematical formulation of the problem is provided
and solved using the CPLEX solver. A basic variable neighborhood search (BVNS) method
is proposed for solving the problem, and the potential benefits achievable through enhanced
communication between centers are analyzed on a set of instances from the literature that
include up to 900 nodes.
To further adapt the p-next center problem to practical needs, the conditional p-next
center problem (CPNCP) is defined. This problem is applicable to the expansion of existing
business networks while retaining existing centers where there is a possibility of sudden center
failures. A mathematical model is proposed, instances with up to 900 nodes are generated,
and the problem instances are solved using the CPLEX solver. A variable neighborhood
search method is proposed for solving this problem. Two approaches to business network
expansion are analyzed, along with potential long-term savings that can be achieved by
their application.
The maximal covering p-next center problem (MCPNCP) with binary and partial cove-
rage is defined. The objective is to maximize the total demand of users that are covered,
that is, users whose distance to their backup center does not exceed a given radius. Two
mathematical models are proposed. Instance with up to 400 nodes are generated and the
proposed models are compared using the CPLEX solver. A skewed variable neighborhood
search method is proposed for solving the problem, and the results are compared with those
obtained by the CPLEX solver. |