Since we know there is a way to incrementally evaluate the change to so simple an objective function, we want to make use of that to gain better performance.

Let's first consider the case where two adjoining customers are swapped, also known as a pair swap. Below is a representation of a piece of a TSP solution where customers A, B, C, D, and E are being visited, in that order.

A

-

B

-

C

-

D

-

E

-

...

Now suppose we swapped C and D. We can see that we will no longer be traveling from B to C so that distance can be subtracted from the pre-existing total distance. Let's see what other segments need to be considered.

				C		D
				↑		↑
A	-	B	-	D	-	C	-	E	-	...
				↑		↑
				D		C

We can subtract the distances for BC, CD, and DE because we are no longer traveling those routers. We must add the distances for BD, DC, and CE. This gives us the expression

-BC -CD -DE +BD +DC +CE.

For our problem we know that the distance from C to D will be the same as D to C for every pair of customers so we can reduce our expression to

-BC -DE +BD +CE.

Now we can calculate the incremental change to our objective function with these four terms. Let's look at one way to code this:

    ...

    // Treat a pair swap move differently
    if( pos1 + 1 == pos2 )
    {  
        //     |-|
        // A-B-C-D-E: swap C and D, say (works for symmetric matrix only)
        dist -= matrix[ tour[pos1-1] ][ tour[pos1] ];           // -BC
        dist -= matrix[ tour[pos2]   ][ tour[(pos2+1)%len] ];   // -DE
        dist += matrix[ tour[pos1-1] ][ tour[pos2] ];           // +BD
        dist += matrix[ tour[pos1]   ][ tour[(pos2+1)%len] ];   // +CE
        return new double[]{ dist };
    }   // end if: pair swap

    ...

Notice that we used the modulus operator (%) to make sure we wrap around to the first customer if necessary.

Next we'll look at the more general case where any two customers are swapped.