Journal
NETWORKS
Volume 71, Issue 1, Pages 60-80Publisher
WILEY
DOI: 10.1002/net.21793
Keywords
expected search time; immobile target; multiple searchers; path optimization; searcher path; unit network
Funding
- National Natural Science Foundation of China [71210002]
- Center for Data Centric Management in the Department of Industrial Engineering at Tsinghua University
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available