LiU Electronic Press
Full-text not available in DiVA
Author:
Burdakov, Oleg (Linköping University, Department of Mathematics, Optimization ) (Linköping University, The Institute of Technology)
Holmberg, Kaj (Linköping University, Department of Mathematics, Optimization ) (Linköping University, The Institute of Technology)
Olsson, Per-Magnus (Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab) (Linköping University, The Institute of Technology)
Title:
A Dual Ascent Method for the Hop-constrained Shortest Path with Application to Positioning of Unmanned Aerial Vehicles
Department:
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab
Linköping University, Department of Mathematics, Optimization
Linköping University, The Institute of Technology
Publication type:
Report (Other academic)
Language:
English
Place of publ.: Linköping Publisher: Linköping University Electronic Press
Distributor:
Matematiska institutionen
Pages:
30
Series:
Report / Department of Mathematics, Universitetet i Linköping, Tekniska högskolan, ISSN 0348-2960; 2008:7
Year of publ.:
2008
URI:
urn:nbn:se:liu:diva-14997
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-14997
Local ID:
LiTH-MAT-R-2008-07
Subject category:
Mathematics
SVEP category:
MATHEMATICS
Keywords(en) :
Hop-constrained, shortest path, dual ascent, visibility graph, UAV, relay
Abstract(en) :

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.

Available from:
2008-10-07
Created:
2008-10-07
Last updated:
2013-08-29
Statistics:
454 hits