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 consumption, 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.
Routing Military Aircraft with a Constrained Shortest-Path Algorithm
2007
44 pages
Report
No indication
English
Flexible Bus Routing System with Shortest Path Search Algorithm
European Patent Office | 2020
|A Distributed Shortest-Path Routing Algorithm for Transportation Systems
British Library Conference Proceedings | 2010
|The Variance-Constrained Shortest Path Problem
Online Contents | 1994
|An improved solution algorithm for the constrained shortest path problem
Online Contents | 2007
|