Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times

Publication Type:
Journal Article
European Journal of Operational Research, 2008, 190 (2), pp. 383 - 397
Issue Date:
Full metadata record
We consider an extension of the optimal searcher path problem (OSP), where a searcher moving through a discretised environment may now need to spend a non-uniform amount of time travelling from one region to another before being able to search it for the presence of a moving target. In constraining not only where but when the search of each cell can take place, the problem more appropriately models the search of environments which cannot be easily partitioned into equally sized cells. An existing OSP bounding method in literature, the MEAN bound, is generalised to provide bounds for solving the new problem in a branch and bound framework. The main contribution of this paper is an enhancement, discounted MEAN (DMEAN), which greatly tightens the bound for the new and existing problems alike with almost no additional computation. We test the new algorithm against existing OSP bounding methods and show it leads to faster solution times for moving target search problems. © 2007 Elsevier B.V. All rights reserved.
Please use this identifier to cite or link to this item: