Logo PTI Logo FedCSIS

Communication Papers of the 21st Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 49

Incorporation of Min/Max, With/Without and Pairing Restrictions in Column Generation Solution Algorithms for Aircrew Rostering

, ,

DOI: http://dx.doi.org/10.15439/2026F4530

Citation: George Kozanidis, ,

Full text

Abstract. We consider the column generation solution framework utilized for handling the crew rostering problem in the context of commercial aviation. Motivated by practical requirements arising in realistic environments, we modify the algorithmic methodology to enable the incorporation of three special types of restrictions termed min/max, with/without and pairing, respectively. Min/max restrictions impose suitable lower/upper bounds on the number of crew members of a specific-category assigned to certain flight duties. With restrictions ensure that crew members of a specific category assigned to certain flight duties are coupled with some other crew members of another specific category. Without restrictions forbid the simultaneous assignment of crew members belonging to two distinct specific categories to certain flight duties. Finally, pairing restrictions dictate that the number of crew members of each of two mutually exclusive, but collectively exhaustive, categories assigned to certain flight duties with even crew complement must also be even. After properly adjusting the algorithmic solution framework for accommodating these restrictions, we present computational results demonstrating how their incorporation affects algorithmic behavior and computational performance.

References

  1. M. Fuentes, L. Cadarso, V. Vaze, and C. Barnhart, “The tail assignment problem: A case study at Vueling Airlines,” Transp. Res. Proc., 52, pp. 445-452, 2021. https://doi.org/10.1016/j.trpro.2021.01.052
  2. G. Kozanidis, “Optimal assignment of aircrew trainees to simulator and classroom training sessions subject to seniority and preference restrictions,” J. Air Transp. Manag., 59, pp. 143-154, 2017. https://doi.org/10.1016/j.jairtraman.2016.11.012
  3. H. Dawid, J. König, and C. Strauss, “An enhanced rostering model for airline crews,” Comput. Oper. Res., 28(7), pp. 671-688, 2001. https://doi.org/10.1016/S0305-0548(00)00002-2
  4. B. Gopalakrishnan, and E. L. Johnson, “Airline crew scheduling: State-of-the-art,” Ann. Oper. Res., 140, pp. 305-337, 2005. https://doi.org/10.1007/s10479-005-3975-3
  5. A. Aydemir-Karadag, B. Dengiz, and A. Bolat, “Crew pairing optimization based on hybrid approaches,” Comput. Ind. Eng., 65(1), pp. 87-96, 2013. https://doi.org/10.1016/j.cie.2011.12.005
  6. P. R. Day, and D. M. Ryan, “Flight attendant rostering for short-haul airline operations,” Oper. Res., 45(5), pp. 649-661, 1997. https://doi.org/10.1287/opre.45.5.649
  7. M. Gamache, F. Soumis, D. Villeneuve, J. Desrosiers, and E. Gélinas, “The preferential bidding system at Air Canada,” Transp. Sci., 32(3), pp. 246-255, 1998. https://doi.org/10.1287/trsc.32.3.246
  8. A. I. Z. Jarrah, and J. T. Diamond, “The problem of generating crew bidlines,” Interfac., 27(4), pp. 49-64, 1997. https://doi.org/10.1287/inte.27.4.49
  9. J. Desrosiers, and M. E. Lübbecke, “A primer in column generation,” in Column Generation, G. Desaulniers, J. Desrosiers, and M.M. Solomon, Eds. Boston, MA, US: Springer, pp. 1-32, 2005. https://doi.org/10.1007/0-387-25486-2_1
  10. D. Ryan, “The solution of massive generalized set partitioning problems in air crew rostering,” J. Oper. Res. Soc., 43, pp. 459-467, 1992. https://doi.org/10.1057/jors.1992.72
  11. M. Gamache, F. Soumis, G. Marquis, and J. Desrosiers, “A column generation approach for large-scale aircrew rostering problems,” Oper. Res., 47(2), pp. 247-263, 1999. https://doi.org/10.1287/opre.47.2.247
  12. T. Fahle, U. Junker, S. E. Karisch, N. Kohl, M. Sellmann, and B. Vaaben, “Constraint programming based column generation for crew assignment,” J. Heuristics, 8(1), pp. 59-81, 2002. https://doi.org/10.1023/A:1013613701606
  13. J. Desrosiers, and M. E. Lübbecke, “Branch-price-and-cut algorithms,” in Encyclopedia of Operations Research and Management Science. Chichester, UK: John Wiley & Sons, pp. 109-131, 2011. https://doi.org/10.1002/9780470400531.eorms0118
  14. G. Kozanidis, “Branch and price for covering shipments in a logistic distribution network with a fleet of aircraft,” Optim. Methods Softw., 33(2), pp. 221-248, 2018. https://doi.org/10.1080/10556788.2017.1281923
  15. G. Kozanidis, “Column generation for optimal shipment delivery in a logistic distribution network,” in Sustainable Logistics and Transportation, D. Cinar, K. Gakis, and P.M. Pardalos, Eds. Springer Optimization and Its Applications, vol. 129, pp. 87-112. Berlin: Springer-Verlag, 2018. https://doi.org/10.1007/978-3-319-69215-9_5
  16. Z. Liu, and Q. Xiang, “A branch-and-price algorithm for the airport gate assignment problem considering the trade-off between robustness and efficiency,” Transp. Res. C Emerg. Technol., 154, 104232, 2023. https://doi.org/10.1016/j.trc.2023.104232
  17. G. Kozanidis, “An integrated column generation solution framework for optimal aircrew vacation planning subject to seniority ranking and priority preference satisfaction,” Omega, 135, 103224, 2025. https://doi.org/10.1016/j.omega.2025.103324
  18. J. Desrosiers, F. Soumis, and M. Desrochers, “Routing with time windows by column generation,” Networks, 14(4), pp. 545-565, 1984. https://doi.org/10.1002/net.3230140406
  19. C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. Savelsbergh, and P. H. Vance, “Branch-and-price: Column generation for solving huge integer programs,” Oper. Res., 46(3), pp. 316-329, 1998. https://doi.org/10.1287/opre.46.3.316
  20. M. Gamache, and F. Soumis, “A method for optimally solving the rostering problem” in Operations Research in the Airline Industry, G. Yu, Ed. Boston, MA, US: Springer, pp. 124-157, 1998. https://doi.org/10.1007/978-1-4615-5501-8_5
  21. A. Kasirzadeh, M. Saddoune, and F. Soumis, “Airline crew scheduling: Models, algorithms, and data sets,” EURO J. Transp. Logist., 6(2), pp. 111-137, 2017. https://doi.org/10.1007/s13676-015-0080-x
  22. G. Kozanidis, and O. Moschopoulos, “Set-cover master problem formulations for maximum flight coverage in branch & price solution algorithms for optimal aircrew rostering,” Oper. Res. Int. J., 25(3), 69, 2025. https://doi.org/10.1007/s12351-025-00950-0
  23. G. Kozanidis, and O. Moschopoulos, “Set-cover master problem formulations in branch & price solution methodologies for optimal aircrew scheduling,” in Lecture Notes in Operations Research, Annual International Conference of the German Operations Research Society, Ham-burg, Germany, August 29 - September 1, pp. 249-256, 2023. https://doi.org/10.1007/978-3-031-58405-3_32
  24. AIMS INTL DWC-LLC (2025). Airline solutions package and aviation software. https://www.aimsairlinesoftware.com/ Last accessed on April 13, 2026.
  25. IBM ILOG CPLEX Optimization Studio v. 22.1.1 (2022). https://www.ibm.com/docs/en/icos/22.1.1 . Last accessed on April 13, 2026.
  26. F. Vanderbeck, “On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm,” Oper. Res., 48(1), pp. 111-128, 2000. https://doi.org/10.1287/opre.48.1.111.12453