Observations on a Traveling Sales Person
Authors
Chad Abbott and Joel Cockrell
Introduction
The Traveling Sales Person (TSP) problem is an interesting exercise in path optimization and time utilization. The objective of this problem is to find the shortest route in the shortest amount of time. We would like our salesperson to travel to fourteen different cities, visiting each one once, and then return to his starting city. The chart below shows the location of the cities relative to each other. For simplicity we decided that our salesperson would begin his travels at city A. We conducted our research using six different algorithms, in search for the most efficient one.
Brute Force
Brute Force is the standard by which we judged path efficiency in the other five algorithms. It is implemented by calculating all the permutations that can arise from starting at city A. Starting with a fixed position cuts the calculation time by about a day and a half. Even with a fixed starting point, the brute force took about thirteen hours to complete, but when it was done we had a bell curve to contrast the other models. The shortest path resolved to be near 3.79 with a mean just over 8.39 and the standard deviation at 0.8.
Random Sampling
Obviously, thirteen hours is too long to wait for the best answer. We would accept a slightly less efficient path if it meant the answer was delivered promptly. The random sampling algorithm provides the quickness we need, therefore it was used to judge the speed of the remaining paradigms. Our random algorithm sampled 10 million permutations. It took about three minutes to conclude the computations. The output received was a scaled bell-curve similar that of the brute force. The shortest path found was 3.9 but the mean and standard deviation were almost identical to brute force. The data presented below is a comparison between a scaled brute force (blue) and random sampling (red).
Semi-Random
The semi-random approach actually was discovered by incorrectly executing the random sampling. In a random sampling a list containing the path to be traveled is manipulated by choosing two arbitrary cities and swapping their positions in the path. The semi-random algorithm chooses one city and swaps it around in the list. Semi-random turned out to be quicker (because it only randomly chose one city) but not drastically so. Still sampling 10 million permutations, the best path found was near 3.8 and the standard deviation remained close to 0.8. The surprising find with the semi-random walk was that the mean dropped close to 7.79. The graph to the left shows the scaled curves of brute force in blue, random walk in red and the semi-random sampling in green.
Greedy
The greedy algorithm was by far the easiest to implement and quickest to execute. This method takes the path to the closest city and then the shortest path from that city to another city, and so on. The computation time was negligible since our traveling sales person starts from city A. The path derived had a distance near 4.19, which is not disturbing considering the time conservation.
Swarm Intelligence
The swarm intelligence algorithm is designed to simulate the behavior of some insects. There are a large number of “bugs” that endeavor to find some solution. They all have the ability to communicate with each other to find out who has the best answer in the local neighborhood and who has found the best answer in the whole swarm. Our group of bugs took eight minutes with 50 thousand iterations to discover their best path. The shortest distance found was 4.23 with a mean of 4.77. The standard deviation showed the most interesting results with a value of 0.15.
Genetic Algorithm
The genetic algorithm is based on the biological model of the chromosome, which has certain functions that are forced upon it by nature. These functions are mutation, crossover, and artificial selection. For the TSP problem the chromosome is a path, mutation is the randomized swapping of two cities, crossover is the combination of two random chromosomes, and artificial selection is the crossover of a selected pair of chromosomes. We experimented with different implementations of artificial selection. First, we tried combining two efficient paths but discovered that this was more likely to destroy a good path than to create one. We then paired a strong path with a weak path, gaining better results. However our best results came from combining two weak paths. On average, by combining weak pairs we were able to lower the mean and find a better path. The best path found was 4.08, with a mean of 7.83 and a standard deviation of 0.78. It took this algorithm approximately thirty seconds to compute 100,000 iterations.
Bell curve of the genetic algorithm
Conclusion
Brute Force will always give the best route possible, but the fact that it takes a half-day to compute this path makes a brute force method uneconomical. Random and semi-random produce good results in a fair amount of time. The fact that semi-random has a better bell curve is not much of a bonus. Swarm intelligence gives better results more consistently, as proven by the standard deviation. The path that was discovered, while not the best, still is only 0.5 off of the best mark. The greedy algorithm was by far the quickest, and would be most beneficial if clock cycles are expensive. The most efficient algorithm is the genetic algorithm. It can compute a good path in a short amount of time. Below is a graph comparing the brute force, random, semi-random, and genetic algorithms.
Algorithm / Best Path Found / Mean / Standard Deviation / TimeBrute Force / 3.79 / 8.39 / 0.8 / 13 hrs
Random Sampling / 3.79 / 8.39 / 0.8 / 3 min
Semi-Random Sampling / 3.8 / 7.79 / 0.8 / 3 min
Greedy / 4.19 / 4.19 / 0 / 1 second
Swarm Intelligence / 4.23 / 4.77 / 0.15 / 8 min
Genetic Algorithm / 4.08 / 7.83 / 0.78 / 20 seconds
Summary of test cases.