This applet finds the shortest roundtrip by local descent from random positions. The algorithm starts at some a round trip randomly chosen from all possible roundtrips. For this path, the algorithm searches through all paths in the neighborhood of this path to find a shorter one. Here, the neighborhood of a path is defined by some simple changes, switching elements of the path. It continues to improve the path until no more improvement is possible. The local search algorithm may get trapped in a local minimum, which is not the global minimum. So the above applet tries more than one random start.

Try pressing "Random" to get a random start configuration of points. You may set the number of points too (500 points take 10 seconds on my computer). Also try the square grid of points. In this case, the solution is obvious. It is found in most cases. The number of iterations is the number of random round trips the algorithm tries.

Here is a work by Matteo Catena, which uses a version of this code.