Apply 2-OPT to the tour of Example 15.4.4; see Figure 15.7. To speed up the running time, it might be a good idea to resort to the strategy first improvement and simply select the first tour g which is better than f in k-opt. In the special case of a metric TSP, it also makes sense not to consider all possible edge replacements, but to restrict the algorithm to edges being rather close to each other (according to the given metric).