Fast or Slow: Search in Discrete Locations with Two Search Modes

Jake Clarkson (), Kevin D. Glazebrook () and Kyle Y. Lin ()
Additional contact information
Jake Clarkson: STOR-i Centre for Doctoral Training, Lancaster University, Lancaster LA1 4YR, United Kingdom
Kevin D. Glazebrook: Department of Management Science, Lancaster University, Lancaster LA1 4YX, United Kingdom
Kyle Y. Lin: Operations Research Department, Naval Postgraduate School, Monterey, California 93943

Operations Research, 2020, vol. 68, issue 2, 552-571

Abstract: An object is hidden in one of several discrete locations according to some known probability distribution, and the goal is to discover the object in the minimum expected time by successive searches of individual locations. If there is only one way to search each location, this search problem is solved using Gittins indices. Motivated by modern search technology, we extend earlier work to allow two modes—fast and slow—to search each location. The fast mode takes less time, but the slow mode is more likely to find the object. An optimal policy is difficult to obtain in general, because it requires an optimal sequence of search modes for each location in addition to a set of sequence-dependent Gittins indices for choosing between locations. Our analysis begins by—for each mode—identifying a sufficient condition for a location to use only that search mode in an optimal policy. For locations meeting neither sufficient condition, an optimal choice of search mode is extremely complicated, depending on both the probability distribution of the object’s hiding location and the search parameters of the other locations. We propose several heuristic policies motivated by our analysis and demonstrate their near-optimal performance in an extensive numerical study.

Keywords: Bayesian updating; Gittins index; optimal search; speed-accuracy trade-off; stochastic coupling; threshold-type policy (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1870 (application/pdf)

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:inm:oropre:v:68:y:2020:i:2:p:552-571

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().