AN EFFICIENT TRANSFORMATION OF THE GENERALIZED TRAVELING SALESMAN PROBLEM CHARLES E. NOON Management Science Program University of Tennessee Knoxville, TN 37996 JAMES C. BEAN Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 91-26 October 1991

An Efficient Transformation of the Generalized Traveling Salesman Problem Charles E. Noon Management Science Program The University of Tennessee, Knoxville 37996. James C. Bean Department of Industrial and Operations Engineering The University of Michigan, Ann Arbor 48109. October 14, 1991 ABSTRACT The Generalized Traveling Salesman Problem (GTSP) is a useful model for problems involving decisions of selection and sequence. The problem is defined on a directed graph in which the nodes hae been pregrouped into m mutually exclusive and exhaustive nodesets. Arcs are defined only between nodes belonging to different nodesets with each arc having an associated cost. The GTSP is the problem of finding a minimum cost m-arc directed cycle which includes exactly one node from each nodeset. In this paper, we show how to efficiently transform a GTSP into a standard asymmetric Traveling Salesman Problem (TSP) over the same number of nodes. The transformation allows certain routing problems which involve discrete alternatives to be modeled using the TSP framework. One such problem is the heterogenous Multiple Traveling Salesmen Problem (MTSP) for which we provide a GTSP formulation. Keywords: Traveling salesman problem, vehicle routing problem, integer programming. 1

1.0 Introduction and Problem Statement The Traveling Salesman Problem (TSP) is one of the oldest and most widely studied optimization problems in the field of operations research (see [9]). For the standard TSP, we assume that a single salesman, based at a home city, must visit a number of cities (or customers). The problem is to find the salesman's minimum cost cycle (or tour) which leaves the home city, visits each customer city once and returns to the home city. Real-life routing or sequencing problems often require additional decisions or considerations. Often, the standard TSP is used only after a number of discrete decisions have been made. For example, in vehicle routing, the standard TSP is often applied after the customer to vehicle assignments have been made. Preliminary decisions may also include choice of fleet vs. contract carrier, depot locations, backhauling, and alternative vehicles. The Generalized Traveling Salesman Problem (GTSP) is a useful model for problems involving decisions of selection and sequence. The asymmetric version of the problem is defined on a directed graph with nodes N^, connecting arcs A and a vector of corresponding arc costs c. The nodes are pregrouped into m mutually exclusive and exhaustive nodesets, i.e., AX = S1 U S2 U. U Sm with SI n Sj = 0, for all I, J, I J J. Connecting arcs are defined only between nodes belonging to different sets, that is, there are no intraset arcs. Each defined arc (i, j) E A has a corresponding nonegative cost cij > 0. The GTSP can be stated as the problem of finding a minimum cost m-arc cycle which includes exactly one node from each nodeset. The standard asymmetric TSP is a special case of the GTSP with nodesets of cardinality one. Figure 1 displays an example GTSP defined on a directed graph. The bold lines illustrate a feasible cycle with a total cost of 59. Early applications using GTSP formulations are given for sequencing computer files [3] and for routing welfare clients through governmental agencies [13]. More recently, Laporte, Nobert and Mercure [81 discuss GTSP applications in the routing of mail vans. Several proposed applications are given in [101 including warehouse order-picking with multiple stock locations, airport selection/routing for courier planes, and certain types of flexible manufacturing scheduling. The main focus of this paper is to show how any problem formulated as a GTSP can be transformed into a standard asymmetric TSP. One benefit of this type of transformation is that it allows existing asymmetric TSP approaches, both heuristic and optimal, to be applied to the transformed GTSP problems. Such an approach may not necessarily outperform specialized algorithms for the GTSP type problems (see [3], [7], [8], [11], and [13]), however, it does provide researchers a means for pursuing or verifying optimality on smaller problems. 2

