Traveling between dispersed locations to search for a hidden object
研究在多个分散地点间移动搜索隐藏物体的问题，提出考虑旅行时间的索引启发式方法，并通过计算实验验证其性能。
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.