2
$\begingroup$

I have a little doubt with respect to the two-opt improvement heuristic for TSP. I understand how it works, from the Wikipedia article on 2-opt and "Heuristics for the Traveling Salesman Problem". However, from my understanding and subsequent experiments, it appears this heuristic does not give any guarantee to at least not lead to a worse tour. If this is so, I don't understand how a two-opt move is any better than a random swap of cities. I would really appreciate if this can be clarified for me. Thanks!

$\endgroup$
  • 1
    $\begingroup$ Unfortunately, I am unable to access any of your links. $\endgroup$ – Yuval Filmus Mar 20 '17 at 11:43
  • 2
    $\begingroup$ 2-opt is indeed just a random change and the new tour may be worse, but it can be incorporated in e.g. simulated annealing. If the new tour is shorter, the chance is bigger that simulated annealing will accept the 2-opt change, otherwise it might undo it. $\endgroup$ – Albert Hendriks Mar 20 '17 at 11:51
  • $\begingroup$ @AlbertHendriks Thanks for the answer. That's quite interesting, though! One wonders then, why it's so much touted? And, sorry to bother you, but could you expatiate on why SA would have a greater chance of accepting a better 2-opt move than a better random swap? $\endgroup$ – ayePete Apr 3 '17 at 13:56
  • $\begingroup$ @AlbertHendriks PS: Sorry about the lateness in my reply! :) $\endgroup$ – ayePete Apr 3 '17 at 14:36
  • $\begingroup$ @ayePete SA just checks if the tour is shorter after applying the random 2-opt change. If so, it accepts the change. If not, it randomly undoes or accepts the change. It's basically just an "if"-statement like that. 2-opt is powerful with simulated annealing, since you can find good solutions this way. $\endgroup$ – Albert Hendriks Apr 6 '17 at 9:54
3
$\begingroup$

2-Opt is a move that doesn't guarantee to give a better tour.

We use such moves ($k$-Opt, swap, insertion,..) in local searches to look for a better tour in the neighbor of the input (which is a tour).
Local search consists of browsing all (feasible) tours that can be produced with only one move from the input.
If the input tour is not improved, we call it a local optimum which may be the optimal solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.