GRAPH THEORY & APPLICATIONS :: TERM PROJECT (Main Page)

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.
- Brute Force Approach,
- A Simple Modification Approach,
- Nearest Neighbor Method,
- Twice Around The MST Algorithm
- One Half Around The MST Algorithm (approximating version)
There is no known efficient algorithm to solve TSP.

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):

algorithms / AlgorithmTSP.h
algorithms / BruteForce.h
algorithms / NearestNeighbor.h
algorithms / SimpleApproach.h
algorithms / TwiceAroundMST.h
algorithms / OneHalfAroundMST.h
archieve / GraphMaker.h --> Uses Chart Director to create graphs
archieve / randomc.h --> Mersenne random number generator
archieve / Distances.h --> Distances between cities in Turkiye
algorithms / AlgorithmTSP.cpp
algorithms / BruteForce.cpp
algorithms / NearestNeighbor.cpp
algorithms / SimpleApproach.cpp
algorithms / TwiceAroundMST.cpp
algorithms / OneHalfAroundMST.cpp
archieve / GraphMaker.cpp
archieve / mersenne.cpp
Run.cpp --> Runs the program

Run uses distances between 81 cities in Turkey.
Run looks for the triangle equality for all triangles in the graph and adjustes some of them if necessary.
In a loop [city number: 3 to 81],
      Run creates algorithms one by one [algorithms use a better random function = mersenne random generator].
      Gets the results of the algorithms to vectors [duration (calculated in µs) & optimal cost (calculates in km)].
GraphMaker creates image files for duration and optimal solutions of the algorithms.

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).
Excluding brute force method, minimal cost comes from simple approach; however, it is the second slowest method, because it tries all possible improvement duos.

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)
duration (nearest neighbor < twice around mst << 1.5 around mst ~ simple approach << brute force)

Beycan Kahraman [25.11.2008]