Methods - Operations Research Models and Methods

Methods

Dynamic Programming

Teach DP

TSP

>	Teach Dynamic Programming Add-in
	-Traveling Salesman Problem

For the TSP a salesman must visit n cities starting and ending at his home base. The objective is to minimize some measure of travel cost subject to the restriction that each city be visited once and only once. A feasible solution is called a tour. We arbitrarily identify city 1 as the home base. Like the sequencing problem, a solution is described by a vector

which implies that the tour starts at city 1, goes through the sequence identified by the solution vector. To complete the tour, the salesman must travel from the last city back to city 1.

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.

The solution for the TSP determined by backward recursion on the state space is shown below.

The optimization statistics shows that the eight city problem has 449 states and the solution was obtained in about one minute. The number of states exponential increases with the number of cities. Unless, the state space is severely limited by precedence order of city visits or other logical conditions, the DP approach will fail for larger problems.

The figure below shows the solution plotted on a map. This figure was not generated by the add-in.

For a given size problem, the TSP has more states than the sequencing problem. The curse of dimensionality makes this approach impractical for all but the smallest problems.