** Next:** 4. Lower Bounds
** Up:** TSP Algorithms in Action
** Previous:** 2. Construction Heuristics

**Subsections**

#

3. Improving Solutions

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

- Node and edge-insertion (in the near future)
- 2-opt exchanges 3.1
- Lin-Kernighan moves (in the future)

##

3.1 2-opt Exchanges

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.

** Next:** 4. Lower Bounds
** Up:** TSP Algorithms in Action
** Previous:** 2. Construction Heuristics
*Stephan Mertens*

*1999-05-10*