Page 157 - Innovations in Intelligent Machines

Algorithms for Routing Problems Involving UAVs 149
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 . Costs
are symmetric, that is, c ij = c ji . A tour of the UAV is an ordered set of
,l =1,...,n
n + 2 elements of the form {V 1 ,V i 1 ,...,V i n ,V 1 }, where V i l
corresponds to n distinct destinations being visited in that sequence. The
overall cost, C(TOUR), associated with the tour of the UAV is defined as
n−1
+ + c i n ,1 . Given the graph G =(V, E), the
k=1
C(TOUR)= c 1,i 1 c i k ,i k+1
single vehicle problem (SVP) is to find a tour for the UAV that minimizes
the overall cost.
2.2 Relevant Literature

The formulated problem is essentially the single Travelling Salesman Problem
(TSP) as referred to in the operations research literature. For a general cost
function (i.e. c ij ), it has been proved that there exists no algorithm with
a constant approximation factor unless P=NP [1]. An approximation factor
β(P, A) of using an algorithm A to solve the problem P (objective is minimize
some cost function) is defined as
C(I, A)
β(P, A)=sup( ), (1)
I C o (I)
where I is a problem instance, C(I, A) is the cost of the solution by apply-
ing algorithm A to the instance I and C o (I) is the cost of the optimal solution
of I. In simple terms, the algorithm A produces an approximate solution to
every instance I of the problem P, whose cost is within β(P, A) times the
optimal solution of I. Constant factor approximation algorithms are useful in
the sense that they give an upper bound to the cost of the resulting solution
that is independent of the size of the problem. If the cost function satisfies tri-
angle inequality and is symmetric, constant factor approximation algorithms
are available. If i, j, k denote the destinations to be visited then satisfying
triangle inequality means that c ij ≤ c ik + c kj . The following are the two main
approximation algorithms available for the single TSP:
• 2 approximation algorithm [2].
• 1.5 approximation algorithm by Christofides [3].
When the destinations lie on a Euclidean plane, the cost function has
additional properties that was exploited by Arora in [4]. Given any > 0,
Arora’s algorithm finds a solution with an approximation factor of 1 + in
1
time n O( )
.
As far as the lower bounds are concerned, Held and Karp’s result [5], [6]
is the best known result for the TSP. An advantage of deriving good lower
bounds is that they can be incorporated in branch and bound solvers used
to solve the TSP to obtain faster results. Also, if one can find lower bounds