Page 164 - Innovations in Intelligent Machines

156 S. Rathinam and R. Sengupta
Hong [9] provide a way of transforming this single depot MTSP to a standard
TSP for the asymmetric case and Rao [10] discuss the symmetric version of
the same problem. GuoXing [11] also provides a transformation of a variant
of an asymmetric, Multiple Depot MTSP to an Asymmetric TSP, wherein
most applicable literature for the standard asymmetric TSP can be put to
good use. Recently, Rathinam et al. [12] provided a 2−approx algorithm for
Multiple Depot MTSP when the edge costs are symmetric and satisfy triangle
inequality. In their work, each vehicle start and end at different locations.
Also, Darbha [13] discuss a generalized version of the multiple depot MTSP’s
where there is an upper bound on the number of vehicles that can be used.
The following subsections discuss three variants of the multiple vehicle TSP
presented in Rao [10], Rathinam et al. [12] and Darbha [13].

3.2 Single Depot, Multiple TSP(SDTSP)

Problem Formulation

Let there be n destinations and m UAVs. V consists of the vertex V 0 repre-
senting the depot along with vertices V 1 ,...,V n that represent the destina-
tions. There are m UAV’s, u 0 ,u 1 ...u m−1 , present in the depot (vertex V 0 ).
Let E = V × V denote the set of all edges (pairs of vertices). A edge join-
ing vertices V i and V j is represented as (V i ,V j ). Each edge (V i ,V j )hasa
cost denoted by c(V i ,V j ) (or simply, c ij ). A tour is an ordered set, TOUR i ,
,V 0 }, where
of at least r +2,r ≥ 1 elements of the form {V 0 ,V i 1 ,...,V i r
,l =1,...,r corresponds to r distinct destinations being visited in that
V i l
sequence by UAV u i . There is a cost, C(TOUR i ), associated with a tour for
r−1
+ c + c i r ,0 . Also,
k=1 i k ,i k+1
the UAV u i and is defined as C(TOUR i )= c 0,i 1
there is a fixed price C i of using the UAV u i . Without loss of generality, we
assume that C 0 ≤ C 1 ... ≤ C m−1 .If S p is the set of p UAVs chosen to visit

the destinations, the overall cost is defined as [C(TOUR i )+ C i ]. Given
i∈S p
the graph G =(V, E) the problem is to choose p (1 ≤ p ≤ m) vehicles so that
each destination is visited by only one UAV and the overall cost is a minimum
among all possible choices of p and their corresponding tours.
Transformation of SDTSP to a Single TSP

Rao [10] presents an approach to solve SDTSP by transforming SDTSP to
an equivalent single TSP. By doing this, most of the available heuristics for
the single TSP can be used to get solutions for the SDTSP. It turns out in
practice, this method of transforming the given SDTSP to a single TSP does
not yield good results as the number of the vehicles increases [14]. Neverthe-
less, this approach gives an insight as to how multiple vehicle problems can
be dealt with.