Dynamic routing of unmanned aerial vehicles using reactive tabu search

Unmanned Aerial Vehicle (UAV) routing is a complex problem faced by the operators of long-duration, unmanned aerial vehicles such as the US Air Force's RQ-1A Predator. The US Air Force uses the Predator UAV to perform reconnaissance and surveillance missions. The Predator is remotely flown by Air Vehicle Operators, who are Air Force pilots, located in a Ground Control Station. Existing mission support routing software automatically generates deterministic items such as terrain avoidance profiles, ground station to UAV line of site availability, route times between defined way points, fuel consumption, heading and turn information, etc., but it does not and will not optimize route selection over assigned targets. This routing task is left to the operator. Even basic routing problems are computationally difficult to solve. Unfortunately, real-world problems such as UAV routing possess many additional side constraints that impose route and vehicle capacity limitations, route length bounds, and feasible visitation time window restrictions. Additionally, the routing task may employ a variety of vehicles located at various operating locations. Fortunately, the tabu search heuristic provides excellent results on these types of problems. In this article, we present the application of a reactive tabu search metaheuristic to the vehicle routing problem with time windows using the object-oriented Java programming language. We describe the specifics of the reactive tabu search, additional considerations for the UAV routing application, and present computational results of our RTS using a benchmark set of routing problems and a notional UAV operational application. This paper was awarded the MORS 2000 Barchi Prize.