Article ID: | iaor20105265 |
Volume: | 57 |
Issue: | 5 |
Start Page Number: | 422 |
End Page Number: | 440 |
Publication Date: | Aug 2010 |
Journal: | Naval Research Logistics |
Authors: | Royset Johannes O, Sato Hiroyuki |
Keywords: | optimization |
We formulate and solve a discrete‐time path‐optimization problem where a single searcher, operating in a discretized three‐dimensional airspace, looks for a moving target in a finite set of cells. The searcher is constrained by maximum limits on the consumption of one or more resources such as time, fuel, and risk along any path. We develop a specialized branch‐and‐bound algorithm for this problem that uses several network reduction procedures as well as a new bounding technique based on Lagrangian relaxation and network expansion. The resulting algorithm outperforms a state‐of‐the‐art algorithm for solving time‐constrained problems and also is the first algorithm to solve multi‐constrained problems.