Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance
2014 (English)In: Examining Robustness and Vulnerability of Networked Systems / [ed] Butenko, S., Pasiliao, E.L., Shylo, V., IOS Press, 2014, 26-50 p.Chapter in book (Refereed)
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 efficient label correcting algorithms.The presented approach is applied to finding suitable 3D locations where unmanned aerial vehicles (UAVs) can be placed to relay information gathered in multi-target monitoring and surveillance. The efficiency 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, edition, pages
IOS Press, 2014. 26-50 p.
, NATO Science for Peace and Security Series - D: Information and Communication Security, ISSN 1874-6268 (print), 1879-8292 (online) ; Volume 37
Steiner trees, hop constraints, local search heuristics, label correcting algorithms, unmanned vehicles placement
IdentifiersURN: urn:nbn:se:liu:diva-110008DOI: 10.3233/978-1-61499-391-9-26ISBN: 978-1-61499-390-2 (print)ISBN: 978-1-61499-391-9 (online)OAI: oai:DiVA.org:liu-110008DiVA: diva2:742139