To model a traveling salesman problem, choose
TSP from the Combinatorics menu. Our first
example has 6 cities. The distances between the cities are provided
by the arc length. In the dialog below we indicate that the
data is to be determined by the Euclidean measure with the 6
cities located randomly in a plane.
The initial worksheet is shown below. The solution is a tour
through the cities starting at city 1 and ending at city 7.
City 7 has the same location as city 1 and represents the completion
of the tour. The computer manipulates the green colored decision
variables in row 9 that indicate the next city in the tour.
Row 10 holds the tour and row 11 holds the lengths of the chosen
arcs. The sum of the lengths of the tour arcs is computed in
cell F5. This is the objective to be minimized. Cells H4 and
H5 hold the condition that a tour must visit all cities. The
objective function and constraint cells are all colored yellow
to indicate that they are not to be changed. This add-in only
solves the traditional minimum distance TSP.
The random locations of the cities are shown to the right of
the distance matrix. The cells of the matrix hold formulas that
compute the distances between the locations. The *** strings
indicate disallowed transitions. The initial solution visits
the cities in numerical order. |