Reactive Tabu Search Metaheuristic Extension of the Air Refueling Tanker Assignment Problem

摘要

The Combined Mating and Ranging Planning System (CMARPS) is the system used by AMC to schedule air refueling for deployments from the continental U.S. to other parts of the world. The tool developed by Capehart (2000) got results similar to CMARPS in less time. Capehart's tool allows AMC to input several receiver groups consisting of various aircraft types and numbers. Each receiver group contains a point of origin and destination, with the option of providing one waypoint along the path, a ready to load date (RLD) and required delivery date (RDD). The user is also able to specify the locations of military tanker aircraft. The main goal of this tool is to assign the tankers to the different refueling points of the receiver groups so that all receiver groups arrive before their RDD. Secondary goals include the reuse of tankers and limiting the total flight distance for all tanker aircraft. The main purpose of this research is to introduce a dynamic feature of tabu search, reactive tabu search, into the tool. This method changes tabu tenure when necessary in the hope of finding better solutions by diversifying the search to the unexplored areas of the solution space.