A combined adaptive tabu search and set partitioning approach for the crew scheduling problem with an air tanker crew application

This research develops two effective tabu search approaches to Air Mobility Command's tanker crew scheduling problem. The first is an adaptive tabu search with intensification. The second is a hybrid adaptive tabu search/set partitioning scheme that combines the metaheuristic tabu search with a classical optimization approach. The research shows that group theory can be used to effectively direct the search process of each algorithm. Since no benchmark flight schedules exist for the tanker crew scheduling problem, this research developed a Java(TM) based flight schedule generator. The robustness of the developed tabu search algorithms is judged by testing them using designed experiments. An integer program (IP) is developed to calculate lower bounds for the tanker crew scheduling problem objectives and to measure the overall quality of solutions produced by the developed algorithms. The results show that either algorithm significantly improves the solutions found by the currently used heuristic methodology.