Page 163 - Innovations in Intelligent Machines

Algorithms for Routing Problems Involving UAVs 155
where Q is the set of all 1-trees in V . Therefore, for any given vector π,

min c ij + π i (d iy − 2) ≤ min c ij . (3)
y∈Q x∈T
{i,j}∈y i∈V {i,j}∈x
Since the above equation is true for any π, we get the following result:

Theorem 3.

max min c ij + π i (d iy − 2) ≤ min c ij . (4)
π y∈Q x∈T
{i,j}∈y i∈V {i,j}∈x
The left hand side in the above result provides a lower bound to the SVP.
c

{i,j}∈y ij + π i (d iy −2). For any fixed π, calculating
Let w(π) = min y∈Q i∈V
w(π) is that of finding an optimal 1-tree. An optimal 1-tree can be easily solved
using the Prim’s algorithm [2]. Note that the function w(π) is concave in π.
This lends itself to a gradient ascent algorithm that produces a sequence of
lower bounds to the SVP as discussed in [5],[6].

3 Multiple Vehicle Resource Allocation Problems
in the Absence of Kinematic Constraints

The resource allocation problems considered in this section involves multiple
UAV’s where vehicles could start from a single depot or from multiple depots.
The general problem discussed in this section is as follows: Given a set of
UAVs and destinations, find tours for each UAV such that (1) each destination
is visited once by only one UAV (2) the sum of the tour cost of all the UAVs
is minimum. As mentioned in the introduction, there are several variants of
this multiple vehicle problem. In this section, we present three such variants
and discuss approaches to solve them. To avoid using redundant variables in
the problem formulation, each variant is formulated separately under each
subsection.

3.1 Literature Review

The Multiple Travelling Salesmen Problem (MTSP) has two distinct cases -
one case where all vehicles start at a root vertex (referred to as Single Depot
MTSP) and an other where vehicles may start at different locations (referred
to as Multiple Depot MTSP). Please refer to the recent paper by Bektas [8]
for an extensive review of MTSP’s. Bellmore and Hong [9] consider a Single
Depot MTSP where each vehicle is available for service at a specific cost and
the edge costs need not satisfy triangle inequality. Since the objective is to
reduce the total cost travelled by the vehicles, there could be situations when
the optimal solution will not necessitate using all the vehicles. Bellmore and