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.
(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> exitThis 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?))
gnuplot> plot "tour" with lThis will join up the dots, and give a graphical display. More specifically
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
10.2 5296 3 2 1 6 5 4 9 8 10 7might 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.
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-679Deadline
Submit solutions via email in the format above so that I can verify them.