Abstract
Airline crew pairing optimization problem (CPOP) aims to find a set of flight sequences (crew pairings) that cover all flights in an airline’s highly constrained flight schedule at minimum cost. Since crew cost is second only to the fuel cost, CPOP solutioning is critically important for an airline. However, CPOP is NP-hard, and tackling it is quite challenging. The literature suggests, that when the CPOP’s scale and complexity is reasonably limited, and an enumeration of all crew pairings is possible, then Metaheuristics are used, predominantly Genetic Algorithms (GAs). Else, Column Generation (CG) based Mixed Integer Programming techniques are used. Notably, as per the literature, a maximum of 45,000 crew pairings have been tackled by GAs. In a significant departure, this paper considers over 800 flights of a US-based large airline (with a monthly network of over 33,000 flights), and tests the efficacy of GAs by enumerating all 400,000+ crew pairings, apriori. Towards it, this paper proposes a domain-knowledge-driven customized-GA. The utility of incorporating domain-knowledge in GA operations, particularly initialization and crossover, is highlighted through suitable experiments. Finally, the proposed GA’s performance is compared with a CG-based approach (developed in-house by the authors). Though the latter is found to perform better in terms of solution’s cost-quality and run time, it is hoped that this paper will help in better understanding the strengths and limitations of domain-knowledge-driven customizations in GAs, for solving combinatorial optimization problems, including CPOPs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aggarwal, D., Saxena, D.K., Emmerich, M.: Interdependence and integration among components of the airline scheduling process. In: Paper presented at the 21st World Conference of the Air Transport Research Society (ATRS 2017), Antwerp, Belgium, 5–8 July 2017 (2017). http://www.optimization-online.org/DB_FILE/2020/05/7774.pdf
Aggarwal, D., Saxena, D.K., Emmerich, M., Paulose, S.: On large-scale airline crew pairing generation. In: 2018 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 593–600. IEEE (2018)
Aggarwal, D., Saxena, D.K., Paulose, S., Bäck, T., Emmerich, M.: Airline crew pairing optimization framework for large networks with multiple crew bases and hub-and-spoke subnetworks. arXiv preprint arXiv:2003.03994 (2020)
Aggarwal, D., Saxena, D.K., Paulose, S., Bäck, T., Emmerich, M.: A novel column generation heuristic for airline crew pairing optimization with large-scale complex flight networks. arXiv preprint arXiv:2005.08636 (2020)
Aggarwal, D., Singh, Y.K., Saxena, D.K.: On learning combinatorial patterns to assist large-scale airline crew pairing optimization. arXiv preprint arXiv:2004.13714 (2020)
Bäck, T.: Optimal mutation rates in genetic search. In: Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo (1993)
Beasley, J.E., Chu, P.C.: A genetic algorithm for the set covering problem. Eur. J. Oper. Res. 94(2), 392–404 (1996)
Deb, K., Myburgh, C.: Breaking the billion-variable barrier in real-world optimization using a customized evolutionary algorithm. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016, pp. 653–660 (2016)
Demirel, N.Ç., Deveci, M.: Novel search space updating heuristics-based genetic algorithm for optimizing medium-scale airline crew pairing problems. Int. J. Comput. Intell. Syst. 10(1), 1082–1101 (2017)
Desaulniers, G., Lessard, F., Saddoune, M., Soumis, F.: Dynamic constraint aggregation for solving very large-scale airline crew pairing problems. SN Oper. Res. Forum 1(3), 1–23 (2020). https://doi.org/10.1007/s43069-020-00016-1
Deveci, M., Demirel, N.C.: A hybrid genetic algorithm for airline crew pairing optimization. In: Economic and Social Development: Book of Proceedings, p. 118 (2016)
Deveci, M., Demirel, N.Ç.: Evolutionary algorithms for solving the airline crew pairing problem. Comput. Ind. Eng. 115, 389–406 (2018)
Garey, M.R., Johnson, D.S.: Computers and Intractibility: A Guide to the Theory of NP-Completeness, vol. 44. W. H. Freeman & Company, New York (1979)
Goldberg, D.E., Deb, K.: A comparative analysis of selection schemes used in genetic algorithms. In: Foundations of Genetic Algorithms, vol. 1, pp. 69–93. Elsevier (1991)
Holland, J.H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, Cambridge (1992)
Irnich, S., Desaulniers, G.: Shortest path problems with resource constraints. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds.) Column Generation, pp. 33–65. Springer, Boston (2005). https://doi.org/10.1007/0-387-25486-2_2
Kornilakis, H., Stamatopoulos, P.: Crew pairing optimization with genetic algorithms. In: Vlahavas, I.P., Spyropoulos, C.D. (eds.) SETN 2002. LNCS (LNAI), vol. 2308, pp. 109–120. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46014-4_11
Levine, D.: Application of a hybrid genetic algorithm to airline crew scheduling. Comput. Oper. Res. 23(6 SPEC. ISS.), 547–558 (1996)
Liu, S., Zhang, Y., Tang, K., Yao, X.: How good is neural combinatorial optimization? arXiv preprint arXiv:2209.10913 (2022)
Lübbecke, M.E.: Column generation. Wiley Encyclopedia of Operations Research and Management Science (2010)
Lübbecke, M.E., Desrosiers, J.: Selected topics in column generation. Oper. Res. 53(6), 1007–1023 (2005)
Maskooki, A., Deb, K., Kallio, M.: A customized genetic algorithm for bi-objective routing in a dynamic network. Eur. J. Oper. Res. 297(2), 615–629 (2022)
Mittal, S., Aggarwal, D., Saxena, D.K.: Innovative design of hydraulic actuation system for operator fatigue reduction and its optimization. In: Salagame, R.R., Ramu, P., Narayanaswamy, I., Saxena, D.K. (eds.) Advances in Multidisciplinary Analysis and Optimization. LNME, pp. 225–233. Springer, Singapore (2020). https://doi.org/10.1007/978-981-15-5432-2_19
Mittal, S., Saxena, D.K., Deb, K., Goodman, E.D.: A learning-based innovized progress operator for faster convergence in evolutionary multi-objective optimization. ACM Trans. Evol. Learn. Optim. (TELO) 2(1), 1–29 (2021)
Morabit, M., Desaulniers, G., Lodi, A.: Machine-learning-based column selection for column generation. Transp. Sci. 55(4), 815–831 (2021)
Morabit, M., Desaulniers, G., Lodi, A.: Machine-learning-based arc selection for constrained shortest path problems in column generation. arXiv preprint arXiv:2201.02535 (2022)
Ozdemir, H.T., Mohan, C.K.: Flight graph based genetic algorithm for crew scheduling in airlines. Proc. Joint Conf. Inf. Sci. 5(3–4), 1003–1006 (2000)
Park, T., Ryu, K.R.: Crew pairing optimization by a genetic algorithm with unexpressed genes. J. Intell. Manuf. 17(4), 375–383 (2006)
Parmentier, A., Meunier, F.: Aircraft routing and crew pairing: updated algorithms at air france. Omega 93, 102073 (2020)
Shen, Y., Sun, Y., Li, X., Eberhard, A., Ernst, A.: Enhancing column generation by a machine-learning-based pricing heuristic for graph coloring. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, pp. 9926–9934 (2022)
Vance, P., et al.: A heuristic branch-and-price approach for the airline crew pairing problem. Technical report lec-97-06, Georgia Institute of Technology, Atlanta (1997)
Zeren, B.I., Özkol, İ: A novel column generation strategy for large scale airline crew pairing problems. Expert Syst. Appl. 55, 133–144 (2016)
Zeren, B., Özkol, İ: An improved genetic algorithm for crew pairing optimization. J. Intell. Learn. Syst. Appl. 04(01), 70–80 (2012)
Acknowledgement
This research work is supported by MEITY, India [grant 13(4)/2015-CC &BT]; NWO, the Netherlands; and GE Aviation, India. Thanks to the industrial sponsor’s (GE Aviation) team members: Saaju Paulose, Arioli Arumugam and Rajesh Alla for their invaluable support in successfully completing this research. Notably, during this research, the first author (Divyam Aggarwal) was a Ph.D. Candidate at IIT Roorkee, India.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Aggarwal, D., Saxena, D.K., Bäck, T., Emmerich, M. (2023). Real-World Airline Crew Pairing Optimization: Customized Genetic Algorithm Versus Column Generation Method. In: Emmerich, M., et al. Evolutionary Multi-Criterion Optimization. EMO 2023. Lecture Notes in Computer Science, vol 13970. Springer, Cham. https://doi.org/10.1007/978-3-031-27250-9_37
Download citation
DOI: https://doi.org/10.1007/978-3-031-27250-9_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-27249-3
Online ISBN: 978-3-031-27250-9
eBook Packages: Computer ScienceComputer Science (R0)