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:

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 N3 steps. If you're careful and clever, this can be improved to N2 steps.

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

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:

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.