A Lagrangian Based Approach to the Asymmetric Generalized Traveling Salesman Problem Charles E. Noon Department of Management Science The University of Tennessee James C. Bean Department of Industrial and Operations Engineering The University of Michigan Technical Report 88-17

A Lagrangian Based Approach to the Asymmetric Generalized Traveling Salesman Problem Charles E. Noon Department of Management Science The University of Tennessee, Knoxville 37996. James C. Bean Department of Industrial and Operations Engineering The University of Michigan, Ann Arbor 48109. November 9, 1988 ABSTRACT This paper presents an optimal approach for the Asymmetric Generalized Traveling Salesman Problem (GTSP). The GTSP is defined on a directed graph in which the nodes are grouped into predefined, mutually exclusive and exhaustive sets with the arcset containing no intraset arcs. The problem is to find a minimum cost m-arc directed cycle which includes exactly one node from each set. Our approach employs a Lagrangian relaxation to compute a lower bound on the total cost of an optimal solution. The lower bound and a heuristically determined upper bound are used to identify and remove arcs and nodes which are guaranteed not to be in an optimal solution. Finally, we use an efficient branch-and-bound procedure which exploits the multiple choice structure of the node sets. We present computational results for the optimal approach tested on a series of randomly generated problems. The results show success on a range of problems with up to 104 nodes. 1

1.0 Introduction and Mathematical Formulation The Traveling Salesman Problem (TSP) is one of the oldest and most widely studied optimization problems in the field of operations research. The basic problem is to find a minimum cost Hamiltonian cycle, or tour, over the nodes of a graph (see Lawler, et al. [19851, Parker and Rardin 11983]). The TSP model assumes that the decision maker has decided which nodes will be sequenced, i.e., which cities will be visited. This paper considers a generalization of the TSP which combines the decisions of node selection and node sequencing. Instead of preselecting the nodes to be visited, the generalized model assumes the nodes have been grouped into mutually exclusive and exhaustive node sets. The Generalized Traveling Salesman Problem (GTSP) is then to find a minimum cost cycle which includes exactly one node from each node set. It is generalized since a TSP is a special case with node sets of cardinality one. The Generalized Traveling Salesman Problem allows node alternatives to be considered in the decision process. The first application of a GTSP was presented by Henry-Labordere [1969] for sequencing computer files. About the same time, Saksena [1970] modeled the routing of welfare clients through governmental agencies as a symmetric GTSP. More recently, Laporte, Mercure and Nobert [1987] describe GTSP applications in the routing of mail vans. Potential applications can be found in Noon [1988] with respect to warehouse order picking with multiple stock locations, airport selection and routing for courier planes, and certain types of flexible manufacturing scheduling. The asymmetric GTSP is defined on a directed graph V with nodes KN and connecting arcs A. Let Af be the union of m mutually exclusive and exhaustive node sets, Kf = Si U S2 U * * U Sm and SI n SJ = 0, for all I, J, I $ J. Assume that arcs are defined only between nodes belonging to different sets, that is, there are no intraset arcs. Each arc (i, j) E A has a corresponding cost cij, with Icij < +oo. The GTSP can be stated as the problem of finding a minimum cost m-arc cycle which includes exactly one node from each node set. Figure 1 displays an example GTSP defined on a digraph. The bold lines illustrate a feasible GTSP tour for the problem. The GTSP simultaneously selects the nodes to include in the cycle and sequences the nodes along the cycle. In the problem form presented, given a preselection of nodes or a presequence 2

Figure 1: Example GTSP on a digraph (with feasible tour in bold). of node sets, the remaining problem is well known. Given a preselection of nodes, the remaining problem is a TSP. Given a presequence of node sets, we could determine the nodes to pass through by solving a series of acyclic shortest path problems. These two characteristics will later play an important role in our optimal approach. Although our problem form assumes considerable structure, we are not narrowly focusing on a special case of the GTSP. It can be shown that a class of problems with overlapping node sets, intraset arcs, and sets which may be visited more than once, can be efficiently transformed to a problem in the form presented (Noon and Bean [1988]). We can model the asymmetric GTSP as an integer program (P) with variable xij equal to 3

