phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2022 - 3 issue » pp. 433-446

Archive of Issues

Russia Yekaterinburg
Year
2022
Volume
32
Issue
3
Pages
433-446
<<
>>
Section Mathematics
Title Keeping order of vessels in problem of safe merging aircraft flows
Author(-s) Spiridonov A.A.a, Kumkov S.S.a
Affiliations Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa
Abstract Nowadays, the problem of creating an optimal safe schedule for arrival of aircraft coming in several flows to a checkpoint, where these flows join into one, is very important for air-traffic management. Safety of the resultant queue is present if there is a safe interval between neighbor arrivals to the merge point. Change of an arrival instant of an aircraft is provided by changing its velocity and/or usage of fragments of the air-routes scheme, which elongate or shorten the aircraft path. Optimality of the resultant queue is considered from the point of some additional demands: minimization of the deviation of the actual aircraft arrival instant from the nominal one, minimization of order changes in the resultant queue in comparison with the original one, minimization of fuel expenditures, etc. The optimality criterion to be minimized, which reflects these demands, is often taken as a sum of penalties for deviations of the assigned arrival instants from the nominal ones. Each individual penalty is considered in almost all papers as either the absolute value of the difference between the assigned and nominal arrival instants or a similar function with asymmetric branches (which punishes delays and accelerations of an aircraft in different ways). The problem can be divided into two subproblems: one is a search for an optimal order of aircraft in the resultant queue, and the other is a search for optimal arrival instants for a given order. The second problem is quite simple since it can be formalized in the framework of linear programming and solved quite efficiently. However, the first one is very difficult and now is solved by various methods. The paper suggests sufficient conditions for the problem, which guarantee that the order of the optimal assigned instants is the same as the order of the nominal ones and, therefore, exclude the first subproblem.
Keywords aircraft, airway merge point, non-conflict flows merging, nominal arrival instants, assigned arrival instants, joined aircraft queue
UDC 519.852.3
MSC 90C05, 90C90, 90-10
DOI 10.35634/vm220306
Received 29 March 2022
Language English
Citation Spiridonov A.A., Kumkov S.S. Keeping order of vessels in problem of safe merging aircraft flows, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2022, vol. 32, issue 3, pp. 433-446.
References
  1. Bayen A., Callantine T., Tomlin C., Ye Y., Zhang J. Optimal arrival traffic spacing via dynamic programming, AIAA Guidance, Navigation, and Control Conference and Exhibit, American Institute of Aeronautics and Astronautics, 2004, pp. 2232-2242. https://doi.org/10.2514/6.2004-5228
  2. Beasley J.E., Krishnamoorthy M., Sharaiha Y.M., Abramson D. Scheduling aircraft landings - the static case, Transportation Science, 2000, vol. 34, no. 2, pp. 180-197. https://doi.org/10.1287/trsc.34.2.180.12302
  3. Bennell J.A., Mesgarpour M., Potts C.N. Airport runway scheduling, 4OR, 2011, vol. 9, issue 2, pp. 115-138. https://doi.org/10.1007/s10288-011-0172-x
  4. Bennell J.A., Mesgarpour M., Potts C.N. Airport runway scheduling, Annals of Operations Research, 2013, vol. 204, issue 1, pp. 249-270. https://doi.org/10.1007/s10479-012-1268-1
  5. Bennell J.A., Mesgarpour M., Potts C.N. Dynamic scheduling of aircraft landings, European Journal of Operational Research, 2017, vol. 258, no. 1, pp. 315-327. https://doi.org/10.1016/j.ejor.2016.08.015
  6. Bianco L., Rinaldi G., Sassano A. A combinatorial optimization approach to aircraft sequencing problem, Flow Control of Congested Networks, Berlin-Heidelberg: Springer, 1987, pp. 323-339. https://doi.org/10.1007/978-3-642-86726-2_20
  7. Boursier L., Favennec B., Hoffman E., Trzmiel A., Vergne F., Zeghal K. Merging arrival flows without heading instructions, 7th USA/Europe Air Traffic Management Research and Development Seminar 2007, Curran Associates, 2015, pp. 403-410.
  8. d'Apice C., de Nicola C., Manzo R., Moccia V. Optimal scheduling for aircraft departures, Journal of Ambient Intelligence and Humanized Computing, 2014, vol. 5, issue 6, pp. 799-807. https://doi.org/10.1007/s12652-014-0223-1
  9. d'Ariano A., Pacciarelli D., Pistelli M., Pranzo M. Real-time scheduling of aircraft arrivals and departures in a terminal maneuvering area, Networks, 2015, vol. 65, issue 3, pp. 212-227. https://doi.org/10.1002/net.21599
  10. Eltoukhy A.E.E., Chan F.T.S., Chung S.H. Airline schedule planning: a review and future directions, Industrial Management and Data Systems, 2017, vol. 117, issue 6, pp. 1201-1243. https://doi.org/10.1108/IMDS-09-2016-0358
  11. Hong Y., Choi B., Kim Y. Two-stage stochastic programming based on particle swarm optimization for aircraft sequencing and scheduling, IEEE Transactions on Intelligent Transportation Systems, 2019, vol. 20, issue 4, pp. 1365-1377. https://doi.org/10.1109/TITS.2018.2850000
  12. Liang M., Delahaye D., Maréchal P. Integrated sequencing and merging aircraft to parallel runways with automated conflict resolution and advanced avionics capabilities, Transportation Research. Part C: Emerging Technologies, 2017, vol. 85, pp. 268-291. https://doi.org/10.1016/j.trc.2017.09.012
  13. Lieder A., Briskorn D., Stolletz R. A dynamic programming approach for the aircraft landing problem with aircraft classes, European Journal of Operational Research, 2015, vol. 243, issue 1, pp. 61-69. https://doi.org/10.1016/j.ejor.2014.11.027
  14. Lieder A., Stolletz R. Scheduling aircraft take-offs and landings on interdependent and heterogeneous runways, Transportation Research. Part E: Logistics and Transportation Review, 2016, vol. 88, pp. 167-188. https://doi.org/10.1016/j.tre.2016.01.015
  15. Montoya J., Rathinam S., Wood Z. Multiobjective departure runway scheduling using dynamic programming, IEEE Transactions on Intelligent Transportation Systems, 2014, vol. 15, issue 1, pp. 399-413. https://doi.org/10.1109/TITS.2013.2283256
  16. Salehipour A. An algorithm for single- and multiple-runway aircraft landing problem, Mathematics and Computers in Simulation, 2020, vol. 175, pp. 179-191. https://doi.org/10.1016/j.matcom.2019.10.006
  17. Simão H.P., Day J., George A.P., Gifford T., Nienow J., Powell W.B. An approximate dynamic programming algorithm for large-scale fleet management: A case application, Transportation Science, 2009, vol. 43, issue 2, pp. 178-197. https://doi.org/10.1287/trsc.1080.0238
  18. Solak S., Solveling G., Clarke J.-P.B., Johnson E.L. Stochastic runway scheduling, Transportation Science, 2018, vol. 52, issue 4, pp. 917-940. https://doi.org/10.1287/trsc.2017.0784
  19. Sölveling G., Clarke J.-P. Scheduling of airport runway operations using stochastic branch and bound methods, Transportation Research. Part C: Emerging Technologies, 2014, vol. 45, pp. 119-137. https://doi.org/10.1016/j.trc.2014.02.021
  20. Soomer M.J., Franx G.J. Scheduling aircraft landings using airlines' preferences, European Journal of Operational Research, 2008, vol. 190, issue 1, pp. 277-291. https://doi.org/10.1016/j.ejor.2007.06.017
  21. Veresnikov G.S., Egorov N.A., Kulida E.L., Lebedev V.G. Methods for solving of the aircraft landing problem. I. Exact solution methods, Automation and Remote Control, 2019, vol. 80, issue 7, pp. 1317-1334. https://doi.org/10.1134/S0005117919070099
  22. Veresnikov G.S., Egorov N.A., Kulida E.L., Lebedev V.G. Methods for solving of the aircraft landing problem. II. Approximate solution methods, Automation and Remote Control, 2019, vol. 80, issue 8, pp. 1502-1518. https://doi.org/10.1134/S0005117919080101
  23. Vié M.S., Zufferey N., Leus R. Aircraft landing planning: past, present and future, Proceedings of the 19th annual congress of the french operations research society, 2018. https://archive-ouverte.unige.ch/unige:104854
  24. Xu B. An efficient Ant Colony algorithm based on wake-vortex modeling method for aircraft scheduling problem, Journal of Computational and Applied Mathematics, 2017, vol. 317, pp. 157-170. https://doi.org/10.1016/j.cam.2016.11.043
  25. Zulkifli A., Aziz N.A.A., Aziz N.H.A., Ibrahim Z., Mokhtar N. Review on computational techniques in solving aircraft landing problem, Proceedings of International Conference on Artificial Life and Robotics, 2018, vol. 23, pp. 128-131. https://doi.org/10.5954/ICAROB.2018.GS5-3
Full text
/doc/issues-2022/22-03-06.pdf
<< Previous article
Next article >>