We study the problem of planning tours for an Unmanned Aerial Vehicle (UAV)
to visit a given set of sites in the least amount of time. This is the classic
Traveling Salesperson Problem (TSP). UAVs have limited battery life and as a
result may not be able to visit all the points on a single charge. We envision
scenarios where the UAVs can be recharged along the way either by landing on
stationary recharging stations or on Unmanned Ground Vehicles (UGVs) acting as
mobile recharging stations. We present an algorithm to find the optimal tours
to determine not only the order in which to visit the sites but also when and
where to land on the UGV to recharge. Our algorithm plans tours for the UGVs as
well as determines best locations to place stationary charging stations. While
the problem we study is NP-Hard, we present a practical solution using
Generalized TSP that finds the optimal solution (albeit in possibly exponential
worst-case running time). Our simulation results show that the running time is
acceptable for reasonably sized instances in practice. We also show how to
modify our algorithms to plan for package delivery with UAVs using UGVs as
mobile warehouses.
%0 Generic
%1 Yu2017Algorithms
%A Yu, Kevin
%A Budhiraja, Ashish K.
%A Tokekar, Pratap
%D 2017
%K statistics
%T Algorithms for Routing of Unmanned Aerial Vehicles with Mobile Recharging Stations and for Package Delivery
%U http://arxiv.org/abs/1704.00079
%X We study the problem of planning tours for an Unmanned Aerial Vehicle (UAV)
to visit a given set of sites in the least amount of time. This is the classic
Traveling Salesperson Problem (TSP). UAVs have limited battery life and as a
result may not be able to visit all the points on a single charge. We envision
scenarios where the UAVs can be recharged along the way either by landing on
stationary recharging stations or on Unmanned Ground Vehicles (UGVs) acting as
mobile recharging stations. We present an algorithm to find the optimal tours
to determine not only the order in which to visit the sites but also when and
where to land on the UGV to recharge. Our algorithm plans tours for the UGVs as
well as determines best locations to place stationary charging stations. While
the problem we study is NP-Hard, we present a practical solution using
Generalized TSP that finds the optimal solution (albeit in possibly exponential
worst-case running time). Our simulation results show that the running time is
acceptable for reasonably sized instances in practice. We also show how to
modify our algorithms to plan for package delivery with UAVs using UGVs as
mobile warehouses.
@misc{Yu2017Algorithms,
abstract = {{We study the problem of planning tours for an Unmanned Aerial Vehicle (UAV)
to visit a given set of sites in the least amount of time. This is the classic
Traveling Salesperson Problem (TSP). UAVs have limited battery life and as a
result may not be able to visit all the points on a single charge. We envision
scenarios where the UAVs can be recharged along the way either by landing on
stationary recharging stations or on Unmanned Ground Vehicles (UGVs) acting as
mobile recharging stations. We present an algorithm to find the optimal tours
to determine not only the order in which to visit the sites but also when and
where to land on the UGV to recharge. Our algorithm plans tours for the UGVs as
well as determines best locations to place stationary charging stations. While
the problem we study is NP-Hard, we present a practical solution using
Generalized TSP that finds the optimal solution (albeit in possibly exponential
worst-case running time). Our simulation results show that the running time is
acceptable for reasonably sized instances in practice. We also show how to
modify our algorithms to plan for package delivery with UAVs using UGVs as
mobile warehouses.}},
added-at = {2019-02-23T22:09:48.000+0100},
archiveprefix = {arXiv},
author = {Yu, Kevin and Budhiraja, Ashish K. and Tokekar, Pratap},
biburl = {https://www.bibsonomy.org/bibtex/2e5c229fdc78b8836ba520c132cd17334/cmcneile},
citeulike-article-id = {14331670},
citeulike-linkout-0 = {http://arxiv.org/abs/1704.00079},
citeulike-linkout-1 = {http://arxiv.org/pdf/1704.00079},
day = 31,
eprint = {1704.00079},
interhash = {d31cc1283bcaaef6a7a41ae86efae2ab},
intrahash = {e5c229fdc78b8836ba520c132cd17334},
keywords = {statistics},
month = mar,
posted-at = {2017-04-04 10:09:27},
priority = {2},
timestamp = {2019-02-23T22:15:27.000+0100},
title = {{Algorithms for Routing of Unmanned Aerial Vehicles with Mobile Recharging Stations and for Package Delivery}},
url = {http://arxiv.org/abs/1704.00079},
year = 2017
}