Traveling salesman problem




The goal is to help our traveling salesman find the shortest closed path that visits all the cities, assuming that the distance between cities is measured "as the crow flies". The problem can be solved (in principle only) by an exhaustive enumeration of all possible paths, but a far simpler heuristical approach is based on "simulated annealing" (a form of Monte Carlo sampling).

In this example, the cities are arranged at random in four clusters. The annealing process is governed by a "temperature" parameter: big values allow large global changes in the route, whereas small values tend to cause localized changes only. The temperature drops automatically as the process advances, but can be manually adjusted as well.

Available user controls are the start/stop button, a button for repeating the calculation using different random numbers (the end results should be fairly similar), a button to generate a new arrangement of the cities, a pair of buttons for controlling temperature, and sliders for choosing the number of annealing iterations between updates and the time delay between display changes.

(c)   D. Rapaport