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).
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2009-05-762 |
| Date | 16 January 2010 |
| Creators | Oberlin, Paul V. |
| Contributors | Darbha, Swaroop |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Thesis |
| Format | application/pdf |
Page generated in 0.002 seconds