- For each city not in the tour, consider the
*shortest*distance from that city to a city already in the tour. Among all cities not in the tour, select the city whose distance is*largest*. - Insert that city into the tour in the position where it causes the smallest increases in the tour distance.

**Node interchange local search.**
Run the original greedy heuristic (or any other heuristic).
Then repeat the following:

- Choose a pair of cities.
- Swap the two cities if this improves the tour. For example if the original greedy heuristic returns 1–5–6–2–3–4–1, you might consider swapping 5 and 3 to get the tour 1–3–6–2–5–4–1.

**Edge exchange local search.**
Run the original greedy heuristic (or any other heuristic).
Then repeat the
following:

- Choose a pair of edges in the tour, say 1–2 and 3–4.
- Replace them with 1–3 and 2–4 if this improves the tour.