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

Frank Mufalli, Rajan Batta, Rakesh Nagi

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)2787-2799
Number of pages13
JournalComputers and Operations Research
Volume39
Issue number11
DOIs
StatePublished - Nov 1 2012
Externally publishedYes

Keywords

  • Column Generation
  • Routing
  • Sensor selection
  • Team orienteering problem
  • Unmanned aerial vehicles

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plans'. Together they form a unique fingerprint.

  • Cite this