An integrated crew scheduling problem considering reserve crew in air transportation: Ant colony optimization algorithm

Subject Areas : Business and Marketing

Saeed Saemi ¹ , Alireza Rashidi Komijan ² , Reza Tavakkoli-Moghaddam ³ , Mohammad Fallah ⁴

1 - Department of Industrial Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran
2 - Islamic Azad University, Firoozkoh Branch
3 - North Karegar Street School of Industrial Engineering, College of Engineering, University of Tehran
4 - Department of Industrial Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran

Received: 2021-08-11 Accepted : 2022-04-11 Published : 2022-09-01

Keywords: Combinatorial optimization, Multiple objective programming, Metaheuristics, Crew Planning, Air transport,

Abstract :

A Crew Scheduling Problem (CSP) is a highly complex airline optimization problem, which includes two sub-problems, namely Crew Rostering Problem (CRP) and Crew Pairing Problem (CPP). Solving these problems sequentially may not lead to an optimal solution. To overcome this shortcoming, the present study introduces a new bi-objective formulation for the integrating CPP and CRP by considering the reserve crew with the objectives of crew cost minimization and crew reserve maximization. The integrated model generates and assigns pairings to a group of crew members by taking into account the rules and regulations about employing the manpower (i.e., crew member) and crew reservation in order to reduce flight delays or even cancellations due to the unexpected disruptions. An Ant Colony Optimization (ACO) algorithm is used to solve the considered problem. To justify the efficiency of this proposed algorithm in solving the presented model, different test problems are generated and solved by ACO and GAMS. The computational results indicate that solutions obtained by the proposed ACO algorithm have a 2.57% gap with the optimal solutions reported by GAMS as optimization software on average and significantly less CPU time for small-sized problems. Also, ACO obtains better solutions in significantly shorter CPU time for large-sized problems. The results indicate the efficient performance of the proposed algorithm in solving the given problems.

References:

Aggarwal, D., Saxena, D. K., Emmerich, M., & Paulose, S.S (2018). On large-scale airline crew pairing generation. In: Proceedings of the 2018 IEEE Symposium Series on Computational Intelligence (SSCI),  Bangalore, India, 18-21, 593-600.

AhmadBeygi, S., Cohn, A., & Weir, M. (2009). An integer programming approach to generating airline crew pairings. Computers & Operations Research, 36(4), 1284-1298.

Aydemir-Karadag, A., Dengiz, B., & Bolat, A. (2013). Crew pairing optimization based on hybrid approaches. Computers & Industrial Engineering, 65(1), 87-96.

Azadeh, A., Farahani, M. H., Eivazy, H., Nazari-Shirkouhi, S., & Asadipour, G. (2013). A hybrid meta-heuristic algorithm for optimization of crew scheduling. Applied Soft Computing, 13(1), 158-164.

Barnhart, C. (2008). Airline scheduling: Accomplishments, opportunities and challenges. In International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming (pp. 1-1). Springer, Berlin, Heidelberg.

Bayliss, C., De Maere, G., Atkin, J. A., & Paelinck, M. (2017). A simulation scenario based mixed integer programming approach to airline reserve crew scheduling under uncertainty. Annals of Operations Research, 252(2), 335-363.

Bayliss, C., De Maere, G., Atkin, J., & Paelinck, M. (2012). Probabilistic airline reserve crew scheduling model. In D. Delling & L. Liberti (Eds.), In: Proceedings of the 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS). Ljubljana, Slovenia, 13 September 2012. 132–143.

Bazargan, M. (2016). Airline operations and scheduling. London: Routledge.

De Armas, J., Cadarso, L., Juan, A. A., & Faulin, J. (2017). A multi-start randomized heuristic for real-life crew rostering problems in airlines with work-balancing goals. Annals of Operations Research, 258(2), 825-848.

Dehnavi-Arani, S., Sabaghian, A., & Fazli, M. (2019). A Job shop scheduling and location of battery charging storage for the automated guided vehicles (AGVs). Journal of Optimization in Industrial Engineering, 12(2), 121-129.

Deng, G. F., & Lin, W. T. (2011). Ant colony optimization-based algorithm for airline crew scheduling problem. Expert Systems with Applications, 38(5), 5787-5793.

Doi, T., Nishi, T., & Voß, S. (2018). Two-level decomposition-based matheuristic for airline crew rostering problems with fair working time. European Journal of Operational Research, 267(2), 428-438.

Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29-41.

Enayati, M., Asadi-Gangraj, E., & Paydar, M. M. (2021). Scheduling on flexible flow shop with cost-related objective function considering outsourcing options. Journal of Optimization in Industrial Engineering, 14(2), 53-72.

