Geoscience Reference
In-Depth Information
Note that in computing the location of the 1-median we do not need to use the
distances. In fact, node D would be the 1-median of the tree for any arc distances for
the tree. To compute the objective function value, we clearly do need the distances.
The objective function value for the 1-median located at node D in Fig.
2.1
is 5,375.
Kariv and Hakimi (
1979
)presentan
O
(
n
2
p
2
) algorithm for the
p
-median problem
on a tree. Tamir (
1996
) improved the computation time and presented an
O
(
pn
2
)
algorithm for the problem of locating
p
facilities on a tree.
2.4
Model Formulation
In this section, we formulate the
p
-median problem. In addition to the notation
defined above, we define the following additional input:
p
the number of facilities to locate.
Finally, we define the following decision variables:
y
i
D
1 if a facility is located at candidate site i
0
otherwise
x
ij
the fraction of the demand of customer
j
that is supplied from facility
i
.
With this notation, we can formulate the
p
-median problem as follows:
minimize
X
i2
I
X
j2
J
d
j
c
ij
x
ij
(2.1)
subject to
X
i2
I
x
ij
D
1
8
j
2
J
(2.2)
X
i2
I
y
i
D
p
(2.3)
x
ij
y
i
0
8
i
2
I
I
j
2
J
(2.4)
y
i
2f
0;1
g 8
i
2
I
(2.5)
x
ij
0
8
i
2
I
I
j
2
J
:
(2.6)
The objective function (
2.1
) minimizes the demand-weighted total cost. Con-
straints (
2.2
) mean that all of the demand at demand site
j
must be satisfied.
Constraints (
2.3
) require exactly
p
facilities to be located. Constraints (
2.4
) state that
demand nodes can only be assigned to open facilities. Constraints (
2.5
) stipulate that
the location variables must be integer and binary. Finally, constraints (
2.6
) state that
the assignment variables must be non-negative.
