Traveling salesman problem with two salesmen

Question

Two salesmen travel around a city visiting all of the stores. Each store needs to be visited by exactly one salesman. How do I compute in Matlab the shortest total distance the salesmen need to travel? Is there a special algorithm for this problem?

Answer 1

Surely this problem is at least as hard as the single traveling salesman (i.e NP-hard) so Matlab will not succeed except for very modest graph size. The usual approach to solving the single traveling salesman is to use dynamic programming, which runs in $O(2^n n)$ time (see e.g. the description on Wikipedia). You can solve the two-salesman variant with only slight modification: once you have finished computing the shortest path length $L$ for a single salesman to visit all subsets of the stores $S$, compute $$\min_{T\subset S}\ L(T) + L(S\setminus T).$$

Answer 2

Though this problem is hard to solve in general, for most purposes you can solve it as an integer linear program. Mathworks even has an example on their website: https://www.mathworks.com/help/optim/examples/travelling-salesman-problem.html