How can a traveling salesman path be easily split up? (approximation)

Question

Let's say we have a problem where there are several cities with variable path costs (in time taken) between them, and we have 2 salesmen that must visit every city at least once, between the two of them.

Now, suppose we have an algorithm that given a salesman and a set of cities, can devise an optimal path for that salesman. What we want to do is split up the cities in such a way that assigning one set to the first salesman and the other set to the other salesman gives us a solution that allows the total time taken to be as low as possible. What is a good way to do this? We want a solution thats good, but not necessarily optimal.

My thought was that we could use some sort of heuristic to determine whether a given split was good or bad, but there are a lot of cities and so picking the split is hard. I'm not entirely sure how to go about this.

To clarify: each city must be visited by at least one salesman, not both.

Edit: its more a Hamiltonian path, we don't need to return to the origin city.

Answer 1

I would start by running Kruskal's algorithm to find the minimum spanning tree. Then cut each edge in turn. Since Kruskal's algorithm finds the minimum spanning tree, cutting an edge should always result in two sets of cities. Check the total spanning distance for the two sets of cities. If the total spanning distance is approximately equal, then the split is worth considering, and you can run the traveling salesman (TS) algorithm on the two sets. If the TS algorithm results in two times that are approximately equal, then that's a good solution. Otherwise, continue cutting edges on the minimum spanning tree.