TSP Problem - Part 1 - Construction Algorithm - Nearest Neighbour
His target is to find the shortest tour that visits every city (just once) and return to the start city...
From xkcd.com ( http://xkcd.com/399/ )
For the algorithm class we had the excercise ("Algorithm Cup") to try out the best solution we could find on 10 TSP problems (from the TSPLIB). We have some restriction too, the algorithm has to run on a "simple machine" (duo-core) and has a time limit of 3 minutes for each instance (for each problem).
Considering I've not much time, I choose this approach for implementing my solution:
1) Construction algorithm: Nearest Neighbour
2) Local optimization: 2/2.5 - OPT (web simulation applet)
3) Meta-Heuristics: Simulated Annealing
My expectation (error from the optimal solution) for the above algorithms (depending on the problem):
1) Around 21-26 %
2) Around 4-8%
3) Lower than 1%
Let's start coding (in C), as data structure I choose the simplest (and fastest) possible: array of integer.
First we need to parse the TSPLIB problem files (.tsp) and construct our distances array, my decision was to keep exactly the same numbering of cities from the problem as index of all my arrays.
For example distances give me the distance from city one to city two.
I keep my actual tour in an array named tour and I used to pass this to my functions where I've implemented the algorithms.
Construction Algorithm: Nearest Neighbour
// Compute Nearest Neighbour
// Return running time in ms
double nearestNeighbour(int *_cityPath)
clock_t start, end;
printf("Nearest Neighbour construction...\n");
// Start clock
start = clock();
// Allocate an "already visited" array (the +1 is cause I start my array from index 1)
bool *visited = (bool *) calloc(sizeof(bool), dimension+1);
// Start from city one
int cityVisited = 1;
int minPath = INT_MAX;
int *cityPath = _cityPath;
int ii = 1;
int minPathCity = 0;
// Iterate all cities
while(cityVisited <= dimension)
printf("Searching neighbor of %d [total: %3d]\n", ii, cityVisited);
// Iterate through all cites near ii
// if distance from city ii to j is lower then the minPath
if(distances[ii][j] < minPath)
// if I've not already choose the city
// replace the minPath
minPath = distances[ii][j];
minPathCity = j;
//printf("New neighbor for %3d: %3d\n", ii, j);
cityPath[cityVisited] = ii;
// set ii as already visited
visited[ii] = true;
// ii is the next city
ii = minPathCity;
// reset minPath to INT_MAX for the next round
minPath = INT_MAX;
// increment cityVisited counter
// Add retour to the first city
cityPath[cityVisited] = cityPath;
// Compute running time of NN algorithm
end = clock();
double ct =((end-start)/ ((double)CLOCKS_PER_SEC)) * 1000.0;
Now let's see how it work on a 1577 cities TSP problem (fl1577.tsp)
In the part two we will se how local optimization can improve this tour...