Erdoğan, G., Haouari, M., Matoglu, M. Ö., & Özener, O. Ö. (2015). Solving a large-scale crew pairing problem. Journal of the Operational Research Society, 66(10), 1742-1754.

Hadianti, R., Novianingsih, K., Uttunggadewa, S., Sidarto, K. A., Sumarti, N., & Soewono, E. (2013). Optimization model for an airline crew rostering problem: Case of Garuda Indonesia. Journal of Mathematical and Fundamental Sciences. 45: 218-234.

Haouari, M., Zeghal Mansour, F., & Sherali, H. D. (2019). A new compact formulation for the daily crew pairing problem. Transportation Science, 53(3), 811-828.

Kasirzadeh, A., Saddoune, M., & Soumis, F. (2017). Airline crew scheduling: models, algorithms, and data sets. EURO Journal on Transportation and Logistics, 6(2), 111-137.

Klabjan, D., Johnson, E. L., Nemhauser, G. L., Gelman, E., & Ramaswamy, S. (2001). Solving large airline crew scheduling problems: Random pairing generation and strong branching. Computational Optimization and Applications, 20(1), 73-91.

Kohl, N., & Karisch, S. E. (2004). Airline crew rostering: Problem types, modeling, and optimization. Annals of Operations Research, 127(1), 223-257.

Maenhout, B., & Vanhoucke, M. (2010). A hybrid scatter search heuristic for personalized crew rostering in the airline industry. European Journal of Operational Research, 206(1), 155-167.

Ozdemir, H. T., & Mohan, C. K. (2001). Flight graph based genetic algorithm for crew scheduling in airlines. Information Sciences, 133(4), 165-173.

Quesnel, F., Desaulniers, G., & Soumis, F. (2017). A new heuristic branching scheme for the crew pairing problem with base constraints. Computers & Operations Research, 80, 159-172.

Quesnel, F., Desaulniers, G., & Soumis, F. (2020). Improving air crew rostering by considering crew preferences in the crew pairing problem. Transportation Science, 54(1), 97-114.

Rashidi Komijan, A., Ghasemi, P., Khalili-Damghani, K., & HashemiYazdi, F. (2021a). A new school bus routing problem considering gender separation, special students and mix loading: a genetic algorithm approach. Journal of Optimization in Industrial Engineering, 14(2), 23-39.

Rashidi Komijan, A., Tavakkoli-Moghaddam, R., & Dalil, S. A. (2021b). A mathematical model for an integrated airline fleet assignment and crew scheduling problem solved by vibration damping optimization. Scientia Iranica, 28(2), 970-984.

Saddoune, M., Desaulniers, G., Elhallaoui, I., & Soumis, F. (2012). Integrated airline crew pairing and crew assignment by dynamic constraint aggregation. Transportation Science, 46(1), 39-55.

Saemi, S., Komijan, A. R., Tavakkoli-Moghaddam, R., & Fallah, M. (2021). A new mathematical model to cover crew pairing and rostering problems simultaneously. Journal of Engineering Research, 9(2).

Saemi, S., Komijan, A. R., Tavakkoli-Moghaddam, R., & Fallah, M. (2022). Solving an integrated mathematical model for crew pairing and rostering problems by an ant colony optimisation algorithm. European Journal of Industrial Engineering, 16(2), 215-240.

Santosa, B., Sunarto, A., & Rahman, A. (2010). Using differential evolution method to solve crew rostering problem. Applied Mathematics. 1: 316-325.

Shafipour-Omrani, B., Komijan, A. R., Sadjadi, S. J., Khalili-Damghani, K., & Ghezavati, V. (2021). "A flexible mathematical model for crew pairing optimization to generate n-day pairings considering the risk of COVID-19: a real case study", Kybernetes, Vol. ahead-of-print No. ahead-of-print. https://doi.org/10.1108/K-02-2021-0127.

Shebalov, S., & Klabjan, D. (2006). Robust airline crew pairing: Move-up crews. Transportation science, 40(3), 300-312.

Sohoni, M. G., Johnson, E. L., & Bailey, T. G. (2006). Operational airline reserve crew planning. Journal of Scheduling, 9(3), 203-221.

Taguchi, G., Chowdhury, S., & Wu, Y. (2005). Taguchi's quality engineering handbook. Wiley.

Zeren, B., & Ozkol, I. (2012). An improved genetic algorithm for crew pairing optimization. Journal of Intelligent Learning Systems and Applications. 4: 70-80.

Zeren, B., & Özkol, I. (2016). A novel column generation strategy for large scale airline crew pairing problems. Expert Systems with Applications, 55, 133-144.