The Travelling Spider Problem

The Travelling Spider Problem

In this directory we present naive dynamic prpgramming algorithms for the famous TSP problem. The version of the problem considered here is as follows:

A travelling spider is required to visit n web sites, commencing and terminating the tour at his/her home web site. Each of the web sites must be visited exactly once. The objective is to determine a tour that minimizes the travel time, assuming that the travel times between sites are known.

For simplicity let 0 (numeric zero) denote the home web site of the travelling spider and let {1,2,3,...,n} represent the set of n sites to be visited. Also, let t(i,j) denote the travel time from site i to site j.

Then the problem under consideration can be stated formally as follows:

z*:= min { t(0,x1) +t(x1,x2) + ... + t(xn-1,xn) + t(xn,0)}
s.t. :
{x1, ...,xn }= {1,2,...,n}

We interpret xj as the j-th site on the tour (excluding the home site).

Now, since a tour (x1, ..., xn) is feasible if and only if it is a permutation of {1,2,...,n}, it follows that threre are exactly n! feasible tours. For the benefit of those of you who are not familiar with the Curse of Dimensionality we provide here a facility to calculate the value of n! for selected values of n. Convince yourself that n! is indeed subjected to the Curse of Dimensionality!

The Factorial Machine

n =
n! =
years =

Observation: For large values of n you'll need to practice your skills in reading numbers expressed in the e-?? format.

Oh, yeh! The "Years" entry tells you how many years it will take to evaluate the duration of all the feasible routes using a computer capable of evaluating 1000000 (one million) routes per second (fast machine!).

The dynamic programming algorithms to be discussed here are naive in two senses: first, they can handle only very small problems thus are completely useless as practical tools for problems of substantial size. Second, the implementation of the algorithm was not design with speed in mind. In short, do not expect a fast code for large scale TSP problems. On the other hand, note that they are guarantted to generate an optimal solution upon termination.

Two algorithms are considered: