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!