An Analysis of Several Heuristics for the Traveling Salesman Problem IV: Insertion Heuristics Can Return Poor k-Optimal ToursResearch Paper
Insertion heuristics build a traveling salesman tour one city at a time: start from a single city, and at each step choose a city not yet on the subtour and splice it into the subtour where it lengthens the subtour least. Local search heuristics start from a tour and repeatedly replace a few of its edges by others while this shortens the tour. Both families…