Optimization with 2-OPT - Part 2 - Animated TSP Solver

I’m dividing this post into 2 parts:

Part 1: Discuss the technique definition, idea and time complexity.

Part 2 (this post): Applies this technique to a real problem by implementing an heuristic algorithm for the Traveling Salesman Problem.

Interactive Demo (2-OPT applied to TSP)

Cities

Iterations Limit

Delay (in millis)

Algorithm

The algorithm implementation follows the 3 main steps described for Simulated Annealing in the previous post using stochastic sampling, but now applied to TSP:

Find a trial Solution \(s \in S\), for which M(s) is as small as we can make it at a first try.

Apply some transformations, called ‘inversions’, which transforms this trial solutions into some other elements of S, whose measures are progressive smaller.

Check C for elements which might be included in the final s at an advantage. If there are any such elements try to find a transformation which decreases the measure of the sequence.

The JavaScript code follows (and for any other language really, the implementation is trivial):

1
2
3
4
5
6
7
8
9
10
11
12
13
function two_opt(currentTour){
    var n = currentTour.vertices.length;
    var bestTour = currentTour;
    for(let i=1; i<n-2; i++){
        for(let j=i+1; j<n+1; j++){
            if(j-i == 1) continue;
            var swap = currentTour.vertices.slice(0,i).concat(currentTour.vertices.slice(i,j).reverse(), currentTour.vertices.slice(j,n))
            var newTour = {vertices:swap, cost:cost(swap)};
            if(newTour.cost < bestTour.cost) bestTour = newTour;
        }
    }
    return bestTour;
}

That’s pretty much the algorithm behind the interactive demo at the beginning of this page. It is executed until the given ‘iteration limit’ is reached or until there’s no cost improvement after reversing the edges, whatever comes first.

I’m dividing this post into 2 parts:

Interactive Demo (2-OPT applied to TSP)

Algorithm

References

Related Posts