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!
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.