Geoscience Reference
In-Depth Information
Note that we do not require the assignment variables to be binary variables. If
the unit cost from a demand node to the nearest open facility is strictly less than
the unit cost between that node and any other open facility, then the corresponding
assignment variables for that demand node will naturally be binary. That is, all of
the demand at that node will be assigned to the nearest open facility. If the unit
costs between a demand node and two or more open facilities are the same, and the
unit costs are less than the unit costs between the demand node and any other open
facility, the assignment variables may indicate that the demand is to be split between
the set of nearest facilities. We can always round all but one of these assignment
variables down to 0 and round the last one up to 1 if we require all-or-nothing
demand assignments or single sourcing.
2.5
Solution Heuristics for the
p
-Median Model on a General
Network
In this section, we outline a number of heuristic algorithms for solving the
p
-median
problem on a general network. We conclude the section by structuring a Lagrangian
relaxation algorithm (Fisher
1981
,
1985
).
2.5.1
Basic Construction and Improvement Algorithms
The simplest algorithm is the myopic or greedy adding algorithm. In this algorithm,
all candidate facility sites are examined and the one whose addition to the current
solution reduces the demand-weighted total distance the most is added to the
incumbent solution. The process continues until the solution includes
p
facilities.
The following is pseudocode for the myopic algorithm. In this and all subsequent
pseudocodes, we define
z
.
;X/
D
X
j2
J
d
j
min
m2X
˚
c
mj
; where
X
is the current
set of candidate facility sites. Note that the function depends on both the set of
demand nodes to be considered and the candidate locations to be used.
J
Myopic Algorithm Pseudocode
1.
Set
X
./*
X
is the set of locations to be used
2.
Find
i
D
argmin
i2
I
∅
f
z
.
J
;X
[f
i
g
/
g
.
3.
Set
X
X
[f
i
g
.
4.
If
j
X
j
<p,gotoStep2;elsestop.
Step 1 initializes the set of locations to the empty set. Step 2 finds the best node
to add to the emerging solution. Step 3 adds that site to the solution. Step 4 asks if
less than
p
facilities have been added to the emerging solution. If so, the algorithm
continues with Step 2; if not, the algorithm stops.
