An exact solution algorithm for maximizing the fleet availability of an aircraft unit subject to flight and maintenance requirements

Flight and Maintenance Planning (FMP) of mission aircraft addresses the question of which available aircraft to fly and for how long, and which grounded aircraft to perform maintenance operations on, in a group of aircraft that comprise a unit. The objective is to achieve maximum fleet availability of the unit over a given planning horizon, while also satisfying certain flight and maintenance requirements. Heuristic approaches that are used in practice to solve the FMP problem often perform poorly, generating solutions that are far from optimum. On the other hand, the more sophisticated mathematical optimization models that have been developed to tackle this problem handle small problems effectively, but tend to be computationally inefficient for larger problems that often arise in practice. In this work, we develop an exact solution algorithm for the FMP Problem, which is capable of identifying the global optimal solution of realistic size problems in very reasonable computational times. Initially, this algorithm obtains a valid upper bound on the optimal objective function value by solving a simplified relaxation of the original problem; then, this value is gradually reduced, until a feasible solution that attains it is identified. The algorithm employs special valid inequalities (cuts), which exclude solutions that do not qualify for optimality from further consideration. The experimental results that we present demonstrate that the proposed solution algorithm is significantly more efficient than a commercial optimization software package that can be used alternatively for the solution of the problem under consideration