Geoscience Reference
In-Depth Information
locations for the facilities coincide with the locations of the demand nodes. In its
discrete version, the p-median problem can be formulated as follows:
Minimize
X
i2J
X
d
j
a
ij
x
ij
(8.1)
j2J
subject to
X
i2J
x
ij
D
1; j
2
J
(8.2)
x
ij
x
ii
; i
2
J; j
2
J
(8.3)
X
x
ii
D
p
(8.4)
i2J
x
ij
2f
0;1
g
; i
2
J; j
2
J:
(8.5)
In this formulation, a
ij
represents the distance or travel time between demand nodes
i and j (i;j
2
J)andd
j
is the demand or weight of node j (j
2
J); x
ij
is a binary
variable equal to 1 if node j
2
J is allocated to node i
2
J and 0 otherwise; x
ii
D
1
indicates that a facility is located at i. The goal is to minimize the total weighted
distance or travel time.
In a p-median problem, uncertainty can occur in the demands (or weights) or
in the distances (or travel times). Denote by ǝ the finite set of scenarios and by
!
2
ǝ one particular scenario (that fully determines the uncertain parameters).
Suppose that the location of the facilities is an
ex ante
decision and the allocation
of the customers to the operating facilities is an
ex post
decision. In order to capture
uncertainty, we need to consider binary location variables y
i
indicating whether a
facility is located at i
2
J, and scenario-indexed binary allocation variables x
ij
!
indicating whether demand node j
2
J is allocated to facility i
2
J in scenario
!
2
ǝ. The minmax p-median problem can be formulated as follows:
Minimize v
(8.6)
subject to
X
i2J
X
d
j!
a
ij
!
x
ij
!
v; !
2
ǝ
(8.7)
j2J
X
x
ij
!
D
1; j
2
J; !
2
ǝ
(8.8)
i2J
x
ij
!
y
i
; i
2
J; j
2
J; !
2
ǝ
(8.9)
X
y
i
D
p
(8.10)
i2J
x
ij
!
2f
0;1
g
; i
2
J; j
2
J; !
2
ǝ
(8.11)
y
i
2f
0;1
g
; i
2
J:
(8.12)
