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

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

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

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

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

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

Представлены оригинальные постановка и алгоритмы решения одной из прикладных задач теории расписаний. Рассматриваемая задача оптимального управления флотом авиакомпании заключается в таком оперативном регулировании расписаний, которое минимизирует потери авиакомпании от нарушений заданных графиков движения воздушных судов. Данная задача обладает 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.
Благодарности. Финансирование

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

Для цитирования:

Мезенцев Ю.А., Эстрайх И.В. Об одной задаче оптимального оперативного управления движением воздушных судов авиакомпании // Доклады АН ВШ РФ. – 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.

Просмотров: 49