Path Optimization for Single and Multiple Searchers: Models and Algorithms
Abstract
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-an-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 e ect. 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 2008
- Accession Number
- ADA488991
Entities
People
- Hiroyuki Sato
Organizations
- Naval Postgraduate School