Formulation and Solution of the Target Visitation Problem

Abstract

This paper presents the Target Visitation Problem (TVP) for a single unmanned aerial vehicle (UAV). The ability to effectively plan a path for a UAV to visit multiple targets is an increasingly important capability in a variety of applications, including surveillance, attack, assessment, search and rescue, disaster relief, and environmental cleanup. The TVP is related to both the Traveling Salesman Problem and the Linear Ordering Problem, with an objective function that combines elements of both problems. The TVP considers both total travel distance and the order of targets visited. In this paper, we formulate the target visitation problem for a single vehicle, describe a heuristic solution procedure, and report results for problems of various size.