Travelling Salesman Problem (tsp) challenge

The Problem
In the tsp we have a number of cities, where each city has an x and y location. The problem is then to visit each city once only, returning to the starting position, and to do so with minimal travel (ie. a minimum cost tour).

There are many practical instances of the tsp. For example, if we have a single machine (a lathe, grinding machine, whatever) and a number of jobs of specific product types that require that machine, and there is a setup cost when we change from one job type to another, then we must find a permutation of the jobs that minimises the makespan for the jobs. In this case the jobs are the cities, and the setup cost is the distance between cities. Another instance is laying an electical circuit between a number of points such that the circuit delay is minimised. And of course we have transportation problems (of increasing importance in the present and future world) where by minimising travel we save scarce resources, and minimise enviroinmental damage (you might care to have a look at the GreenTrip page). We may see this problem in a micro-scale when we are routing an autonomous guided vehicle (AGV) within some environment, or in a macro-scale when routing deliveries on a world wide scale (by sea, air, land).

The tsp is a well studied problem and is of increasing economic importance to us all.

Complexity
If we have an n city tsp then a "tour" is a permutation of the n cities. In order to be sure that we find the best tour we might, in the worst case, have to explore all possible tours (ie. all possible permutations of the n cities). There are n! permutations (look at the tables in Notes 6 for an appreciation of this).

Randomly Generated tsp's /home/s7/pat/scheme/tsp/
This directory contains a number of randomly generated tsp's of varying size (number of cities). Typically there are 5 tsp's of each size, so 10.1 is the 1st tsp of 10 cities, 10.5 is the 5th tsp of 10 cities, and more generally n.i is the ith tsp with n cities.

Reading Randomly Generated tsp's
File /home/s7/pat/scheme/tsp/tsp.scm contains a number of interesting functions. For example there is a function to load in a problem, and a function to create the cost matrix. Read them and use them to get going!

Displaying tsp's
The randomly generated tsp's can be viewed (graphically) via gnuplot. Instructions are as follows:

  (1) type gnuplot
  (2) in gnuplot
     gnuplot> cd "/home/s7/pat/scheme/tsp"
     gnuplot> load "tsp.gnu"
     gnuplot> plot "10.3"
     gnuplot> plot "100.2"
     gnuplot>!ls
     gnuplot> plot "1000.3"
     gnuplot> exit

This will give a "scatter" for the third 10 city tsp, second 100 city tsp, list the files in the directory /home/s7/pat/scheme/tsp, plot the third 1000 city tsp, and then exit out of gnuplot (and for more info on gnuplot see systems support, or make a posting to a helpfull newsgroup (cs.unix?))

Manhattan Distance
It is assumed that cities exist within a Manhattan landscape. This is described in tsp.scm, and there is a function that computes the Manhattan distance between two points (secretly disguised as a function named manhattan-distance). We will use Manhattan distance because it is faster to compute than Eucledian distance.

What you are required to do
Implement one or more techniques to find the minimum cost tour. Display results using gnuplot ie. output a tour as a file of x y pairs (ie. 2 columns) and then plot this tour as:

     gnuplot> plot "tour" with l

This will join up the dots, and give a graphical display. More specifically

Find a low cost soluton for 100.4

Email me your solutions (to cs219) as files, and the cost (distance travelled) in your solutions. A solution will be a list of numbers, one number per line, where the number corresponds to the city. The first line in the file should give the problem number and the cost of the solution. For example

might be a solution to tsp 10.2 , with a cost of 5296 (distance travelled), where the tour starts at city 3, goes to city 2, then city 1, ..., city 8, then city 10, city 7, returns to starting city 3.

Possible Ways to Go
There are a number of ways to address this problem. Assume that we have read a tsp into a list. A solution to the tsp (a tour) is then a permutation of that list. The following approaches might be explored:

1. Generate all possible permutations of the list of cities, and
deliver as a solution the permutation that corresponds to the minimum
cost tour. This is guaranteed to find the optimal solution.
Unfortunately, it is hopelessly inefficient for large problems.

2. Modifying 1 above such that we cease to explore permutations that
cannot possibly be better than the best found so far. That is, incorporate
some lower bound during search. Again, this is guaranteed to find the optimal solution.

3. At random, generate permutations (see for example function
randomise in misc.scm), and take the best found after a given
amount of computational effort.

4. Use a heuristic/greedy algorithm. For example, always moving to
the nearest neighbouring city.

5. Combining 3 and 4, randomly restarting 4 from differing initial points

6. Something else, such as the 2-OPT heuristic or SA (simulated annealing).
In the 2-OPT heuristic we select a subtour and reverse it. This can
be done by selecting two positions in the tour, p1 and p2, and
reversing the list of elements from p1 to p2. It is worth looking at
this graphically to see just what it does. This heuristic can be applied
iteratively (and randomly) accepting tour improvements. As an aside,
2-OPT is similar to the inversion operator in an order-based chromosome
used by a genetic algorithm (GA). The heuristic may be incorporated
into an SA. That is, we might accept non-improving moves with a given
probability, and this probability varies over time. For more info
on SA see

S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi "Optimization by Simulated
Annealing" SCIENCE 220, Number 4598, May 13th 1983, pp 671-679

Deadline
Deadline is Friday the 14th of August.

Submit solutions via email in the format above so that I can verify them.

Good luck!