Geoscience Reference
In-Depth Information
4.5.4
The
p
-Center Problem with Uncertain Parameters
Finally, we consider the variants with uncertain parameters. Averbakh and Berman
(
1997
) studied the minmax regret version of the problem where the node weights
are uncertain within given intervals. They showed that the robust version of the
problem can be reduced to the resolution of n
C
1 deterministic problems. Averbakh
(
1997
) showed that the robust 1-center problem is strongly NP-hard on general
networks when there is uncertainty in edge lengths. Averbakh and Berman (
2000
)
developed polynomial time algorithms for the robust weighted 1-center problem
with uncertainty in both node weights and edge lengths on a tree network.
4.6
Conclusions
We conclude this chapter with some future research directions. The majority of the
solution methods proposed for the p-center problem are based on either the set
covering or the dominating set problems. Well known optimization methods such
as the cutting plane, branch-and-cut, Benders decomposition, or dynamic program-
ming are rarely used. Recently, Calik (
2013
) provided a Benders decomposition
method to solve the vertex restricted p-center problem and developed a branch-
and-cut method for the capacitated p-center problem with multiple allocation. The
experimental study conducted by Calik (
2013
) revealed that the utilization of a
branch-and-cut method enables obtaining optimal solutions of large instances in
small CPU time. The multiple allocation variant, which was previously studied by
Jaeger and Goldberg (
1994
) on trees, is also an open research area for the capacitated
p-center problem.
Although there are many studies for the p-center problem on trees, the capac-
itated version is not extensively investigated. The only study on this problem
considers facilities with identical capacities and allows multi centers and multiple
allocation. Hence investigating the capacitated p-center problem on tree networks
with non-identical capacities, without multi centers and/or with single allocation
might be a worthwhile undertaking.
Another variant of the p-center problem that has recently attracted the attention
of the researchers is the fault tolerant p-center problem. This is a generalization of
the p-center problem in which each customer is assigned to Ǜ different facilities.
The idea is to make back-up services available in case of a failure of some
facilities. The fault tolerance can also be taken into account for the capacitated
p-center problem. Among the existing studies for the fault tolerant p-center and
capacitated p-center problems, Krumke (
1995
), Khuller et al. (
2000
), and Chechik
and Peleg (
2012
) focus on approximation algorithms and a recent study by Chen
andChen(
2013
) presents two exact algorithms. Therefore, developing different
exact approaches and meta-heuristic algorithms for this problem might appeal to
the researchers.
