Page 167 - Innovations in Intelligent Machines

Algorithms for Routing Problems Involving UAVs 159
V i to vertex V j . We consider costs that are symmetric and satisfy triangle
inequality. A path is an ordered set, PATH i ,ofatleast r +2,r ≥ 1ele-
,l =1,...,r corresponds
ments of the form {V i ,V i 1 ,...,V i r ,V i f }, where V i l
to r distinct destinations being visited in that sequence by the i th UAV and
is a terminal location. Any two paths PATH i and PATH j are such that
V i f

PATH i PATH j = Φ. There is a cost, C(PATH i ), associated with a path
for the i th UAV and is defined as C(PATH i )= c i,i 1 + r−1 c + c i r ,i f .
k=1 i k ,i k+1
Let each UAV be allowed to choose any one of the given terminal locations
present in V m+n+1 ,...,V 2m+n not visited by other UAVs. Given the graph
G =(V, E), find m UAV paths such that each destination is visited by only
m
one UAV and the overall cost defined as C(PATH i ) is minimum.
i=1
Approximation Algorithm for MDMTSP

Before, we present the approximation algorithm we give the definition of a
constrained forest as discussed in [12]. A constrained forest is a subgraph of
G with m disjoint trees such that each tree spans exactly one vertex from
{V 1 ,...,V m }, exactly one vertex from {V m+n+1 ,...,V 2m+n } and a subset of
vertices from {V m+1 ,...,V m+n }. (i.e. each tree must consist of exactly one
starting vertex and one terminal vertex). The approximation algorithm CF
[12] that solves the MDMTSP is as follows:

1. Find the minimum cost constrained forest. The output of this step for an
example with five vehicles is shown in Fig. 12.

2. For each tree corresponding to a vehicle, double its edges to construct its
Eulerian graph (Fig. 13).
3. Then construct a path for each vehicle based on its Eulerian graph
(Fig. 14). This step essentially uses the same algorithm implemented for
the tour computation in the single TSP (section 2.3).

The following theorem in [12] shows algorithm CF has an approximation
factor of 2.
Theorem 5. The algorithm CF solves the MDMTSP with an approximation
6
factor of 2 in O((n +2m) ) steps when the costs are symmetric and satisfy
triangle inequality.

3.4 Generalized Multiple Depot Multiple TSP (GMTSP)

Problem Formulation
Let there be n destinations and m UAVs. Let V be the set of vertices that
correspond to the location of UAVs and the destinations, with the first m