Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plans

Military reconnaissance missions often employ a set of unmanned aerial vehicles (UAVs) equipped with sensors to gather intelligence information from a set of known targets. UAVs are limited by the number of sensors they can hold. Also, attaching a sensor adds weight to the aircraft which in turn reduces the flight time available during a mission. The task of optimally assigning sensors to UAVs and routing them through a target field to maximize intelligence gain is a generalization of the team orienteering problem studied in vehicle routing literature. This work presents a mathematical programming model for simultaneous sensor selection and routing of UAVs, which solves optimally using CPLEX for simple missions. Larger missions required the development of three heuristics, which were augmented by column generation. Results from a performance study indicated that the heuristics quickly found good solutions. Column Generation improved the solution in many instances, with minimal impact on the final solution time. The rapid nature of the overall solution approach allows it to be used in other mission planning tasks. A fleet sizing application is discussed as an example of its flexible usage.;A cutting plane procedure is presented to prove optimality for small-medium size test instances. This allowed for the quality of the heuristics to be evaluated. Also, the effectiveness of multiple sub tour elimination constraint types is compared in a numerical study. Finally, a search problem is considered where benefit levels are removed from individual targets and scattered across a geographic region. The cutting plane formulation is modified to accommodate the search problem, which relies on the generation of dummy targets that lead to attractive search routes. Randomized target placement is compared with an intelligent target generation scheme along with a simulated annealing approach.