Geoscience Reference
In-Depth Information
maximum distance between a node and its facility (among p C q facilities) is
minimized. Minieka ( 1980 ) introduced the conditional 1-center problem. Drezner
( 1989 ) showed that the conditional p-center problem can be solved by solving
O. log n/ p-center problems. Suppose that the nodes are ranked in non-increasing
order of their distances to their facilities (using the existing q facilities). Then there
exists a node s such that the optimal value of the conditional p-center problem is
equal to the maximum of the optimal value of the p-center problem solved for the
first s nodes and the distance of the s C 1st node to its facility using the existing q
facilities. The algorithm tries to find the best s using bisection.
Berman and Simchi-Levi ( 1990 ) solved the conditional p-center problem by
solving a p C 1 center problem. They add a dummy demand node and a dummy
possible location. The distance from a demand node to the dummy location is the
distance of that node to its facility considering the existing facilities. The distance
of the dummy demand node to the dummy location is zero and its distance to the
other possible locations is a very large number. As a result, an optimal solution to
the p C 1-center problem includes the dummy facility location and opens p other
facilities. Berman and Drezner ( 2008 ) improved this approach and showed that the
conditional p-center problem can be solved by solving a p-center problem where
the distance between a node and a potential facility is set to the minimum of this
distance and the distance between this node and the closest existing facility.
4.5.3
The Continuous
p
-Center Problem
The next variant is the continuous p-center problem. When demand points are
continuously distributed over the whole graph, a set X p of p points of the graph
minimizing the largest distance from a demand point to a closest point of X p is
called a continuous p-center.
In the single facility case, i.e., when p D 1, the problem can still be solved
by choosing a best solution among all the local continuous centers, i.e., solutions to
continuous center problem in which the location is restricted to an edge. On an edge,
the objective function is again piecewise linear with O. j E j / breakpoints. Based on
these facts, O. j E j 2 log . j E j / algorithms were proposed by Hansen et al. ( 1991 )and
Tam ir ( 1988 ).
On a tree, the absolute center coincides with the unweighted absolute center.
For the continuous p-center problem, Tamir ( 1987 ) identified a finite set of
rational numbers containing the optimal solution value. Hence, a continuous
p-center can be found by solving a finite number of continuous set covering
problems, i.e., problems in which one looks for the smallest set of facilities needed
to cover all points of the graph (vertices and interior points to edges) within a given
maximum distance.
Search WWH ::




Custom Search