The aircraft rotation problem

Given a set of flights to be flown for a specific aircraft type, with specified maintenance locations, durations, and needed frequency, the aircraft rotation problem is to determine the specific route flown by each aircraft. The objective is to maximize the benefit derived from making specific connections. In this paper, the authors present a mathematical formulation for the aircraft rotation problem (ARP) and discuss its similarity with the asymmetric traveling salesman problem. They solve the ARP by Lagrangian relaxation and subgradient optimization and present computational results on real data from a major airline.