مدل ریاضی یکپارچه مسیریابی هواپیماها و زمانبندی خدمه برای خطوط هوایی با تنوع ناوگان و هاب تعمیرات

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

نویسندگان

1 گروه مهندسی صنایع، دانشگاه آزاد اسلامی واحد فیروزکوه

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

10.22054/jims.2019.27175.1925

چکیده

مسائل برنامه ریزی پرواز به طور کلی شامل چهار مسئله ( طراحی برنامه پرواز ، تخصیص ناوگان، مسیریابی هواپیماها و زمانبندی خدمه ) می باشد. در این پژوهش مدلی برای یکپارچه سازی مسیریابی هواپیماها و زمانبندی خدمه برای خطوط هوایی با تنوع ناوگان و هاب تعمیرات ارائه شده است. هدف اصلی مدل ارائه شده تعیین زنجیره‌ی پروازی برای هواپیما‌ها و تخصیص خدمه ( تیم پرواز) به تمام پروازهای هواپیماها با توجه به قوانین و مقررات در نظرگرفته شده توسط خطوط هوایی برای هواپیماها و خدمه به نحوی است، که هزینه‌های کل خطوط هوایی کمینه شود. بر خلاف مدل‌های پکپارچه سازی شده که توسط پژوهشگران پیشین در این حوزه ارائه شده است، نوع ناوگان و هاب نگهداری و تعمیرات در این پژوهش متنوع در نظر گرفته شده است. همچنین بحث کمینه کردن پرواز‌های بدون بلیت برای خدمه و هواپیما که می تواند هزینه‌های سنگینی را بر خطوط هوایی تحمیل کند به عنوان بخشی از تابع هدف در مدل ارائه شده، آورده شده است. برای حل مسئله در ابعاد کوچک از نرم افزار گمز و در ابعاد بزرگتر با توجه به پیچیده بودن مسئله و پیچیدگی محاسباتی آن، از روش فراابتکاری ژنتیک استفاده شده است. با توجه به آزمایش‌های انجام شده، الگوریتم ژنتیک پیشنهادی می تواند جوابی بهینه و یا نزدیک به بهینه را در زمانی قابل قبولی ارائه دهد.

کلیدواژه‌ها


عنوان مقاله [English]

An integrated mathematical model for aircraft routing and crew scheduling for airlines with multi fleet and multi maintenance hub

نویسندگان [English]

  • Alireza Rashidi Komijan 1
  • Amin Gordani 2
1 Department of Industrial Engineering, Islamic Azad University, Firoozkooh Branch
2 Department of Industrial Engineering, Islamic Azad University, Tehran South Branch
چکیده [English]

The problem of Airline planning has totally been divided into four sub-problems.These problems include Flight Scheduling, Fleet Assignment, Aircraft Routing, Maintenance, and Crew Scheduling. In this research, firstly, we defined basic concepts and common terminology about Airline Planning then early models and previous researchers were presenting investigated articles. Moreover, by identifying existing research gaps, an Integrated Mathematical model presented for Aircraft Routing and Crew Scheduling for Airlines with Multi Fleet and Multi Maintenance hub with considering the rules of the Airlines. The main purpose of the proposed model is to determine the flight chains for each aircraft and crew assignments to all aircrafts with the attention to the airlines rules and regulations for aircrafts and crew. In the integrated models by previous researcher in this field, usually the type of fleet is considered the same while in the model presented in this research, the type of fleet is considered different. Other innovations of this research consider several maintenance units for an airline. In addition, the minimizations of deadheading flights for crew and aircraft that can impose heavy costs to the airline is presented as a part of the objective function in the model presented. Finally, the problem has been solved into small dimensions by GAMS software and in order to solve it in the larger dimensions a meta-heuristic method is being used, such as genetics algorithm. At the end, we have presented the results, which came from meta-heuristic Algorithm and GAMS Software.

کلیدواژه‌ها [English]

  • Aircraft Routing and Maintenance
  • Crew Scheduling
  • Multi Fleet
  • Multi Maintenance hub
  • Genetics Algorithm
حسینی ، سید زمان  . علیرضا ، رشیدی کمیجان (1395) ، ارائه مدل ریاضی و روش حل برای زمان بندی مجدد پروازها در شرایط مجاز بودن امکان جابجائی فرودگاه قطب و کمبود ناوگان هواپیمائی ، مجموعه مقالات کنفرانس بین المللی مهندسی صنایع و مدیریت پایدار اصفهان، شماره 1125 .

