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

We address the Flight and Maintenance Planning (FMP) problem, i.e., the problem of deciding 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 aim is to maximize the unit fleet availability over a multi-period planning horizon, while also ensuring that certain flight and maintenance requirements are satisfied. Heuristic approaches that are used in practice to solve the FMP problem often perform poorly, generating solutions that are far from the optimum. On the other hand, the exact optimization models that have been developed to tackle the problem handle small problems effectively, but tend to be computationally inefficient for larger problems, such as the ones that arise in practice. With these in mind, we develop an exact solution algorithm for the FMP problem, which is capable of identifying the optimal solution of considerably large realistic problems in reasonable computational times. The algorithm solves suitable relaxations of the original problem, utilizing valid cuts that guide the search towards the optimal solution. We present extensive experimental results, which demonstrate that the algorithm's performance on realistic problems is superior to that of two popular commercial optimization software packages, whereas the opposite is true for a class of problems with special characteristics that deviate considerably from those of realistic problems. The important conclusion of this research is that the proposed algorithm, complemented by generic optimization software, can handle effectively a large variety of FMP problem instances. (C) 2014 Published by Elsevier B.V