Solving the moving target search problem using indistinguishable searchers

François-Alex Bourque

European Journal of Operational Research, 2019, vol. 275, issue 1, 45-52

Abstract: Searching for a single target in a discrete space and time is a well-known problem in military operational research that also finds applications in other areas such as search and rescue. Solving this problem is difficult, as search routes depend on the knowledge of where the target may be at a given time, which itself changes as the search proceeds. It is even more so for multiple searchers, as the size of the state space now depends on the number of searchers. This contribution deals with this problem variant for a single moving target by assuming that searchers are not only identical, but also indistinguishable. In the standard branch and bound approach to this problem, this assumption permits the calculation of bounds by solving minimum-cost flow problems, which are independent of the number of searchers and where there is no need to relax the integrality of the search effort. Both of these outcomes are novel in comparison to previous efforts with multiple searchers. The author illustrates the proposed approach in the context of a counter-piracy scenario where warships aim to deter and interdict pirates and where the pirate motion model derives from an environmental forecast of the likelihood of piracy and the Markov assumption. Computational experiments are performed to compare the proposal to an alternative found in the literature to solve the problem to optimality.

Keywords: OR in defence; Search theory; Integer programming; Branch and bound (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718309317
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:275:y:2019:i:1:p:45-52

DOI: 10.1016/j.ejor.2018.11.006

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().