Estimating the Number of Feasible Rosterlines in Airline Individual Crew Rostering Problems

We present an exact algorithm for counting the number of feasible rosterlines in two airline crew rostering problems based on data from a large Asian airline. Taking these results, we then find formulae that give the approximate number of rosterlines given the number of employees and the approximate number of rosterlines given the number of days in the rostering period. Our main result is that one algorithm can be used to count the number of rosterlines for both problem types. Also, for the two problems types considered, the logarithm of the number of rosterlines exhibits linear growth versus the number of days in the roster period (i.e. the number of rosters grows exponentially) and linear growth with an added logarithmic term versus the number of employees.