The Travelling Salesman Problem Problem Definition: A salesman wishes to visit a number of towns, and then will return to his starting town. Given the travelling durations between towns; he should visit each town exactly once, and travels in as short time as possible. The problem is equivalent to find a minimum-weight Hamilton cycle in a weighted complete graph. Algorithms Assuming that triangle inequality is satisfied in the graph, we could find sufficient solutions by these algorithms. |
||
Performance & Outcome Comparison of TSP Algorithms Download program (715 kb) Project Files are (chartdir41.dll should be in Debug or Release Folder in order to use graphing methods):
Run uses distances between 81 cities in Turkey. |
||
Since, durations are very small for some of the algorithms (about µs - not ms), the performance could change according to other processes that uses the system resources. In addition, there is a large performance gap between the algorithms. As a result, algorithm performances are divided by DIVIDE_BF_T(100000), DIVIDE_SA_T(1000), DIVIDE_NN_T (1), DIVIDE_TA_T(10), DIVIDE_TA_T(5000) constants. And lastly, releasing and debugging performances are changing because of using vectors and data structures. The results given below are achieved in release configuration in Visual Studio 2008 [AMD Athlon 64 4000 X2, 2GB 800Mhz DDR2]. The fastest algorithm is nearest neighbor method, and the slowest one is brute force of course (could get results to 12 nodes). |
||
3 nodes to 7 nodes: cost (simple approach ~ brute force)
|
||
3 nodes to 12 nodes: cost (still simple ~ brute force) Brute force / 100000 ! |
||
3 nodes to 81 nodes: cost(simple aprroach outperforms others) , duration (nearest neighbor is always the best)
minimal cost (brute force > simple approach > nearest neighbor > 1.5 around mst > twice around mst) |