The cost of the tour is
where the function c(i, j) specifies
the cost of traveling from city i to city j. When c(i, j)
represents the distance between i and j,
the objective of the problem is simply to minimize the total
distance traveled. For those cases where c(i, j)
= c(j, i), the TSP is said to be
symmetric; otherwise it is asymmetric.
With Data Form option 1, a table is constructed to
hold the (x, y) coordinates of the specified
number of cities. The value of p specified in cell
W10 is the norm for the distance measure. Distances are computed
when needed in the decision objective cell of the model using
the formula below.
With p =
2 this is the Euclidean distance.
The dynamic programming model is similar to
the sequencing model in that the state identifies the set of
cities that have been visited at any point in the tour. To
compute the cost of traveling to the next city, though, we
need to know the last city visited. An additional state
variable is defined for this purpose. The figure below shows
the state and decision definitions for the TSP model.