Geoscience Reference
In-Depth Information
neighborhood, there is no guarantee that it will find the global optimum for the
problem.
The exchange algorithm, proposed by Teitz and Bart (
1968
), is another heuristic
improvement algorithm that tends to do better than the neighborhood search
algorithm. The algorithm attempts to improve the current solution by removing a
node that is in the solution and replacing it with a node that is not in the solution.
If an exchange of this sort can be found and improves the solution (i.e., reduces
the demand-weighted total distance), it is implemented. The algorithm terminates
when there is no such exchange that improves the solution. The pseudocode for one
variant of the exchange algorithm is shown below.
Exchange Algorithm Pseudocode
1.
Input:
X
/*
X
is a set of
p
facility locations
2.
For
i
2
X
do
3.
For
k
2
I
n
X
4.
;X
[f
k
gnf
i
g
/
then
5.
Set
X
X
[f
k
gnf
i
g
and stop
6.
End If
7.
End For
8.
End For
If
z
.
J
;X/>
z
.
J
Step 1 initializes the solution with any set of
p
facilities. In Step 2 we loop over
the sites in the current solution. In Step 3 we loop over candidate sites that are not
in the solution. In Step 4, we ask if removing one site from the current solution
and replacing it with a site not in the current solution will improve the objective
function. If so, we make that substitution and the algorithm stops.
There are numerous ways of implementing an exchange algorithm. The algo-
rithm might implement the
first
exchange that improves the solution, as shown in
the pseudocode above. Alternatively, the algorithm might find the first node in the
solution whose removal will result in an improvement to the solution and then find
the
best
node to insert into the solution in place of the removed facility. Finally, the
algorithm can find the best improving pair of nodes over all possible nodes to be
removed and inserted into the solution.
If either of the first two approaches are adopted—that is, if the exchange
algorithm does not find the best overall exchange possible—there are alternate ways
in which the algorithm can proceed. One option is to continue the search with the
next indexed node that is not in the solution, attempting to replace the node that was
just inserted into the solution with another node. Another option is to proceed to
the next node in the solution and attempt to find exchanges based on that node. A
third option is to reinitiate the search from the first node in the solution. The various
options for selecting an exchange to implement, as well as the different ways in
which the algorithm can proceed once an improving exchange has been identified,
result in numerous possible implementations of the exchange algorithm. Most of the
literature does not identify which implementation was employed.
