Traveling Salesman Problem

Explore the classic problem of the Traveling Salesman. The salesman has to stop at n cities, and he wishes to take a tour so that he visits each city exactly once and finishes at the city that he started from. This applet is a demostration of one possible algorithm he can use to minimize the total cost of the trip.

To find such a tour, the algorithm starts with a random tour connecting all n cities. Upon each iteration, the algorithm tries to improve on the tour. While not guaranteed to be optimal, the final solution will be much better than the initial tour and will often be a reasonable tour for the salesman to use. The reason the algorithm is not optimal is because finding the shortest tour is a NP-complete problem, with all known algorithms having exponential growth as n increases.

Press "Start" to start the algorithm and "Stop" to stop the simulation. You can choose to see the simulation on a map of China or the US. Due to yet unresolved reasons, only part of the map may be loaded.





If you should have any comments or questions, please send email to angelx@alum.mit.edu.

Java programs