Geoscience Reference
In-Depth Information
Sussmann ( 2000 ). If multiple centers can be located at the same location, then the
guarantee is further improved to 5.
Jaeger and Goldberg ( 1994 ) proposed a polynomial time algorithm for the
capacitated p-center problem when the graph is a tree, capacities are equal, and
multiple facilities can be located at the same location. In this work, the demand of a
node can be split among different facilities.
Ozsoy and Pinar ( 2006 ) proposed an exact algorithm to solve the capacitated
p-center problem. The idea is to see if the all nodes can be assigned within a given
distance and update lower and upper bounds on the radius using this information.
In the subproblem solved to see whether it is possible to assign all nodes within a
given distance, the objective is to minimize the number of facilities required.
In addition to the subproblem solved by Ozsoy and Pinar ( 2006 ) to obtain bounds
on the optimal radius, Albareda-Sambola et al. ( 2010 ) proposed a second approach
where they solved the problem of maximizing the demand covered within a given
distance using at most p facilities. They used bounds from the Lagrangian relaxation
of the two subproblems to eliminate some radius values and concluded that the first
approach for finding the minimum number of required facilities is a better approach.
Based on this conclusion, they proposed an exact algorithm using binary search over
possible values of the optimal radius.
A very large-scale neighborhood heuristic was developed by Scapparra et al.
( 2004 ). Two types of exchanges were considered. In a cyclic exchange, one takes
a sequence of nodes that are served by different facilities and replaces the facility
of each node with the facility of the next node in the sequence (the facility of the
last node in the sequence becomes the facility of the first node). In a path exchange,
we again take a sequence of nodes served by different facilities and replace the
facility of each node with the facility of the next node. The facility of the last node
is replaced by a facility different from the facilities of the nodes in the sequence. A
relocation step that moves the facilities to better locations with respect to the set of
nodes they are serving is also added to the algorithm.
Three data sets were used in the last three papers mentioned. The first data set
contains 20 instances of the capacitated p-median problem from the OR-Library
(Beasley 1990 ), with 50 and 100 nodes. The second data set is from Lorena and
Senne ( 2004 ) and is also for the capacitated p-median problem. Here there are six
instances with the number of nodes ranging from 100 to 402. Finally, Scapparra
et al. ( 2004 ) provided a data set with 8 instances containing 100 and 150 nodes.
Additional instances of the p-median problem were used by Albareda-Sambola
et al. ( 2010 ). These authors also compared their approach with the one of Ozsoy
and Pinar ( 2006 ).
4.5.2
The Conditional
p
-Center Problem
The second variant is the conditional p-center problem. In this variant, there
are q existing facilities and additional p facilities are to be located so that the
Search WWH ::




Custom Search