Aircraft maintenance, routing, and crew scheduling planning for airlines with a single fleet and a single maintenance and crew base

• Sequential and integrated aircraft maintenance routing and crew scheduling problems.
• Heuristics for first feasible solution of the CSP.
• Labeling algorithm to solve the pricing problem of the column generation.
• Approaches tested with real data from 3 different Latin American airlines.

This work proposes an approach for solving the aircraft maintenance routing problem (AMRP) and the crew scheduling problem (CSP) in sequential and integrated fashions for airlines having a single fleet with a single maintenance and crew base, as is the case for most Latin American and many low-cost airlines. The problems were initially solved in the traditional sequential fashion. The AMRP was formulated to maximize revenue while satisfying fleet size. It was solved such that the final flight schedule was also determined. The CSP was solved by including a heuristic to obtain an efficient first feasible solution, and adapting a labeling algorithm to solve the pricing problems that arise in the column-generation technique. Finally, an integrated model was formulated and solved. Both approaches were tested on the real flight schedules of three important Latin American airlines. The solutions were coherent, independent of computational parameters, and obtained in short computational times in a standard PC (e.g. <1 h for up to 522 flights). Continuous relaxations gave very tight bounds (e.g. gaps < 0.8%). The integrated solutions offered small improvements over the sequential solutions (e.g. up to 0.6% or US$45,000 savings/year). However, these savings should increase drastically with fleet size and with the complexity of the flight schedule offered by the airline.