The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm (Q1083379)

An algorithm of Held and Karp for the ordinary TSP is extended to the following situation: Given n cities and m salesmen, find m tours, all starting at the same given city, so that no city is visited twice and total distance travelled is minimum. The algorithm employs a Lagrangean relaxation, a subgradient procedure to solve the dual and a greedy algorithm to obtain minimal m-trees. For up to \(n=50\) cities, solutions can be routinely obtained; computational experience with \(n=100\) is documented, too. Alternatively, the problem can be transformed into an equivalent ordinary TSP with \(n+m-1\) cities. Whether the approach given here is more efficient than solving the transformed problem remains to be an open question.