Geoscience Reference
In-Depth Information
The myopic algorithm can readily paint itself into a corner. There is no guarantee
of optimality for the myopic algorithm. As illustrated below in the computational
results, the algorithm can perform quite poorly. That said, it is clear that it is optimal
if we are locating only a single facility.
Exploiting the optimality of the myopic algorithm for the 1-median problem,
Maranzana (
1964
) proposed a neighborhood improvement algorithm. Starting with
any feasible solution to the
p
-median problem, the algorithm assigns each demand
node to its nearest facility. Ties are broken arbitrarily. The set of nodes assigned to
a facility constitutes the neighborhood of that facility. Within each neighborhood,
the algorithm examines each candidate node and selects the one that minimizes
the demand-weighted total distance among all nodes in the neighborhood. In other
words, within each neighborhood, the algorithm solves a 1-median problem. If
no facility locations have changed, the algorithm stops; otherwise, if any facility
locations have changed as a result of solving the 1-median problem, the algorithm
re-assigns all demand nodes to the nearest open facility. If no assignments have
changed, the algorithm stops; otherwise, the algorithm continues by solving the 1-
median problem in each neighborhood. This process of determining neighborhoods
and solving 1-median problems within each neighborhood continues until no further
improvement is possible. The pseudocode below outlines the neighborhood search
algorithm.
Neighborhood Search Algorithm Pseudocode
1.
Input:
X
/*
X
is a set of
p
facility locations
2.
Set:
N
i
;
8
i
2
/*
N
i
is the set of demand nodes for which
/* candidate site
i
is the closest open facility
3.
For
j
2
I
J
do
4.
Set
i
argmin
i2
I
˚
c
ij
5.
Set
N
i
N
i
[f
j
g
6.
End For
7.
Set
X
new
/*
X
new
is the set of new facility locations
do
9.
If
j
N
i
j
>0
then
10.
Find
k
D
argmin
k2N
i
z
.N
i
;
f
k
g
/
11.
Set
X
new
X
new
[f
k
g
12.
End If
13.
End For
14.
If
X
¤
X
new
8.
For
i
2
I
then set
X
X
new
andgotoStep2;elsestop
Step 1 initializes the solution with any set of
p
facilities. Steps 2 through
6 initialize and then set the neighborhoods. Step 7 initializes a new candidate
set of facility locations. Steps 8 through 13 find the new candidate locations. In
particular, in Step 10, the algorithm finds the 1-median within each neighborhood
and adds that vertex to the emerging new solution in Step 11. The algorithm, as
written, assumes that the sets of demand locations and candidate sites are the same.
While the neighborhood search algorithm finds the optimal location within each
