The tours computed by the various construction heuristics in the previous section 2 were only of moderate quality. In this section we address the question of how to improve these tours. In general, improvement heuristics are characterized by a certain type of basic move to alter the current tour. A detailled discussion of improvement strategies can be found in [2].
We will discuss
A 2-opt move consists of eliminating two edges and reconnecting the two resulting paths in a different way to obtain a new tour. There is only one way to reconnect the paths that yield a different tour. Among all pairs of edges whose 2-opt exchange decreases the length we choose the pair that gives the shortest tour. This procedure is then iterated until no such pair of edges is found. The resulting tour is called 2-optimal. Note that the optimum tour is 2-optimal, of course.
Here is the applet. Select the starting tour, which is given to the 2-opt iterator: either a random tour (rand.) or a tour found by the nearest neighbor heuristic 2.1.