Another, perhaps more significant, benefit is that the transformation may allow us to relate polyhedral results for the well-studied TSP to more realistic, complex routing problems. Facets of the asymmetric TSP polytope could be examined under an inverse transformation to possibly yield strong cuts for the GTSP polytope. Many important problems in the area of vehicle routing have relaxations which can be modeled as GTSP's and could benefit from this new source of valid inequalities. One such problem is the basic single-depot capacitated vehicle routing problem (VRP). When the vehicle capacity constraints of the VRP are dualized, the relaxed problem becomes a heterogeneous Multiple Traveling Salesmen Problem (MTSP). After presenting details of the transformation in Section 2, we provide a GTSP formulation for the heterogeneous MTSP in Section 3. 2.0 Transformation of GTSP to TSP In this section we show that any asymmetric GTSP can be transformed to a standard asymmetric TSP. The fact that this is possible is not surprising since complexity theory assures us that any NP-hard problem can be polynomially transformed to any other NP-hard problem. Such transformations, however, are often accompanied by a significant increase in the size of the problem instance. For the transformation we present, there is no increase in the number of nodes and only a slight increase in the number of arcs. We begin by formally defining an instance of the asymmetric GTSP which we refer to as P. The transformation consists of two stages. In the first stage, we transform P into a clustered TSP which we denote as P'. In the second stage, P' is transformed into P", a standard asymmetric TSP Definition: P is an instance of the asymmetric GTSP defined over nodes An, connecting arcs A and a vector of nonnegative arc costs c. In addition, Af is the union of m mutually exclusive and exhaustive nodesets S1 U S2 U... U Sm = X and A contains only arcs which connect nodes of different nodesets. Although the problem form presented assumes a rigid structure, it should be noted that we are not narrowly focusing on a special case of the GTSP. In [10], it is shown that problems with overlapping node sets, intraset arcs, and more general costs, can be transformed to a problem in the form of P. In the first stage of the transformation, we construct an instance of the clustered TSP by redefining arcs and arc costs. A clustered TSP is similar to the standard asymmetric TSP except that the nodes are pregrouped into mutually exclusive and exhaustive node clusters. A 3

feasible tour for the clustered TSP must visit all nodes of a cluster before visiting the nodes of any other cluster. Definition: P' is a clustered TSP defined over nodes NM', connecting arcs A' and a vector of corresponding arc costs c'. In addition, A' is the union of m mutually exclusive and exhaustive node clusters C1 U C2 U... U Cm = A'. The data for P' is constructed as follows. Set NA' =_ A and let each set of nodes in AT, Si, corresponds to a cluster of nodes in A', Ci. For each nodeset (or cluster), we assume its member nodes have a given arbitrary ordering. Let il, i2,..., i be the nodes of nodeset Si (or cluster Ci) with r = ISI = ICI. The arcset A' is constructed as follows. Within each cluster Ci with r = ICi| > 1, create intracluster arcs forming a single directed cycle according to its given ordering. Hence, create arcs (il, i2), (i2, i3), (i3, i4),..., (-1, r), (ir, il) in A'. Assign to each of these intracluster arcs a cost of zero, that is, c'l12 = c23 =... = c iOr = cri = 0. For each arc (ij, k1) E A, with j > 1, create an arc (i-1, Jk) E A' with identical cost, hence, c/ijkl = Cijlk. For each arc (il, k') E A with r = 1C||, create an arc (ir, kl) E A' with cost Cirkl = Cilk. Problem 'P' is a clustered TSP with a special structure. Since the only intracluster arcs are the zero cost arcs which form a directed cycle, it is easy to see that any feasible solution to the clustered TSP will traverse ICi - 1 of the intracluster arcs of Ci. Figure 2 displays P' constructed from the GTSP given in Figure 1. The following lemma establishes the relationship between P and P'. Lemma 1: Problem P is equivalent to problem P'. Proof: Given any feasible solution to P, x, expressed as a sequence of nodes x = {ij, kl,..., pq, i }, we can construct a solution y to p as y = {i3, ij+l,..., i-1, kl, kl+l1 k1-1,..., p, pq+l,..., pq-1, i }. The solution y is feasible for P' by definition of a clustered TSP and by the construction of A'. Since each intercluster arc of y has cost equal to a corresponding interset arc of x, the costs of the two solutions are the same. Any feasible solution to P' which enters cluster Ci through node i3 with j $ 1, must leave the cluster from node i-l'. Any feasible solution to P' which enters cluster Ci through node il, must leave the cluster from node ir where r = IC |. This means if we are given a feasible solution to P' which uses intercluster arc (ij, kl), then the solution must necessarily include an intercluster arc into node ij+1 and an intercluster arc out of 4

