# Nearest Insertion Traveling Salesman Heuristic: is it faster to insert nearest nodes first?

I am trying to implement the nearest insertion TSP heuristic. However, I am wondering if it matters which node I insert into the subgraph first.

For example, should I start with one node; calculate the distance between this node and the other nodes; and sort the other nodes by this distance? Then, I will insert the closest node (to the first node) first. Will this be faster than randomly choosing nodes to insert?

• I'm a little confused: sure, it can be faster if you insert a random node as the next node, but then you are not following the nearest insertion heuristic anymore. – Juho Dec 1 '18 at 19:57
• @Juho Well, I didn't know a name for this "new technique" but it doesn't matter that I'm not following the insertion heuristic if this variation is faster, so do u know if it is? – Goldname Dec 1 '18 at 20:07

The nearest neighbor heuristic should return considerably shorter tours than random insertion. In fact, we can prove that the ratio of the nearest insertion heuristic's solution to the minimum tour length is bounded by $$O(\log n)$$, where $$n$$ is the number of cities. No such guarantee exists for the random insertion that you propose, i.e., such a heuristic can return very long tours.