This paper addresses the problem of generating valid crew pairings in the context of a regional air carrier. The classical column generation solution approach based on extensive enumeration of all valid duties is impractical in this context where duties comprise ten to twelve legs. In order to alleviate this difficulty, we propose an alternate approach which takes into account all clauses in the work convention and the appropriate air traffic regulations during the construction of valid crew pairings. Two network structures compatible with this approach are described. The first is a leg-on-node model while the second involves a leg-on-arc representation. Computational results obtained with the GENCOL optimizer on problems varying from 63 to 986 legs lead us to conclude that the leg-on-arc representation is substantially more efficient. In addition, we study the cost impact of three changes in the operating scenario. Finally, we illustrate how bounded perturbation variables virtually eliminate degeneracy, hence significantly decreasing CPU time.