A column generation approach for operational flight scheduling and aircraft maintenance routing

Abstract

Aircraft is one of the most expensive resources owned by an airline which should be properly planned. The aircraft maintenance routing problem (AMRP) generates aircraft routes to serve scheduled flights, while satisfying the strict maintenance requirements. However, in operations, the pre-determined aircraft routes are usually disrupted due to unplanned maintenance requirements or insufficient remaining legal flying time to maintenance stations. Thus, airlines often have to re-route aircraft in real time. This study proposes a new aircraft re-routing approach to fulfil the maintenance requirements arising in the operational stage. Specifically, maintenance stations are capacity-constrained, while airlines could allocate maintenance resources (like staff and equipment) to other airports with additional costs. Besides, flights could be re-scheduled (i.e., cancelled with a high penalty), while the model endeavors to minimize the impact of recovery actions on the original plan. To achieve this, specialized flight networks are constructed, and a column generation-based algorithm is developed to obtain high-quality solutions within short computational times. Computational experiments show that the solutions obtained by the proposed algorithm are optimal or near-optimal with an optimality gap of 0.3% on average. In addition, some managerial insights on allocating maintenance resources to other airports to fulfil aircraft maintenance demands in operations are discussed.