How does the nearest insertion heuristic for TSP work?

Question

In my theoretical computer science class and we were covering "Heuristics". In it we covered "Greedy Heuristics" for the "Vertex Cover Problem", "Interval Scheduling" and the "Traveling Salesperson Problem".

In it we covered the "Nearest Neighbor", "Closest Pair" and "Insertion" heuristics approach to solve the TSP Problem.

The first two are quite clear - the first one connects the starting point to the nearest neighbor and then connect that to its neighbor and so on. The second one you move to the point closest to one of the two ends of your current path. But I don't understand how the third one actually works.

The example is as follows:

And continue this five more times and you get the answer below.

Answer 1

I think that by "insertion heuristic" you mean "nearest insertion heuristic". If this is the case, here is how it works:

1. We're looking to construct a cycle $C$ containing all the nodes of our problem. We will do this by initially constructing a small cycle and slowly adding nodes to it until it contains all the nodes. We start by choosing some starting node $N$ and adding it to $C$. $C$ now contains a single node, $N$.

2. We want to add to $C$ the node which will increase its length the least. To do this we need to find which node to add to our cycle and then figure out where in the cycle to put it. We select this node by choosing the node (not in $C$) which is the closest to any node in $C$. We then insert this node between two nodes in $C$ such that the increase in length is minimal. More formally: Let $k$ be the node we selected. Find an edge $(i,j)$ such that $d_{ik}+d_{kj}-d_{ij}$ is minimal.

3. Add $k$ to $C$, remove edge $(i,j)$, and add edges $(i,k)$ and $(k,j)$.

4. If $C$ contains all the nodes, stop. Otherwise, go to 2.