توسعه یک مدل ریاضی چندهدفه برای مسئله زمان‌بندی خدمه پرواز و حل آن توسط روش‌های MODE و NSGA-II

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشیار، دانشگاه آزاد اسلامی، واحد تهران شمال.

2 دکتری مهندسی صنایع، دانشگاه آزاد اسلامی، واحد تهران شمال.

10.52547/jimp.11.1.247

چکیده

در این پژوهش، یک مدل ریاضی چندهدفه برای مسئله زمان‌بندی خدمه پرواز چندمهارته ارائه شده است. در این مسئله، خدمه دارای دو مهارت سرمهمانداری و مهمانداری هستند و هر یک با توجه به تجربه‌ای که دارند، امکان تخصیص­ یافتن به پروازها و یا انواع هواپیما را پیدا می‌کنند. اهداف مدل پیشنهادی عبارت‌­اند از: 1. بیشینه‌سازی مجموع انطباق روزهای مرخصی بر روزهای درخواستی افراد و 2. کمینه‌سازی مجموع جریمه انحرافات از حداقل و حداکثر ساعات کاری مجاز. با توجه به NP-Hard بودن مسئله زمان‌بندی خدمه، برای حل مدل پیشنهادی از دو الگوریتم فراابتکاری تکامل تفاضلی چندهدفه (MODE) و الگوریتم ژنتیک با مرتب‌سازی غیرمغلوب نسخه دوم (NSGA-II) استفاده شده است. پارامترهای دو الگوریتم توسط روش تاگوچی تنظیم شده‌اند. دو الگوریتم بر اساس چند معیار سنجش عملکردی چندهدفه مورد­مقایسه قرار گرفتند. هر کدام از الگوریتم‌ها توانستند از نظر برخی از معیارهای سنجش عملکردی موفق‌تر عمل کنند. نتایج مقایسات الگوریتم‏‌ها و تحلیل حساسیت نشان داد که الگوریتم NSGA-II در زمان کمتر (حدود 18درصد) و کیفیت جواب‌های بهتری می‏تواند زمان‌بندی‏‌های مناسب‌تری برای مسئله زمان‌بندی خدمه پرواز ارائه کند.

کلیدواژه‌ها

موضوعات


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.