1 if arc (i, j) is used in a solution tour and 0 if it is not. Problem (P) is displayed as follows. Minimize E: cijxij (i,j)EA Subject to,:E E Xj= 1 iESi jesI (i,j)EA for all sets, SI. (i):E E zj=l1 ifSj jEs, (i,j)EA xij- =: zjk 0 for all nodesj EN. (ii) iEN' ckE~ (i,j)EA (j,k)EA E>1 Z Z E xij > 1 for all sets T, which are proper subsets (iii) IET iESi JET. jESj (i,j)EA of the total number of node sets. xij = 0 or 1 for all (i, j) E A. (iv) Constraint group () contains two constraints for each node set. One constraint requires a solution to include exactly one of the arcs entering a set and the other requires a solution to include exactly one of the arcs leaving a set. Group (it) contains one constraint for each node. They are equivalent to network flow conservation constraints and ensure that a solution tour is uninterrupted and continuous. Constraint group (iii) is needed to prevent subtours from occurring and may contain as many as 2m-1 - m - 1 constraints. Constraint groups () and (iiz) are generalizations of the assignment and subtour prevention constraints commonly used in formulations for the asymmetric TSP. Early approaches for the GTSP were presented by Henry-Labordere [1969], Srivastava, et al. [1969] and Saksena [19701. These approaches are similar to the dynamic programming approach for the TSP (Gonzalez [1962]) in which a state is defined by the sets already visited. One drawback to these types of approaches is that the number of states grows rapidly as the number of node sets increases. More recently, Laporte and Nobert [1983] proposed an integer 4

programming approach for the symmetric GTSP which was successful on problems with up 50 nodes. For the asymmetric GTSP, relaxation-based approaches are presented in two papers by Laporte, Mercure and Nobert [1985,1987]. In the first paper, the subtour prevention and node flow conservation constraints are relaxed with the latter being brought into the objective function. The relaxed problem is solved as a network flow problem and serves as a lower bound. In the second paper, the authors relax the subtour prevention constraints and a set of constraints which ensure that each set is visited. The relaxed problem is solved as an INAI x I/XI assignment problem. In both approaches, the relaxations are used in a branch-and-bound algorithm which branches on the arcs of subtours or on nodes of unvisited sets. The later approach proved to be the most successful and was able to solve 100 node problems using several hundred cpu seconds on a mainframe computer. 2.0 An Optimal Approach The optimal approach we present consists of three separate procedures; problem bounding, arc/node elimination, and branch-and-bound enumeration. The procedures exploit the problem structure realized by mutually exclusive node sets, no intraset arcs, and the requirement of exactly one visit to each set. The first procedure uses a relaxation to efficiently compute lower bounds on the optimal objective value of the problem. The procedure also includes a heuristic for determining upper bounds. These bounds are then used in the second procedure to identify and remove many nonoptimal arcs and nodes. With the problem well-bounded and reduced in size, the third procedure uses implicit enumeration to guarantee an optimal solution. 2.1 Bounds for the GTSP The first procedure employs a Lagrangian relaxation for bounding. The constraints in group (ii) are relaxed and brought into the problem's objective function via a vector of multipliers, A. The relaxed problem reduces to that of finding a minimum cost tour over the node sets, without requiring the tour to enter and leave a set through the same node. We can show that the relaxed problem can be solved as an m-city TSP or closely bounded with an m x m 5

assignment problem. An advantage of this approach is that the size of the relaxed problem depends only on the number of node sets. Let A be a vector of length 1f\X where Ai is the multiplier applied to the node i constraint of group (ii). A nonzero Ai value has the effect of subtracting that value from the costs of all in-arcs of node i and adding the value to costs of all out-arcs of node i. This does not change the order or cost of GTSP solutions, it merely redistributes the costs of the problem. We can define the following Lagrangian relaxation (PR\) as, Minimize E (cij - Ai + Aj)xij (PR,) (i,j)EA Subject to, (i) (iii), (iv). For any problem (.), let V(.) equal the problem's optimal objective value. For any given A, V(PRA) is a lower bound on V(P). Our relaxation has the advantage that in solving (PR\), we need consider only the minimum cost arcs between node sets. For a given A, let c> be the adjusted arc costs, i.e., c- = Cij - Ai + Aj. Lemma 1: There exists no optimal solution to (PRx) in which xij = l,i E SI,j E Sj, and c> > ck,k E SI,I E S,. Proof: Let x* be an optimal solution to (PR\) with element xi- = 1 and c- > ck1, with i, k E SI and j, I E SJ. We could reduce the cost of the tour x* by replacing arc (i, j) with arc (k, 1). The constraints of (PRA) require each set to be visited and prevent node set subtours. The solution obtained by replacing arc (i,j) with arc (k, I) would remain feasible since both arcs connect the same pair of sets. The new solution would be feasible with a lower cost. Hence, x* could not be optimal. m In solving (PRx), Lemma 1 allows us to eliminate all arcs which are not arguments of the minimum costs between node sets. We can now define an aggregation of the original digraph based on the interset arc cost minimums. Definition: Digraph D' = (K', A') is an aggregation of the original digraph V. Let K' consist of m nodes where each node corresponds to a node set of K. Given two nodes 6

