Traveling salesman problem (TSP) using Simulated Annealing

Author: Frits Beukers

Before starting choose at least three cities. This can be done by clicking in the black panel. Or by entering a value for #cities and then press the zap or grid button.

This applet attempts to solve the traveling salesman problem by simulated annealing. In the black window one can select a set of cities in the following manner. Click in it with the mouse. A small dot depicting a city will appear. Repeat until you think you have enough cities. Note that the city counter has increased while doing so. Another method is to set the city counter with a number and then press the button `zap' or `grid'. If desired one can add a few more cities with the mouse. The number of cities should be below 100, otherwise the program becomes very slooooow...
When you are happy with the arrangement push `start'. A path will appear which is usually far from shortest. However, it will gradually improve. If so desired one can stop the process to change the temperature. Unfortunately the program's reaction to the stop button is often slow, especially with more than 50 cities. So be patient. A good starting temperature is T about 10 or 20. The value T=0 forces a greedy behaviour of the system, in which it is easy to get stuck in local minima. When T>50 you really cook the system to get only randomish paths.
To leave the process altogether push `stop' and then `reset'. The city counter is then set to zero and you can start all over again.

This applet is only an attempt to learn a little about simulated annealing. Anyone interested in REAL SOFTWARE for solving TSP and some history around the problem should definitely look at William Cook's TSP-site,/a>.


Back to my Homepage.