OpenTS Tutorial
MyObjectiveFunction
Incremental Evaluation: General Swap

Now we have the more difficult case where any two customers are swapped. Let's take a look at our partial solution again.

A - B - C - D - E - F - ...

Now suppose we swapped B and E. 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 look at this switch:

B E
A - E - C - E - B - F - ...
E B

Like before, let's see which segments can be subtracted and which must be added:

-AB -BC -DE -EF +AE +EC +EB +BF

There's nothing that can be easily canceled out from here, so let's look at one way to code it:

    ...

    // Else the swap is separated by at least one customer
    else
    {
// | | // A-B-C-D-E-F: swap B and E, say dist -= matrix[ tour[pos1-1] ][ tour[pos1] ]; // -AB dist -= matrix[ tour[pos1] ][ tour[pos1+1] ]; // -BC dist -= matrix[ tour[pos2-1] ][ tour[pos2] ]; // -DE dist -= matrix[ tour[pos2] ][ tour[(pos2+1)%len] ]; // -EF dist += matrix[ tour[pos1-1] ][ tour[pos2] ]; // +AE dist += matrix[ tour[pos2] ][ tour[pos1+1] ]; // +EC dist += matrix[ tour[pos2-1] ][ tour[pos1] ]; // +DB dist += matrix[ tour[pos1] ][ tour[(pos2+1)%len] ]; // +BF
return new double[]{ dist }; } // end if: pair swap ...

Again we use the modulus operator (%) to make sure we wrap around to the first customer if necessary.

We now have an objective function that can either evaluate a solution from scratch or, if a move is proposed, calculate the possible value. Not only can we calculate the possible value, but we can do it efficiently by only calculating the change to the objective function.

That's it for the objective function. Next we'll look at our moves and how we plan to move through the solution space.