**Introduction**

Some initial results from experimenting with the 2-opt heuristic and applying it to a standard traveling salesman test problem.

C# / WPF equivalent implementation can be found here:

A summary of the 2-opt heuristic is given here:

http://en.wikipedia.org/wiki/2-opt

A nearest neighbour search algorithm is included in the implementation. A comparison is made of the kind of results we get from the 2-opt algorithms, with and without improving the initial tour using the nearest neighbour algorithm.

This prototype is written as a C++ dialog application in Visual Studio 2010.

The usage is simple: simply import a standard *.tsp test problem, such as Att48.tsp (48 capitals of the USA) and click Run. The program periodically updates the graphical layout as the algorithm proceeds and the solutions get progressively better.

As with all other code samples given here, feel free to download it, try it out and improve it or use it to suit your own purpose.

**C++ implementation of the 2-opt algorithm**

// Do all 2-opt combinations void TSPalgorithm::TwoOpt() { // Get tour size int size = tour.TourSize(); // repeat until no improvement is made int improve = 0; while ( improve < 20 ) { double best_distance = tour.TourDistance(); for ( int i = 0; i < size - 1; i++ ) { for ( int k = i + 1; k < size; k++) { TwoOptSwap( i, k ); double new_distance = new_tour.TourDistance(); if ( new_distance < best_distance ) { // Improvement found so reset improve = 0; tour = new_tour; best_distance = new_distance; Notify( tour.TourDistance() ); } } } improve ++; } }

And this is how the swap is done:

