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

Document Type : Original Article

Authors

1 Associate Professor, Islamic Azad University, Tehran North Branch

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

Abstract

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.

Keywords

Main Subjects

References

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, Interfaces, 21(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 Research, 153(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 Research, 189(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 Research, 98, 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 Research, 153(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 Manufacturing, 29(1), 35-49.
12. Fowler J.W., Wirojanagud, P., & Gel, P.S. (2008). Heuristics for workforce planning with worker differences. European Journal of Operational Research, 190(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 Research, 34(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 Research, 171(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 Research, 202(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 Engineering, 63(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 Science, 35(4), 359-374.
20. Komilakis, H., & Stamatopoulos, P. (2002). Crew pairing optimization with genetic algorithm. Lecture Notes in Computer Science, 1(1), 109-120.
21. Lourenco H., Paixao, J., & Portugal, R. (2001). Multiobjective metaheuristics for the bus-driver scheduling problem. Transportation Science, 35(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 Computation, 251, 132-142.
24. Mercier A., & Soumis, F. (2007). An integrated aircraft routing, crew scheduling and flight retiming model. Computers & Operations Research, 34(8), 2251-2265.
25. Mora-Camino, F. (2001). A bi-critertion approach for the airline crew rostering problem. Lecture Notes in Computer Science, 1(1), 93-102.
26. Ozdemir, H., & Mohan, C. (2001). Flight graph based genetic algorithm for crew scheduling in airlines. Information Sciences, 133(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 Research, 180(1), 82-98.
28. Rajagopalan H.K., & Saydam, C. (2009). A minimum expected response model: Formulation, heuristic solution, and application. Socio-Economic Planning Sciences, 43(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 Research, 199(3), 674-683.
32. Stojkovic M., Soumis, F., & Desrosiers, J. (1998). The operational airline crew scheduling problem. Transportation Science, 32(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 Research, 37(5), 833-844.
36. Wu, X., & Che, A. (2019). A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. Omega, 82, 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 Research, 169(3), 978-993.
38. Zeghal F.M., & Minoux, M. (2006). Modeling and solving a Crew Assignment Problem in air transportation. European Journal of Operational Research, 175(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.

Files

Share

How to cite

Statistics