Routing Military Aircraft with a Constrained Shortest-Path Algorithm
Loading...
Authors
Carlyle, W. Matthew
Royset, Johannes O.
Wood, R. Kevin
Subjects
Advisors
Date of Issue
2007-04-17
Date
2007-04-17
Publisher
Language
Abstract
We formulate and solve aircraft-routing problems that arise when planning missions for military aircraft that are subject to ground-based threats such as surface-to-air missiles. We use a constrained-shortest path (CSP) model that discretizes the relevant airspace into a grid of vertices representing potential waypoints, and connects vertices with directed edges to represent potential flight segments. The model is flexible: It can route any type of manned or unmanned aircraft; it can incorporate any number of threats; and it can incorporate, in the objective function or as side constraints, numerous mission-specific metrics such as risk, fuel consuption, and flight time. We apply a new algorithm for solving the CSP problem and present computational results for the routing of a high-altitude F/A-18 strike group, and the routing of a medium-altitude unmanned aerial vehicle. The objectives minimize risk from ground-based threats while constraints limit fuel consumption and / or flight time. Run times to achieve a near-optimal solution range from fractions of a second to 80 seconds on a personal computer. We also demonstrate that our methods easily extend to handle turn-radius constraints and round-trip routing.
Type
Paper
Description
Military Operations Research, to appear.
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Carlyle, W.M., Royset, J.O. and Wood, R.K., 2007, "Routing Military Aircraft with a Constrained Shortest-Path Algorithm," Military Operations Research, to appear.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.