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:
