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.

Pranav Gupta & Carlos Jose Nohra Khouri, Amadeus

Connection banks are clusters of flights arriving and departing within short time frames, improving connectivity and serving key markets. These flight banks minimize layovers at hub airports, expand network reach and capture market share by enhancing service counts. Clean-sheet scheduling optimizing for banks in an integrated manner can unlock new value for airlines. We propose a local iterative search to identify a “good” set of connections using the frequency plan and subsequently use them as constraints in our clean-sheet scheduling problem where optimal connections and bank times are identified with all operational and commercial considerations. We solve the problem for a large North American carrier having nine hubs with multiple banks throughout the day. We compare the profitability and connectivity of the resultant schedule against the resultant schedule generated with their manual recommendations.