node k1l-. Therefore, given any y feasible for 'P we can construct a feasible solution to P. x, as follows. For every intercluster arc (ij, k1) in y, include arc (ij+l, k1) in x. Since Cij+l k = Cik, the costs of the two solutions will be the same. * Once the problem is in the form of '/, it can be solved directly as a clustered TSP as in [5] or we can use an approach equivalent to that of Chisman [2] to transform a clustered TSP into a standard asymmetric TSP by simply adding a large cost to all the intercluster arcs, as follows. Definition: P" is a standard asymmetric TSP defined over nodes A"", connecting arcs A", and a corresponding vector of arc costs c". The data for P" is constructed as follows. Set A" _= N' and A" = A'. The arc costs for P" are computed as follows. Let c'- = cj- + 3 if i E Al' and j E Af' belong to different clusters, and let c'i = c-j if i E A' and j E A' belong to the same cluster, where +c > > E cfl. (iJ,)EA, Our main result for transforming the GTSP to a standard asymmetric TSP can easily be stated. Theorem 2: Given P, an asymmetric GTSP with m nodesets, we can transform it to ]p", a standard asymmetric TSP over the same number of nodes. Given an optimal solution to P" with cost strictly less than (m + 1)/3, we can construct an optimal solution to P. 3.0 A GTSP Formulation of the Heterogeneous MTSP For the Multiple Traveling Salesmen Problem (MTSP), each of n customer cities must be visited by one of v salesmen. The salesmen's travel costs between cities are considered homogeneous if they are the same for all salesmen, or heterogeneous if they are different. For the single-depot homogeneous MTSP, a number of transformations to the standard TSP have been provided (see [1], [4], [6], and [12]). For the heterogeneous MTSP, no such transformations are given. In this section show how a single-depot heterogeneous MTSP can be modeled as an asymmetric GTSP. By using the results in Section 2, the problem can then be transformed to an asymmetric TSP. 5

In the single-depot heterogeneous MTSP, the salesmen begin and end their tours from a common depot (city 0). Let IdIr- | < +c be given as the cost for salesman r to travel from city i to city j. For notational convenience, we assume dr is given for all r = 1,..., v, i = 0,..., n, and j = O,..., n, with i $ j. The problem is to determine a set of v distinct salesman routes such that each customer is visited by exactly one salesman and the total travel costs are minimized. To model the problem as a GTSP, we create v + n mutually exclusive nodesets. The first v nodesets, Sr, r = 1, 2,..., v, each contain exactly one node. Let the node in nodeset Sr be denoted as Or, for r = 1, 2,..., v. These v nodes represent copies of the depot with each node corresponding to a particular salesman. Hence, node Or E Sr represents "salesman r's depot". The remaining n nodesets, Si, i = v + 1,..., v + n, each correspond to a particular customer. Each of these nodesets contains v nodes with each node corresponding to a visit by one of the salesmen. Let ir denote the node in the nodeset of customer i corresponding to a visit by salesman r. For the preceding GTSP node and nodeset structure, we define the arcs and their costs as shown in Table 1. Define arc With cost For all Comment (Or, ir) E A corir = do i 1,2,, n salesman r ventures out from "his" depot r = 1, 2,..., v to the rth node of any customer nodeset (ir, jr) E A C'r dj i = 1, 2,..., n salesman r can travel among = 1, 2,..., n the nodesets using only the rth i j node in each customer nodeset r = l2,..., v (jr, Or+l) E A Cjror+l = djr j = 1,2,... n from the rth node of any customer r = 1, 2,..., v - 1 nodeset to "salesman (r + l)'s depot" (j0,O ) E A cjvol = djo j =1,2,..., n salesman v completes the cycle by returning to "salesman l's depot" Table 1: Arcset for GTSP model of heterogeneous MTSP After venturing from his depot, node O', salesman r may pass only through the rth node of each customer nodeset he visits. After salesman r's visits are complete, he returns to the depot into node Or+1, thus launching salesman r + 1 on his way. A feasible GTSP tour can be likened'to the movements of a single driver assigned to a fleet of heterogeneous vehicles. The 6

