In this repository, the Traveling Salesman Problem or TSP is addressed with a variety of approaches.
System Specifications | |
---|---|
IDE | Visual Studio 2019 Version 16.7.2 |
Programming Language | C++ 17 |
Operating System | Windows 10 |
Compiler | Intel Compiler 19.1 |
Extra Frameworks | OpenMP 5.1 |
Processor | Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz |
RAM | 16 GB 2667 MHz |
- Open a terminal
- Clone the repository
git clone https://github.com/andreasceid/tsp.git
- Change directory using
cd tsp/
- Compile the project using
make
- Execute the project using
make run
To rebuild the project, use make clean
first and then execute make
and make run
.
- In
Common.h
the developer can access all the project settings, such as the number of the requested threads or the algorithm to execute - In
Driver.cpp
files the developer can inspect themain
function of the project - In
Utilities.cpp
the developer can inspect the functions called uppon the different algorithms - In
Colonize.cpp
the developer can inspect the main body of the ACS implementation - In
Operation.cpp
there are some helper functions - In
Validation.cpp
there are some functions that perform data extraction - In
Interface.cpp
there are some functions that output in CLI form some feedback to the developer - In
Naive.cpp
there is a custom implementation of the Roulette Wheel Selection algorithm - In
City.cpp
andPherormone.cpp
there are random initializers to generate the required datasets - In
Distance.cpp
there are functions that help with the computation of the cost functions in each of the implemented algorithms
Comparing the different algorithms with some fixed data, there were some interesting results attached below:
Algorithm | Performance (10 cities fixed dataset) | TSP tour cost |
---|---|---|
Naive TSP | 0.02773 seconds | 4500 (mean of 10 executions) |
Heinritz - Hsiao | 0.04765 seconds | 3116.622 |
Naive Heinritz - Hsiao | 0.02859 seconds | 4000 (mean of 10 executions) |
ACS | 0.07339 seconds | 3800 (mean of 10 executions) |
However, with random data, the ACS shows better results regarding the cost function.
To visualize the results and the progress of those algorithms, another repository was created. Using that repository, the result data in ./data
project directory can be moved to the input directory of that project and monitor the algorithms' results.
For the parallel implementations, using the Intel VTUNE profiler, the following results came up:
- For the parallel implementation of the Naive TSP:
98% effective core utilization with 10000 cities sample
- For the parallel implementation of the Naive Heinritz - Hsiao:
98.5% effective core utilization with 100000 cities sample
- For the parallel implementation of the ACS:
95.3% effective core utilization with 1000 cities sample
The GIF below is illustrates the progress of the Naive TSP algorithm approach for 10 cities:
The next images show sample outputs of the ACS algorithm for 10 cities:
The first approach is a naive yet efficient approach:
Consider a radnom TSP tour
Repeat:
Select 2 random cities from that tour
Permutate them
Compute new cost
If cost was worse:
Permutate those cities to their initial order
Until all cities are explored
The second approach is an implementation of the Heinritz - Hsiao algorithm:
Place the traveling salesman on a city
Repeat:
Select the closest city
Update the path
Until all cities have been explored
The third implementation is a variation of the above algorithm:
Place the traveling salesman on a city
Repeat:
Find the closest city
Find the second closest city
Randomly select between those two options
Update the path
Until all cities have been explored
The fourth and final approach uses the Ant Colony Optimization algorithm:
Place
N
ants onN
random cities Repeat:For each ant repeat:
Compute the cost for each possible edge
Fetch each edge's past pherormone
Use roulette wheel and select an edge
Update path
Leave some pherormone on the selected edge
Until
ant memory limit
is reachedVaporize a pherormone percentage globally
Until
M
number of iterations have been completedPick the best edge based on the
pherormone matrix
and make a TSP tour
There is also a parallel implementation for each of the first, the third and the fourth approach using OpenMP 4.0. Finally, there is a project report in Greek.