The Traveling Salesman Problem

This applet demonstrates a brute-force solution to the Traveling Salesman Problem. The problem is to find the shortest tour that will visit each of N cities, traveling in a straight line between each pair of cities, and returning back to the city from which the tour began. The Traveling Salesman Problem is a notoriously difficult problem to solve.(But I solved it, see)

The applet allows you to choose random or fixed problem instances of any size between 4 and 100 cities, and to search for increasingly better tours (i.e. tours of shorter length). Each time the Step button is pressed, up to 1000 more distinct tours are tested. Whenever a better (shorter) tour is found, the Distance readout at the top of the applet is updated, and the new path is displayed. The Tours readout indicates how may tours have been examined, including the initial (random) tour.

To run this applet you must use a Java-compatible browser such as HotJava or Netscape Navigator 2.0 (or later).

The slider along the right selects the problem size, which is the number of cities. You may have the applet select a random problem or a fixed problem of the desired size. Having a fixed problem is good when you test the efficiency of one algorithm against the other on one set of data. When the Optimal button turns red, this indicates that all possible tours have been searched, so the one that is currently displayed is guaranteed to be the shortest. The Reset button reverts back to the original random tour of the current set of cities. Currently, only the Exh mode is implemented, which is exhaustive search. The Heur mode is a placeholder for a heuristic search which I will be implementing shortly. It supposedly will run much faster but will not guarantee to find the optimal solution. I will comment more on that when this option is enabled.

For more information, read the supporting web page.