Traveling between dispersed locations to search for a hidden object

• We consider a generalization of a classical search problem in which candidate search locations are geographically dispersed. • We propose an index heuristic which takes the topology of the search space into account. • Stronger-performing heuristics are developed by applying various improvement methods to the base heuristic. • Computational experiments demonstrate strong performance of the heuristics in randomly generated scenarios. We consider a search problem in which an object is hidden in one of n geographically distinct locations according to a known probability distribution. A searcher moves between these locations in order to find the object. A search at location i takes t i time units and independently finds the object with probability q i if the object is there, for i = 1 , … , n . Additionally, traveling from location i to location j takes d ij time units, for i , j = 1 , … , n . The searcher aims to minimize the expected total amount of time needed to find the object. The version of our problem without travel times can be solved to optimality using Gittins indices, which directs the searcher to always search the location that yields the maximal rate of finding the object. When travel times are included the problem becomes much more challenging, because the searcher becomes less willing to move to another location due to the potential future travel time back to the current location. In addition, when choosing the next destination, the searcher needs to take into account not only the distance to each destination, but also each destination’s distance to all other locations. We draw upon restless bandit theory to derive an index heuristic that takes travel times into account, and show that this heuristic has a tendency to leave a location prematurely. Subsequently, we use a range of methods to improve the index heuristic and demonstrate their strong performance via computational experiments.