A Dual Ascent Method for the Hop-constrained Shortest Path with Application to Positioning of Unmanned Aerial Vehicles
2008 (English)Report (Other academic)
We study the problem of positioning unmanned aerial vehicles (UAVs) to maintain an unobstructed flow of communication from a surveying UAV to some base station through the use of multiple relay UAVs. This problem can be modeled as a hopconstrained shortest path problem in a large visibility graph. We propose a dual ascent method for solving this problem, optionally within a branch-and-bound framework. Computational tests show that realistic problems can be solved in a reasonably short time, and that the proposed method is faster than the classical dynamic programming approach.
Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2008. , 30 p.
Report / Department of Mathematics, Universitetet i Linköping, Tekniska högskolan, ISSN 0348-2960 ; 2008:7
Hop-constrained, shortest path, dual ascent, visibility graph, UAV, relay
IdentifiersURN: urn:nbn:se:liu:diva-14997Local ID: LiTH-MAT-R-2008-07OAI: oai:DiVA.org:liu-14996DiVA: diva2:37550