×

Multiple searchers searching for a randomly distributed immobile target on a unit network. (English) Zbl 1418.90057

Summary: The authors study an optimal searcher path problem of the following type. A team of searchers tries to find an immobile target on a unit network (in a unit network, all edges are of unit length). The target is located at some point on this network, and its location probability distribution is known to the searcher team. Searchers move along the edges on the network at a constant speed. When one searcher passes the target location, detection happens and the search ends. The objective is to find paths for this team of searchers to minimize the expected search time. A linear binary programming model is built to find the optimal search strategy. Computational experiments are conducted to test the capability of this model, and to analyze how searcher team size and target distribution might affect the search time. Analytical results are given for a special problem scenario: one searcher searching for a uniformly distributed target on a tree. We prove that, any depth-first search path is optimal for a given searcher start point, and the best start point is one of the leaf nodes.

MSC:

90B10 Deterministic network models in operations research
90C05 Linear programming
90B40 Search theory
PDFBibTeX XMLCite
Full Text: DOI