How can I approach the Travelling Saleman Problem with multiple salesman?

Merged with Travelling Salesman with multiple salesmen?.

I have a problem that has been effectively reduced to a Travelling Salesman Problem with multiple salesman. I have a list of cities to visit from an initial location, and have to visit all cities with limited salesman.

I am trying to come up with a heuristic and was wondering if anyone could give a hand. For example, if I have 20 cities with 2 salesman, the approach that I thought of taking is a 2 step approach. First, divide the 20 cities up randomly into 10 cities for 2 salesman each, and I'd find the tour for each 开发者_如何学编程as if it were independent for a few iteratinos. Afterwards, I'd like to either swap or assign a city to another salesman and find the tour. Effectively, it'd be a TSP and then minimum makespan problem. The problem with this is that it'd be too slow and good neighborhood generation of swapping or assigning a city is hard.

Can anyone give an advise on how I could improve the above? Thanks.