Geoscience Reference
In-Depth Information
Tabl e 2. 1
Median results for top 100 counties in US
Demand weighted
average distance
p
Change
Sites
1
969.45
St. Louis, MO
2
450.65
518.80
San Bernardino, CA; Allegheny,
PA
3
320.15
130.50
Los Angeles, CA; Shelby, TN;
Hudson, NJ
4
257.23
62.92
Los Angeles, CA; Tarrant, TX;
New York, NY; Jefferson, KY
5
190.22
67.01
Los Angeles, CA; Cook, IL;
Dallas, TX; New York, NY;
Orange, FL
We would also expect that the marginal improvement in the demand weighted
total (or average) cost or distance would decrease monotonically as we add facilities.
This is frequently the case, but not always. As an example of a situation in which
this is not so, consider the
p
-median problem with the 100 largest counties in the
contiguous United States based on the 2010 census. While these counties represent
only 3.2 % of the 3,109 counties in the contiguous United States, they account for
42.2 % of the total population. Using great circle distances and population as a
proxy for demand, we obtain the results shown in Table
2.1
. The demand weighted
average distance decreases with the number of facilities as shown in the second
column. However, the
change
in the demand weighted average distance increases
from about 63 miles to 67 miles as we increase from four to five facilities.
2.3
The
p
-Median Problem on a Tree
NP
While the
p
-median problem is
-hard on a general graph, the problem can be
solved in polynomial time on a tree. We illustrate this with a linear time algorithm
for finding the 1-median on a tree, which was proposed by Goldman (
1971
). This
algorithm also helps explain why the problem is called the “median” problem. If
any node of the tree has half or more of the total demand of all nodes on the tree,
then it is clearly optimal to locate at that node. Moving away from that node will
move the facility further from half or more of the demand and closer to less than
half of the demand, thereby increasing the objective function value.
To outline this algorithm, we define the following sets:
I
D
f
1;:::;i;:::;m
g
the set of candidate locations
J
Df
1;:::;j;:::;n
g
the set of demand nodes:
