UAV routing for reconnaissance mission: A multi-objective orienteering problem with time-dependent prizes and multiple connections

Dasdemir E., Batta R., Köksalan M., TEZCANER ÖZTÜRK D.

Computers and Operations Research, vol.145, 2022 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 145
  • Publication Date: 2022
  • Doi Number: 10.1016/j.cor.2022.105882
  • Journal Name: Computers and Operations Research
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, PASCAL, ABI/INFORM, Aerospace Database, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Communication Abstracts, Computer & Applied Sciences, INSPEC, Metadex, zbMATH, Civil Engineering Abstracts
  • Keywords: Multiple objective programming, UAV routing, Orienteering, Time-dependent prizes, Mixed integer programming, UNMANNED AERIAL VEHICLE, MAXIMUM COLLECTION PROBLEM, LOCAL SEARCH, WINDOWS, INFORMATION, ALGORITHMS, SURVEILLANCE
  • Middle East Technical University Affiliated: Yes


© 2022 Elsevier LtdWe address the route planning problem of an unmanned air vehicle (UAV) tasked with collecting information from a radar-monitored environment for a reconnaissance mission. The UAV takes off from a home base, visits a set of targets, and finishes its movement at a final base. Collectable information at a target depends on the time the target is visited by the UAV. There are multiple trajectory alternatives between the target pairs with different travel time and threat attributes. A route plan involves the selection of the targets to visit, the order of visit to the targets, and the trajectories to follow between the targets. Multiple routing objectives, information collection, mission duration and mission safety, are considered to present the trade-offs among the objectives to the route planner. The problem is classified as a multi-objective orienteering problem with time-dependent prizes and multiple connection options. A mixed integer programming model that can be used for small-sized problems is formulated. Larger problems are addressed with a hybrid algorithm involving heuristics and exact approaches. A case study based on a terrain in the State of Colorado is presented. Finally, some practical issues for the UAV route planning problem is discussed.