Adaptive unmanned aerial vehicle surveillance using a prize-collecting vertex routing model

Surveillance using unmanned aerial vehicles (UAVs) in the military context needs to be adaptable, at times not visiting some regions while visiting other regions that contain highly valuable information multiple times. Motivated by this premise, we analyze UAV surveillance using a prize-collecting vertex routing (PCVR) model. The problem is defined on an undirected graph with each vertex having an information value and collection time. Each edge connecting vertices has a travel time. The sum of all travel times and collection times for a vehicle must not exceed a predefined parameter. A vertex may be visited multiple times with decreasing information collection in subsequent visits. The PCVR model is formulated as a mixed integer program (MIP). A simulated annealing heuristic is developed to solve large problem instances. The solution methods are subjected to extensive computational testing. Two aspects of the model are examined to further its potential applicability. A hypothetical usage scenario is developed to demonstrate how the model could be applied in a military context. Further, a hardware demonstration is detailed to identify technical challenges that are likely to be present in a field application.