Çiya Aydoğan and Sinan Gürel, Middle East Technical University - Industrial Engineering

Operating leases have become a widely adopted method for aircraft acquisition in the airline industry. However, such leases often impose operational constraints on lessees, including target hour-to-cycle ratios that reflect engine wear and maintenance requirements. Failure to satisfy these targets within designated periods may lead to significant financial penalties in the form of supplementary lease payments. This study addresses the Tail Assignment Problem under hour-to-cycle ratio constraints. We propose an exact branch-and-price algorithm to solve this problem efficiently. To enhance the algorithm's practical performance, we integrate a beam search-based method that quickly generates high-quality feasible solutions and develop a dancing links-based heuristic to provide tight upper bounds. Computational results demonstrate that our branch-and-price algorithm significantly outperforms a state-of-the-art commercial solver (CPLEX) applied to a connection network-based formulation. The proposed method successfully solves instances involving up to 60 aircraft and 450 flights to optimality.