void TSPalgorithm::TwoOptSwap( const int& i, const int& k ) { int size = tour.TourSize(); // 1. take route[0] to route[i-1] and add them in order to new_route for ( int c = 0; c <= i - 1; ++c ) { new_tour.SetCity( c, tour.GetCity( c ) ); } // 2. take route[i] to route[k] and add them in reverse order to new_route int dec = 0; for ( int c = i; c <= k; ++c ) { new_tour.SetCity( c, tour.GetCity( k - dec ) ); dec++; } // 3. take route[k+1] to end and add them in order to new_route for ( int c = k + 1; c < size; ++c ) { new_tour.SetCity( c, tour.GetCity( c ) ); } }

**How the program calculates distance**

Notice in the Att48.tsp test file the edge weight type given on the 5th line of text is of type “ATT”. This corresponds to a special pseudo-Euclidean distance function, information on which can be found in the PostScript file at Gerhard Reinelt’s University of Heidelberg link. Using ordinary Euclidean distances to calculate tour lengths will give you results that differ from those in the literature, so use this calculation instead. C++ code for setting up distance matrices of this type is listed below:

int CoordMatrix::CalcPseudoEuclidDistance( const int& x1, const int& x2, const int& y1, const int& y2 ) { int dij = 0; int xd = x1 - x2; int yd = y1 - y2; double rij = sqrt( (xd*xd + yd*yd) / 10.0 ); int tij = round( rij ); if ( tij < rij ) { dij = tij + 1; } else { dij = tij; } return dij; }

Loading the test problem

To try out the algorithm on a standard test problem, click Open and locate where you have saved the Att48.tsp test problem. This will represent the geographical locations of cities as a series of nodes:

**Example usage: generating an aribtrary tour**

In the `TSPalgorithm::Run()`

loop, use the APIs contained in the `Tour`

class to generate the initial ordering of cities visited. In this case we will just use `CreateRandomTour()`

without using the 2-opt heuristic, to demonstrate:

void TSPalgorithm::Run() { tour.Reset(); tour.CreateRandomTour(); Notify( tour.TourDistance() ); }

Upon using the `Run()`

API in this way, loading the Att48.tsp problem and pressing Run, we get the following initial arbitrary tour of length 50802:

Not very good! though readily improvable.

**Example usage: using the 2-opt heuristic**

The 2-opt heuristic is a simple operation to delete two of the edges in the tour path, and re-connect them in the remaining possible way. If the modified tour is an improvement over the previous one, it becomes the best solution, otherwise it is discarded.

So in additional to creating an initial arbitrary tour, we apply the `TwoOpt()`

routine to whizz through all two-edge combinations and finding the best solution obtained from this process:

void TSPalgorithm::Run() { tour.Reset(); tour.CreateRandomTour(); TwoOpt(); }

Giving a total tour length of 11318, a significant improvement:

**Example usage: improving the 2-opt solution with a nearest neighbour search**

Further improvements are possible by employing the use of a nearest neighbour search before the 2-opt heuristic. The nearest neighbour algorithm was one of the first algorithms applied to the travelling salesman problem. The algorithm usually starts at an arbitrary city and repeatedly looks for the next nearest city until all cities have been visited. It can quickly generate a short but sub-optimal tour.

void TSPalgorithm::Run() { tour.Reset(); tour.CreateNearestNeighbourTour(); TwoOpt(); }

Employing the nearest neighbour search beforehand results in a further improvement of tour length 10959:

**Example usage: displaying known optimal solutions**

Like many standard TSP test problems, the optimal solution for the ‘Att48’ problem has long been discovered, and is given in the bottom section of the att.tsp file. So we have an idea of what the optimization algorithm should be aiming for, here is an example in setting up the `Run()`

API to generate our own tours, in this case the optimal one:

void TSPalgorithm::Run() { tour.Reset(); // Create the optimal tour int ct[ 48 ] = {1,8,38,31,44,18,7,28,6,37,19,27,17,43,30,36,46,33,20,47,21,32,39,48,5,42,24,10,45,35,4,26,2,29,34,41,16,22,3,23,14,25,13,11,12,15,40,9 }; for ( int i = 0; i < 48; i++ ) ct[ i ]--; std::vector<int> v( ct, ct + 48 ); tour.SetCities( v ); Notify( tour.TourDistance() ); }

The graphical display of the known optimal solution of tour length 10628 is as shown:

There are many ways of improving the performance of algorithms like these, such as the Lin-Kernighan heuristic or Simulated Annealing, which I will implement in future postings. In the meantime, have fun!

Visual Studio 2010 project with Sample Att48.tsp test problem downloadable from here:

Excellent job! Continue with Lin-Kernighan!:)

Thanks Vernan! Will do eventually, when I get the time…

Can you tell me the systematic sequence of how to run this program ?

From the beginning, let say, what SW we should download to run your code .

Thanx

1. Obtain the download.

2. Extract the folder to a location of your choice.

3. Open the Visual Studio 2010 solution inside this folder – Two_opt.sln.

4. Build the solution by selecting Build > Build Solution.

5. Run the program or debug it by stepping the code (press F10)

Hope this helps.

Hi!

Can somebody help me with the following Task: I have to read the distances from this file att48, used above, and implement the TSP adn calculate the Eucldean distance in c++. Can somebody help me with the code, because I am totally stuck and have no idea even how to begin…Thanks

Thanks for a great write up. In your Tour::DoTwoOpt() function you pass c1, c2, c3, c4 and these are used for testing feasibility, but you copy the nodes at c1 and c4 which are not used and restore them if there is not cost improvement. These move seem to be unnecessary ad those nodes are not changed. Removing these extra moves would improve performance. Or did I total miss something?

Hi Stephen many thanks for the feedback. I haven’t looked at this post for some time, but it would seem you’re absolutely right, that code is superfluous and could probably be safely removed to improve performance. It would be great to implement the Lin-Kernighan algorithm in the same graphical way some day as it also uses n-opt moves and produces world class results. It’s just that some of the documentation on it is pretty impenetrable!

Hi Stephen you are correct I had misunderstood this bit. The downloadable source code has been updated to implement the 2-opt

exactlyas described on the Wiki page, and is now giving significantly better results than previously:http://en.wikipedia.org/wiki/2-opt