| The successful use of Tomahawk cruise missiles in recent conflicts motivated the U.S. Navy to develop new system requirements for long-range, subsonic cruise missiles. One of these requirements is the ability to retarget the missile in flight, based on information that may become available after launch. Effective use of this ability implies planning a route that maximizes the chance of successfully attacking an alternate target if redirected, while allowing the missile to reach the original (default) target otherwise. The portion of the route where the missile is intended to be available for possible retargeting is called a loiter. Including a loiter in the subject to constraints on missile endurance, rather than simply minimizing a measure of cost, such as distance or risk. This is a distinctly different type of route planning problem that has received very little attention in the literature.; This dissertation derives a procedure for finding an optimal route that includes a loiter, based on a network flow approach in which utility, with respect to the loiter objective, is treated as a negative cost. In this formulation, finding an optimal loiter can be seen as a variation of the Tramp Steamer, or negative cost cycle, problem. It is shown that, under conditions which are fundamentally characteristic of practical route planing problems, a near-optimal solution can be found after only a few iterations of a Lagrangian relaxation procedure. |
