There's an old, nice, simple, somewhat similar piece of work by Karp: For the cities, use one of the two usual, simple, fast algorithms to find a minimum spann

There's an old, nice, simple, somewhat similar piece of work by Karp: For the cities, use one of the two usual, simple, fast algorithms to find a minimum spanning tree, and then do a depth first traversal of the tree just declining to revisit a city already visited. Turns out that in Euclidean spaces (right, the symmetric problem) this simple device has some astoundingly good convergence properties as the number of cities grows. Having lots of cities is where the usual combinatorial optimization techniques, worst case, go exponential, and the work by Karp works great in just those cases. In effect, roughly, due to the subtrees nearest the leaves, Karp's technique also works with clusters of cities maybe something like in the OP.