I have $M$ vertices $V_1$ through $V_m$, which are paired into $N$ edges edges $E_1$ through $E_n$. I wish to add $N-1$ additional edges to the graph to produce a path graph that visits all of the vertices exactly once in an order that minimises the total length of the graph.
I currently have a solver using the nearest neighbour algorithm, starting with the edge with a vertex closest to a corner of the bounding box as the start, and then adding a new edge to the closest vertex of the closest unconnected edge, and continuing until the graph is connected.
Given the constraints, is there a better approach than a branch-and-bound iterative approach to finding a more optimal solution? Are there any additional heuristics that could be used to cull the problem space?