UAV routing for reconnaissance mission: A multi-objective orienteering problem with time-dependent prizes and multiple connections. (September 2022)

• Record Type: Journal Article
• Authors: Dasdemir, Erdi; Batta, Rajan; Köksalan, Murat; Tezcaner Öztürk, Diclehan
• Is Part Of: Computers & operations research. Volume 145(2022)
• Publication Date: 2022-09
• Subjects: Multiple objective programming -- UAV routing -- Orienteering -- Time-dependent prizes -- Mixed integer programming; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105882
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: We 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. Highlights: Routing a UAV for reconnaissance under radar surveillance. Multiple objectives, time-dependent prizes, and multiple connections are considered. A new type of orienteering problem is introduced. An MIP model and a hybrid solution algorithm including a heuristic are developed. A case study based on the terrain properties of the State of Colorado is presented.