# Multiple Traveling Salesman Problem optimal home base

Here is an interesting variation to the classic TSP.

Consider the 20-city TSP. Let city 11 be the home base of a company with an eight-person sales force. Each of the the cities must be visited exactly once (except for the home base). How should the cities be divided up? What routes should sales people take? Assume that each sales person must visit at least two other cities other than the home base on his route.

I have found an optimal solution to this problem by taking note that city 11 must have degree 16 (all the rest having degree exactly 2), and going forward with sub-tour eliminations until a solution is reached.

Now I am trying to modify the problem in order to find the best home base possible. What changes would I need to make in order to minimize the total distance traveled and ensure that one of the cities has degree 16 while the rest have degree 2? Any thoughts or comments would be appreciated!

• Perhaps there is something useful in Rathinam, Sivakumar and Sengupta, Raja, Lower and upper bounds for a symmetric multiple depot, multiple travelling salesman problem, available at escholarship.org/uc/item/4z68041r#main – Gerry Myerson Nov 1 '17 at 1:56
• Have you had a look at that reference? – Gerry Myerson Nov 3 '17 at 0:58
• Are you still here? – Gerry Myerson Nov 4 '17 at 5:52
• I'm voting to close this question as off-topic because OP has abandoned it. – Gerry Myerson Nov 6 '17 at 12:10