Dynamic reassignment and rerouting in cooperative airborne operations
Murray, Chase C.
MetadataShow full item record
Unmanned aerial vehicles (UAVs), increasingly vital to the success of military operations, operate in a complex and dynamic environment, sometimes in concert with manned aircraft. This work addresses the problem of dynamically reallocating these airborne resources to timesensitive tasks in response to changes in battlespace conditions. This problem is characterized by diverse priority-based tasks with time windows, heterogeneous resources with fuel- and payload-capacity limitations, and multiple competing objectives (e.g., maximizing overall mission effectiveness and minimizing changes to the original resource routes). An extensible modeling framework for the solution to this dynamic resource management problem is developed and formulated as an integer linear program. To solve this challenging problem, a novel solution approach based on a branch-and-bound procedure that is guided by five route construction procedures is proposed. This strategy is aided by a solution space reduction procedure, and the incorporation of valid network-strengthening cuts at each node of the branch-and-bound tree. Extensive numerical analysis indicates that this approach outperforms the state-of-the art commercial integer programming software, both in terms of solution quality and runtime. The test problems developed for this analysis may be used to benchmark future solution approaches to this problem, as no comparable set of problems exist. To demonstrate the extensible nature of the modeling framework, numerous extensions to the general model are provided. These enhancements include improved approximations of flight dynamics, soft time windows for tasks, escort operations to protect high-valued assets in hostile territories, additional task types, and refueling operations. In addition to rerouting resources in a reactionary manner, knowledge about the likely appearance of future tasks may be incorporated within the modeling framework. Preliminary simulation trials suggest that the proposed method for addressing stochastic tasks can increase the number of pop-up tasks that are assigned when they actually appear, and may improve the overall mission effectiveness compared to the purely reactionary approach. Although motivated by airborne military operations, the proposed general modeling framework is applicable to a wide array of settings, such as disaster relief operations. Additionally, land- or water-based operations may be modeled within this framework, as well as any combination of manned and unmanned vehicles.