To solve the problem we choose
*Search *from the *Optimize* menu. We have chosen
to exhaustive enumerate all solutions.
On pressing OK, the add-in computes the number
of solutions that will be enumerated and presents the option
whether to continue. The add-in generates only valid tours.
For a problem not much larger than this one, the
number of solutions becomes exorbitant and one should choose
not to continue. For example, the ten city problem has 362,880
tours. Although evaluating this number of solutions is not impossible,
the serious user should look elsewhere for more efficient methods.
The add-in will not begin problems with more than 1,000,000
solutions.
During the solution process, the add-in generates
and evaluates all valid tours. The best 19 solutions are placed
to the right of the data. The optimum solution is evaluated
twice and is shown at the top of this sorted list. The solution
shows the city that follows each city in the sequence. Thus
x1 = 7 means that city 7 follows city 1. The remainder of the
tour is derived from the solution.
Optimum Tour = (1, 7, 4, 6, 5, 3, 2, 8, 1)
The second solution has the same length (99).
In a symmetric problem there will always be at least two optimum
solutions. Based on the second solution the alternative optimum
is
Optimum Tour = (1, 2, 3, 5, 6, 4, 7, 8 ,1)
The tours follow the same sequence but in opposite
directions. |