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?
Inserting a random point instead of a nearest point can be faster, but then you are not following the nearest insertion heuristic anymore. The key is to realize that the point is not the runtime efficiency of the algorithm, but rather the quality of the solution obtained. Indeed, remember that we are dealing with an NP-hard problem.
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.
