Applying the 2-opt algorithm to travelling salesman problems in Java

This post tackles the problem of applying the 2-opt algorithm to travelling salesman problems in Java.

The results of applying the 2-opt heuristic and applying it to a number standard traveling salesman test problems. are shown

For a more in-depth description of the 2-opt heuristic, please refer to the following Wiki page:

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

The actual 2-opt heuristic can be summarised by the following pseudocode steps, repeating for all feasible combinations of I and k:

1. take route[1] to route[i-1] and add them in order to new_route
2. take route[i] to route[k] and add them in reverse order to new_route
3. take route[k+1] to end and add them in order to new_route       
4. return the new_route;  

A nearest neighbour search algorithm is included in the Java 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 Java Windows-based application in Eclipse . Version: Neon.3 Release (4.6.3)

The usage is simple: using the ‘Open’ dialog button, import a standard *.tsp test problem file, such as Att48.tsp (the 48 capitals of the USA) and click the ‘Run’ dialog button in order to run the algorithm.

Architecture

The application is organised using the Model View Presenter pattern, commonly used for building user interfaces as a means of separating the data to be displayed from the presentation logic.

The application is organised using the Model View Presenter pattern, commonly used for building user interfaces as a means of separating the data to be displayed from the presentation logic.

https://en.wikipedia.org/wiki/Model%E2%80%93view%E2%80%93presenter

The program periodically updates the graphical layout of the tour as the 2-opt algorithm continues to find progressively better solutions ie those with shorter overall tour distances. As with all other code samples available from site here, feel free to download it, try it out and improve it or use it to suit your own purpose.

Java implementation of the 2-opt algorithm

The following code applies the Two-Opt swap to all (i,k) pair combinations

// Do all 2-opt combinations
private void TwoOpt()
{
	// Get tour size
	int size = _tour.TourSize();

	//CHECK THIS!!		
	for (int i=0;i<size;i++)
	{
	       newTour.SetCity(i, _tour.GetCity(i));
	}

	// repeat until no improvement is made 
	int improve = 0;
	int iteration = 0;

	while ( improve < 800 )
	{
		double best_distance = _tour.TourDistance();

		for ( int i = 1; i < size - 1; i++ ) 
		{
			for ( int k = i + 1; k < size; k++) 
			{
				TwoOptSwap( i, k );
				iteration++;
				double new_distance = _newTour.TourDistance();

				if ( new_distance < best_distance ) 
				{
					// Improvement found so reset
					improve = 0;
												
					for (int j=0;j<size;j++)
					{
					    _tour.SetCity(j, _newTour.GetCity(j));
					}
						
					best_distance = new_distance;
						
					// Update the display						
					NotifyTourUpdate(_tour, Double.toString(best_distance), Integer.toString(iteration));
				}
			}
		}

		improve ++;
	}
}

And this code shows how the swap is actually done:

void TwoOptSwap( int i, 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 )
	{
		_newTour.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 )
	{
		_newTour.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 )
	{
		_newTour.SetCity( c, _tour.GetCity( c ) );
	}
}

How the program calculates distance

This implementation current handles two types of distance calculation:
1. “ATT” a special pseudo-Euclidean distance function, information on which can be found in the PostScript file at Gerhard Reinelt’s University of Heidelberg link. http://www.coin-or.org/SYMPHONY/branchandcut/VRP/data/spec.ps
2. “EUC_2D” – an ordinary Euclidean distance function calculated using ordinary Pythagoras.

The pseudo-Euclidean distance is calculated as follows:

// For edge weight type 'ATT'
// Pseudo Euclidean distance
private int CalcPseudoEuclidDistance( int x1, int x2, int y1, int y2 )
{
	int dij = 0;

	int xd = x1 - x2;
	int yd = y1 - y2;

	double rij = Math.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 open standard test problem, click Open and locate where you have saved the test problem.
For example the att48.tsp file:

Once opened, the geographical locations of cities will get plotted as a series of black nodes:

Example usage: generating an aribtrary tour

In the 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:

// Run the optimization algorithm
void Run()
{					
   _tour.CreateRandomTour();
   NotifyTourUpdate(_tour, Double.toString(_tour.TourDistance()), "1"); 
}

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 43900:

A very inefficient solution but one that is 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 addition to creating an initial arbitrary tour, we apply the TwoOpt() routine to process all of the two-edge combinations and discover the shortest-distance solution:

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

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

travelling salesman problems in Java

Improving the efficiency 2-opt heuristic using a nearest neighbour search on the pcb442.tsp test problem

On bigger test problems, a further improvement in performance was observed to be possible by employing the use of a nearest neighbour search before employing the 2-opt heuristic. In other words, instead of starting tour being an arbitrary random tour, we generate a tour that should be an improvement by utilising a nearest neighbour heuristic before applying the 2-opt algorithm.
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.

For this example we use the test problem pcb442.tsp.

We first test on a tour that has first been created randomly before applying 2-opt:

// Run the optimization algorithm
void Run()
{                   
   _tour.CreateRandomTour();     
   TwoOpt();
}

This generated the following tour within the given maximum number of iterations, tour length 57747.

The the same test problem was tested by first using the nearest neighbour algorithm instead of the random tour:

// Run the optimization algorithm
void Run()
{                   
   _tour.CreateNearestNeighbourTour();   
   TwoOpt();
}

Giving an improved overall tour distance of 54637:

travelling salesman problems in Java

One more test problem

Just to prove the efficacy the deceptively simple 2-opt algorithm I finally tested on a 1000+ node problem, pr1002.tsp, which managed to obtain a solution of distance 277460 with in the given time span:

travelling salesman problems in Java

A zip file of the importable Eclipse project (plus sample tsp test problem files) is obtainable from the following link. Any questions or suggestion please contact me.