Page 162 - Innovations in Intelligent Machines

154 S. Rathinam and R. Sengupta

UAV
destination

Fig. 8. Find an Eulerian walk

UAV
destination

Fig. 9. Find a tour from the Eulerian walk

where as, the optimal solution of the minimum cost 1-tree may change. π i can
be treated as weights on each vertex i ∈ V . The reason why the optimal solu-
tion for a SVP doesn’t change is because for any tour x, (c ij +π i +π j )
{i,j}∈x
c
= {i,j}∈x ij +2 i∈V π i . Therefore, arg min x { {i,j}∈x (c ij + π i + π j ):

c
x∈T}=arg min x { {i,j}∈x ij : x ∈ T}, where T is the set of all tours in V .But

c
if y denotes a 1-tree, then, (c ij +π i +π j )= {i,j}∈y ij + π i d iy ,
{i,j}∈y i∈V
where d iy is the degree of vertex i in y. Hence, the additional cost added
depends on the degree of each vertex in the 1-tree. Using the fact that every
tour is a 1-tree, we have,

min c ij + π i d iy ≤ min c ij +2 π i , (2)
y∈Q x∈T
{i,j}∈y i∈V {i,j}∈x i∈V