Priority-based assignment and routing of a fleet of unmanned combat aerial vehicles

This paper considers the strategic routing of a fleet of unmanned combat aerial vehicles (UCAVs) to service a set of predetermined targets from a prior surveillance mission. Targets are characterized by their priority or importance level, and minimum and maximum service levels that, respectively, represent the lower bound of munitions for destruction and upper bound of munitions to limit collateral damage. Additional constraints to be respected are the payload capacities of the (possibly heterogeneous) UCAV fleet and the range based on fuel capacity and payload transported. The vital aspect of this paper is the integrated optimal utilization of available resources-weaponry and flight time-while allocating targets to UCAVs and sequencing them to maximize service to targets based on their criticality. The complexity of the problem is addressed through a decomposition scheme with two problems: a target assignment problem (modeled as a minimum cost network flow problem) and a vehicle routing problem, which in turn splits into multiple decision traveling salesman problems, one for each UAV. A Tabu search heuristic is developed to coordinate the two problems. Using test problems we establish the applicability of this approach to solve practical-sized problems. (c) 2006 Elsevier Ltd. All rights reserved.