The 2-change heuristic operates
on the sequence. City 1 is fixed. Each pair of cities, not involving
1 or 11, is considered in turn and the elements of the sequence
vector for these two cities are switched. For the example, the
first three sequences considered are shown in the table.
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
Switch 2, 3
(1, 3, 2, 4, 5, 6, 7, 8, 9, 10, 11)
Switch 2, 4
(1, 4, 3, 2, 5, 6, 7, 8, 9, 10, 11)
Switch 2, 5
(1, 5, 3, 4, 2, 6, 7, 8, 9, 10, 11)
Considering the nine cities that may be switched, there are
36 possible switches. For each case, the decisions leading to
the sequence are placed in the decision vector on the worksheet
and the worksheet formulas compute the tour length. If an improving
switch is observed the sequence is changed and the remainder
of the switch operations are performed on the new sequence.
The 2-change procedure is repeated until a pass through the
possible switches is completed with no improvement.
The table below shows the result of the 2-change procedure
for the example. Row 3 shows the run statistics. The best
solution observed has a tour length of 105. Each pass requires
37 runs (1 to evaluate the starting solution and 36 to evaluate
each pairwise switch). The example required five passes through
the 2-change procedure totaling 185 runs. The 2 runs indicated
in the cell labeled Enum. counts the first and last
solutions. The program estimates the number of runs required
for the improvement assuming that three passes will be necessary.
The estimate may be in error because the process will finish
in a single pass if there are no improvements to be made
or the process may take several passes if there are a number
of improving switches.
The individual lines of the table
show the decisions defining the tour, not the tour itself.
The optimum tour starts at city 1 and travels to city 3. From
city 3 the tour goes to city 7. The complete tour is shown
as the sequence in row 8.
The dialog also allows the improvement process to start from
a greedy solution of the TSP. The greedy solution has a length
of 107. The improvement process finds a tour of 105 with the
sequence shown below. It is a different tour than
the one above.
The 3-change procedure selects 3 elements in the sequence
and evaluates all permutations of the three elements. The
program evaluates only permutations that are different from
the incumbent solution in all three elements. This reduces
the number of duplicate sequences evaluated. When the dialog
specifies the 3-change procedure, the add-in first performs
the 2-change procedure until no improvement is observed and
then performs the 3-change procedure. The 3-change heuristic
applied to the tour just above found no improvement.
The user can specify larger values for n_change, but the number
of runs will certainly grow.