Publications

Detailed Information

Optimal search-relocation trade-off in Markovian-target searching

Cited 21 time in Web of Science Cited 26 time in Scopus
Authors

Hong, Sung-Pil; Cho, Sung-Jin; Park, Myoung-Ju; Lee, Moon-Gul

Issue Date
2009-06-01
Publisher
PERGAMON-ELSEVIER SCIENCE LTD
Citation
COMPUTERS & OPERATIONS RESEARCH; Vol.36 6; 2097-2104
Keywords
OptimizationNetworks and graphsProbabilitySearch
Abstract
In this study, a standard moving-target search model was extended with a multiple-search-speed option, whereby a trade-off is enabled between the increased detection chances owing to the searcher''''''''s better location and the increased uncertainty of the target''''''''s location resulting from the diminished search performance incurred in the relocation. This enhances the detection probability of the output search path and, thereby, the model''''''''s practicality. However, the scalability of the solution method is essential to its implementation, as the basic model is already NP-hard. We developed an efficient heuristic by combining the idea of approximate nondetection probability minimization and a hybridized shortest-path heuristic that exploits the fast-mixing property of the Markov chain. According to the results of an intensive experiment, the heuristic achieves a near-optimal trade-off within a very reasonable computation time. (C) 2008 Elsevier Ltd. All rights reserved.
ISSN
0305-0548
Language
English
URI
https://hdl.handle.net/10371/75336
DOI
https://doi.org/10.1016/j.cor.2008.07.007
Files in This Item:
There are no files associated with this item.
Appears in Collections:

Altmetrics

Item View & Download Count

  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Share