Path optimization for single and multiple searchers: models and algorithms
Royset, Johannes O.
MetadataShow full item record
We develop models and solution methodologies to solve the discrete-time path-optimization problem where a single or multiple searchers look for a moving target in a finite set of cells. The single searcher is constrained by maximum limits on the consumption of several resources such as time, fuel, and risk along any path. We develop a specialized branch-and-bound algorithm for this problem that utilizes several new network reduction procedures as well as new bounding technique based on Lagrangian relaxation and network expansion. The resulting algorithm is quite efficient and promising. For the multiple searchers, an optimal set of paths (search plan) is determined by taking advantage of the cooperative search effect. We present a new exact algorithm and two new heuristics to find an optimal or near-optimal search plan. One of the heuristics is based on the cross-entropy method and is found to perform well for a broad range of problem instances. The exact algorithm deals with the specific case of homogeneous searchers and is based on outer approximations by several new cutting planes. In addition, we prove that under certain assumptions the path-optimization problem becomes equivalent to a large-scale linear mixed-integer program.
Showing items related by title, author, creator and subject.
Santos, Almir Garnier (Monterey, California. Naval Postgraduate School, 1993-09);The need to search effectively for objects presents itself in many civilian and military applications. This thesis develops and tests six heuristics and an optimal branch and bound procedure to solve the heretofore ...
Dell, Robert F.; Eagle, James N.; Martins, Gustavo Henrique Alves; Santos, Almir Garnier (1996);The search theory open literature has paid little, if any, attention to the multiple-searcher, moving-target search problem. We develop an optimal branch-and-bound procedure and six heuristics for solving constrained-path ...
Foraker, Joseph Carl. (Monterey, California. Naval Postgraduate School, 2011-09);We show how to formulate many continuous time-and-space search problems as generalized optimal control problems, where multiple searchers look for multiple targets. Speci cally, we formulate problems in which we minimize ...