Princeton COS 126: TSP Heuristics

Below are some ideas for finding a better TSP tour. None of the methods guarantees to find an optimal tour, but they often lead to good tours in practice.

Crossing edges. If two edges in a tour cross, you can decrease the length of the tour by replacing the pair that crosses with a pair that does not cross.

Farthest insertion. It is just like the smallest increase insertion heuristic described in the assignment, except that the cities need not be inserted in the same order as the input. Start with a tour consisting of the two cities that are farthest apart. Repeat the following:

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.

You will have to store all of the unused cities in an appropriate data structure, until they get inserted into the tour. If your code takes a long time, you algorithm probably performs approximately n³ steps. If you're careful and clever, this can be improved to n² steps.

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.

Writing a function to swap two nodes in a linked list provides great practice with coding linked lists. Be careful, it can be a little trickier that you might first expect (e.g., make sure your code handles the case when the 2 cities occur consecutively in the original tour).

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.

This requires some care, as you will have to reverse the orientation of the links in the original tour between nodes 3 and 2 so that your data structure remains a circular linked list. After performing this heuristic, there will be no crossing edges in the tour, although it need not be optimal.