A Stochastic Multi-objective Optimization Approach to Cooperative Task and Route Planning for Heterogeneous UAVs in Uncertain Combat Environments

Abstract This paper addresses the coordinated task assignment and route planning for a fleet of heterogeneous unmanned air vehicles (UAVs) operating in a stochastic threat environment. Each UAV is capable of engaging and destroying designated targets, while enemy air defenses pose risks of UAV losses based on specified survival probabilities. The study aims to minimize mission tardiness within a fixed time horizon and maximize cumulative mission rewards by neutralizing the highest number of targets while minimizing UAV losses. We first formulate the problem as a stochastic, multi-objective mixed-integer linear program defined on a graph, integrating task scheduling, timing, and connectivity constraints to simultaneously optimize UAV routes and target assignments. For small-scale instances, this formulation can be solved optimally. However, the problem’s NP-hard, combinatorial nature renders exact methods impractical for larger instances. To address this, we develop a novel two-stage heuristic, combining simulated annealing and genetic algorithms. In the first stage, simulated annealing generates a robust initial task allocation common to all scenarios. In the second stage, a genetic algorithm refines the routes and assignments independently for each scenario. A custom scenario generator was developed to vary survival probabilities, target densities, distance metrics, and UAV capacities to rigorously test solution quality. Computational experiments demonstrate that the proposed heuristic produces high-quality solutions across various settings within tractable time frames, offering decision makers a practical tool to plan UAV-based airstrike operations under uncertainty.