liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.ORCID-id: 0000-0003-1836-4200
Linköpings universitet, Institutionen för datavetenskap, Artificiell intelligens och integrerade datorsystem. Linköpings universitet, Tekniska högskolan.
Linköpings universitet, Institutionen för datavetenskap, Artificiell intelligens och integrerade datorsystem. Linköpings universitet, Tekniska högskolan.ORCID-id: 0000-0002-5500-8494
2014 (Engelska)Ingår i: Examining Robustness and Vulnerability of Networked Systems / [ed] Butenko, S., Pasiliao, E.L., Shylo, V., IOS Press, 2014, s. 26-50Konferensbidrag, Publicerat paper (Refereegranskat)
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 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.

Ort, förlag, år, upplaga, sidor
IOS Press, 2014. s. 26-50
Serie
NATO Science for Peace and Security Series - D: Information and Communication Security, ISSN 1874-6268, E-ISSN 1879-8292 ; 37
Nyckelord [en]
Steiner trees, hop constraints, local search heuristics, label correcting algorithms, unmanned vehicles placement
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:liu:diva-110008DOI: 10.3233/978-1-61499-391-9-26ISI: 000452122700003ISBN: 978-1-61499-390-2 (tryckt)ISBN: 978-1-61499-391-9 (digital)OAI: oai:DiVA.org:liu-110008DiVA, id: diva2:742139
Konferens
NATO Advanced Research Workshop (ARW), Examining Robustness and Vulnerability of Critical Infrastructure Networks, Kiev, Ukraine, June 2013
Projekt
CADICSELLIITCUASSHERPANFFP6 KISATillgänglig från: 2014-08-31 Skapad: 2014-08-29 Senast uppdaterad: 2020-06-29Bibliografiskt granskad

Open Access i DiVA

Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance(1337 kB)646 nedladdningar
Filinformation
Filnamn FULLTEXT03.pdfFilstorlek 1337 kBChecksumma SHA-512
d95ddfa56f2a5ee49f354579bd6d2d5e3f088282e418d642f2420bea0efdd2fe2a699387d116248461a9967416b70a155d654334dbf38cc88e9360977480730f
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextFind book in another country/Hitta boken i ett annat land

Person

Burdakov, OlegDoherty, PatrickKvarnström, Jonas

Sök vidare i DiVA

Av författaren/redaktören
Burdakov, OlegDoherty, PatrickKvarnström, Jonas
Av organisationen
OptimeringsläraTekniska högskolanArtificiell intelligens och integrerade datorsystem
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 647 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 555 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf