ДОКЛАДЫ АКАДЕМИИ НАУК
ВЫСШЕЙ ШКОЛЫ РОССИЙСКОЙ ФЕДЕРАЦИИ

Представлены оригинальные постановка и алгоритмы решения одной из прикладных задач теории расписаний. Рассматриваемая задача оптимального управления флотом авиакомпании заключается в таком оперативном регулировании расписаний, которое минимизирует потери авиакомпании от нарушений заданных графиков движения воздушных судов. Данная задача обладает NP-полнотой и не может быть решена точно для сколько-нибудь реальных размерностей. Предложен параметрический эффективный алгоритм ее приближенного решения, являющийся расширением подобного алгоритма оптимизации расписаний системы несвязанных параллельных приборов с задержками начала обслуживания по критерию быстродействия (С_max). Параметр алгоритма задает число анализируемых промежуточных вариантов расписания на каждом шаге и соответственно число отсеиваемых локально наихудших вариантов. Это позволяет гибко регулировать общую трудоемкость и точность получаемых корректирующих расписаний. Приведены содержательный пример применения алгоритма и статистика его тестирования на данных порождающей задачи по критерию С_max. В дополнение к параметрическому алгоритму предложен улучшающий обменный алгоритм, позволяющий на завершающих шагах параметрического алгоритма конструировать улучшенные по критерию С_max расписания. Приведены результаты вычислительных экспериментов с применением обоих алгоритмов на сгенерированных примерах приближенных к реальным размерностей, которые показали высокую общую эффективность подхода.

1. Grönkvist M. The tail assignment problem: Thesis for the degree of Doctor of Philosophy / Chalmers University of Technology and Göteborg University. – Göteborg, Sweden, 2005. – 276 p.
2. Sherali H.D., Bish E.K., Zhu X. Airline fleet assignment concepts, models and algorithms // European Journal of Operational Research. – 2006. – Vol. 172, N 1. – P. 1–30.
3. The fleet assignment problem: solving a large-scale integer program / C.A. Hane, C. Barnhart, E.L. Johnson, R.E. Marsten, G.L. Nemhauser, and G. Sigismondi // Mathematical Programming. – 1995. – Vol. 70, N 1–3. – P. 211–232.
4. Some properties of the fleet assignment problem / Z. Gu, E.L. Johnson, G.L. Nemhauser, and Y. Wang // Operations Research Letters. – 1994. – Vol. 15, N 2. – P. 59–71.
5. Coldstart: fleet assignment at delta air lines / R. Subramanian, R.P. Scheff, J.D. Quillinan, D.S. Wiper, and R.E. Marsten // Interfaces. – 1994. – Vol. 24, N 1. – P. 104–120.
6. Ozdemir Y., Basligil H., Nalbant K.G. Optimization of fleet assignment: a case study in Turkey // An International Journal of Optimization and Control: Theories & Applications. – 2012. – Vol. 2, N 1. – P. 59–71.
7. Blegur F.M.A., Bakhtiar T., Aman A. Scenarios for fleet assignment: a case study at Lion Air // IOSR Journal of Mathematics. – 2014. – Vol. 10, iss. 5. – P. 64–68.
8. Kabbani N.M., Patty B.W. Aircraft routing at American airlines // Proceedings of the Thirty-Second Annual Symposium of AGIFORS. – Budapest, Hungary, 1992. – P. 12–28.
9. The aircraft rotation problem / L.W. Clarke, E.L. Johnson, G.L. Nemhauser, and Z. Zhu // Annals of Operations Research. – 1997. – Vol. 69. – P. 33–46.
10. Benders decomposition for simultaneous aircraft routing and crew scheduling /
    
    J.-F. Cordeau, G. Stojkovi´c, F. Soumis, and J. Desrosiers // Transportation Science. –
    
    2001. – Vol. 35, N 4. – P. 375–388.
