The p-Median Problem - Location Science - page 21

We refer the reader to ReVelle et al. ( 2008 ) for a fairly recent annotated bibliography
of the p -median and related models.
The remainder of this chapter is organized as follows. Section 2.2 outlines several
key properties of the problem. Section 2.3 discusses optimal solution algorithms
for the problem on a tree. Section 2.4 formulates the p -median problem as an
optimization problem. Section 2.5 outlines algorithms for the problem on a general
network. Section 2.6 presents selected computational results. Section 2.7 outlines
two key multi-objective extensions of the p -median problem. Finally, conclusions
are briefly presented in Sect. 2.8 .

2.2 Model Properties

There are three key properties of the p -median problem that are important to know.
First, Kariv and Hakimi ( 1979 ) showed that the p -median problem is -hard on a

general graph. This is the bad news. The good news, as outlined below, is that there
are many effective algorithms and approaches to solving the p -median problem.
Second, Hakimi ( 1965 ) showed that at least one optimal solution to the p -median
problem consists of locating only on the nodes. To see that this is true, consider
a solution that entails locating a facility somewhere on an edge between nodes A
and B. Let D A be the total demand served by this facility that enters the edge via
node A, and let D B be the total demand served by the facility that enters via node B.
Clearly, if D A >D B we can move the facility to node A and reduce the objective
function. This contradicts the assumed optimality of the facility at an intermediate
location on the edge. Similar arguments hold if D B >D A in which case we move
the facility to node B. If D A D D B we can move the facility to either node without
adversely impacting the objective function value. Note that moving the facility to
one of the nodes may result in the reassignment of demands to or from the facility if
doing so will reduce the objective function. Such reassignments will only improve
the objective function. Also note that moving the facility to one of the nodes may
also result in some demands that were served by the facility, and that entered via the
other node, to now enter the facility directly without traversing the edge between A
and B. This would occur if traveling directly to the facility is shorter than traveling
via the edge between A and B. Finally, we note that the nodal optimality property
holds if the distance between a demand node and a candidate facility site is replaced
by any concave function of the distance.
Finally, the demand weighted total cost or distance (or the demand weighted
average cost or distance) decreases with the addition of each subsequent facility.
This is clearly true since, if there exists an optimal solution to the problem with
p facilities, then adding a p C 1 st facility at any of the candidate nodes that does
not have a facility will decrease the demand-weighted total cost or distance and
therefore will also decrease the objective function. Locating the p C 1 facilities
optimally is clearly as good or better than first locating p facilities optimally and
adding a subsequent facility to that solution.

NP