A Multi-Objective Mathematical Formulation for the Airline Crew Scheduling Problem: MODE and NSGA-II Solution Approaches

Document Type : Original Article


1 Associate Professor, Islamic Azad University, Tehran North Branch

2 Ph.D, Industrial Engineering, Islamic Azad University, Tehran North Branch.


In this research, a multi-objective mathematical model is proposed for the airline multi-skilled crew scheduling problem. The multi-skilled crew can be assigned to flights and airplanes according to their skills. The objective functions of the proposed model are: (1) Maximizing the number of leave days planned according to the days announced by the flight crew, and (2) Minimizing the penalty costs associated with violation of minimum and maximum working hours. Several test problems have been designed based on the data acquired by the airline studied in this research. Due to the NP-hard essence of the model, we have employed two meta-heuristics, namely the multi-objective differential evolution (MODE) and Non-dominated Sorting Genetic Algorithm II (NSGA-II). These algorithms are calibrated using the Taguchi method. The algorithms have been compared based on several multi-objective performance measures. Each algorithm has been more successful in terms of some metrics. The comparisons between algorithms and sensitivity analysis show that the proposed model and algorithms can produce appropriate schedules for the airline crew scheduling problem.


Main Subjects

1. Alinezhad, A., Sabet, S.  & Ekhtiari, M. (2014). Solving Fuzzy Multiple Objective Dynamic Cellular Manufacturing System Problem using a Hybrid Algorithm of NSGA-II and Progressive Simulated Annealing. Journal of Industrial Management Perspective, 4(3), 131-156.
2. Anbil, R., Gelman, E., Patty, B., & Tanga, R. (1991). Recent Advances in Crew-Pairing Optimization at American Airlines, Interfaces21(1), 62–74.
3. Ayough, A., Zandieh, M., Farsijani, H.  & Dorri Nokarani, B. (2014). Job Rotation Scheduling in a New Arranged Lean Cell, a Genetic Algorithm Approach. Journal of Industrial Management Perspective, 4(3), 33-59.
4. Azmat, C.S., & Widmer, M. (2004). A case study of single shift planning and scheduling under annualized hours: A simple three-step approach. European Journal of Operational Research153(1), 148-175.
5. Chien C.F., Tseng, F.P., & Chen, C.H. (2008). An evolutionary approach to rehabilitation patient scheduling: A case study. European Journal of Operational Research189(3), 1234-1253.
6. Deb, K., Pratap, A., Agrawal, S., & Meyarivan, T. (2000). A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-II. IEEE Transactions on evolutionary computation, 6(2), 182-197.
7. Deveci, M., & Demirel, N.C. (2018). A Survey of the literature on airline crew scheduling. Engineering Applications of Artificial Intelligence, 74, 54-69.
8. Ding, S., Chen, C., Xin, B., & Pardalos, P.M. (2018). A bi-objective load balancing model in a distributed simulation system using NSGA-II and MOPSO approaches. Applied soft computing, 63, 249-267.
9. Eremeev, A.V (1999). A genetic algorithm with a none-binary repersentation for the set covering problem. In Proceedings of Operation Research98, 175.181.
10. Ernst, A.T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research153(1), 3-27.
11. Fan, Q., & Yan, X. (2015). Multi-objective modified differential evolution algorithm with archive-base mutation for solving multi-objective p-xylene oxidation process. Journal of Intelligent Manufacturing29(1), 35-49.
12. Fowler J.W., Wirojanagud, P., & Gel, P.S. (2008). Heuristics for workforce planning with worker differences. European Journal of Operational Research190(3), 724-740.
13. Gamache, M., Hertz, A., & Ouellet, J.O. (2007). A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding. Computers & Operations Research34(8), 2384-2395.
14. Guo Y., Mellouli, T., Suhl, L., & Thiel, M.P. (2006). A partially integrated airline crew scheduling approach with time-dependent crew capacities and multiple home bases, European Journal of Operational Research171(3), 1169-1181.
15. Ho, S.C., & Leung, J.M.Y. (2010). Solving a manpower scheduling problem for airline catering using metaheuristics. European Journal of Operational Research202(3), 903-921.
16. Hung-Tso, L., Yen-Ting, C., Tsung-Yu, C., & Yi-Chun, L. (2012). Crew rostering with multiple goals: An empirical study. Computers and Industrial Engineering63(2), 483-493.
17. Imani Imanlu, M.  & Atighehchian, A. (2017). Daily Operating Rooms Scheduling under Uncertainty using Simulation based Optimization Approach. Journal of Industrial Management Perspective, 7(2), 53-82.
18. 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.
19. Klabjan, D., Johnson, E., & Nemhauser, G. (2002). Airline crew scheduling with regularity. Transportation Science35(4), 359-374.
20. Komilakis, H., & Stamatopoulos, P. (2002). Crew pairing optimization with genetic algorithm. Lecture Notes in Computer Science1(1), 109-120.
21. Lourenco H., Paixao, J., & Portugal, R. (2001). Multiobjective metaheuristics for the bus-driver scheduling problem. Transportation Science35(3), 331-341.
22. Marchiori, E. & Steenbeek, A. (2000). An evolutionary algorithm for large scale set covering problem with application to airline crew scheduling. In Real World Application of Evolutionary Computing, LNCS (1803), 367-381.
23. Masri, H., Krichen, S., & Guitouni, A. (2015). A multi-start variable neighborhood search for solving the single path multicommodity flow problem. Applied Mathematics and Computation251, 132-142.
24. Mercier A., & Soumis, F. (2007). An integrated aircraft routing, crew scheduling and flight retiming model. Computers & Operations Research34(8), 2251-2265.
25. Mora-Camino, F. (2001). A bi-critertion approach for the airline crew rostering problem. Lecture Notes in Computer Science1(1), 93-102.
26. Ozdemir, H., & Mohan, C. (2001). Flight graph based genetic algorithm for crew scheduling in airlines. Information Sciences133(3-4), 165-173.
27. Peters E., De-Matta, R., & Boe, W. (2007). Short-term work scheduling with job assignment flexibility for a multi-fleet transport system. European Journal of Operational Research180(1), 82-98.
28. Rajagopalan H.K., & Saydam, C. (2009). A minimum expected response model: Formulation, heuristic solution, and application. Socio-Economic Planning Sciences43(4), 253-262.
29. Schneider, J., & Hull, W. (1990). Airline Crew Scheduling: Supercomputers and Algorithms. SIAM, 23(6), 165-176.
30. Schott, J.R. (1995). Fault tolerant design using single and multicriteria genetic algorithms optimization. Master's thesis, Department of Aeronautics and Astronautics, (1995), Massachusetts Institute of Technology, Cambridge, MA.
31. Souai N., & Teghem, J. (2009). Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem. European Journal of Operational Research199(3), 674-683.
32. Stojkovic M., Soumis, F., & Desrosiers, J. (1998). The operational airline crew scheduling problem. Transportation Science32(3), 232-245.
33. Storn, R., & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11, 341-359.
34. Toledo, R., Aznárez, J.J., Greiner, D., & Maeso, O. (2017). A methodology for the multi-objective shape optimization of thin noise barriers. Applied Mathematical Modelling, 50, 656-675.
35. Weide O., Ryan, D., & Ehrgott, M. (2010). An iterative approach to robust and integrated aircraft routing and crew scheduling. Computers & Operations Research37(5), 833-844.
36. Wu, X., & Che, A. (2019). A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. Omega82, 155-165.
37. Xu J., Sohoni, M., McCleery, M., & Bailey, T.G. (2006). A dynamic neighborhood based tabu search algorithm for real-world flight instructor scheduling problems. European Journal of Operational Research169(3), 978-993.
38. Zeghal F.M., & Minoux, M. (2006). Modeling and solving a Crew Assignment Problem in air transportation. European Journal of Operational Research175(1), 187-209.
39. Zitzler, E. (1999). Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. PhD. Thesis, Dissertation ETH No. 13398, Swiss Federal Institute of Technology (ETH), Zürich, Switzerland.
40. Zitzler, E., & Thiele, L. (1998). Multi-objective optimization using evolutionary algorithms a comparative case study. In: A.E. Eiben, T. Back, M. Schoenauer, H.P. Schwefel (Eds.), Fifth International Conference on Parallel Problem Solving from Nature (PPSN-V), Berlin, Germany, 292–301.