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 the 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 overall 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.