I, J E 1/', an arc (I, J) E A' will exist if and only if there is at least one arc (i, j) E A with i E SI and j E SJ. Let the cost of arc (I, J) E A' be defined as CIj where c' = minimum A CJJ - i E S,j E Sj Lemma 2: If x is a feasible solution to (PRx) overV, then there exists a feasible TSP tour y over V' with c'y < cAx. Proof: This follows from the construction of V'. * From Lemma 2, we can translate a feasible set-tour over V to a feasible TSP over VD'. We may now define a mapping that allows us to translate a feasible TSP tour over )' to a feasible solution for (PR\) over ). Definition: Let y be a TSP tour over V'. Let the mapping f be defined as [ f: Y -* X], where Y is a subset of all 0 - 1 vectors of order X'12 and X is all 0 - 1 vectors of order 1f1V2. Given a solution y, f maps y to a solution x as follows: - For yIJ = 1, choose (arbitrarily) exactly one xij, i E SI, j E Sj, such that c'j = cA and set that xij = 1 and all other Xkl, k E SI, I E SJ, equal to 0. - For YIJ = 0, set xij = 0 over all i E S, j E Sj. From the construction of V' and the mapping f, it follows that if y is feasible for the m-city TSP, then x = f(y) is feasible for (PRA) and the solutions have equal objective values. In fact, (PR\) is feasible if and only if the m-city TSP is feasible. Theorem 3: For a given A, an optimal solution to (PR\) can be obtained by solving an m-city TSP over the digraph D'. Proof: Let y* be an optimal solution to the TSP defined over'. We can map y* to a solution, x*, which is feasible for (PR\) and has objective c'y* = cAx*. If x* is not optimal for (PR\), then there exists a feasible xI such that cXxl < cAx*. From Lemma 2, there must exist a feasible TSP tour y1 over V with c'yl < cAxl. This implies c'y < cAxl < cx* = c'y* and contradicts the assumption of optimality on y*. Hence, no such x1 exists and x* must be optimal to (PRA). m 7

Theorem 3 allows us to solve (PRA) as an m-city TSP to determine lower bounds and, under certain conditions, optimal solutions for (P). Although the TSP is considerably smaller than (P), it is nevertheless an NP-hard problem and may be difficult to solve. Let (APRA) be the problem obtained by dropping the subtour elimination constraints of (PRA). Minimize E (cij - Ai + j)xij (APRA) (i,j)EA Subject to, (), (iv). Since (APRA) is a further relaxation of (PR\), V(APRA) is a lower bound on V(PRA). From the usual relationship between the TSP and the assignment problem, Corollary 4 easily follows. Corollary 4: For a given A, an optimal solution to (APRA) can be obtained by solving an m x m assignment problem over the nodes of'. The problems are ordered as below. V(APRA) < V(PRx) < V(P) {m x m Assignment Problem} { m-city TSP} {Full GTSP} The relaxation (APRA) allows us to obtain a fast lower bound on our original problem (P). The strength of the bound depends greatly on the vector A. Ideally, we would like to find a vector of Lagrange multipliers such that V(APRA) is maximized. Since (APRA) has the integrality property (see Geoffrion [1974]), we know that V(APRA) is maximized by setting A equal to the optimal dual values of a linear programming relaxation of (P) excluding constraint group (iii). Rather than optimally solve such a large LP using a direct method, we approximate the A vector using an iterative subgradient algorithm (see Fisher [1981]). The subgradient approach is easier to code and, relative to direct methods, uses little storage. Our bounding procedure begins with a nearest neighbor heuristic generated from each node. The heuristic is identical to the well known nearest neighbor heuristic for the TSP except that a node becomes ineligible once its node set has been visited. The heuristic provides the feasible incumbent (upper bound) as needed for the subgradient algorithm. At each step of 8

the subgradient algorithm, (APRA) is solved as an assignment problem and its solution is used to compute a subgradient direction. Throughout the algorithm, if an assignment problem solution is also a feasible TSP tour, we use it to check for a better incumbent. A TSP tour over the aggregated digraph represents a sequence of node sets over the original digraph. Given a sequence of node sets, we can find a local optimum by solving acyclic shortest path problems over the sequence of node sets. This is often successful in finding better incumbent solutions and, in some cases, optimal solutions. The subgradient algorithm terminates when either the lower bound equals the upper bound or the rate of improvement nears zero. The final output of the bounding procedure consists of a final vector of Lagrange multipliers A, a lower bound V(APR>), and a feasible incumbent with upper bound value Z. 2.2 Arc/Node Elimination After the bounding procedure, we use arc and node elimination tests to reduce the size of the problem. The tests are performed using the reduced (or relative) arc costs for (APRQ). The reduced cost of an arc represents the minimum amount the objective value will increase over V(APR,) if the arc is used in a solution. Given the output A vector from the bounding procedure, we can solve for the optimal dual solution of (APRJ). For node set Si, let uI, vi be the optimal dual values of the constraints of (i) corresponding to Si. In computing the reduced costs, ui is subtracted from the costs of all arcs entering SI, and vi is subtracted from the costs of all arcs leaving SI. For an arc (i,j), i E Si,j E Sj, its reduced cost is given as cij = cij - Ai + Aj - ui - vJ and, by dual feasibility,?ij > 0. These computations do not change the underlying problem, they merely remove costs that will necessarily be incurred in a problem. This allows us to work with the problem defined over the reduced costs. The cost of the current incumbent solution defined over the reduced costs is [Z - V(APR5)], where Z is the upper bound from the subgradient optimization. One classic variable elimination test for integer programming was first discussed by Dakin [19651]. It was noted that a variable could be eliminated if its reduced cost exceeded the reduced cost of the incumbent solution. This simple yet powerful test is valid since any solution with the variable equal to one would have an objective value greater than the known feasible incumbent. 9

