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 Hamil-tonian
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 Applica-tions
( 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. Euro-pean
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.