
small (250x250 max)
medium (500x500 max)
large ( > 500x500)
Full Resolution


5/ 3  Approximation Algorithm for a Multiple Depot, Terminal Hamiltonian Path Problem Sivakumar Rathinam and Raja Sengupta RESEARCH REPORT UCB ITS RR 2007 1 May 2007 ISSN 0192 4095 1 53  Approximation Algorithm for a Multiple Depot, Terminal Hamiltonian Path Problem Sivakumar Rathinam1 and Raja Sengupta2 Abstract Though 2 approximation algorithms are available for several Multiple Depot Travelling Salesman Problems ( TSPs) and Hamiltonian Path Problems ( HPPs), there are no algorithms in the literature for any multiple depot variant of TSP or HPP that has an approximation ratio better than 2. This paper addresses one variant of the Multiple Depot HPP and provides the first 53  approximation algorithm for the same when the costs are symmetric and satisfy triangle inequality. Keywords Multiple Depot Routing, Hamiltonian Path Problem, Travelling Salesman Problem, Approximation Algorithm. I. Introduction This paper considers the following symmetric Multiple Depot, Terminal Hamiltonian Path Problem ( MDTHPP): Given k salesmen that start at different depots, k terminals and n destinations, the problem is to choose paths for each of the salesmen so that ( 1) each salesman starts at his respective depot, visits at least one destination and reaches any one of the terminals not visited by other salesmen, ( 2) each destination is visited exactly once by one salesman and ( 3) the cost of the paths is a minimum among all possible paths for the salesmen. The criteria for the cost of paths considered is the total cost of the edges travelled by the entire collection. MDTHPP is a generalization of the single Travelling Salesman Problem ( TSP) and is NP Hard. Figure ( 1) illustrates a feasible set of paths for a five salesmen problem. Though 2 approximation algorithms are available for several Multiple Depot TSPs and HPPs ([ 17], [ 18], [ 20], [ 21]), there are no algorithms for any multiple depot variant of TSP or HPP that has an approximation ratio better than 2. In this paper, we provide an algorithm with an approximation ratio of 5 3 for MDTHPP if the costs are symmetric and satisfy triangle inequality. We were motivated to do this work with an aim of improving the 2 approximation algorithm 1 already available for MDTHPP ( Rathinam et al. [ 19]). The MDTHPP is closely related to the Multi Depot TSP that has been addressed in GuoXing [ 9]. GuoXing is motivated by a Chinese truck company service where there are three depots and a set of trucks available at each depot. Each truck has to accomplish at least one task and return to any of the three depots. The constraint here is that each depot should retain the same number of trucks after the service. The main difference between MDTHPP and the problem addressed in GuoXing is that MDTHPP allows for the possible set of terminals to be distinct from the set of depots. GuoXing provides a transformation to a standard single TSP wherein most applicable literature for the single TSP can be put to good use. An integer programming formulation of a generalized version of the problem discussed by GuoXing is presented in Kara and Bektas [ 12]. In the formulation of Kara and Bektas, there is an upper and lower bound on the number of vertices visited by each salesman. As 1. Graduate Student, Department of Civil Engineering, University of California, Berkeley, CA 94720, corresponding author: rsiva@ berkeley. edu. 2. Assistant Professor, Department of Civil Engineering, University of California, Berkeley, CA 94720. 1An ! − approximation algorithm is an approximation algorithm that • has a polynomial time running time, and • returns a solution whose cost is within ! times the optimal cost. 2 Starting depot Destination Terminal Fig. 1. A feasible set of paths for 5 salesmen. pointed out in Kara and Bektas, an earlier version of this problem also appears in Kulkarni and Bhave [ 13]. Related to this paper are the approximation algorithms available for the single TSP and the Hamiltonian Path Problems. The 3 2  approximation algorithm by Christofides [ 3] for the single TSP has been extended to a Single Depot, Terminal Hamiltonian Path Problem ( SDTHPP) by Hoogeveen [ 11]. Hoogeveen addresses the SDTHPP of finding a minimum cost path for a salesman that starts at a given depot vertex, visits all the vertices exactly once and ends at a specified terminal vertex. He presents an approximation algorithm by finding a feasible solution to SDTHPP and showing that the cost of the feasible solution is at most 5 3 rd of the optimal cost. In this paper, we tighten this result and show that the cost of the feasible solution thus obtained is at most 5 3 rd of a optimal LP relaxation cost of the SDTHPP. Eventually, we use this tightened result to prove the approximation ratio for MDTHPP. The work by Held and Karp [ 10] for the single TSP are also related to the results in this paper. Held and Karp successfully used Lagrangian Relaxation ( Fisher [ 6], Nemhauser and Wolsey [ 15]) for finding tight lower bounds to the single TSP. In particular, they formulated the single TSP as a minimum cost 1 tree problem with degree constraints on the vertices. By dualizing the degree constraints, they obtained tight lower bounds to the single TSP. It was also shown by Held and Karp that the best lower bound ( also known as the Held and Karp lower bound) computed using this method is equal to the optimal cost of the LP relaxation of the single TSP. Theoretically, it has been shown that the integrality ratio of the LP relaxation of the single TSP is at most 3 2 ( Wolsey [ 24], Shmoys and Williamson [ 22]) when the costs are symmetric and satisfy triangle inequality. There is also an open conjecture that this integrality ratio is at most 4 3 . A. Our approach We formulate MDTHPP as a minimum cost constrained forest problem subject to degree constraints on the vertices. By dualizing the degree constraints, one can obtain an infinite family of lower bounds for the MDTHPP. Each lower bound involves calculating a minimum cost constrained forest. This constrained forest problem is posed as a problem of intersection of two matroids. Since the polyhedra corresponding to the matroid intersection problem has the integrality property, it follows that the best lower bound computed using this method equals the optimal cost corresponding to the Linear Programming ( LP) relaxation of the MDTHPP. As a result, we decompose the LP relaxation of the MDTHPP into a collection of LP relaxations of the Single Depot, Terminal Hamiltonian Path Problem 3 ( SDTHPP). Then we use the approximation algorithm by Hoogeveen [ 11] for the SDTHPP to construct a feasible solution for MDTHPP. If the costs satisfy triangle inequality, we show the cost of this feasible solution is at most 5 3 rd of the optimal LP relaxation cost of the MDTHPP. Hence, it follows that the LP relaxation of MDTHPP has an integrality ratio of at most 5 3 . Also, this LP relaxation of MDTHPP can be solved in polynomial time using the results of Grotschel, Lovasz and Schrijver [ 8]. Hence, we prove there is a 5 3  approximation algorithm for MDTHPP. II. Problem formulation Let k ( ! n) vehicles be initially located at distinct depots represented by vertices { 1, 2, · · · , k}. Let { 1+ k, 2+ k, · · · , n+ k} be vertices representing the destinations to be visited. Each vehicle is required to visit at least one vertex in { 1+ k, 2+ k, · · · , n+ k} and reach a terminal vertex. There are k possible terminals denoted by the set of vertices, { n+ k+ 1, n+ k+ 2, · · · , n+ 2k}. Let V = { 1, 2, · · · , n+ 2k}. Each edge joining vertices i and j has a cost Cij " Q associated with it where Q is the set of all rational numbers. Costs are assumed to be positive and symmetric, i. e., Cij > 0 and Cij = Cji for all i, j. To simplify the presentation in the later part of the paper, MDTHPP is defined over a set of vertices S # V . Let DS and TS be the set of all the depot and terminal vertices present in S respectively ( i. e., DS = S ! { 1, 2, · · · , k}, TS = S ! { n + k + 1, · · · , n + 2k}). Let US := S\{ DS " TS}. The problem formulation given below supposes that  DS =  TS > 0. We use the variable xij to represent the choice of the edge between vertex i and j for all i, j " S. xij = 1 implies the edge joining vertex i and vertex j is chosen and xij = 0 otherwise. The integer programming formulation of MDTHPP is as follows: Copt( S) = min x # i ! DS, j ! US Cijxij + # i, j ! US, i< j Cijxij + # i ! US, j ! TS Cijxij ( 1) i. $ j ! US xij = 1 for all i " DS, ii. $ j ! DS xji + $ j ! US, i< j xij + $ j ! US, j< i xji + $ j ! TS xij = 2 for all i " US, iii. $ j ! US xji = 1 for all i " TS, iv. $ { i, j} ! R, i< j xij !  R − 2 for all R # S,  R ! DS = 2, v. $ { i, j} ! R, i< j xij !  R − 2 for all R # S,  R ! TS = 2, vi. $ { i, j} ! R, i< j xij !  R − 1 for all R # S, vii. xij " { 0, 1} for all i, j " S, i < j. Constraints ( i)( iii) enforce the degree constraints on each vertex. Constraint ( iv) removes any possibility of a path joining two depot vertices. Similarly, constraint ( v) removes any possibility of a path joining two terminal vertices. Constraint ( vi) does not allow the presence of a cycle in any feasible solution. To facilitate further analysis, we add an additional constraint to MDTHPP without changing its set of feasible solutions. This is stated in the following lemma. Lemma II. 1: The following additional constraint can be added to the MDTHPP defined in ( 1) without changing its set of feasible solutions: # i ! DS, j ! US xij + # i ! US, j ! US, i< j xij + # i ! US, j ! TS xij =  US +  DS. ( 2) Proof: Summing the constraints ( 1) over i in problem ( 1) for all vertices in DS, we get $ i ! DS, j ! US xij =  DS. Similarly, summing constraints ( 3) over i, we get $ i ! TS, j ! US xji =  TS =  DS. Summing constraint ( 2) for all vertices in US and using the fact that $ i ! US, j ! US, i< j xij = 4 $ i ! US, j ! US, j< i xji, we get, # i ! DS, j ! US xij + 2 # i ! US, j ! US, i< j xij + # i ! TS, j ! US xji = 2 US % # i ! US, j ! US, i< j xij =  US −  DS. Therefore, # i ! DS, j ! US xij + # i ! US, j ! US, i< j xij + # i ! TS, j ! US xji =  DS + ( US −  DS) +  DS =  US +  DS. Now, MDTHPP can be reformulated with the additional constraint as follows, Copt( S) = min x # i ! DS, j ! US Cijxij + # i, j ! US, i< j Cijxij + # i ! US, j ! TS Cijxij ( 3) i. $ j ! US xij = 1 for all i " DS, ii. $ j ! DS xji + $ j ! US, i< j xij + $ j ! US, j< i xji + $ j ! TS xij = 2 for all i " US, iii. $ j ! US xji = 1 for all i " TS, iv. $ i ! DS, j ! US xij + $ i ! US, j ! US, i< j xij + $ i ! US, j ! TS xij =  US +  DS, v. $ { i, j} ! R, i< j xij !  R − 2 for all R # S,  R ! DS = 2, vi. $ { i, j} ! R, i< j xij !  R − 2 for all R # S,  R ! TS = 2, vii. $ { i, j} ! R, i< j xij !  R − 1 for all R # S, viii. xij " { 0, 1} for all i, j " S, i < j. Let the constraints ( i)( iii) be written as A1 Sx = B1S and ( iv)( vii) written as A2 Sx ! B2S . Let P( S) := { x : A1 Sx = B1S , A2 Sx ! B2S , x & 0}. Hence, the MDTHPP can be restated as Copt( S) = min x { CS( x) : x " P( S), x is an integer}. ( 4) where CS( x) := $ i ! DS, j ! US Cijxij + $ i, j ! US, i< j Cijxij + $ i ! US, j ! TS Cijxij . The LP relaxation of this problem is: Clp( S) = min x { CS( x) : x " P( S)}. ( 5) Just as how the 1 tree played an important role in the single TSP, a forest with  DS disjoint trees satisfying the following constraint plays an important role in MDTHPP: Each tree in the forest spans exactly one vertex from DS, exactly one vertex from TS and a subset of vertices from US. An illustration of such a forest with 5 trees is shown in Fig. 2. Let F( S) = { x : A2 Sx ! B2S , x & 0}. The constrained forest problem, denoted by CF, is: Cf ( S) = min x { CS( x) : x " F( S), x is an integer}. ( 6) The MDTHPP is actually CF with the additional degree constraints present in A1 Sx = B1S . Before we present the algorithm, in the next section, we discuss a Lagrangian dual of MDTHPP and its related results that are crucial in proving the approximation results. 5 Starting depot Destination Terminal Fig. 2. An example of a constrained forest with 5 trees. III. Lagrangian dual of MDTHPP Given x, let di( x, S) denote the degree of vertex i in S. That is di( x, S) = $ j ! US xij for all i " DS, di( x, S) = $ j ! DS xji+ $ j ! US, i< j xij+ $ j ! US, j< i xji+ $ j ! TS xij for all i " US, di( x, S) = $ j ! US xji for all i " TS. Let vi( x, S) := di( x, S) − 1 if i " DS " TS and vi( x, S) := di( x, S) − 2 if i " US. By dualizing the constraints in A1 Sx = B1S , we can obtain the Lagrangian dual to the MDTHPP. This Lagrangian dual problem can be formulated as max ! w( ! , S) where w( ! , S) = min x ! F( S), x is an integer [ CS( x) + # i ! DS ! i( di( x, S) − 1) + # i ! US ! i( di( x, S) − 2) + # i ! TS ! i( di( x, S) − 1)], = min x ! F( S), x is an integer [ CS( x) + # i ! S ! ivi( x, S)]. ( 7) Proposition III. 1: The optimal solutions of the problem, minx{ CS( x) : x " F( S)}, are integers. This implies minx{ CS( x) : x " F( S)} = minx{ CS( x) : x " F( S), x is an integer}. Proof: Let ES include all the edges joining any two vertices in S except the edges that join one vertex in DS and one vertex in TS. Let I1 and I2 be two collections of subsets of ES as follows: I1 = { A # ES: Graph ( S, A) is free of cycles and free of paths connecting any pair of vertices in DS}. I2 = { A # ES: Graph ( S, A) is free of cycles and free of paths connecting any pair of vertices in TS}. It is known in the literature ( Cerdeira [ 1], Cordone and Maffioli [ 4]) that M1 = ( ES, I1) and M2 = ( ES, I2) are matroids. Any x is feasible in { x " F( S), x is an integer} if and only if the set of edges corresponding to x is a common independent set of matroids M1 and M2 with  US +  DS elements. Hence CF can be posed as a maximum weighted two matroid intersection problem. Edmonds [ 5] has shown that the set of feasible solutions corresponding to the intersection of two matroid polyhedra has its extremal points as integers. Hence, the integer constraint on the decision variables can be removed in the constrained forest problem. Thus the optimal solutions of the problem, minx{ CS( x) : x " F( S)}, are integers. 6 Proposition III. 2: The Lagrangian dual problem, max ! w( ! , V ), can be solved using the ellipsoid method in polynomial time. Proof: If  UV  =  DV , for any ! , note that solving the constraint forest problem, w( ! , V ), reduces to solving two minimum cost, assignment problems. In this special case, any ! " " R is optimal for max ! w( ! , V ) where R is the set of all real numbers. Therefore, in the remaining part of the proof, we consider the non trivial case, i. e. when  UV  >  DV . The Lagrangian dual problem can also be written as a linear program as follows: max t, ! i t, ( 8) t ! CV ( x) + # i ! ivi( x, V ), ' x " F( V ). If t " , ! " i solves the above linear program so does t " , ( ! " i + " ) for all " " R. Hence, without loss of generality, we can choose one of the variables in { ! i : ' i " V } to be zero. For simplicity, let us choose ! q = 0 for some q " UV . Let P:= { t, ! i, ' i " V \{ q} : t ! CV ( x)+ $ i ! V \{ q} ! ivi( x, V ), ' x " F( V ).}. Also, let to = Cmin/ 6, ! o i = Cmin/ 6 and # o = Cmin/ 6 where Cmin = mini, j ! V Cij ( Note that by assumption Cmin > 0). Consider the ball Bo = { t, ! i :  t − to ! # o,  ! i − ! o i  ! # o, ' i " V \ { q}}. It is easy to check that Bo # P. Without loss of generality, one can assume 0 ! t ! ( n+ k) Cmax. Using lemma VI. 1 proved in the appendix, all the variables in { ! i : ' i " V \ { q}} can be upper bounded by ( 2n + 2k + 1) Cmax and lower bounded by −( n + k) Cmax where Cmax = maxi, j ! V Cij . Now, consider the following separation problem related to the linear program: Given t " Q and ! i " Q, ' i " V \{ q}, decide whether t, ! i " P and if not find a violated constraint. Using proposition III. 1, we know that the above separation problem is solvable in polynomial time. Since all the variables are bounded and Bo # P, one can use the results in Grotschel et. al [ 8] to conclude that the linear program formulated in ( 8) is solvable in polynomial time using the ellipsoid method. Proposition III. 3: For all S # V with  DS =  TS > 0, max ! w( ! , S) = Clp( S) ! Copt( S). ( 9) Proof: Note that Clp( S) ! Copt( S). By proposition III. 1, since the optimal solutions of the problem, minx{ CS( x) : x " F( S)}, are integers, using corollary ( 6.6) in Nemhauser and Wolsey [ 15], it follows that max ! w( ! , S) = Clp( S). IV. Approximation Algorithm for MDTHPP We generate a feasible solution for the MDTHPP using the following algorithm approx: • Solve the lower bound max ! minx ! F( V )[ CV ( x) + $ i ! V ! ivi( x, V )] using the ellipsoid method. Let ( ! " , x " ) be the corresponding optimal solution. x " corresponds to a disjoint forest with k trees such that a depot vertex and a terminal vertex is contained in each tree. Let Pi( x " ) be the set of all vertices present in the ith tree. Note that Pi( x " ) ! Pj( x " ) = ( for i ) = j and " i ! 1, · · · , k Pi( x " ) = V . Let the depot vertex and the terminal vertex present in Pi( x " ) be denoted as ri and ti. We use Hoogeveen’s approximation algorithm [ 11] to construct a path for each i = { 1, · · · , k} as follows: i. Find the minimum spanning tree Ti corresponding to the vertices in Pi( x " ). ii. Find the set of all wrong degree vertices, Wi, in Ti. A vertex has a wrong degree if – it is not a depot or a terminal vertex and its degree is odd. 7 – it is a depot vertex and its degree is even. – it is a terminal vertex and its degree is even. Note that  Wi is always even. iii. Find the minimum cost perfect matching, Mi, on the set Wi. iv. Now consider the graph using the union of edges in Ti and Mi. This graph is connected and has exactly two odd degree vertices. The two odd degree vertices are the depot vertex and the terminal vertex. v. Construct an Eulerian path that traverses each edge exactly once in the resultant graph. The Eulerian path would have the two odd degree vertices as its end points. This construction can be done using the algorithms given in [ 11],[ 16]. vi. Shortcut this Eulerian path to produce a Hamiltonian path starting at depot vertex ri, visiting all the vertices present in Pi( x " ) and ending at the terminal vertex ti. If the triangle inequality is satisfied, the cost of this Hamiltonian path would be less than or equal to the cost of the Eulerian path. The following is the main result of this paper: Theorem IV. 1: Algorithm approx provides a feasible solution for MDTHPP with an approximation ratio of 5 3 when the costs are symmetric and satisfy triangle inequality. V. Proofs The following theorem states that the integrality ratio of the LP relaxation of MDTHPP is at most 5 3 . Combining this result with theorem III. 2 will prove theorem IV. 1. The rest of the section constructs the necessary results to prove this integrality ratio. Theorem V. 1: If the costs satisfy triangle inequality, then Clp( V ) = max ! w( ! , V ) & 3 5 Copt( V ) . The total cost of the generated feasible solution by algorithm approx is upper bounded by # i ! 1, · · · , k ( C( Ti) + C( Mi)), where C( Ti) and C( Mi) represent the total cost of the edges present in Ti and Mi respectively. Proposition V. 1: C( Ti) ! Clp( Pi( x " )). ( 10) Proof: Since Pi( x " ) has only one depot vertex and Ti is the minimum spanning tree corresponding to the vertices in Pi( x " ), we have C( Ti) = minx{ CPi( x ! )( x) : x " F( Pi( x " )), x is an integer}. Due to lemma III. 1, we get C( Ti) = minx{ CPi( x ! )( x) : x " F( Pi( x " ))}. By definition, Clp( Pi( x " )) = minx{ CPi( x ! )( x) : A1 Pi( x ! ) x ! B1P i( x ! ), x " F( Pi( x " ))}. Hence C( Ti) ! Clp( Pi( x " )). Hence, the total cost of the feasible solution is upper bounded by # i ! 1, · · · , k ( Clp( Pi( x " )) + C( Mi)). ( 11) In the following subsections, we show how to bound $ i= 1, · · · , k Clp( Pi( x " )) and the matching cost C( Mi). A. Decomposition of the LP Relaxation Proposition V. 2: Let ( ! " , x " ) solve the problem Clp( V ) = max ! minx ! F( V )[ CV ( x)+ $ i ! V ! ivi( x, V )]. Then, Clp( V ) = # m= 1, · · · , k Clp( Pm( x " )). Proof: Refer to the appendix. 8 B. Bound on the cost of matching Proposition V. 3: Let O be the set of vertices having odd degree in a given forest = ( A, F). Then the forest contains a union of  O/ 2 edge disjoint paths such that 1. Each path starts and ends with an odd degree vertex. 2. The starting or the terminal vertex of any path never appears as a starting or a terminal vertex in any of the other remaining paths. Proof: Consider the forest G # = ( A, F # ) where F # := F. Consider the following algorithm to generate the desired paths: i. Any non trivial tree ( i. e. a tree that consists at least two vertices) in G # contains at least two odd degree vertices with degree equal to 1. Now, select any two odd degree vertices from each non trivial tree in G # . Remove all the edges on the path joining the two selected vertices in each tree. Let the set of all the edges removed be R. ii. Let F # := F # \ R. Consider the new forest G # = ( A, F # ) and re apply the previous step until G # has no edges. After each iteration, note the following: • Each iteration generates at least one path and all the generated paths are edge disjoint. Note that there could be at most  F iterations. • If a vertex is not selected in a iteration, then the parity of its degree remains the same after the removal of the edges during that iteration. • If a vertex having a odd degree was selected during the iteration, then its degree becomes even after the removal of the edges. Hence, a selected odd degree vertex is never considered for selection again in the subsequent iterations. Therefore, the starting or the terminal vertex of any path never appears as a starting or a terminal vertex in any of the other generated paths. • Each odd degree vertex should have been selected by the end of the algorithm because the iteration stops only when F # is empty. Therefore, the number of edge disjoint paths generated must be equal to  O 2 . Proposition V. 4: Let G # = ( A, F) be a forest with O representing the set of odd degree vertices of G # . Let Eo be the set of all edges joining any two vertices in O. Given a complete graph ( O, Eo), let M be a perfect matching on O such that C( M) ! C( M # ) for every other perfect matching M # on O. If the costs satisfy triangle inequality, then C( M) ! C( F). Proof: From proposition V. 3, G # can be decomposed into a set of edge disjoint paths between all the odd vertices in O. One can replace each path by an edge connecting the starting and the terminal vertex of the path. Now, we have a perfect matching M # # on the set O with C( M # # ) ! C( F) since the costs satisfy triangle inequality. But since C( M) ! C( M # # ), the proposition follows. Let A # V with  DA =  TA = 1. Now, consider the SDTHPP on a set of vertices denoted by A that starts at the depot vertex r " A and ends at the terminal vertex t " A . The LP relaxation of this Hamiltonian path problem is Clp( A) = min x CA( x) ( 12) 9 # j ! A\ t xrj = 1 # j ! A\ r xjt = 1 # j ! A, i< j xij + # j ! A, j< i xji = 2 for all i " A\{ r, t} # i ! A, j ! A, i< j xij =  A − 1 # i ! R, j ! R, i< j xij !  R − 1, for all R # A, 0 ! xij ! 1 for all i, j " A, i < j ( 13) The LP relaxation of the single TSP ( Held and Karp [ 10]) on A can be formulated as follows: Ctsp( A) = min x # i ! A, j ! A, i< j Cijxij ( 14) # j ! A, i< j xij + # j ! A, j< i xji = 2 for all i " A # i ! R, j ! R, i< j xij !  R − 1, for all R * A, 0 ! xij ! 1 for all i, j " A, i < j ( 15) Proposition V. 5: Let A # V with  DA =  TA = 1. Consider the minimum spanning tree MST = ( A, T). Let W the set of all wrong degree vertices in MST. Let M be the minimum cost perfect matching on the set of vertices denoted by W. If the costs satisfy triangle inequality, then C( M) ! 2 3 Clp( A). Proof: Note that C( T) ! Clp( A) ( Refer to the argument in proposition V. 1). Remove the set of edges, Ert, lying on the path joining vertices r and t from T. Now, the degree of each vertex of W in the graph ( A, T\ Ert) is odd. From proposition V. 4 the optimal matching M on the set W has a cost C( M) ! C( T\ Ert). Then we get the following inequality: 2Clp( A) & Clp( A) + C( T) = Clp( A) + C( Ert) + C( T\ Ert) & Clp( A) + C( Ert) + C( M). ( 16) Since the costs satisfy triangle inequality, C( Ert) & Crt. Hence, 2Clp( A) & Clp( A) + Crt + C( M). ( 17) 10 Let xh solve LP relaxation of the SDTHPP defined in ( 12). Now construct a solution x such that xij = xh ij ' i, j " A, i < j and xrt = 1. Clearly x is a feasible solution to the LP relaxation of single TSP defined in ( 14). Hence, Ctsp( A) ! Clp( A) + Crt. If M is the minimum cost perfect matching on W, W # A and if the triangle inequality is satisfied, then Shmoys and Williamson [ 22] have shown that 2C( M) ! Ctsp( A). Using these results in equation ( 17), we get, 2Clp( A) & Clp( A) + Crt + C( M) & Ctsp( A) + C( M) & 2C( M) + C( M) = 3C( M). ( 18) C. Proof of the integrality ratio The following steps show that the integrality ratio is at most 5 3 . From equation ( 11), we have Copt( V ) ! # i= 1, · · · , k ( Clp( Pi( x " )) + C( Mi)) ( 19) Using proposition V. 5, we get Copt( V ) ! # i= 1, · · · , k ( Clp( Pi( x " )) + 2 3 Clp( Pi( x " ))). ( 20) Now, we use proposition VI. 1 to get Copt( V ) ! 5 3 Clp( V ). ( 21) This is the 5 3 integrality factor. Combining this result with theorem III. 2 proves the approximation ratio. References [ 1] Cerdeira, J. O., 1994. Matroids and a forest cover problem. Mathematical Programming 66, p. 403 405. [ 2] Chandler, P., Pachter, M., Swaroop, D., Jeffrey, M. F., Howlett, J. K., Rasmussen, S., Schumacher, C., and Nygard, K., Complexity in UAV Cooperative Control, Proceedings of the American Control Conference, Anchorage, AK May 8 10, 2002. [ 3] N. Christofides, Worst case analysis of a new heuristic for the Traveling Salesman Problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA, 1976. [ 4] Cordone, R., Maffioli, F., 2004. On the complexity of graph tree partition problems. Discrete Applied Mathematics 134, p. 51 65. [ 5] Edmonds, J., 1970. Submodular functions, matroids, and certain polyhedra, in: Combinatorial Structures and Their Applications ( Proceedings Calgary International Conference on Combinatorial Structures and Their Applications, Calgary, Alberta, June 1969; R. Guy, H. Hanani, N. Sauer, J. Schonheim, eds.), Gordon and Breach, New York, pp. 6987. [ 6] Fisher, M., 1981. The Lagrangean relaxation method for solving integer programming problems, Management Science 27, 118. [ 7] Geoffrion, A. M., 1974. Lagrangian relaxation for integer programming, Mathematical Programming Study 2, 81114. [ 8] Martin Grtschel, Lszl Lovsz and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1( 2): 169 197 ( 1981) [ 9] GuoXing, Y., 1995. Transformation of multidepot multisalesmen problem to the standard traveling salesman problem. European Journal of Operational Research 81, p. 557 560. [ 10] Held, M., Karp, R. M., 1970. The traveling salesman problem and minimum spanning trees. Operations Research 18, p. 1138 1162. 11 [ 11] Hoogeveen, J. A., 1991. Analysis of christofides’ heuristic: Some paths are more difficult than cycles. Operations Research Letters, 10: 291– 295 [ 12] Kara, I., Bektas, T., 2005. Integer programming formulations of multiple salesmen problems and its variations. European Journal of Operational Research ( available currently at http:// www. crt. umontreal. ca/ tolga/). [ 13] Kulkarni, R. V., Bhave, P. R., 1985. Integer programming formulations of vehicle routing problems. European Journal of Operational Research 20, p. 58 67. [ 14] Lawler, E., Dec 1975. Mathematical Programming, vol 9, Number 1, pp 31 56. [ 15] Nemhauser, G. L., and Wolsey, L., 1988. Integer and Combinatorial Optimization, J. Wiley and Sons. [ 16] Papadimitriou, C. H., Steiglitz, K., 1998. Combinatorial Optimization: Algorithms and Complexity, Dover Publishers. [ 17] M. Lagoudakis, V. Markakis, D. Kempe, P. Keskinocak, S. Koenig, A. Kleywegt, C. Tovey, A. Meyerson and S. Jain, 2005. Auction Based Multi Robot Routing. In Proceedings of the International Conference on Robotics: Science and Systems ( ROBOTICS), pp 343 350. [ 18] Rathinam, S., R. Sengupta and S. Darbha, “ A Resource Allocation Algorithm for Multi Vehicle Systems with Non holonomic Constraints,” Vol. 4, no. 1, pp. 98 104, IEEE Transactions on Automation Sciences and Engineering, January 2007. [ 19] Rathinam, S. and Sengupta, R., 2006. ” Lower and Upper bounds for a Multiple Depot UAV Routing Problem”, IEEE Control and Decision Conference, San Diego, California. [ 20] Malik, W., Rathinam, S. and Darbha, S., Feb 2007. ” An approximation algorithm for a symmetric Generalized Multiple Depot, Multiple Travelling Salesman Problem ”, Accepted in Operations Research Letters. [ 21] Rathinam, S., 2007. Routing and Monitoring algorithms for UAVs, Ph. D thesis, University of California, Berkeley. [ 22] Shmoys, D. B., Williamson, D. P., September 1990. Analyzing the Held Karp TSP bound: a monotonicity property with application. Information Processing Letters, Vol 35 , Issue 6, Pages: 281  285. [ 23] The Travelling Salesman Problem and its Variations, Kluwer Academic Publishers, 2002. [ 24] Wolsey,. L. A. 1980 Heuristic analysis, linear programming and branch and bound. Math. Programming 13, 121 34. VI. Appendix Proposition VI. 1: For any ( ! " , x " ) that solves max ! minx ! F( S)[ CS( x) + $ i ! S ! ivi( x, S)], Clp( V ) = # m= 1, · · · , k Clp( Pm( x " )) Proof: By proposition ( III. 3) and the definition of w( ! , S) in ( 7), Clp( V ) = max ! w( ! , V ) = max ! min x ! F( V ), x is an integer [ CV ( x) + # i ! V ! ivi( x, V )] = max ! min x ! F( V ) [ CV ( x) + # i ! V ! ivi( x, V )]. ( 22) Since x " is a feasible solution for the above optimization problem, the following constraints must be satisfied by x = x " . xij = 0, for alli " Pm( x " ), for all j " Pn( x " ), for all m, n = 1, · · · , k and m ) = n, # i ! Pm( x ! ), j ! Pm( x ! ), i< j xij =  Pm( x " ) − 1, m = 1, · · · , k, # i ! R, j ! R, i< j xij !  R − 1, for all R # Pm( x " ), m = 1, · · · , k, xij & 0, for all i, j " Pm( x " ), i < j, m = 1, · · · , k. ( 23) Let all the above additional constraints in ( 23) be denoted by Acx ! Bc. Observe that adding these constraints pertaining to the optimal solution, x " , to the constraints present in F( V ) will not the change the optimal cost Clp( V ). Let F " ( V ) = { x : x " F( V ) and Acx ! Bc}. Now, continuing with 12 the definition of Clp( V ), we get, Clp( V ) = max ! min x ! F ! ( V ) [ CV ( x) + # i ! V ! ivi( x, V )]. ( 24) To prove the proposition, we are further going to simplify the objective function and the set of feasible solutions. Since for all i " Pm( x " ), j " Pn( x " ), m, n " { 1, · · · , k}, m ) = n, xij = 0 in x " F " ( V ), equation ( 24) can be written as Clp( V ) = max ! min x ! F ! ( V ) # m= 1, · · · , k [ CPm( x ! )( x) + # i ! Pm( x ! ) ! ivi( x, Pm( x " ))]. ( 25) Let F1 × F2 denote the cartesian product of two sets F1 and F2. Then, x " F " ( V ) if and only if ( x1, x2, · · · , xk) " × k m= 1F( Pm( x " )) where for all i, j " Pm( x " ), i < j, each xm := xij . Hence, equation ( 25) can be further simplified as follows: Clp( V ) = max ! min ( x1, · · · , xk) ! × k m= 1F( Pm( x ! )) # m= 1, · · · , k [ CPm( x ! )( xm) + # i ! Pm( x ! ) ! ivi( xm, Pm( x " ))]. ( 26) This breaks the inner minimization into k independent minimization problems implying Clp( V ) = max ! # m= 1, · · · , k min xm ! F( Pm( x ! )) [ CPm( x ! )( xm) + # i ! Pm( x ! ) ! ivi( xm, Pm( x " ))]. ( 27) Applying the same reasoning to the maximization problem we get Clp( V ) = # m= 1, · · · , k max ! i, i ! Pm( x ! ) min xm ! F( Pm( x ! )) [ CPm( x ! )( xm) + # i ! Pm( x ! ) ! ivi( xm, Pm( x " ))]. ( 28) Using proposition III. 3 with S = Pm( x " ), m = 1, · · · , k, we get, Clp( V ) = # m= 1, · · · , k Clp( Pm( x " )). ( 29) Lemma VI. 1: Let  UV  >  DV , t & 0 and ! q = 0 for some q " UV . For all s " { ! i : ' i " V \{ q}}, without loss of generality, we can assume −( n + k) Cmax ! ! s ! ( 2n + 2k + 1) Cmax where Cmax = maxi, j ! V Cij . 13 Proof: Since  UV  >  DV , one can always choose a forest, xf " F( V ), such that vs( xf , V ) = 1, vq( xf , V ) = − 1 and vi( xf , V ) = 0, ' i " V \ { s, q}. Therefore, we have, t ! CV ( xf ) + ! s − ! q. ( 30) Since t & 0 and CV ( xf ) ! ( n + k) Cmax, ! s & t − CV ( xf ) & −( n + k) Cmax. ( 31) The above equation can be used to lower bound all the variables. To upper bound the variables, we need to consider two cases, i. e. when s is a destination vertex and when s is a depot vertex. Case 1 s is a destination vertex: Similar to the lower bounding argument, one can choose a forest, x # f " F( V ), such that vs( x # f , V ) = − 1, vq( x # f , V ) = 1 and vi( x # f , V ) = 0, ' i " V \ { s, q}. Therefore, we have, t ! CV ( x # f ) + ! q − ! s. Since t & 0 and ! q = 0, it follows that ! s ! CV ( x # f ) − t ! ( n + k) Cmax. ( 32) Case 2 s is a depot vertex: The modified cost of any edge ( Cij + ! i + ! j) joining two destinations i and j, by equation ( 32), is upper bounded by ( 2n+ 2k + 1) Cmax. If ! s & ( 2n+ 2k + 1) Cmax, the degree of the depot vertex ( s) in the optimal solution to the Lagrangian dual problem must be one. Therefore if ! s = ( 2n+ 2k+ 1) Cmax is optimal for the Lagrangian dual problem, so is ! s = ( 2n + 2k + 1) Cmax + " for any " & 0. Hence without any loss of generality, we can upper bound ! s by ( 2n + 2k + 1) Cmax.
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  5/3approximation algorithm for a multiple depot, terminal Hamiltonian path problem 
Subject  TA1001.C792 no. 20071; Business logisticsMathematical models. 
Description  "May 2007."; Includes bibliographical references (leaves 1011).; Harvested from the web on 6/13/07 
Creator  Rathinam, Sivakumar. 
Publisher  Institute of Transportation Studies, University of California, Berkeley 
Contributors  Sengupta, Raja.; University of California, Berkeley. Institute of Transportation Studies. 
Type  Text 
Language  eng 
Relation  Also available online.; http://www.its.berkeley.edu/publications/UCB/2007/RR/UCBITSRR20071.pdf 
DateIssued  [2007] 
FormatExtent  13 leaves : ill. ; 28 cm. 
RelationIs Part Of  Research report, UCBITSRR20071; Research report (University of California, Berkeley. Institute of Transportation Studies) ; UCBITSRR20071. 
Transcript  5/ 3  Approximation Algorithm for a Multiple Depot, Terminal Hamiltonian Path Problem Sivakumar Rathinam and Raja Sengupta RESEARCH REPORT UCB ITS RR 2007 1 May 2007 ISSN 0192 4095 1 53  Approximation Algorithm for a Multiple Depot, Terminal Hamiltonian Path Problem Sivakumar Rathinam1 and Raja Sengupta2 Abstract Though 2 approximation algorithms are available for several Multiple Depot Travelling Salesman Problems ( TSPs) and Hamiltonian Path Problems ( HPPs), there are no algorithms in the literature for any multiple depot variant of TSP or HPP that has an approximation ratio better than 2. This paper addresses one variant of the Multiple Depot HPP and provides the first 53  approximation algorithm for the same when the costs are symmetric and satisfy triangle inequality. Keywords Multiple Depot Routing, Hamiltonian Path Problem, Travelling Salesman Problem, Approximation Algorithm. I. Introduction This paper considers the following symmetric Multiple Depot, Terminal Hamiltonian Path Problem ( MDTHPP): Given k salesmen that start at different depots, k terminals and n destinations, the problem is to choose paths for each of the salesmen so that ( 1) each salesman starts at his respective depot, visits at least one destination and reaches any one of the terminals not visited by other salesmen, ( 2) each destination is visited exactly once by one salesman and ( 3) the cost of the paths is a minimum among all possible paths for the salesmen. The criteria for the cost of paths considered is the total cost of the edges travelled by the entire collection. MDTHPP is a generalization of the single Travelling Salesman Problem ( TSP) and is NP Hard. Figure ( 1) illustrates a feasible set of paths for a five salesmen problem. Though 2 approximation algorithms are available for several Multiple Depot TSPs and HPPs ([ 17], [ 18], [ 20], [ 21]), there are no algorithms for any multiple depot variant of TSP or HPP that has an approximation ratio better than 2. In this paper, we provide an algorithm with an approximation ratio of 5 3 for MDTHPP if the costs are symmetric and satisfy triangle inequality. We were motivated to do this work with an aim of improving the 2 approximation algorithm 1 already available for MDTHPP ( Rathinam et al. [ 19]). The MDTHPP is closely related to the Multi Depot TSP that has been addressed in GuoXing [ 9]. GuoXing is motivated by a Chinese truck company service where there are three depots and a set of trucks available at each depot. Each truck has to accomplish at least one task and return to any of the three depots. The constraint here is that each depot should retain the same number of trucks after the service. The main difference between MDTHPP and the problem addressed in GuoXing is that MDTHPP allows for the possible set of terminals to be distinct from the set of depots. GuoXing provides a transformation to a standard single TSP wherein most applicable literature for the single TSP can be put to good use. An integer programming formulation of a generalized version of the problem discussed by GuoXing is presented in Kara and Bektas [ 12]. In the formulation of Kara and Bektas, there is an upper and lower bound on the number of vertices visited by each salesman. As 1. Graduate Student, Department of Civil Engineering, University of California, Berkeley, CA 94720, corresponding author: rsiva@ berkeley. edu. 2. Assistant Professor, Department of Civil Engineering, University of California, Berkeley, CA 94720. 1An ! − approximation algorithm is an approximation algorithm that • has a polynomial time running time, and • returns a solution whose cost is within ! times the optimal cost. 2 Starting depot Destination Terminal Fig. 1. A feasible set of paths for 5 salesmen. pointed out in Kara and Bektas, an earlier version of this problem also appears in Kulkarni and Bhave [ 13]. Related to this paper are the approximation algorithms available for the single TSP and the Hamiltonian Path Problems. The 3 2  approximation algorithm by Christofides [ 3] for the single TSP has been extended to a Single Depot, Terminal Hamiltonian Path Problem ( SDTHPP) by Hoogeveen [ 11]. Hoogeveen addresses the SDTHPP of finding a minimum cost path for a salesman that starts at a given depot vertex, visits all the vertices exactly once and ends at a specified terminal vertex. He presents an approximation algorithm by finding a feasible solution to SDTHPP and showing that the cost of the feasible solution is at most 5 3 rd of the optimal cost. In this paper, we tighten this result and show that the cost of the feasible solution thus obtained is at most 5 3 rd of a optimal LP relaxation cost of the SDTHPP. Eventually, we use this tightened result to prove the approximation ratio for MDTHPP. The work by Held and Karp [ 10] for the single TSP are also related to the results in this paper. Held and Karp successfully used Lagrangian Relaxation ( Fisher [ 6], Nemhauser and Wolsey [ 15]) for finding tight lower bounds to the single TSP. In particular, they formulated the single TSP as a minimum cost 1 tree problem with degree constraints on the vertices. By dualizing the degree constraints, they obtained tight lower bounds to the single TSP. It was also shown by Held and Karp that the best lower bound ( also known as the Held and Karp lower bound) computed using this method is equal to the optimal cost of the LP relaxation of the single TSP. Theoretically, it has been shown that the integrality ratio of the LP relaxation of the single TSP is at most 3 2 ( Wolsey [ 24], Shmoys and Williamson [ 22]) when the costs are symmetric and satisfy triangle inequality. There is also an open conjecture that this integrality ratio is at most 4 3 . A. Our approach We formulate MDTHPP as a minimum cost constrained forest problem subject to degree constraints on the vertices. By dualizing the degree constraints, one can obtain an infinite family of lower bounds for the MDTHPP. Each lower bound involves calculating a minimum cost constrained forest. This constrained forest problem is posed as a problem of intersection of two matroids. Since the polyhedra corresponding to the matroid intersection problem has the integrality property, it follows that the best lower bound computed using this method equals the optimal cost corresponding to the Linear Programming ( LP) relaxation of the MDTHPP. As a result, we decompose the LP relaxation of the MDTHPP into a collection of LP relaxations of the Single Depot, Terminal Hamiltonian Path Problem 3 ( SDTHPP). Then we use the approximation algorithm by Hoogeveen [ 11] for the SDTHPP to construct a feasible solution for MDTHPP. If the costs satisfy triangle inequality, we show the cost of this feasible solution is at most 5 3 rd of the optimal LP relaxation cost of the MDTHPP. Hence, it follows that the LP relaxation of MDTHPP has an integrality ratio of at most 5 3 . Also, this LP relaxation of MDTHPP can be solved in polynomial time using the results of Grotschel, Lovasz and Schrijver [ 8]. Hence, we prove there is a 5 3  approximation algorithm for MDTHPP. II. Problem formulation Let k ( ! n) vehicles be initially located at distinct depots represented by vertices { 1, 2, · · · , k}. Let { 1+ k, 2+ k, · · · , n+ k} be vertices representing the destinations to be visited. Each vehicle is required to visit at least one vertex in { 1+ k, 2+ k, · · · , n+ k} and reach a terminal vertex. There are k possible terminals denoted by the set of vertices, { n+ k+ 1, n+ k+ 2, · · · , n+ 2k}. Let V = { 1, 2, · · · , n+ 2k}. Each edge joining vertices i and j has a cost Cij " Q associated with it where Q is the set of all rational numbers. Costs are assumed to be positive and symmetric, i. e., Cij > 0 and Cij = Cji for all i, j. To simplify the presentation in the later part of the paper, MDTHPP is defined over a set of vertices S # V . Let DS and TS be the set of all the depot and terminal vertices present in S respectively ( i. e., DS = S ! { 1, 2, · · · , k}, TS = S ! { n + k + 1, · · · , n + 2k}). Let US := S\{ DS " TS}. The problem formulation given below supposes that  DS =  TS > 0. We use the variable xij to represent the choice of the edge between vertex i and j for all i, j " S. xij = 1 implies the edge joining vertex i and vertex j is chosen and xij = 0 otherwise. The integer programming formulation of MDTHPP is as follows: Copt( S) = min x # i ! DS, j ! US Cijxij + # i, j ! US, i< j Cijxij + # i ! US, j ! TS Cijxij ( 1) i. $ j ! US xij = 1 for all i " DS, ii. $ j ! DS xji + $ j ! US, i< j xij + $ j ! US, j< i xji + $ j ! TS xij = 2 for all i " US, iii. $ j ! US xji = 1 for all i " TS, iv. $ { i, j} ! R, i< j xij !  R − 2 for all R # S,  R ! DS = 2, v. $ { i, j} ! R, i< j xij !  R − 2 for all R # S,  R ! TS = 2, vi. $ { i, j} ! R, i< j xij !  R − 1 for all R # S, vii. xij " { 0, 1} for all i, j " S, i < j. Constraints ( i)( iii) enforce the degree constraints on each vertex. Constraint ( iv) removes any possibility of a path joining two depot vertices. Similarly, constraint ( v) removes any possibility of a path joining two terminal vertices. Constraint ( vi) does not allow the presence of a cycle in any feasible solution. To facilitate further analysis, we add an additional constraint to MDTHPP without changing its set of feasible solutions. This is stated in the following lemma. Lemma II. 1: The following additional constraint can be added to the MDTHPP defined in ( 1) without changing its set of feasible solutions: # i ! DS, j ! US xij + # i ! US, j ! US, i< j xij + # i ! US, j ! TS xij =  US +  DS. ( 2) Proof: Summing the constraints ( 1) over i in problem ( 1) for all vertices in DS, we get $ i ! DS, j ! US xij =  DS. Similarly, summing constraints ( 3) over i, we get $ i ! TS, j ! US xji =  TS =  DS. Summing constraint ( 2) for all vertices in US and using the fact that $ i ! US, j ! US, i< j xij = 4 $ i ! US, j ! US, j< i xji, we get, # i ! DS, j ! US xij + 2 # i ! US, j ! US, i< j xij + # i ! TS, j ! US xji = 2 US % # i ! US, j ! US, i< j xij =  US −  DS. Therefore, # i ! DS, j ! US xij + # i ! US, j ! US, i< j xij + # i ! TS, j ! US xji =  DS + ( US −  DS) +  DS =  US +  DS. Now, MDTHPP can be reformulated with the additional constraint as follows, Copt( S) = min x # i ! DS, j ! US Cijxij + # i, j ! US, i< j Cijxij + # i ! US, j ! TS Cijxij ( 3) i. $ j ! US xij = 1 for all i " DS, ii. $ j ! DS xji + $ j ! US, i< j xij + $ j ! US, j< i xji + $ j ! TS xij = 2 for all i " US, iii. $ j ! US xji = 1 for all i " TS, iv. $ i ! DS, j ! US xij + $ i ! US, j ! US, i< j xij + $ i ! US, j ! TS xij =  US +  DS, v. $ { i, j} ! R, i< j xij !  R − 2 for all R # S,  R ! DS = 2, vi. $ { i, j} ! R, i< j xij !  R − 2 for all R # S,  R ! TS = 2, vii. $ { i, j} ! R, i< j xij !  R − 1 for all R # S, viii. xij " { 0, 1} for all i, j " S, i < j. Let the constraints ( i)( iii) be written as A1 Sx = B1S and ( iv)( vii) written as A2 Sx ! B2S . Let P( S) := { x : A1 Sx = B1S , A2 Sx ! B2S , x & 0}. Hence, the MDTHPP can be restated as Copt( S) = min x { CS( x) : x " P( S), x is an integer}. ( 4) where CS( x) := $ i ! DS, j ! US Cijxij + $ i, j ! US, i< j Cijxij + $ i ! US, j ! TS Cijxij . The LP relaxation of this problem is: Clp( S) = min x { CS( x) : x " P( S)}. ( 5) Just as how the 1 tree played an important role in the single TSP, a forest with  DS disjoint trees satisfying the following constraint plays an important role in MDTHPP: Each tree in the forest spans exactly one vertex from DS, exactly one vertex from TS and a subset of vertices from US. An illustration of such a forest with 5 trees is shown in Fig. 2. Let F( S) = { x : A2 Sx ! B2S , x & 0}. The constrained forest problem, denoted by CF, is: Cf ( S) = min x { CS( x) : x " F( S), x is an integer}. ( 6) The MDTHPP is actually CF with the additional degree constraints present in A1 Sx = B1S . Before we present the algorithm, in the next section, we discuss a Lagrangian dual of MDTHPP and its related results that are crucial in proving the approximation results. 5 Starting depot Destination Terminal Fig. 2. An example of a constrained forest with 5 trees. III. Lagrangian dual of MDTHPP Given x, let di( x, S) denote the degree of vertex i in S. That is di( x, S) = $ j ! US xij for all i " DS, di( x, S) = $ j ! DS xji+ $ j ! US, i< j xij+ $ j ! US, j< i xji+ $ j ! TS xij for all i " US, di( x, S) = $ j ! US xji for all i " TS. Let vi( x, S) := di( x, S) − 1 if i " DS " TS and vi( x, S) := di( x, S) − 2 if i " US. By dualizing the constraints in A1 Sx = B1S , we can obtain the Lagrangian dual to the MDTHPP. This Lagrangian dual problem can be formulated as max ! w( ! , S) where w( ! , S) = min x ! F( S), x is an integer [ CS( x) + # i ! DS ! i( di( x, S) − 1) + # i ! US ! i( di( x, S) − 2) + # i ! TS ! i( di( x, S) − 1)], = min x ! F( S), x is an integer [ CS( x) + # i ! S ! ivi( x, S)]. ( 7) Proposition III. 1: The optimal solutions of the problem, minx{ CS( x) : x " F( S)}, are integers. This implies minx{ CS( x) : x " F( S)} = minx{ CS( x) : x " F( S), x is an integer}. Proof: Let ES include all the edges joining any two vertices in S except the edges that join one vertex in DS and one vertex in TS. Let I1 and I2 be two collections of subsets of ES as follows: I1 = { A # ES: Graph ( S, A) is free of cycles and free of paths connecting any pair of vertices in DS}. I2 = { A # ES: Graph ( S, A) is free of cycles and free of paths connecting any pair of vertices in TS}. It is known in the literature ( Cerdeira [ 1], Cordone and Maffioli [ 4]) that M1 = ( ES, I1) and M2 = ( ES, I2) are matroids. Any x is feasible in { x " F( S), x is an integer} if and only if the set of edges corresponding to x is a common independent set of matroids M1 and M2 with  US +  DS elements. Hence CF can be posed as a maximum weighted two matroid intersection problem. Edmonds [ 5] has shown that the set of feasible solutions corresponding to the intersection of two matroid polyhedra has its extremal points as integers. Hence, the integer constraint on the decision variables can be removed in the constrained forest problem. Thus the optimal solutions of the problem, minx{ CS( x) : x " F( S)}, are integers. 6 Proposition III. 2: The Lagrangian dual problem, max ! w( ! , V ), can be solved using the ellipsoid method in polynomial time. Proof: If  UV  =  DV , for any ! , note that solving the constraint forest problem, w( ! , V ), reduces to solving two minimum cost, assignment problems. In this special case, any ! " " R is optimal for max ! w( ! , V ) where R is the set of all real numbers. Therefore, in the remaining part of the proof, we consider the non trivial case, i. e. when  UV  >  DV . The Lagrangian dual problem can also be written as a linear program as follows: max t, ! i t, ( 8) t ! CV ( x) + # i ! ivi( x, V ), ' x " F( V ). If t " , ! " i solves the above linear program so does t " , ( ! " i + " ) for all " " R. Hence, without loss of generality, we can choose one of the variables in { ! i : ' i " V } to be zero. For simplicity, let us choose ! q = 0 for some q " UV . Let P:= { t, ! i, ' i " V \{ q} : t ! CV ( x)+ $ i ! V \{ q} ! ivi( x, V ), ' x " F( V ).}. Also, let to = Cmin/ 6, ! o i = Cmin/ 6 and # o = Cmin/ 6 where Cmin = mini, j ! V Cij ( Note that by assumption Cmin > 0). Consider the ball Bo = { t, ! i :  t − to ! # o,  ! i − ! o i  ! # o, ' i " V \ { q}}. It is easy to check that Bo # P. Without loss of generality, one can assume 0 ! t ! ( n+ k) Cmax. Using lemma VI. 1 proved in the appendix, all the variables in { ! i : ' i " V \ { q}} can be upper bounded by ( 2n + 2k + 1) Cmax and lower bounded by −( n + k) Cmax where Cmax = maxi, j ! V Cij . Now, consider the following separation problem related to the linear program: Given t " Q and ! i " Q, ' i " V \{ q}, decide whether t, ! i " P and if not find a violated constraint. Using proposition III. 1, we know that the above separation problem is solvable in polynomial time. Since all the variables are bounded and Bo # P, one can use the results in Grotschel et. al [ 8] to conclude that the linear program formulated in ( 8) is solvable in polynomial time using the ellipsoid method. Proposition III. 3: For all S # V with  DS =  TS > 0, max ! w( ! , S) = Clp( S) ! Copt( S). ( 9) Proof: Note that Clp( S) ! Copt( S). By proposition III. 1, since the optimal solutions of the problem, minx{ CS( x) : x " F( S)}, are integers, using corollary ( 6.6) in Nemhauser and Wolsey [ 15], it follows that max ! w( ! , S) = Clp( S). IV. Approximation Algorithm for MDTHPP We generate a feasible solution for the MDTHPP using the following algorithm approx: • Solve the lower bound max ! minx ! F( V )[ CV ( x) + $ i ! V ! ivi( x, V )] using the ellipsoid method. Let ( ! " , x " ) be the corresponding optimal solution. x " corresponds to a disjoint forest with k trees such that a depot vertex and a terminal vertex is contained in each tree. Let Pi( x " ) be the set of all vertices present in the ith tree. Note that Pi( x " ) ! Pj( x " ) = ( for i ) = j and " i ! 1, · · · , k Pi( x " ) = V . Let the depot vertex and the terminal vertex present in Pi( x " ) be denoted as ri and ti. We use Hoogeveen’s approximation algorithm [ 11] to construct a path for each i = { 1, · · · , k} as follows: i. Find the minimum spanning tree Ti corresponding to the vertices in Pi( x " ). ii. Find the set of all wrong degree vertices, Wi, in Ti. A vertex has a wrong degree if – it is not a depot or a terminal vertex and its degree is odd. 7 – it is a depot vertex and its degree is even. – it is a terminal vertex and its degree is even. Note that  Wi is always even. iii. Find the minimum cost perfect matching, Mi, on the set Wi. iv. Now consider the graph using the union of edges in Ti and Mi. This graph is connected and has exactly two odd degree vertices. The two odd degree vertices are the depot vertex and the terminal vertex. v. Construct an Eulerian path that traverses each edge exactly once in the resultant graph. The Eulerian path would have the two odd degree vertices as its end points. This construction can be done using the algorithms given in [ 11],[ 16]. vi. Shortcut this Eulerian path to produce a Hamiltonian path starting at depot vertex ri, visiting all the vertices present in Pi( x " ) and ending at the terminal vertex ti. If the triangle inequality is satisfied, the cost of this Hamiltonian path would be less than or equal to the cost of the Eulerian path. The following is the main result of this paper: Theorem IV. 1: Algorithm approx provides a feasible solution for MDTHPP with an approximation ratio of 5 3 when the costs are symmetric and satisfy triangle inequality. V. Proofs The following theorem states that the integrality ratio of the LP relaxation of MDTHPP is at most 5 3 . Combining this result with theorem III. 2 will prove theorem IV. 1. The rest of the section constructs the necessary results to prove this integrality ratio. Theorem V. 1: If the costs satisfy triangle inequality, then Clp( V ) = max ! w( ! , V ) & 3 5 Copt( V ) . The total cost of the generated feasible solution by algorithm approx is upper bounded by # i ! 1, · · · , k ( C( Ti) + C( Mi)), where C( Ti) and C( Mi) represent the total cost of the edges present in Ti and Mi respectively. Proposition V. 1: C( Ti) ! Clp( Pi( x " )). ( 10) Proof: Since Pi( x " ) has only one depot vertex and Ti is the minimum spanning tree corresponding to the vertices in Pi( x " ), we have C( Ti) = minx{ CPi( x ! )( x) : x " F( Pi( x " )), x is an integer}. Due to lemma III. 1, we get C( Ti) = minx{ CPi( x ! )( x) : x " F( Pi( x " ))}. By definition, Clp( Pi( x " )) = minx{ CPi( x ! )( x) : A1 Pi( x ! ) x ! B1P i( x ! ), x " F( Pi( x " ))}. Hence C( Ti) ! Clp( Pi( x " )). Hence, the total cost of the feasible solution is upper bounded by # i ! 1, · · · , k ( Clp( Pi( x " )) + C( Mi)). ( 11) In the following subsections, we show how to bound $ i= 1, · · · , k Clp( Pi( x " )) and the matching cost C( Mi). A. Decomposition of the LP Relaxation Proposition V. 2: Let ( ! " , x " ) solve the problem Clp( V ) = max ! minx ! F( V )[ CV ( x)+ $ i ! V ! ivi( x, V )]. Then, Clp( V ) = # m= 1, · · · , k Clp( Pm( x " )). Proof: Refer to the appendix. 8 B. Bound on the cost of matching Proposition V. 3: Let O be the set of vertices having odd degree in a given forest = ( A, F). Then the forest contains a union of  O/ 2 edge disjoint paths such that 1. Each path starts and ends with an odd degree vertex. 2. The starting or the terminal vertex of any path never appears as a starting or a terminal vertex in any of the other remaining paths. Proof: Consider the forest G # = ( A, F # ) where F # := F. Consider the following algorithm to generate the desired paths: i. Any non trivial tree ( i. e. a tree that consists at least two vertices) in G # contains at least two odd degree vertices with degree equal to 1. Now, select any two odd degree vertices from each non trivial tree in G # . Remove all the edges on the path joining the two selected vertices in each tree. Let the set of all the edges removed be R. ii. Let F # := F # \ R. Consider the new forest G # = ( A, F # ) and re apply the previous step until G # has no edges. After each iteration, note the following: • Each iteration generates at least one path and all the generated paths are edge disjoint. Note that there could be at most  F iterations. • If a vertex is not selected in a iteration, then the parity of its degree remains the same after the removal of the edges during that iteration. • If a vertex having a odd degree was selected during the iteration, then its degree becomes even after the removal of the edges. Hence, a selected odd degree vertex is never considered for selection again in the subsequent iterations. Therefore, the starting or the terminal vertex of any path never appears as a starting or a terminal vertex in any of the other generated paths. • Each odd degree vertex should have been selected by the end of the algorithm because the iteration stops only when F # is empty. Therefore, the number of edge disjoint paths generated must be equal to  O 2 . Proposition V. 4: Let G # = ( A, F) be a forest with O representing the set of odd degree vertices of G # . Let Eo be the set of all edges joining any two vertices in O. Given a complete graph ( O, Eo), let M be a perfect matching on O such that C( M) ! C( M # ) for every other perfect matching M # on O. If the costs satisfy triangle inequality, then C( M) ! C( F). Proof: From proposition V. 3, G # can be decomposed into a set of edge disjoint paths between all the odd vertices in O. One can replace each path by an edge connecting the starting and the terminal vertex of the path. Now, we have a perfect matching M # # on the set O with C( M # # ) ! C( F) since the costs satisfy triangle inequality. But since C( M) ! C( M # # ), the proposition follows. Let A # V with  DA =  TA = 1. Now, consider the SDTHPP on a set of vertices denoted by A that starts at the depot vertex r " A and ends at the terminal vertex t " A . The LP relaxation of this Hamiltonian path problem is Clp( A) = min x CA( x) ( 12) 9 # j ! A\ t xrj = 1 # j ! A\ r xjt = 1 # j ! A, i< j xij + # j ! A, j< i xji = 2 for all i " A\{ r, t} # i ! A, j ! A, i< j xij =  A − 1 # i ! R, j ! R, i< j xij !  R − 1, for all R # A, 0 ! xij ! 1 for all i, j " A, i < j ( 13) The LP relaxation of the single TSP ( Held and Karp [ 10]) on A can be formulated as follows: Ctsp( A) = min x # i ! A, j ! A, i< j Cijxij ( 14) # j ! A, i< j xij + # j ! A, j< i xji = 2 for all i " A # i ! R, j ! R, i< j xij !  R − 1, for all R * A, 0 ! xij ! 1 for all i, j " A, i < j ( 15) Proposition V. 5: Let A # V with  DA =  TA = 1. Consider the minimum spanning tree MST = ( A, T). Let W the set of all wrong degree vertices in MST. Let M be the minimum cost perfect matching on the set of vertices denoted by W. If the costs satisfy triangle inequality, then C( M) ! 2 3 Clp( A). Proof: Note that C( T) ! Clp( A) ( Refer to the argument in proposition V. 1). Remove the set of edges, Ert, lying on the path joining vertices r and t from T. Now, the degree of each vertex of W in the graph ( A, T\ Ert) is odd. From proposition V. 4 the optimal matching M on the set W has a cost C( M) ! C( T\ Ert). Then we get the following inequality: 2Clp( A) & Clp( A) + C( T) = Clp( A) + C( Ert) + C( T\ Ert) & Clp( A) + C( Ert) + C( M). ( 16) Since the costs satisfy triangle inequality, C( Ert) & Crt. Hence, 2Clp( A) & Clp( A) + Crt + C( M). ( 17) 10 Let xh solve LP relaxation of the SDTHPP defined in ( 12). Now construct a solution x such that xij = xh ij ' i, j " A, i < j and xrt = 1. Clearly x is a feasible solution to the LP relaxation of single TSP defined in ( 14). Hence, Ctsp( A) ! Clp( A) + Crt. If M is the minimum cost perfect matching on W, W # A and if the triangle inequality is satisfied, then Shmoys and Williamson [ 22] have shown that 2C( M) ! Ctsp( A). Using these results in equation ( 17), we get, 2Clp( A) & Clp( A) + Crt + C( M) & Ctsp( A) + C( M) & 2C( M) + C( M) = 3C( M). ( 18) C. Proof of the integrality ratio The following steps show that the integrality ratio is at most 5 3 . From equation ( 11), we have Copt( V ) ! # i= 1, · · · , k ( Clp( Pi( x " )) + C( Mi)) ( 19) Using proposition V. 5, we get Copt( V ) ! # i= 1, · · · , k ( Clp( Pi( x " )) + 2 3 Clp( Pi( x " ))). ( 20) Now, we use proposition VI. 1 to get Copt( V ) ! 5 3 Clp( V ). ( 21) This is the 5 3 integrality factor. Combining this result with theorem III. 2 proves the approximation ratio. References [ 1] Cerdeira, J. O., 1994. Matroids and a forest cover problem. Mathematical Programming 66, p. 403 405. [ 2] Chandler, P., Pachter, M., Swaroop, D., Jeffrey, M. F., Howlett, J. K., Rasmussen, S., Schumacher, C., and Nygard, K., Complexity in UAV Cooperative Control, Proceedings of the American Control Conference, Anchorage, AK May 8 10, 2002. [ 3] N. Christofides, Worst case analysis of a new heuristic for the Traveling Salesman Problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA, 1976. [ 4] Cordone, R., Maffioli, F., 2004. On the complexity of graph tree partition problems. Discrete Applied Mathematics 134, p. 51 65. [ 5] Edmonds, J., 1970. Submodular functions, matroids, and certain polyhedra, in: Combinatorial Structures and Their Applications ( Proceedings Calgary International Conference on Combinatorial Structures and Their Applications, Calgary, Alberta, June 1969; R. Guy, H. Hanani, N. Sauer, J. Schonheim, eds.), Gordon and Breach, New York, pp. 6987. [ 6] Fisher, M., 1981. The Lagrangean relaxation method for solving integer programming problems, Management Science 27, 118. [ 7] Geoffrion, A. M., 1974. Lagrangian relaxation for integer programming, Mathematical Programming Study 2, 81114. [ 8] Martin Grtschel, Lszl Lovsz and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1( 2): 169 197 ( 1981) [ 9] GuoXing, Y., 1995. Transformation of multidepot multisalesmen problem to the standard traveling salesman problem. European Journal of Operational Research 81, p. 557 560. [ 10] Held, M., Karp, R. M., 1970. The traveling salesman problem and minimum spanning trees. Operations Research 18, p. 1138 1162. 11 [ 11] Hoogeveen, J. A., 1991. Analysis of christofides’ heuristic: Some paths are more difficult than cycles. Operations Research Letters, 10: 291– 295 [ 12] Kara, I., Bektas, T., 2005. Integer programming formulations of multiple salesmen problems and its variations. European Journal of Operational Research ( available currently at http:// www. crt. umontreal. ca/ tolga/). [ 13] Kulkarni, R. V., Bhave, P. R., 1985. Integer programming formulations of vehicle routing problems. European Journal of Operational Research 20, p. 58 67. [ 14] Lawler, E., Dec 1975. Mathematical Programming, vol 9, Number 1, pp 31 56. [ 15] Nemhauser, G. L., and Wolsey, L., 1988. Integer and Combinatorial Optimization, J. Wiley and Sons. [ 16] Papadimitriou, C. H., Steiglitz, K., 1998. Combinatorial Optimization: Algorithms and Complexity, Dover Publishers. [ 17] M. Lagoudakis, V. Markakis, D. Kempe, P. Keskinocak, S. Koenig, A. Kleywegt, C. Tovey, A. Meyerson and S. Jain, 2005. Auction Based Multi Robot Routing. In Proceedings of the International Conference on Robotics: Science and Systems ( ROBOTICS), pp 343 350. [ 18] Rathinam, S., R. Sengupta and S. Darbha, “ A Resource Allocation Algorithm for Multi Vehicle Systems with Non holonomic Constraints,” Vol. 4, no. 1, pp. 98 104, IEEE Transactions on Automation Sciences and Engineering, January 2007. [ 19] Rathinam, S. and Sengupta, R., 2006. ” Lower and Upper bounds for a Multiple Depot UAV Routing Problem”, IEEE Control and Decision Conference, San Diego, California. [ 20] Malik, W., Rathinam, S. and Darbha, S., Feb 2007. ” An approximation algorithm for a symmetric Generalized Multiple Depot, Multiple Travelling Salesman Problem ”, Accepted in Operations Research Letters. [ 21] Rathinam, S., 2007. Routing and Monitoring algorithms for UAVs, Ph. D thesis, University of California, Berkeley. [ 22] Shmoys, D. B., Williamson, D. P., September 1990. Analyzing the Held Karp TSP bound: a monotonicity property with application. Information Processing Letters, Vol 35 , Issue 6, Pages: 281  285. [ 23] The Travelling Salesman Problem and its Variations, Kluwer Academic Publishers, 2002. [ 24] Wolsey,. L. A. 1980 Heuristic analysis, linear programming and branch and bound. Math. Programming 13, 121 34. VI. Appendix Proposition VI. 1: For any ( ! " , x " ) that solves max ! minx ! F( S)[ CS( x) + $ i ! S ! ivi( x, S)], Clp( V ) = # m= 1, · · · , k Clp( Pm( x " )) Proof: By proposition ( III. 3) and the definition of w( ! , S) in ( 7), Clp( V ) = max ! w( ! , V ) = max ! min x ! F( V ), x is an integer [ CV ( x) + # i ! V ! ivi( x, V )] = max ! min x ! F( V ) [ CV ( x) + # i ! V ! ivi( x, V )]. ( 22) Since x " is a feasible solution for the above optimization problem, the following constraints must be satisfied by x = x " . xij = 0, for alli " Pm( x " ), for all j " Pn( x " ), for all m, n = 1, · · · , k and m ) = n, # i ! Pm( x ! ), j ! Pm( x ! ), i< j xij =  Pm( x " ) − 1, m = 1, · · · , k, # i ! R, j ! R, i< j xij !  R − 1, for all R # Pm( x " ), m = 1, · · · , k, xij & 0, for all i, j " Pm( x " ), i < j, m = 1, · · · , k. ( 23) Let all the above additional constraints in ( 23) be denoted by Acx ! Bc. Observe that adding these constraints pertaining to the optimal solution, x " , to the constraints present in F( V ) will not the change the optimal cost Clp( V ). Let F " ( V ) = { x : x " F( V ) and Acx ! Bc}. Now, continuing with 12 the definition of Clp( V ), we get, Clp( V ) = max ! min x ! F ! ( V ) [ CV ( x) + # i ! V ! ivi( x, V )]. ( 24) To prove the proposition, we are further going to simplify the objective function and the set of feasible solutions. Since for all i " Pm( x " ), j " Pn( x " ), m, n " { 1, · · · , k}, m ) = n, xij = 0 in x " F " ( V ), equation ( 24) can be written as Clp( V ) = max ! min x ! F ! ( V ) # m= 1, · · · , k [ CPm( x ! )( x) + # i ! Pm( x ! ) ! ivi( x, Pm( x " ))]. ( 25) Let F1 × F2 denote the cartesian product of two sets F1 and F2. Then, x " F " ( V ) if and only if ( x1, x2, · · · , xk) " × k m= 1F( Pm( x " )) where for all i, j " Pm( x " ), i < j, each xm := xij . Hence, equation ( 25) can be further simplified as follows: Clp( V ) = max ! min ( x1, · · · , xk) ! × k m= 1F( Pm( x ! )) # m= 1, · · · , k [ CPm( x ! )( xm) + # i ! Pm( x ! ) ! ivi( xm, Pm( x " ))]. ( 26) This breaks the inner minimization into k independent minimization problems implying Clp( V ) = max ! # m= 1, · · · , k min xm ! F( Pm( x ! )) [ CPm( x ! )( xm) + # i ! Pm( x ! ) ! ivi( xm, Pm( x " ))]. ( 27) Applying the same reasoning to the maximization problem we get Clp( V ) = # m= 1, · · · , k max ! i, i ! Pm( x ! ) min xm ! F( Pm( x ! )) [ CPm( x ! )( xm) + # i ! Pm( x ! ) ! ivi( xm, Pm( x " ))]. ( 28) Using proposition III. 3 with S = Pm( x " ), m = 1, · · · , k, we get, Clp( V ) = # m= 1, · · · , k Clp( Pm( x " )). ( 29) Lemma VI. 1: Let  UV  >  DV , t & 0 and ! q = 0 for some q " UV . For all s " { ! i : ' i " V \{ q}}, without loss of generality, we can assume −( n + k) Cmax ! ! s ! ( 2n + 2k + 1) Cmax where Cmax = maxi, j ! V Cij . 13 Proof: Since  UV  >  DV , one can always choose a forest, xf " F( V ), such that vs( xf , V ) = 1, vq( xf , V ) = − 1 and vi( xf , V ) = 0, ' i " V \ { s, q}. Therefore, we have, t ! CV ( xf ) + ! s − ! q. ( 30) Since t & 0 and CV ( xf ) ! ( n + k) Cmax, ! s & t − CV ( xf ) & −( n + k) Cmax. ( 31) The above equation can be used to lower bound all the variables. To upper bound the variables, we need to consider two cases, i. e. when s is a destination vertex and when s is a depot vertex. Case 1 s is a destination vertex: Similar to the lower bounding argument, one can choose a forest, x # f " F( V ), such that vs( x # f , V ) = − 1, vq( x # f , V ) = 1 and vi( x # f , V ) = 0, ' i " V \ { s, q}. Therefore, we have, t ! CV ( x # f ) + ! q − ! s. Since t & 0 and ! q = 0, it follows that ! s ! CV ( x # f ) − t ! ( n + k) Cmax. ( 32) Case 2 s is a depot vertex: The modified cost of any edge ( Cij + ! i + ! j) joining two destinations i and j, by equation ( 32), is upper bounded by ( 2n+ 2k + 1) Cmax. If ! s & ( 2n+ 2k + 1) Cmax, the degree of the depot vertex ( s) in the optimal solution to the Lagrangian dual problem must be one. Therefore if ! s = ( 2n+ 2k+ 1) Cmax is optimal for the Lagrangian dual problem, so is ! s = ( 2n + 2k + 1) Cmax + " for any " & 0. Hence without any loss of generality, we can upper bound ! s by ( 2n + 2k + 1) Cmax. 
PDI.Title  5/3approximation algorithm for a multiple depot, terminal Hamiltonian path problem / 



B 

C 

I 

S 


