Optimization with visualization: An interactive tool for the traveling salesman problem

The Traveling Salesman Problem (TSP) can be stated as follows: Given n points, find a tour through all points (i.e. a roundtrip visiting each point exactly once and returning to the starting point) whose total length is minimum. The most straightforward solution for the TSP would be to try all possible combinations and determine the cheapest. Since the number of permutations of n points is n! this approach is not feasible. Keeping the starting point constant we would have (n - 1)! combinations and for symmetric cases the number of combinations further reduces by half. So, for a problem instance having 100 points the number of possible combinations is (n - 1)! / 2 = 4.67 x 10155. It is still a very big number even for the very fast machines available today. We present visualization as a tool to work with already existing algorithms in an effort to obtain optimal tours for the TSP. The approach (human machine interaction) makes use of the perception abilities of humans to find shorter tours. The interaction is provided by a graphical user interface in which the best tour so far is displayed to the user. The user can look at the tour and suggest changes that he believes will result in a shorter tour. Using the visual approach the user can look at the tour and concentrate only on areas that need improvement.