Path optimization for single and multiple searchers: models and algorithms
Loading...
Authors
Sato, Hiroyuki
Subjects
Path optimization
Branch-and-bound
Cross-entropy method
Outer approximation
Branch-and-bound
Cross-entropy method
Outer approximation
Advisors
Royset, Johannes O.
Date of Issue
2008-09
Date
September 2008
Publisher
Monterey, California. Naval Postgraduate School
Language
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-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.
Type
Thesis
Description
Series/Report No
Department
Operations Research
Organization
Identifiers
NPS Report Number
Sponsors
Funding
Format
xviii, 121 p. ; 28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.