# 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[1][2] 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;

if(DEBUG)

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 j;

int minPathCity = 0;

// Iterate all cities

while(cityVisited <= dimension)

{

if(DEBUG)

printf("Searching neighbor of %d [total: %3d]\n", ii, cityVisited);

// Iterate through all cites near ii

for(j=1; j<=dimension;j++)

{

// 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

if(!visited[j])

{

// replace the minPath

minPath = distances[ii][j];

minPathCity = j;

//printf("New neighbor for %3d: %3d\n", ii, j);

}

}

}

// set

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

cityVisited++;

}

// Add retour to the first city

cityPath[cityVisited] = cityPath[1];

// Compute running time of NN algorithm

end = clock();

double ct =((end-start)/ ((double)CLOCKS_PER_SEC)) * 1000.0;

return ct;

}

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...

Keep tuned!