|
Description:
|
Unmanned aerial vehicles (UAVs ) are becoming increasingly popular for surveillance
in civil and military applications . Vehicles built for this purpose vary in their
sensing capabilities , speed and maneuverability . It is therefore natural to assume
that a team of UAVs given the mission of visiting a set of targets would include
vehicles with differing capabilities . This paper addresses the problem of assigning
each vehicle a sequence of targets to visit such that the mission is completed with
the least "cost" possible given that the team of vehicles is heterogeneous . In order
to simplify the problem the capabilities of each vehicle are modeled as cost to travel
from one target to another . In other words , if a vehicle is particularly suited to visit
a certain target , the cost for that vehicle to visit that target is low compared to
the other vehicles in the team . After applying this simplification , the problem can be
posed as an instance of the combinatorial problem called the Heterogeneous Travelling
Salesman Problem (HTSP ) . This paper presents a transformation of a Heterogenous ,
Multiple Depot , Multiple Traveling Salesman Problem (HMDMTSP ) into a single ,
Asymmetric , Traveling Salesman Problem (ATSP ) . As a result , algorithms available
for the single salesman problem can be used to solve the HMDMTSP . To show the
effectiveness of the transformation , the well known Lin -Kernighan -Helsgaun heuristic
was applied to the transformed ATSP . Computational results show that good quality
solutions can be obtained for the HMDMTSP relatively fast .
Additional complications to the sequencing problem come in the form of precedence
constraints which prescribe a partial order in which nodes must be visited . In this context the sequencing problem was studied seperately using the Linear Program
(LP ) relaxation of a Mixed Integer Linear Program (MILP ) formulation of the
combinatorial problem known as the "Precedence Constrained Asymmetric Travelling
Salesman Problem" (PCATSP ) . |