<div class="description">
<p>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.
</p>
<br>Subjects: Decision making; Path optimization; Branch-and-bound; Cross-entropy method; Outer approximation</div>
<div class="fn value">
Sato, Hiroyuki</div>
Internet Archive identifier