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: | Dell Robert F., Henrique Gustavo, Martins Alves, Santos Almir Garnier |
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.