11. Flight string models for aircraft fleeting and routing / C. Barnhart, N.L. Boland, L.W. Clarke, E.L. Johnson, G.L. Nemhauser, and R.G. Shenoi // Transportation Science. – 1998. – Vol. 32, N 3. – P. 208–220.
12. Elf M., Jünger M., Kaibel V. Rotation planning for the continental service of a European airline // Mathematics – Key Technologies for the Future. – Berlin; Heidelberg: Springer, 2003. – P. 675–689.
13. Sarac A., Batta R., Rump C.M. A branch-and-price approach for operational aircraft maintenance routing // European Journal of Operational Research. – 2006. – Vol. 175, N 3. – P. 1850–1869.
14. Gopalan R., Talluri K.T. The aircraft maintenance routing problem // Operations Research. – 1998. – Vol. 46, N 2. – P. 260–271.
15. A very large-scale neighborhood search algorithm for the combined through–fleet–assignment model / R.K. Ahuja, J. Goodstein, A. Mukherjee, J.B. Orlin, D. Sharma // INFORMS Journal on Computing. – 2007. – Vol. 19, N 3. – P. 416–428.
16. A network airline revenue management framework based on decomposition by origins and destinations / S.I. Birbil, J.B.G. Frenk, J.A.S. Gromicho, S. Zhang // Transportation Science. – 2013. – Vol. 48, N 3. – P. 313–333.
17. Yan S., Tseng C.-H. A passenger demand model for airline flight scheduling and fleet routing // Computers & Operations Research. – 2002. – Vol. 29, N 11. – P. 1559–1581.
18. Sandhu R., Klabjan D. Integrated airline fleeting and crew-pairing decisions // Operations Research. – 2007. – Vol. 55, N 3. – P. 439–456.
19. Rakshit A., Krishnamurty N., Yu G. System operations advisor: a real-time decision support system for managing airline operations at United Airlines // Interfaces. – 1996. – Vol. 26, N 2. – P. 50–58.
20. Lettovsky L. Airline operations recovery: an optimization approach: PhD thesis / School of Industrial & Systems Engineering, Georgia Institute of Technology. – Atlanta, GA, USA, 1997. – 271 p.
21. Airline disruption management – perspectives, experiences and outlook / N. Kohl, A. Larsen, J. Larsen, A. Ross, S. Tiourine // Journal of Air Transport Management. – 2007. – Vol. 13, N 3. – P. 149–162.
22. Rosenberger J.M. Topics in airline operations: PhD thesis / School of Industrial & Systems Engineering, Georgia Institute of Technology. – Atlanta, GA, USA, 2002. – 265 p.
23. Мезенцев Ю.А. оптимизация расписаний параллельных динамических систем в календарном планировании // Информационные технологии. – 2008. – № 2. – С. 24–33.
24. Avdeenko T.V., Mezentsev Yu.A. Efficient approaches to scheduling for unrelated parallel machines with release dates // IFAC-Papers Online. – 2016. – Vol. 49, iss. 12. – P. 1743–1748.
25. Avdeenko T.V., Mezentsev Yu.A., Estraykh I.V. Heuristic approach to unrelated parallel machines scheduling under availability and resource constraints // IFAC-PapersOnline. – 2017. – Vol. 50, iss. 1. – P. 13096–13101.
26. Mezentsev Yu.A., Estraykh I.V. Problems and optimization algorithms of schedules of parallel-serial systems with undefined service routes // Abstracts of the International Conference “Constructive Nonsmooth Analysis and Related Topics”. – St. Petersburg, 2017. – Pt. 2. – P. 79–83.
27. Mezentsev Yu.A. Binary cut-and-branch method for solving linear programming problems with boolean variables // Proceedings DOOR 2016. – Vladivostok, 2016. – Vol. 1623. – P. 72–85.
28. Mezentsev Yu.A. Binary cut-and-branch method for solving mixed integer programming problems // Abstracts of the International Conference “Constructive Nonsmooth Analysis and Related Topics”. – St. Petersburg, 2017. – Pt. 2. – P. 74–78.