Embedding a Reactive Tabu Search Heuristic in Unmanned Aerial Vehicle Simulations

摘要

We apply a Reactive Tabu Search (RTS) heuristic within a discrete eventsimulation to solve routing problems for Unmanned Aerial Vehicles (UAVs). Our formulation represents this problem as a Multiple Traveling Salesman Problem with Time Windows (MTSPTW), with the objective of attaining a specified level of target coverage using a minimum number of vehicles. Incorporating weather and probability of UAV survival at each target as random inputs, the RTS heuristic in the simulation searches for the best solution in each realization of the problem scenario in order to identify those routes that are robust to variations in weather, threat, or target service times. Generalizing this approach as Embedded Optimization (EO), we define EO as a characteristic of a discrete event simulation model that contains optimization or heuristic procedures that can affect the state of the system. The RTS algorithm in the UAV simulation demonstrates the utility of EO by determining the necessary fleet size for an operationally representative scenario. From our observation of robust routes, we suggest a methodology for using robust tours as initial solutions in subsequent replications. We present an object oriented implementation of this approach using MODSIM III, and show how mapping object inheritance to the GVRP hierarchy allows for minimal adjustments from previously written objects when creating new types. Finally, we use EO to conduct an analysis of fleet size requirements within an operationally representative scenario.