The Crew Pairing Problem (CPP) involves constructing feasible pairings (sequences of flights, connections, and rest periods) for airline crew while minimizing operational costs and ensuring full flight coverage. However, beyond cost minimization, regularity has become a crucial objective for many airlines, as it enhances operational stability and may reduce indirect logistical costs. Traditional CPP optimization methods primarily focus on cost reduction but often fail to effectively incorporate regularity, as they lack a structured mechanism to balance both objectives.

This study proposes several approaches to enhance regularity in the CPP. The first approach is bonus-based, identifying pairings with high repetition potential in the initial solution. The CPP is then re-solved using a branch-and-price algorithm to encourage the selection of these repeatable pairings. The second approach reoptimizes the initial solution by solving an MIP that explicitly maximizes regularity. Finally, we show that both approaches are complementary and can be applied sequentially to further enhance regularity while maintaining cost efficiency, forming a hybrid method.

Computational experiments conducted on datasets from a major Asian airline demonstrate the effectiveness of the proposed methods. The results show that they generate highly regular solutions with minimal cost deviations, achieving up to an 88% improvement in regularity ratio and a 58% reduction in pairing patterns. This significant improvement highlights the practical applicability of the methods in optimizing airline crew pairing.