Доклады АН ВШ РФ

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

Print ISSN: 1727-2769    Online ISSN: 2658-3747
English | Русский

Последний выпуск
№3(72) июль-сентябрь 2026

Об одной задаче оптимального оперативного управления движением воз-душных судов авиакомпании

Выпуск № 3 (40) июль-сентябрь 2018
Авторы:

Мезенцев Юрий Анатольевич ,
Эстрайх Игорь Викторович ,
DOI: http://dx.doi.org/10.17212/1727-2769-2018-3-74-90
Аннотация

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


Ключевые слова: оптимальное регулирование расписаний, назначения флота воздушных судов, критерий быстродействия, эффективный параметрический алгоритм, дискретная оптимизация
Мезенцев Юрий Анатольевич
д-р техн. наук, профессор кафедры автоматизированных систем управления НГТУ. Область научных интересов: задачи и методы дискретного программирования. Опубликовано 65 научных работ. (Адрес: 630073, Россия, Новосибирск, пр. Карла Маркса,
• E-mail: ).

mezencev@corp.nstu.ru
Orcid:

Эстрайх Игорь Викторович
старший преподаватель кафедры автоматизированных систем управления НГТУ. Область научных интересов: задачи и методы дискретного программирования. Опубликовано 9 научных работ. (Адрес: 630073, Россия, Новосибирск, пр. Карла Маркса,
• E-mail: ).

estrajx@corp.nstu.ru
Orcid:

Список литературы
  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.
Благодарности. Финансирование

Исследование выполнено при финансовой поддержке Министерства науки и высшего образования РФ (проект \No~2.2327.2017/PCh); НГТУ (темплан НИР НГТУ), проект
ТП-ЭИ-1_17.

Просмотров аннотации: 2264
Скачиваний полного текста: 915
Просмотров интерактивной версии: 0
Для цитирования:

Мезенцев Ю.А., Эстрайх И.В. Об одной задаче оптимального оперативного управления движением воздушных судов авиакомпании // Доклады АН ВШ РФ. – 2018. – № 3 (40). – C. 74–90. doi: 10.17212/1727-2769-2018-3-74-90

For citation:

Mezentsev Yu.A., Estraykh I.V. Ob odnoi zadache optimal'nogo operativnogo upravleniya dvizheniem vozdushnykh sudov aviakompanii [An optimal fleet assignment and flight scheduling problem for an airline company]. Doklady Akademii nauk vysshei shkoly Rossiiskoi Federatsii – Proceedings of the Russian higher school Academy of sciences, 2018, no. 3 (40), pp. 74–90. doi: 10.17212/1727-2769-2018-3-74-90.

 

Обработка персональных данных

Мы используем сервис веб-аналитики Яндекс Метрика, который использует cookie.

Собранная при помощи cookie информация не может идентифицировать вас, однако может помочь нам улучшить работу нашего сайта. Вы можете отказаться от использования cookies, выбрав соответствующие настройки в браузере. Также Вы можете запретить сбор данных с помощью расширения для браузера «Блокировщик Яндекс Метрики». Используя этот сайт, вы соглашаетесь на обработку персональных данных.