Burdakov, Oleg Holmberg, Kaj Olsson, Per-Magnus 2008 (English)Rapport (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, 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:nbn:se:liu:diva-14997 (URN)LiTH-MAT-R-2008-07 (Local ID)oai:DiVA.org:liu-14996 (OAI)