Unmanned aerial vehicle route selection using reactive tabu search

In recent years the Air Force has begun employing unmanned systems, such as the Predator unmanned aerial vehicle (UAV), on surveillance and reconnaissance missions in the Balkans and Southwest Asia. The typical mission profile often involes fifty or more targets during a 24-hour period, where each individual target requires that overhead surveillance begin within a specified time of the day. Furthermore, the amount of reconnaissance time required for each target is unknown in advance, and surface-to-air threats can exist both enroute and at certain targets. Consequently, these conditions present a major challenge to UAV operators and mission planners when deciding how to sequence a mission's targets. In this paper Joel Ryan, Glenn Bailey, Jim Moore and Bee Carlton present a reactive tabu search heuristic within a Monte Carlo simulation to solve such routing problems for UAVs. Their formulation models this problem as a multiple traveling salesman problem with time windows, with the hierarchical objective of first maximizing expected target coverage, then minimizing total travel time. The authors demonstrate their technique on a notional Bosnia scenario using an object-oriented implementation of this approach.