As usual, we consider the TSP of Example 15.1.2. Let us choose the tour of weight 266 constructed using Christofides’ algorithm in Example 15.4.8 as our initial tour f; see Figure 15.8. During the first iteration of 2-OPT, the edges BeMu and NuSt are replaced with BeNu and MuSt; this yields the tour Be__ Nu__ Mu__ St__ Ba__ Fr__ Du__ Aa__ Ha__ Be of length 253; see Figure 1.10.