driver ventures from the depot in vehicle 1, performs the vehicle 1 deliveries, returns vehicle 1 to the depot, then ventures from the depot in vehicle 2, performs vehicle 2 deliveries, and so on. The GTSP formulation for the heterogeneous MTSP has at most (n+ l)v nodes and (n+ l)vn arcs. Since there is exactly one GTSP arc created for each dZ given, degeneracy is not built into the model. As constructed, the model requires each salesman to visit at least one customer. This requirement can be relaxed by adding zero cost arcs (Ov, 01) and (Or, Or+1) for r = 1,..., v - 1. The formulation can also be easily modified to accommodate fixed salesman charges, multiple depots and salesman/customer incompatibilities. 4.0 Concluding Remarks The results presented in Section 2 allow us to transform any problem modeled as a GTSP into a standard asymmetric TSP. One practical complication with this transformation is that arc costs can become very large. This is of no theoretical importance, but may cause stability problems in some solution techniques. In particular, the resulting TSP has an arc and arc cost structure that will cause severe difficulties for traditional assignment-based methods for solving asymmetric TSP's. Specifically, the directed zero cost intracluster cycle will cause a simple subtour elimination algorithm to branch m levels before the first non-zero lower bound might be reached. The approaches for the TSP based on cutting-plane methods may, however, be suitable for solving the transformed problem. Such methods, however, could be successfully applied only if the large costs are avoided. Within a cutting-plane approach, the presence of large costs would pose numerical stability problems for the LP-solver and would inhibit variable elimination. The large costs could, however, be avoided by modifying the transformation in the construction of P". Instead of adding the large constant to intercluster arcs, constraints could be added which would explicitly serve the same purpose as the added constant. The final product of the transformation would be an asymmetric TSP with no large costs but with an additional set of constraints. 7

REFERENCES [1] M. Bellmore and S. Hong, "Transformation of Multisalesmen Problem to the Standard Traveling Salesman Problem," Journal of the A CM 21 (1974) 500-504. [2] J. Chisman, "The Clustered Traveling Salesman Problem," Computers and Operations Research 2 (1975) 115-119. [3] A.L. Henry-Labordere, "The Record Balancing Problem: A Dynamic Programming Solution of a Generalized Travelling Salesman Problem," RIRO B-2 (1969) 43-49. [4] S. Hong and M. Padberg, "A Note on the Symmetric Multiple Traveling Salesman Problem with Fixed Charges," Operations Research 25, (1977) 871-874. [5] K. Jongens and T. Volgenant, "The Symmetric Clustered Traveling Salesman Problem," European Journal of Operational Research 19 (1985) 68-75. [6] R. Jonker and T. Volgenant, "An Improved Transformation of the Symmetric Multiple Traveling Salesman Problem," Operations Research 36 (1988) 163-167. [7] G. Laporte, H. Mercure and Y. Nobert, "Generalized Travelling Salesman Problem Through n Sets of Nodes: The Asymmetrical Case," Discrete Applied Mathematics 18 (1987) 185 -197. [8] G. Laporte and Y. Nobert, "Generalized Travelling Salesman Problem Through n Sets of Nodes: An Integer Programming Approach," INFOR 21(1) (1983) 60-75. [9] E.L. Lawler, J.K. Lenstra, A.H. Rinnooy Kan and D.B. Shmoys, The Traveling Salesman Problem (Wiley, New York, 1985). [10] C.E. Noon, "The Generalized Traveling Salesman Problem," unpublished dissertation, Department of Industrial and Operations Engineering, The University of Michigan (Ann Arbor, 1988). [11] C.E. Noon and J.C. Bean, "A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem," Operations Research 39 (1991) 623-632. [12] M.R. Rao, "A Note on the Multiple Traveling Salesman Problem," Operations Research 28 (1980) 628-632. [13] J.P. Saksena, "Mathematical Model of Scheduling Clients Through Welfare Agencies," CORS Journal 8 (1970) 185-200. 8

Figure 1: Example GTSP with feasible tour in bold. 9

Figure 2: Problem P' constructed from problem P given in Figure 1 (broken line arcs have zero cost). 10