|
|
 |
Optimize |
 |
-
Improve TSP |
| |
| |
The Traveling Salesman Problem
is to find a sequence of cities such that the length of the
distance traveled on the tour through the cities is minimized.
An example 10 city problem is shown below. The form shows 11
cities since the first and the last repeats city 1. The distance
matrix is randomly generated and represents the intercity distances
when the cities are placed randomly on a plane. Row 7 shows
the decision at each city that gives the next city to be visited.
Row 8 shows the corresponding sequence. This initial solution
visits the cities in numerical order. The tour length for this
solution is computed in cell D3 and is 301. The contents of
cells F2 and F3 are not relevant for this problem. |
| |
The add-in includes improvement
algorithms specifically adapted for the TSP. To improve this
initial solution we choose Search from the menu, click
the Current Solution button and click the Improve
checkbox. We enter 2 in the n_change field. The Change field
is not used for the TSP. We explain the Assume Linear Objective
box later. |
| |
| |
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.
Action |
Sequence |
Initial |
(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 115. Each pass requires 37 runs
(1 to evaluate the starting solution and 36 to evaluate each
pairwise switch). The example required three passes through
the 2-change procedure totaling 111 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 7. From city
7 the tour goes to city 9. The complete tour is shown on the
combinatorial form.
The dialog also allows the improvement process to start from
a greedy solution of the TSP. With this option the best tour
found by the program has a length of 107. The greedy solution
has a length of 107 and the 2-change procedure is unable to
improve it. The sorted list shows the greedy solution twice.
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 user can specify larger values for n_change, but the number
of runs will certainly grow. |
Improving Random Solutions
| |
Improvements may
also be applied to randomly generated sequences. In the
dialog below, we specify that 10 random sequences are
to be generated. Each sequence will be improved with the
3-opt procedure. |
| |
| |
The results obtained with the 10 random
sequences are shown below. The tour length of 105 is improved
over the greedy solution. We do not know whether this
is the optimum. Only exhaustive enumeration assures optimality
and for this problem that method would require almost
400,000 evaluations. |
|
|
| |
The Assume Linear Model
box is enabled for the TSP and the Tree models. When clicked,
the add-in evaluates the contribution to the tour length
of each allowed cell of the TSP distance matrix. This
is done at the beginning of the run. If one assumes that
the contribution of a cell does not depend on the other
cells used in the tour, this single evaluation can be
used throughout the search process. This reduces the number
of evaluations of the entire worksheet by a great deal.
Although the two cases shown here involving random search
are not directly comparable, the assumption of linearity
reduces the computation time from 27 seconds to 4 seconds.
This savings will be greater for larger problems. |
 |
| |
Although we have illustrated
the improvement algorithms using the TSP, they are appropriate
for any sequencing problem that can be evaluated using
Excel functions. The add-in provides the search algorithms,
but worksheet formulas evaluate the solutions. |
|
| |
|
|
