Page 169 - Innovations in Intelligent Machines

Algorithms for Routing Problems Involving UAVs 161

UAV starting
location
Destination
terminal location

Fig. 14. Step 3 of algorithm CF for MDMTSP: Construct a path out of each
Eulerian graph

vertices V 1 ,...,V m representing the UAVs (i.e., the vertex V i corresponds to
the i th UAV) and V m+1 ,...,V m+n representing the destinations. Let E =
V × V denote the set of all edges (pairs of vertices) and let c : E → +
denote the cost function with c(V i ,V j ) (or simply, c ij ) representing the cost of
travelling from vertex V i to vertex V j . We consider costs that are symmetric,
i.e. c ij = c ji and satisfy triangle inequality. A tour is an ordered set, TOUR i ,
,V i }, where
of at least r +2,r ≥ 1 elements of the form {V i ,V i 1 ,...,V i r
,l =1,...,r corresponds to r distinct destinations being visited in that
V i l
sequence by the i th UAV. There is a cost, C(TOUR i ), associated with a tour
for the i th UAV and is defined as C(TOUR i )= c i,i 1 + r−1 c + c i r ,i .
k=1 i k ,i k+1
If S p is the set of p vehicles chosen to visit the destinations, the overall cost
is defined as C(TOUR i ). Given the graph G =(V, E), and a number
i∈S p
p ≤ m, choose at most p UAVs so that each destination is visited by at least
one UAV and the overall cost is a minimum among all possible choice of p or
fewer UAVs and their corresponding tours.

Approximation Algorithm for GMTSP

The approximation algorithm CT [13] that solves the GMTSP is given as
follows:
˜
1. Construct a graph G as follows: Add a new vertex (called as the root)
denoted by r. Connect r to all the vertices denoting the UAVs through zero