Possible Heuristics for TSP Extra Credit
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 a good tour
in practice.
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:
- Among all cities not in the tour, choose the one that
is farthest from any city already in the tour.
- Insert it 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
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:
- Choose a pair of cities.
- Swap the two cities in 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.