# How does the nearest insertion heuristic for TSP work?

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. • You give the example, but not what exactly your question about it is. "I don't understand" is not enough and, as nbro notes correctly, makes the example useless. Please add which step you don't follow, and why. – Raphael Nov 12 '18 at 15:23

## 1 Answer

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.

• Probably. Sorry about the names, they're originally in German and it's called "Incremental Insertion Heuristic ". – xxxtentacion Mar 5 '18 at 21:29