Page 165 - Innovations in Intelligent Machines

Algorithms for Routing Problems Involving UAVs 157

The basic idea is to construct a new graph G =(V ,E ) and the corres-
ponding cost function such that finding a single optimal tour on graph G
is equivalent to solving the SDTSP.Graph G =(V ,E ) is constructed as

follows:
• Add additional m−1 vertices to V represented by V −1 ,V −2 ...V −(m−1) .The

new set of vertices V := V {V −1 ,V −2 ...V −(m−1) }.

• E contains
1. every edge present in E.
2. an edge (V −i ,V j )if(V 0 ,V j )ispresentin E, ∀i ∈{1, 2..(m − 1)} and
∀j ∈{1..n}.
3. an edge (V −i ,V −(i−1) ), ∀i ∈{1..(m − 1)}.

• The new cost function c : E → + is defined as follows:
1. c (V i ,V j )= c(V i ,V j ), ∀i = {1, 2..n}, ∀j = {1, 2..n} and edge

(V i ,V j ) ∈ E.
1
2. c (V −i ,V j )= c(V 0 ,V j )+ C i , ∀i = {0, 1,..(m − 1)}, ∀j = {1, 2..n} and

2
edge (V 0 ,V j ) ∈ E.
1
3. c (V −i ,V −i+1 )= (C i−1 − C i ), ∀i ∈{1..(m − 1)}.

2
An example of this transformation is shown in Fig. 10 and Fig. 11. The
main result in Rao [10] that helps us solve the SDTSP is stated in the fol-
lowing theorem.
Theorem 4. Solving the SDTSP on graph G is equivalent to solving a single

TSP on the transformed graph G .
V 5
c 56
c 45
V 4
V 6
c 34 c 04
V 3 c 06

c 23 V 0
depot
c 01
V 2 c 12 destination

V 1
Fig. 10. An example of a graph G with 3 vehicles present at the depot