For the GTSP, the preceding variable elimination can be extended. Let the shortest reduced cost path be defined as the shortest directed path from one node to another over the reduced arc costs. Let SP(i, j) be the total cost of the shortest reduced cost path from node i to node j. Theorem 5: If [ij + SP(j, i)] > [Z - V(APR3)] then the variable xij and its corresponding arc cannot be included in a feasible solution which is better than the current incumbent and can be eliminated from the problem. Proof: For a given arc (i, j), its reduced cost is separable, and hence, only represents the additional cost incurred by traveling from the arc's tail (node i) to its head (node j). Yet if the arc is to be used in a feasible solution it must be connected to a tour. Any tour which includes arc (i, j) also includes a "return path" from j to i. The length of a tour's "return path" must be at least as long as the shortest "return path" from j to i. Hence, Tij + SP(j, i) is a lower bound on the reduced cost of any tour which includes arc (i, j). If this lower bound exceeds the reduced cost of the current incumbent, then arc (i, j) is guaranteed not to be in a feasible solution which is better than the incumbent and can be eliminated. * The arc elimination test can remove a considerable number of arcs from a problem. In some cases all arcs incident to a node might be eliminated, thus allowing the node to be eliminated. Typically, that is not the case and the eliminations merely result in a less connected digraph. The following node elimination test checks for nodes which are not fully connected to all other sets. Theorem 6: For a given node i and any set SK such that i $ SK, if Minimum [SP(i,j) + SP(j, i)] > [Z - V(APRA)], then node i cannot be included in a je SK feasible solution which is better than the current incumbent and can be eliminated from the problem. Proof: For node i to remain under consideration, there must exist a round trip path between i and at least one node in SK with a total path cost less than the current incumbent reduced cost. A lower bound on the round trip cost between some node i E Si and a 10

node j E SK is equal to SP(i, j) + SP(j, i). Otherwise, node i can be eliminated since there can exist no GTSP tour which visits node i and a member of SK and has a cost less than the incumbent. I We begin the elimination procedure by calculating the reduced arc costs. The optimal dual values needed for the calculations can be obtained by solving the assignment problem associated with (APRi). The dual solutions of the two problems are equivalent. Once the reduced costs are computed, we apply the nearest neighbor heuristic. In our experiments, the heuristic applied over the reduced costs often produced an improved incumbent. Next, an induction algorithm is employed for computing the shortest reduced cost path between all pairs of nodes. The algorithm requires 0(n3) steps, where n is the total number of nodes. Note that since the shortest path computations are all performed on the nonnegative reduced costs, there is no chance for a negative cycle to appear. The procedure then iterates between the elimination tests and the nearest neighbor heuristic. The arc elimination test checks each arc one at a time for elimination. The node elimination test is applied on each node and involves checking every other node set for round trip connectivity. After the tests are performed, the nearest neighbor heuristic is applied to the reduced costs of the remaining arcs. If a better incumbent is found, the elimination tests are repeated as well as the heuristic. In many cases, the eliminations allowed for better incumbents to be found. The procedure terminates when the heuristic fails to produce a better incumbent. Theoretically, the procedure could iterate as many times as there are arcs, however, in practice, the elimination procedure iterated at most three times. 2.3 Enumeration Procedure If the upper bound is equal to the lower bound then the upper bound solution is optimal. If it is not, we must use an enumeration procedure to divide the feasible region and optimize over the components. One way to enumerate the problem would be as follows. First, list all possible selections of exactly one node from each node set. For each of these combinations, optimally solve an m-city TSP over the selected nodes. The optimal TSP tour with the least cost among all combinations is the optimal tour for the GTSP. This methodology provides the framework for our approach. But rather than explicitly enumerate and list all node selection 11

