LiU Electronic Press
Download:
File size:
2224 kb
Format:
application/pdf
Author:
Burdakov, Oleg (Linköping University, Department of Mathematics, Optimization ) (Linköping University, The Institute of Technology)
Doherty, Patrick (Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems) (Linköping University, The Institute of Technology)
Kvarnström, Jonas (Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems) (Linköping University, The Institute of Technology)
Title:
Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance
Department:
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems
Linköping University, Department of Mathematics, Optimization
Linköping University, The Institute of Technology
Publication type:
Report (Other academic)
Language:
English
Publisher: Linköping University Electronic Press
Pages:
25
Series:
LiTH-MAT-R, ISSN 0348-2960; 2014:10
Year of publ.:
2014
URI:
urn:nbn:se:liu:diva-109605
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-109605
ISRN:
LiTH-MAT-R--2014/10--SE
Subject category:
Discrete Mathematics
Computer Vision and Robotics (Autonomous Systems)
Keywords(en) :
Steiner trees, hop constraints, local search heuristics, label correcting algorithms, unmanned vehicles placement
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.

Available from:
2014-08-21
Created:
2014-08-21
Last updated:
2014-09-04
Statistics:
7 hits
FILE INFORMATION
File size:
2224 kb
Mimetype:
application/pdf
Type:
fulltext
Statistics:
0 hits