6.4.11 m-TSP Problem

Keeping in mind that the m-traveling salesmen problem is, by definition, a single origin-destination problem, it can be easily shown that it can be reformulated as a classical TSP with little effort. Thus, the m-salesmen problem is no more difficult than its one-salesman counterpart, as measured by worstcase computational complexity. (Interestingly, this simple observation was not made until 1973 and 1974 in several independently published papers [BELL 74, ORLO 74, SVES 73].)

Suppose that a m-TSP is given with n points to be visited and with all tours beginning and ending at a common origin V. [Were m = I we would thus have a (n + I)-node TSP.] The equivalent formulation is then obtained by replacing the origin V by m exact copies of it, V_l, V₂, . . . , V_m each connected to the other n nodes exactly as was the original origin and with the same distances. That is, if x is any one of the n points to be visited, then

However, the links connecting the m copies of the origin to each other are assigned "infinite" length, that is, very large by comparison to all other distances in the problem [d(V_i, V_j) = for all i, j = 1, 2, . . . , m].

If we now solve this as a classical single-salesman, (m + n)-point TSP, it can be seen that a minimum tour will never use a link connecting two copies of the origin. In other words, in the shortest single-salesman tour, the sequence "V_i followed by V_j" will never appear (i, j = 1, 2, . . . , m). Then, if the (m + n)-point, single-salesman tour is "folded back" by merging together all copies of the origin into a single node V, the single-salesman tour will decompose into m tours as required by the m-TSP.

Example 12: Two-Salesmen Problem

Consider the problem described by the (symmetric) distance matrix of Table 6-2. (The geometric problem on which the matrix is based is shown in Figure 6.29; ignore the indicated solution for the moment.)

Four points are to be visited from an origin V, using two salesmen. Hence, we need two copies of the origin V, which we call V₁, and V₂. The new distance matrix is then shown in Table 6-3. Note that the V₁ and V₂ rows (and columns) are identical and that we have set d(V₁ V₂) = d(V₂, V₁) = , i.e. to a "very large" number by comparison to other distances in a computer solution of the problem. (We have also set all distances from a point to itself to infinity, to prevent any "self-loops" no matter what solution method is used for the TSP.)

Table 6-3 now describes what is in effect a six-point single TSP. Careful consideration of the problem and some trial-and-error comparisons (or application of an exact TSP algorithm) Iead to the conclusion that the optimum solution of the TSP consists of the tour V_l-3-4-V₂-5-6-V₁, with a total length of 237 units. This tour is shown schematically in Figure 6.30. Merging V₁ and V₂ into the single original origin Vgives Figure 6.29, the solution to the two-TSP, with a length of 237 units.

With regard to the solution of the m-TSP problem, it should be noted that, theoretically, the "MST-and-matching" heuristic algorithm that we presented earlier (Algorithm 6.6) is not applicable, even when the original distance matrix is symmetric and satisfies the triangular inequality. The reason is that, because of setting the distances between the copies of the origins to infinity (or to a "very large" number), the expanded matrix--with the m - 1 copies of the origin--does not satisfy the triangular inequality.

In practice, however, if one is careful, the algorithm still can be applied with success (in the great majority of cases) to obtain a single TSP tour with the expanded matrix. The only cases when the algorithm fails occur when more than half of the odd nodes of the minimum spanning tree on completion of Step 1 of Algorithm 6.6 are nodes that correspond to copies of the origin. This, in turn, would mean that in matching odd degree nodes (Step 2) we would be forced to match two copies of the origin to each other--leading to a tour of infinite length.

We conclude our discussion of the m-TSP by noting that, irrespective of whether or not the original distance matrix satisfies the triangular inequality,

where L(m-TSP) and L(TSP) are, respectively, the lengths of the optimum m-salesmen and single-salesman tours for any given problem. To see the validity of (6.10) simply note that the m-TSP tour has been shown here to cover m - 1 points in addition to the original n + 1 that the 1-TSP tour covers. In fact, we have shown by construction that, more generally,