combinations, we use branch-and-bound to implicitly enumerate them. The node sets possess a "multiple choice" structure since a feasible solution must include exactly one node from each set. We take advantage of this structure by using a branching scheme similar to the approach found in Bean [19841 for multiple choice variable sets. The basis of our branching strategy is that if we select a node to be included in the solution, then we are automatically fixing the other nodes of its set to be excluded. This allows us to divide any problem into separable subproblems by choosing a node set and branching on each node of the set. Any subproblem can be divided further by choosing an unbranched set and branching on each node of the set. If we branch down m levels, we reach subproblems at the bottom of the enumeration tree. A bottom-of-tree subproblem will have one node selected from each node set. Let us refer to these subproblems as full combination subproblems. Any subproblem at a higher level of the tree will have fewer than m nodes selected. Let us refer to these subproblems as partial combination subproblems. In the spirit of branch-and-bound, we try to avoid explicit enumeration by eliminating (or fathoming) partial combination subproblems at the higher levels of the tree. For a given partial combination subproblem, we first check to see if the node most recently selected for inclusion in the subproblem can be eliminated. This is done by calculating the round trip costs between this node and every other selected node of the subproblem. If any one of these round trip costs exceeds the current incumbent, then we know that the subproblem cannot yield a better feasible incumbent and can be fathomed. If a partial combination subproblem cannot be fathomed using the round trip test, we solve a relaxed problem to get a lower bound. The mathematical formulation of any partial combination subproblem is identical to the original GTSP problem except for the nodes that are automatically excluded by the selected nodes. Therefore, for the given subproblem, if we delete the arcs incident to the excluded nodes, we can use the Lagrangian relaxation (APR>) to compute a lower bound on the subproblem. This is done by simply adjusting the aggregated arc costs c' corresponding to the node sets of the selected nodes and solving the resulting m x m assignment problem. The subproblem can be fathomed if its lower bound exceeds the cost of 12

the incumbent since any solution that includes the selected nodes will have a total cost greater than or equal to the incumbent. The enumeration algorithm begins by choosing a node set and branching. Each resulting subproblem is checked for fathoming. Subproblems which cannot be fathomed are put on a list with other unfathomed partial combination subproblems. The subproblem with the least lower bound is selected and we branch on its next unbranched node set. If branching has the effect of creating a full combination subproblem (a bottom-of-tree subproblem), then we model the full combination using (PRy) and solve it as an n-city TSP. The TSP solution tour either produces a new feasible incumbent or it demonstrates that the selection of nodes is not the optimal combination. Hence, bottom-of-tree subproblems are never added to the list. The algorithm continues until the subproblem list is empty or the least lower bound of the list is greater than the incumbent. At this point, the optimal solution is the feasible incumbent. Throughout the algorithm, each assignment problem solution is checked for being a TSP tour. If a TSP tour is found, we search for a better incumbent by solving acyclic shortest paths over the sequence of sets. If a shortest path cost is lower than the current incumbent cost, the shortest path becomes the new incumbent. Let P^ ik represent a subproblem with the first k node sets fixed so that a solution tour must pass through, in no specific order, node il of set S1, node i2 of set S2,..., and node ik of set Sk. Let Z represent the cost of the best feasible incumbent. The enumeration algorithm is given below. Step 0: Formulate the problem with no sets fixed, P~, and solve (APR~) for a lower bound. If V(APR>) > Z, stop, the incumbent is optimal. Otherwise, start a list with P~ and go to Step 1. Step 1: If the list is empty, stop, the incumbent is optimal. Otherwise, choose and remove from the list the problem that has the least lower bound. Let that problem be Ptk,. If its lower bound is greater than or equal to Z, stop, the incumbent is optimal. Otherwise, create a subproblem for each node in node set Sk+l, that is, k+ k j for all j E Sk+1. If k + 1 = m, go to Step 3. Otherwise, go to Step 2. 13

Step 2: For each newly created subproblem, k+l do the following: ii2.....ik., j E Sk+l, do the following: If SP(i, j)+SP(j, i) > [Z-V(APR,)] for any i = i i2,..., ik, then fathom P.k+lj. Otherwise, formulate (APR>) for the subproblem and solve the associated m x m assignment problem. The optimal objective value of the assignment problem represents a lower bound on the subproblem. If the lower bound is greater than or equal to Z, fathom P'+ l ik j. Otherwise, add p,, k. to the list and check if its assignment problem,t,,' solution is a feasible TSP tour. If so, solve the acyclic shortest path problems defined by the tour sequence. If a shortest path yields a feasible GTSP tour with cost less than Z, then the path is a new incumbent. When all newly created subproblems have been addressed, go to Step 1. Step 3: For each newly created subproblem, Pi i2...m-ij, j E Sm, do the following: Formulate (APR,) for the subproblem and solve the associated m x m assignment problem. If the optimal assignment problem objective value is greater than or equal to Z, fathom P, i2,... i_, Otherwise, formulate (PRa) for the subproblem and solve the associated m-city TSP. If the optimal TSP objective value is greater than or equal to Z, fathom Pi2.m-1 Otherwise, the TSP solution is a new feasible incumbent solution and set Z equal to the TSP objective value. When all newly created subproblems have been addressed, go to Step 1. 3.0 Computational Results The objectives of the computer implementation were to gain a better understanding of GTSP difficulty and to test the performance of our approach. The procedures were coded in FORTRAN, and tested on a series of randomly generated problems. In addition to specially written subprograms, the code employed routines for solving the following problems; Assignment Problem (Burkard and Derigs [1977]), All Shortest Paths (described in Murty [1976]), Asymmetric TSP (Phillips and Garcia-Diaz [19811). All computational tests were performed on the University of Tennessee's Vax 8800 computer. Test problems were created by specifying the number of sets (m) and number of nodes per set (n). Since each of the m sets contained n nodes, a problem had a total of mn nodes. Arcs 14

were implied to exist from each node to every other node not in the same set. Hence, the total number of arcs, JAl, is given as m(m - l)n2. As in Laporte, Mercure and Nobert [1985,1987], arc costs were generated according to two methods, namely, Euclidean and Non-Euclidean. For Euclidean problems, 2mn points are randomly drawn on the [0, 100]2 plane. Let the points be P1, P2,.., Pmn and Q1, Q2,..., Qmn. The Euclidean problem arc costs were calculated as cj = Pi - Pj I I if i < j and cij = I IQi - Qj I if i > j and then rounded to the nearest integer. The Non-Euclidean problems were assigned arc costs drawn from a uniform [0,100] distribution and then rounded to the nearest integer. Table 1 shows the combinations of m, n and cost generation used in our study. For each combination, five random problems were created from randomly drawn seeds. With the exception of one combination, all combinations of five problems were successfully solved and the reported results represent average performance for the five problems. The sole exception was in the Euclidean combination of m = 18 and n = 3. Our attempt to solve one of the problems in this combination was unsuccessful in that an unusually large number of subproblems were listed in the enumeration algorithm. As noted, the results for this combination are averaged over the four successful problems. Results for the bounding procedure show its ability to produce good bounds with little computational expense. Table 1, column l(a), shows average final lower bounds attained by (APR,) as a percent of the optimal objective, Z*. The percentages tend to decrease as the number of nodes per set increases. The more nodes per set present, the more opportunity there is for fractional solutions to be present. As the number of sets increase, there appears to be no definite trend. This is probably due to the fact that we are using an assignment problem relaxation. An assignment problem solution can be decomposed so that each subtour is an optimal assignment over some subset of nodes. Therefore, as the number of sets increases, so will the number of solution subtours. Each subtour group, therefore, has approximately the same ratio of lower bound to optimal. The collection of these ratios stays approximately the same as the number of sets increases. The number of subgradient algorithm iterations averaged 44 for the Euclidean problems and 39 for the Non-Euclidean. The percentages of arcs and nodes eliminated during the elimination procedure are shown 15

Problem Bounding Elim. Enumeration Specifications 1(a) 1(b) 1(c) 1(d) 1(e) 1(f) 1(g) % Eliminated No. Max No. cpu m n IAI %(x)% Arcs Nodes AP's Queue TSP's secs Euclidean 8 3 504 87.2 83.7 15.0 119 20 3.0 0.6 4 896 85.3 89.7 28.8 146 17 1.0 0.9 6 2016 77.2 84.7 6.7 1288 205 72 4.2 10 5600 75.2 94.5 29.8 4347 352 1.4 19.3 13 9464 69.3 95.4 19.8 2896 291 1.6 25.9 10 3 810 85.6 83.5 11.3 289 30 4.6 1.3 4 1440 84.2 75.0 1.0 1574 182 12.8 4.6 6 3240 77.0 84.0 1.3 5024 653 2.0 17.1 10 9000 74.3 90.3 2.2 20,584 2647 2.2 107.4 12 3 1188 86.8 70.6 0.5 977 126 10.0 3.8 4 2112 84.9 73.2 0.8 2432 348 8.0 9.4 6 4752 82.5 88.3 12.2 6509 1258 0.8 32.1 15 3 1890 84.7 59.7 0.8 7634 801 t81.2 39.6 4 3360 86.9 76.0 0.3 5970 1055 4.8 34.6 t 18 3 2754 87.9 68.1 0.0 3869 1163 19.8 30.5 Non-Euclidean 8 3 504 83.3 86.6 22.5 69 12 0.8 0.5 4 896 67.7 83.1 2.5 426 57 1.8 1.3 6 2016 70.2 93.6 34.2 367 39 0.4 2.4 10 5600 43.7 96.6 44.5 968 150 0.2 9.0 13 9464 38.4 98.5 61.9 524 75 0.0 15.1 10 3 810 77.8 86.8 24.0 362 38 2.0 1.4 4 1440 59.9 86.0 7.0 1968 157 8.4 5.5 6 3240 74.5 96.6 54.7 838 216 0.4 5.0 10 9000 40.4 95.7 19.0 6903 742 1.6 38.9 12 3 1188 73.9 76.6 3.3 1008 142 2.6 3.9 4 2112 73.1 85.9 1.7 715 115 1.0 4.2 6 4752 57.5 88.2 3.3 4687 741 0.6 23.6 15 3 1890 72.9 75.3 0.0 2337 501 6.0 12.6 4 3360 60.2 83.4 0.3 10,704 1023 5.2 62.2 18 3 2754 69.8 67.6 0.0 9888 1457 19.6 75.7 t Averaged over four successful problems. One problem had 255. Table 1: Results for test problems (average of five problems for each combination). 16

in Table 1, columns l(b) and l(c). With some exceptions, the arc eliminations tend to increase as the number of nodes per set increases. This is due to the fact that for a fixed number of sets, an incumbent value obtained will generally be lower as the number of nodes per set increases. The reduced costs, however, will not tend to change with such an increase. Therefore, an increase in number of nodes per set will yield a lower incumbent solution and serve to eliminate a greater percentage of arcs. The results also show a general tendency for arc eliminations to decrease as the number of sets increases. The problems with more node sets are more difficult to solve and, therefore, the incumbents obtained at this stage of the overall procedure will be relatively further from optimal than would be for problems with fewer sets. The node eliminations occur mostly in problems with fewer node sets. The heuristic applications within the elimination procedure often resulted in better incumbents or, in some cases, optimal solutions. The total number of optimal solutions found before the enumeration procedure were 18 out of 75 Euclidean problems and 27 out of 75 Non-Euclidean problems. Column 1(d) shows the average number of partial combination subproblems for which an m x m assignment problem was solved. As expected, the numbers generally increase with problem size and difficulty. This contrasts sharply with column l(e) which shows the maximum number of subproblems enqueued in the partial subproblem list. To store a listed subproblem, we need only an integer vector of length m (to identify its included nodes) and a single real value (to store its lower bound). The results indicate that although a considerable number of nodes are examined, the storage demands remain modest. This claim was supported by implementing our code on an Apple Macintosh SE. Although the cpu times were considerably longer, we were able to solve practically all of the test problems. For unfathomed full combination subproblems at the bottom of the enumeration tree, we are required to solve an m-city TSP. Column l(f) shows the average number of TSP's solved for the problem combinations. Overall, these numbers are very low. It means that virtually all of the fathoming occurs at the higher levels of the tree and that the methods for finding optimal solutions through acyclic shortest paths work well. 17

Laporte, et al. [1987] Noon and Bean Problem Specs. No. % Al No. cpu No. % IAI No. ttcpu cpu IN I m Al Succ Elim. AP's secs Succ. Elim. AP's sees Ratio 20 8 348 5 16.4 53 1.56 5 71.7 70 52 3.0 11 362 5 8.3 124 4.04 5 79.0 13.45 9.0 30 9 798 5 14.4 465 32.50 5 68.1 422 1.68 19.3 11 816 5 12.3 517 36.54 5 79.5 532 2.18 16.8 40 9 1420 5 17.4 265 37.05 5 81.7 887 3.42 10.8 11 1452 5 12.9 1080 123.26 5 81.0 1759 5.94 20.8 50 8 2186 5 22.1 385 59.17 5 94.2 854 4.20 14.1 9 2220 5 20.1 507 100.55 5 85.7 1803 6.76 14.9 11 2270 5 14.7 396 127.79 5 80.3 5208 17.94 7.1 60 8 3148 5 23.7 317 82.00 5 92.4 1749 7.79 10.5 9 3198 5 22.1 555 147.29 5 86.1 3343 11.97 12.3 11 3270 1 16.7 1257 262.27 5 79.6 11,185 43.18 6.1 70 8 4286 5 24.0 573 195.87 5 89.9 8660 24.98 7.8 11 4452 1 16.5 519 419.48 5 82.0 6960 31.02 13.5 13 4520 1 13.9 785 389.33 5 74.3 8235 45.28 8.6 80 8 5600 4 25.7 437 233.61 5 94.5 4347 19.27 12.1 11 5816 2 18.7 220 223.23 5 88.9 13,878 75.82 2.9 90 8 7086 3 27.8 372 269.06 5 93.9 7542 41.17 6.5 100 8 8748 2 26.7 358 275.08 5 96.1 1569 30.97 8.9 t cpu seconds on a CYBER 173. tt cpu seconds on a VAX 8800. Table 2: Comparison of results for Euclidean problems. The overall optimal approach consisted of the bounding, elimination and enumeration algorithms. Table 1, column l(g), displays the average total cpu times for the problem size combinations (excluding problem read-in). For m < 12, the Euclidean problems generally require more cpu than the Non-Euclidean problems. For m > 15, the Non-Euclidean problems tend to require more effort. One possible explanation for this behavior is that the ratio of pre-enumeration upper bounds to optimal were observed to be much higher for the NonEuclidean problems compared to the Euclidean problems. This means that the Non-Euclidean enumerations were probably spending considerably more time finding the optimal rather than just proving optimality. 18

The test problems generated in Laporte, Mercure and Nobert [1987] differ slightly from our own by including intraset arcs and allowing each set to be visited more than once. However, the authors point out that for the Euclidean problems, it is not necessary to consider intraset arcs or multiple set visits when triangle inequality holds. This allows us to make direct comparisons between results for the Euclidean problems. To test the relative performance of our approach, we created Euclidean problems which were identical to those in Laporte, Mercure and Nobert [19871 in terms of size, configuration and arc cost generation. Table 2 displays a comparison of the results. For a given number of nodes [V/j and sets m, the nodes were distributed as uniformly as possible over the sets. An arc was generated from each node to every other node not in the same set. The results are compared on the basis of successful attempts out of five problems, the percent of arcs eliminated, the number of bounded enumeration subproblems, and the overall cpu time. Both approaches were successful on most problems, however, on problems with Kj| > 60, the Laporte, Mercure and Nobert [1987] approach solved 29 of 50 problems. Our approach successfully solved all 50 such problems. With respect to arc eliminations, our approach was able to significantly reduce the problem size, especially for the very large problems. A comparison between the number of enumeration subproblems indicates that our approach required significantly more assignment problem solutions for lower bounds. It is important to note, however, that our method solves m x m assignment problems as compared to worst case NX1 x 1IX assignment problems. If compared on the basis of the total number of basic operations using an O(n3) assignment problem solver, our approach requird fewer. The last column displays a ratio of cpu times for the two approaches. It indicates our approach to be faster, especially for medium sized problems. 19

4.0 Conclusion The Generalized Traveling Salesman Problem is a difficult optimization problem with potential applications in the areas of distribution, warehousing and scheduling. Its enhancement over the traditional TSP is its ability to simultaneously combine selection and sequencing decisions. The combined approach of bounding, elimination and enumeration proved to be a practical method for solving the asymmetric GTSP. The approach blends the tasks of searching for the optimal solution and establishing its optimality in an efficient, organized fashion. As the computational tests have demonstrated, fairly large problems can be solved. 20

REFERENCES Bean, J.C. [1984], "A Lagrangian Algorithm for the Multiple Choice Integer Program," Operations Research, Vol. 32, pp. 1185-1193. Burkard, R.E. and U. Derigs [1977], "Assignment and Matching Problems: Solution Methods with FORTRAN Programs," Lecture Notes in Economics and Mathematical Systems No. 184, Springer-Verlag. Dakin, R. [1965], "A Tree Search Algorithm for Mixed-Integer Programming Problems," Computer Journal, Vol 8., pp. 250-255. Fisher, M.L. [1981], "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, Vol. 27, No. 1, pp. 1-18. Geoffrion, A.M. [1974], "Lagrangean Relaxation for Integer Programming," Mathematical Programming Study 2, pp. 82-114. Gonzalez, R.H. [1962], "Solutions of the Traveling Salesman Problem by Dynamic Programming on the Hypercube," Interim Technical Report No. 18, Massachusetts Institute of Technology. Henry-Labordere, A.L. [1969], "The Record Balancing Problem: A Dynamic Programming Solution of a Generalized Travelling Salesman Problem," RIRO, B-2, pp. 43-49. Laporte, G. and Y. Nobert [1983], "Generalized Travelling Salesman Problem Through n Sets of Nodes: An Integer Programming Approach," INFOR, Vol. 21, No. 1, pp. 60-75. Laporte, G., H. Mercure and Y. Nobert [1985], "Finding the Shortest Hamiltonian Circuit Through n Clusters: A Lagrangean Approach," Congressus Numerantium, Vol. 48, pp. 277-290. Laporte, G., H. Mercure and Y. Nobert [1987], "Generalized Travelling Salesman Problem Through n Sets of Nodes: The Asymmetrical Case," Discrete Applied Mathematics, Vol. 18, pp. 185-197. 21

Lawler, E.L., J.K. Lenstra, A.H. Rinnooy Kan and D.B. Shmoys [1985], The Traveling Salesman Problem, John Wiley & Sons Ltd., New York. Murty, K.G. [1976], Linear and Combinatorial Programming, John Wiley & Sons Ltd., New York. Noon, C.E. [1988], "The Generalized Traveling Salesman Problem," unpublished dissertation, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor. Noon, C.E. and J.C. Bean [1988], "An Efficient Transformation of the Routing With Alternatives Problem," working paper, Department of Management, University of Tennessee, Knoxville. Parker, R.G. and R.L. Rardin [19831, "The Traveling Salesman Problem: An Update of Research," Naval Research Logistics Quarterly, Vol. 30, pp. 69-96. Phillips, D.T. and A. Garcia-Diaz [1981], Fundamentals of Network Analysis, PrenticeHall, New Jersey. Saksena, J.P. [19701, "Mathematical Model of Scheduling Clients Through Welfare Agencies," CORS Journal, Vol. 8, pp. 185-200. Srivastava, S.S., S. Kumar, R.C. Garg and P. Sen [1969], "Generalized Traveling Salesman Problem Through n Sets of Nodes," CORS Journal, pp. 97-101. 22