Using multiple searchers in constrained-path, moving-target search problems

Using multiple searchers in constrained-path, moving-target search problems

0.00 Avg rating0 Votes
Article ID: iaor19962063
Country: United States
Volume: 43
Issue: 4
Start Page Number: 463
End Page Number: 480
Publication Date: Jun 1996
Journal: Naval Research Logistics
Authors: , , ,
Abstract:

The search theory open literature has paid little, if any, attention to the multiple-searcher, moving-target search problem. The authors develop an optimal branch-and-bound procedure and six heuristics for solving constrained-path problems with multiple searchers. The present optimal procedure outperforms existing approaches when used with only a single searcher. For more than one searcher, the time needed to guarantee an optimal solution is prohibitive. The present heuristics represent a wide variety of approaches: One solves partial problems optimally, two use paths based on maximizing the expected number of detections, two are genetic algorithm implementations, and one is local search with random restarts. A heuristic based on the expected number of detections obtains solutions within 2% of the best known for each one-, two-, and three-searcher test problem considered. For one- and two-searcher problems, the same heuristic’s solution time is less than that of other heuristics. For three-searcher problems, a genetic algorithm implementation obtains the best-known solution in as little as 20% of other heuristic solution times.

Reviews

Required fields are marked *. Your email address will not be published.