How does the nearest insertion heuristic for TSP work?
I think that by "insertion heuristic" you mean "nearest insertion heuristic". If this is the case, here is how it works:


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$.
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.
Add $k$ to $C$, remove edge $(i,j)$, and add edges $(i,k)$ and $(k,j)$.
If $C$ contains all the nodes, stop. Otherwise, go to 2.