2. علیرضا ، رشیدی کمیجان . مهسا ، شبانکاره (1396) ، مدل ریاضی تخصیص ناوگان، همراه با زمان بندی فعالیت های تعمیر ، نگهداری و رمپینگ هواپیما ، نشریۀ تخصصی مهندسی صنایع، دورۀ 25 ، شمارۀ 1.

3. ناصر علوی ، سید صابر (1388)، برنامه ریزی پرواز با روش های بهینه یابی  جستجویی ، پژوهشنامه حمل و نقل ، سال ششم ، شماره دوم .

4. Abara, J. 1989. Applying integer linear programming to the fleet assignment problem. Interfaces 19 211–232.

5. Barnhart, C. et al. (1998). Flight strings models for aircraft fleeting and routing. Transportation Science, 32(3).

6. Bazargan,M.,(2010)“Airline Operations and Scheduling”, 2ND Edition, Embry-Riddle Aeronautical University ,USA,Burlington, ASHGATE Publication.

7. Cordeau, J., Stojkovic, G., Soumis, F., Desrosiers, J., 2001. Benders decomposition for simultaneous aircraft routing and crew scheduling. Transportation Science 35 (4), 375–388.

8. De Falco , A. Della Cioppa , E. Tarantino, Mutation-based genetic algorithm: performance evaluation , Applied Soft Computing 1 (2002) 285–299 .

9. Dunbar, M., Froyland, G., Wu, C.-L., 2012. Robust airline schedule planning: minimizing propagated delay in an integrated routing and crewing framework. Transportation Science 46 (2), 204–216.

10. J.E. Beasley , RC. Chu, A genetic algorithm for the set covering problem, European Journal of Operational Research 94 (1996) 392-404.

11.  Jenny Díaz - Ramírez Aircraft maintenance, routing, and crew scheduling planning for airlines with a single fleet and a single maintenance and crew base. Computers & Industrial Engineering 75 (2014) 68–78.

12. Juan-José Salazar-González , Approaches to solve the fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems of a regional carrier , Omega 43 (2014) 71–82.

13. Loo Hay Lee, Chul Ung Lee, Yen Ping Tan, A multi-objective genetic algorithm for robust flight scheduling using simulation, European Journal of Operational Research 177 (2007) 1948–1968

14. Nadia Souai , Jacques Teghem, Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem , European Journal of Operational Research 199 (2009) 674–683 .

15. Papadakos, N. (2009). Integrated airline scheduling. Computers & Operations Research, 36(1), 176–195.

16. Sandhu, R., & Klabjan, D. (2007). Integrated airline fleeting and crew pairing decisions. Operations Research, 55, 430–438.

17. Shao, S., Sherali, H.D., Haouari, M., 2015. A novel model and decomposition approach for the integrated airline fleet assignment, aircraft routing,and crew pairing problem.

18, Chiu-Hung Chen, Jyh-Horng Chou , Optimization of short-haul aircraft schedule recovery problems using a hybrid multiobjective genetic algorithm, Expert Systems with Applications 37 (2012) 2307–2315 .

19. Valentina Cacchiani , A heuristic approach for an integrated fleet-assignment, aircraft-routing and crew-pairing problem , Electronic Notes in Discrete Mathematics 41 (2013) 391–398 .

20. Xiaoge Zhang, Sankaran Mahadevan , Aircraft re-routing optimization and performance assessment under uncertainty , Decision Support Systems 96 (2017) 67–82 .

21. Hüseyin Gürkan , Sinan Gürel , M. Selim Aktürk, An integrated approach for airline scheduling, aircraft fleeting and routing with cruise speed control , Transportation Research Part C 68 (2016) 38–57 .

22. J.H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.

23. Taguchi G, Konishi S ,Taguchi Methods, orthogonal arrays and linear graphs, tools for quality American supplier institute, American Supplier Institute; 1987 [p. 8-35].

24. Jamili, A., A robust mathematical model and heuristic algorithms for integrated - aircraft routing and scheduling, with consideration of fleet assignment problem Journal of Air Transport Management 58 (2016) 21 – 30.

25. Mohamed Ben Ahmed , Wisal Ghroubi , Mohamed Haouari , Hanif Sherali , A hybrid optimization-simulation approach for robust weeklyaircraft routing and retiming , Transportation Research Part C 84 (2017) 1–20 .

26. Yuzhen Hu , Hong Liao , Song Zhang , Yan Song, Multiple objective solution approaches for aircraft rerouting under the disruption of multi-aircraft , Expert Systems With Applications 83 (2017) 283–299 .