Geoscience Reference
In-Depth Information
Fig. 2.1
Example tree
150
100
B
A
5
6
125
C
D
175
3
4
7
F
E
200
250
In addition, we define the following additional inputs:
d
j
demand of customer
j
c
ij
unit cost of satisfying customer
j
from facility
i
.
Now suppose that no node has half or more of the total demand. We call any
node that is connected to only one other node in the tree, a tip node. We let
d
j
be the
.WealsodefineD
total
D
X
j2
J
modified demand at node j
2
J
d
j
. The algorithm
is as follows.
Step 1:
Let d
j
D
d
j
for all nodes j
2
J
.
Step 2:
Select any tip node. Call the tip node, node A and the node to which it is
connected node B. Remove node A and edge (A, B). Add the modified demand at
node A to the modified demand at node B. If the new modified demand at node B
equals or exceeds
D
total
/2, stop; node B is the 1-median of the tree. Otherwise repeat
step 2.
This is clearly an
O
(
n
) algorithm since Step 2 can be performed in constant time
and each node is examined at most once in Step 2. The complexity of Step 1 is also
clearly
O
(
n
).
We can illustrate this algorithm with the tree shown in Fig.
2.1
. The demand
associated with each node is shown in a box beside the node and the edge distances
are shown beside the edges. Nodes A, B, E and F are tip nodes. The total demand
in the tree is
D
total
D
1,000. Clearly, no node has half or more of the total demand.
We select node E as the first tip node to eliminate (since it has the largest demand
of any tip node). We remove node E and link (C, E) from the tree and add 250 (the
demand at node E) to the demand at node C. The modified demand at node C is now
375, which does not exceed half of the total demand. Next we can process node F,
removing it as well as arc (D, F) and adding its demand to that of node D, resulting
in a modified demand at node D of 375. Next we process node B, removing it as
well as arc (B, D) and adding its demand to that of node D, resulting in a modified
demand at node D of 525, which exceeds half of the total demand in the tree. Node
D is therefore the 1-median of the tree.
