COSC 461/561
Travelling Salesman Problem


OK folks. You have the data set. Here's what to do: solve the TSP with the following algorithms. For each algorithm, report the total number of tours tested, as well as the run time of your program. Also report the shortest tour given and graph it (please!!)


1) Genetic Algorithm. Choose a population size of 30 and initially, seed it randomly. Have the algorithm execute for 1,000,000 times and report the shortest tour every 100,000 steps. Repeat this for a mutation rate of 0.0  , 0.00001 , 0.001  , and 0.1  .  You should describe in a commnet at the start of your program how you represent a tour and implement crossover.


2) Uniform Cost. I would try this with 20 cities, then 30, 40, etc (see 3 below)


3) Our "in class" heuristic. That is, only consider tours that don't cross each other. Implement data structure with uniform cost (branch and bound) as above. I would suggest limiting this to the first 20 cities in the data file; if that runs in a reasonbale time, try 30, 40, etc.


4) Simulated Annealing. Be sure to include your cooling schedule in a commnet at the start of your program.


5) Greedy algorithm: start at a city, goes to the next closest unvisited city, etc.

You should have a cover sheet with the results of all methods in  table (calculated length and CPU time).

Due Dates:

Let's have 2) , 3) , and 5) due by Monday October 28
Let's have 1) and 4) due by Monday December 2 . Make sure to include results from October 20 in your handin.

What to include in the handin:

1) What did you learn ? Please be explicit and specific!

2) Include actual graphs of tours! For some algorithms (like simulated annealing) it is VERY instructive to draw the minial tour in real time (that is, as the algorithm is running)

3) Include tables where you compare the algorithms

PLEASE NOTE: for algorithms 2) and 3) you may not be able to do "large" instances of the algorithm. Instead, you might try tours with N=5,6,7,8,....... cities until your program "explodes". Report the time, number of nodes visited , actual tout and tout length until
the program explodes. Better grades for larger value of N reported.