liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance
2014 (English)Report (Other academic)
Abstract [en]

We consider the directed Steiner tree problem (DSTP) with a constraint on the total number of arcs (hops) in the tree. This problem is known to be NP-hard, and therefore, only heuristics can be applied in the case of its large-scale instances.   For the hop-constrained DSTP, we propose local search strategies aimed at improving any heuristically produced initial Steiner tree. They are based on solving a sequence of hop-constrained shortest path problems for which we have recently developed ecient label correcting algorithms.   The presented approach is applied to nding suitable 3D locations where unmanned aerial vehicles (UAVs) can be placed to relay information gathered in multi-target monitoring and surveillance. The eciency of our algorithms is illustrated by results of numerical experiments involving problem instances with up to 40 000 nodes and up to 20 million arcs.

Place, publisher, year, pages
Linköping University Electronic Press, 2014. , 25 p.
LiTH-MAT-R, ISSN 0348-2960 ; 2014:10
Keyword [en]
Steiner trees, hop constraints, local search heuristics, label correcting algorithms, unmanned vehicles placement
National Category
Discrete Mathematics Computer Vision and Robotics (Autonomous Systems)
URN: urn:nbn:se:liu:diva-109605ISRN: LiTH-MAT-R--2014/10--SEOAI: diva2:739485
Available from2014-08-21 Created:2014-08-21 Last updated:2014-09-04

Open Access in DiVA

fulltext(2224 kB)45 downloads
File information
File name FULLTEXT03.pdfFile size 2224 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Burdakov, OlegDoherty, PatrickKvarnström, Jonas
By organisation
Optimization The Institute of TechnologyArtificial Intelligence and Intergrated Computer systems
Discrete MathematicsComputer Vision and Robotics (Autonomous Systems)

Search outside of DiVA

GoogleGoogle Scholar
Total: 50 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 44 hits
ReferencesLink to record
Permanent link

Direct link